数理言語情報論 第11回
2007年1月21日
数理言語情報学研究室 講師 二宮 崇
1
今日の講義の予定





識別モデル
確率的HPSG
最大エントロピー法

GIS, IIS, CG

Yusuke Miyao (2006) From Linguistic Theory to Syntactic
Analysis: Corpus-Oriented Grammar Development and
Feature Forest Model, Ph.D Thesis, University of Tokyo
北研二(著) 辻井潤一(編) 言語と計算4 確率的言語モデル 東大
出版会
Jorge Nocedal, Stephen Wright (1999) “Numerical
Optimization” Springer, 1st edition 1999, 2nd edition 2006
Cristopher M. Bishop “PATTERN RECOGNITION AND
MACHINE LEARNING” Springer, 2006
パーセプトロン
教科書



2
HPSGの確率モデル？
PCFGは各書換
規則に対応す
るパラメータ
を用意すれば
良かった
 HPSGでは？？
S
構文木 t

VP1
SUBJ
NP
OBJ1
が
香織
NP
S
SUBJ
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 → 読んだ
3
PHON: <he, gives, her, a present>
SUBJ: <>
COMPS: <>
SPR: <>
VAL:
PHON: <gives, her, a present>
VAL:
SUBJ: < 1 >
COMPS: <>
SPR:<>
PHON: <gives, her>
VAL:
SUBJ:< 1 >
COMPS:< 3 >
SPR:<>
PHON: <gives>
1
NP[nom][3rd, sing]
he
VAL:
SUBJ: < 1 >
COMPS: < 2 , 3 >
SPR: <>
gives
2 NP[acc]
her
3
NP[acc]
a present
生成モデルから識別モデルへ

識別モデル
直接
~
t  arg max p(t | s; )
t
を解く
 独立な事象を仮定しない
 「条件部の確率」をモデルにいれない
5
生成モデルと識別モデル
(イメージ)
生成モデル
識別モデル
GOOD
BAD
生成モデルと識別モデル
（イメージ２）

生成モデル
絵を描いて全体像の比較

識別モデル
それぞれの特徴を比較




鼻の位置
耳の形
体の大きさ
舌の表面
7
識別するための訓練

教師付学習

良い例と悪い例を与えて、どこに注目すれば
より良く識別出来るのか学習
good examples
bad examples
8
識別モデル
p(t | s )
素性ベクトル
(特徴ベクトル)
(0,0,1,0)
t1
s = “A blue eye girl with white hair and skin walked”
(1,0,1,0)
(1,1,1,0)
t2
t3
(0,0,1,1)
t4
(1,0,0,0)
…
tn
文法Gによりsから導出出来る全ての構文木集合
p(t3|s) はt1,t2,t3,..,tnからt3を選択する確率
CFGの識別モデルの例

構文木生成に用いられた各書換規則の適用
回数
各次元は書
ルールID
1 2 3 4 5 6 7 8 9 10
素性ベクトル(0,0,1,0,3,0,1,1,2,0)
換規則に対
応
構文木中に
含まれる各
書換規則の
適用回数
構文木
構文木の素性ベクトル
簡単なCFGの例
ID
S → SUBJ VP1
1
S → SUBJ V
2
SUBJ → NP が
3
VP1 → OBJ1 V
4
OBJ1 → NP を
5
NP → S NP
6
V → 送った
7
V → 読んだ
8
NP → 香織
9
NP → 恵
10
NP → 電子メール
11
NP → プレゼント
12
NP → 香織 NP1
13
NP → 恵 NP1
14
NP1 → と NP
15
ID 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
素性ベクトル( 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0)
S
構文木 t
VP1
SUBJ
NP
OBJ1
が
香織
NP
S
SUBJ
NP
恵
が
V
を
読んだ
NP
V
電子メール
送った
11
識別モデルのいいところ

独立性を仮定していないので、思いつく限り
いろんな素性をいれれればいれるほど性能が
良くなる


訓練データに対してより良い予測ができるように
なる
逆にoverfittingする可能性がある
c.f. 最大エントロピー法での正規分布の事前分布による
MAP推定でoverfittingを緩和


CFGなら、ルールだけでなく、head wordな
どいろんな素性をいれれば良い
現在の計算機の性能なら数千万次元ぐらい
あっても大丈夫
12
確率的HPSG

