EM-алгоритм с последовательным добавлением компонент (пример)

Материал из MachineLearning.

Версия от 14:49, 29 апреля 2009; Pavlov99 (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Постановка задачи
2 Алгоритм отыскания оптимальных параметров
3 Смотри также
4 Литература

EM-алгоритм с последовательным добавлением компонент (пример) — общий метод нахождения функции плотности распределения объектов. Предполагается, что она имеет вид смеси $k$ распределений. В данной статье рассматривается гауссовское распредение выборки, количество гауссианов произвольно.

Постановка задачи

Задана выборка $\{(\mathbf{x}_i,y_i)\}_{i=1}^{\ell}$ , в которой $X^{\ell}$ = $\{\mathbf{x}_i\}_{i=1}^{\ell}$ - множество объектов, $Y^{\ell}$ = $\{\mathbf{y}_i\}_{i=1}^{\ell}$ - множество ответов. Предполагается, что объекты имеют плотность распределения $p(x)$ , представимую в виде смеси $k$ гауссиан с параметрами $\mu$ и $\Sigma$ .

$p(x) = \sum_{i=1}^k w_jp_j(x) = \sum_{i=1}^k w_jN(x;\mu_j,\Sigma_j)$

Задача разделения смеси заключается в том, чтобы, имея выборку $X^m$ случайных и независимых наблюдений из смеси $p(x)$ оценить вектор параметров $\theta = (w_1,...,w_k,\mu_1,...,\mu_k,\Sigma_1,...,\Sigma_k)$ доставляющий максимум функции правдоподобия

$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$

Алгоритм отыскания оптимальных параметров

Оптимальные параметры отыскиваются последовательно с помощью EM-алгоритма. Идея заключается во введении вспомогательного вектора скрытых переменных $G$ , обладающего двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров $\Theta$ , с другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных. EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вы- числяется ожидаемое значение (expectation) вектора скрытых переменных $G$ по те- кущему приближению вектора параметров $\Theta$ . На М-шаге решается задача максими- зации правдоподобия (maximization) и находится следующее приближение вектора $\Theta$ по текущим значениям векторов $G$ и $\Theta$ . Если число компонент смеси заранее не известно, то применяется EM-алгоритм с последовательным добавлением компонент. Если при каком-либо $k$ число неправильно классифицированных объектов превышает допустимое, то $k$ увеличивается и повторяется EM( $X,k_{new}$ )

Вход:

Выборка $X^m = \{x_1,...,x_m\}$ ; $R$ - максимальный допустимый разброс правдоподобия объектов; $m_0$ - минимальная длина выборки, по которой можно восстановить плотность; $\delta$ - параметр критерия останова;

Выход:

$k$ - число компонент смеси; $\Theta = (w_j,\mu_j,\Sigma_j)_{j=1}^k$

Алгоритм

1. начальное приближение - одна компонента:
     $k:=1; \qquad w_1:=1; \qquad \mu_1=\frac{1}{w_1}\sum_{i=1}^m g_{i1}x_i; \qquad \Sigma_1 = \frac{1}{mw_1}\sum_{i=1}^m g_{i1}(x_i-\mu_j)(x_i-\mu_j)^{T};$
2. для всех $k:= 2,3,4...$
3.      выделить объекты с низким правдоподобием
         $U:= \{x_i \in X^m\ | ~ p(x_i) < \frac{max ~ p(x_j)}{R} \}$
4.      Если $|U|<m_0$ то выход из цикла по $k$
5.      Начальное приближение для $k$ компоненты:
         $w_k:=\frac{1}{m}|U|; \qquad \mu_k=\frac{1}{mw_k}\sum_{i=1}^m g_{ik}x_i; \qquad \Sigma_k = \frac{1}{mw_k}\sum_{i=1}^m g_{ik}(x_i-\mu_j)(x_i-\mu_j)^{T};$
         $w_j:=w_j(1-w_k) \qquad j = 1,...,k-1;$
6.     $EM(X^m,k,\Theta,\delta);$