mlmt100520

A Stochastic approximation method
for inference in probabilistic
graphical models
機械学習勉強会
2010/05/20
森井正覚
1
紹介する論文
• A Stochastic approximation method for
inference in probabilistic graphical models
(P. Carbonetto, M. King, F. Hamze NIPS 2009)
2
概要
• 確率モデルの推論の新たな枠組み．
• 近似分布は扱い易いクラスに限定されない．
• 逐次モンテカルロ法とみなすこともできるが，
人工的な分布の列を設計する必要がない．
• LDAの推論と関連がある集団遺伝学の推定
問題で実験した．
3
目次
1.
2.
3.
4.
5.
導入
潜在的ディリクレ配分法
アルゴリズムの説明
集団遺伝学への応用
まとめ
4
確率モデルの近似推論法
1. MCMCによるモンテカルロ推定
2. 重点サンプリングによるモンテカルロ推定
3. 変分推論法
– 解析的に”良い”性質を持っている近似分布族を
見つける．
– いい近似分布を見つけるため，KL情報量を最適
化する．
– 最もいい近似分布が，真の分布より大きくずれ
るかもしれない．
5
提案手法
• 扱い易い近似分布のクラスを制限しない変分
推論法を提案する．
6
提案手法の特徴
• KL情報量の勾配が直接計算できないため最
適化するのが難しい．
• 勾配をモンテカルロ推定し，それを逐次モン
テカルロ法により更新する．
タイトルが確率推論の確率的近似法
• 勾配降下のステップ幅が大きいと，縮退して
しまうので，それを防ぐ仕組みを導入．
7
目次
1.
2.
3.
4.
5.
導入
潜在的ディリクレ配分法
アルゴリズムの説明
集団遺伝学への応用
まとめ
8
2 潜在的ディリクレ配分法(Latent
Dirichlet allocation)
• 文書集合の生成モデル
– 文書 d ∈ {1,…,D}
– 単語 wdi ∈ {1,…,W}
– トピック zdi ∈{1,…,K}
– トピック集合で k 番目のトピックで，語彙集合で j
番目の単語が現れる確率は βkj．
– τdk ≡ p(zdi = k | τd)
9
潜在的ディリクレ配分法(Latent
Dirichlet allocation)
• 観測データ w と未知の β,τ,z の確率は，
K
D
k 1
d 1
D
N
p ( w,  , , z |  , )   p (  k |  )  p ( d |  )  p ( wdi | z di ,  )  p ( z di |  d )
d 1 i 1
10
目次
1.
2.
3.
4.
5.
導入
潜在的ディリクレ配分法
アルゴリズムの説明
集団遺伝学への応用
まとめ
11
重点サンプリング
• 目標とする分布 p(x) について，φ(x) の期待値
E p () [ ( X )]    ( x) p( x)dx を求めたい．
• 重点サンプリングは．提案分布 q(x) と重要度
重み w(x) = p(x)/ q(x) を用いると，モンテカル
ロ推定量は，
n
(s)
(s)
1
E p () [ ( X )]  n s 1 w( x ) ( x )
• 提案分布をうまく設計しないと，大きな誤差が
生じてしまう．
12
3. アルゴリズムの説明
• p(x) を p^(x;θ) で置き換えたモンテカルロ推定
をする．
• この推定量は偏りがあるが，変分問題を解く
ことにより，偏りを最小化する．
• 確率的近似ステップと逐次モンテカルロス
テップを反復する．
• p^(x;θk) → p(x) a.s. なら，モンテカルロ推定量
は目標の期待値にほとんど確実に収束する．
13
アルゴリズムの概要
3.1
• Draw samples from initial density p^(x;θ1).
• for k = 2, 3, 4, . . .
3.3
3.2
– Stochastic approximation step: take gradient
descent step θk = θk-1 – αk gk where gk is a Monte
Carlo estimate of the gradient of the K-L
divergence, and αk is the variance safeguarded
step size.
3.5
– SMC step: update samples and importance
weights to reflect new density p^(x;θk).
3.4
14
3.1 The family of approximating
distributions
• θでパラメータ化された近似分布族 p^(x;θ) を作
る．
• 以下の条件を満たす近似分布族を考える．
p^(x;θ1) からサンプリングできるような θ1 が1つ以上
存在する．
2. p^(x;θ*) = p(x) となるような θ* が存在する．
3. 以下で表される指数型分布族である．
1.
pˆ ( x; )  exp a( x),   c( )
+. 常に p^(xA|xB;θ) と p^(xB|xA;θ) からサンプリングでき
るように，x を2つの集合に分割できる．
15
3.1 The family of approximating
distributions
• LDAでは，以下の近似分布族を用いた．
D
K
K
W
pˆ ( x; )  expd 1 k 1 ( k  ndk  1) log  dk  k 1  j 1 (ˆkj  1) log  kj
K
W
K
W
  k 1  j 1 mkj log  kj   k 1  j 1 (c j  mkj ) log  kj  c( )
• mkj は，j 番目の単語が k 番目のトピックに割り当てら
れた数．
• ndk は，k 番目のトピックが d 番目の文書に割り当てら
れた数．
• cj は j 番目の単語が観測された数．
– 自然母数 θ = {η^, φ, γ} ≧ 0.
– φ = 1,γ = 0, η^ = η とすると p(x) が復元できる．
16
3.2 The variational objective
• p(x) =p^(x;θ*) と p^(x;θ) の KL情報量は，
F ( )  E pˆ (; ) [a( X )],    *  c( *)  c( )
F ( )  Var pˆ (; ) [a( X )](   *)
• ∇F(θ) にある積分を計算するが難しい．
• 標本 x(s) と重要度重み w(s) から，モンテカル
ロ推定をする．
F ( )  s 1 w( s ) (a( x( s ) )  a )(a( x( s ) )  a )T (   *)
n
a  
n
(s)
(s)
w
a
(
x
)
s 1

