43 Boltzmann Machines 44 Supervised Learning in

``Exponentiated Gradient Algorithms for LogLinear Structured Prediction’’
A.Globerson, T.Y.Koo, X.Carreras, M.Collins
を読んで
渡辺一帆（東大・新領域）
構成
１．Introduction
２．Primal and Dual Problems for Log-Linear Models（モデルと主、双対問題）
３．Exponentiated Gradient Algorithms（Kivinen & Warmuth, 1997）（アルゴリズム）
４．Convergence Results （収束性の証明）
4.1 Divergence Measures
4.2 Convergence of the Batch Algorithm
4.3 Convergence of the Online Algorithm
この辺りがメイン
4.4 Convergence Rate of the Batch Algorithm
4.5 Convergence for Max-Margin Learning
5. Structured Prediction with LLEG (ラベルが構造を持つ場合)
6. Related Work
7. Experiments（多クラス分類と係り受け解析で実験）
8. Conclusion
対数線形モデル（2節）
入力 x  
ラベル y  Y (xに依存しても良い)
時系列、木などの内部構造をもつ高次元データ
特徴ベクトル
 ( x, y)  R d
を用意
（条件付き）対数線形モデル
p( y | x; w ) 
1 w ( x , y )
e
Zx
w
○ x の分類は
y*  arg maxw   ( x, y)
y
○ ロジスティック回帰モデルを含む
:パラメータ
主問題と双対問題（2節）
n
学習データ ( xi , yi )i1
正則化された対数尤度を最大化
主問題
C
n

w  arg max log p( yi | xi ; w)  || w ||2 
2
w
 i 1

*
Q (α ) とおく
双対問題
n

1
α  arg min i , y log i , y 
|| w(α) ||2 
2C
α
 i 1 y

*
n
w(α)   i , y i , y
i 1
 i, y   ( xi , yi )   ( xi , y)
y
制約：各 αi は確率分布（  i , y  1）
y
（ αi  
と書く）
導出
n
 log p( yi | xi ; w) 
i 1
C
|| w ||2
2

 C
  log expw( ( xi , y)   ( xi , yi ))  || w ||2
i 1
 y
 2
 w  i, y Zi   exp w i , y 
n
i, y
n
   i , y log
i 1
y
1  w i , y
e
Z i  w
（等号は  i , y 
C
  log Z i  || w ||2  L(w, α)
2
i 1
e
i,y
e
 w i , y
y
L(w, α )
0
w
y
n
のとき）
1 n
w   i , y i , y
C i 1 y
これを L(w, α) に代入してQを得る
とおく
Exponentiated Gradient（３節）
• Exponentiated Gradient Algorithm (Kivinen and Warmuth, 1997)
α t  n を

t 1
i, y
1

 it, y e i , y
Zi
i , y 
Q(α)
 i , y
により更新
Zi   it, yˆ e
i , yˆ
：学習係数
ˆ
y
オンラインだと
i , y 

 i , y
Q(α1t 1 , α t21 ,...,α ti 11 , α ti ,...,α tn )
双対問題のQだと
 i , y  1  log  i , y 
1
w (α )  i , y
C
とする
ダイバージェンス（4.1節）
α, β  n 間のダイバージェンス
• KL-ダイバージェンス
D[α i || βi ]   i , y log
y
i, y
D[α || β]   D[α i || βi ]   i , y log
i , y
i
i
y
• Bregman ダイバージェンス
i, y
i , y
Qˆ (α)  i , y logi , y
i
y
Qˆ (α)：凸関数
BQˆ [α || β]  Qˆ (α )  Qˆ (β)  Qˆ (β)  (α  β)
• マハラノビス距離
M A [α || β] 
1
(α  β)T A(α  β)
2
1
Qˆ (α )  α T Aα
2
収束性の証明（4.2節）
• Lemma 1
Qˆ は任意の凸関数（具体的な形にはよらない）
D[α t 1 || α t ]  BQˆ [α t 1 || α t ] のようにηをとれば
1
Qˆ (α t )  Qˆ (α t 1 )  D[α t || α t 1 ]

EGの更新で Qˆ は単調減少する
双対問題のQだと
• Lemma 2
0  
1
1  n | A |
1
| A |  max (i , y ),( j , z ) | A(i , y ),( j , z ) | max (i , y ),( j , z ) |  i , y  j , z |
C
ととれば
Q(α t )  Q(α t 1 ) 
1

D[α t || α t 1 ]
(略証)
BQ[αt 1 || αt ]  D[αt 1 || αt ]  M A[αt 1 || αt ] となることを使う
○ オンラインも同様に証明可能（4.3節）
収束の速さ（4.4節）
• Lemma 4 (Kivinen & Warmuth, 1997)
任意の u   に対し、
n
Q(αt ) Q(u)  D[u || αt ]  D[u || αt 1 ]  D[αt || αt 1 ]
Q(αt 1 ) Q(u)  D[u || αt ]  D[u || αt 1 ]
Lemma 2
Q(α
T 1
t=1,…Tの和をとり
Qが単調減少することから
D[u || α1 ]  D[u || αT 1 ]
)  Q(u) 
T
Q(α
u  α*（最適解）とすると
T 1
D[α* || α1 ]
)  Q(α ) 
T
*
 1 
Q(αT 1 )  Q(α* )   とするには T  O 
  
1
2
○ Max-Marginの場合（ QMM (α)  bT α  α T Aα のとき）も同様（4.5節）
構造があるとき（5節）
ラベル
はパーツ r の集合だとする
y
yR
 ( x, y)   ( x, r )
:パーツ全体
のように分解できるとする
ry
αti の代わりに θti
変換は
を使う
θti  {it,r | r  R}


 ry

t

 it, y (θ ti )  exp 


i ,r 

t
 it,r 1   it,r   
 i , r 

パーツの個数だけ
1

w (α(θt ))   ( xi , r ) 
C

で更新できる。
（EGでの i, y はyに含まれるrに関する項のみきいてくるので）
実験（7節）
この例では（たまたま）
• 多クラス分類
w y x
p( y | x)  e
y  {1,...,10}
wy , x  R
784
目
的
関
数
の
値
EG(primal)も単調増加（しかも速い）
分
類
精
度
共役勾配法、L-BFGSと比較
計算時間
計算時間
• 構造がある場合（係り受け解析）
目
的
関
を単語のペア (h, m)に与える数
の
値
解
析
精
度
特徴ベクトル  ( x, h, m)
計算時間
計算時間
結論
• 対数線形モデルに対し最適解への収束が保証され
たアルゴリズムを提案
• 証明のほとんどはBregmanダイバージェンスとKLダ
イバージェンスの間の関係に因る
• 他の関数Qについても同様の解析が可能であると
期待される
• オンラインアルゴリズムについても1/Tの収束の速さ
を証明するのは今後の課題

Download Report