DPMから学ぶノンパラベイズの思想

はじめまして。そろそろ何かしら情報を発信していく必要性を感じたため、主に研究関連で、まとまったことがあれば記事にしていくことにしました。どれだけ更新出来るかは謎ですが。今回は、ノンパラベイズの基本をディリクレ過程を中心にまとめます。

機械学習におけるノンパラベイズは、出て来てから10年以上経っていることもあり、大分一般的な話題になってる気がしますが、例えばブログできちんと分かりやすく説明したものってほとんどないように思います。僕がそもそも研究系のブログをあまりチェックしないというのもあるかもしれないですが、、、。個人的には去年の夏頃からの卒論で、Tehや持橋さんなどの論文を泣きながら読みつつ理解出来なかったので、その時の気持ちを思い出しながら書いてみたいと思います。例えばディリクレ過程（以下DP）を理解しようとして論文など読むと、DPはCRPと等価であるとか、SBPと等価であるとか書いてあって、そもそもDPって何？という状態になるんですよね（僕だけ？）。そんな人の疑問を払拭出来たらなと。個人的な理解も含まれるので、間違っている箇所があったら申し訳ないです。ちなみに、全くディリクレ過程を知らないという人は他の人の記事や持橋さんのスライド[1]などを見るといいかもしれません。またベイズについてPRML1章程度の知識は前提とします。ノンパラとは、（パラメタの個数=モデルの複雑さ）に制限をかけないという意味です。

ノンパラメトリック ベイズ

ノンパラベイズの応用範囲は多岐に渡るため、ここでは最も基本的かつ（思想的に）重要なディリクレ過程混合モデル（DPM）に焦点を当てます。DPMを用いる主な動機は、混合モデルによるクラスタリングにおいて、コンポーネント数kをデータから自動的に決めたい、というものです。例えば2次元データを混合正規分布に従ってクラスタリングしようとした場合、従来kはモデルのパラメタとして与えられるとしていました。kが問題になる場合、モデル選択（周辺尤度の最大化や、交差検証）に基づきモデルの複雑さ=kを決定します。この問題を、kが観測データに応じて自動的に調整されるようなモデルを置くことで、つまりkの推定自体をモデルに組み込むことで自然に解決しよう、というのが、ノンパラベイズの基本的な発想になります。

モデルの設計

さてこのような前提のもと、どうしてDPが出現するのか、DPとは何なのか、について説明します。上で述べたモデルの生成過程は、次のように書けます。
$\90dpi x_i \sim F(\theta_i)$
$\90dpi \theta_i \sim G$
ここで、 $\90dpi F(\theta_i)$ は各コンポーネントの分布で、例えば正規分布。 $\90dpi \theta_i$ がそのパラメタに相当します。我々が推定したいのは、 $\90dpi \theta_i$ が従う分布Gです。これは各 $\90dpi \theta_i$ を要素として持つような離散分布です。従来のパラメトリックな手法では、このGを、各データがどのクラスタから発生するかを規定するインディケータに関する多項分布と、そのクラスタの実際のパラメタに関する分布によって表現します。ベイズの枠組みでは、インディケータである多項分布に対する事前分布としてディリクレ分布を置いて推定したりします。この場合、ディリクレ分布の事後分布を推定出来れば、多項分布のパラメタが分布の形で得られます。*1。ノンパラベイズではこの考えをより一般化します。つまり、クラスタ数kを決めた上で何らかの事前分布（例えばディリクレ分布）を設計するのではなく、kがいくつになるか、まで含めた確率モデルというものを考えます。具体的には以下のCRPでkの個数まで含めた分布を考えることが出来ます。

Chinese Restaurant Process (CRP)

CRPは以下のような生成過程です。

レストランに無限のテーブルが存在し、客が一人ずつ入店する
新しく来た客は、他の客が多くいるテーブルに座りやすい（客が多い = そのテーブルの料理はおいしいのだろうと推測する）
客は、誰も座っていない新しいテーブルに座ることも出来る。この場合、そのテーブルに新しい料理が運ばれる。１つのテーブルにはそれぞれ１つの料理のみが対応する。

