パワーポイント2007(推奨)

数理言語情報論第9回
2007年12月3日
数理言語情報学研究室講師二宮崇
1
今日の講義の予定



EMアルゴリズム
内側外側アルゴリズム(inside outside
algorithm)
教科書



北研二(著) 辻井潤一(編) 言語と計算4 確率的言語モ
デル東大出版会
C. D. Manning & Hinrich Schütze
“FOUNDATIONS OF STATISTICAL NATURAL
LANGUAGE PROCESSING” MIT Press, 1999
Christopher M. Bishop “PATTERN
RECOGNITION AND MACHINE LEARNING”
Springer, 2006
2
PCFG
CFGの書換規則の適
用確率をパラメータ
化した文法
 構文木の確率は、適
用された書換規則の
パラメータの積
 各パラメータは
0.0≦θ≦1.0

簡単なCFGの例
パラメータ
S → SUBJ VP1
θS → SUBJ
VP1
S → SUBJ V
θS → SUBJ
V
SUBJ → NP が
θSUBJ → NP
VP1 → OBJ1 V
θVP1 → OBJ1
OBJ1 → NP を
θOBJ1 → NP を
NP → S NP
θNP → S
V → 送った
θV → 送った
V → 読んだ
θV → 読んだ
NP → 香織
θNP → 香織
NP → 恵
θNP → 恵
NP → 電子メール
θNP → 電子メール
NP → プレゼント
θNP → プレゼント
NP → 香織 NP1
θNP → 香織 NP1
NP → 恵 NP1
θNP → 恵
NP1 → と NP
θNP1 → と
が
V
NP
NP1
NP
3
構文木の確率
文 s = “香織が恵が送った電子メールを読んだ”
S
構文木 t
VP1
SUBJ
簡単なCFGの例
パラメータ
S → SUBJ VP1
θS → SUBJ
VP1
S → SUBJ V
θS → SUBJ
V
SUBJ → NP が
θSUBJ → NP
VP1 → OBJ1 V
θVP1 → OBJ1
OBJ1 → NP を
θOBJ1 → NP を
NP → S NP
θNP → S
V → 送った
θV → 送った
V → 読んだ
θV → 読んだ
NP → 香織
θNP → 香織
NP → 恵
θNP → 恵
NP → 電子メール
θNP → 電子メール
NP → プレゼント
θNP → プレゼント
NP → 香織 NP1
θNP → 香織 NP1
NP → 恵 NP1
θNP → 恵
NP1 → と NP
θNP1 → と
NP
香織
が
OBJ1
が
NP
V
S
SUBJ
NP
NP
が
V
を
読んだ
NP
V
電子メール
送った
恵
P(t) = θS → SUBJ VP1 × θSUBJ → NP が × θNP → 香織 ×
θVP1 → OBJ1 V × θOBJ1 → NP を × θNP → S NP ×
θS → SUBJ V × θSUBJ → NP が × θNP → 恵×
θV → 送った× θNP → 電子メール × θV → 読んだ
NP1
4
NP
PCFG

パラメータ推定 (estimation)

単純な数え上げ (教師付学習)
 C( A   ;t)
 
  C ( A   ; t )
tTreebank
A
tTreebank

最尤法 (教師無学習)
~
  arg max


 
C ( r ;t )

r
ただし
sText tT ( s ) rP
デコーディング (decoding)
~
t  arg max p(t )
tT ( s )



A
 1.0
C(r;t): 書換規則rが構文
木t中に出現する回数
T(s): 文sに対して、フル
パージングで得られる全
構文木集合
今回の内容は

EMアルゴリズム (expectationmaximization algorithm)

不完全データ（欠損や曖昧性のあるデータ）
に対する有名な学習法
 PCFGの教師無学習
 削除補間法(deleted

interporation)のパラメータ推定
内側・外側アルゴリズム(inside-outside
algorithm)

