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

Slides:



Advertisements
Similar presentations
1 小暮研究会2 第1章ベイジアンアルゴリズ ム 2値選択 ベルヌーイ試行 尤度原理 同一性 交換可能性 尤度についてのまとめ 環境情報学部3年 渡邊洋一.
Advertisements

5 章 標本と統計量の分布 湯浅 直弘. 5-1 母集団と標本 ■ 母集合 今までは確率的なこと これからは,確率や割合がわかっていないとき に, 推定することが目標. 個体:実験や観測を行う 1 つの対象 母集団:個体全部の集合  ・有限な場合:有限母集合 → 1つの箱に入っているねじ.  ・無限な場合:無限母集合.
『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
土木計画学 第3回:10月19日 調査データの統計処理と分析2 担当:榊原 弘之. 標本調査において,母集団の平均や分散などを直接知ることは できない. 母集団の平均値(母平均) 母集団の分散(母分散) 母集団中のある値の比率(母比率) p Sample 標本平均 標本分散(不偏分散) 標本中の比率.
1 徹底討論「主成分分析 vs 因子分析」 主成分分析は因子分析ではない ! 狩野裕 (大阪大学) 日本行動計量学会第 30 回大会 於:多摩大学.
Determining Optical Flow. はじめに オプティカルフローとは画像内の明る さのパターンの動きの見かけの速さの 分布 オプティカルフローは物体の動きの よって変化するため、オプティカルフ ローより速度に関する情報を得ること ができる.
看護学部 中澤 港 統計学第5回 看護学部 中澤 港
確率・統計Ⅰ 第12回 統計学の基礎1 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
遺伝的アルゴリズム  新川 大貴.
統計的仮説検定 基本的な考え方 母集団における母数(母平均、母比率)に関する仮説の真偽を、得られた標本統計量を用いて判定すること。
Pattern Recognition and Machine Learning 1.5 決定理論
Bassモデルにおける 最尤法を用いたパラメータ推定
統計的仮説検定の考え方 (1)母集団におけるパラメータに仮説を設定する → 帰無仮説 (2)仮説を前提とした時の、標本統計量の分布を考える
疫学概論 母集団と標本集団 Lesson 10. 標本抽出 §A. 母集団と標本集団 S.Harano,MD,PhD,MPH.
Effect sizeの計算方法 標準偏差が正確に求められるほど症例数が十分ないときは、測定しえた症例の中で、最大値と最小値の値の差を4で割り算した値を代用することが出来る。この場合には正規分布に従うことを仮定することになる。
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
Bias2 - Variance - Noise 分解
Bias2 - Variance - Noise 分解
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
雑音重み推定と音声 GMMを用いた雑音除去
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
クラスター変分法と確率的情報処理 --Belief Propagation と画像処理アルゴリズム--
計測工学 -測定の誤差と精度2- 計測工学 2009年5月17日 Ⅰ限目.
ベイズ基準によるHSMM音声合成の評価 ◎橋本佳,南角吉彦,徳田恵一 (名工大).
Probabilistic Latent Semantic Visualization: Topic Model for Visualizing Documents Tomoharu Iwata, Takeshi Yamada ,Naonori CS研 ,KDD /6.
【小暮研究会2】 「ベイズのアルゴリズム」:序章 【1,2:計量経済分析と統計分析】 【 3:ベイズ定理】
第3章 補足:パラメータが極小値に収束する例
母集団と標本:基本概念 母集団パラメーターと標本統計量 標本比率の標本分布
高次元データの解析 -平均ベクトルに関する検定統計量の 漸近分布に対する共分散構造の影響-
協調機械システム論 ( ,本郷) 協調機械システム論 東京大学 人工物工学研究センター 淺間 一.
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
正規分布における ベーテ近似の解析解と数値解 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
決定木とランダムフォレスト 和田 俊和.
第9章 混合モデルとEM 修士2年 北川直樹.
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
確率論の基礎 「ロジスティクス工学」 第3章 鞭効果 第4章 確率的在庫モデル 補助資料
第14章 モデルの結合 修士2年 山川佳洋.
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
第3章 統計的推定 (その1) 統計学 2006年度.
第5章 特徴の評価とベイズ誤り確率 5.5 ベイズ誤り確率の推定法 [1] 誤識別率の偏りと分散 [2] ベイズ誤り確率の上限および下限
第6章 特徴空間の変換 6.1 特徴選択と特徴空間の変換 6.2 特徴量の正規化 平成15年5月23日(金) 発表者 藤井 丈明
訓練データとテストデータが 異なる分布に従う場合の学習
遺伝的アルゴリズムを用いた 構造物の最適形状探索の プログラムの作成
ゲノム科学概論 ~ゲノム科学における統計学の役割~ (遺伝統計学)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
ベイズ・アプローチによる グラフィカル・テスト理論
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
第4章 識別部の設計 4-5 識別部の最適化 発表日:2003年5月16日 発表者:時田 陽一
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
第3章 線形回帰モデル 修士1年 山田 孝太郎.
「アルゴリズムとプログラム」 結果を統計的に正しく判断 三学期 第7回 袖高の生徒ってどうよ調査(3)
ベイズ最適化 Bayesian Optimization BO
Data Clustering: A Review
情報経済システム論:第13回 担当教員 黒田敏史 2019/5/7 情報経済システム論.
経営学研究科 M1年 学籍番号 speedster
HMM音声合成における 変分ベイズ法に基づく線形回帰
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
人工知能特論II 第8回 二宮 崇.
ベイズ音声合成における 事前分布とモデル構造の話者間共有
JNNS-DEX-SMI-玉川 公開講座 「交換モンテカルロ法とその応用」
ポッツスピン型隠れ変数による画像領域分割
ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
表紙 分散遺伝的アルゴリズムのための 新しい交叉法.
1ーQー18 音声特徴量抽出のための音素部分空間統合法の検討
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年8月1日 3.2 競合学習
第3章 統計的推定 (その2) 統計学 2006年度 <修正・補足版>.
ガウシアングラフィカルモデルにおける一般化された確率伝搬法
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

アルゴリズムの概要 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

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つの集合に分割できる.

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

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

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

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

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

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

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

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

実験手法 以下の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回.

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

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

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

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

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

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

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

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