CRPは割と総称的な言葉で、具体的なモデルによってバリエーションがありますが、共通部分を抜き出すと上のようになります。よくある図ですが、イメージは下のような感じです。これはレストランに５人の客が座っていて、次の客がどこに座るかを表す図です。それぞれのテーブルに、そのテーブルに座っている客の数に比例する確率で座りますが、CRPのパラメタである $\90dpi \alpha$ に比例する確率で、新しいテーブルに座ります。

これをデータの生成過程と考えます。つまり、新たな客がテーブルに座る毎に、それに対応する料理がデータとして生成され、観測されるというモデルを考えます。このとき重要なのは、CRPが交換可能（exchangeable）な過程であるという点です。交換可能というのは、系列データ $\90dpi x_1, x_2, \cdots, x_n$ に関して、その順序を入れ替えた列 $\90dpi x_{\sigma(1)}, x_{\sigma(2)}, \cdots, x_{\sigma(n)}$ を考えると、この２つの列の生成確率が等しいことをいいます。例えば $\90dpi x_1, \cdots, x_n = 1 2 1 3$ という列が得られたとして、この順序を変えた列 $\90dpi x_1, \cdots, x_n = 3 2 1 1$ というものを考えても、その同時確率は変わりません。これはCRPを実際にシミュレートして計算してみるとすぐに分かると思います。実際、同時確率を式で表せば証明出来ます。
ここで、レストランの客を実際に観測される各データとすると、同じテーブルに座っている客を、同じクラスタに属するデータと考えることが出来ます。つまり１つのテーブルが１つのクラスタに相当し、そこに座っている客が、そのクラスタに属するデータ、とするわけです。そして、各テーブルに対応する料理は、そのクラスタに対応する正規分布のパラメタ（平均分散）に対応付けます。このように考えると、上で述べたような、データに応じてクラスタ数が自動的に増加するようなモデルの生成過程を定義出来たことになります。ここで問題なのは、CRPは逐次的な生成過程であるということです。つまり、１つ１つのデータがそれまで生成されたデータ（に対応する客がどのテーブルに座ったか）に応じて、生成されるというモデルです。我々が推定したいのは、混合モデルの混合比、及び各コンポーネントのパラメタを定める１つの離散分布が何かしら存在し、その分布に応じてコンポーネントが選択され、各データが生成される、というモデルです。イメージは以下のような感じです。

実はこのモデルをBayes推定した結果とCRPとが一致するという結論になるのですが、これを理解するには、数学的な定理としてde Finettiの表現定理というものを用います。これは以下のようなものです。
ある系列 $\90dpi x_1,\cdots,x_n$ が交換可能な性質を持つとする。このとき、この結果はあるパラメタのもとでの独立同分布な試行の結果として表現することが出来る。そのパラメタを積分消去した確率と、交換可能な生成過程で生成されたとする同時確率は等しくなる。
$\90dpi p(x_1,\cdots,x_n) = \int p(\theta) \prod_{i=1}^{n} p(x_i | \theta) d\theta$
結論をいうと、この $\90dpi p(\theta)$ がディリクレ過程と呼ばれるものです。これは数学的な結果なのですが、上の定理において、パラメタである $\90dpi \theta$ は分布（測度）に置き換えることが可能です。これを明示的に $\90dpi \theta$ の代わりにGを用いて書くと
$\90dpi p(x_1,\cdots, x_n) = \int p(G) \prod_{i=1}^{n} p(x_i | G) dG$
となります。上で説明したようにCRPの生成列は交換可能なので、この $\90dpi x_1,\cdots ,x_n$ をCRPで生成されるデータとおけます。さて右辺ですが、まずこのGの１つは具体的な離散分布を定めます。データはGから独立同分布に得られ、それをp(G)のもとで平均をとるという式です。これはまさに、離散分布Gに対する事前分布p(G)を考え、そのもとでGを周辺化（積分消去）するというベイズの予測の式です。ベイズ的には、データを発生させた真の分布（パラメトリックな問題では分布のパラメタ）を１つ決めるのでなく、その分布が従う分布を求めます。その上で、新たなデータに関する予測としては、データを発生させたとする分布を、積分消去したものが欲しいわけです（つまりp(G)自体は必ずしも必要ではない）。このp(G)が、ディリクレ過程と呼ばれるものです。そしてp(G)からのサンプルが、いわゆる加算無限次元の離散分布といわれるものです。要するに、我々は本当は上の式の右辺を計算したかったが、p(G)をどのように設計すればいいのかよく分からない。代わりにCRPが交換可能であることを用いて、CRPから左辺で計算する、ということが出来るのです。さらに推定の際には、Gibbs samplingで交換可能であることが本質的に重要になります。この辺の詳細は他の論文などに譲ります。代表的なのは[2]など。

