Алгоритм EM является английской аббревиатурой английского алгоритма максимизации ожидания. В переводе это алгоритм максимизации ожидания. Фактически, это итеративная стратегия оптимизации, основанная на оценке параметров с максимальным правдоподобием. Алгоритм EM можно широко оценить, потому что это возможно Оценка параметров методом максимального правдоподобия из неполных наборов данных очень эффективна для работы с неполными данными, цензурированными данными и некоторыми данными с шумом.
Перед тем, как написать эту статью, я прочитал много блогов, получил много знаний и сослался на множество материалов.Я надеюсь, что смогу начать с теории итеративной оптимизации и общих шагов алгоритма EM, а затем я могу дать пример, чтобы сделать Мы понимаем этот алгоритм EM, а затем доказываем его сходимость, цель состоит в том, чтобы показать, что каждая итерация алгоритма EM может улучшить значение функции правдоподобия, а затем сходиться к стабильной точке, а затем привести к скорости сходимости алгоритм ЭМ.
Вероятно, за счет вышеуказанной части мы можем получить преимущества, основанные на ее простоте, сходимости и стабильном подъеме, но есть и некоторые недостатки, такие как метод ускорения со слишком медленной скоростью сходимости и т. д. Во второй статье мы представим метод устранения недостатков, а затем напишите некоторые важные приложения алгоритма EM, включая применение алгоритма EM для оценки параметров двумерного нормального распределения, применение оценки параметров смешанного гауссовского распределения и применение ЭМ-алгоритма к параметрам скрытой марковской модели (частный случай ЭМ-алгоритма), я надеюсь, что благодаря этой серии статей вы сможете понять очевидные преимущества и принципы ЭМ-алгоритма, давайте приступим!
задний план:
Оценка максимального правдоподобия и байесовская статистика на самом деле являются очень популярными областями в текущей области статистики. Фактически, их процесс расчета имеет некоторые схожие компоненты, такие как метод расчета оценки функции максимального правдоподобия. Расчет апостериорной вероятности очень похож на расчет Байесовский, Мы знаем, что байесовский делится на две категории, одна имеет явное апостериорное распределение, например, Обычно используется для простых функций правдоподобия, а другой представляет собой алгоритм добавления данных, Иногда наши данные могут отсутствовать или функция правдоподобия не является явным. Класс добавления данных может быть хорошо применен в это время. Он может добавить некоторые «потенциальные данные» к наблюдаемым данным, чтобы упростить их и завершить работу по максимизации, а затем метод добавления данных, который мы обычно используем, на самом деле является Алгоритм EM, который мы представили сегодня.
Алгоритм EM является итеративной стратегией оптимизации.Его метод расчета делится на шаг ожидания (шаг E) и шаг максимума (шаг M), поэтому название этого алгоритма происходит от этого, и на алгоритм EM влияет отсутствующий Алгоритм. Первоначально эффект заключается в решении проблемы отсутствия данных, упомянутой выше. Основная идея состоит в том, чтобы сначала оценить значение параметров модели в соответствии с наблюдаемыми данными, а затем оценить значение недостающих данных в соответствии с оцененным значением параметра. на предыдущем шаге Затем значения параметров переоцениваются в соответствии с отсутствующими данными в оценке плюс ранее наблюдаемые данные, а затем итеративно повторяются до тех пор, пока они окончательно не сойдутся и итерация не закончится.
Сейчас алгоритм ЭМ разрабатывался десятилетиями.В то время, когда данные быстро росли, было очень сложно обрабатывать данные, и часто были случаи, когда данные отсутствовали или были недоступны.В то время это было ничего. больше, чем подгонка нейронной сетью и дополнение ее методом, методом фильтрации Калмана и т. д., но в итоге выделяется ЭМ. Самое главное, что шаги его алгоритма просты, а при стабильном подъеме можно надежно найти оптимальные значение сходимости.Однако, используя эту идею, мы расширили, чтобы упростить стратегию проблемы. Иногда недостающие данные на самом деле не отсутствуют. В настоящее время EM вводит соответствующую технологию добавления данных. Такие данные называются «скрытыми данными». Сложные проблемы могут быть эффективно решается путем введения скрытых данных.
«Скрытые данные» можно интерпретировать как то, что в самих данных нет отсутствующих переменных, но с данными наблюдения труднее иметь дело, если добавляются дополнительные переменные, с ними становится легче иметь дело. Предполагая, что X является известными данными наблюдений, представьте данные наблюдений, сгенерированные случайной величиной X вместе с отсутствующими или ненаблюдаемыми данными из случайной переменной y, и получите Z=(X,Y) как полные данные. Учитывая данные наблюдения X, мы хотим максимизировать функцию правдоподобия L (0/x).Вывод из-за отсутствия данных или других причин
В результате использование этой функции правдоподобия было бы затруднительным, в то время как использование плотностей Z|0 и Y|(x,0) проще. Алгоритм EM избегает рассмотрения P (0 | X), беря эти более простые плотности p (0 | z), Но это байесовское приложение, где P — случайная величина для апостериорного распределения.
Но неизбежный алгоритм EM также имеет некоторые недостатки:
1: в случае большего количества отсутствующих данных скорость сходимости ниже.
2: В некоторых случаях очень сложно вычислить M шагов алгоритма, то есть завершить оценку функции правдоподобия
3: В некоторых случаях очень сложно или невозможно явно получить ожидание E-шага в алгоритме EM.
Принцип алгоритма и шаги:
Теперь предположим, что X — это наблюдаемые данные, Y — скрытые данные, итерация алгоритма EM заключается в поиске функции максимизации L(0|X) относительно 0, и пусть 0(k) — максимальная точка, оцененная после K итераций, K принадлежит (0,1,2...), определяя Q(0|0(k))
представляет собой математическое ожидание совместной логарифмической функции правдоподобия полных данных при условии наблюдаемых данных X = {x1, x2....xn}, и может быть получена следующая формула:
Из приведенной выше формулы мы можем найти, что как только наша точка выборки X задана, тогда Y является единственной случайной частью Z. Найдя условное математическое ожидание для Y, Y можно снова проинтегрировать, так что Q (0 | 0 (k )) полностью стал функцией 0, так что 0, максимизирующий Q(0|0(k)) может быть найден и записан как 0(k+1) для следующей итерации.
Алгоритм EM начинается с 0 (0), а затем чередуется между двумя частями: E для ожидания и M для максимизации.Алгоритм можно обобщить следующим образом:
1: Шаг E, при условии заданных данных наблюдения X и уже известных параметров, найти математическое ожидание отсутствующих данных Y, то есть вычислить условное ожидание Q(0|0(k) упомянутой выше логарифмической функции правдоподобия. )).
2: M шагов, как будто нет пропущенных данных Y (после заполнения пропущенных данных), максимизируя математическое ожидание функции логарифмического правдоподобия при полных данных, то есть нахождение функции 0-правдоподобия Q(0|0 (k)) максимизируется Установите 0(k+1) равным максимальной точке, обновите 0(k):
3: Возвращайтесь к шагу E до тех пор, пока не будет соблюдено определенное правило остановки.
Теперь используйте пример из анализа данных Хана Цзявэя, чтобы подробно проиллюстрировать алгоритм EM:
1: Теперь предположим, что выполнение эксперимента приведет к четырем исходам, и вероятность каждого исхода равна:
Эксперимент проводился 197 раз, а четыре результата встречались 125, 18, 20 и 34. В это время X={x1,x2,x3,x4}={125,18,20,34}
Чтобы оценить параметры, мы можем взять априорное распределение p (0) для 0 как U (0,1).Из формулы Байеса мы знаем, что апостериорное распределение 0 равно:
Разделите первый результат на две части с вероятностью появления 1/2 и 0/4 соответственно, пусть Y и x1-Y соответственно представляют количество успешных испытаний этих двух частей (Y - отсутствующие данные), затем добавление 0 Апостериорное распределение:
В это время пришло время для алгоритма EM добавить данные.Кроме того, более проблематично напрямую получить оценку максимального правдоподобия 0. Теперь гораздо проще выполнить итерацию последней функции апостериорного распределения после использования алгоритма EM.(В приведенный выше процесс вычисления, символ внизу, указывает на то, что выражения на обоих концах символа пропорциональны, и это соотношение не имеет ничего общего с 0, это соотношение не повлияет на результат оценки итеративного алгоритма EM, потому что последняя максимизация может быть уменьшена).
Теперь предположим, что на i+1-й итерации имеется оценочное значение 0(i), тогда новую оценку можно получить с помощью шагов E и M алгоритма EM. На шаге E:
Поскольку Y подчиняется биномиальному распределению при данных x и 0 (i), мы можем получить E (Y | X, 0 (i)) = 2x (1) / [2 + 0 (i)]. Таким образом, есть:
На этапе M вывод 0 в приведенной выше формуле и получение результата 0, итеративная формула может быть получена как:
В это время он начинается с 0 (0) = 0,5 и сходится к 0,6268 после четырех итераций EM.Согласно Matlab, кривая сходимости выглядит следующим образом:
Кроме того, R используется в книге Хана Цзявэя, здесь я использую MATLAB, эффект аналогичен, и его можно достичь.
Доказательство сходимости алгоритма EM:
Простота алгоритма и устойчивая сходимость являются самыми большими преимуществами алгоритма EM.Простота алгоритма EM была полностью понята выше, и теперь необходимо оценить, соответствует ли полученная последовательность ожидаемым требованиям сходимости, что то есть предполагаемый результат алгоритма EM. Может ли сходимость стабильно сходиться, и является ли результат сходимости максимальным значением или локальным максимальным значением p (0IX), чтобы проверить, в этой статье необходимо доказать сходимость алгоритма EM. .
Шаг 1: Неравенство Гиббса:
Знак равенства имеет место тогда и только тогда, когда x=1
{PS: На самом деле, неравенство Гиббса является частным случаем неравенства Дженсена, потому что log(x) является выпуклой функцией. Если вы нарисуете график, вы можете обнаружить, что в определенный момент неравенство Гиббса и неравенство Дженсена имеют пересечения на кривой}
Шаг 2:
Теперь введем несколько теорем: если f(x), g(x) имеют одинаковую функцию плотности вероятности опорного множества, пусть теперь:
но:
доказывать:
Знак равенства имеет место тогда и только тогда, когда f(x)=g(x), тогда log(g(x)/f(x))=f(x)/g(x)-1
третий шаг:
Запишите оценочную последовательность EM-алгоритма как {0(k)} и докажите, что каждый шаг максимизации EM-алгоритма улучшает значение логарифмической функции правдоподобия L(0|X) для наблюдаемых данных, а именно:
Помните:
Доказательство: известно:
Тогда в соответствии с функциональной связью байесовских статистических априорных и апостериорных значений мы получаем:
Известно, что в предпосылке большой выборки и равномерного распределения 0, где p(x|0) — наблюдаемая плотность X, а p(y|x,0) — недостающие данные с учетом наблюдаемого данные Плотность данных:
Помните:
но:
тем самым:
и получить:
так:
Процесс максимизации ищется из M шагов:
Видно, что Q увеличивается, и получается теорема 1 со вторым шагом:
Здесь может быть известно, что функция правдоподобия постоянно увеличивается при попеременной работе шагов E и M алгоритма EM, и мы можем думать, что оцениваемая последовательность параметров в конечном итоге будет сходиться к оценке максимального правдоподобия.
Если на каждой итерации получается оценка максимального правдоподобия функции правдоподобия и вместо 0 выбирается максимизированный 0 (k + 1), это составляет алгоритм EM, и большую часть времени функция максимального правдоподобия выражений, но не всегда, поэтому иногда существует обобщенный алгоритм EM (GEM), в котором каждый шаг увеличения Q также увеличивает функцию логарифмического правдоподобия.
Здесь я привожу это без доказательства, вывод о сходимости в основном дается для значения логарифмической функции правдоподобия, а не для сходимости оцениваемой последовательности; и в общем случае мы используем алгоритм EM для получения Оценочное значение 0(k) может только гарантированно сходятся к стабильной точке функции правдоподобия, но не к точке глобального максимума или точке локального максимума.
Использованная литература:
Алгоритм EM Эндрю Нг
blog.CSDN.net/Zou Xiaoyun09/art…
Блог Woohoo.cn на.com/open EI/afraid/3…
И помощь других людей, спасибо им, следующим будет дополнительный метод для ускорения сходимости алгоритма EM, спасибо за чтение