ノンパラベイズのあれこれ

自分用メモ。超基礎的なこと。書くのが躊躇されるレベルだが、書かないと忘れる。全部は書かない、自分が必要なところだけ。

ディリクレ過程(Dirichlet Process; DP)を使ったようなモデルを自分で実装する必要が出てきた。今までは必要でなければ必ずしもDP使う必要ないじゃんという感じでいたが、今回はDPが本質的に必要な場面のような気がするので、頑張る。基本的には上田さん、山田さんの資料を見ながら話を進めていく。

やりたいこと(というか初期ステップ)。超単純。コーパス全体を一つの文書と見なす&bag of wordsの状態で単語をクラスタリングする(クラスタ数は∞)。LDAの拡張っぽくdocumentごとにtopic propotionが...ということをやろうかと思っていたのだが、それをちゃんとやろうとするとHierarchical Dirichlet Processesをまじめにやらないといけない。今回は超初歩ステップをやりたいので、文書の区切りというものは忘れることにする。そうすると普通にDPを使ってクラスタリングするだけになるので話が簡単。

Gibbs Sampling

ちょっと分からなくなったのはGibbs Samplingのところで基底測度(Base Measure) G_0(\theta)は一体何にすればいいねん、というところ。結論としては普通にディリクレ分布でよい。が、ちょっとちゃんと書く。Gibbsのサンプリングの式はLDA gibbsのときと同じ要領でposteriorをpriorとlikelihoodに分解してやればよい。
p(z_i = k | \mathbf{z}_{-i}, x_i, \mathbf{x}_{-i}) \propto p(z_i = k | \mathbf{z}_{-i}) p(x_i | z_i = k, \mathbf{z}_{-i}, \mathbf{x}_{-i})

第一項

第一項は中華料理店過程(Chinese Restaurant Process; CRP)をまんま使えばよろしいので、kが既存のクラスタidの時は
p(z_i = k | \mathbf{z}_{-i}) = \frac{m_{-i, k}}{n - 1 + \gamma}
で、kが新しいクラスタに振られるときは
p(z_i = k | \mathbf{z}_{-i}) = \frac{\gamma}{n - 1 + \gamma}
となる。ここで、\gammaはCRPのパラメータで客がどれだけ新しいtableに座りやすいかを表わしたものである(小さいとできるクラスタ数は少なく、大きいとクラスタ数もでかくなっていく)。

第二項

問題*1p(x_i | z_i = k, \mathbf{z}_{-i}, \mathbf{x}_{-i})の項。ベイズな枠組みで考えているので、これはパラメータ\theta_kについて積分消去した式であることに注意したい。kが既存のクラスタである場合、その積分消去の式は
p(x_i | z_i = k, \mathbf{z}_{-i}, \mathbf{x}_{-i}) = \int p(x_i | z_i = k, \theta_k) p(\theta_k | \mathbf{z}_{-i}, \mathbf{x}_{-i}) d \theta_k
となる。この積分の式は「多項分布とディリクレ分布の共役性」+「ディリクレ分布の期待値の性質」の2つを使えば\frac{n_{-i, j}^{x_i} + \beta}{n_{-i, j}^{\cdot} + W \beta}と瞬時に分かる*2。ここで、ハイパーパラメータ\betaが追加されてしまったことはちょっと覚えておく。

次にkが新しいクラスタだった場合について考える。この場合、\theta_kは今まで生成されていないわけなので、基底測度から生成してあげると考えると
p(x_i | z_i = k, \mathbf{z}_{-i}, \mathbf{x}_{-i}) = \int p(x_i | z_i = k, \theta_k) G_0(\theta_k) d \theta_k
となる。テキストのほうにはこれは積分できるように基底測度を共役なもので置けば問題ない、と書いてある。現在は単語のクラスタリングについて考えているので、p(x_i | z_i = k, \theta_k)は多項分布、G_0(\theta_k)はディリクレ分布となる...え?基底測度は単純にディリクレとかでいいんだろうか...と小一時間悩むがこれしかないっぽい。なので、ディリクレ分布\mbox{Dir}(\alpha)のパラメータをどういう風におけばいいか考えないといけないが、特に前提知識があるわけでもないので、\mbox{Dir}(\frac{1}{W})と置くのが自然である。そうすると
p(x_i | z_i = k, \mathbf{z}_{-i}, \mathbf{x}_{-i}) = \int p(x_i | z_i = k, \theta_k) G_0(\theta_k) d \theta_k = \int \theta_{k, x_i} \mbox{Dir}(\frac{1}{W}) d \theta_k = \frac{1}{W}
となってなんか超簡単になってしまった...。そして、一様なので実際にサンプリングのプログラムを書くときにはここの項なくてもいいという。

まとめ

Gibbs Samplingの式のところをまとめてみると、kが既存のクラスタの場合は
p(z_i = k | \mathbf{z}_{-i}, x_i, \mathbf{x}_{-i}) = \frac{m_{-i, k}}{n - 1 + \gamma} \cdot \frac{n_{-i, k}^{x_i} + \beta}{n_{-i, k}^{\cdot} + W \beta}
となり、kが新しいクラスタの場合は
p(z_i = k | \mathbf{z}_{-i}, x_i, \mathbf{x}_{-i}) = \frac{\gamma}{n - 1 + \gamma} \cdot \frac{1}{W}
となって、超簡単である。一個注意しておくべき点としては、グラフィカルモデル上では\gammaG_0(\theta)がハイパーパラメータのようなものだったが、GibbsのときにはG_0(\theta)が具体的なディリクレ分布となるので、ハイパーパラメータは\gamma\betaの2種類になる。

実装上の工夫はちょっと必要で、上の式を使ってGibbsでずっとsamplingしていくとクラスタ数がどんどん増えまくっていってしまう。なので、実装するときにはお客さんがいないクラスタは消去するということをやっておかないとひどいことになるので注意。この辺はNeubigさんのチュートリアルにも書いてあったなぁと今頃思い出した...。

*1:後から見ると問題でもないのだが、最初は問題だった

*2:分からない人はGibbs Sampling in the Generative Model of Latent Dirichlet Allocationで勉強してください