「....を満たすブランチ（分岐）はいくつあ
るか？」という素性の集合
CAT: verb
SUBCAT: <NP>
CAT: verb
SUBCAT: <VP>
…
CAT: verb
SUBCAT: <NP>
…
親のcatがverbで左娘の
catがverbで右娘のcatが
verbであるか？
→yes
→ +1
親のcatがverbで左娘の
catがnounで右娘のcatが
verbであるか？
→no
→+0
13
確率的HPSG
ブランチの周辺状況を素性にしている
 親のカテゴリーと左娘のカテゴリーと右娘
のカテゴリーの全ての組み合わせを列挙し
て素性にすれば、先ほどの例のCFGと同じ
素性になる
 カテゴリーだけでなく、head wordや、距
離などいろいろな素性をいれられる

14
確率的HPSGの素性の実例
verb 
 CAT :
head- comp- rule,1, 0,1,VP, has, VBZ, 
,
SUBCAT
:

VP



f 
verb 
 CAT :
1, VP, com e, VBN, 

rule name
SUBCAT :  NP 
distance
of head
words
comma
exists or
not
CAT: verb
SUBCAT: <>
left
daughter’s
category
left
daughter
CAT: noun ’s span
SUBCAT<>
…
Spring
left
daughter
’s POS
CAT: verb
left <NP>
SUBCAT:
daughter’s
head word
CAT: verb
SUBCAT: <VP>
…
has
left
daughter
’s head
lexical
entry
CAT: verb
SUBCAT: <NP>
…
come
素性に関する注意その1

単語の素性と素性値って？

例: head wordが``apple’’であった時の素性値
は？
appleに対応する次元
各次元が単語に対応
する
(0,0,0,0,0,.....,0,1,0,.....,0,0,0,0,0,0)
(訓練データに出現した)単語の数だけ次元がある！
16
素性に関する注意その2

素性の組み合わせ

最大エントロピー法では、素性同士の共起情
報が別素性として自動的に組み込まれるわけ
ではない
 先ほどの例の素性では右娘と左娘のcatが同時に
verbであったときの共起
 SVMなら、カーネルを使うとカーネルの特性によ
る組み合わせを自動的に計算することになる

素性の組み合わせを手で指示しないといけな
い⇒自動的に行うなら「素性選択」を行う
17
素性に関する注意その2: 確率的
HPSGの素性組み合わせの実例
RULE
DIST
COMMA
✔
✔
✔
SPAN
SYM
WORD
POS
LE
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
✔
18
識別モデルの学習
19
問題設定
x: 入力
 y: 出力
 訓練データ

(xi, yi) i=1,...,N
例

 xは文で、yはxに対する正解の構文木
 xは競馬情報で、yは1位の馬

問題

ある未知の入力xに対する出力yの予測
20
素性関数

入力や出力から特徴を抽出する素性関数
(feature function) を複数定義
 fj(x, y)
 注意
j=1,...,M
人手で定義しないといけない
 Mは特にいくつでもかまわないが、増やした分だけ計算
時間・空間がかかったり、overfittingしてしまう
 良い素性関数をできるだけ見つける！ということが人間
がしなくてはいけない重要な仕事


素性ベクトル (または特徴ベクトル, feature
vector)

( f1(x,y), f2(x,y), ..., fM(x, y) )
21
全体の流れ(1/2)

Estimation (推定、パラメータ推定)

各素性 fj に対する重み λj を学習
訓練データ
入力
出力
素性ベクトル
x1
y1
<f1(x1,y1), f2(x1,y1), ..., fM(x1,y1)>
x2
y2
<f1(x2,y2), f2(x2,y2), ..., fM(x2,y2)>
...
...
...
xN
yN
<f1(xN,yN), f2(xN,yN), ..., fM(xN,yN)>
学習
<λ1, λ2, ..., λM>
22
全体の流れ(2/2)

Inference (推測、推定)

未知のデータxに対する出力yの推定
xに対する全
出力候補y
未知の
データ
x
y1
素性ベクトル
y2
<f1(x,y1), f2(x,y1), ..., fM(x,y1)>
y3
<f1(x,y2), f2(x,y2), ..., fM(x,y2)>
学習により得
られた重みベ
クトル
<λ1,...,λM>
...
...
<f1(x,yn), f2(x,yn), ..., fM(x,yn)>
yn
推測
yi
23
最大エントロピー法 (Maximum
Entropy model, ME model)

