7.2. ЕМ-АЛГОРИТМ. ВВЕДЕНИЕ

ЕМ-алгоритм — очень общий итеративный алгоритм для МП-оценивания в задачах с неполными данными. На деле круг задач, которые можно решать с помощью ЕМ-алгоритма, очень широк. Он охватывает задачи, постановка которых обычно не связана с проблемой отсутствующих и неполных данных (например, оценивание компонент дисперсии, итеративно взвешиваемые оценки наименьших квадратов).

В ЕМ-алгоритме формализована относительно старая идея обработки неполных данных: 1) заполнение пропусков оценками пропущенных значений; 2) оценивание параметров; 3) повторное оценивание пропущенных значений, при этом оценки параметров считаются точными; 4) повторное оценивание параметров и так далее до сходимости процесса. Такие алгоритмы являются ЕМ-алгоритмами для моделей, где логарифм правдоподобия для полных данных линеен или в более общей форме, где надо оценивать не отдельные пропуски, а отсутствующие достаточные статистики, и более того, где на каждой итерации алгоритма надо оценивать логарифм правдоподобия

Поскольку ЕМ-алгоритм тесно связан с основанной на интуиции идеей заполнения пропусков и совершения итераций, неудивительно, что он уже давно предлагался в частных случаях. Одним из первых его предложил МакКендрик [McKendrick (1926)] для медицинских приложений. Хартли [Hartley (1958)] рассмотрел общий случай дискретных данных и довольно широко разработал теорию. В его статье содержится много ключевых идей современной теории Баум и соавторы [Baum, Petrie, Soules and Weiss (1970)] использовали этот алгоритм для марковской, модели и доказали важные математические результаты, которые довольно легко обобщаются. Орчард и Вудбери [Orchard and Woodbery (1972)] первыми отметили широкую применимость основной идеи, названной ими «принципом отсутствующей информации». Сандберг [Sundberg (1974)] рассмотрел свойства общих уравнений максимального правдоподобия, а Бил и Литтл [Beale and Little (1975)] развили теорию для нормальной модели. Термин был введен в [Dempster, Laird and Rubin (1977)]. В этой работе показана высокая общность алгоритма. В ней: 1) доказаны общие результаты о поведении алгоритма и, в частности, отмечено свойство, что каждая итерация увеличивает правдоподобие ; 2) приведено множество примеров. С 1977 г. появилось большое число работ по применению ЕМ-алгоритма и с исследованием его сходимости (см., например, [Wu (1983)]).

Каждая итерация ЕМ-алгоритма состоит из шага (вычисление математического ожидания) и шага М (максимизация)- Эти шаги можно легко представить содержательно, запрограммировать и

разместить в памяти компьютера. Далее, каждый шаг имеет непосредственную статистическую интерпретацию. Еще одним достоинством алгоритма является надежная сходимость, т. е. в определенных нестрогих условиях каждая итерация увеличивает логарифм правдоподобия и если ограничен, то последовательность сходится к стационарному значению . С достаточной степенью общности можно сказать, что если последовательность сходится, то она сходится к локальному максимуму или точке перегиба Недостаток ЕМ-алгоритма заключается в том, что скорость сходимости может быть очень низкой, если пропущено много данных. В [Dempster, Laird and Rubin (1977)] показано, что сходимость линейна со скоростью, пропорциональной наблюдаемой доле информации о 6 в о чем более точно говорится в разделе 7.5. Кроме того, ЕМ-алгоритм не обладает свойством, присущим алгоритму Ньютона-Рафсона или методу вкладов, согласно которому оценки, получаемые после одной итерации, асимптотически эквивалентны ОМП.