Nonparametric Bayes for Non-Bayesians
IBIS 2008 企画セッション「ノンパラメトリックベイズ」
持橋大地
NTT コミュニケーション科学基礎研究所
daichi@cslab.kecl.ntt.co.jp
2008-10-29 (木)仙台

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.1/19

チュートリアル• ノンパラメトリックベイズって何?
• 混合モデルとディリクレ過程混合モデル• 階層ディリクレ過程• ノンパラメトリックベイズのポイント:… Stick-breaking process (SBP)• Infinite Tree, Indian Buffet, The Mondrian Process, · · ·• ノンパラメトリックベイズと測度論• まとめ

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.2/19

ノンパラメトリックベイズとは• モデルをデータの複雑さに応じて増やす生成モデル◦ クラスタリング (クラスタ)◦ グラフマイニング (木, グラフ)
◦ 自然言語処理 (カテゴリ, 単語)• 理論的に可算無限個まで増やせる◦ “Infinite Models” とも呼ばれている◦ 実際には, n 個のデータに対して O(log n) 前後− データの複雑さによって変わる

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.3/19

ノンパラメトリックベイズとは• モデルをデータの複雑さに応じて増やす生成モデル◦ クラスタリング (クラスタ)◦ グラフマイニング (木, グラフ)
◦ 自然言語処理 (カテゴリ, 単語)• 理論的に可算無限個まで増やせる◦ “Infinite Models” とも呼ばれている◦ 実際には, n 個のデータに対して O(log n) 前後− データの複雑さによって変わる• 注:「ノンパラメトリック」◦ パラメータがないという意味ではない◦ 少数パラメータの連続分布の推測ではない, という意味

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.3/19簡単な例: 混合モデル• データ x は確率分布 1 · · · K のどれかから生成• EM アルゴリズム: x が 1 · · · K のどの分布から生成されたか?

p(k|x) ∝ p(x|k) p(k)(k = 1 · · · K)

(1)

を計算する
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.4/19

混合モデルの推定 (2): 問題• 問題: 外れ値の場合はどうするか?
◦ K が有限の場合, p(k|x) が比較的大きいものに無理矢理割り当てる⇓• p(K +1|x) (新しいクラスタ) を考えた方がいいのでは?
◦ p(K +1|x) ∝ p(x|K +1) p(K +1) に従って, 新しいクラスタに帰属させる
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.5/19

混合モデルの推定 (3)• ちょっと待った: 新しいクラスタは, K +1, K +2, K +3, · · · と無限にあるのでは?
◦ EM で p(K+1|x), p(K+2|x), .. を全部持っておくのは無理⇓• MCMC 法で, 確率的にランダムにクラスタ番号を決めよう◦ “現在のクラスタ数の最大値 +1” まで考えればよい

1: for n = 1 · · · N do
2:
for k = 1 · · · K + 1 do
3:p(k|xn ) ∝ p(xn |k) p(k)end for4:5:zn ∼ p(·|xn )if zn = K + 1 then6:
7:
K =K+18:
end if
9: end for
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.6/19

ディリクレ過程混合モデル (DPM)• 今のアルゴリズムを行うためには, p(k) (k = 1, 2, · · · , ∞)が必要⇓• GEM 分布, Stick-breaking process (SBP)wk ∼ Be (1, α) (k = 1 · · · ∞)k−1
p(k) = wk
(1 − wi )

(2)
(3)

i=1

↓

◦ 幾何分布Geo(k) = λ (1−λ)k−1(4)のソフト化.

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.7/19

Stick-breaking process: 事前分布→事後分布• Stick-breaking prior:

wk ∼ Be(1, α), p(k) = wk

k−1(1−wi )

(5)i=1

◦ 事前分布は最初は指数減衰→データによって変化− 「事前分布の事前分布」

事前分布 (の事前分布)
データ

事後分布

