Алгоритм максимизации ожидания

Итерационный метод нахождения оценок максимального правдоподобия в статистических моделях

В статистике алгоритм максимизации ожидания ( EM ) — это итеративный метод поиска (локального) максимального правдоподобия или максимальной апостериорной (MAP) оценки параметров в статистических моделях , где модель зависит от ненаблюдаемых скрытых переменных . ^[1] Итерация EM чередуется между выполнением шага ожидания (E), который создает функцию для ожидания логарифмического правдоподобия , оцененного с использованием текущей оценки параметров, и шага максимизации (M), который вычисляет параметры, максимизирующие ожидаемое логарифмическое правдоподобие, найденное на шаге E. Эти оценки параметров затем используются для определения распределения скрытых переменных на следующем шаге E. Его можно использовать, например, для оценки смеси гауссианов или для решения задачи множественной линейной регрессии. ^[2]

Кластеризация данных об извержении вулкана Old Faithful с помощью ЭМ . Случайная начальная модель (которая из-за разного масштаба осей выглядит как два очень плоских и широких эллипса) подгоняется под наблюдаемые данные. На первых итерациях модель существенно меняется, но затем сходится к двум режимам гейзера . Визуализировано с помощью ELKI .

История

Алгоритм EM был объяснен и получил свое название в классической статье 1977 года Артура Демпстера , Нэн Лэрд и Дональда Рубина . ^[3] Они указали, что этот метод «предлагался много раз при особых обстоятельствах» более ранними авторами. Одним из самых ранних является метод подсчета генов для оценки частот аллелей Седрика Смита . ^[4] Другой был предложен Х. О. Хартли в 1958 году, а также Хартли и Хокингом в 1977 году, из которого произошли многие идеи в статье Демпстера–Лэрда–Рубина. ^[5] Еще один был предложен СК Нг, Триямбакамом Кришнаном и Г. Дж. Маклахланом в 1977 году . ^[6] Идеи Хартли можно расширить до любого сгруппированного дискретного распределения. Очень подробное рассмотрение метода EM для экспоненциальных семейств было опубликовано Рольфом Сундбергом в его диссертации и нескольких статьях, ^{[7] [8] [9]} после его сотрудничества с Пером Мартином-Лёфом и Андерсом Мартином-Лёфом . ^{[10] [11] [12] [13] [14]} Статья Демпстера–Лэрда–Рубина в 1977 году обобщила метод и набросала анализ сходимости для более широкого класса задач. Статья Демпстера–Лэрда–Рубина установила метод EM как важный инструмент статистического анализа. См. также Meng and van Dyk (1997).

Анализ сходимости алгоритма Демпстера–Лэрда–Рубина был несовершенным, и правильный анализ сходимости был опубликован CF Jeff Wu в 1983 году. ^[15] Доказательство Wu установило сходимость метода EM также за пределами экспоненциального семейства , как утверждали Демпстер–Лэрд–Рубин. ^[15]

Введение

Алгоритм EM используется для поиска (локальных) параметров максимального правдоподобия статистической модели в случаях, когда уравнения не могут быть решены напрямую. Обычно эти модели включают скрытые переменные в дополнение к неизвестным параметрам и известным данным наблюдений. То есть, либо среди данных существуют пропущенные значения , либо модель может быть сформулирована проще, предполагая существование дополнительных ненаблюдаемых точек данных. Например, смешанную модель можно описать проще, предполагая, что каждая наблюдаемая точка данных имеет соответствующую ненаблюдаемую точку данных или скрытую переменную, указывающую компонент смеси, к которому принадлежит каждая точка данных.

Нахождение решения максимального правдоподобия обычно требует взятия производных функции правдоподобия по всем неизвестным значениям, параметрам и скрытым переменным и одновременного решения полученных уравнений. В статистических моделях со скрытыми переменными это обычно невозможно. Вместо этого результатом обычно является набор взаимосвязанных уравнений, в которых решение параметров требует значений скрытых переменных и наоборот, но подстановка одного набора уравнений в другой дает неразрешимое уравнение.

Алгоритм EM исходит из наблюдения, что существует способ решить эти два набора уравнений численно. Можно просто выбрать произвольные значения для одного из двух наборов неизвестных, использовать их для оценки второго набора, затем использовать эти новые значения для нахождения лучшей оценки первого набора, а затем продолжать чередовать их, пока оба результирующих значения не сойдутся к фиксированным точкам. Неочевидно, что это сработает, но это можно доказать в этом контексте. Кроме того, можно доказать, что производная правдоподобия (произвольно близка к) нулю в этой точке, что, в свою очередь, означает, что точка является либо локальным максимумом, либо седловой точкой . ^[15] В общем случае могут возникать множественные максимумы, без гарантии, что будет найден глобальный максимум. Некоторые правдоподобия также имеют в себе сингулярности , т. е. бессмысленные максимумы. Например, одно из решений , которое может быть найдено с помощью EM в смешанной модели, включает установку одного из компонентов с нулевой дисперсией и среднего параметра для того же компонента, равного одной из точек данных. Сходимость алгоритмов, основанных на максимизации ожидания (EM), обычно требует непрерывности функции правдоподобия относительно всех неизвестных параметров (называемых переменными оптимизации) ^{[16] .}

Описание

Символы

Учитывая статистическую модель , которая генерирует набор наблюдаемых данных, набор ненаблюдаемых скрытых данных или пропущенных значений и вектор неизвестных параметров , а также функцию правдоподобия , оценка максимального правдоподобия (ОМП) неизвестных параметров определяется путем максимизации предельного правдоподобия наблюдаемых данных. ${\displaystyle \mathbf {X} }$ ${\displaystyle \mathbf {Z} }$ ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})}$