確率モデル

対数線形モデル(log-linear model)
重み
素性関数


1

p( y | x;  ) 
exp   j f j ( x, y ) 
Z ( x,  )
 j

ただし


Z ( x,  )   exp   j f j ( x, y) 
yY ( x )
 j

正規化項
(Partition function)
24
対数線形モデルの直感的理解
スコアの対数=各素性の(値×重み)の和
 p(y|x)= (xyのスコア)/(xに対する候補集合
y’のスコアの和)




s( x, y,  )  exp   j f j ( x, y ) とおくと、
 j



1

p ( y | x;  ) 
exp   j f j ( x, y )  
Z ( x,  )
 j

s ( x, y ,  )
 s( x, y,  )
y Y ( x )
となる。ちなみに、
s( x, y,  )  e 1 f1 ( x , y )  2 f 2 ( x , y )  M f M ( x , y )  e 1 f1 ( x , y ) e 2 f 2 ( x , y )  e M f M ( x , y )
log s ( x, y,  )    j f j ( x, y )
j
25
パラメータ推定

訓練データに対する対数尤度
 N

log  p( yi | xi ;  ) 
 i 1

当たり前ですが…
N
log ab  log a  logb
  log p( yi | xi ;  )
i 1


1
  log
exp   j f j ( xi , yi ) 
Z ( xi ,  )
i 1
 j

N
N
N
i 1
i 1
loge exp(x)  loge e x  x
だよ！
  log Z ( xi ,  )    j f j ( xi , yi )
j
Zはパラメータを含むexpの足し算になっているか
ら、これの極値を求めるのは難しい…
26
パラメータ推定 もんちぇ
EMの時と
同じだね

パラメータ更新式に変形
新しいパラメータと古いパラメータによる
データ全体に対する対数尤度の差を正（もし
くは正が保証されている中で最大にする）に
するよう更新
 古いパラメータ: λ
 新しいパラメータ: λ’

 N

 N

L( ,  )  log  p( yi | xi ;  )   log  p( yi | xi ;  ) 
 i 1

 i 1

27
パラメータ更新式の導出
 N

 N

L( ,  )  log  p ( yi | xi ;  )   log  p( yi | xi ;  ) 
 i 1

 i 1

N
N
i 1
N
i 1
  log p( yi | xi ;  )   log p( yi | xi ;  )

 N


1
1
  log
exp   j f j ( xi , yi )    log
exp   j f j ( xi , yi ) 
Z ( xi ,  )
Z ( xi ,  )
i 1
 j
 i 1
 j

N
Z ( xi ,  ) N
  log
  ( j   j ) f j ( xi , yi )
Z ( xi ,  ) i 1 j
i 1
N
N
Z ( xi ,  )
  ( j   j ) f j ( xi , yi )   log
Z ( xi ,  )
i 1 j
i 1
 log x  1  xより
N
N
 Z ( xi ,  ) 


  ( j   j ) f j ( xi , yi )   1 
Z ( xi ,  ) 
i 1 j
i 1 
28
パラメータ更新式の導出
Z ( xi ,  )
i 1 j
i 1 Z ( xi ,  )
N
N



1
  exp   j f j ( xi , y )  
  ( j   j ) f j ( xi , yi )  N  



i 1 j
i 1 Z ( xi ,  )  yY ( xi )
 j

N
N



1


  ( j   j ) f j ( xi , yi )  N  
exp  ( j   j ) f j ( xi , y )    j f j ( xi , y )  



i 1 j
i 1 Z ( xi ,  )  yY ( xi )
j
 j

N
N




1
  ( j   j ) f j ( xi , yi )  N   
exp  ( j   j ) f j ( xi , y )  exp   j f j ( xi , y ) 
i 1 j
i 1 yY ( xi ) Z ( xi ,  )
 j

 j

N
N





  ( j   j ) f j ( xi , yi )  N    p ( y | xi ;  ) exp  ( j   j ) f j ( xi , y ) 
i 1 j
i 1 yY ( xi )
 j

N
N


   j f j ( xi , yi )  N    p ( y | xi ;  ) exp   j f j ( xi , y ) 
i 1 j
i 1 yY ( xi )
 j

N
N
L( ,  )   ( j   j ) f j ( xi , yi )  N  
ただし、j
  j   j