wk ∼ Be (1, α)(6)⇓wk ∼ Be (1+#(k で止まったデータ数),α+#(k より右のデータ数))(7)

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.8/19

振り返ってみると有限混合モデル:→∼ Dir(α)

DPM:→∼ DP(α, G0 )• ディリクレ過程とは…「元」となる分布 (基底測度) に似た,無限離散分布を生成するモデル→ データをフィッティングする◦ データが多く複雑なほど, より多くの「クラスタ」が現れる
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.9/19

HDP (Hierarchical Dirichlet Process) (Teh+ 2004)• DP の基底測度を, 親 DP から引いた無限離散分布にする⇓• ある離散分布に似た, 多数のランダムな離散分布◦ 「ある混合比に似た, 多数のランダムな混合比」◦ 技術的には: {Gn } の中で, アトムが共有される− H から直接 {Gn } を引くと, ⊥ の立っている位置が共有されない
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.10/19

HDP の応用• HDP-LDA : 無限トピックの潜在意味モデル◦ 混合モデルの混合モデル
潜在トピックの Prior
潜在トピック分布

トピック別
単語出現分布p(w|k)

テキストp(w|η, H) =

 N ∞n=1 k=1p(wn |k) G[k] dG
• 実装には Gibbs sampling を用いる

(8)

無限離散分布の第 k 要素

◦ http://www.gatsby.ucl.ac.uk/˜ywteh/research/npbayes/npbayes-r21.tgz
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.11/19

The Trinity of Nonparametric Bayes• ノンパラメトリックベイズの本質 (機械学習として)… Stick-Breaking Process (SBP)
ノンパラメトリックベイズ法• Stick-Breaking Process の拡張
wk ∼ Be(1, α)(9)◦ Be(1, α) でなくともよい− Be(1−α, β +kα) · · · Pitman-Yor
process (Pitman and Yor 1997)− Be(α, β) · · · Beta two-parameter
process (Ishwaran and Zarepour 2000)
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.12/19

Infinite Stochastic Tree
• 木の各ノードに, w ∼ Be(α, β)がある• 木の各 Branch が, 一つの SBP◦ SBP の構造化
◦ 深いノードほど, 到達しにくい(木が「薄い」)• 有限のデータでの近似◦ The Infinite Markov Model :Gibbs◦ NTR (Neutral-To-Right)
process と関係が深いらしい◦ 一般のグラフにも同様の無限化を考えることができそう

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.13/19

The Mondrian Process (Roy and Teh, NIPS 2008 to appear)⇐⇒

Mondrian Process

Mondrian (3D)

IRM

• Infinite Relational Model の最先端…確率的階層分割◦ Poisson process の階層化
◦ Blockmodel → IRM (Kemp+ 2006) → Annotated Hierarchy(Roy+ 2006) → Mondrian• 再帰的な定義
MP(λ, µ, Θ) ≡λ = λ − E, E ∼ Exp(μ(Θ)), · · ·˙ ¸
<d x

>d x
return λ , d, x, MP(λ , µ, Θ), MP(λ , µ, Θ)Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.14/19

その他の新しい話題• The Infinite Hidden Markov Model (Beal+ 2002)◦ HMM の隠れ状態数が推測できる (!)◦ HDP を使って, 可算無限個の隠れ状態を生成− 動的計画法も提案された (ICML2008)− HDP-PCFG もこの一種• Indian Buffet Process (Griffiths and Ghahramani 2005)= Beta Process (Hjort 1990)◦ 複数の隠れ素性を持つ無限マトリクスの生成モデル◦ 階層化と HBP (Thibaux+ 2007…難解)◦ 時系列化: The Infinite Factorial HMM (NIPS 2008 to appear)
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.15/19

ノンパラメトリックベイズと測度論• ノンパラメトリックベイズの学習に測度論は必要か?

→ 必要.
◦ 全く基礎知識がないと, 研究のレベルが大きく制限される◦ ただし, 全部知る必要は (とりあえず) ない◦ 知らなくても, DPM+α 程度の実装は可能• お薦め書籍:“Measure, Integral and Probability”
Capinski and Kopp, Springer 2004.
(Springer Undergraduate Mathematicsseries)
ISBN 1852337818◦ 〜p70 くらいまで読めばよい◦ a.e. や M を見ても固まらなくて済む!

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.16/19

まとめ• ノンパラメトリックベイズ…モデルを動的に増やす生成モデル◦ 複雑なデータほど, 複雑なモデル◦ クラスタリングに限らず, 木やグラフへも拡張可能• DP, HDP, HPY, IBP, HBP, Mondrian, …
◦ 確率論として見ても深いモデル◦ 測度論の初歩は, 適切な本を使えば難しくない◦ NPBayes stat だけで, ご飯 20 杯くらい食べられる(ex. Newton Institute 2007, “Construction and Propertiesof Bayesian Nonparametric Regression Models”
http://www.newton.ac.uk/programmes/BNR/bnrw01p.html• 機械学習における多くの応用◦ 自然言語処理, バイオインフォマティクス◦ クラスタリング, データマイニング, ネットワーク分析◦ 画像処理, 音声処理, 音楽情報処理, …
Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.17/19

注意• ノンパラベイズに, 汎用の「パッケージ」はない◦ 一応存在するが, 理論がわかっていないと使えない◦ ベイズ哲学…データを注意深く観察してモデル化する◦ 相手に応じて自分の振舞いを変える (動的: N. Wiener)• どんな入力に対しても, 一定の性能を保障するミニマックス最適化 (静的: v. Neumann)◦ 入力分布を仮定しないので, パッケージ化できる(例: SVM)
◦ ただし, ノンパラベイズのような柔軟性は難しい

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.18/19

参考文献 (チュートリアル類)• NIPS 2005, Michael Jordan

http://www.cs.berkeley.edu/˜jordan/nips-tutorial05.ps• UAI 2005, Zoubin Ghahramani

http://learning.eng.cam.ac.uk/zoubin/talks/uai05tutorial-b.pdf• MLSS 2007, Yee Whye Teh

http://www.gatsby.ucl.ac.uk/˜ywteh/research/npbayes/mlss2007.pdf• 日本語:◦ 上田&山田, 「応用数理」2007◦ 佐藤, 中川研機械学習勉強会 2007
◦ 栗原, MIRU 2008

Nonparametric Bayes for Non-Bayesians (IBIS 2008) – p.19/19