CRPのテーブルの数の分布

  • ????????????????????

Chinese Restaurant Process (→ 以前の記事) でデータ数(レストランに来る人数/壺からボールを取り出す回数)や \(\alpha\) が変化した時に利用されるテーブルの数の分布がどうなるか実験してみた(下の図をクリックで拡大)。


  • 一見、ポアソン分布っぽいが、どれも平均>分散となっていて underdispersion ぎみ。
  • \(\alpha\) が小さいとテーブルの数は少なく、大きくなるにつれてテーブルの数の平均、分散は増加する
  • レストランを訪れる人数(図ではdata size)が増加するとやはりテーブルの数の平均、分散は増加する。しかし増加の仕方はゆっくり(平均、分散ともに理論値がわかる。増加の仕方は漸近的に対数 → 記事の一番下の補足)。
  • 【わかること】CRPを事前分布として使うときは、潜在クラスタの数の事前分布をこの分布のように仮定していることになる。data size は与えられたデータの数なので変更不可。\(\alpha\) を使って事前知識をモデル化するが、1パラメータなので平均と分散の両方を独立に制御することはできない。実際、データ数10000で\(\alpha=3\)とすると、潜在クラス数が5個以下の可能性をほとんど排除していることになる(右下の図)

実験に使ったR的なスクリプト。

#--------------------------------------------------
# CRP で確保されるテーブルの数の分布に関する実験

CRP_probs <- function(size,alpha){
  alpha/((1:size)-1+alpha)
} # Polyaの壺的な確率を返す

rCRP_numLatentClass <- function(n, size, alpha=1){
  probs <- CRP_probs(size,alpha)
  sapply(1:n,function(i) sum(runif(size) < probs))
}  # テーブルの数をサンプリングするだけならこれだけでOK

numLC_theoretical <- function(size,alpha){
  pp <- CRP_probs(size,alpha)
  list(mean=signif(sum(pp),3),var=signif(sum(pp*(1-pp)),3))
}  # テーブルの数の平均、分散の理論値を返す



#--- Main ---

library(MASS)
par(mfrow=c(3,3))
xlab <- "Number of tables allocated in CRP"
for(alpha in c(0.5,1,3)){
  for(datasize in 10^(2:4)){
    # テーブル数のシミュレーション10000回
    num.table.simulated <- rCRP_numLatentClass(10000,datasize,alpha)
    # 理論的な平均、分散を計算
    theo <- numLC_theoretical(datasize,alpha)

    # プロット
    truehist(num.table.simulated,xlim=c(0,40),ylim=c(0,0.3),h=1,xlab=xlab)
    text(20,0.3,paste("data size =",datasize,"/ alpha =",alpha),cex=2)
    text(30,0.27,paste("mean =",theo$mean,"/ sdv =",signif(sqrt(theo$var),3)),cex=1.2)
  }
}

補足、というか疑問

よく、テーブル数の平均値は漸近的に \(\alpha\log n/\alpha\) になる、みたいなことが書いてあるけど、級数を使えば厳密計算可能なのでここではそちらを採用している。
\begin{align*}
E[\text{# of tables}]=\sum_{i=1}^n\frac{\alpha}{\alpha-1+i} \sim \alpha\log n/\alpha\qquad (n\to\infty)
\end{align*}
という漸近挙動。同様に分散も厳密計算可能。
\begin{align*}
V[\text{# of tables}] = \sum_{i=1}^n\frac{\alpha}{\alpha-1+i}\bigg(1-\frac{\alpha}{\alpha-1+i}\bigg) \sim ??\qquad (n\to\infty)
\end{align*}
この右辺がどうなるかわからない。数値的には対数的な挙動になることをチェック済み。なんとなく、てきとうな定数に対して \(C+\alpha\log n/\alpha\) になりそうな気がするが。

はてなブックマーク - CRPのテーブルの数の分布
Pocket