29
パラメータ更新式の導出:
Generalized Iterative Scaling (GIS)





p
(
y
|
x
;

)
exp
(



)
f
(
x
,
y
)

i
j
j
i
 j

i 1 j
i 1 yY ( xi )
 j

N
N
f j ( xi , y ) 


   j f j ( xi , yi )  N    p( y | xi ;  ) exp C   j

C
i 1 j
i 1 yY ( xi )
 j

N
N
L( ,  )   ( j   j ) f j ( xi , yi )  N  
ただし、 j
  j   j
ジェンセンの
不等式
C  max f j ( x, y)
x, y
N
j
N
L( ,  )    j f j ( xi , yi )  N  
i 1
j

i 1 yY ( xi )
p( y | xi ;  )
f j ( xi , y)
C


exp C   j 
 j

この最後の式をA(λ, λ’)とおこう
30
パラメータ更新式の導出:
Generalized Iterative Scaling (GIS)
N
N
A( ,  )    j f j ( xi , yi )  N  
i 1

i 1 yY ( xi )
j
p( y | xi ;  )
f j ( xi , y)
C


exp C   j 
 j

ここで、Aを最大化 (=極値を求める)
N
A( ,  ) N
  f j ( xi , yi )    p( y | xi ;  ) f j ( xi , y) exp(C j )  0
 j
i 1
i 1 yY ( xi )
N
exp(C j ) 
f
i 1
j
( xi , yi )
N
  p( y | x ;  ) f
i 1 yY ( xi )
i
j
( xi , y )
N
1
 j  log
C
f
i 1
j
( xi , yi )
これがGISのパラ
メータ更新式だ！
N
  p( y | x ;  ) f
i 1 yY ( xi )
i
j
( xi , y )
31
パラメータ更新式の直感的理解
訓練データに対する素性値の
合計
N
1
 j  log
C

i 1
f j ( xi , yi )
N
  p( y | x ;  ) f
i 1 yY ( xi )
i
j
( xi , y )
正解候補集合に対する素性値
の期待値を合計
パージングなら、、、
文s
...
t1
t2
t3
tn
p(t1|s;λ)
p(t2|s;λ)
×
fj(s,t2)
p(t3|s;λ)
×
fj(s,t3)
p(tn|s;λ)
×
fj(s, tn)
×
fj(s, t1)
32
GISアルゴリズム
Input: training data D={<x,y>}, feature functions f={fj}, initial parameters λ={λj}
Output: optimal parameters λ
foreach <x,y> ∈ D
foreach fj ∈ f such that fj(x,y) ≠ 0
μ’j := fj(x,y)
C := -∞
loop until λ converges
foreach <x,y> ∈ D
R := {}; Z := 0
foreach y’ ∈ Y(x)
C := max(∑j fj(x,y’), C); S := exp(∑k λkfk(x,y’)); Z := Z + S
R := R ∪ {<y’, S>}
foreach <y’, S> ∈ R
foreach fj ∈ f such that fj(x,y’) ≠ 0
μj := μj + fj(x,y’)・1/Z・S
foreach fj∈f
Δλj := 1/C・log(μ’j/μj)
λj := λj + Δλj
33
素性森 (Feature Forest)

最大エントロピー法では基本的に、「あ
る文xに対する全ての構文木集合Y(x)に対
する確率」を計算しないといけない
N
1
 j  log
C
f
i 1
( xi , yi )
N
  p( y | x ;  ) f
i 1 yY ( xi )

j
i
j
( xi , y )
PCFGの内側外側アルゴリズムと同じアイ
デアで、畳みこまれた構文木集合（構文
解析後のチャート）を展開することなく
∑y∈Y(x)p(y|x)×fj(x, y)を計算
34
素性森

各ブランチのスコアの積＝全体のスコア
構文木全体の素性ベクトル: (1,0,2,1,0)
e11e2 0e3 2e4 1e5 0
...
(0,0,1,0,0)
...
(1,0,1,1,0)
...
...
...
e10e2 0e3 1e4 0e5 0
掛算
e11e2 0e3 1e4 1e5 0
35
素性森

構文木の確率


1

p( y | x;  ) 
exp   j f j ( x, y ) 
Z ( x,  )
 j

Z ( x,  ) : 構文木集合全体の確率の和（＝文全体に対す る内側確率）


 f ( x, y )
 f (c)
