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

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

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

История

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

Анализ сходимости алгоритма Демпстера – Лэрда – Рубина был ошибочным, и правильный анализ сходимости был опубликован К. Ф. Джефф Ву в 1983 г.^[13]Доказательство Ву установило сходимость ЭМ-метода вне экспоненциальная семья, как утверждает Демпстер – Лэрд – Рубин.^[13]

Вступление

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

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

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

Описание

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

${ 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 предельного правдоподобия, итеративно применяя эти два шага:

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

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

Типичные модели, к которым применяется ЭМ, используют ${ 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 может сходиться к локальный максимум функции правдоподобия наблюдаемых данных в зависимости от начальных значений. Разнообразие эвристических или метаэвристический существуют подходы, позволяющие избежать локального максимума, такие как случайный перезапуск скалолазание (начиная с нескольких различных случайных начальных оценок θ^(т)) или применяя имитация отжига методы.

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

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

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

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

Максимизация ожиданий работает на улучшение ${ Displaystyle Q ({ boldsymbol { theta}} mid { boldsymbol { theta}} ^ {(t)})}$ вместо прямого улучшения ${ Displaystyle журнал р ( mathbf {X} mid { boldsymbol { theta}})}$. Здесь показано, что улучшения первого подразумевают улучшения второго.^[14]

Для любого ${ 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 ^ {(т)}}$ умножив обе части на ${ Displaystyle п ( mathbf {Z} mid mathbf {X}, { boldsymbol { theta}} ^ {(т)})}$ и суммируя (или интегрируя) по ${ displaystyle mathbf {Z}}$. Левая часть - это математическое ожидание константы, поэтому мы получаем:

${ displaystyle { begin {align} 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 {выравнивается}}}$

где ${ Displaystyle Н ({ 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 { жирный символ { theta}} ^ {(t)}).}$

На словах выбирая ${ displaystyle { boldsymbol { theta}}}$ улучшить ${ Displaystyle Q ({ boldsymbol { theta}} mid { boldsymbol { theta}} ^ {(t)})}$ причины ${ Displaystyle журнал р ( 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)} + журнал 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)}$

Приложения

EM часто используется для оценки параметров смешанные модели,^[17][18] особенно в количественная генетика.^[19]

В психометрия, EM практически незаменим для оценки параметров предметов и скрытых способностей теория ответа элемента модели.

Благодаря способности работать с недостающими данными и наблюдать неопознанные переменные, 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},}$

где ${ displaystyle { widehat {x}} _ {k}}$ являются скалярными выходными оценками, вычисленными фильтром или сглаживателем из N скалярных измерений ${ 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), в которой каждый параметр θ_я максимизируется индивидуально, при условии, что остальные параметры остаются неизменными.^[27] Сама может быть расширена в Условная максимизация ожидания либо (ECME) алгоритм.^[28]

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

Также можно рассматривать алгоритм EM как подкласс ММ Алгоритм (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 интерпретируются как проекции двойственного аффинные связи, называемые электронной связью и мобильной связью; то Дивергенция Кульбака – Лейблера также можно понимать в этих терминах.

Примеры

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

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

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

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

${ 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_ {я} = 1) = тау _ {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}$ это функция плотности вероятности многомерной нормали.

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

E шаг

Учитывая нашу текущую оценку параметров θ^(т), условное распределение Z_я определяется Теорема Байеса быть пропорциональной высоте нормального плотность взвешенный τ:

${ 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 {align} 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} сумма _ {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 {align}}}$

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

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

Шаг M

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

Для начала рассмотрим τ, имеющий ограничение τ₁ + τ₂=1:

${ displaystyle { begin {align} { 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 {выравнивается}}}$

Он имеет ту же форму, что и 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 {align} ({ 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 {align}}.}$

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

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

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

Рекомендации

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

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

внешняя ссылка

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