A Stochastic approximation method for inference in probabilistic graphical models 機械学習勉強会 2010/05/20 森井正覚.

Presentation on theme: "A Stochastic approximation method for inference in probabilistic graphical models 機械学習勉強会 2010/05/20 森井正覚."— Presentation transcript:

1 A Stochastic approximation method for inference in probabilistic graphical models
機械学習勉強会 2010/05/20 森井正覚

2 紹介する論文 A Stochastic approximation method for inference in probabilistic graphical models (P. Carbonetto, M. King, F. Hamze NIPS 2009)

3 概要 確率モデルの推論の新たな枠組み． 近似分布は扱い易いクラスに限定されない．
逐次モンテカルロ法とみなすこともできるが，人工的な分布の列を設計する必要がない． LDAの推論と関連がある集団遺伝学の推定問題で実験した．

4 目次 導入 潜在的ディリクレ配分法 アルゴリズムの説明 集団遺伝学への応用 まとめ

5 確率モデルの近似推論法 MCMCによるモンテカルロ推定 重点サンプリングによるモンテカルロ推定 変分推論法
解析的に”良い”性質を持っている近似分布族を見つける． いい近似分布を見つけるため，KL情報量を最適化する． 最もいい近似分布が，真の分布より大きくずれるかもしれない．

6 提案手法 扱い易い近似分布のクラスを制限しない変分推論法を提案する．

7 提案手法の特徴 KL情報量の勾配が直接計算できないため最適化するのが難しい．
勾配をモンテカルロ推定し，それを逐次モンテカルロ法により更新する． タイトルが確率推論の確率的近似法 勾配降下のステップ幅が大きいと，縮退してしまうので，それを防ぐ仕組みを導入．

8 目次 導入 潜在的ディリクレ配分法 アルゴリズムの説明 集団遺伝学への応用 まとめ

9 2 潜在的ディリクレ配分法(Latent Dirichlet allocation)
文書集合の生成モデル 文書 d ∈ {1,…,D} 単語 wdi ∈ {1,…,W} トピック zdi ∈{1,…,K} トピック集合で k 番目のトピックで，語彙集合で j 番目の単語が現れる確率は βkj． τdk ≡ p(zdi = k | τd)

10 潜在的ディリクレ配分法(Latent Dirichlet allocation)
観測データ w と未知の β,τ,z の確率は，

11 目次 導入 潜在的ディリクレ配分法 アルゴリズムの説明 集団遺伝学への応用 まとめ

12 重点サンプリング 目標とする分布 p(x) について，φ(x) の期待値 を求めたい．
重点サンプリングは．提案分布 q(x) と重要度重み w(x) = p(x)/ q(x) を用いると，モンテカルロ推定量は， 提案分布をうまく設計しないと，大きな誤差が生じてしまう．

13 3. アルゴリズムの説明 p(x) を p^(x;θ) で置き換えたモンテカルロ推定をする．
この推定量は偏りがあるが，変分問題を解くことにより，偏りを最小化する． 確率的近似ステップと逐次モンテカルロステップを反復する． p^(x;θk) → p(x) a.s. なら，モンテカルロ推定量は目標の期待値にほとんど確実に収束する．

14 アルゴリズムの概要 Draw samples from initial density p^(x;θ1).
3.1 Draw samples from initial density p^(x;θ1). for k = 2, 3, 4, . . . 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. SMC step: update samples and importance weights to reflect new density p^(x;θk). 3.2 3.3 3.5 3.4

15 3.1 The family of approximating distributions
θでパラメータ化された近似分布族 p^(x;θ) を作る． 以下の条件を満たす近似分布族を考える． p^(x;θ1) からサンプリングできるような θ1 が1つ以上存在する． p^(x;θ*) = p(x) となるような θ* が存在する． 以下で表される指数型分布族である． +. 常に p^(xA|xB;θ) と p^(xB|xA;θ) からサンプリングできるように，x を2つの集合に分割できる．

16 3.1 The family of approximating distributions
LDAでは，以下の近似分布族を用いた． mkj は，j 番目の単語が k 番目のトピックに割り当てられた数． ndk は，k 番目のトピックが d 番目の文書に割り当てられた数． cj は j 番目の単語が観測された数． 自然母数 θ = {η^, φ, γ} ≧ 0. φ = 1,γ = 0, η^ = η とすると p(x) が復元できる．