exp   j f j ( x, y )    e j j
  e j j
j
c
j
 j

c : 構文木の各ブランチ

内側外側アルゴリズムの適用
PCFGの書換規則の
確率に対応
書換規則の適用回数⇒素性値(素性の発火回数)

e
 書換規則の確率 θr ⇒ブランチのスコア 

j
j
f j (c)
36
EMと最大エントロピー法
POSタガー
パーザー
データ構造
曖昧性のある畳み込まれた列 曖昧性のある畳み込まれ
た木構造
EMアルゴリズム
前向き後向きアルゴリズム
内側外側アルゴリズム
最大エントロピー法
CRF (Conditional Random
Field)
素性森 (Feature
Forest)
37
その他のパラメータ推定アルゴ
リズム
38
パラメータ更新式の導出:
Improved Iteretive Scaling (IIS)
GISでは
としていたが、
C  max f j ( x, y)
x, y
j
C ( x, y)   f j ( x, y) とする
j





p
(
y
|
x
;

)
exp
(



)
f
(
x
,
y
)

i
j
j
i
 j

i 1 j
i 1 yY ( xi )
 j

N
N
f j ( xi , y ) 


   j f j ( xi , yi )  N    p( y | xi ;  ) exp C ( x, y )  j

C
(
x
,
y
)
i 1 j
i 1 yY ( xi )
j


N
N
L( ,  )   ( j   j ) f j ( xi , yi )  N  
ただし、
j   j   j
ジェンセンの
不等式
C ( x, y)   f j ( x, y)
j
N
N
L( ,  )    j f j ( xi , yi )  N  
i 1
j

i 1 yY ( xi )
p( y | xi ;  )


exp C ( x, y)  j 
C ( x, y)
j


f j ( xi , y)
この最後の式をA(λ, λ’)とおこう
39
パラメータ更新式の導出:
Improved Iteretive Scaling (IIS)


A( ,  )    j f j ( xi , yi )  N    p( y | xi ;  )
exp C ( xi , y)  j 
C ( xi , y)
i 1 j
i 1 yY ( xi )
j


N
N
f j ( xi , y)
ここで、Aを最大化 (=極値を求める)
N


A( ) N
  f j ( xi , yi )    p( y | xi ;  ) f j ( xi , y) exp C ( xi , y)  j   0
 j
i 1
i 1 yY ( xi )
j


・1変数の方程式になっているので、上の式をニュートン法で
解けばよい
・上の式のC(xi,y)が同じ項をまとめるとC(xi,y)が同じデータ
に対してのみモデル期待値を記憶しておくだけですむ
・C(xi,y)を定数CにしたのがGISで、GISではニュートン法を
使わなくても直接解析的に解ける。GISの収束はIISより遅い。
・C(xi,y)のバリエーションが多いと、メモリが大量に必要。
40
パラメータ推定:勾配ベースのア
ルゴリズム

目的関数の勾配から勾配ベースの推定アル
ゴリズムでパラメータ推定が可能
最急降下法 (steepest decent method)
 共役勾配法 (Conjugate Gradient, CG; Fletcher
& Reeves 1964)
 BFGS (L-BFGS) (Nocedal 1980)
 自然言語処理では、経験的に勾配ベースのア
ルゴリズムの方がIISより非常に速く収束する
ため、勾配ベースのアルゴリズムが望ましい
(Malouf 2002)

41
パラメータ推定: 勾配ベースのア
ルゴリズム
目的関数


L( )  log  p( y | x ;  )    log Z ( x ,  )   


 勾配

N
N
i
i
N

i 1
N

i 1
N
i 1
j
f j ( xi , yi )
j
Z ( xi ,  )
1
f j ( xi , yi )  
 j
i 1 Z ( xi ,  )
N


1

f j ( xi , yi )  
f j ( xi , y ) exp   j f j ( xi , y ) 

i 1 Z ( xi ,  ) yY ( xi )
 j

N
N
  f j ( xi , yi )  
i 1
i
i 1
i 1
L( )
 j
N
 p( y | x ;  ) f
i 1 yY ( xi )
g  L( ) 
i
j
( xi , y )
L( )
L( )
, ,
1
n
42
パラメータ推定: 最急降下法



