Towards sub-quadratic learning of probability density models in the form of mixtures of trees
François Schnitzler, Philippe LERAY, Louis A. Wehenkel · Open Repository and Bibliography (University of Liège) · 2010
Abstract. We consider randomization schemes of the Chow-Liu algorithm from weak (bagging, of quadratic complexity) to strong ones (full random sampling, of linear complexity), for learning probability density models in the form of mixtures of Markov trees. Our empirical study on high-dimensional synthetic problems shows that, while bagging is the most accurate scheme on average, some of the stronger randomizations remain very competitive in terms of accuracy, specially for small sample sizes. 1 Background and motivations A bayesian network (BN) over a finite set X = {Xi} n i=1 of n discrete random variables is a graphical probabilistic model consisting of two parts [1]. The first is a directed acyclic graph over the variables (each variable corresponds to a vertex in this graph). The second is a set of conditional probability distributions (for each variable Xi, conditionally to its parents in the graph). A BN encodes a joint distribution over X by the product of these conditional distributions, and it may be exploited to perform probabilistic inferences over that distribution.