${\displaystyle L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} \mid {\boldsymbol {\theta }})=\int p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z} =\int p(\mathbf {X} \mid \mathbf {Z} ,{\boldsymbol {\theta }})p(\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z} }$

Однако эта величина часто оказывается трудно поддающейся обработке, поскольку она не наблюдается, а распределение неизвестно до достижения . ${\displaystyle \mathbf {Z} }$ ${\displaystyle \mathbf {Z} }$ ${\displaystyle {\boldsymbol {\theta }}}$

Алгоритм ЭМ

Алгоритм EM стремится найти оценку максимального правдоподобия предельного правдоподобия путем итеративного применения следующих двух шагов:

Шаг ожидания (шаг E) : Определим как ожидаемое значение логарифмической функции правдоподобия относительно текущего условного распределения заданных и текущих оценок параметров : ${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$ ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle \mathbf {Z} }$ ${\displaystyle \mathbf {X} }$ ${\displaystyle {\boldsymbol {\theta }}^{(t)}}$

${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} \sim p(\cdot |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}\left[\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})\right]\,}$

Шаг максимизации (шаг M) : найдите параметры, которые максимизируют эту величину:

${\displaystyle {\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\,}$

Более кратко это можно записать в виде одного уравнения: $${\displaystyle {\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\operatorname {E} _{\mathbf {Z} \sim p(\cdot |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}\left[\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})\right]\,}$$

Интерпретация переменных

Типичные модели, к которым применяется ЭМ, используют в качестве скрытой переменной принадлежность к одной из групп: ${\displaystyle \mathbf {Z} }$

1. Наблюдаемые точки данных могут быть дискретными (принимающими значения в конечном или счетно бесконечном множестве) или непрерывными (принимающими значения в несчетно бесконечном множестве). С каждой точкой данных может быть связан вектор наблюдений. ${\displaystyle \mathbf {X} }$
2. Отсутствующие значения ( также известные как скрытые переменные ) являются дискретными , извлекаются из фиксированного числа значений, и на каждую наблюдаемую единицу приходится одна скрытая переменная. ${\displaystyle \mathbf {Z} }$
3. Параметры являются непрерывными и бывают двух видов: параметры, связанные со всеми точками данных, и параметры, связанные с определенным значением скрытой переменной (т. е. связанные со всеми точками данных, соответствующая скрытая переменная которых имеет это значение).

Однако ЭМ можно применять и к другим типам моделей.

Мотивация такова. Если значение параметров известно, то обычно значение скрытых переменных можно найти, максимизируя логарифмическое правдоподобие по всем возможным значениям , либо просто итерируя , либо используя алгоритм, такой как алгоритм Витерби для скрытых марковских моделей . И наоборот, если мы знаем значение скрытых переменных , мы можем довольно легко найти оценку параметров , обычно просто группируя наблюдаемые точки данных в соответствии со значением связанной скрытой переменной и усредняя значения или некоторую функцию значений точек в каждой группе. Это предполагает итерационный алгоритм в случае, когда и неизвестны: ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle \mathbf {Z} }$ ${\displaystyle \mathbf {Z} }$ ${\displaystyle \mathbf {Z} }$ ${\displaystyle \mathbf {Z} }$ ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle \mathbf {Z} }$

1. Сначала инициализируем параметры некоторыми случайными значениями. ${\displaystyle {\boldsymbol {\theta }}}$
2. Вычислите вероятность каждого возможного значения , если задано . ${\displaystyle \mathbf {Z} }$ ${\displaystyle {\boldsymbol {\theta }}}$
3. Затем используйте только что вычисленные значения для вычисления более точной оценки параметров . ${\displaystyle \mathbf {Z} }$ ${\displaystyle {\boldsymbol {\theta }}}$
4. Повторяйте шаги 2 и 3 до тех пор, пока не будет достигнута сходимость.

Описанный выше алгоритм монотонно приближается к локальному минимуму функции стоимости.

Характеристики

Хотя итерация EM действительно увеличивает функцию правдоподобия наблюдаемых данных (т. е. маргинальную), нет гарантии, что последовательность сходится к оценке максимального правдоподобия . Для мультимодальных распределений это означает, что алгоритм EM может сходиться к локальному максимуму функции правдоподобия наблюдаемых данных в зависимости от начальных значений. Существует множество эвристических или метаэвристических подходов, позволяющих избежать локального максимума, таких как случайный перезапуск восхождения на холм (начиная с нескольких различных случайных начальных оценок ) или применение методов имитации отжига . ${\displaystyle {\boldsymbol {\theta }}^{(t)}}$

EM особенно полезен, когда вероятность является экспоненциальным семейством , см. Sundberg (2019, Ch. 8) для всестороннего рассмотрения: ^[17] шаг E становится суммой ожиданий достаточной статистики , а шаг M включает максимизацию линейной функции. В таком случае обычно можно вывести обновления выражения в замкнутой форме для каждого шага, используя формулу Sundberg ^[18] (доказанную и опубликованную Рольфом Sundberg на основе неопубликованных результатов Per Martin-Löf и Anders Martin-Löf ). ^{[8] [9] [11] [12] [13] [14]}

Метод EM был модифицирован для вычисления максимальных апостериорных оценок (MAP) для байесовского вывода в оригинальной статье Демпстера, Лэрда и Рубина.

Существуют и другие методы поиска оценок максимального правдоподобия, такие как градиентный спуск , сопряженный градиент или варианты алгоритма Гаусса–Ньютона . В отличие от EM, такие методы обычно требуют оценки первых и/или вторых производных функции правдоподобия.

Доказательство правильности

