続・わかりやすいパターン認識ひとり読書会 5 - 渡邊哲司（Satoshi Watanabe）の日記

今回は保留になっていたものの一つ、事前確率P(s)の妥当性について考えます。

続パタ読書会 1:ディリクレ過程混合モデル
 続パタ読書会 2:ディリクレ過程混合モデルのアルゴリズム
 続パタ読書会 3:実験
 続パタ読書会 4:実装
続パタ読書会 5:事前確率P(s)の妥当性 1
続パタ読書会 6:事前確率P(s)の妥当性 2
続パタ読書会 7:ベル数 1
続パタ読書会 8:ベル数 2
続パタ読書会 9:P(s_k|x_k, s_-k, θ)の導出
 続パタ読書会 10:演習問題12.5の計算
 続パタ読書会 11:演習問題12.6の計算 1
続パタ読書会 12:演習問題12.6の計算 2

今回は保留になっていたものの一つ、何故 $\boldsymbol{s}$ の事前確率 $P(\boldsymbol{s})$ を

$P(\boldsymbol{s})=P(s_1, \ldots , s_n)=P_E(n_1, \ldots , n_c)=\displaystyle\frac{\alpha^c\displaystyle\prod_{i=1}^{c}{(n_i-1)!}}{\text{AF}(\alpha, n)}$

と定めるのが妥当なのか、また集中度パラメータαの意味は何なのかについて考えます。長いため読書会5と6に分けて記述します。

事前確率 $P(\boldsymbol{s})$ の妥当性 1

$P(\boldsymbol{s})$ は $n$ 個の観測パターン $\boldsymbol{x}=\{x_1, \ldots , x_n\}$ が各々どのパターンに属するかを表す潜在変数 $\boldsymbol{s}=\{s_1, \ldots , s_n\}$ の事前確率です。つまりパターンを観測する前に $n$ 個のパターンを分割するとすればどのような分割がどのような確率で起こりうるかをモデル化したものです。妥当な事前分布 $P(\boldsymbol{s})$ を定めるためにはまず妥当な分割ルールを定めなくてはいけません。結果としてディリクレ過程を分割の確率モデルとして使用しますが、その実現例の一つにCRPがあります。

CRP

CRP（Chinese Restaurant Process）は中華料理店過程と呼ばれるもので、テーブルが無限にある中華料理店に客が一人ずつ来店し以下のルールに従ってテーブルに着席する過程のことを指します。

最初の客は任意のテーブルに着席する
$n(\geq 2)$ 番目以降の客はすでに $n_i(\geq0)$ 人着席しているテーブル $i$ に確率 $\displaystyle\frac{n_i}{\alpha+n-1}$ で、誰も着席していないテーブルに確率 $\displaystyle\frac{\alpha}{\alpha+n-1}$ で着席する

CRPでの各テーブルは各クラスタに対応し、 $n$ 人の客は $n$ このパターンに対応しています。この分割ルールがディリクレ過程の実現例であることの説明は別途行うとして、ここではこのルールの下6人の来客があったケースを考えます。まず $1, 2, 2, 1, 1, 3$ の順で着席する確率を考えると

$\begin{eqnarray} P(1, 2, 2, 1, 1, 3) &=& \displaystyle\frac{\alpha}{\alpha}\cdot\frac{\alpha}{\alpha+1}\cdot\frac{1}{\alpha+2}\cdot\frac{1}{\alpha+3}\cdot\frac{2}{\alpha+4}\cdot\frac{\alpha}{\alpha+5}\\ &=& \displaystyle\frac{\alpha^3\cdot 2!}{\text{AF}(\alpha, 6)} \end{eqnarray}$

また $1, 1, 2, 1, 2, 3$ の順で着席する確率を考えると

$\begin{eqnarray} P(1, 1, 2, 1, 2, 3) &=& \displaystyle\frac{\alpha}{\alpha}\cdot\frac{1}{\alpha+1}\cdot\frac{\alpha}{\alpha+2}\cdot\frac{2}{\alpha+3}\cdot\frac{1}{\alpha+4}\cdot\frac{\alpha}{\alpha+5}\\ &=& \displaystyle\frac{\alpha^3\cdot 2!}{\text{AF}(\alpha, 6)} \end{eqnarray}$

となり結果は変わりません。つまり6人の客を3人、2人、1人のテーブルに分割する確率は来店の順にかかわらず

$P_E(3, 2, 1)=\displaystyle\frac{\alpha^3\cdot(3-1)!\cdot(2-1)!\cdot(1-1)!}{\text{AF}(\alpha, 6)}=\displaystyle\frac{\alpha^3\cdot 2!}{\text{AF}(\alpha, 6)}$

となります。つまりCRPによる分割の確率は

テーブルがいくつあるか
各テーブルに何人ずつ着席しているか

のみに依存しており、来客の順番やテーブルの種類には依存しません。クラスタリングとして考えると

いくつのクラスタが存在するか
各クラスタに所属するパターンはいくつあるか

のみに依存し、パターンがクラスタに割り当てられる順序やどのクラスタに割り当てられているかに依存しないことを意味します。これを $n$ 人の客が $c$ 個のテーブルに各々 $n_1, \ldots , n_c$ 人着席した場合に一般化すると

$P_E(n_1, \ldots, n_c)=\displaystyle\frac{\alpha^c\displaystyle\prod_{i=1}^{c}{(n_i-1)!}}{\text{AF}(\alpha, n)}$

となり、これがディリクレ過程に基づく $\boldsymbol{s}$ の事前確率に他なりません。結果として初めの式

$P(\boldsymbol{s})=P(s_1, \ldots , s_n)=P_E(n_1, \ldots , n_c)=\displaystyle\frac{\alpha^c\displaystyle\prod_{i=1}^{c}{(n_i-1)!}}{\text{AF}(\alpha, n)}$

はCRPを妥当な分割ルールであるとするならば妥当な式であると言えます。CRP自体が妥当な分割ルールであることはこれがディリクレ過程の実現例であることによって示されます。

ディリクレ過程の定義

CRPによる分割ルールがディリクレ過程の実現例である事を示すため、まずはディリクレ過程の定義から始めます。これはテキスト通りの定義ですのでテキスト持っている方はすっ飛ばしてください。

ディリクレ過程の定義 1

集合 $\Phi$ とその部分集合を要素とする集合族 $\mathcal{F}$ からなる可測空間 $(\Phi, \mathcal{F})$ の基底分布を $G_0$ 、集中度パラメータを $\alpha(\geq0)$ とする。確率測度 $G$ が $\Phi$ のいかなる可測な排他的分割

$\displaystyle\bigcup_{i=1}^{c}{A_i}=\Phi\quad\land\quad A_i\cap A_j=\phi(i\neq j)$

に対しても $r$ 次元確率ベクトル $(G(A_1), \ldots , G(A_r))$ がディリクレ分布 $\text{Dir}(\alpha G_0(A_1), \ldots , \alpha G_0(A_r))$ に従うときすなわち

$(G(A_1), \ldots , G(A_r))\sim\text{Dir}(\alpha G_0(A_1), \ldots , \alpha G_0(A_r))$

のとき、その時に限り $G$ はディリクレ過程に従うといい

$G\sim\text{DP}(\alpha, G_0)$

と記す。ただし $G_0(A_i)$ は $G_0$ から生成された $\theta$ が区間 $A_i$ に所属する確率

$G_0(A_i)=\displaystyle\int_{A_i}{G_0(\theta)d\theta}$

を意味する。

ディリクレ過程の定義を多少かみ砕いた形に変えるために以下の定義を導入します。

$\begin{eqnarray} \alpha_i &=& \alpha G_0(A_i)\\ \boldsymbol{g} &=& (g_1, \ldots , g_r) &=& (G(A_1), \ldots , G(A_r)) \end{eqnarray}$

この定義において

$\begin{eqnarray} \displaystyle\sum_{i=1}^{r}{G_0(A_i)} &=& 1\\ \displaystyle\sum_{i=1}^{r}{G(A_i)} &=& 1 \end{eqnarray}$

であることを考えると

$\begin{eqnarray} \displaystyle\sum_{i=1}^{r}{\alpha_i} &=& \alpha\\ \displaystyle\sum_{i=1}^{r}{g_i} &=& 1 \end{eqnarray}$

