スライド 1

論理生命学第7回：
潜在変数モデルとEMアルゴリズム
渡辺一帆
内容
潜在変数モデルとは
例）混合正規分布
隠れマルコフモデル
EM（Expectation Maximization）法
潜在変数モデルの最尤推定のためのアルゴリ
ズム
講義資料：http://hawaii.naist.jp/~wkazuho/index-j.html
混合正規分布（１）
Gaussian Mixture Model （GMM）
x  RM
K
p ( x | w )   ak g ( x |  k )
k 1
コンポーネント：
g ( x | k ) 
 || x  k ||2 

exp 
M
2


2
M次元正規分布
1
K
混合比: ak  0,  ak  1
k 1
a  (a1 , a2 ,...,aK ) は確率ベクトル
K

M
パラメータ: w  ak , k | ak  0,  ak  1, k  R 
k 1


x
x ( 2)
(1)
.
. .
. . ..
. .. .
..
.
. . . . ...
.
. ..
..
x ( 2)
x (1)
応用）クラスタリング, 密度推定
混合正規分布（２）
潜在変数（隠れ変数、不観測変数）
y  ( y (1) ,..., y ( K ) ) {( 1, 0, ..., 0), ...,(0, 0,...,1)}
K
p( x, y | w)   ak g ( x | k )
y
(k )
どれか一つの要素のみが 1.
k 1
K
p ( y | a)   a
y  ( 1, 0, 0)
y( k )
k
k 1
K
p( x | μ, y)   g ( x | k )
y  ( 0, 1, 0)
y( k )
k 1
K
p( x | w)   p( x, y | w)  ak g ( x | k )
k 1
y
周辺化
y  ( 0, 0, 1)
隠れマルコフモデル（１）
x  {x1, x2 ,...,xn }
xt  ( x ,..., x
(1)
t
a12
データ系列
(M )
t
1
)
{( 1, 0, ..., 0), ...,(0, 0,...,1)}
aij
：状態遷移確率
状態iから状態jへ遷移する確率
K
a
j 1
ij
1
bim ：出力確率
状態iにおいてmを出力する確率
M
b
m 1
im
1
a22
a11
Hidden Markov Model (HMM)
a13
応用）文字列、時系列のモデリング
B  bim 
K M
a31
3
A  aij 
KK
2
隠れマルコフモデル（２）
yt  ( yt(1) ,..., yt( K ) )
{( 1, 0, ..., 0), ...,(0, 0,...,1)}
K
K
1
2
p( yt | yt 1 , A)   a
j 1 i 1
K M
yt( j ) yt(i1)
ij
p( xt | yt , B)   b
yt( i ) xt( m )
im
i 1 m 1
簡単のため y1
 ( 1, 0, ..., 0)
3
w  ( A, B)
（状態１からスタート）
n
n
t 2
t 1
p(x, y | w)   p( yt | yt 1 , A) p( xt | yt , B)
周辺化
p(x | w)  ... p(x, y | w)
y2
yn
HMMの尤度
演習
混合二項分布（ x{0, 1, 2,...,N} N は既知）
N x
N x
N x
p( x | w)  a  p1 (1  p1 )
 (1  a)  p2 (1  p2 ) N  x
x
x
w  {a, p1, p2 ; 0  a  1, 0  p1  1, 0  p2  1} について
(1)
( 2)
（１）潜在変数を y  ( y , y ) {(1,0), (0,1)}として p( x, y | w )を表せ
（２）ベイズの定理
p ( y | x, w ) 
p ( x, y | w )
 p ( x, y | w )
y
により p( y | x, w )を表せ
最尤推定
学習データ:
尤度関数:
x  {x1 ,...,xn }
潜在変数:
混合分布の場合：各
p(x | w )
n
xi
は独立と仮定
n
p(x | w)   p( xi | w)   p( xi , yi | w)
i 1
最尤推定量:
y  { y1 ,..., yn }
i 1 yi
ˆ ML  arg max log p(x | w)
w
w
潜在変数モデルでは
log p(x | w)  log  p(x, y | w)
y
EM（Expectation Maximization）法:
潜在変数モデルの最尤推定のための（効率的な）アルゴリズム
EMアルゴリズム
 Q関数
