Is EM feasible when there is no closed form maximization of the expectation of log likelihood?

Question

In every example I've seen of expectation maximization, the E step concludes with an expression of the expectation of log likelihood ( $Q(\theta | \theta^{(t)})$ ) for which a maximum w.r.t. $\theta$ can be determined easily in closed form using

$\frac{\partial Q(\theta | \theta^{(t)})}{\partial \theta} = 0 $.

However, I am working on a model where the expectation of the log likelihood is quite complex, and cannot be maximized in closed form expressions. I am wondering whether it's feasible to estimate the maximum numerically as part of the algorithm.

Questions:

1. When there is no closed form maximization of $Q(\theta | \theta^{(t)})$, can one be determined numerically in code?
2. Are there any good examples of work where this is done that I can study?

Answer 1

Answer to Question 1:

The maximization step can be conducted by numerical optimization. In fact, it is possible to incorporate constraints (if any) on the original problem into the numerical optimization by use of constrained numerical optimization. One possible use of such constraints is to steer the whole EM optimization away from "bad" regions; but they can also be used to incorporate hard constraints on parameter values.

In fact, the maximum need not even be found during the maximum step. In a variant called Generalized Expectation Maximization, the M step may consist of only one or some number of optimization algorithm iterations, with the M step being terminated prior to a maximum being found. The key is to get an improvement in the objective function in each M step.

If numerical optimization of the M step isn't easy or effective enough, you may be better off using a traditional numerical optimizer on the full problem. All sorts of hybrid approaches are possible.

Answer to Question 2:

Example of use of numerical maximization to perform M step: Slides 16-21 of http://www.control.isy.liu.se/student/graduate/MachineLearning/Lectures/le6.pdf show an example of nonlinear system identification, in which the objective function for the M step does not have a closed form maximum. However, a formula for the gradient of the objective function is derived. The gradient can be used in an off-the-shelf gradient-based numerical optimizer, for example, a Quasi-Newton method such as BFGS (if the gradient were not available, some other numerical maximization method could be used). I have no idea whether this EM algorithm is better or faster in this case than applying Quasi-Newton (BFGS) to the original problem.

Answer 2

If I understand correctly, the question is about the E step, in which one has to find the variational distribution Q with minimal KL divergence to the log likelihood. The global minimum of KL divergence is obtained when the two distributions are the same. This is accomplished by setting Q to be the log likelihood itself. However, If the log likelihood is too complicated to be dealt with analytically, one can use approximations. One of the best known approximations is the mean field, when one constrains Q to the family of factorized distributions over the parameters. In any case, it is always possible to use a numerical procedure in either step of the EM algorithm. But if optimization is too involved, it might become computationally unfeasible. In this situation, you would have to use other algorithms such as MCMC methods.