畳みこまれた構文木集合に対して効率的にEM
アルゴリズムを実行する手法
6
PCFGのEMアルゴリズム
1.
2.
θ(0) := 適当な値
[Eステップ] θ(i)を用いて各構文木の確率を計
算。文sに対する各構文木の相対確率を計算。
p (t )   ( r ) C ( r ;t )
(i )
p(t | s) 
rP
3.
[Mステップ] θ(i+1)を求める
 A(i1) 
p(t )
 p(u)
uT ( s )
  p(t | s)C ( A   ; s, t )
   p(t | s)C ( A   ; s, t )
sText tT ( s )
sText tT ( s )
4.
2.に戻る
7
PCFGのEMアルゴリズム

[Eステップ]各構文木の文sに対する確率



仮のパラメータθ(i)を用いてフルパーズした結果の各々の構文木の確率を計算。
文sに対するそれぞれの構文木の相対確率p(t|s)を計算
[Mステップ]パラメータ更新


書換規則の適用回数の期待値を計算
単純な数え上げと同じ方法でパラメータを求める
s1
parse
p(t|s1)=p(t)/Z1 =
s2
0.1
0.3
0.6
Zi 
parse
p(t|s2)=p(t)/Z 2=
s3
C’(r;t) = 0.6×C(r; t)
1.0
 p(t )
tT ( si )
parse
p(t|s3)=p(t)/Z3 =
0.21
0.16
0.51
0.05
0.07
...
...
...
8
補間法でのEMアルゴリズム

1.
2.
3.
4.
トライグラム補間のEMアルゴリズム
データを訓練データDtとヘルドアウトデータDh（と評価データ）に分割
訓練データで p(wn;Dt), p(wn|wn-1;Dt), p(wn|wn-1,wn-2;Dt)を頻度から計算。
λ(0)←適当な値
[Eステップ] 各パラメータの貢献度を計算
1(i ) p( wn | wn 1 , wn  2 ; Dt )
 n,1  (i )
1 p( wn | wn 1 , wn 2 ; Dt )  (2i ) p( wn | wn 1 ; Dt )  (3i ) p( wn ; Dt )
 n, 2
(2i ) p( wn | wn 1 ; Dt )
 (i )
1 p( wn | wn 1 , wn  2 ; Dt )  (2i ) p( wn | wn 1 ; Dt )  (3i ) p( wn ; Dt )
(3i ) p( wn ; Dt )
 n ,3  ( i )
1 p( wn | wn 1 , wn  2 ; Dt )  (2i ) p( wn | wn 1 ; Dt )  (3i ) p( wn ; Dt )
5.
[Mステップ] パラメータ更新

( i 1)
1
5.
1 |Dh |
1 |Dh |
1 |Dh |
( i 1)
( i 1)

 n,1 , 2 
 n, 2 , 3 
 n ,3



| Dh | n 1
| Dh | n 1
| Dh | n1
4.に戻る
9
EMアルゴリズムの疑問
問題によってパラメータの更新式が違うけ
ど、この更新式はどうやって出てきたの？
 この更新式が正しい保証は？

10
EMアルゴリズムの全体像
~
  arg max l ( )

問題変形
[Eステップ] p(y | x ; θ)
を計算
 (i 1)  arg max Q( ( i ) , )

個々の問題に応じ
て決まるQ関数の
極値を解析的に求
める
[Mステップ]
 (i 1)  arg max Q( ( i ) ,  )

によりパラメータ更新
個々の問題によって決
まるパラメータ更新式
11
問題設定


実際に観測されたデータx1,...,xNが存在
それぞれのデータは隠れ状態y1,...,yMのいずれかから
生成されたと仮定


隠れ状態の集合はデータ毎に変わっても良い
パラメータ集合θによりp(x, y)が計算される
x1
y1
y2
y3
p(x1, y1) p(x1, y2) p(x1, y3)
x2
y4
p(x2, y4)
x3
y5
y6
y7
y8
y9
p(x3, y5) p(x3, y6) p(x3, y7) p(x3, y8) p(x3, y9)
..
..
..
12
Q関数の導出 (1)

