Известно, что ЕМ-алгоритм для задачи разделения смесей распреде-
ления имеет ряд преимуществ перед другими методами оптимизации,
такими как проекция градиента и ньютоновские алгоритмы [19].
ЕМ-алгоритм состоит из итерационного повторения двух шагов. На
Е-шаге вычисляется ожидаемое значение (expectation) вектора скры-
тых переменных по текущему приближению вектора параметров
Θ
. На
М-шаге решается задача максимизации правдоподобия (maximization)
и находится следующее приближение вектора
Θ
по текущим значе-
ниям.
Е-шаг (expectation).
Найдем
p
(
x, θ
i
)
— плотность вероятности того,
что объект
x
получен из
i
-го компонента смеси. По формуле условной
вероятности:
p
(
x, θ
i
) =
p
(
x
)
P
(
θ
i
|
x
) =
w
i
p
i
(
x
)
.
Введем обозначение
g
ji
≡
P
(
θ
i
|
x
j
)
. Это неизвестная апостериорная ве-
роятность того, что обучающий объект
x
j
получен из
i
-го компонента
смеси. Возьмем эти величины в качестве скрытых переменных. Обо-
значим
G
= (
g
ji
)
m
×
k
= (
g
1
, . . . , g
i
)
, где
g
i
—
i
-й столбец матрицы
G
.
Предполагается, что каждый объект может быть сгенерирован одним
и только одним компонентом. Согласно формуле полной вероятности
отсюда следует условие нормировки для
g
ij
:
k
X
i
=1
g
ji
= 1
для всех
j
= 1
, . . . , l.
Зная параметры компонентов
w
i
, θ
i
, легко вычислить
g
ji
по формуле
Байеса:
g
ji
=
w
i
p
i
(
x
j
)
k
X
s
=1
w
s
p
s
(
x
j
)
для всех
i, j.
В этом и заключается E-шаг алгоритма EM.
M-шаг (maximization).
Покажем, что знание значений скрытых пе-
ременных
g
ji
и принцип максимума правдоподобия приводят к опти-
мизационной задаче, допускающей эффективное численное решение.
Будем максимизировать логарифм правдоподобия
Q
(Θ) = ln
m
Y
j
=1
p
(
x
j
) =
m
X
j
=1
ln
k
X
i
=1
w
i
p
j
(
x
j
)
→
max
Θ
Q
(Θ)
при ограничении
k
X
i
=1
w
i
= 1
. Запишем лангранжиан этой оптимизаци-
142
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
1,2,3,4,5,6,7,8,9 11,12,13,14,15,16,17,18,19,...20