Title: A novel computationally tractable algorithm for discovering probabilistic graphical models in high-dimensional data
Authors: Edith Alice Kovacs - University of Debrecen (Hungary) [presenting]
Noemi Horvath - Budapest University of Technology and Economics (Hungary)
Roland Molontay - Budapest University of Technology and Economics (Hungary)
Abstract: Revealing the dependence structure in high dimensional distributions has attracted a lot of research interest recently. We introduce a procedure that aims to reduce redundancy between random variables by exploiting conditional independences using only low-dimensional marginal probability distributions in the approximation task. The basis is a previous method and its generalization - the cherry tree. The first model uses only two-dimensional marginal probability distributions in the approximation of the high dimensional probability distributions, while the latter uses typically three-, four- or five-dimensional marginals. It has been shown that the cherry tree probability distributions give better approximation than the Chow-Liu algorithm does. However, fitting cherry tree probability distributions to the sample data is computationally much more expensive, in high dimensions (greater than 50) it may even be intractable. A computationally more tractable method for modeling probability distributions by cherry trees will be presented. We prove that the new algorithm also provides a better approximation than Chow-Liu does. We also give some numerical results to illustrate the effectiveness of our new method.