第 2 回 HMMゼミ EMアルゴリズム

第 2 回 HMM ゼミ
EM アルゴリズム
徳田・李研究室宇藤陽介
1
尤度
尤度とは，
「ある確率論的モデルを仮定した状況下で，観測データがそのモデルから出力される
確率」である．つまり，そのモデルに観測データがどれくらいあてはまっているのかという尺度の
ことである．学習データに対する尤度が高いほどそのモデルは学習データを正確に表現していると
いうことになる．
例えば，表を出す確率が 0.8，裏が出る確率が 0.2 のコインをコイン 1(モデル 1)，表を出す確率
が 0.6，裏が出る確率が 0.4 のコインをコイン 2(モデル 2) とする．このとき，どちらかのコインだ
けを投げて事象「表，裏，表，表」が出たとする．このとき，どちらのコインを投げたと考えるの
が妥当であろうか?
この場合はコイン 1 である．つまり，事象「表，裏，表，表」に対してはコイン 1(モデル 1) の
方が尤度が高いということになる．
モデルを λ，学習データを X = [x1 , x2 , . . . , xT ] とした場合，尤度関数は一般的に以下のように
表される．
L(λ) = P (X|λ)
=
T
Y
t=1
P (xt |λ)
以上をふまえて先ほどのコインの問題において尤度を実際に計算すると以下のようになる．
• コイン 1
L(コイン 1) = 0.8 × 0.2 × 0.8 × 0.8 = 0.1024
• コイン 2
L(コイン 2) = 0.6 × 0.4 × 0.6 × 0.6 = 0.0864
このように，コイン 1 の方がコイン 2 よりも尤度が高いことが計算によってもわかる．
1
(1)
最尤推定 (Maximum Likelihood Estimation)
2
与えられた学習データに対する尤度を最大にするためにモデルパラメータを推定することを最尤
推定 (Maximum Likelihood Estimation) という．つまり，最尤推定とは最も尤度が高くなるパラ
メータ
λmax
= arg max L(λ)
λ
T
Y
= arg max
P (xt |λ)
λ t=1
(2)
を求めることである．ただし，このままだと T 回の掛け算を行う必要があり計算が大変なため，log
をとって掛け算を足し算にする．
λmax
= arg max log L(λ)
λ
T
X
= arg max
logP (xt |λ)
λ t=1
(3)
x が単調増加すると log x も単調増加するため，対数尤度を最大化することは尤度を最大化するこ
とと等しくなる．
2.1
ガウス分布 (1 次元) の ML 推定
1 次元のガウス分布を表すモデルパラメータの平均と分散をそれぞれ µ, σ 2 と表す．この時，こ
のガウス分布の尤度関数は以下のように表される．
L(λ)
=
T
Y
t=1
P (xt |λ)
½
¾
(xt − µ)2
√
exp −
=
2σ 2
2πσ 2
t=1
T
Y
logL(λ)
=
T
X
t=1
=
1
logP (xt |λ)
¾
T ½
X
1
(xt − µ)2
1
− log2π − logσ 2 −
2
2
2σ 2
t=1
(4)
式 (4) を µ で偏微分して 0 とおき，最適な µ を求める．
∂logL(λ)
∂µ
T
X
xt
=
T
X
2(xt − µ)
t=1
=
t=1
T
X
2σ 2
=0
µ = Tµ
t=1
µ =
T
1X
xt
T t=1
2
(5)
同様に σ 2 で偏微分して 0 とおき，最適な σ 2 を求める．
¾
T ½
X
1
(xt − µ)2
=0
=
− 2+
2σ
2(σ 2 )2
t=1
∂logL(λ)
∂σ 2
T
X
©
t=1
−σ 2 + (xt − µ)2
T
X
ª
= 0
σ2
=
t=1
T
X
t=1
T σ2
=
T
X
t=1
σ2
2.2
=
(xt − µ)2
(xt − µ)2
T
1X
(xt − µ)2
T t=1
(6)
ガウス分布 (多次元) の ML 推定
d 次元ガウス分布を表すモデルパラメータの平均ベクトルと共分散行列をそれぞれ，µ, Σ と表
す．この時，このガウス分布の尤度関数は以下のように表される．
L(λ)
=
T
Y
P (xt |λ)
T
X
log P (xt |λ)
t=1
=
log L(λ)
=
½
¾
1
1
p
exp − (xt − µ)> Σ−1 (xt − µ)
2
(2π)d |Σ|
t=1
T
Y
t=1
¾
T ½
X
d
1
1
−1
T −1
=
− log 2π + log |Σ| − (xt − µ) Σ (xt − µ)
2
2
2
t=1
(7)
式 (7) をµで偏微分して 0 とおき，最適な µ を求める．
∂logL(λ)
∂µ
T
X
t=1
(xt − µ)
T
X
µ
=
T
X
t=1
−Σ−1 (xt − µ) × (−1) = 0
= 0
=
t=1
T
X
xt
t=1
µ
=
T
1X
xt
T t=1
(8)
ただし，以下の関係を用いている．
∂ >
y Ay = 2Ay
∂y
3
(9)
同様に，Σ−1 で偏微分して 0 とおき，最適な Σ を求める．
∂L(λ)
∂Σ−1
T
X
=
Σ =
t=1
T ½
X
1
t=1
T
X
©
t=1
Σ =
1
Σ − (xt − µ)(xt − µ)>
2
2
(xt − µ)(xt − µ)>
¾
=0
ª
T
ª
1 X©
(xt − µ)(xt − µ)>
T t=1
(10)
ただし，以下の関係を用いている．
∂ log |A|−1
= A> = A,
∂A−1
∂a> Ab
= ab>
∂A
(11)
このように，ガウス分布のような単純なモデルでは，尤度関数を偏微分することにより最適なモデ
ルパラメータを簡単に求めることができる．しかし，もっと複雑なモデル (例えば，ガウス混合モ
デル (Gaussian Mixture Model)) のパラメータ推定は尤度関数から直接行うことはできない．そこ
で，EM アルゴリズムを用いて推定を行う．
EM アルゴリズム
3
3.1
EM アルゴリズムとは
EM(Expectation Maximum) アルゴリズムとは，観測できるデータ (可観測データ) の他に，観
測することができないデータ (非観測データ) が存在する場合に最尤推定を行うための手法である．
名前の通り期待値を最大にするアルゴリズムであり，具体的には，非観測データの期待値を最大に
近づけることにより，尤度最大化を実現する．
EM アルゴリズムでは，期待値を表すために，以下の Q 関数を導入する．ただし，x, y はそれ
ぞれ可観測データ，非観測データ，λ, λ̄ はそれぞれ，現在のモデルパラメータ，新しいモデルパラ
メータを表す．
¡
¢
Q λ, λ̄
£
¡
¢
¤
= E log P x, y|λ̄ |x, λ
Z
¡
¢
=
P (y|x, λ) log P x, y|λ̄ dy
Z
¡
¢
P (x, y|λ)
=
log P x, y|λ̄ dy
P (x|λ)
(12)
この Q 関数では，以下の関係が成り立つ．
¡
¢
¡
¢
Q λ, λ̄ ≥ Q (λ, λ) ⇒ P x|λ̄ ≥ P (x|λ)
4
(13)
¶
式 (13) の証明
³
¡
¢
Q λ, λ̄ − Q (λ, λ)
Z
Z
¡
¢
=
P (y|x, λ) log P x, y|λ̄ dy − P (y|x, λ) log P (x, y|λ)dy
Z
Z
¡
¢
P (x, y|λ)
P (x, y|λ)
=
log P x, y|λ̄ dy −
log P (x, y|λ) dy
P (x|λ)
P (x|λ)
¡
¢
Z
P x, y|λ̄
P (x, y|λ)
=
log
dy
P (x|λ)
P (x|λ)
Ã ¡
!
¢
Z
P (x, y|λ) P x, y|λ̄
− 1 dy
≤
P (x|λ)
P (x, y|λ)
Z
© ¡
¢
ª
1
=
P x, y|λ̄ − P (x, y|λ)dy
P (x|λ)
© ¡
¢
ª
1
P x|λ̄ − P (x|λ)dy
=
P (x|λ)
¡
¢
P x|λ̄
=
−1
P (x|λ)
¡
¢
ここで，Q λ, λ̄ ≥ Q (λ, λ) が満たされると，
¡
¢
P x|λ̄
−1≤0
P (x|λ)
となる．以上より，
¡
¢
¡
¢
Q λ, λ̄ ≥ Q (λ, λ) ⇒ P x|λ̄ ≥ P (x|λ)
が満たされる．
µ
EM アルゴリズムでは式 (12) の Q 関数を用いて，以下のようにしてパラメータを最適な値へと近
づける．
1. 初期推定値 λ を与える
2. Q(λ, λ̄) を計算する (E ステップ)
3. Q(λ, λ̄) を λ̄ に関して最大化する (M ステップ)
4. 現在のモデルパラメータ λ を λ̄ で置き換える
以上の 2∼4 をある程度収束するまで繰り返す
3.2
GMM のパラメータ推定
¡
¢
Q λ, λ̄
=
T
X
t=1
¡
¢
Qt λ, λ̄
5
´
=
T Z
X
¡
¢
P (y t |xt , λ) log P xt , y t |λ̄ dy t
t=1
=
T X
M
X
t=1 yt =1
=
P (yt |xt , λ) log P̄yt P (xt |ϕ̄yt )
T X
M
X
P (xt , yt |λ)
log P̄yt P (xt |ϕ̄yt )
P (xt |λ)
t=1 y =1
t
=
T X
M
X
t=1 yt
=
Pyt P (xt |ϕyt )
log P̄yt P (xt |ϕ̄yt )
P (xt |λ)
=1
M X
T
X
Pi P (xt |ϕi )
i=1 t=1
P (xt |λ)
log P̄i +
M X
T
X
Pi P (xt |ϕi )
i=1 t=1
P (xt |λ)
log P (xt |ϕ̄i )
• P̄i に関して最大化
M
X
条件 :
P̄i = 1
¶
³
i=1
参考
²=
N
X
ωj log yj を
j=1
N
X
j=1
⇒ ラグランジ法
E=
yj = 1 の下で {y1 , y2 , · · · , yN } に関して最大化
N
X
j=1
N
X
ωj log yj − λ(
yj − 1)
j=1
を λ と {y1 , y2 , · · · , yN } に関して最大化する．

