Участник:Pavlov99

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 4: Строка 4:
== Постановка задачи ==
== Постановка задачи ==
-
Задана выборка <tex>\{(\mathbf{x}_i,y_i)\}_{i=1}^l</tex>, в которой <tex>X^l</tex> = <tex>\{\mathbf{x}_i\}_{i=1}^l</tex> - множество объектов, <tex>Y^l</tex> = <tex>\{\mathbf{y}_i\}_{i=1}^l</tex> - множество ответов. Предполагается, что объекты имеют плотность распределения <tex>p(x)</tex>, представимую в виде смеси <tex>k</tex> гауссиан с параметрами <tex>\mu</tex> и <tex>\Sigma</tex>.
+
Задана выборка <tex>\{(\mathbf{x}_i,y_i)\}_{i=1}^{\ell}</tex>, в которой <tex>X^{\ell}</tex> = <tex>\{\mathbf{x}_i\}_{i=1}^{\ell}</tex> - множество объектов, <tex>Y^{\ell}</tex> = <tex>\{\mathbf{y}_i\}_{i=1}^{\ell}</tex> - множество ответов. Предполагается, что объекты имеют плотность распределения <tex>p(x)</tex>, представимую в виде смеси <tex>k</tex> гауссиан с параметрами <tex>\mu</tex> и <tex>\Sigma</tex>.
<center><tex>p(x) = \sum_{i=1}^k w_jp_j(x) = \sum_{i=1}^k w_jN(x;\mu_j,\Sigma_j)</tex></center>
<center><tex>p(x) = \sum_{i=1}^k w_jp_j(x) = \sum_{i=1}^k w_jN(x;\mu_j,\Sigma_j)</tex></center>
Строка 12: Строка 12:
== Алгоритм отыскания оптимальных параметров ==
== Алгоритм отыскания оптимальных параметров ==
-
Оптимальные параметры отыскиваются последовательно с помощью EM-алгоритма. Идея заключается во введении вспомогательного вектора скрытых переменных
+
Оптимальные параметры отыскиваются последовательно с помощью EM-алгоритма. Идея заключается во введении вспомогательного вектора скрытых переменных <tex>G</tex>, обладающего двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров <tex>\Theta</tex>, с другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных.
 +
EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вы-
 +
числяется ожидаемое значение (expectation) вектора скрытых переменных <tex>G</tex> по те-
 +
кущему приближению вектора параметров <tex>\Theta</tex>. На М-шаге решается задача максими-
 +
зации правдоподобия (maximization) и находится следующее приближение вектора <tex>\Theta</tex>
 +
по текущим значениям векторов <tex>G</tex> и <tex>\Theta</tex>.
 +
Если число компонент смеси заранее не известно, то применяется EM-алгоритм с последовательным добавлением компонент. Если при каком-либо <tex>k</tex> число неправильно классифицированных объектов превышает допустимое, то <tex>k</tex> увеличивается и повторяется EM(<tex>X,k_{new}</tex>)
 +
*'''Вход:'''
 +
Выборка <tex>X^m = \{x_1,...,x_m\}</tex> ;
 +
<tex>R</tex> - максимальный допустимый разброс правдоподобия объектов;
 +
<tex>m_0</tex> - минимальная длина выборки, по которой можно восстановить плотность;
 +
<tex>\delta</tex> - параметр критерия останова;
 +
*'''Выход:'''
 +
<tex>k</tex> - число компонент смеси;
 +
<tex>\Theta = (w_j,\mu_j,\Sigma_j)_{j=1}^k</tex>
 +
*Алгоритм
 +
1. начальное приближение - одна компонента:<br />
 +
&nbsp;&nbsp;&nbsp;&nbsp; <tex>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}; </tex><br />
 +
2. для всех <tex>k:= 2,3,4... </tex><br />
 +
3. &nbsp;&nbsp;&nbsp;&nbsp; выделить объекты с низким правдоподобием <br />
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tex>U:= \{x_i \in X^m\ | ~ p(x_i) < \frac{max ~ p(x_j)}{R} \}</tex> <br />
 +
4. &nbsp;&nbsp;&nbsp;&nbsp; Если <tex>|U|<m_0</tex> то выход из цикла по <tex>k</tex><br />
 +
5. &nbsp;&nbsp;&nbsp;&nbsp; Начальное приближение для <tex>k</tex> компоненты: <br/>
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>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}; </tex><br/>
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>w_j:=w_j(1-w_k) \qquad j = 1,...,k-1;</tex><br/>
 +
6.&nbsp;&nbsp;&nbsp;&nbsp; <tex>EM(X^m,k,\Theta,\delta);</tex><br/>
 +
 
 +
== Смотри также ==
 +
* [[Метод ближайших соседей]]
 +
* [[Многомерная случайная величина]]
 +
 
 +
==Литература==
 +
*К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации
 +
 
 +
[[Категория:Кластеризация данных]]
 +
[[Категория:Популярные и обзорные статьи]]
 +
[[Категория:Библиотеки алгоритмов]]

Версия 14:45, 29 апреля 2009

Содержание

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);

Смотри также

Литература

  • К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Pavlov99»
Личные инструменты