== Определение == '''Алгоритм EM ''' - алгоритм поиска максимума правдоподобия параметров для решения задач, где некоторые переменные не являются наблюдаемыми.
Алгоритм ищет параметры модели итеративно, каждая итерация состоит из двух шагов:
'''E(Expectation''') шаг, в котором находится распределение скрытых переменных используя значение наблюдаемых переменных и текущего значения параметров. '''M(Maximisation)''' шаг - пересчет параметров, находя максимум правдоподобия исходя из распределения скрытых переменных, полученных на E - шаге. == Задача разделения смеси распределений == '''Общий алгоритм''' {{---}} '' Необходимо описать плотность распределения функции на X как сумму k функций, которые можно рассматривать как элементы параметрического семейства функций <tex> p_j(x) = \phi(x;\theta_j)</tex>. Плотность распределения будет выглядеть как <br><tex>p(x) = \sum\limits_{i=1}^k \omega_j p_j(x); \sum\limits_{i=1}^k w_j = 1; w_j >= 0 </tex> <br /> где <tex>\omega_j</tex>- априорная вероятность j компоненты распределения.Задача разделения смеси заключается в том, чтобы, имея выборку <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> E-шаг: <tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex> <br />Введем обозначение: <tex> g_{ij} = P(\theta_j | x_i) </tex> это и будут скрытые параметры данной задачи - апостериорная вероятность того, что обучающий объект <tex> x_i </tex> получен из <tex>j</tex>-й компоненты По формуле Байеса справедливо равенство:<br /><tex> g_{ij} = \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^k w_t p_t(x_i)}</tex><br />Таким образом при зная значение параметров легко найти скрытые переменные. Перейдем к M-шагу: Посчитаем для аддитивности логарифм правдоподобия:<br /><tex> Q(\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) \longrightarrow max</tex> <br />при условии <tex>\sum\limits_{i=1}^k w_j = 1; w_j >= 0</tex> имеет смысл рассматривать лагранжиан задачи:<br /><tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{p_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} - \lambda = 0</tex><br />
M(Maximisation) шаг - пересчет параметров, находя максимум правдоподобия исходя из распределения скрытых переменных, полученных Умножим на E - шаге.<tex>\omega_j</tex> и просумируем уравнения для всех <tex>j</tex> <br />
<tex>\sum\limits_{j=1}^k \sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = \lambda \sum\limits_{j=1}^kw_j</tex> <br />
----Так как можно заменить порядок суммы и <tex>\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = 1</tex> и <tex>\sum\limits_{j=1}^kw_j = 1</tex> из чего следует <tex>\lambda = m</tex> <br />
<tex>\omega_j = \frac{1}{m}\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = \frac{1}{m}\sum\limits_{i=1}^mg_{ij}</tex><br />
== k-means как EM алгоритм ==Приравняв к нулю лагранжиан по <tex>\theta_j</tex> схожим способом найдем:<br />
Скрытыми переменными в данной задаче являются классы, к которым относятся объекты для кластеризации. Сами же параметры это центры масс классов. На шаге E - распределяются все объекты по классам исходя из расстояния от центра, на шаге M находится оптимальное месторасположение центра.<tex> \theta_j = arg \max\limits{\theta}\sum\limits_{i=1}^mg_{ij}ln(\phi(x_i;\theta)) </tex><br />
Аналогично рассматривается и алгоритм c-means. Скрытые переменные здесь будут вероятности принадлежности к классам, которые находятся на E-шаге по расстоянию от центра. Центр так же рассчитывается Таким образом на M-шаге исходя из скрытых переменныхнеобходимо взять среднее значение <tex>g_{ij}</tex> и решить k независимых оптимизационных задач.
'''Разделение смеси гауссиан''' {{----}} ''
Важным на практике примером является случай, когда параметрическое семейство - нормальные распределения. Параметрами функций будут являться матожидание и дисперсия.<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>
Суть
Необходимо описать плотность распределения функции на X как сумму k функций, которые можно рассматривать как элементы параметрического семейства функций <tex> p_j(x) = \phi(x;\theta_j)</tex>. Плотность распределения будет выглядеть как <tex>p(x) = \sum\limits_{i=1}^k \omega_j p_j(x); \sum\limits_{i=1}^k w_j = 1; w_j >= 0 </tex> где <tex>\omega_j</tex> - априорная вероятность j компоненты распределения.
Задача разделения смеси заключается в том, чтобы, имея выборку <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>
E== k-шаг:means как EM алгоритм ==
<tex>p(xСкрытыми переменными в данной задаче являются классы,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex>к которым относятся объекты для кластеризации. Сами же параметры это центры масс классов. На шаге E - распределяются все объекты по классам исходя из расстояния от центра, на шаге M находится оптимальное месторасположение центра.
Введем обозначение: <tex> g_{ij} = P(\theta_j | x_i) </tex> это Аналогично рассматривается и алгоритм c-means. Скрытые переменные здесь будут скрытые параметры данной задачи вероятности принадлежности к классам, которые находятся на E- апостериорная вероятность того, что обучающий объект <tex> x_i </tex> получен шаге по расстоянию от центра. Центр так же рассчитывается на M-шаге исходя из <tex>j</tex>-й компоненты скрытых переменных.
По формуле Байеса справедливо равенство <tex> g_{ij} = \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^k w_t p_t(x_i)}</tex>
Таким образом при зная значение параметров легко найти скрытые переменные.
Перейдем к M-шагу:== См. также ==*[[Кластеризация]]
Посчитаем для аддитивности логарифм правдоподобия:<tex> Q(\Theta) = ln \mul\limits_{i=1}^mp(x_i) Источники информации = \sum\limits_{i=1}^mln\sum\limits_{j=1}^kw_jp_j(x_i) -> max\limits{Theta} </tex>
при условии <tex>\sum\limits_{i=# [http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1}^.pdf Математические методы обучения по прецедентам К. В. Воронцов]# [http://dendroid.sk/2011/05/09/k w_j = 1; w_j >= 0<-means-clustering/tex> имеет смысл расcматривать лагранжиан задачи:k-means]
<tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} - \lambda = 0</tex>[[Категория:Машинное обучение]]
