Threshold-based multi-thread EM algorithm

The EM algorithm is an efficient algorithm to obtain the ML estimate for incomplete data, but has the local optimality problem. The deterministic annealing EM (DAEM) algorithm was once proposed to solve the problem, but the global optimality is not guaranteed because of a single-token search. Then, the multi-thread DAEM (m-DAEM) algorithm was proposed by incorporating a multiple-token search with solution quality improvement with a heavy computing cost. Later, another variant of m-DAEM (ε-DAEM) was proposed by introducing threshold-based dynamic annealing with more quality improvement for an adequate threshold ε; however, finding such ε is not easy. This paper proposes a new variant of EM, called ε-EM, by incorporating a multiple-token search together with threshold-based bifurcation. Our experiments using Gaussian mixture estimation problems showed that the ε-EM finds excellent solutions with relatively small computing cost, and the threshold ε plays a key role in reducing computing cost.