~ )  p(y | x, w
~ ) logp(x, y | w)
Q(w; w

y
とする
（密度関数ではない）
EMアルゴリズム
1.
~
w
に適当な初期値を与える
2. Eステップ：
を計算
3.
~)
Q(w; w
~
Mステップ： Q(w; w )
を最大にする
4.
ˆ の対数尤度を計算し、収束しているか判定する
w
~
収束していなければ、w
ˆ
w
w を wˆ
として2.に戻る
とする
準備：カルバック情報量
 ２つの確率分布p(x) と q(x) の間の擬距離
p ( x)
K ( p || q)   p( x) log
q( x)
x
  p( x) log
p ( x)
dx
q ( x)
xが離散のとき
xが連続のとき
K ( p || q)  0 等号は p( x)  q( x) のときのみ

∵ K ( p || q)  
t
q( x)
として
p( x)


p ( x) q ( x)
p( x)log

 1dx y
q ( x)
p ( x)


log t  t  1 より
y  t 1
y  logt
t 1
（等号成立はt=1）
☆注意データx上の確率分布間以外にも潜在変数y上やパラメータw上
の確率分布間の距離を測る場合もあります
t
EMアルゴリズム（２）
 EM法で尤度が増加する理由
（言いたいこと L(w
ˆ )  0）
~)
L(w)  log  p(x, y | w)  log  p(x, y | w
y
y
 p(x, y | w )
 log
~)
 p(x, y | w
y
y
 log
p(x, y | w ) / p(y | x, w )
~ ) / p(y | x, w
~)
p(x, y | w
（∵ベイズの定理）
~)
p(x, y | w)
p(y | x, w
 log
 log
~
p(x, y | w)
p(y | x, w)
~ ) で期待値をとると
両辺を p(y | x, w
EMアルゴリズム（３）
 EM法で尤度が増加する理由（続き）
~)
p(x, y | w)
p(y | x, w
~
~
  p(y | x, w) log
L(w )   p(y | x, w) log
~
p(x, y | w) y
p(y | x, w)
y
潜在変数の分布に関す
るカルバック情報量
~ )  Q(w
~; w
~ )  K ( p(y | x, w
~ ) || p(y | x, w))
 Q(w; w
~ )  Q(w
~;w
~)
 Q(w; w
（∵カルバック情報量は非負）
~)
ˆ  arg maxQ(w; w
ww
w
ととれば、 L(w
ˆ)0
（尤度が必ず増加）
混合正規分布の場合


 a

p(x, y | w)    k M g ( xi | k )

i 1 k 1 
 2

n
完全尤度:
潜在変数の事後分布
K
yi( k )
|| xi   k ||2
g ( xi |  k )  exp{
}
2
各データは独立
p(x, y | w) n
p(y | x, w) 
  p( yi | xi , w)
p(x | w )
i 1
K
p( yi | xi , w) 
p( xi , yi | w) 
 p( xi , yi | w)
y
 ak g ( xi | k )
k 1
K
 a g(x |  )
yi
p( yi( k )  1 | xi , w ) 
(k )
i
l 1
l
i
l
ak g ( xi |  k )
K
 a g(x |  )
l 1
l
i
l
(＊)
混合正規分布の場合
~) 
~ ) logp(x, y | w)
Q関数 Q(w; w
 p(y | x, w
y
n
K
~)
  p(y | x, w
 yi(k ) logak g ( xi | k )
i 1 k 1
y
n
K
~ ) loga g ( x |  ) 
  p( yi( k )  1 | xi , w
k
i
k
i 1 k 1
n
nk   p( y
i 1
(k )
i
~)
 1 | xi , w
コンポーネントkからのデータ数
1
k 
nk
n
(k )
p
(
y
 i  1 | xi , w~ )xi
とすると
i 1
コンポーネントkからのデータの平均
K

||  k ||2 
~
Q(w; w )   nk log ak  k  k 
 +(wに依存しない項)
2 
k 1

ˆ k   k
EM法：
(†)
nk
aˆ k 
(＊)と(†)を繰り返す
n
応用例）混合正規分布 (アルゴリズム)
* k
初期化
~
□：data（n
 50 ）
~ )  0.76
p( yi(1)  1 | xi , w
Eステップ
~  0.49
a
1
**
~* * 0.51
a
2
~ )  0.77
p( yi(2)  1 | xi , w
Mステップ
終了
*
* aˆ1  0.40
*
aˆ2  0.60
繰り返す
*
aˆ1  0.49
aˆ2  0.51
まとめ
潜在変数モデルの実例
混合正規分布
隠れマルコフモデル
潜在変数モデルの最尤推定法のための
EMアルゴリズム
演習（つづき）
混合二項分布（ x{0, 1, 2,...,N} N は既知）
N x
N x
N x
p( x | w)  a  p1 (1  p1 )
 (1  a)  p2 (1  p2 ) N  x
x
x
w  {a, p1, p2 ; 0  a  1, 0  p1  1, 0  p2  1} について
(1)
( 2)
（１）潜在変数を y  ( y , y ) {(1,0), (0,1)}として p( x, y | w )を表せ
（２）ベイズの定理
p ( y | x, w ) 
p ( x, y | w )
 p ( x, y | w )
により p( y | x, w ) を表せ
y
（３）n個のデータ x  {x1 ,..., xn }が与えられたときの
~ ) を計算せよ（ nk ,  k を用いて表せ）
Q関数 Q(w; w
（４）EM法による尤度最大化のためのアルゴリズムを導け
ヒント
Qの最大化
~) 
~ ) logp(x, y | w)
Q(w; w
 p(y | x, w
y

||  k ||2 
  nk log ak  k  k 
 +(wに依存しない項)
2
k 1


K
K
nk
nk / n
log
はカルバック情報量なので非負

ak
k 1 n
K
K
nk
nk / n
nk
nk 1 K
log

log
  nk log ak  0

n
a
n
n
n k 1
k 1
k 1
k
K
K
nk
nk
n
log
a

n
log
a



k
k
k
（等号成立は k
のとき）
n
k 1
k 1
n
||  k ||2
||  k ||2 ||  k ||2
2
 k k 
  ||  k  k || 

2
2
2
（等号成立は k   k のとき）

Download Report