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

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

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

История [ править ]

Алгоритм EM был объяснен и получил свое название в классической статье 1977 года Артура Демпстера , Нэн Лэрд и Дональда Рубина . ^[1] Они указали, что этот метод «много раз предлагался при особых обстоятельствах» более ранними авторами. Одним из первых является метод подсчета генов для оценки частот аллелей Седрика Смита . ^[2] Очень подробное рассмотрение метода ЭМ для экспоненциальных семейств было опубликовано Рольфом Сундбергом в его диссертации и нескольких статьях ^{[3] [4] [5]} после его сотрудничества с Пером Мартином-Лёфом и Андерсом Мартином-Лёфом . ^{[6] [7][8] [9] [10] [11] [12]} Статья Демпстера – Лэрда – Рубина 1977 г. обобщила метод и наметила анализ сходимости для более широкого класса задач. В статье Демпстера – Лэрда – Рубина ЭМ-метод определен как важный инструмент статистического анализа.

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

Введение [ править ]

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

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

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

Описание [ править ]

Учитывая статистическую модель , которая генерирует набор наблюдаемых данных, набор ненаблюдаемых латентных данных или пропущенные значения , и вектор неизвестных параметров , а также функция правдоподобия , то оценка максимального правдоподобия (MLE) неизвестных параметров определяются путем максимизации предельная вероятность наблюдаемых данных${\ 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} }$

Однако с этой величиной часто трудно справиться (например, если это последовательность событий, так что количество значений растет экспоненциально с длиной последовательности, точное вычисление суммы будет чрезвычайно трудным).${\displaystyle \mathbf {Z} }$

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

Шаг Ожидание (Е шаг) : Определить , как ожидаемое значение из журнала функции правдоподобия из , по отношению к текущему условного распределения из дается и текущих оценок параметров :${\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} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}}\left[\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )\right]\,}$

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

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

Типичные модели, к которым применяется EM, используют как скрытую переменную, указывающую на принадлежность к одной из множества групп:${\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 до схождения.

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

Свойства [ править ]

Говорить о шаге ожидания (E) немного неправильно . То , что вычисляются на первом этапе являются фиксированными, данные , зависящие от параметров функции Q . Как только параметры Q известны, они полностью определяются и максимизируются на втором (M) шаге алгоритма EM.

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

EM особенно полезен, когда вероятность является экспоненциальным семейством : шаг E становится суммой ожиданий достаточной статистики , а шаг M включает максимизацию линейной функции. В таком случае обычно можно получить обновления выражений в закрытой форме для каждого шага, используя формулу Сундберга (опубликованную Рольфом Сундбергом с использованием неопубликованных результатов Пера Мартина-Лёфа и Андерса Мартина-Лёфа ). ^{[4] [5] [8] [9] [10] [11] [12]}

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

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

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

Максимизация ожиданий работает скорее на улучшение , чем на прямое улучшение . Здесь показано, что улучшения первого подразумевают улучшения второго. ^[14]${\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 можно рассматривать как два чередующихся шага максимизации, то есть как пример спуска координат . ^{[15] [16]} Рассмотрим функцию:

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

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

Шаг ожидания : выберите, чтобы максимизировать :${\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 )}$

Приложения [ править ]

ЭМ часто используются для оценивания параметров смешанных моделей , ^{[17] [18]} В частности , в количественных генетиках . ^[19]

В психометрии EM - важный инструмент для оценки параметров предмета и скрытых способностей моделей теории реакции на предмет .

Благодаря способности работать с недостающими данными и наблюдать неопознанные переменные, EM становится полезным инструментом для определения цены и управления рисками портфеля. ^{[ необходима цитата ]}

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

В проектировании конструкций алгоритм структурной идентификации с использованием максимизации ожиданий (STRIDE) ^[20] - это метод только для вывода для определения свойств естественной вибрации структурной системы с использованием данных датчиков (см. Оперативный модальный анализ ).

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

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

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

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

E-шаг

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

M-шаг

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

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

${\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})}{\sum _{k=1}^{N}{\widehat {x}}_{k}^{2}}}.}$

Сходимость оценок параметров, подобных приведенным выше, хорошо изучена. ^{[21] [22] [23] [24]}

Варианты [ править ]

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

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

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

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

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

алгоритм α-EM [ править ]

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

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

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

Геометрическая интерпретация [ править ]

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

Примеры [ править ]

Гауссова смесь [ править ]

Пусть будет выборкой независимых наблюдений из смеси двух многомерных нормальных распределений размерности , и пусть будет скрытыми переменными, которые определяют компонент, из которого происходит наблюдение. ^[16]${\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)}$

Шаг E [ править ]

Учитывая нашу текущую оценку параметров θ ^{( 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 {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} ,\mathbf {Z} )]\\&=\operatorname {E} _{\mathbf {Z} \mid \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 {\theta } ^{(t)}}[\sum _{i=1}^{n}\log L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\sum _{i=1}^{n}\operatorname {E} _{Z_{i}\mid \mathbf {X} ;\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}}$

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

Шаг M [ править ]

Q ( θ  |  θ ^{( t )} ) квадратичная форма означает, что определение максимальных значений θ относительно несложно. Кроме того, τ , ( μ ₁ , Σ ₁ ) и ( μ ₂ , Σ ₂ ) могут быть максимизированы независимо, поскольку все они появляются в отдельных линейных членах.

Для начала рассмотрим τ , у которого есть ограничение τ ₁ + τ ₂ = 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}}}$

Он имеет ту же форму, что и MLE для биномиального распределения , поэтому

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

Он имеет ту же форму, что и взвешенный MLE для нормального распределения, поэтому

${\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 был реализован в случае, когда существует базовая модель линейной регрессии, объясняющая изменение некоторой величины, но когда фактически наблюдаемые значения являются цензурированными или усеченными версиями представленных в модели. ^[33] Частные случаи этой модели включают цензурированные или усеченные наблюдения из одного нормального распределения . ^[33]

Альтернативы [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Хогг, Роберт; Маккин, Джозеф; Крейг, Аллен (2005). Введение в математическую статистику . Река Аппер Сэдл, Нью-Джерси: Пирсон Прентис Холл. С. 359–364.
• Делларт, Франк (2002). «Алгоритм максимизации ожидания». CiteSeerX  10.1.1.9.97 35 . Cite journal requires |journal= (help) дает более простое объяснение алгоритма EM в отношении максимизации нижней границы.
• Епископ, Кристофер М. (2006). Распознавание образов и машинное обучение . Springer. ISBN 978-0-387-31073-2.CS1 maint: ref duplicates default (link)
• Гупта, MR; Чен, Ю. (2010). «Теория и использование алгоритма ЭМ». Основы и тенденции в обработке сигналов . 4 (3): 223–296. CiteSeerX  10.1.1.219.6830 . DOI : 10.1561 / 2000000034 . Хорошо написанная короткая книга по EM, включая подробный вывод EM для GMM, HMM и Дирихле.
• Билмес, Джефф (1998). "Мягкое руководство по алгоритму ЭМ и его применению к оценке параметров для гауссовской смеси и скрытых марковских моделей". CiteSeerX  10.1.1.28.613 . Cite journal requires |journal= (help) включает упрощенный вывод уравнений EM для гауссовых смесей и скрытых марковских моделей гауссовской смеси.
• Маклахлан, Джеффри Дж .; Кришнан, Триямбакам (2008). Алгоритм EM и расширения (2-е изд.). Хобокен: Вайли. ISBN 978-0-471-20170-0.

Внешние ссылки [ править ]

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