17
3.3 Stochastic approximation
• “平均して”前進することが求められる．
• 次式で探索方向を更新する．
 k 1   k   k Bk1 g k
– Bk は準ニュートン法(BFGS)で用いられるヘッセ行列
を減衰(?)した行列，gk は ∇F(θk-1) のモンテカルロ推
定量．
• θ≧0 の条件があるため，確率内点法を用いる．
• ステップ後，標本は新しい分布を反映するよう
更新する．
18
3.4 Sequential Monte Carlo
• 最初のステップでは，標本 x1(s) は， q1(x)
=p^(x;θ1) からサンプリングする．
• kステップ後の提案分布は，
q~k ( x1:k )  K k ( xk | xk 1 )  K 2 ( x2 | x1 ) pˆ ( x1;1 )
• p~k(x1:k) をうまく選べば，重要度重みは，
~ (x )  ~
~ (x )
w
p
(
x
)
/
q
k
1:k
k
1:k
k
1:k
• 重要度重みを以下のように更新する．
~ (x )  ~
~
~ (x )
w
p
(
x
;

)
/
p
(
x
;

)

w
k
1:k
A
k
A
k 1
k 1 1:k 1
19
3.5 Safeguarding the variance
• ステップ幅が大きいと，縮退してしまうので，
次の尺度を用いてステップ幅を抑える．
~ ( x( s ) )  1 )2
Sk ( k )  s 1 (w
k
1:k
n
n
S k ( k )  S k 1 ( k 1 )
• 保護ステップ幅 αk は次式を解いて得る．
1
2
kT 2 Sk (k 1 )k k2  kT Sk (k 1 ) k  1 Sk 1 (k 1 )
– Δθk は反復kにおける探索方向．
– Sk(θk) の微分は線形時間で計算できる．
• ESS(有効サンプルサイズ) も用いる．
20
21
目次
1.
2.
3.
4.
5.
導入
潜在的ディリクレ配分法
アルゴリズムの説明
集団遺伝学への応用
まとめ
22
4 集団遺伝学への応用
• LDAと同じPrichardらのモデル
LDA
population
structure
文書
個体
単語
遺伝子
トピック
個体群
• 右図のような過程
を考える．
– 個体 60
– 遺伝子 30
– 個体群 4
23
実験の目標
• 次の2つの統計量を復元することが目標
– d と d’ の admixture distance
1 K
 ( d , d ' )    dk   d 'k
2 k 1
2つの個体の祖
先の非類似度
– admixture level
K
K
1
 ( d )  1 
 dk 

2( K  1) k 1
K
0・・・個人の遺伝子
が1つの集団から来
ている．
1・・・祖先が K の集
団に等しく分けられ
ている．
24
実験手法
• 以下の3つの手法を比較する．
– Stochastic approximation (SA) ・・・提案手法
– MCMC
– Annealed importance sample (AIS)
• 2つのデータセットに対し，K を 2～6まで．
• 各手法は独立な試行を 20 回行った．
• 公平のためサンプリング事象の数は同じに．
– MCMC・・・50000のマルコフ連鎖，10000のburn-in．
– SMC・・・100粒子，反復数500回．
25
admixture distance と admixture level
の推定
• E ( d , d ' ), E ( d ) の推定値からの最も大きい
差をプロット．
• Stochastic approximation は，ほぼすべての
場合で最も良い．
26
結果の分析
• 突然変異率 1/2,K = 4 と突然変異率 2,K=3 の
場合でシミュレーション結果を詳しく見てみる．
• 平均行列(60次正方行列，集団ごとに整列)
– 黒い要素は共通の祖先を持つことを意味し，白
い要素は共通の祖先を持たないことを意味する．
• 標準偏差行列
– 要素が黒いほど，分散が大きいことを意味する．
(結果が疑わしい．)
27
admixture distance の平均と分散(突
然変異率1/2,K=4)
28
admixture distance の平均と分散(突
然変異率1/2,K=4)
• MCMC
– 試行1では，集団を正しく4つに区別した．
– 試行2では，集団3と集団4を区別するのに失敗し，
集団2もおかしい．
• AIS
– MCMCと似た振る舞いをした．
• Stochastic approximation
– 集団3と集団4を区別するのに失敗した．
– 結果に一致性がある．
29
admixture distance の平均と分散(突
然変異率2,K=3)
30
admixture distance の平均と分散(突
然変異率2,K=3)
• 先程の設定，突然変異率1/2,K=4 より難しい．
• MCMC
– 試行1はとても正確だった．
– 試行2では，集団1と集団2を区別するのに失敗し，
集団3と集団4を正しく割り当てるのに失敗した．
• Stochastic approximation
– いくつか不一致なところがあるが，結果にばらつ
きがあるMCMCとは違い，結果に一致性がある．
31
目次
1.
2.
3.
4.
5.
導入
潜在的ディリクレ配分法
アルゴリズムの説明
集団遺伝学への応用
まとめ
32
5 まとめ
• 変分推論，モンテカルロ法と確率的近似法に
基づく新しい確率推論手法を提案した．
• 確率推論の問題で一致性と信頼性のある結
果を得た．
• 提案手法の成功は，変分近似の選び方にか
かっている．
– LDA以外のモデルに対してはまだよく分からない．
• 反復数に敏感であることを改善したい．
33

Download Report