パラメータ更新式
λ ( k 1)  λ ( k )   ( k )g( k )
αは適当な小さな値もしくは一次元最適化(直線探索 ともい
う) (one-dimensional line search) で決定
黄金分割にすると、
L(λ)の計算が2回で
収束が非常に遅い
はなくて1回で済む
一次元最適化
1. 候補領域の決定
あるステップ幅をg方向に2乗しなが
ら探索し、L(λ’)<L(λ)になったと
ころで候補領域の決定
λ‘(k)
λ(k)
2. 候補領域を3分割(黄金分割)し、2
つの中間点のL(λ)を計算し、その大小
を比較することにより、左か右の領域
を候補領域から削除。2.を繰り返す。
削除
λ’(k)
λ(k)
43
パラメータ推定: 共役勾配法
Conjugate Gradient (CG)

更新式
λ ( k 1)  λ ( k )   ( k )d ( k )
d ( k )  g ( k )   FRd ( k 1)
 FR
g (k )g (k )
 ( k 1) ( k 1)
g g
αは1次元最適化(one-dimensional line search)
で求める
 毎回、直交する方向に探索している
 n次元なら、n回の繰り返しで終了

44
パラメータ推定: 準ニュートン法

多次元のニュートン法


ヘシアンの逆行列の計算が重い…
準ニュートン法



ヘシアン逆行列を近似する
BFGS (Broyden 1970, Fletcher 1970, Goldfarb 1970,
Shanno 1970)が有名。ただし、|λ|2のサイズの行
列を扱うので、巨大な次元の素性ベクトルには向
かない
Limited-memory BFGS (L-BFGS) (Nocedal 1980)は
少ないメモリでヘシアン逆行列を近似する。最大
エントロピー法ではよく使われる。
45
パーセプトロン (Perceptron)

最大エントロピー法の問題点


Z(正解候補集合のスコアの和)の計算が重い
パーセプトロン

訓練データxiに対しyiを出力する確率が、正解候補集合
Y(xi)のどの要素の確率よりも高ければ良い
log p( yi | xi ;  )  log p ( y | xi ;  )を大きく ( y  arg max p( y | xi ;  ))
yY ( xi )
   j f j ( xi , yi )   j f j ( xi , y)を大きく
j



j
訓練データの正解と現在のパラメータで推測され
る最も確率の高い答えとだけ比較
実装もアルゴリズムも簡単！
最大エントロピーより性能は落ちるけど、メモ
リー使用量や学習時間の点で非常に有利
46
パーセプトロン: アルゴリズム
Input: training data D={<x,y>}, feature functions
f={fj}, initial parameters λ={λj}
Output: optimal parameters λ
loop until λ converges
foreach <x,y> ∈ D
z’ := argmaxz p(z|x;λ)
if( y ≠ z’ )
foreach fj ∈ f
λj := λj + fj(x, y) – fj(x, z’)
47
おまけ
最大エントロピー法の理論的背景
48
最大エントロピー法の理論的背景
確率モデルはどこからきたのか？
 エントロピーを最大化？



1

p( y | x;  ) 
exp   j f j ( x, y ) 
Z ( x,  )
 j

ただし


Z ( x,  )   exp   j f j ( x, y) 
yY ( x )
 j

49
経験確率（経験期待値）と
モデル確率（モデル期待値）

経験確率

データ {<xi, yi>}が与えられた時、
C ( x, y )
~
p ( x, y ) 
N
C ( x)
~
p ( x) 
N

モデル確率
求める確率分布
 パラメータを含み、これを推定するのが目標

pM ( y | x)
pM ( x, y)  ~
p( x) pM ( y | x)
50
経験確率
データの頻度(経験確率分布)
訓練データの列
x1
x2
x3
y
freq(x,y)
p(x,y)
0
0
0
0
983428
983428/N
x1
x2
x3
y
0
0
0
1
58123
58123/N
1
1
0
1
0
0
1
0
178237
178237/N
1
0
0
0
0
0
1
1
1323
1323/N
0
1
1
1
0
1
0
0
748
748/N
1
1
0
1
0
1
0
1
23
23/N
1
1
1
0
0
1
1
0
373
373/N
0
0
1
1
0
1
1
1
2384
2384/N
0
0
1
1
1
0
0
0
82
82/N
1
1
1
0
1
0
0
1
343781
343781/N
1
1
0
0
1
0
1
0
45854
45854/N
1
1
1
0
1
0
1
1
83472
83472/N
0
1
0
0
1
1
0
0
6474
6474/N
0
0
0
1
1
1
0
1
27
27/N
...
...
...
...
1
1
1
0
8239
8239/N
1
1
1
1
634
634/N
=
準備
X: 入力xの全空間
 Y(x): 入力xに対する出力yの全空間
 F: 素性関数の集合
 エントロピー

