Участник:Марина/Песочница
Материал из MachineLearning.
Строка 27: | Строка 27: | ||
Из формулы Байеса <br /> | Из формулы Байеса <br /> | ||
::<tex>g_{ij} = \frac{w_jp_j(x_i)}{\sum_{s=1}^k w_sp_s(x_i)} </tex> для всех <tex>i, j</tex>. | ::<tex>g_{ij} = \frac{w_jp_j(x_i)}{\sum_{s=1}^k w_sp_s(x_i)} </tex> для всех <tex>i, j</tex>. | ||
- | |||
* '''М-шаг''' <br /> | * '''М-шаг''' <br /> | ||
Строка 33: | Строка 32: | ||
::<tex>Q(\Theta) = \ln\prod_{i=1}^mp(x_i|w,\mu,\Sigma) = \sum_{i=1}^m\ln\sum_{j=1}^kw_jp_j(x_i) \rightarrow \max_{\Theta}</tex>. <br /> | ::<tex>Q(\Theta) = \ln\prod_{i=1}^mp(x_i|w,\mu,\Sigma) = \sum_{i=1}^m\ln\sum_{j=1}^kw_jp_j(x_i) \rightarrow \max_{\Theta}</tex>. <br /> | ||
Решая оптимизационную задачу Лагранжа с ограничением на сумму <tex>w_j</tex>, находим: <br /> | Решая оптимизационную задачу Лагранжа с ограничением на сумму <tex>w_j</tex>, находим: <br /> | ||
- | ::<tex>w_j = \frac1m sum_{i=1}^m g_{ij} , j = 1, \dots, k </tex> | + | ::<tex>w_j = \frac1m \sum_{i=1}^m g_{ij} ,\: j = 1, \dots, k </tex> |
- | ::<tex>\theta_j = arg max_{\theta} sum_{i=1}^m g_{ij}\ln\varphi(x_i,\theta) , j = 1, \dots, k </tex>. | + | ::<tex>\theta_j = arg \max_{\theta} \sum_{i=1}^m g_{ij}\ln\varphi(x_i,\theta) ,\: j = 1, \dots, k </tex>. |
=== Смесь нормальных распределений === | === Смесь нормальных распределений === | ||
+ | Далее часто будет встречаться смесь нормальных распределений, поэтому выпишем для нее результаты Е- и М-шага алгоритма: <br /> | ||
+ | <tex>\theta = (w_1,...,w_k;\mu_1,...,\mu_k;\sigma_1,...,\sigma_k)</tex> <br /> | ||
+ | <tex>p_j(x) = N(x;\mu_j, \sigma_j) = \frac1{\sqrt{2\pi}\sigma_j}exp{-\frac{(x - \mu_j)^2}{2\sigma_j^2}} </tex> | ||
+ | |||
+ | * E-шаг <br /> | ||
+ | ::<tex>g_{ij} = \frac{w_jN(x_i;\mu_j, \sigma_j)}{\sum_{s=1}^k w_sN(x_i;\mu_s, \sigma_s)} </tex> | ||
+ | |||
+ | * М-шаг <br /> | ||
+ | ::<tex>w_j = \frac1m\sum_{i=1}^m g_{ij}</tex> , | ||
+ | ::<tex>\mu_j = \frac1{mw_j}\sum_{i=1}^m g_{ij}x_i</tex> , | ||
+ | ::<tex>\sigma_j^2 = \frac1{mw_j}\sum_{i=1}^m g_{ij}(x_i - \mu_j)^2,\; j = 1, \dots, k</tex>. | ||
+ | |||
+ | == Недостатки ЕМ-алгоритма == | ||
+ | # ЕМ-алгоритм неуйстойчив по начальным данным (то есть тем, которые инициализируют вектор параметров <tex>\theta</tex> на первой итерации), так как он находит локальный экстремум, значение которого может оказаться гораздо ниже, чем глобальный максимум. В зависимости от выбора начального приближения алгоритм может сходиться к разным точкам. Также может сильно варьироваться скорость сходимости. | ||
+ | # ЕМ-алгоритм не позволяет определять количество <tex>k</tex> компонент смеси. Эта величина является структурным параметром алгоритма! | ||
+ | |||
+ | В связи с этим рассмотрим некоторые модификации ЕМ-алгоритма, так или иначе противоборствующие данным недостаткам. ?????? | ||
== Медианные модификации ЕМ-алгоритма == | == Медианные модификации ЕМ-алгоритма == | ||
Строка 57: | Строка 73: | ||
=== SEM-алгоритм с удалением клмпонент === | === SEM-алгоритм с удалением клмпонент === | ||
+ | |||
+ | == Смотрите также == | ||
+ | |||
+ | == Литература == | ||
+ | |||
+ | {{Задание|Марина|Константин Воронцов|8 января 2010}} |
Версия 20:13, 3 января 2010
EM-алгоритм (англ. expectation-maximization) - алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.
Как правило, ЕМ-алгоритм применяется для решения задач двух типов. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин. Ко второму типу задач можно отнести те задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные “ненаблюдаемые” (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.
Содержание |
Постановка задачи
Пусть плотность распределения на множестве имеет вид смеси
распределений:
,
,
,
где - функция правдоподобия j-й компоненты смеси,
- ее априорная вероятность.
Функции правдоподобия принадлежат параметрическому семейству распределений и отличаются только значениями параметра
.
Задача разделения смеси заключается в том, чтобы, имея выборку случайных и независимых наблюдений из смеси
, зная число
и функцию
, оценить вектор параметров
.
Основной алгоритм
Идея алгоритма заключается в следующем. Искусственно вводится вспомогательный вектор скрытых переменных , обладающий двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров
. С другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных.
EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных по текущему приближению вектора параметров
. На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора
по текущим значениям векторов
и
.
- Е-шаг
Обозначим через плотность вероятности того, что объект
получен из
-й компоненты смеси. По формуле условной вероятности
.
Введём обозначение
.
Это неизвестная апостериорная вероятность того, что обучающий объект получен из
-й компоненты смеси. Возьмём эти величины в качестве скрытых переменных.
, для любого
, так как имеет смысл полной вероятности принадлежать объекту
одной из
компонент смеси.
Из формулы Байеса
для всех
.
- М-шаг
Будем максимизировать логарифм полного правдоподобия:
.
Решая оптимизационную задачу Лагранжа с ограничением на сумму , находим:
.
Смесь нормальных распределений
Далее часто будет встречаться смесь нормальных распределений, поэтому выпишем для нее результаты Е- и М-шага алгоритма:
- E-шаг
- М-шаг
,
,
.
Недостатки ЕМ-алгоритма
- ЕМ-алгоритм неуйстойчив по начальным данным (то есть тем, которые инициализируют вектор параметров
на первой итерации), так как он находит локальный экстремум, значение которого может оказаться гораздо ниже, чем глобальный максимум. В зависимости от выбора начального приближения алгоритм может сходиться к разным точкам. Также может сильно варьироваться скорость сходимости.
- ЕМ-алгоритм не позволяет определять количество
компонент смеси. Эта величина является структурным параметром алгоритма!
В связи с этим рассмотрим некоторые модификации ЕМ-алгоритма, так или иначе противоборствующие данным недостаткам. ??????
Медианные модификации ЕМ-алгоритма
Первая медианная модификация
Вторая медианная модификация
SEM-алгоритм
CEM-алгоритм
MCEM-алгоритм
GEM-алгоритм
Модификации с добавлением/удалением компонент
EM-алгоритм с добавлением компонент
SEM-алгоритм с удалением клмпонент
Смотрите также
Литература
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |