情報意味論（7） EM より複雑なモデル例: 混合正規分布

by user

on 28 марта 2017

Category: Documents

>> Downloads: 0

views

Report

Comments

Description

Download 情報意味論（7） EM より複雑なモデル例: 混合正規分布

Transcript

情報意味論（7） EM より複雑なモデル例: 混合正規分布

より複雑なモデル
情報意味論（7） EM

確率モデルであって、一個の著名(?)な分布で表せないもの、… で
表せそうもないもの、…ではなさそうなものが、世の中にはたくさんあ
る。

様々な分布を考える

分布を組み合わせる

櫻井彰人
慶應義塾大学理工学部

正規分布（ガウス混合）の線形和
線形和 – 非観測変数の出現
しかし、工夫がある → EMアルゴリズム
分布を考えない – しょせん、多項分布

例: 混合正規分布
指数・ポアソン・t・対数正規・…
変数が多いと大変。
しかし、工夫がある → Bayesian network
推定の面倒さ
データが一個の正規分布から生成されることがわかっていれば、
その分布を推定することができる（平均と分散を推定すればよい。
最尤推定すればよい）。例えば
0.15
m
µ ML = argmin ∑ ( xi − µ ) =
0.10
線形和（重みの和は１）
p(x) = ∑ πj pj(x)
0.0
0.05
考え方: 各データは、まず、 j のどれか
をランダムに選び（確率分布は {πj} ）、
次に pj に従い生成される
| | | ||||||||||||||||||||| |||||||| || ||
-10
-5
|| ||||||||| |||||| ||| |||| |
0
| | | |||||||| |||| ||||||||||||||||||| ||||||||| ||
5

i =1
しかし、混合分布の場合、分布が2個以上あるので、ある観測点が
どの分布に属するかが分からない限り、分布（平均値等）を推定す
ることはできない。
10
ところで、
分布推定は「教師なし学習」

µ
1 m
∑ xi
m i =1
教師付き学習: データ <x, y>
教師なし学習: データ x
教師なし学習が必要となるところ

分布関数（確率密度関数）の推定
クラスタリング
外れ値/新規点の検出
データ圧縮
可視化
1
分布推定とクラスタリング
クラスタリング: 混合分布から生成されたデータに対し、
どの分布から生成されたかを推定する
0.15

収入
混合分布
0.10
p(x) = ∑ πj pj(x)
0.0
0.05
各クラスタは混合分布の個々の分布
に対応すると考える
| | | ||||||||||||||||||||| |||||||| || ||
-10

-5
|| ||||||||| |||||| ||| |||| |
0
| | | |||||||| |||| ||||||||||||||||||| ||||||||| ||
5
10
隠れ変数: データ点がどのガウス分布から生成されたか
すなわち, 観測データ <x>, 全データ <x, c>.
課題: <x> から <x, c> を推定する
（EM）クラスタリング例
http://jormungand.net/projects/em/
クラスタリングと分布推定

クラスタリング/密度推定
年齢
（K-means）クラスタリング例
http://www.cs.washington.edu/research/imagedatabase/demo/kmcluster/
ヒント: K-Means クラスタリング
つまり、クラスタリングができれば、

データ x → クラスタ（正規分布） j
クラスタ（正規分布） j → j の平均値・分散
という具合に分布推定ができる

しかし、分布推定ができれば、

データ x →クラスタ（正規分布） j に属する確率
クラスタ（正規分布） j に属する確率 → 確率最大のクラスタ
という具合にクラスタリングができる

ということは、鶏と卵。つまり、解けない。さて、どうする？
2
K-means の行っていること
K-means クラスタリング例

前提（「動作だけ」を記述するには不要）

初期値

繰り返し
第一回
真のデータ

（各正規分布の）分散は同じとする
クラスタ中心 oj をランダムに定め、推定を開始する
各観測点ごと、その（産みの親である）クラスタを推定する

第二回

第三回

クラスタごと、同一クラスタの点のみを用いて、その重心（平均
値）を新たにクラスタ中心とする

K-means をソフトに
前提

x の生成もとがクラスタ j (1≤j≤k)である確率を πj 、クラスタ j から生
成された場合に生成される確率を pj(x) とする。そして
p(x) = ∑ πj pj(x) とする。
まず、簡単のため、 πj =1/k とする

初期値

繰り返し

クラスタ中心 oj をランダムに定め、推定を開始する
各観測点ごと、その（産みの親である）クラスタを推定する

読み換えよう (2)

x の生成もとがクラスタ j (1≤j≤k)である確率を πj 、クラスタ j から生成さ
れた場合に生成される確率を pj(x) とする。そして
p(x) = ∑ πj pj(x) とする。
確率変数 zij =1 if データ xi∈Cj or 0 otherwise

初期値

繰り返し

各 j につき、 oi = center of { x | <x, j> }
i.e. oi = (1/Nj) ∑ x (where x∈Cj ) ⇒ oi = (1/∑P(x∈Cj)) ∑ x P(x∈Cj)
繰り返しの部分

クラスタ中心 oj をランダムに定め、推定を開始する
確率変数 zij ="1 if データ xi∈Cj or 0 otherwise"
各観測点ごと、その（産みの親である）クラスタを
推定する

E[zij]=Prob(zij=1)=(1/∑jpj(xi)) pj(xi)
各観測点ごと、その（産みの親である）クラスタを推定する

各 <x> → <x, j>, ただし j = arg min | x - oj | .
i.e. j = arg max pj(x) ⇒ Prob( x∈Cj )=Const. pj(x)=(1/∑pj(x)) pj(x)
クラスタごと、同一クラスタの点のみを用いて、その重心（平均値）を
新たにクラスタ中心とする

前提
各 j につき、 oi = center of { x | <x, j> }
読み換えよう

各 j につき、 oi = center of { x | <x, j> }
i.e. oi = (1/Nj) ∑i xi (where xi∈Cj ) = (1/N) ∑i xi P(xi∈Cj)
⇒ oi = (1/N) ∑i xi P(zij=1) = (1/∑iE[zij]) ∑i xi E[zij]

クラスタごと、同一クラスタの点のみを用いて、そ
の重心（平均値）を新たにクラスタ中心とする

oi = (1/∑iE[zij]) ∑i xi E[zij]
3
混合正規分布の学習
混合正規分布の学習
(分散は共通・既知)
(分散は共通・既知)
x1 , x2 ,… , x N ~ N ( x | µ j , σ ) with probability π j = 1 k
x1 , x2 ,… , x N ~ N ( x | µ j , σ ) with probability π j
1 if C ( xi ) = j ,
zij = 
0 otherwise.
1 if C ( xi ) = j ,
zij = 
0 otherwise.
p (C ( xi ) = j )
E[ zij ] ←
E-Step
N ( xi | µ j , σ )
=
k
∑ p(C ( x ) = j ) ∑ N ( x | µ , σ )
i
j =1
i
j =1
N
1
M-Step µ j ←
N
∑ E[ z
i =1
ij
]
∑ E[ z
i =1
1
1
e 2σ
2π σ
1
k
− 2 ( xi − µ j ) 2
1
∑ e 2σ
2π σ j =1
M-Step
µj ←
i
π j N ( xi | µ j , σ )
k
∑ E[ z
πj ←
1
N
j =1
N
1
N
i =1
混合正規分布の学習
=
∑ p(C ( x ) = j ) ∑ π
j =1
( xi − µ j ) 2
2
] xi
ij
k
j
−
=
p (C ( xi ) = j )
E[ zij ] ←
E-Step
k
ij
]
∑ E[ z
i =1
N
∑ E[ z
i =1
ij
ij
j
N ( xi | µ j , σ )
] xi
]
混合正規分布の学習
(分散は既知)
x1 , x2 ,… , x N ~ N ( x | µ j , σ j ) with probability π j
x1 , x2 ,… , x N ~ N ( x | µ j , σ j ) with probability π j
1 if C ( xi ) = j ,
zij = 
0 otherwise.
1 if C ( xi ) = j ,
zij = 
0 otherwise.
E[ zij ] ←
E-Step
p (C ( xi ) = j )
k
∑ p(C ( xi ) = j)
π j N ( xi | µ j , σ j )
=
∑ π j N ( xi | µ j , σ j )
j =1
M-Step
µj ←
∑ E[ zij ]
∑ E[ z
i =1
E[ zij ] ←
j =1
N
1
N
E-Step
k
ij
1
N
=
M-Step
] xi
µj ←
1
N
∑ E[ zij ]
∑π
j =1
N
∑ E[ z
i =1
π j N ( xi | µ j , σ j )
k
ij
j
N ( xi | µ j , σ j )
] xi
πj ←
1
N
N
∑ E[ z
i =1
ij
]
i =1
N
∑ E[ z
i =1
∑ p(C ( xi ) = j)
j =1
i =1
πj ←
p (C ( xi ) = j )
k
ij
σj ←
]
1
N
∑ E[ zij ]
N
∑ E[ z
i =1
ij
] ( xi − µ j ) 2
i =1
混合正規分布の学習
ソフト化(?) K-means
（高次元）
x1 , x2 ,… , x N ~ N ( x | µ j , Σ j ) with probability π j
1 if C ( xi ) = j ,
zij = 
0 otherwise.
E-Step
E[ zij ] ←

p (C ( xi ) = j )
k
µj ←
i
k
N
∑ E[ z
ij
i =1
]
∑ E[ z
i =1
N
1
N
∑ E[ z
j =1
N
1
i =1
σj ←
π j N ( xi | µ j , Σ j )
∑ p(C ( x ) = j ) ∑ π
j =1
M-Step
=
ij
]
∑ E[ z
i =1
ij
ij
] xi
j

E/M stepは、データの尤度を減少させない
鞍点に収束する

説明が必要ですね…

N ( xi | µ j , Σ j )
πj ←
収束する!
証明 [Neal&Hinton '99, McLachlan&Krishnan '97]:
1
N
N
∑ E[ z
i =1
ij
]
] ( xi − µ j )( xi − µ j )T
4
EM 一般的な定義

EM 一般的な定義 (続)
X={x1,…,xN} 観測データ
Z={z1,…,zN} 非観測データ
(隠れ変数)
Y=X∪Z

Q(h’ | h) = E[ln P( Y | h’ ) | h, X ]
目標: E[ ln P( Y | h ) ] を最大化する h を見出
すこと, i.e. （非観測データ含めた）データの事後
確率を最大化する h を求める
EM化 K-Means で考えてみよう

k 個の(等荷重)正規分布から生成されたデータ:
1
2πσ 2

N
X = N 個のデータ点の集合
Z = {zij}. 但し
zij=1 iff i-番目のデータは
j-番目の正規分布から生成

E-Step: Y の確率（の対数）の期待値を求める（式で表
す）. ただし, 現在の仮説 h と観測データ X は既知とする
（目標: E[ ln P( Y | h ) ] の最大化であった）
−
1
2πσ
2
e
1
2
k
∑ zij
j =1
( xi − µ j ) 2
σ2
EM化 K-Means, M-Step
1
2πσ 2
−
e
1
2
k
∑ zij
j =1
( xi − µ j ) 2
σ2
i =1
= E[∑ ln P ( yi | h' ) | h, X ]
i =1
k
( xi − µ j ') 
1
− ∑ zij
N 


2
1
σ2
e j=1
= E[∑  ln
 | h, X ]
i =1 
2πσ 2



N 

1
1 k
z ( xi − µ j ' ) 2  | h, X ]
= E[∑  ln
−
2 ∑ ij
i =1 
2πσ 2 2σ j =1

2
N 

1
1 k
= ∑  ln
− 2 ∑ E[ zij | h, X ]( xi − µ j ' ) 2 
i =1 
2πσ 2 2σ j =1

EM化 K-Means, まとめ
h ← arg max Q(h' | h)
h'
N 

1
1 k
= argmax ∑  ln
− 2 ∑ E[ zij | h, X ]( xi − µ j ' ) 2 
h'
i =1 
2πσ 2 2σ j =1

N
k
= argmin ∑∑ E[ zij | h, X ]( xi − µ j ' ) 2
h'
E[ zij ] ← η e
i =1 j =1
仮説は µ の組であった。
すなわち、h は µ の組、h′ は µ′ の組である.
最小化は µ′ による偏微分が0とおいて達成できる, i.e.,
µj ←
N
∑ E[ z
i =1
ij
| h, X ]
∑ E[ z
i =1
ij
| h, X ] xi
E[ zij | h, X ] =
−
1 ( xi − µ i ) 2
2 σ2
M-Step:
なお
N
1
E-Step:
e
k
1 ( xi − µ i ) 2
−
2 σ2
∑e
−
1 ( xi − µ n ) 2
2 σ2
µj ←
1
N
∑ E[ zij ]
N
∑ E[ z
i =1
ij
] xi
i =1
n =1
5
EM

EM
“Expectation Maximization” の略
探索アルゴリズム

隠れ変数の値がわかっていれば, 正しい最尤仮説
（ML hypothesis）を求めることができる

尤度（likelihood）の最大化
Greedy, 局所最大点につかまるかも
ある問題クラスに適用

役に立つ状況は:

正しい最尤仮説があれば, 上記の隠れ変数の事後分
布が、直ちに計算できる

“隠れ変数 hidden (latent) variables” 対応
最急降下法より遅いことも
最急降下法より速いことも

つまり、各データごと隠れ変数の値の事後分布が推定可能
大切なポイント: 隠れ変数

「鶏と卵」状況は隠れ変数のせい。
しかし、「隠れ変数」は極めて重要な概念

つまり、混合分布のパラメータが推定できる

ポピュラー. しかし有効性は問題依存
目次
EM Algorithm
K-means クラスタリング

より一般的な説明

確率密度推定

D = {xn : n = 1,
, N}
 1 if j = arg min x − µ
j
i
j
zij = 
 0 otherwise.

第二ステップ
µj =
1
∑z
i
j
i
∑z
i
K-means クラスタリング

これらを K 個のクラスタに分けるにはどうしたらよい
か？ただし、K は所与とする.
第一ステップ
2
条件付混合分布上の EM
EM Algorithm の一般形

問題: 一組の観測データが所与とする
（条件なし）混合分布上の EM
回帰と分類

K-means クラスタリング
Coordinate Descending algorithm
Coordinate descent 法
一変数ごと下記の歪み尺度 J の最小化を試
みることに相当
N
k
J = ∑∑ zij xi − µ j
2
i =1 j =1
各偏微分値を0にすればよい
j
i
xi
6
混合分布
混合分布
問題: 与えられたサンプルデータが多峰 multimodal で
あったら、その真の分布はどうやって推定したらよい
のだろうか?

分割統治 “divide-and-conquer” 法が使える
隠れ変数 Z の導入
例えば、2項分布を fit し
ようとする
多峰性を現すノード. k 個の値
のうちの一つをとる
Z
当然、アルゴリズムは収
束する。しかし、結果の分
布は真の分布とはかけ離
れたものであろう
それぞれについて, 一つの分布を割
り当てる, 分布の全体は
p( x | θ ) = ∑ p( Z j = 1 | π j ) p( x | Z j = 1,θ j )
j
= ∑ π j p( x | Z j = 1,θ j )
X
j
混合分布

混合分布

混合正規分布

隠れ変数 Z の事後確率:
τ j = p ( Z j | x, θ )
このモデルでは, 混合分布の一つ一つは正規分布
（未知パラメータあり）である
=
θ j = ( µ j , Σ j ), θ = (θ1 ,… , θ k )

=
混合正規分布の確率

l (θ | x1 ,
j
j
1
(2π ) m 2 Σ j
12
= ∑ log ∑ p( xi , Z | θ )
1
exp{− ( x − µ j )T Σ −j1 ( x − µ j )}
2
i
z
i
j
p( x | θ )
= ∑ p ( Z j = 1 | π j ) p ( x | Z j = 1, θ j )
j
= ∑ π j p ( x | Z j = 1,θ j )
j
= ∑ log ∑ π j N ( xi | µ j , Σ j )
混合分布
変数 π j に関する l の偏微分（言い忘れたが、
Lagrange乗数を用いている）
∂
∂
{l + λ (1 − ∑ j π j )} =
{∑ log ∑ π j N ( xi | µ j , Σ j )} − λ
∂π j
∂π j i
j
N ( xi | µ j , Σ j )
=∑
−λ
i ∑ j π j N ( xi | µ j , Σ j )
τj
= ∑ i −λ
i πj

, xN ) = ∑ log p( xi | θ )
i
混合分布

変数 µ j に関する l の偏微分
∂l
∂
=
{∑ log ∑ π j N ( xi | µ j , Σ j )}
∂µ j ∂µ j i
j
π j N ( xi | µ j , Σ j ) ∂
1
=∑
{− ( xi − µ j )T Σ −j1 ( xi − µ j )}
2
i ∑ j π j N ( xi | µ j , Σ j ) ∂µ j
= ∑ τ i j Σ −j1 ( xi − µ j )
i

これを 0 とおけば、次式が得られる
∑τ x
∑τ
j
µj =
i
i
i
j
i
i
7
混合分布

混合分布
変数 Σ i に関する l の偏微分
∂l
∂
=
{∑ log ∑ π j N ( xi | µ j , Σ j )}
∂Σ j ∂Σ j i
j
π j N ( xi | µ j , Σ j ) ∂
1
1
=∑
{− log Σ j − ( xi − µ j )T Σ −j1 ( xi − µ j )}
2
2
i ∑ j π j N ( xi | µ j , Σ j ) ∂Σ j
∑τ
i
j
i
( xi − µ j )( xi − µ j )T
∑τ
i
= ∑i log ∏ [π j N ( xi | µ j , Σ j )]zi
= ∑i
∑
j
lc (θ | {( xi , Z i )})
∑τ
i
i
,
( xi − µ (jt +1) )( xi − µ (jt +1) )T
∑ log p( x , Z | θ ) θ
=∑ ∑ Z
log[π N ( x | µ , Σ
θ
= ∑ ∑ τ log[π N ( x | µ , Σ )]
θ (t )
=
i
i
i
(t )
j
i
i
j
j
(t )
i
j
j
)]
j (t )
i

j
i
j
i
j
j
Graphical Model
回帰と分類用
X
∑τ
i
j (t )
∑τ
i
1
j ( t −1)
i
i
条件付混合分布
j (t )
i
j (t )
i
∑τ
1
k
この値を Z i = ( Z i ,… , Z i ) に対するベストな推定とすれば,
i
i
i
1
N
π (jt ) =
xi ,
E[( Z i j | x, θ ( t ) )] = p ( Z i j = 1 | x, θ (t ) ) = τ i j ( t )
j
∑τ i j (t ) ,
∑τ
∑τ
j (t )
i
確率変数 X と θ (t ) で条件付けた変数 Z i = ( Z i1 ,… , Z ik )
の期待値を求める
なお Z i j は２値の確率変数であり
z j log[π j N ( xi | µ j , Σ j )]
j i
前述の完全観測の対数尤度の期待値を, その偏微
分値を 0 にすることにより
1
i
完全観測の対数尤度の期待値
混合分布
Σ (jt +1) =
j (t )
i
∑τ
（ xi がクラスタ j か
ら発生した確率）
混合分布
lc (θ | {( xi , zi )}) = ∑i log p( xi , zi | θ )
µ (jt +1) =
1
∑τ
i
完全観測の対数尤度の期待値という観点から EM
アルゴリズムをみてみよう
隠れ変数 Z i = ( Z i1 ,… , Z ik )
を観測したと仮定する
データ集合 {( xi , zi )} は完全に観測されたことになり,
尤度は完全観測の対数尤度となり
1
N
π (jt ) N ( xi | µ (jt ) , Σ (jt ) )
.
∑ j π (jt ) N ( xi | µ (jt ) , Σ(jt ) )
第二ステップ
1
µ (jt +1) =
j (t )
Σ (jt +1) =
j

π (jt +1) =
τ ij (t ) =
i
混合分布

第一ステップ
∑i τ i
これを 0 とおくと次式が得られる
Σj =
EM Algorithm

1
1
= ∑τ i j {− Σ −j1 − Σ −j1 ( xi − µ j )( xi − µ j )T Σ −j1}
2
2
i

i
i
j (t )
j (t )
xi ,
( xi − µ (jt +1) )( xi − µ (jt +1) )T .
Z
Y
変数 X と Z の間の関係を判別分類的
にモデル化することができる, e.g. ソフ
トマックス softmax .
π j ( x, ξ ) = p ( Z j = 1 | x, ξ ) =
exp(ξ Tj x)
∑
j
exp(ξ Tj x)
隠れ変数 Z, 多峰性を表すもの.
k 個の値をとる
Back
8
条件付混合分布

条件付混合分布
変数 Z に関して周辺化すると,
各要素分布にはいくつかのとり方がある

p ( y | x, θ ) = ∑ p ( Z j = 1 | x, ξ ) p ( y | Z j = 1, x, θ j )

j
X は常に観測可能とする. 事後確率 τ ( x, y, θ )
は次のように定まる
j

y
j
ただし µ (θ iT x) はロジスティック関数:
π j ( x, ξ ) p ( y | Z j = 1, x,θ )
∑ j π j ( x, ξ ) p( y | Z j = 1, x,θ )
µ (θ Tj x) =
条件付混合分布

EM を用いたパラメータ推定

lc (θ | {( xi , yi , zi )}) = log ∏ p ( yi , zi | xi , θ j )
= log ∏∏ [π j ( xi , ξ ) p( yi | Z i = 1, xi , θ j )]
j
i
zij
j
j
zij log[π j ( xi , ξ ) p( yi | Z i j = 1, xi , θ j )]

期待値を最良な推定と考え
Zij
θ (t )
そうすると完全観測の対数尤度は
l (θ | {( xi , yi , zi )})
= ∑i ∑ j τ i j ( t ) log[π j ( xi , ξ ) p ( yi | Z i j = 1, xi ,θ j )]
i
∑
1
1 + exp(θ Tj x)
条件付混合
完全観測の対数尤度 :
= ∑i
ロジスティック分布
p ( y | x, θ ) = ∑ π j ( x, ξ ) µ (θ Tj x) (1 − µ (θ Tj x))1− y ,
τ j ( x, y , θ ) = p ( Z j = 1 | x, y , θ )
p ( Z j = 1 | x,θ ) p ( y | Z j = 1, x,θ )
=
∑ j p( Z j = 1 | x,θ ) p( y | Z j = 1, x,θ )
=
正規分布
p ( y | x, θ ) = ∑ π j ( x, ξ ) N ( y | β Tj x, σ 2j )
j
偏微分をとり, それらを 0 とおけば, EMの更新
公式が得られる
= p( Z i j = 1 | xi , yi , θ ( t ) )
= τ i j ( xi , yi ,θ (t ) )
条件付混合
一般公式
条件付混合モデルに対する EM algorithm のまとめ
j (t )
(E step): 事後確率 τ i
を計算する
(M step): 例えば、IRLS algorithm を用い, データ
j (t )
対 ( xi ,τ i ) の元で, パラメータ ξ を更新する.
(M step): 荷重付き IRLS algorithm を用い, データ
j (t )
点 ( xi , yi ) と荷重 τ i のもとで, パラメータ θ j
を更新する
IRLS: iterative reweighted least square

X - 全観測可能変数
Z - 全隠れ変数
完全観測の対数尤度
θ - 全パラメータ
仮に Z が観測されたとき, その ML 推定量は
θ = arg maxθ lc (θ ; x, z ) = arg maxθ log p( x, z | θ )
しかしながら, Z は実際には観測されないので
l (θ ; x) = log p( x | θ ) = log ∑ p( x, z | θ )
z
不完全観測の対数尤度
9
一般公式
一般公式
仮に p ( x, z | θ ) が積に分解できたとすると, 完
全観測の対数尤度は

q ( z | x) を f ( z | x, θ z ) の推定量とすれば, 完全観測
の対数尤度は完全観測の対数尤度の期待値とな
り

lc (θ ; x, z ) = ∑ f ( z | x, θ z ) log p( x, z | θ )
lc (θ ; x, z )
z
ここで f ( z | x,θ z ) は未知であるので, この ML
推定量の求め方は不明である. しかしながら,
もし f ( z | x,θ z ) の確率変数の上で平均化すれ
ば

q
= ∑ q( z | x) log p ( x, z | θ )
z
この完全観測の対数尤度の期待値はとけて, 期待
としては, それが完全観測の対数尤度をなぜか改
善する. (EM の基本的アイデア.)

q ( z | x ) = ∑ f ( z | x, θ z )
θz
一般公式

一般公式

前記において, EMの各ステップで, L(q, θ ) を最大
化した
しかしながら, 最後に最大化した L(q, θ ) が同時
に不完全観測対数尤度 l (θ ; x ) をも最大化する
と, どうして分かるのか?
= log p ( x | θ (t ) )
= l (θ (t ) ; x)
注: L( q, θ
(t )
) は l (θ (t ) ; x) の上界となる
10
一般公式

一般公式
l (θ ; x) と L(q,θ )との差は

p ( x, z | θ )
q( z | x)
p ( x, z | θ )
= ∑ q ( z | x ) log p ( x | θ ) −∑ p ( z | x) log
q( z | x)
z
z
q( z | x)
= ∑ q ( z | x) log p ( x | θ ) + log
p ( z | x, θ ) p ( x | θ )
z
q ( z | x)
= ∑ q ( z | x) log
= D( q( z | x) || p ( z | x, θ ) )
p ( z | x, θ )
z
l (θ ; x) − L(q,θ ) = l (θ ; x ) − ∑ q( z | x ) log
z
非負でありq ( z | x) = p ( z | x,θ )
でユニークに最小化する
EM と交互最小化について
尤度の最大化はモデルと経験分布との間の
KL divergence を最小化することと同値であっ
た.
隠れ変数 Z を含めることにより、 KL
divergence は ( x, z ) の結合分布（それぞれ
の）間の完全観測の KL divergence となる
KL divergence
一般公式
一般公式
D( ~
p ( x) || p( x | θ ) ) = −∑ ~
p ( x) log p ( x | θ ) + ∑ ~
p ( x) log ~
p ( x)
x
≤ −∑ ~
p ( x) L ( q, θ ) + ∑ ~
p ( x) log ~
p ( x)
x
x

EM algorithm の再定式化
(E step)
D( q( z | x) || p( z | x,θ ) )
q (t +1) ( z | x) = arg min D(q || θ (t ) )
x
p ( x, z | θ )
= −∑ ~
p ( x)∑ q ( z | x) log
+∑~
p ( x) log ~
p ( x)
q ( z | x)
x
z
x
~
p ( x)q( z | x)
=∑~
p ( x)∑ q( z | x) log
p ( x, z | θ )
x
z
= D( ~
p ( x) q( z | x) || p( x, z | θ ) )
q (t +1) ( z | x) = p( z | x,θ (t ) )
q

(M step)
θ (t +1) = arg min D(q (t +1) || θ )
交互最小化
θ
まとめ（一般的な説明）

（条件なし）混合分布

条件付混合分布

Graphic model
EM algorithm
Graphic model
EM algorithm
EM algorithm の一般的な表現

補助関数の最大化
完全観測のKL divergence の最小化
11

情報意味論（7） EM より複雑なモデル 例: 混合正規分布

Comments

Description

Transcript

情報意味論（7） EM より複雑なモデル例: 混合正規分布