17 3.2 The variational objective
p(x) =p^(x;θ*) と p^(x;θ) の KL情報量は， ∇F(θ) にある積分を計算するが難しい． 標本 x(s) と重要度重み w(s) から，モンテカルロ推定をする．

18 3.3 Stochastic approximation
“平均して”前進することが求められる． 次式で探索方向を更新する． Bk は準ニュートン法(BFGS)で用いられるヘッセ行列を減衰(?)した行列，gk は ∇F(θk-1) のモンテカルロ推定量． θ≧0 の条件があるため，確率内点法を用いる． ステップ後，標本は新しい分布 を反映するよう更新する．

19 3.4 Sequential Monte Carlo
最初のステップでは，標本 x1(s) は， q1(x) =p^(x;θ1) からサンプリングする． kステップ後の提案分布は， p~k(x1:k) をうまく選べば，重要度重みは， 重要度重みを以下のように更新する．

20 3.5 Safeguarding the variance
ステップ幅が大きいと，縮退してしまうので，次の尺度を用いてステップ幅を抑える． 保護ステップ幅 αk は次式を解いて得る． Δθk は反復kにおける探索方向． Sk(θk) の微分は線形時間で計算できる． ESS(有効サンプルサイズ) も用いる．

21

22 目次 導入 潜在的ディリクレ配分法 アルゴリズムの説明 集団遺伝学への応用 まとめ

23 4 集団遺伝学への応用 LDAと同じPrichardらのモデル 右図のような過程 を考える． 個体 60 遺伝子 30 個体群 4 LDA
　 を考える． 個体 60 遺伝子 30 個体群 4 LDA population structure 文書 個体 単語 遺伝子 トピック 個体群

24 実験の目標 次の2つの統計量を復元することが目標 d と d’ の admixture distance admixture level
2つの個体の祖先の非類似度 0・・・個人の遺伝子が1つの集団から来ている． 1・・・祖先が K の集団に等しく分けられている．

25 実験手法 以下の3つの手法を比較する． 2つのデータセットに対し，K を 2～6まで． 各手法は独立な試行を 20 回行った．
Stochastic approximation (SA) ・・・提案手法 MCMC Annealed importance sample (AIS) 2つのデータセットに対し，K を 2～6まで． 各手法は独立な試行を 20 回行った． 公平のためサンプリング事象の数は同じに． MCMC・・・50000のマルコフ連鎖，10000のburn-in． SMC・・・100粒子，反復数500回．

26 admixture distance と admixture level の推定
　　　　　　　　　　　の推定値からの最も大きい差をプロット． Stochastic approximation は，ほぼすべての場合で最も良い．

27 結果の分析 突然変異率 1/2,K = 4 と 突然変異率 2,K=3 の場合でシミュレーション結果を詳しく見てみる．
平均行列(60次正方行列，集団ごとに整列) 黒い要素は共通の祖先を持つことを意味し，白い要素は共通の祖先を持たないことを意味する． 標準偏差行列 要素が黒いほど，分散が大きいことを意味する．(結果が疑わしい．)

28 admixture distance の平均と分散(突然変異率1/2,K=4)

29 admixture distance の平均と分散(突然変異率1/2,K=4)
MCMC 試行1では，集団を正しく4つに区別した． 試行2では，集団3と集団4を区別するのに失敗し，集団2もおかしい． AIS MCMCと似た振る舞いをした． Stochastic approximation 集団3と集団4を区別するのに失敗した． 結果に一致性がある．

30 admixture distance の平均と分散(突然変異率2,K=3)

31 admixture distance の平均と分散(突然変異率2,K=3)
MCMC 試行1はとても正確だった． 試行2では，集団1と集団2を区別するのに失敗し，集団3と集団4を正しく割り当てるのに失敗した． Stochastic approximation いくつか不一致なところがあるが，結果にばらつきがあるMCMCとは違い，結果に一致性がある．

32 目次 導入 潜在的ディリクレ配分法 アルゴリズムの説明 集団遺伝学への応用 まとめ

33 5 まとめ 変分推論，モンテカルロ法と確率的近似法に基づく新しい確率推論手法を提案した． 確率推論の問題で一致性と信頼性のある結果を得た．
提案手法の成功は，変分近似の選び方にかかっている． LDA以外のモデルに対してはまだよく分からない． 反復数に敏感であることを改善したい．