15
$\begingroup$

There are many literature emphasize Expectation Maximization method on mixture models (Mixture of Gaussian, Hidden Markov Model, etc.).

Why EM is important? EM is just a way to do optimization and is not widely used as gradient based method (gradient decent or newton's / quasi-newton method) or other gradient free method discussed HERE. In addition, EM still has local minima problem.

Is it because the process is intuitive and can be easily turn into code? Or what other reasons?

$\endgroup$
14
$\begingroup$

In principle, both EM and standard optimization approaches can work for fitting mixture distributions. Like EM, convex optimization solvers will converge to a local optimum. But, a variety of optimization algorithms exist for seeking better solutions in the presence of multiple local optima. As far as I'm aware, the algorithm with best convergence speed will depend on the problem.

One benefit of EM is that it naturally produces valid parameters for the mixture distribution on every iteration. In contrast, standard optimization algorithms would need constraints to be imposed. For example, say you're fitting a Gaussian mixture model. A standard nonlinear programming approach would require constraining covariance matrices to be positive semidefinite, and constraining mixture component weights to be nonnegative and sum to one.

To achieve good performance on high dimensional problems, a nonlinear programming solver typically needs to exploit the gradient. So, you'd have to either derive the gradient or compute it with automatic differentiation. Gradients are also needed for constraint functions if they don't have a standard form. Newton's method and related approaches (e.g. trust region methods) need the Hessian as well. Finite differencing or derivative-free methods could be used if the gradient is unavailable, but performance tends to scale poorly as the number of parameters increases. In contrast, EM doesn't require the gradient.

EM is conceptually intuitive, which is a great virtue. This often holds for standard optimization approaches as well. There are many implementation details, but the overall concept is simple. It's often possible to use standard optimization solvers that abstract these details away under the hood. In these cases, a user just has to supply the objective function, constraints, and gradients, and have enough working knowledge to select a solver that's well suited for the problem. But, specialized knowledge is certainly required if it gets to the point where the user has to think about or implement low-level details of the optimization algorithm.

Another benefit of the EM algorithm is that it can be used in cases where some data values are missing.

Also of interest (including the comments):

$\endgroup$
  • $\begingroup$ The constraints in the case of mixture models can often be enforced by reparameterisation. E.g. $\sum_i p_i = 1$ can be done via optimising over $q_i \in \mathbb{R}$ and $p_i = \frac{\exp(q_i)}{\sum_j\exp(q_j)}$. $\endgroup$ – bayerj Feb 17 '17 at 19:52
  • 1
    $\begingroup$ Yes, that's certainly true. This would be a form of imposing constraints from the perspective of the user (who has to code it in), but not the perspective of the solver (who no longer directly receives the corresponding constraint). Another trick: a covariance matrix $C$ can be expressed using unconstrained matrix $U$, where $C = U^T U$. But, this increases both computation and number of parameters compared to using $C$ directly and constraining it to be a positive semidefinite symmetric matrix. $\endgroup$ – user20160 Feb 17 '17 at 20:14
  • $\begingroup$ Yes, good perspective to shift it from the solver to the user. You can also only consider triangular $U$. That way, you don't over specify the system since most of the parameters are $0$. $\endgroup$ – bayerj Feb 17 '17 at 20:17
  • $\begingroup$ Right, right, cholesky decomposition. Much better. $\endgroup$ – user20160 Feb 17 '17 at 20:27
  • 1
    $\begingroup$ +1 great answer! could you explain more on "it naturally produces valid parameters for the mixture distribution on every iteration"? For other methods, we still have decision variable values for each iteration, Right? $\endgroup$ – Haitao Du Feb 18 '17 at 4:09
2
$\begingroup$

I think user20160's answer provides a very good explanation, the most important reason that makes gradient based methods not suitable here is the constraint for covariance matrices to be positive semidefinite, and mixture coefficients to be nonnegative and sum up to one.

Just want to point out that if we restrict the covariance matrices to be diagonal, then these two constraints can be expressed easily.

A diagonal covariance matrix can be written as $$ \Sigma = \begin{bmatrix} \sigma^2_{1} & & \\ & \ddots & \\ & & \sigma^2_{N} \end{bmatrix}$$ the mixture coefficients can be represented via a softmax as $$\phi_k=e^{p_k}/\sum_Ke^{p_i}$$ then the two constrains are satisfied, and gradients can be evaluated simply say by back propagation.

Moreover this allows us to directly optimize for the true likelihood instead of the variational lower bound (ELBO), thus removes the need for latent variables.

However even in such cases EM often turns out to be a better algorithm than gradient decent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.