We investigate a new, convex relaxation of an expectation-maximization (EM) variant that approximates a standard objective while eliminating local minima. First, a cautionary result is presented, showing that any convex relaxation of EM over hidden variables must give trivial results if any dependence on the missing values is retained. Although this appears to be a strong negative outcome, we then demonstrate how the problem can be bypassed by using equivalence relations instead of value assignments over hidden variables. In particular, we develop new algorithms for estimating exponential conditional models that only require equivalence relation information over the variable values. This reformulation leads to an exact expression for EM variants in a wide range of problems. We then develop a semidefinite relaxation that yields global training by eliminating local minima.

21st Annual Conference on Neural Information Processing Systems, NIPS 2007
School of Computer Science

Guo, Y, & Schuurmans, D. (Dale). (2009). Convex relaxations of latent variable training. In Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference.