🍖

ディリクレ分布から中華料理店過程の分割ルールを導出する

8 min read
\gdef\ds{\displaystyle} \gdef\b#1{\mathbf{#1}} \gdef\bs#1{\boldsymbol{#1}}

まえがき

ディリクレ分布から中華料理店仮定(CRP)の分割ルールを導出します。CRPの詳細は参考にさせて頂いた『続・わかりやすい パターン認識 -教師なし学習入門-』を参照してください。

前準備

  • サンプルの数をnとします。
  • クラスタの数をc(ただしn << c)とし、各クラスタを\omega_j \; (j = 1, \ldots, c)で表現します。
  • 各サンプルへのクラスタの割り当てをs_kとして表現します。s_kは1つのクラスタのみに属するとします。
  • s_k\omega_iが割り当てられる確率を\pi_iとします。\sum_{j = 1}^c \pi_j = 1です。
  • \bs{\pi} = \left[\pi_1, \ldots, \pi_c \right]^\top, \bs{\alpha} = \left[\alpha_1, \ldots, \alpha_c \right]^\topという表記を用います。
  • \bs{\pi}の確率分布として、以下のようにディリクレ分布を仮定します。
p(\bs{\pi}) = \mathrm{Dir} ( \bs{\pi} | \bs{\alpha} ) = \frac{\Gamma\left(\sum_{j = 1}^c \alpha_j \right)}{\prod_{j = 1}^c \Gamma (\alpha_j)} \prod_{j = 1}^c \pi_j^{\alpha_j - 1}
  • \bs{\pi}が与えられたとき、s_kはカテゴリ分布に従うと考えられます。
p(s_k = \omega_i | \bs{\pi}) = \mathrm{Cat} (s_k = \omega_i | \bs{\pi}) = \pi_i

導出

事前に、今回想定しているグラフィカルモデルを示します。\bs{\alpha}から\bs{\pi}が確率的に生成され、\bs{\pi}からs_1, \ldots, s_nが生成されるという構造になっています。

graphical-model
想定するグラフィカルモデル

CRPの分割ルールを導出するため、s_1, \ldots, s_{n - 1}が与えられたとき、s_nがあるクラスタ\omega_iに割り当てられる確率p(s_n = \omega_i | s_1, \ldots, s_{n - 1})を求めます。\bs{\alpha}は与えられていますが、\bs{\pi}は未知です。ここで、1つのパラメータ\alphaを用いて各クラスタの\alpha_j = \alpha / cとして、全て等しいとします。このとき、p(\bs{\pi})

p(\bs{\pi}) = \mathrm{Dir} ( \bs{\pi} | \alpha ) = \frac{\Gamma(\alpha)}{\Gamma (\alpha / c)^c} \prod_{j = 1}^c \pi_j^{\alpha / c - 1}

となっています。s_1, \ldots, s_{n - 1}の中で\omega_jに割り当てられた個数をn_jとすると、

p(s_1, \ldots, s_{n - 1} | \bs{\pi}) = \prod_{k = 1}^{n - 1} p(s_k | \bs{\pi}) = \prod_{j = 1}^c \pi_j^{n_j}

です。これを用いてp(s_n = \omega_i | s_1, \ldots, s_{n - 1})を求めます。

\begin{aligned} p(s_n = \omega_i | s_1, \ldots, s_{n - 1}) = \frac{p(s_n = \omega_i, s_1, \ldots, s_{n - 1})}{p(s_1, \ldots, s_{n - 1})} \end{aligned}

計算が煩雑になるため、まずは分母p(s_1, \ldots, s_{n - 1})を求めます。\bs{\pi}についての周辺化を考慮することで

\begin{aligned} & p(s_1, \ldots, s_{n - 1}) \\ &= \int p(s_1, \ldots, s_{n - 1}, \bs{\pi}) d \bs{\pi} = \int p(s_1, \ldots, s_{n - 1} | \bs{\pi}) p(\bs{\pi}) d \bs{\pi} \\ &= \int \left\{ \prod_{j = 1}^c \pi_j^{n_j} \right\} \frac{\Gamma(\alpha)}{\Gamma(\alpha / c)^c} \prod_{j = 1}^c \pi_j^{\alpha / c - 1} d \bs{\pi} = \int \frac{\Gamma(\alpha)}{\Gamma(\alpha / c)^c} \prod_{j = 1}^c \pi_{j}^{n_j + \alpha / c - 1} d \bs{\pi} \\ &= \frac{\Gamma(\alpha)}{\Gamma(\alpha / c)^c} \frac{\prod_{j = 1}^c \Gamma(n_j + \alpha / c)}{\Gamma(\sum_{j = 1}^c (n_j + \alpha / c))} \quad \left(\because \mathrm{補足を参照してください} \right) \\ &= \frac{\Gamma(\alpha)}{\Gamma(\alpha / c)^c} \frac{\prod_{j = 1}^c \Gamma(n_j + \alpha / c)}{\Gamma(n - 1 + \alpha)} \quad \left(\because \sum_{j = 1}^c n_j = n - 1, \sum_{j = 1}^c \alpha / c = \alpha \right) \\ &= \frac{\Gamma(\alpha)}{\Gamma(n - 1 + \alpha)} \prod_{j = 1}^c \frac{\Gamma(n_j + \alpha / c)}{\Gamma(\alpha / c)} \end{aligned}

が得られます。分子p(s_n = \omega_i, s_1, \ldots, s_{n - 1})ではs_1, \ldots, s_{n - 1}に加えてs_n = \omega_iとなる確率を求めることになります。これは分母p(s_1, \ldots, s_{n - 1})を求めるときと同様の手順によって式変形を行うことにより、

\begin{aligned} & p(s_n = \omega_i, s_1, \ldots, s_{n - 1}) \\ &= \int p(s_n = \omega_i, s_1, \ldots, s_{n - 1}, \bs{\pi}) d \bs{\pi} = \int p(s_n = \omega_i, s_1, \ldots, s_{n - 1} | \bs{\pi}) p(\bs{\pi}) d \bs{\pi} \\ &= \int p(s_n = \omega_i | \bs{\pi}) \left\{ \prod_{k = 1}^{n - 1} p(s_k | \bs{\pi}) \right\} p(\bs{\pi}) d \bs{\pi} \\ &= \frac{\Gamma(\alpha)}{\Gamma(n + \alpha)} \frac{\Gamma(n_i + 1 + \alpha / c)}{\Gamma(\alpha / c)} \left\{ \prod_{\substack{j = 1 \\ j \neq i}} \frac{\Gamma(n_j + \alpha / c)}{\Gamma(\alpha / c)} \right\} \end{aligned}

となります。したがって、求めたいp(s_n = \omega_i | s_1, \ldots, s_{n - 1})

\begin{aligned} & p(s_n = \omega_i | s_1, \ldots, s_{n - 1}) \\ &= \frac{p(s_n = \omega_i, s_1, \ldots, s_{n - 1})}{p(s_1, \ldots, s_{n - 1})} \\ &= \frac{\Gamma(\alpha)}{\Gamma(n + \alpha)} \frac{\Gamma(n_i + 1 + \alpha / c)}{\Gamma(\alpha / c)} \left\{ \prod_{\substack{j = 1 \\ j \neq i}} \frac{\Gamma(n_j + \alpha / c)}{\Gamma(\alpha / c)} \right\} \cdot \frac{\Gamma(n - 1 + \alpha)}{\Gamma(\alpha)} \prod_{j = 1}^c \frac{\Gamma(\alpha / c)}{\Gamma(n_j + \alpha / c)} \\ &= \frac{\bcancel{\Gamma(\alpha)}}{\Gamma(n + \alpha)} \frac{\Gamma(n_i + 1 + \alpha / c)}{\bcancel{\Gamma(\alpha / c)}} \left\{ \prod_{\substack{j = 1 \\ j \neq i}} \frac{\Gamma(n_j + \alpha / c)}{\bcancel{\Gamma(\alpha / c)}} \right\} \cdot \frac{\Gamma(n - 1 + \alpha)}{\bcancel{\Gamma(\alpha)}} \prod_{j = 1}^c \frac{\bcancel{\Gamma(\alpha / c)}}{\Gamma(n_j + \alpha / c)} \\ &= \frac{\Gamma(n - 1 + \alpha)}{\Gamma(n + \alpha)} \frac{\Gamma(n_i + 1 + \alpha / c)}{\Gamma(n_i + \alpha / c)} \\ &= \frac{1}{n - 1 + \alpha} \cdot (n_i + \alpha / c) = \frac{n_i + \alpha / c}{n - 1 + \alpha} \end{aligned}

と計算することができます。

c個の全てのクラスタを含む集合を\Omegaとします。ここで、n << cと仮定していることから、n_i = 0、即ち1つも属するサンプルが存在しないクラスタが存在します。\Omegaを1つも属するサンプルが存在しないクラスタの集合\Omega_0 = \left\{\omega_i | n_i = 0, i = 1, \ldots, c \right\}およびそれ以外のクラスタの集合\Omega_1 = \left\{\omega_i | n_i \neq 0, i = 1, \ldots, c \right\}に分割します。つまり\Omega = \Omega_0 \cup \Omega_1, \emptyset = \Omega_0 \cap \Omega_1, c = |\Omega| = |\Omega_1| + |\Omega_2|です。
このとき、

\begin{aligned} & p(s_n \in \Omega_0 | s_1, \ldots, s_{n - 1}) = \sum_{\omega_i \in \Omega_0} p(s_n = \omega_i | s_1, \ldots, s_{n - 1}) = \sum_{\omega_i \in \Omega_0} \frac{n_i + \alpha / c}{n - 1 + \alpha} \\ &= \sum_{\omega_i \in \Omega_0} \frac{\alpha / c}{n - 1 + \alpha} = \frac{c - |\Omega_1|}{c} \frac{\alpha}{n - 1 + \alpha} \end{aligned}

であり、c \rightarrow \inftyの極限では

\begin{aligned} & p(s_n \in \Omega_0 | s_1, \ldots, s_{n - 1}) = \left(1 - \frac{|\Omega_1|}{c} \right) \frac{\alpha}{n - 1 + \alpha} \rightarrow \frac{\alpha}{n - 1 + \alpha} \quad (c \rightarrow \infty) \end{aligned}

です。一方、\Omega_1に属するクラスタに対しては

p(s_n = \omega_i \in \ \Omega_1 | s_1, \ldots, s_{n - 1}) = \frac{n_i + \alpha / c}{n - 1 + \alpha} \rightarrow \frac{n_i}{n - 1 + \alpha} \quad (c \rightarrow \infty)

です。以上の計算をまとめると

\begin{cases} \ds p(s_n \in \Omega_0 | s_1, \ldots, s_{n - 1}) = \frac{\alpha}{n - 1 + \alpha} \\ \\ \ds p(s_n = \omega_i \in \ \Omega_1 | s_1, \ldots, s_{n - 1}) = \frac{n_i}{n - 1 + \alpha} \end{cases}

となります。s_nn_i \neq 0の既存のクラスタ\omega_i \in \Omega_1のいずれかに属する確率とs_nn_i = 0の新規のクラスタ\omega_i \in \Omega_0に属する確率はn_i : \alphaの比になっています。したがって、これはCRPの分割ルールに対応していることが分かります。

補足

\int \prod_{j = 1}^c \pi_{j}^{n_j + \alpha / c - 1} d \bs{\pi} = \frac{\prod_{j = 1}^c \Gamma(n_j + \alpha / c)}{\Gamma(\sum_{j = 1}^c (n_j + \alpha / c))}

を示します。
\bs{\tilde{\alpha}} = \left[n_1 + \alpha / c, \ldots, n_c + \alpha / c \right]^\topとすると、\bs{\tilde{\alpha}}をパラメータとするディリクレ分布は

\mathrm{Dir} (\bs{\pi} | \bs{\tilde{\alpha}}) = \frac{\Gamma(\sum_{j = 1}^c (n_j + \alpha / c))}{\prod_{j = 1}^c \Gamma(n_j + \alpha / c)} \prod_{j = 1}^c \pi_{j}^{n_j + \alpha / c - 1}

と表せます。ディリクレ分布は確率分布なので、\bs{\pi}で積分すると1になります。

\begin{aligned} \int \mathrm{Dir} (\bs{\pi} | \bs{\tilde{\alpha}}) d \bs{\pi} &= \int \frac{\Gamma(\sum_{j = 1}^c (n_j + \alpha / c))}{\prod_{j = 1}^c \Gamma(n_j + \alpha / c)} \prod_{j = 1}^c \pi_{j}^{n_j + \alpha / c - 1} d \bs{\pi} \\ &= \frac{\Gamma(\sum_{j = 1}^c (n_j + \alpha / c))}{\prod_{j = 1}^c \Gamma(n_j + \alpha / c)} \int \prod_{j = 1}^c \pi_{j}^{n_j + \alpha / c - 1} d \bs{\pi} \\ &= 1 \end{aligned}

分数の中には\bs{\pi}を含んでいないため、積分の対象にはなっていません。よって、この結果から

\int \prod_{j = 1}^c \pi_{j}^{n_j + \alpha / c - 1} d \bs{\pi} = \frac{\prod_{j = 1}^c \Gamma(n_j + \alpha / c)}{\Gamma(\sum_{j = 1}^c (n_j + \alpha / c))}

が得られます。

参考文献

Discussion

ログインするとコメントできます