Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algorithm

The present work analyzes different randomized methods to learn Markov tree mixtures
for density estimation in very high-dimensional discrete spaces (very large number n of
discrete variables) when the sample size (N ) is very small compared to n. Several sub-
quadratic relaxations of the Chow-Liu algorithm are proposed, weakening its search proce-
dure. We first study na¨ıve randomizations and then gradually increase the deterministic
behavior of the algorithms by trying to focus on the most interesting edges, either by
retaining the best edges between models, or by inferring promising relationships between
variables. We compare these methods to totally random tree generation and randomiza-
tion based on bootstrap-resampling (bagging), of respectively linear and quadratic com-
plexity. Our results show that randomization becomes increasingly more interesting for
smaller N/n ratios, and that methods based on simultaneously discovering and exploiting
the problem structure are promising in this context.