が成り立つことに注意します。この定義の下ディリクレ過程の定義は次のように書き換えられます。

ディリクレ過程の定義 2

$\displaystyle\sum_{i=1}^{r}{G_0(A_i)}=1,\quad\displaystyle\sum_{i=1}^{r}{\alpha_i}=\alpha$

の下で確率ベクトル $\boldsymbol{g}=(G(A_1), \ldots , G(A_r))$ が分割数及び分割の仕方にかかわらず

$p(\boldsymbol{g})=\text{Dir}(\alpha_1, \ldots , \alpha_r)$

を満たすとき、このような確率分布 $G(\theta)$ を生成する確率過程をディリクレ過程といい

$G(\theta)\sim\text{DP}(\alpha, G_0(\theta))$

と記す。

CRPによる分割ルールがディリクレ過程の実現例であることの確認

ディリクレ過程において生成された $G$ において $\theta$ がどのように生成されるかを考えます。 $\theta^1, \ldots , \theta^{n-1}$ を $G(\theta)$ から独立に生成された系列とすると、 $\theta^n$ の事後分布は

$P(\theta^n\vert\theta^1, \ldots , \theta^{n-1})=\displaystyle\frac{\alpha}{\alpha+n-1}G_0(\theta^n)+\displaystyle\sum_{i=1}^{c}{\displaystyle\frac{n_i}{\alpha+n-1}\cdot{}^\delta\theta_i}$

となります。この式の導出は後ほど行います。ここで $\theta_i$ はクラスタを表しており、 $\theta_i\neq\theta_j\quad(i\neq j)$ です。また ${}^\delta\theta_i$ は $\theta=\theta_i$ に位置する大きさ $1$ の点を表し、 $n_i$ はクラスタ $\theta_i$ に所属する $\theta^k$ の数、つまり $\theta_i=\theta^k$ となる $\theta^k$ の数です。 $\displaystyle\sum_{i=1}^{c}{n_i}=n-1$ が成り立つことに注意します。この式をクラスタリングの過程として考えれば $\theta^1, \ldots , \theta^{n-1}$ の観測の下 $\alpha:n-1$ の比で新規クラスタ、もしくは既存のクラスタに確率的に割り当てていることになります。つまり

$\begin{eqnarray} \theta^n\leftarrow \begin{cases} \displaystyle\frac{n_i}{\alpha+n-1}&&\text{の確率で}\theta_i\\ \displaystyle\frac{\alpha}{\alpha+n-1}&&\text{の確率で}G_0(\theta)\text{から生成される新しい}\theta_{new} \end{cases} \end{eqnarray}$

といった割り当て方です。これはCRPでの分割ルールと等価であり、よってCRPがディリクレ過程の実現例であることが確認できました。

ディリクレ過程の共役性

CRPがディリクレ過程の実現例であることは確認できましたが、ディリクレ過程で生成される $G(\theta)$ がどのような分布か、また先の $P(\theta^n\vert\theta^1, \ldots , \theta^{n-1})$ をどのように求めるかは保留されています。ですのでそれを知るためにまずディリクレ過程の共役性について考えます。初めに $\theta^1, \ldots , \theta^{n-1}$ を $G(\theta)$ から独立に生成された系列としたとき、これらを観測した後の $\boldsymbol{g}=(G(A_1), \ldots , G(A_r))$ の事後分布 $p(\boldsymbol{g}\vert\theta^1, \ldots , \theta^{n-1})$ を求めます。

$\begin{eqnarray} p(\boldsymbol{g}\vert\theta^1, \ldots , \theta^{n-1}) &\propto& p(\theta^1, \ldots , \theta^{n-1}\vert\boldsymbol{g})p(\boldsymbol{g})\\ &=&p(\boldsymbol{g})\displaystyle\prod_{i=1}^{r}{p(\{\theta^k\vert\theta^k\in A_i\}\vert\boldsymbol{g})} \end{eqnarray}$

ここで区間 $A_i$ 内に位置する $\theta^k$ の総数を $m_i$ とすると