周辺の話題

またDPの説明の際Polya Urn表現というのも出てきますが、これはCRPと全く同じです。Stick Breaking Process（SBP）についてもよく出てきますが、上では説明しませんでした。これはSBPがなくてもDPについて説明出来るからです。一応解説すると、SBPはDPから具体的な１つのサンプル分布Gを得る方法です。つまり、SBPから具体的なGが構成出来ますが、このサンプルを取りまくれば、p(G)が原理的に得られるというわけです。推定の際は、CRPを基にすると、交換可能性からGibbs samplingを用い、SBPを基にすると変分ベイズを用いて推定出来ます。

まとめ

要するに解釈の仕方なのですが、歴史的な経緯はどうであれ、DPが機械学習のどういう要請で出現したのかが重要なのだと思います。繰り返しになりますが、DPは混合モデルにおける混合数を実質無限まで拡大出来るようにしたい、という要請から生まれたものです。でも実際どんな分布を置けばそれを表現出来るかというと難しい、、、。代わりにde Finettiの定理を足がかりに、無限個まで要素を増やせる生成モデルを考えてみればいいのでは？となります。それが交換可能な系列を生成するのであれば、de Finettiの定理から、そのような分布の存在を暗に証明することが出来るのです。
以上の解釈でノンパラベイズを捉えると、理解しやすいと思うのですがどうでしょうか。例えば、Dirichlet Diffusion Tree（DDT）[3]というのがあるのですが、これはDPMを一般化したモデルです。DPMの各クラスタが、それぞれ独立ではなく階層的な構造を持っているとするモデルで、ノンパラモデルの一種です。これに関しても、データの背後に、階層モデルを生成する１つの真の木構造があると仮定します。そしてベイズ推定で、その木を積分消去したものを考えるのですが、これは、データを階層的に生成するCRPのような交換可能な生成過程を考えることで、上の議論と全く同様に、真の木構造を暗に仮定したモデルを考えることが出来ます。DPの場合は一応SBPによって具体的なサンプルを直接得ることが可能ですが、このような複雑なモデルになると直接具体的なモデルのサンプルを構成することは困難です（存在を暗に仮定するだけ）。DDTに関しては今年のICMLでGhahramaniらが推定を高速化したらしく、今個人的にチェックしてます[4]。

参考資料

[1]Nonparametric Bayes for Non-Bayesians, 持橋大地 [IBIS2008] pdf
[2]Markov Chain Sampling Methods for Dirichlet Process Mixture Models, Neal, R.M. [2000] pdf
[3]Density Modeling and Clustering Using Dirichlet Diffusion Trees, Neal, R.M. [2003] pdf
[4]Message Passing Algorithms for Dirichlet Diffusion Trees, Knowles, D.A. et al. [ICML 2011] pdf

*1:この辺りは専門外なのですが、このように混合正規分布をベイズ推定する話はあまり見ないので一般的ではないのかもしれません。言語処理的には、オリジナルのLDAが混合モデルの混合数（トピック数）を決めた上でベイズ推定する代表でしょうか。しっくりこない人は適当に読み替えながら進んでください。