Ожидание-Максимизация работает на улучшение, а не на прямое улучшение . Здесь показано, что улучшение первого подразумевает улучшение второго. ^{[19] [20]} ${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$ ${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}$

Для любого с ненулевой вероятностью мы можем записать ${\displaystyle \mathbf {Z} }$ ${\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})}$

${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}).}$

Мы берем ожидание возможных значений неизвестных данных при текущей оценке параметров , умножая обе стороны на и суммируя (или интегрируя) по . Левая сторона представляет собой ожидание константы, поэтому мы получаем: ${\displaystyle \mathbf {Z} }$ ${\displaystyle \theta ^{(t)}}$ ${\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}$ ${\displaystyle \mathbf {Z} }$

${\displaystyle {\begin{aligned}\log p(\mathbf {X} \mid {\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})\\&=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)}),\end{aligned}}}$

где определяется отрицательным значением суммы, которое оно заменяет. Это последнее уравнение справедливо для каждого значения, включая , ${\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$ ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle {\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}}$

${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}),}$

и вычитание этого последнего уравнения из предыдущего уравнения дает

${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).}$

Однако неравенство Гиббса говорит нам, что , поэтому мы можем заключить, что ${\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})}$

${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})\geq Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).}$

Другими словами, выбор улучшения приводит к как минимум такому же улучшению. ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$ ${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}$

Как процедура максимизации–максимизации

Алгоритм EM можно рассматривать как два чередующихся шага максимизации, то есть как пример спуска по координатам . ^{[21] [22]} Рассмотрим функцию:

${\displaystyle F(q,\theta ):=\operatorname {E} _{q}[\log L(\theta ;x,Z)]+H(q),}$

где q — произвольное распределение вероятностей по ненаблюдаемым данным z , а H(q) — энтропия распределения q . Эту функцию можно записать как

${\displaystyle F(q,\theta )=-D_{\mathrm {KL} }{\big (}q\parallel p_{Z\mid X}(\cdot \mid x;\theta ){\big )}+\log L(\theta ;x),}$

где — условное распределение ненаблюдаемых данных с учётом наблюдаемых данных , а — расхождение Кульбака–Лейблера . ${\displaystyle p_{Z\mid X}(\cdot \mid x;\theta )}$ ${\displaystyle x}$ ${\displaystyle D_{KL}}$

Тогда шаги алгоритма ЭМ можно рассматривать следующим образом:

Шаг ожидания : Выберите для максимизации : ${\displaystyle q}$ ${\displaystyle F}$

${\displaystyle q^{(t)}=\operatorname {arg\,max} _{q}\ F(q,\theta ^{(t)})}$

Шаг максимизации : Выберите для максимизации : ${\displaystyle \theta }$ ${\displaystyle F}$

${\displaystyle \theta ^{(t+1)}=\operatorname {arg\,max} _{\theta }\ F(q^{(t)},\theta )}$

Приложения

• ЭМ часто используется для оценки параметров смешанных моделей , ^{[23] [24]} особенно в количественной генетике . ^[25]
• В психометрии ЭМ является важным инструментом для оценки параметров предметов и скрытых возможностей моделей теории реакций на предметы .
• Благодаря возможности работать с отсутствующими данными и наблюдать неопознанные переменные, EM становится полезным инструментом для оценки и управления рисками портфеля. ^{[ необходима цитата ]}
• Алгоритм EM (и его более быстрый вариант упорядоченного подмножества максимизации ожидания ) также широко используется в реконструкции медицинских изображений , особенно в позитронно-эмиссионной томографии , однофотонной эмиссионной компьютерной томографии и рентгеновской компьютерной томографии . Ниже приведены другие более быстрые варианты EM.
• В строительной инженерии алгоритм структурной идентификации с использованием максимизации ожидания (STRIDE) ^[26] представляет собой метод, дающий только выходные данные для определения свойств собственных колебаний структурной системы с использованием данных датчиков (см. Операционный модальный анализ ).
• EM также используется для кластеризации данных . В обработке естественного языка два известных примера алгоритма — это алгоритм Баума-Уэлча для скрытых марковских моделей и алгоритм «изнутри-снаружи» для неконтролируемой индукции вероятностных контекстно-свободных грамматик .
• При анализе времени ожидания между сделками , т.е. времени между последовательными сделками с акциями на фондовой бирже, алгоритм EM оказался весьма полезным. ^[27]

Фильтрация и сглаживание алгоритмов ЭМ

Фильтр Калмана обычно используется для оценки состояния в режиме онлайн, а сглаживатель с минимальной дисперсией может использоваться для оценки состояния в режиме офлайн или пакетной оценки. Однако эти решения с минимальной дисперсией требуют оценок параметров модели пространства состояний. Алгоритмы EM могут использоваться для решения задач оценки совместного состояния и параметров.

Алгоритмы фильтрации и сглаживания ЭМ возникают путем повторения этой двухэтапной процедуры:

E-шаг

Используйте фильтр Калмана или сглаживатель с минимальной дисперсией, разработанный с текущими оценками параметров, чтобы получить обновленные оценки состояния.

М-шаг

Используйте отфильтрованные или сглаженные оценки состояний в расчетах максимального правдоподобия для получения обновленных оценок параметров.

Предположим, что фильтр Калмана или сглаживатель с минимальной дисперсией работает с измерениями системы с одним входом и одним выходом, которая обладает аддитивным белым шумом. Обновленная оценка дисперсии шума измерения может быть получена из расчета максимального правдоподобия

${\displaystyle {\widehat {\sigma }}_{v}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{(z_{k}-{\widehat {x}}_{k})}^{2},}$

где скалярные оценки выходных данных, вычисленные фильтром или сглаживателем из N скалярных измерений . Вышеуказанное обновление также может быть применено к обновлению интенсивности шума измерения Пуассона. Аналогично, для процесса авторегрессии первого порядка обновленная оценка дисперсии шума процесса может быть вычислена с помощью ${\displaystyle {\widehat {x}}_{k}}$ ${\displaystyle z_{k}}$