$\begin{eqnarray} p(\boldsymbol{g})\displaystyle\prod_{i=1}^{r}{p(\{\theta^k\vert\theta^k\in A_i\}\vert\boldsymbol{g})} &=& p(\boldsymbol{g})\displaystyle\prod_{i=1}^{r}\prod_{\theta^k\in A_i}{G(A_i)}\\ &=& p(\boldsymbol{g})\displaystyle\prod_{i=1}^{r}\prod_{\theta^k\in A_i}{g_i}\\ &=& p(\boldsymbol{g})\displaystyle\prod_{i=1}^{r}{g_i^{m_i}}\\ &=& \text{Dir}(\alpha_1, \ldots , \alpha_r)\displaystyle\prod_{i=1}^{r}{g_i^{m_i}}\\ &=& \displaystyle\frac{\Gamma(\alpha)}{\displaystyle\prod_{i=1}^{r}{\Gamma(\alpha_i)}}\displaystyle\prod_{i=1}^{r}{g_i^{\alpha_i-1}}\displaystyle\prod_{i=1}^{r}{g_i^{m_i}}\\ &\propto& \displaystyle\prod_{i=1}^{r}{g_i^{\alpha_i+m_i-1}}\\ \end{eqnarray}$

と計算できるので結局

$p(\boldsymbol{g}\vert\theta^1, \ldots , \theta^{n-1}) \propto \displaystyle\prod_{i=1}^{r}{g_i^{\alpha_i+m_i-1}}$

となります。右辺はディリクレ分布型ですので正規化項を計算するまでもなく

$\begin{eqnarray} p(\boldsymbol{g}\vert\theta^1, \ldots , \theta^{n-1}) &=& \text{Dir}(\alpha_1+m_1, \ldots , \alpha_r+m_r)\\ &=& \text{Dir}(\alpha_1', \ldots , \alpha_r') \end{eqnarray}$

となります。ここで $\alpha_i'=\alpha_i+m_i$ としています。また、 ${}^\delta\theta^k$ を $\theta^k$ に位置する大きさ1の点とすると

$\displaystyle\sum_{\theta^k\in A_i}{{}^\delta\theta^k}=m_i$

なのでパラメータ $\alpha_i'$ は以下のように書き換えることが出来ます。

$\begin{eqnarray} \alpha_i' &=& \alpha_i+m_i\\ &=& \alpha_i+\displaystyle\sum_{\theta^k\in A_i}{{}^\delta\theta^k}\\ &=& \displaystyle\frac{\alpha+n-1}{\alpha+n-1}\cdot\left(\alpha_i+\displaystyle\sum_{\theta^k\in A_i}{{}^\delta\theta^k}\right)\\ &=& (\alpha+n-1)\cdot\displaystyle\frac{1}{\alpha+n-1}\left(\alpha G_0(A_i)+\displaystyle\sum_{\theta^k\in A_i}{{}^\delta\theta^k}\right) \end{eqnarray}$

ここで

$\begin{eqnarray} \alpha' &=& \alpha+n-1\\ G_0'(A_i) &=& \displaystyle\frac{1}{\alpha+n-1}\left(\alpha G_0(A_i)+\displaystyle\sum_{\theta^k\in A_i}{{}^\delta\theta^k}\right) \end{eqnarray}$

と置くと

$\alpha_i'=\alpha'G_0'(A_i)$

とあらわせます。さらに

$\begin{eqnarray} \displaystyle\sum_{i=1}^{r}{G_0'(A_i)} &=& \displaystyle\frac{1}{\alpha+n-1}\left(\alpha\displaystyle\sum_{i=1}^{r}{G_0(A_i)}+\displaystyle\sum_{k=1}^{n-1}{{}^\delta\theta^k}\right)\\ &=& \displaystyle\frac{1}{\alpha+n-1}(\alpha+n-1)\\ &=& 1 \end{eqnarray}$
$\displaystyle\sum_{i=1}^{r}{\alpha_i'}=\displaystyle\sum_{i=1}^{r}{(\alpha_i+m_i)}=\alpha+n-1=\alpha'$

の二つが言えます。この結果から $G(\theta)$ から $\theta^1, \ldots , \theta^{n-1}$ を生成した下での事後分布 $G(\theta)\vert\theta^1, \ldots ,\theta^{n-1}$ においても下記のように「ディリクレ過程の定義 2」を満たすことを示すことが出来ます。