ωj
∂E


=
−λ=0

 ∂yj
yj
N
X
∂E


=
yj − 1 = 0

 ∂λ
j=1
ωj = λyj
N
X
ωj = λ
j=1
yj =
µ
N
X
yj
j=1
ωj
ωj
= N
λ
X
ωl
l=1
P̄i
=
T
X
Pi P (xt |ϕi )
t=1
M X
T
X
l=1 t=1
6
P (xt |λ)
Pl P (xt |ϕl )
P (xt |λ)
´
T
1 X Pi P (xt |ϕi )
T
P (xt |λ)
=
(14)
k=t
• µ̄ に関して最大化
∂Q(λ, λ̄)
∂ µ̄i
µ̄i
=
T
X
Pi P (xt |ϕi )
P (xt |λ)
t=1
=
T
X
Pi P (xt |ϕi )
P (xt |λ)
t=1
T
X
=
xt
Pi P (xt |ϕi )
P (xt |λ)
t=1
T
X
−1
Σ̄i (xt − µ̄i ) = 0
P (i|xt , λ)xt
t=1
T
X
(15)
P (i|xt , λ)
t=1
• Σ̄ に関して最大化
∂Q(λ, λ̄)
−1
∂ Σ̄i
Σ̄i
=
T
X
Pi P (xt |ϕi ) 1 ©
t=1
P (xt |λ) 2
=
T
X
Pi P (xt |ϕi )
=
T
X
t=1
P (xt |λ)
ª
=0
(xt − µ̄i )(xt − µ̄i )T
T
X
Pi P (xt |ϕi )
P (xt |λ)
t=1
t=1
Σ̄i − (xt − µ̄i )(xt − µ̄i )T
P (i|xt , λ)(xt − µ̄i )(xt − µ̄i )T
T
X
(16)
P (i|xt , λ)
t=1
7

Download Report