15
правок
Изменения
Сделал мелкие правки по форматированию
== Определение ==
'''Алгоритм EM''' (англ: expectation-maximization) {{--- }} итеративный алгоритм поиска оценок максимума правдоподобия модели, в ситуации, когда она зависит от скрытых(ненаблюдаемых) переменных.
Алгоритм ищет параметры модели итеративно, каждая итерация состоит из двух шагов:
'''E(Expectation)''' шаг {{--- }} поиск наиболее вероятных значений скрытых переменных.
'''M(Maximisation)''' шаг {{--- }} поиск наиболее вероятных значений параметров, для полученных на шаге E значений скрытых переменных.
EM алгоритм подходит для решения задач двух типов:
Плотность распределения смеси имеет вид:<br/>
<tex>p(x) = \sum\limits_{j=1}^k \omega_j w_j p_j(x)</tex><br/>Где <tex> \sum\limits_{j=1}^k w_j = 1; w_j \geq 0; p_j(x) = \phi(x;\theta_j)</tex> {{--- }} функция правдоподобия <tex>j</tex>-ой компонеты смеси, <tex>\omega_jw_j</tex> {{--- }} априорная вероятность <tex>j</tex>-ой компоненты распределения.<br/>
Перед нами стоит две задачи:<br/>
# По заданной выборке <tex>X^m</tex> случайных и независимых наблюдений полученных из смеси <tex>p(x)</tex>, числу <tex>k</tex> и функцию <tex>\phi</tex>, оценить вектор параметров <tex>\Theta = (\omega_1w_1,..,\omega_kw_k,\theta_1,..,\theta_k)</tex>
# Найти <tex>k</tex>
Скрытые переменные представляют из себя матрицу <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 />
=== Критерий остановки ===
Алгоритм EM вы полняется до сходимости, но как нам определить, что сходимость наступила?. Мы можем останавливаться, когда либо <tex>Q(\Theta)</tex>, либо <tex>H</tex> перестают сильно меняться. Но, обычно, удобней контролировать изменения значений скрытых переменных, так как они имеют смысл вероятностей и принимают значения из отрезка <tex>[0,1]</tex>. Поэтому один из возможных критериев остановки будет выглядеть так: <tex>max_\max\limits_{i,j} |h_{ij} - h_{ij}^{(0)}| > \delta</tex>
=== Псевдокод ===
Каноническим примером использования EM алгоритма является задача разделения смеси гауссиана. Данные у нас получены из нормального распределения. В этом случае параметрами функций ялвяются матожидание и дисперсия.<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 \biggl(-\frac{(x - \mu_j)^2}{2\sigma_j^2}\biggr) </tex> - плотность распределения <br/>