問題: 実際に観測されたデータx1,...,xNが存在して、それに
対して、対数尤度を最大化するパラメータを求める
N
~
  arg max l ( )  arg max  log p( xi ; )



i 1
問題チェンジ: パラメータをθからθ’にした時の対数尤度
の差を最大化することを繰り返せば極大値が求まる
N
arg max  log p ( xi ; )  log p ( xi ; )

i 1
argmaxを求めているが、ようは正の値になればより尤度の高いパラ
メータが得られることに注意
13
Q関数の導出 (2)

個々の事象の対数尤度の差
log p( xi ; )  log p ( xi ; )  log
p( xi ; )
p ( xi ; )
p( xi ; )
p( xi ; )
y
 p( xi , y; ) p( y | xi ; ) 
  p( y | xi ; ) log 

y
 p( xi , y; ) p( y | xi ; ) 
p( xi , y; )
p( y | xi ; )
  p( y | xi ; ) log
  p( y | xi ; ) log
p( xi , y; )
p( y | xi ; )
y
y
  p( y | xi ; ) log
ジェンセンの不等式より、常に≧0
14
Q関数の導出 (3)

個々の事象の対数尤度の差
p ( xi , y; )
p ( y | xi ; )
  p ( y | xi ; ) log
p ( xi , y; )
p ( y | xi ; )
y
y
p ( xi , y; )
  p ( y | xi ; ) log
p ( xi , y; )
y
  p ( y | xi ; ) log p ( xi , y; )   p ( y | xi ; ) log p ( xi , y; )
log p ( xi ; )  log p ( xi ; )   p ( y | xi ; ) log
y
y
ここをQ関数とみなす
Q( ,  )   p( y | xi ; ) log p( xi , y; )
y
すると、ここは、
Q( ,  )
15
Q関数の導出 (4)

まとめ

