ディリクレ過程(中華料理店過程)のトピック数(テーブル数)の期待値を導出してみる #ぞくパタ

「続・わかりやすいパターン認識」(以降「ぞくパタ」)の11章「ノンパラメトリックベイズモデル」を読んでいる。


ぞくパタはこの11章・12章のための本、と言ったらさすがに言いすぎなのかもしれないけど、そのつもりで読んでる人はけっこう多そう。
ノンパラベイズをしたかったら英語の論文読むしかない状態だったのが、日本語で読めるようになったというだけでも十分価値があるわけだが、ディリクレ過程と、無限次元ディリクレ分布や中華料理店過程との関係などもきちんとフォローされているし、ディリクレ過程とはどのようなふるまいをするものなのか、あれこれ実験して示してもくれていて、これは力作だなあと頭が下がる。


といっても、そもそも題材が本質的に易しくないので、これほどていねいに解説されてあっても、さらっと読んだだけではまったく意味はわからない。紙と鉛筆無しで理解できたら、ウン千人かに一人の天才以上だろう。
読書会もまもなくノンパラベイズに突入するが、それなりの覚悟を持って予習するのがおすすめ。


とまあ前振りはこれくらいで。
ぞくパタ 11章の p227 にて

CRP(中華料理店過程)では、客に使用されているテーブル数は、来客数 n の増加とともに増大し、その使用テーブル数の期待値 E[c] は、理論的には E[c] = O(αlog n) となることが知られている。

とあった。
テーブル数(つまりトピック数)の期待値が分かれば、集中度 α を決める目安になるので、どうやって求めるのかちょっと興味を持って探してみたら、英語 wikipedia の Chinese Restaurant Process のページに載っていた。

(ぞくパタとは記号の使い方が異なるので注意)


が、式見た瞬間に導出方法がわかるくらい簡単なものだったので(答え見る前に自力でわかればよかったのだけどw)、せっかくだから紹介してみよう。


n 人の客が着席したときの、テーブル数を表す確率変数 c = c_n を考える。
また確率変数 X_k を「 k 人目の客が来たときに新しいテーブルに着いたら 1、すでに客のいるテーブルに着いたら 0 」(つまり k 人目の客のときのテーブル数の増分)とすると、 c は X_k の和に等しい。

  • c = \sum_{k=1}^n X_k


k 人目の客が新しいテーブルに着く確率は \frac{\alpha}{k-1+\alpha} なので、

  • E[X_k]=1\cdot\frac{\alpha}{k-1+\alpha}+0\cdot\frac{k-1}{k-1+\alpha}=\frac{\alpha}{k-1+\alpha}


ここで、確率変数の和の期待値は、期待値の和になる(独立でなくても成立するが、今回は独立なのでどっちでもいい)ので、

  • E[c] = \sum_{k=1}^n E[X_k] = \sum_{k=1}^n \frac{\alpha}{k-1+\alpha}


とわかる。
さらに digamma 関数Ψの特性 \Psi(z+1)=\Psi(z)+\frac1z を使えば E[c]=\alpha\{\Psi(\alpha+n)-\Psi(\alpha)\} と表せる。実装や見積もりではこちらが速くて便利だろう。
クラスタ数(トピック数)はわからないとはいっても目星くらいはあるだろうから、この期待値がその目安となる数字を少し超えるくらいにαを選ぶと良さそう。


あとは E[c] = O(αlog n) であることを大雑把に示してみる。
といっても \alpha\approx 1 として、さらに和を積分で近似してしまえばあっさり出る*1

  • E[c]=\sum_{k=1}^n \frac{\alpha}{k-1+\alpha}\approx \sum_{k=1}^n \frac{\alpha}{k} \approx \int_1^n \frac{\alpha}{k}dk = \alpha\log n


ちなみに、alpha = 1.0, n = 500 のとき(ぞくパタ 12章の実験の設定)、E[c] = 6.8 なのだが、αlog n = 6.2 とそれなりの近さ。
まあ元の式も十分簡単なので近似の意味はたいしてなさそうだけど、計算機を使わずに頭の中で目安を立てるくらいになら使えるかも。

*1:真面目にやるなら、ちゃんと上からおさえなきゃなんだろうけど、ごちゃごちゃするだけなのでネグる