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

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

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

История

Алгоритм EM был объяснен и получил свое название в классической статье 1977 года Артура Демпстера , Нэн Лэрд и Дональда Рубина . Они отметили, что этот метод «много раз предлагался в особых обстоятельствах» более ранними авторами. Одним из первых является метод подсчета генов для оценки частот аллелей Седрика Смита . Другой был предложен Х. О. Хартли в 1958 году, а также Хартли и Хокингом в 1977 году, из которого возникли многие идеи в статье Демпстера-Лэрда-Рубина. Еще один, сделанный С. К. Нг, Триямбакамом Кришнаном и Г. Дж. Маклахланом в 1977 году. Идеи Хартли можно распространить на любое сгруппированное дискретное распределение. Очень подробное описание метода EM для экспоненциальных семейств было опубликовано Рольфом Сундбергом в его диссертации и нескольких статьях: после его сотрудничества с Пером Мартином-Лёфом и Андерсом Мартином-Лёфом . В статье Демпстера-Лэрда-Рубина 1977 года был обобщен метод и набросан анализ сходимости для более широкого класса задач. В статье Демпстера-Лэрда-Рубина ЭМ-метод стал важным инструментом статистического анализа. См. также Мэн и ван Дайк (1997).

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

Введение

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

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

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

Описание

Символы

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

$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}$

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

Алгоритм EM

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

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

$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) : Найдите параметры, которые максимизируют эту величину:

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

Более кратко мы можем записать это в виде одного уравнения: $${\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]\,$$

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

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

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

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

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

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

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

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

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

ЭМ особенно полезна, когда вероятность представляет собой экспоненциальное семейство . Подробную трактовку см. в Sundberg (2019, Ch. 8): шаг E становится суммой ожиданий достаточной статистики , а шаг M предполагает максимизацию линейной функции. В таком случае обычно можно получить обновления выражений в закрытой форме для каждого шага, используя формулу Сундберга. (доказано и опубликовано Рольфом Сундбергом на основе неопубликованных результатов Пера Мартина-Лёфа и Андерса Мартина-Лёфа ).

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

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

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

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

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

$\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 }}).$

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

${\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}}$

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

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

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

$\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)}).$

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

$\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)}).$

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

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

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

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

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

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

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

Тогда шаги алгоритма EM можно рассматривать как:

Шаг ожидания : Выберите $q$ максимизировать $F$:

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

Шаг максимизации : выберите $\theta$ максимизировать $F$:

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

Приложения

• EM часто используется для оценки параметров смешанных моделей . особенно в количественной генетике .
• В психометрии ЭМ является важным инструментом для оценки параметров заданий и скрытых способностей моделей теории ответов на задания .
• Благодаря способности работать с недостающими данными и наблюдать неопознанные переменные, EM становится полезным инструментом для оценки и управления рисками портфеля.
• Алгоритм EM (и его более быстрый вариант максимизации ожидания упорядоченного подмножества ) также широко используется в медицинских изображений реконструкции , особенно в позитронно-эмиссионной томографии , однофотонной эмиссионной компьютерной томографии и рентгеновской компьютерной томографии . Ниже приведены другие более быстрые варианты EM.
• В структурном проектировании используется структурная идентификация с использованием максимизации ожиданий (STRIDE). Алгоритм представляет собой метод только для вывода для определения свойств собственных колебаний структурной системы с использованием данных датчиков (см. Операционный модальный анализ ).
• EM также используется для кластеризации данных . В обработке естественного языка двумя яркими примерами алгоритма являются алгоритм Баума-Уэлча для скрытых моделей Маркова и алгоритм внутри-вне для неконтролируемой индукции вероятностных контекстно-свободных грамматик .
• При анализе времени ожидания между сделками , т.е. времени между последующими сделками с акциями на фондовой бирже, алгоритм EM оказался очень полезным.

Алгоритмы фильтрации и сглаживания EM

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

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

E-шаг

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

М-шаг

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

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

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

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

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

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

${\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}}}.$

Сходимость оценок параметров, подобных приведенным выше, хорошо изучена.

Варианты

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

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

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

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

Также можно рассматривать алгоритм EM как подкласс алгоритма MM (Majorize/Minimize или Minorize/Maximize, в зависимости от контекста), и поэтому использовать любую технику, разработанную в более общем случае.

алгоритм α-EM

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

Связь с вариационными методами Байеса

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

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

Дополнительная информация: Информационная геометрия.

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

Примеры

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

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

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

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

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

где

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

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

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

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

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

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

$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)},$

или

$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\},$

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

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

шаг Е

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

$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:

${\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}}$

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

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

М шаг

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

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

${\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}}$

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

$\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)}.$

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

${\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}}.$

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

${\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)}}}$ и $\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)}}}$

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

${\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)}}}$ и $\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)}}}.$

Прекращение действия

Завершите итерационный процесс, если $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$ для $\varepsilon$ ниже некоторого заданного порога.

Обобщение

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

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

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

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

EM обычно сходится к локальному оптимуму, а не обязательно к глобальному оптимуму, без ограничений на скорость сходимости в целом. Возможно, что оно может быть сколь угодно бедным в больших размерностях и может существовать экспоненциальное число локальных оптимумов. Следовательно, существует потребность в альтернативных методах гарантированного обучения, особенно в многомерных условиях. Существуют альтернативы EM с лучшими гарантиями последовательности, которые называются подходами, основанными на моменте. или так называемые спектральные методы . Моментные подходы к изучению параметров вероятностной модели имеют такие гарантии, как глобальная конвергенция при определенных условиях, в отличие от EM, который часто сталкивается с проблемой застревания в локальных оптимумах. Алгоритмы с гарантиями обучения могут быть получены для ряда важных моделей, таких как смешанные модели, СММ и т. д. Для этих спектральных методов не возникает ложных локальных оптимумов, и истинные параметры могут быть последовательно оценены при некоторых условиях регулярности. .

См. также

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

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

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

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

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