${\displaystyle {\widehat {\sigma }}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}^{2},}$

где и являются скалярными оценками состояния, вычисленными фильтром или сглаживателем. Обновленная оценка коэффициента модели получается через ${\displaystyle {\widehat {x}}_{k}}$ ${\displaystyle {\widehat {x}}_{k+1}}$

${\displaystyle {\widehat {F}}={\frac {\sum _{k=1}^{N}{({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}^{2}}{\sum _{k=1}^{N}{\widehat {x}}_{k}^{2}}}.}$

Сходимость оценок параметров, подобных приведенным выше, хорошо изучена. ^{[28] [29] [30] [31]}

Варианты

Было предложено несколько методов для ускорения иногда медленной сходимости алгоритма EM, например, методы, использующие сопряженный градиент и модифицированные методы Ньютона (Ньютона–Рафсона). ^[32] Кроме того, EM можно использовать с методами ограниченной оценки.

Алгоритм максимизации ожиданий с расширенными параметрами (PX-EM) часто обеспечивает ускорение за счет «использования `ковариационной корректировки' для корректировки анализа шага M, извлекая выгоду из дополнительной информации, полученной в вмененных полных данных». ^[33]

Максимизация условий ожидания (ECM) заменяет каждый шаг M последовательностью шагов условной максимизации (CM), в которых каждый параметр θ _i максимизируется индивидуально, при условии, что другие параметры остаются фиксированными. ^[34] Сама по себе она может быть расширена до алгоритма максимизации условий ожидания (ECME) . ^[35]

Эта идея далее расширена в алгоритме обобщенного максимизирования ожиданий (GEM) , в котором ищется только увеличение целевой функции F как для шага E, так и для шага M, как описано в разделе «Как процедура максимизации–максимизации». ^[21] GEM далее развивается в распределенной среде и показывает многообещающие результаты. ^[36]

Алгоритм EM также можно рассматривать как подкласс алгоритма MM (Majorize/Minimize или Minorize/Maximize, в зависимости от контекста) ^[37] и, следовательно, использовать любой механизм, разработанный в более общем случае.

Алгоритм α-EM

Q-функция, используемая в алгоритме EM, основана на логарифмическом правдоподобии. Поэтому он рассматривается как алгоритм log-EM. Использование логарифмического правдоподобия можно обобщить до использования α-логарифмического отношения правдоподобия. Затем α-логарифмическое отношение правдоподобия наблюдаемых данных можно точно выразить как равенство, используя Q-функцию α-логарифмического отношения правдоподобия и α-дивергенцию. Получение этой Q-функции является обобщенным шагом E. Его максимизация является обобщенным шагом M. Эта пара называется алгоритмом α-EM ^[38] , который содержит алгоритм log-EM в качестве своего подкласса. Таким образом, алгоритм α-EM Ясуо Мацуямы является точным обобщением алгоритма log-EM. Не требуется вычисления градиента или матрицы Гессе. α-EM показывает более быструю сходимость, чем алгоритм log-EM, за счет выбора подходящего α. Алгоритм α-EM приводит к более быстрой версии алгоритма оценки скрытой марковской модели α-HMM. ^[39]

Отношение к вариационным байесовским методам

EM — это частично небайесовский метод максимального правдоподобия. Его конечный результат дает распределение вероятностей по скрытым переменным (в байесовском стиле) вместе с точечной оценкой для θ (либо оценка максимального правдоподобия , либо апостериорная мода). Может потребоваться полностью байесовский вариант этого метода, дающий распределение вероятностей по θ и скрытым переменным. Байесовский подход к выводу заключается в том, чтобы просто рассматривать θ как еще одну скрытую переменную. В этой парадигме различие между шагами E и M исчезает. Если использовать факторизованное приближение Q, как описано выше ( вариационный Байес ), решение может выполнять итерации по каждой скрытой переменной (теперь включая θ ) и оптимизировать их по одной за раз. Теперь требуется k шагов на итерацию, где k — количество скрытых переменных. Для графических моделей это легко сделать, поскольку новое Q каждой переменной зависит только от ее марковского покрытия , поэтому локальная передача сообщений может использоваться для эффективного вывода.

Геометрическая интерпретация

В информационной геометрии шаг E и шаг M интерпретируются как проекции относительно двойственных аффинных связей , называемых e-связью и m-связью; расхождение Кульбака–Лейблера также можно понимать в этих терминах.

Примеры

Гауссова смесь

Сравнение k-средних и EM на искусственных данных, визуализированных с помощью ELKI . Используя дисперсии, алгоритм EM может точно описать нормальное распределение, в то время как k-средние разделяют данные в ячейках Вороного . Центр кластера обозначен более светлым и большим символом.

Анимация, демонстрирующая алгоритм EM, подгоняющий модель двухкомпонентной смеси Гаусса к набору данных Old Faithful . Алгоритм проходит от случайной инициализации до сходимости.

Пусть будет выборкой независимых наблюдений из смеси двух многомерных нормальных распределений размерности , и пусть будут скрытыми переменными, которые определяют компонент, из которого происходит наблюдение. ^[22] ${\displaystyle \mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle \mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})}$

${\displaystyle X_{i}\mid (Z_{i}=1)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1})}$и ${\displaystyle X_{i}\mid (Z_{i}=2)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2}),}$

где

${\displaystyle \operatorname {P} (Z_{i}=1)=\tau _{1}\,}$и ${\displaystyle \operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}.}$

Цель состоит в том, чтобы оценить неизвестные параметры, представляющие собой значение смешения между гауссианами и средними значениями и ковариациями каждого из них:

${\displaystyle \theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )},}$

где функция правдоподобия неполных данных равна

${\displaystyle L(\theta ;\mathbf {x} )=\prod _{i=1}^{n}\sum _{j=1}^{2}\tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j}),}$

и функция правдоподобия полных данных равна

${\displaystyle L(\theta ;\mathbf {x} ,\mathbf {z} )=p(\mathbf {x} ,\mathbf {z} \mid \theta )=\prod _{i=1}^{n}\prod _{j=1}^{2}\ [f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})\tau _{j}]^{\mathbb {I} (z_{i}=j)},}$

или

${\displaystyle L(\theta ;\mathbf {x} ,\mathbf {z} )=\exp \left\{\sum _{i=1}^{n}\sum _{j=1}^{2}\mathbb {I} (z_{i}=j){\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}\right\},}$

где — индикаторная функция , а — функция плотности вероятности многомерного нормального распределения. ${\displaystyle \mathbb {I} }$ ${\displaystyle f}$

В последнем равенстве для каждого i один показатель равен нулю, а один показатель равен единице. Внутренняя сумма, таким образом, сводится к одному члену. ${\displaystyle \mathbb {I} (z_{i}=j)}$

Шаг Е

Учитывая нашу текущую оценку параметров θ ^{( t )} , условное распределение Z i _{определяется} теоремой Байеса как пропорциональная высота нормальной плотности, взвешенная по τ :

${\displaystyle T_{j,i}^{(t)}:=\operatorname {P} (Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})={\frac {\tau _{j}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j}^{(t)},\Sigma _{j}^{(t)})}{\tau _{1}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{1}^{(t)},\Sigma _{1}^{(t)})+\tau _{2}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{2}^{(t)},\Sigma _{2}^{(t)})}}.}$

Они называются «вероятностями членства», которые обычно считаются результатом шага E (хотя это не функция Q, представленная ниже).

Этот шаг E соответствует настройке этой функции для Q:

${\displaystyle {\begin{aligned}Q(\theta \mid \theta ^{(t)})&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x} ;\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} ,\mathbf {Z} )]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x} ;\mathbf {\theta } ^{(t)}}[\log \prod _{i=1}^{n}L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x} ;\mathbf {\theta } ^{(t)}}[\sum _{i=1}^{n}\log L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\sum _{i=1}^{n}\operatorname {E} _{Z_{i}\mid X_{i}=x_{i};\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}P(Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})\log L(\theta _{j};\mathbf {x} _{i},j)\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}T_{j,i}^{(t)}{\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}.\end{aligned}}}$

Ожидание внутри суммы берется относительно функции плотности вероятности , которая может быть разной для каждого обучающего набора. Все в шаге E известно до того, как шаг сделан, за исключением , которое вычисляется в соответствии с уравнением в начале раздела шага E. ${\displaystyle \log L(\theta ;\mathbf {x} _{i},Z_{i})}$ ${\displaystyle P(Z_{i}\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})}$ ${\displaystyle \mathbf {x} _{i}}$ ${\displaystyle T_{j,i}}$

Это полное условное ожидание не обязательно вычислять за один шаг, поскольку τ и μ / Σ появляются в отдельных линейных членах и, таким образом, могут быть максимизированы независимо.

М шаг

${\displaystyle Q(\theta \mid \theta ^{(t)})}$будучи квадратичным по форме, это означает, что определение максимизирующих значений является относительно простым. Кроме того, и могут быть максимизированы независимо, поскольку все они появляются в отдельных линейных членах. ${\displaystyle \theta }$ ${\displaystyle \tau }$ ${\displaystyle ({\boldsymbol {\mu }}_{1},\Sigma _{1})}$ ${\displaystyle ({\boldsymbol {\mu }}_{2},\Sigma _{2})}$

Для начала рассмотрим , который имеет ограничение : ${\displaystyle \tau }$ ${\displaystyle \tau _{1}+\tau _{2}=1}$

${\displaystyle {\begin{aligned}{\boldsymbol {\tau }}^{(t+1)}&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ Q(\theta \mid \theta ^{(t)})\\&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ \left\{\left[\sum _{i=1}^{n}T_{1,i}^{(t)}\right]\log \tau _{1}+\left[\sum _{i=1}^{n}T_{2,i}^{(t)}\right]\log \tau _{2}\right\}.\end{aligned}}}$

Это имеет ту же форму, что и оценка максимального правдоподобия для биномиального распределения , поэтому

${\displaystyle \tau _{j}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{j,i}^{(t)}}{\sum _{i=1}^{n}(T_{1,i}^{(t)}+T_{2,i}^{(t)})}}={\frac {1}{n}}\sum _{i=1}^{n}T_{j,i}^{(t)}.}$

Для следующих оценок : ${\displaystyle ({\boldsymbol {\mu }}_{1},\Sigma _{1})}$

${\displaystyle {\begin{aligned}({\boldsymbol {\mu }}_{1}^{(t+1)},\Sigma _{1}^{(t+1)})&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\ Q(\theta \mid \theta ^{(t)})\\&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\ \sum _{i=1}^{n}T_{1,i}^{(t)}\left\{-{\tfrac {1}{2}}\log |\Sigma _{1}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})^{\top }\Sigma _{1}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})\right\}\end{aligned}}.}$

Это имеет ту же форму, что и взвешенная оценка максимального правдоподобия для нормального распределения, поэтому

${\displaystyle {\boldsymbol {\mu }}_{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}}$и ${\displaystyle \Sigma _{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}}$

и, по симметрии,

${\displaystyle {\boldsymbol {\mu }}_{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}}$и ${\displaystyle \Sigma _{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}.}$

Прекращение

Завершите итерационный процесс, если значение ниже некоторого заданного порога. ${\displaystyle E_{Z\mid \theta ^{(t)},\mathbf {x} }[\log L(\theta ^{(t)};\mathbf {x} ,\mathbf {Z} )]\leq E_{Z\mid \theta ^{(t-1)},\mathbf {x} }[\log L(\theta ^{(t-1)};\mathbf {x} ,\mathbf {Z} )]+\varepsilon }$ ${\displaystyle \varepsilon }$

Обобщение

Описанный выше алгоритм можно обобщить для смесей более чем двух многомерных нормальных распределений .

Усеченная и цензурированная регрессия

Алгоритм EM был реализован в случае, когда существует базовая модель линейной регрессии, объясняющая изменение некоторой величины, но когда фактически наблюдаемые значения являются цензурированными или усеченными версиями тех, которые представлены в модели. ^[40] Особые случаи этой модели включают цензурированные или усеченные наблюдения из одного нормального распределения . ^[40]

Альтернативы

EM обычно сходится к локальному оптимуму, не обязательно глобальному оптимуму, без ограничений на скорость сходимости в целом. Возможно, что он может быть произвольно плохим в больших размерностях, и может быть экспоненциальное число локальных оптимумов. Следовательно, существует потребность в альтернативных методах гарантированного обучения, особенно в многомерной обстановке. Существуют альтернативы EM с лучшими гарантиями согласованности, которые называются подходами, основанными на моментах ^[41] или так называемыми спектральными методами . ^{[42] [43]} Подходы, основанные на моментах, к изучению параметров вероятностной модели пользуются гарантиями, такими как глобальная сходимость при определенных условиях, в отличие от EM, который часто страдает от проблемы застревания в локальных оптимумах. Алгоритмы с гарантиями обучения могут быть выведены для ряда важных моделей, таких как модели смесей, HMM и т. д. Для этих спектральных методов не возникает ложных локальных оптимумов, и истинные параметры могут быть последовательно оценены при некоторых условиях регулярности. ^{[ требуется ссылка ]}

Смотрите также

• распределение смеси
• распределение соединений
• оценка плотности
• Анализ главных компонент
• спектроскопия полного поглощения
• Алгоритм EM можно рассматривать как частный случай алгоритма мажорирования-минимизации (MM) . ^[44]

Ссылки

1. Мэн, X.-L.; ван Дайк, Д. (1997). «Алгоритм EM – старая народная песня, спетая на быстрый новый мотив». J. Royal Statist. Soc. B . 59 (3): 511–567. doi : 10.1111/1467-9868.00082 . S2CID  17461647.
2. Чонъёль Квон, Константин Караманис Труды Двадцать третьей Международной конференции по искусственному интеллекту и статистике , PMLR 108:1727-1736, 2020.
3. Демпстер, AP ; Лэрд, NM ; Рубин, DB (1977). «Максимальное правдоподобие неполных данных с помощью алгоритма EM». Журнал Королевского статистического общества, серия B. 39 ( 1): 1–38. JSTOR  2984875. MR  0501537.
4. Ceppelini, RM (1955). «Оценка частот генов в популяции со случайным скрещиванием». Ann. Hum. Genet . 20 (2): 97–115. doi :10.1111/j.1469-1809.1955.tb01360.x. PMID  13268982. S2CID  38625779.
5. Хартли, Герман Отто (1958). «Оценка максимального правдоподобия по неполным данным». Биометрия . 14 (2): 174–194. doi :10.2307/2527783. JSTOR  2527783.
6. Нг, Шу Кей; Кришнан, Триямбакам; Маклахлан, Джеффри Дж. (2011-12-21), «Алгоритм EM», Справочник по вычислительной статистике , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 139–172, doi :10.1007/978-3-642-21551-3_6, ISBN 978-3-642-21550-6, S2CID  59942212 , получено 2022-10-15
7. Сандберг, Рольф (1974). «Теория максимального правдоподобия для неполных данных из экспоненциального семейства». Scandinavian Journal of Statistics . 1 (2): 49–58. JSTOR  4615553. MR  0381110.
8. Rolf Sundberg. 1971. Теория максимального правдоподобия и ее применение для распределений, полученных при наблюдении функции экспоненциального семейства переменных . Диссертация, Институт математической статистики, Стокгольмский университет.
9. Sundberg, Rolf (1976). "Итеративный метод решения уравнений правдоподобия для неполных данных из экспоненциальных семейств". Communications in Statistics – Simulation and Computation . 5 (1): 55–64. doi :10.1080/03610917608812007. MR  0443190.
10. См. признание Демпстера, Лэрда и Рубина на страницах 3, 5 и 11.
11. Per Martin-Löf . 1966. Статистика с точки зрения статистической механики . Конспект лекций, Математический институт, Орхусский университет. («Формула Сундберга», приписывается Андерсу Мартину-Лёфу).
12. Пер Мартин-Лёф . 1970. Statistiska Modeller (Статистические модели): Антекнингар из семинарии 1969–1970 (конспекты лекций 1969–1970), при содействии Рольфа Сундберга. Стокгольмский университет.
13. Martin-Löf, P. Понятие избыточности и его использование в качестве количественной меры отклонения между статистической гипотезой и набором наблюдаемых данных. С обсуждением F. Abildgård, AP Dempster , D. Basu , DR Cox , AWF Edwards , DA Sprott, GA Barnard , O. Barndorff-Nielsen, JD Kalbfleisch и G. Rasch и ответом автора. Труды конференции по фундаментальным вопросам статистического вывода (Орхус, 1973), стр. 1–42. Мемуары, № 1, кафедра теорет. статистики, Институт математики, Университет Орхуса, Орхус, 1974.
14. Martin-Löf, Per (1974). «Понятие избыточности и его использование в качестве количественной меры расхождения между статистической гипотезой и набором наблюдаемых данных». Scand. J. Statist . 1 (1): 3–18.
15. Wu, CF Jeff (март 1983). «О свойствах сходимости алгоритма EM». Annals of Statistics . 11 (1): 95–103. doi : 10.1214/aos/1176346060 . JSTOR  2240463. MR  0684867.
16. Джозеф, Гиту (24 апреля 2024 г.). «Сходимость алгоритма максимизации ожидания с оптимизацией смешанного целого числа». IEEE Signal Processing Letters . 31 : 1229–1233.
17. Sundberg, Rolf (2019). Статистическое моделирование экспоненциальными семействами . Cambridge University Press. ISBN 9781108701112.
18. Лэрд, Нэн (2006). "Формулы Сандберга". Энциклопедия статистических наук . Wiley. doi :10.1002/0471667196.ess2643.pub2. ISBN 0471667196.
19. Little, Roderick JA; Rubin, Donald B. (1987). Статистический анализ с пропущенными данными . Wiley Series in Probability and Mathematical Statistics. Нью-Йорк: John Wiley & Sons. С. 134–136. ISBN 978-0-471-80254-9.
20. Сонг, Юйхан; Миллидж, Берен; Сальватори, Томмазо; Лукасевич, Томас; Сюй, Чжэнхуа; Богач, Рафал (февраль 2024 г.). «Вывод нейронной активности до пластичности как основа для обучения за пределами обратного распространения». Nature Neuroscience . 27 (2): 348–358. doi :10.1038/s41593-023-01514-1. ISSN  1546-1726. PMC 7615830 . 
21. Нил, Рэдфорд; Хинтон, Джеффри (1999). «Взгляд на алгоритм EM, который оправдывает инкрементальные, разреженные и другие варианты». В Michael I. Jordan (ред.). Learning in Graphical Models (PDF) . Cambridge, MA: MIT Press. стр. 355–368. ISBN 978-0-262-60032-3. Получено 22.03.2009 .
22. Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2001). "8.5 Алгоритм EM". Элементы статистического обучения . Нью-Йорк: Springer. С. 236–243. ISBN 978-0-387-95284-0.
23. Линдстром, Мэри Дж.; Бейтс, Дуглас М. (1988). «Алгоритмы Ньютона—Рафсона и ЭМ для линейных моделей смешанных эффектов для данных повторных измерений». Журнал Американской статистической ассоциации . 83 (404): 1014. doi :10.1080/01621459.1988.10478693.
24. Ван Дайк, Дэвид А. (2000). «Подгонка моделей со смешанными эффектами с использованием эффективных алгоритмов типа EM». Журнал вычислительной и графической статистики . 9 (1): 78–98. doi :10.2307/1390614. JSTOR  1390614.
25. Диффи, С. М.; Смит, А. Б.; Уэлш, А. Х.; Куллис, Б. Р. (2017). «Новый алгоритм REML (расширенный параметр) EM для линейных смешанных моделей». Australian & New Zealand Journal of Statistics . 59 (4): 433. doi : 10.1111/anzs.12208 . hdl : 1885/211365 .
26. Матараццо, Т. Дж. и Пакзад, С. Н. (2016). «STRIDE для структурной идентификации с использованием максимизации ожидания: итеративный метод с выходом только для модальной идентификации». Журнал инженерной механики. http://ascelibrary.org/doi/abs/10.1061/(ASCE)EM.1943-7889.0000951
27. Kreer, Markus; Kizilersu, Ayse; Thomas, Anthony W. (2022). «Цензурированный алгоритм максимизации ожиданий для смесей: применение к межторговым временам ожидания». Physica A: Статистическая механика и ее приложения . 587 (1): 126456. Bibcode : 2022PhyA..58726456K. doi : 10.1016/j.physa.2021.126456. ISSN  0378-4371. S2CID  244198364.
28. Эйнике, GA; Малос, JT; Рейд, DC; Хейнсворт, DW (январь 2009 г.). «Уравнение Риккати и сходимость алгоритма ЭМ для выравнивания инерциальной навигации». IEEE Trans. Signal Process . 57 (1): 370–375. Bibcode : 2009ITSP...57..370E. doi : 10.1109/TSP.2008.2007090. S2CID  1930004.
29. Эйнике, GA; Фалько, G.; Малос, JT (май 2010 г.). «Оценка матрицы состояний алгоритма EM для навигации». IEEE Signal Processing Letters . 17 (5): 437–440. Bibcode : 2010ISPL...17..437E. doi : 10.1109/LSP.2010.2043151. S2CID  14114266.
30. Эйнике, GA; Фалько, G.; Данн, MT; Рейд, DC (май 2012 г.). «Оценка дисперсии на основе итерационного сглаживания». IEEE Signal Processing Letters . 19 (5): 275–278. Bibcode : 2012ISPL...19..275E. doi : 10.1109/LSP.2012.2190278. S2CID  17476971.
31. Эйнике, GA (сентябрь 2015 г.). «Итеративная фильтрация и сглаживание измерений, содержащих пуассоновский шум». Труды IEEE по аэрокосмическим и электронным системам . 51 (3): 2205–2011. Bibcode : 2015ITAES..51.2205E. doi : 10.1109/TAES.2015.140843. S2CID  32667132.
32. Джамшидиан, Мортаза; Дженнрих, Роберт И. (1997). «Ускорение алгоритма EM с использованием квазиньютоновских методов». Журнал Королевского статистического общества, серия B. 59 (2): 569–587. дои : 10.1111/1467-9868.00083. MR  1452026. S2CID  121966443.
33. Лю, С (1998). «Расширение параметров для ускорения EM: алгоритм PX-EM». Biometrika . 85 (4): 755–770. CiteSeerX 10.1.1.134.9617 . doi :10.1093/biomet/85.4.755. 
34. Мэн, Сяо-Ли; Рубин, Дональд Б. (1993). «Оценка максимального правдоподобия с помощью алгоритма ECM: общая структура». Biometrika . 80 (2): 267–278. doi :10.1093/biomet/80.2.267. MR  1243503. S2CID  40571416.
35. Лю, Чуанхай; Рубин, Дональд Б. (1994). «Алгоритм ECME: простое расширение EM и ECM с более быстрой монотонной сходимостью». Biometrika . 81 (4): 633. doi :10.1093/biomet/81.4.633. JSTOR  2337067.
36. Цзянтао Инь; Яньфэн Чжан; Лисинь Гао (2012). «Ускорение алгоритмов максимизации ожиданий с частыми обновлениями» (PDF) . Труды Международной конференции IEEE по кластерным вычислениям .
37. Хантер Д.Р. и Ланге К. (2004), Учебник по алгоритмам ММ, The American Statistician, 58: 30–37
38. Мацуяма, Ясуо (2003). «Алгоритм α-EM: суррогатная максимизация правдоподобия с использованием α-логарифмических информационных мер». Труды IEEE по теории информации . 49 (3): 692–706. doi :10.1109/TIT.2002.808105.
39. Мацуяма, Ясуо (2011). «Оценка скрытой марковской модели на основе алгоритма альфа-EM: дискретные и непрерывные альфа-HMM». Международная объединенная конференция по нейронным сетям : 808–816.
40. Wolynetz, MS (1979). «Оценка максимального правдоподобия в линейной модели из ограниченных и цензурированных нормальных данных». Журнал Королевского статистического общества, Серия C. 28 ( 2): 195–206. doi :10.2307/2346749. JSTOR  2346749.
41. Пирсон, Карл (1894). «Вклад в математическую теорию эволюции». Philosophical Transactions of the Royal Society of London A. 185 : 71–110. Bibcode : 1894RSPTA.185...71P. doi : 10.1098/rsta.1894.0003 . ISSN  0264-3820. JSTOR  90667.
42. Шабан, Амирреза; Мехрдад, Фараджтабар; Бо, Се; Ле, Сонг; Байрон, Бутс (2015). «Изучение моделей скрытых переменных путем улучшения спектральных решений с помощью метода внешней точки» (PDF) . UAI : 792–801. Архивировано из оригинала (PDF) 24-12-2016 . Получено 12-06-2019 .
43. Балле, Борха Кваттони, Ариадна Каррерас, Ксавье (27 июня 2012 г.). Оптимизация локальных потерь в операторских моделях: новый взгляд на спектральное обучение . OCLC  815865081.{{cite book}}: CS1 maint: multiple names: authors list (link)
44. Ланге, Кеннет. «Алгоритм ММ» (PDF) .

Дальнейшее чтение

• Хогг, Роберт; МакКин, Джозеф; Крейг, Аллен (2005). Введение в математическую статистику . Аппер Сэдл Ривер, Нью-Джерси: Pearson Prentice Hall. С. 359–364.
• Деллэрт, Фрэнк (февраль 2002 г.). Алгоритм максимизации ожидания (PDF) (Технический отчет номер GIT-GVU-02-20). Georgia Tech College of Computing.дает более простое объяснение алгоритма EM с точки зрения максимизации нижней границы.
• Бишоп, Кристофер М. (2006). Распознавание образов и машинное обучение . Springer. ISBN 978-0-387-31073-2.
• Гупта, М. Р.; Чен, И. (2010). «Теория и использование алгоритма EM». Основы и тенденции в обработке сигналов . 4 (3): 223–296. CiteSeerX  10.1.1.219.6830 . doi :10.1561/2000000034.Хорошо написанная короткая книга по ЭМ, включающая подробный вывод ЭМ для GMM, HMM и Дирихле.
• Билмес, Джефф (1997). Мягкое руководство по алгоритму EM и его применению к оценке параметров для гауссовых смесей и скрытых марковских моделей (технический отчет TR-97-021). Международный институт компьютерных наук.включает упрощенный вывод уравнений ЭМ для гауссовых смесей и скрытых марковских моделей гауссовых смесей.
• Маклахлан, Джеффри Дж.; Кришнан, Триямбакам (2008). Алгоритм EM и расширения (2-е изд.). Хобокен: Wiley. ISBN 978-0-471-20170-0.

Внешние ссылки

• Различные 1D, 2D и 3D демонстрации EM вместе с Mixture Modeling предоставляются как часть парных действий и апплетов SOCR . Эти апплеты и действия эмпирически демонстрируют свойства алгоритма EM для оценки параметров в различных условиях.
• Иерархия классов в C++ (GPL), включая гауссовские смеси
• Электронный учебник «Теория информации, вывод и алгоритмы обучения» Дэвида Дж. К. Маккея включает простые примеры алгоритма EM, такие как кластеризация с использованием алгоритма мягких k -средних, и подчеркивает вариационный взгляд на алгоритм EM, как описано в главе 33.7 версии 7.2 (четвертое издание).
• В книге «Вариационные алгоритмы для приближенного байесовского вывода» М. Дж. Била приводятся сравнения ЭМ с вариационным байесовским ЭМ и выводы нескольких моделей, включая вариационные байесовские HMM (главы).
• Алгоритм максимизации ожидания: краткое руководство, самостоятельный вывод алгоритма EM Шона Бормана.
• Алгоритм EM, Сяоцзинь Чжу.
• Алгоритм EM и его варианты: неформальное руководство Алексиса Роша. Краткое и очень понятное описание EM и многих интересных вариантов.