Estimating Mixture Models via Mixtures of Polynomials
Mixture modeling is a general technique for making any simple model more expressive through weighted combination. This generality and simplicity in part explains the success of the Expectation Maximization (EM) algorithm, in which updates are easy to derive for a wide class of mixture models. However, the likelihood of a mixture model is non-convex, so EM has no known global convergence guarantees. Recently, method of moments approaches offer global guarantees for some mixture models, but they do not extend easily to the range of mixture models that exist. In this work, we present Polymom, an unifying framework based on method of moments in which estimation procedures are easily derivable, just as in EM. Polymom is applicable when the moments of a single mixture component are polynomials of the parameters. Our key observation is that the moments of the mixture model are a mixture of these polynomials, which allows us to cast estimation as a Generalized Moment Problem. We solve its relaxations using semidefinite optimization, and then extract parameters using ideas from computer algebra. This framework allows us to draw insights and apply tools from convex optimization, computer algebra and the theory of moments to study problems in statistical estimation. Simulations show good empirical performance on several models.
The paper presents a general framework for deriving methods of moments for learning mixture models. Its main contributions are: (1) showing how expressions for the moments of the base distribution can be bootstrapped to derive expressions for the moments of mixtures of base distributions; and, (2) providing recipes for solving the resulting moment equations combining SDP and generalised eigenvalue problems. The overall impression is that the paper does not contain a great deal of technical novelty, but it provides a fresh perspective on moment matching methods for mixture models. The main paper is well-written, but several crucial details are discussed only in the appendix.It is a bit disappointing that the paper pays very little attention to two aspects that initially attracted a lot of attention about spectral methods of moments: the possibility of proving finite-sample bounds, and their scalability as compared to vanilla EM. About the latter, my impression is that obtaining really efficient solutions for the SDP problems arising from different mixture models will require exploiting specific structural properties in each individual case. So the method might not be as "turnstyle" as the authors promise when scalability considerations are taken into account.The scope of the experiments is quite limited, but nearly enough due to the nature of the paper. It does not help dispel any doubts about the scalability of the proposed method, but it showcases the potential benefits of this approach when compared to EM. There are, however, two aspects of these results that could be improved: adding a comparison with the baseline from reference [9] for the linear regression case, and comparing the methods using more than one accuracy measure (eg. perplexity), since somehow one suspects that L2 distance to the true parameter is what poly is hiddenly optimizing, while EM is clearly optimizing another metric.The weakest point of the paper is perhaps its lack of awareness of some relevant previous results. In particular, although the paper does a good job at connecting with literature related to generalised moment problems and solutions of polynomial equations, it misses some quite direct connections to other methods of moments based on Hankel matrices. These follow by simply observing that the moment matrix M(y) is nothing else than a Hankel matrix with indices on the commutative free monoid \mathbb{N}^P. From this point of view, rank properties of M(y), the way in which the truncation M_r(y) is defined, and the shifting exploited in Section 4, are all direct consequences of the same properties for Hankel matrices on the non-commutative free monoid (eg. see [1]). Also, non-commutative versions of problems (6) and (7) were considered already in [2] and [3] with similar constraints as the ones used in the paper, and in [4] in a more general non-probabilistic setting. In view of this, the paper would probably do a better service to the community by making these connections explicit.After reading the authors' response I am more inclined to recognize the novelty in their contribution. However, the feeling of this reviewer (and apparently other reviewers as well) is that in general the paper glosses over a number of important points (eg. identifiability, sample bounds, scalability of SDP relaxations, possibility of special-purpose optimization algorithms). It is clear that a conference paper cannot be asked to tackle all these in detail, but the current paper could be improved with a more systematic and upfront discussion of what it tries and tries not to do. In summary, I think this work shows promise, but perhaps it could benefit from a more elaborate presentation.  *** Minor Comment ***--- In Line 193, the only immediate conclusion one can draw from \mu being K-atomic is that rank(M_r(y)) <= K (note the inequality, not equality like in the paper). To obtain the equality claimed in the paper one needs to: (1) suppose that r is large enough, and (2) somehow make an argument showing that when the theta^*_k are all different then the vectors v_r(theta^*_k) for k = 1...K are linearly independent. Since this point might have impact on the identifiability of the model, I think it is too important to be hand-waved like the authors do. [1] Borja Balle, Xavier Carreras, Franco M. Luque, Ariadna Quattoni: Spectral learning of weighted automata - A forward-backward perspective. Machine Learning 96(1-2): 33-63 (2014)[2] Raphael Bailly, Xavier Carreras, Ariadna Quattoni: Unsupervised Spectral Learning of Finite State Transducers. NIPS 2013[3] Raphael Bailly, Xavier Carreras, Franco M. Luque, Ariadna Quattoni: Unsupervised Spectral Learning of WCFG as Low-rank Matrix Completion. EMNLP 2013[4] Borja Balle and Mehryar Mohri: Spectral learning of general weighted automata via constrained matrix completion. NIPS 2012