対数尤度の差は次のようにおける
log p( xi ; )  log p( xi ; )  Q( , ' )  Q( , )
ただし Q( ,  ) 
 p( y | x ; ) log p( x , y; )
i
i
y

より良いパラメータθ’を見つけるためには、




Q(θ, θ’)-Q(θ, θ)≧0となれば良いが、
効率を考えると、対数尤度の差が最大になるほうが良い
Q(θ, θ)はθ’に関わりなく一定なので、対数尤度の最大化するには、
Q(θ, θ’)を最大化すれば良い
θ’ = θとおくと(古いパラメータと同じにすると)Q関数の差は0にな
る⇒argmaxをとれば、常にQ(θ, θ’)-Q(θ, θ) ≧0
16
EMアルゴリズム: Q関数の最大
化

次のパラメータ更新を繰り返すアルゴリズ
ム
 (i 1)  arg max Q( ( i ) , )

ただし、 Q( ,  ) 
 p( y | x ; ) log p( x , y; )
i
i
y
全ての観測データx1, x2, ..., xnに対しては、
N
Q( , )   p( y | xi ; ) log p( xi , y; )
i 1
y
とすればよい
しかし、まだ問題は解けていない！
argmax Qをどうやって求めるか？？
17
休憩: Q関数の直感的な意味 (1)

Q関数 Q( , )   p( y | xi ; ) log p( xi , y; )
y

(古いパラメータθで計算した隠れ状態の相対確
率)× (新しいパラメータθ’によるxiとyの同時確
率の対数)
p( y1 | xi ; )
y1
log p( xi , y1 ; )
xi
p( y2 | xi ; )
y2
log p( xi , y2 ; )
p( y3 | xi ; )
...
y3
log p( xi , y3 ; )
18
休憩: Q関数の直感的な意味 (2)

そもそもなぜ直接θを最大化しないのか？
N
l ( )  log  p ( xi , y; )
i 1
y
N
  log  p ( xi , y; )
i 1
 ????
y
logの中に和があると、微分するのが難しい…
⇒パラメータ更新式にすれば、実はこのsumをlogの外
にだすことができるのであった
19
休憩: ジェンセンの不等式
ジェンセンの不等式
 凸関数 f(x) は区間 I 上の実数値関数
 p1,p2,...,pnはp1+p2+...+pn=1を満たす実数
 任意のx1,x2,...,xn∈ I に対し次の不等式が成
り立つ
p1 f ( x1 )  p2 f ( x2 )    pn f ( xn )  f ( p1 x1  p2 x2    pn xn )

f(x)=－log(x)、xi=qi /piとおくと

pi
qi 
i pi log q   log  i pi p    log i qi  0
i
i 

20
EMアルゴリズムの全体像
~
  arg max l ( )

問題変形
[Eステップ] p(y | x ; θ)
を計算
 (i 1)  arg max Q( ( i ) , )

個々の問題に応じ
て決まるQ関数の
極値を解析的に求
める
[Mステップ]
 (i 1)  arg max Q( ( i ) ,  )

によりパラメータ更新
個々の問題によって決
まるパラメータ更新式
21
例: 混合モデルのパラメータ更新
式導出

混合モデル (mixture model)
観測データx1,..,xNに対し、それらを生成する複
数の隠れ状態y1,...,yMを仮定
 いずれかの隠れ状態がλj (=p(yj) )の確率で選択
され、その隠れ状態から観測データxがp(x | yj)
の確率で生成されたと考える

M
p( x)    j p( x | y j )　ただし　j 1
M

j 1
j
1
22
例: 混合モデルのパラメータ更新
式導出

混合モデル (mixture model)
M
p( x)    j p( x | y j )　ただし　j 1

M

j 1
j
1
Q関数
N
M
Q( ,  )   p( y j | xi ;  ) log p( xi , y j ;  )
i 1 j 1
23
例: 混合モデルのパラメータ更新
式導出

Q関数を最大化するλ’を見つける⇒ラグラ
ンジュの未定乗数法
(i 1)  arg max Q((i ) ,  )

N
M
Q( ,  )   p( y j | xi ;  ) log p( xi , y j ;  )
i 1 j 1
24
ラグランジュの未定乗数法

ラグランジュの未定乗数法
arg max f (θ)ただし g1 (θ)  0,..., g m (θ)  0
θ

L(θ)  f (θ)  1 g1 (θ)  ...  m g m (θ)
L
L
L
 0,
 0,...,
0
1
 2
 n

ラグランジュ関数
M

L( ,  )  Q( ,  )      j  1
 j 1

25
例: 混合モデルのパラメータ更新
式導出

ラグランジュ関数を偏微分
M

L( ,  )  Q( ,  )      j  1
 j 1

L( ,  )
 j
を解いてみよう！
26
例: 混合モデルのパラメータ更新
式導出

ラグランジュ関数を偏微分
L( ,  )
 j
 p( y j | xi ;  )
 log p( xi , y j ;  ) 

log p( xi , y j ;  )  p( y j | xi ;  )
  



 j
 j

i 1 j 1 

N M 
 log p( xi , y j ;  ) 

   p( y j | xi ;  )


 j

i 1 j 1 

N
M

p( xi , y j ;  ) 
1
   p( y j | xi ;  )



 j
p( xi , y j ;  )

i 1 j 1 

N
1
p( xi | y j ;  )  
  p( y j | xi ;  )
 j p( xi | y j ;  )
i 1
N
1
  p( y j | xi ;  )    0
 j
i 1
N
M
27
例: 混合モデルのパラメータ更新
式導出
 j 
1
p( y


i 1
M

j 1
N
j
j
| xi ;  )
 1であるから
N
M
1
p( y


j 1 i 1
p ( y j | xi ) 
p ( xi , y j )
p ( xi )

j
p ( xi , y j )
M

j 1
j
N
1  1より


| xi ;  ) 
 N
i 1
 j p ( xi | y j )
M
 p( x , y )  
i
1
j 1
j
p ( xi | y j )
したがって
1
 j 
N
N

i 1
 j p ( xi | y j )
M

j 1
j
p ( xi | y j )
28
PCFGのパラメータ更新式導出

PCFGのQ関数
N
Q( ,  )  
 p(t | s ; ) log p(s , t; )
i 1 tT ( si )
N
i
i

C ( r ;t ) 
    p(t | si ; ) log   r

i 1 tT ( si ) 
rP

N



    p(t | si ; ) C (r ; t ) log  r 
i 1 tT ( si ) 
rP

29
PCFGのパラメータ更新式導出

PCFGのQ関数


Q( ,  )     p(t | si ; ) C (r ; t ) log  r 
i 1 tT ( si ) 
rP

N

ラグランジュ関数
L( ,  )  Q( , ) 

AVN
A
(1  A )

30
PCFGのパラメータ更新式導出

ラグランジュ関数をパラメータで偏微分
L( ,  )
 A 
 p(t | si ; )
 log  r 
  
C (r; t ) log  r  p(t | si ; ) C (r ; t )
  A

 A  
i 1 tT ( si ) 
rP
  A  rP
N

 log  r 
    p(t | si ; ) C (r ; t )
  A
 A  
i 1 tT ( si ) 
rP

N

1 
    p(t | si ; )C ( A   ; t )
  A  0

 A 
i 1 tT ( si ) 

N
31
PCFGのパラメータ更新式導出

パラメータ更新式
 A  
1 N

p (t | si ; )C ( A β; t )


  i 1 tT ( si )
  
 1であるから、
A 
N
  

 p(t | si ; )C ( A β; t )
i 1 tT ( si ) 
よって
書換規則の適
用回数の期待
値になってい
ることに注意
N
 A   
  p(t | s ; )C ( A β; t )
i 1 tT ( si )
i
N
   p(t | s ; )C ( A β; t )
i 1 tT ( si )
i
32
PCFGに対するEMアルゴリズム
の問題点

s
構文木が多すぎて現実的な時間で各構文木
の相対確率を計算できない！(文長に対し
て指数爆発的に増加。簡単に数百億ぐらい
になる。)
parse
...
p(t)/Z =
0.21
0.06
0.001
0.05
0.07
数百億続く！
33
内側外側アルゴリズム

アイデア
CKYアルゴリズムでフルパーズした後のCKY
テーブルから構文木を展開することなく各書
換規則の適用回数の期待値が計算できればよ
い
 バイナリールールを仮定し、内側確率と外側
確率を動的計画法で効率的に計算
 内側確率と外側確率から書換規則の適用回数
の期待値が計算

34
内側確率

内側確率 β(i,j,A)

非終端記号Aから単語列wi+1,...,wjを導出する確
率(=単語列wi+1,...,wjを構文解析してルート(根)
がAとなる構文木集合の確率の和)
A
w1,...,wi wi+1, ..................,wj wj+1,...,wn
35
内側確率の計算

Si,jをビタビアルゴリズムと同様に計算

ただし、ファクタリングの際にmaxをとっていたのをsumに
する
Si,j: <X, p>の集合 (X: 非終端記号, p: 部分木の確率)
 Si,jの求め方
sumをmaxにする
for k = i+1 to j-1
とビタビアルゴリ
forall <B, pX>∈ Si,k
ズムになる
forall <C, pY>∈ Sk,j
forall A ∈ G(B, C)
if( <A, p> exists in Si,j )
p := p + pX×pY×θZ→X Y
else
Si,j := Si,j ∪ <A, pX×pY×θZ→X Y>

36
外側確率

外側確率α(i,j,B)

S(開始記号)からw1...wiBwj+1...wnを導出する確
率
S
B
w1,...,wi wi+1, ..................,wj wj+1,...,wn
37
外側確率計算のアイデア

バイナリールールなので、次の2通りとAC
の組み合わせからα(i,j,B)が計算できる
A→B C: Aの外側確率×Cの内側確率×θA→B
 A→C B :Aの外側確率×Cの内側確率×θA→C

S
S
A
B
w1..wi
C
B
A
C
wi+1 ..wj wj+1 ..wk wk+1..wn
C
w1..wk wk+1 ..wi
B
wi+1 ..wj wj+1..wn
外側確率の計算

α(i,j,B)の計算
 (i, j, B) 

n
A BC
A ,C

A ,C
ACB
 (i, k , A) ( j, k , C ) 
k  j 1
0
 (k , j, A) (k , i, C )
k i 1
39
外側確率の計算

α(i,j,X)の計算の順番
S0,6
スタート
S0,5
S0,4
S0,3
S0,2
S0,1
0
w1
S1,5
S1,4
S1,3
S1,2
1
w2
S1,6
S2,5
S2,4
S2,3
2
S2,6
w3
S3,6
S3,5
S3,4
3
w4
S4,6
S4,5
4
w5
S5,6
5
w6
6
40
外側確率計算アルゴリズム
フルパージングと内側確率計算後を仮定
for all 0 ≦i < j ≦n, X∈VN
Ai,j → Bi,k Ck,j in Si,jはフル
パージングの際にSi,j中の
α(i,j,X) := 0
非終端記号Aを生成するに
α(0,n,S) := 1.0
到った履歴
for l = n – 1 to 1
・書換規則がA→B C
・BはSi,kの中の要素
for i = 0 to n － l
・CはSk,jの中の要素
j := i + l
forall Ai,j → Bi,k Ck,j in Si,j
α(i, k, B):=α(i, k, B)+α(i,j,A)×β(k,j,C)×θA→ B C
α(k, j, C):=α(k, j, C)+α(i,j,A)×β(i,k,B)×θA→B C
41
書換規則の適用回数の期待値
内側確率と外側確率を使って書換規則の適
用回数の期待値を計算
 Ai,j→Bi,k Ck,jの適用回数の期待値= Ai,j→Bi,k
Ck,j の出現した構文木の確率の和

s
Ai,j
Ai,j
Ai,j
Bi,k Ck,j
Bi,k Ck,j
Bi,k Ck,j
parse
p(t)/Z =
0.21
0.16
...
0.07
42
書換規則の適用回数の期待値

Ai,j→Bi,k Ck,jの適用回数の期待値
=1/Z×(Ai,j→Bi,k Ck,j の出現した構文木の確率の和)
=1/Z×(Bi,kの内側確率×Ck,jの内側確率×θA→B C×Ai,jの外側確率)
S
A
B
w1..wi
C
wi+1 ..wk wk+1 ..wj wj+1..wn
43
書換規則の適用回数の期待値
1
p ( Ai , j  Bi ,k Ck , j | s ) 
 A BC (i, j , A)  (i, k , B)  (k , j , C )
p( s)
j 1
n 1 n
1
C ( A  BC ; s ) 
 A BC     (i, j , A)  (i, k , B)  (k , j , C )
p( s)
i  0 j i  2 k i 1
p ( s )   (0, n, S )
44
内側外側アルゴリズム
1.
2.
3.
θ(0) := 適当な値
[Eステップ] θ(i)を用いて内側確率と外側確率を計算。
[Mステップ] 書換規則の適用回数の期待値を計算。
θ(i+1)を求める
j 1
n 1 n
1
C ' ( A  BC ; s) 
 A BC     (i, j, A)  (i, k , B)  (k , j, C )
 (0, n, S )
i  0 j i  2 k i 1
)
 A(i1BC

 C( A  BC ; s)
  C( A  BC ; s)
sText
sText B ,C
4.
2.に戻る
45
まとめ
EMアルゴリズム
 内側外側アルゴリズム
 次回は、12/10(月) 16:30～確率的HPSG導
入 (単一化アルゴリズム、フルパージングア
ルゴリズム、確率的HPSG)
 講義資料


http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH19w/
46

Download Report