Изменения

'''Алгоритм EM''' (англ: expectation-maximization) -- - итеративный алгоритм поиска оценок максимума правдоподобия параметров для решения задачмодели, в ситуации, где некоторые переменные не являются наблюдаемымикогда она зависит от скрытых(ненаблюдаемых) переменных.

'''E(Expectation)''' шаг --- поиск наиболее вероятных значений скрытых переменных. '''M(Maximisation) ''' шаг--- поиск наиболее вероятхын значений параметров, для полученных на шаге E значений скрытых переменных. EM алгоритм подходит для решения задач двух типов: # Задачи с неполными данными.# Задачи, в которых удобно вводить скрытые переменные для упрощения подсчета функции правдободобия. Примером такой задачи может служить кластеризация == Проблема восстановления распределения смеси ==  === Постановка задачи === Плотность распределения смеси имеет вид:<br/><tex>p(x) = \sum\limits_{i=1}^k \omega_j p_j(x)</tex><br/>Где <tex> \sum\limits_{i=1}^k w_j = 1; w_j >= 0; p_j(x) = \phi(x;\theta_j)</tex> - функция правдоподобия <tex>j</tex>-ой компонеты смеси, <tex>\omega_j</tex> - априорная вероятность <tex>j</tex>-ой компоненты распределения.<br/> Перед нами стоит две задачи:<br/> # По заданной выборке <tex>X^m</tex> случайных и независимых наблюдений полученных из смеси <tex>p(x)</tex>, числу <tex>k</tex> и функцию <tex>\phi</tex>, оценить вектор параметров <tex>\Theta = (\omega_1,..,\omega_k,\theta_1,..,\theta_k)</tex># Найти <tex>k</tex> === Проблема ===  Задачи подобного рода мы умеем решать максимизируя логармиф правдоподобия:<br><tex> L(\Theta) = ln \prod\limits_{i=1}^mp(x_i) = \sum\limits_{i=1}^m ln\sum\limits_{j=1}^k w_j p_j(x_i; \theta_j) \longrightarrow max</tex><br/> Но пробелма в том, что мы не знаем как аналитически посчитать логарифм суммы. Тут нам и поможет алгоритм EM. === Решение ===  Основная идея алгоритма EM заключается в котором находится распределение том, что мы добавляме скрытые переменные такие, что:<br/> # Они могут быть выражены через <tex>\Theta</tex># Они помогают разбить сумму так: <tex>p (X, H|\Theta) = \prod\limits_{i=1}^k p (X|H, \Theta) p(H|\Theta)</tex>, где <tex>H</tex> - матрица скрытых переменных используя значение наблюдаемых переменных и текущего . Тогда алгоритм EM сводится к повторению шагов, указанных в [[#Определение|Определение]]. === E-шаг ===  <tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex> <br /> Скрытые переменные представляют из себя матрицу <tex>H = (h_{ij})_{m \times k}</tex><br/>где <tex>h_{ij} = P(\theta_j | x_i)</tex> - вероятность того, что <tex>x_i</tex> пренадлежит <tex>j</tex>-ой компоненте.<br/> По формуле Байеса справедливо равенство:<br /><tex> h_{ij} = \frac{w_jp_j(x_i)}{p (x_i)} = \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^k w_s p_s(x_i)}</tex><br/> Также <tex>\sum\limits_{j=1}^k h_{ij} = 1</tex><br/> Таким образом, зная значения вектора параметров<tex>\Theta</tex>, мы легко можем пересчитать значения скрытых переменных<br/> === M-шаг ===  {{Теорема|statement=Если известны скрытые переменные, то задача минимизации <tex>Q(\Theta)</tex> сводится к <tex>k</tex> независимым подзадачам:<br/><center><tex>\theta_j = argmax_{\theta} \sum\limits_{i=1}^m h_{ij}*ln \phi (x_i, \theta)</tex></center>Оптимальные же веса считаются как:<br/><center><tex> w_j = \frac {1} {m} \sum\limits_{i=1}^m h_{ij}</tex></center>}} === Псевдокод ===   Input:<tex>X^m, k, \theta^{(0)}</tex> Repeat '''E-step''': for all i = 1..m; j = 1..k: <tex>h_{ij} = \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^k w_s p_s(x_i)}</tex> '''M-step''': for all j = 1..k: <tex>\theta_j = argmax_{\theta} \sum\limits_{i=1}^m h_{ij}*ln \phi (x_i, \theta)</tex> <tex>w_j = \frac {1} {m} \sum\limits_{i=1}^m h_{ij}</tex> Until stopping criteria is satisfied