H ( p)    p( x) log p( x)
xX

条件付きエントロピー
H ( p)    p( x)
xX
 p( y | x) log p( y | x)
yY ( x )
52
準備

カルバックライブラー距離(Kullback-Leibler
distance)
KL( p, q)   p( x) log
xX

条件付き確率の場合
KL( p, q)   p( x)
xX





p ( x)
q ( x)
 p( y | x) log
yY ( x )
p( y | x)
q ( y | x)
二つの確率分布の近さを表す尺度
相対エントロピー(relative entropy)とも呼ばれる
一様分布との距離最小化⇔エントロピー最大化
KL(p,q)≧0
p=qならばKL(p,q)=0
53
最大エントロピー法

素性値の制約

モデル期待値=経験期待値
f j  F　 ~
p( x)
xX

 p( y | x) f j ( x, y) 
yY ( x )
~
 p( x, y) f j ( x, y)
xX , yY ( x )
条件付き確率にするための制約
x  x　 p( y | x)  1
yY ( x )

エントロピー最大化
H ( p)    ~
p ( x)
xX
 p( y | x) log p( y | x)
yY ( x )
pM ( y | x)  arg max H ( p)
p
54
解く

H(p)を等式制約の元で最大化⇒ラグラン
ジェの未定乗数法
 ラグランジアン
 ( p,  ,  )  H ( p ) 
 ~

~
p ( x)  p( y | x) f j ( x, y )   p ( x, y ) f j ( x, y ) 
j  j x
yY ( x )
xX , yY ( x )
 X



 x   p( y | x)  1

xX
 yY ( x )


ラグランジアンをp(y|x)で偏微分
( p,  ,  )
 ~
p ( x)(log p( y | x)  1)  ~
p ( x)  j f j ( x, y)   x  0
p( y | x)
j
55
解く
前スライドの等式をp(y|x)について解くと、




x 
x 





p( y | x)  exp   j f j ( x, y)  1  ~   exp   j f j ( x, y)  exp  1  ~ 
p ( x) 
p ( x) 

 j
 j

次に、ラグランジアンをκxで偏微分
( p,  ,  )
  p( y | x)  1  0
 x
yY ( x )
上の式を代入して解くと、、、（次スライ
ド）
56
パラメトリックフォームがでました



x 


exp   j f j ( x, y )  exp  1  ~   1  0

p ( x) 
yY ( x )

 j




x 

 exp  1  ~   exp   j f j ( x, y )   1
p ( x)  yY ( x )

 j


 
 exp  1  ~ x  
p ( x) 

1


exp   j f j ( x, y ) 

yY ( x )
 j

p(y|x)の式に代入すると、


p( y | x) 
exp   j f j ( x, y ) 


 j




exp

f
(
x
,
y
)

 j j


y Y ( x )
 j

でました！
1
57
解く
最後にラグランジアンに求まったp(y|x)を
代入、極値を求めてλを求める
 ( p,  ,  )   ~
p ( x)  p( y | x) log p( y | x) 

xX
yY ( x )
 ~

~
p ( x )  p ( y | x ) f j ( x, y )   p ( x, y ) f j ( x, y )  
j  j x
yY ( x )
xX , yY ( x )
 X



この項は0になる
 x   p( y | x)  1

ことに注意
xX
 yY ( x )

 ( ) 
 ~p( x)
xX




1
1




exp

f
(
x
,
y
)
log
exp

f
(
x
,
y
)



j j
j j




Z ( x)
yY ( x ) Z ( x )
 j

 j





1
 ~

~



p
(
x
)
exp

f
(
x
,
y
)
f
(
x
,
y
)

p
(
x
,
y
)
f
(
x
,
y
)

j j x


j
 j j
 j
Z
(
x
)

yY ( x )
xX , yY ( x )
 j

 X

58
解く
 ( ) 







1



exp   j f j ( x, y )  log Z ( x)    j f j ( x, y )  

x X
yY ( x ) Z ( x )
j
 j






1


~
~


p
(
x
)
exp

f
(
x
,
y
)

f
(
x
,
y
)

p ( x, y )   j f j ( x, y )
 





j
j
j
j



x X
j 
j
 j

 yY ( x ) Z ( x)
 xX , yY ( x )



1
~




p
(
x
)
exp

f
(
x
,
y
)
log
Z
(
x
)


f
(
x
,
y
)




j j
j j




x X
yY ( x ) Z ( x )
j
 j





1
~



  ~
p
(
x
)
exp

f
(
x
,
y
)

f
(
x
,
y
)
p ( x, y )   j f j ( x, y )




j
j
j
j




x X
yY ( x ) Z ( x )
j
 j
 j
 xX , yY ( x )


1
~

 log Z ( x)   ~
p
(
x
)
exp

f
(
x
,
y
)
p ( x, y )   j f j ( x, y )



j
j


x X
yY ( x ) Z ( x )
x X , yY ( x )
j
 j



1
~

p ( x) log Z ( x) 
exp   j f j ( x, y )    ~
p ( x, y )   j f j ( x, y )

Z
(
x
)
x X
yY ( x )
j
 j
 xX , yY ( x )
 ~p ( x) log Z ( x)   ~p ( x, y)  j f j ( x, y)
 ~p ( x)
x X
x X , yY ( x )
j
59
解けたー
 ( ) 
~
 p( x) log Z ( x) 
xX

1
N
N

xX , yY ( x )
N
1
log Z ( xi ) 

N
i 1
 
i 1
~
p ( x, y )  j f j ( x, y )
j
j
f j ( xi , yi )
j
なんと、p.26の数式をみてみると、ラグラン
ジアンの極値と最尤推定の極値は一致して
いる！
つまり、エントロピー最大化により求まる
モデルと最尤推定により求まるモデルは一
致するのだ
60
最大エントロピー法と対数線形法

最大エントロピー法(maximum entropy
model)


対数線形モデル(log-linear model)



素性に対する制約＋エントロピー最大化によるモ
デル推定
log-linearで表現される確率モデルの最尤推定
歴史的には、この二つは別々に研究されてき
たが、近年これらのモデル推定の結果が同一
になることがわかった
以上の理由で、最大エントロピー法と対数線
形モデルと二つの呼び名がある
61
まとめ
識別モデル
 確率的HPSG
 学習アルゴリズム

最大エントロピー法 (GIS, IIS, CG)
 パーセプトロン

次回は涙の最終回、1/28(月) 16:30～ HPSG
文法開発
 講義資料


http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH19w/
62
レポート課題

課題（いずれかのうち一つ）

言語学、パージングもしくは機械学習に関する論文を一つ以上
読んで内容をまとめよ


授業内容でよくわからなかった箇所を教科書やスライドを頼り
に例題を作りつつ内容をまとめ、考察せよ

例: CCGやHPSGで簡単な文法を（紙の上に)書き、（紙の上で）構文
解析
例: 正規分布の混合分布に対するEMの導出
例: エントロピー最大化によるパラメータ推定とパラメトリック形式
の最尤法によるパラメータ推定が一致することを確認
例: 素性構造のコピーや等価性チェックのアルゴリズムを書く

例: 最大エントロピー法のスムージングのための正規分布の事前分布





ACL, NAACL, COLING, EMNLP, ICML, NIPS, IJCAIあたりが望ま
しいがこれらに限定はしない
授業内容に関連する内容を発展させた内容を調査もしくは考察
全ての授業に出席した人は、全ての回の感想を簡単にまとめて
提出
63
レポート課題





A4で4ページ以上
日本語か英語
microsoft word, pdf, psの電子的媒体もしくは紙で提出
締切: 2008年2月15日(金)
提出先

電子的媒体の場合(最も推奨)


[email protected]に提出
紙の場合


事務に提出(推奨)
直接持ってくる


http://www.r.dl.itc.u-tokyo.ac.jp/?q=node/12
学内便で「総合図書館内 情報基盤センター 二宮 崇」宛に送る (た
だし、1週間前の2月8日(金)までに提出する)
64

ベイズ的ロジスティックモデル における研究

スライド 1

ダウンロード

パターン認識と機械学習

周辺尤度計算における温度交換の確率

PowerPoint プレゼンテーション

物性物理学序論

数理シミュレーションによる個体群管理技術の検討と生