SatoshiWatanabeの日記

続・わかりやすいパターン認識 ひとり読書会 8

今回はベル数の続きです。前回証明した包除原理からまずは第二種スターリング数を求め、その第二種スターリング数を用いてベル数を求めます。


続パタ読書会 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

ベル数 2

第二種スターリング数

第二種スターリング数はクラスタリングの言葉で言うと

  •  n個のパターンを区別のないちょうど k個のクラスタに分割する場合の数


を表す数で \text{S}(n, k)などとあらわします。この第二種スターリング数を求めるためにまず

  •  n個のパターンを区別のあるちょうど k個のクラスタに分割する場合の数


を求めます。これは n個のパターンが k個のクラスタのいずれかに属する場合の数から、いずれかのクラスタに誰も属さない場合の数をすべて引くことで求めることが出来ます。まず n個のパターンが k個のクラスタのいずれかに属する場合の数を考えると、各パターンは 1, \ldots, kクラスタのどれかに任意に割り当てることが出来るので k^nとなります。ではいずれかのクラスタに誰も属さない場合の数はどのように考えればよいでしょうか。これを考えるために各クラスタ 1, \dots, kにどのパターンも属さない場合を要素とする集合をそれぞれ A_1, \ldots, A_kとします。このそれぞれの集合の要素数 |A_1|, \ldots, |A_k|のようにあらわされ、いずれかのクラスタに誰も属さない場合の数は |A_1\cup\ldots\cup A_k|であらわすことが出来ます。ここで読書会7で証明した包除原理を用いると



    \begin{eqnarray}
        && |A_1\cup\ldots\cup A_k|\\
        &=& \displaystyle\sum_{i}{|A_i|}-\displaystyle\sum_{i\lt j}{|A_i\cap A_j|}+\displaystyle\sum_{i\lt j \lt l}{|A_i\cap A_j\cap A_l|}-\\
        && \cdots+(-1)^{n-1}|A_1\cap\cdots\cap A_k|
    \end{eqnarray}


が成り立ちます。では |A_i| |A_i\cap A_j|などはどのようにして求めればよいでしょうか。まずは |A_i|について考えます。 |A_i|クラスタ iに誰も属さない場合の数です。これは n個のパターンが iを除いた k-1個のクラスタのいずれかに属する場合の数のことですので前述と同じ考え方で (k-1)^nとなります。続いて |A_i\cap A_j|つまりクラスタ iにも jにも誰も属さない場合の数について同じように考えると (k-2)^nとなります。これらの考えを進めていくと、



    \begin{eqnarray}
        |A_i| &=& (k-1)^n\\
        |A_i\cap A_j| &=& (k-2)^n\\
        &\text{…}\\
        |A_1\cap\cdots\cap A_{i-1}\cap A_{i+1}\cap\cdots\cap A_k| &=& 1^n\\
        |A_1\cap\cdots\cap A_k| &=& 0^n
    \end{eqnarray}


となります。また、 A_1, \ldots, A_kから i個の集合を選ぶ組み合わせは {}_k\mathrm{C}_iですので結局包除原理の式は



    \begin{eqnarray}
        && |A_1\cup\ldots\cup A_k|\\
        &=& \displaystyle\sum_{i}{|A_i|}-\displaystyle\sum_{i\lt j}{|A_i\cap A_j|}+\displaystyle\sum_{i\lt j \lt l}{|A_i\cap A_j\cap A_l|}-\\
        && \cdots+(-1)^{n-1}|A_1\cap\cdots\cap A_k|\\
        &=& {}_k\mathrm{C}_1\cdot(k-1)^n-{}_k\mathrm{C}_2\cdot(k-2)^n+\cdots+(-1)^{k-2}{}_k\mathrm{C}_{k-1}\cdot1^n+(-1)^{k-1}{}_k\mathrm{C}_k\cdot 0^n\\
        &=& \displaystyle\sum_{i=1}^{k-1}{(-1)^{k-i-1}{}_k\mathrm{C}_{k-i}\cdot i^n}\\
        &=& \displaystyle\sum_{i=1}^{k-1}{(-1)^{k-i-1}{}_k\mathrm{C}_i\cdot i^n}
    \end{eqnarray}


となります。この |A_1\cup\ldots\cup A_k| n個のパターンが k個のクラスタのいずれかに属する場合の数 k^nから引けばよいので



    \begin{eqnarray}
        k^n-|A_1\cup\ldots\cup A_k| &=& k^n-\displaystyle\sum_{i=1}^{k-1}{(-1)^{k-i-1}{}_k\mathrm{C}_i\cdot i^n}\\
        &=& \displaystyle\sum_{i=1}^{k}{(-1)^{k-i}{}_k\mathrm{C}_i\cdot i^n}
    \end{eqnarray}


と結果が出ました。求めていたものを思い出すとこれは

  •  n個のパターンを区別のあるちょうど k個のクラスタに分割する場合の数


でしたので区別のない場合はここからクラスタの区別による重複分を削除することを考慮すればよいことになります。つまり k!で割ることになりますので第二種スターリング数は


 \text{S}(n, k)=\displaystyle\frac{1}{k!}\displaystyle\sum_{i=1}^{k}{(-1)^{k-i}{}_k\mathrm{C}_i\cdot i^n}


と求まります。

ベル数

ベル数は「n個のものを分割する方法の総数」のことを指します。このベル数を考えるにあたって

  •  n個のパターンを区別のない k個以下クラスタに分割する場合の数


を考えていきます。これを \text{B}(n, k)とあらわすこととします。第二種スターリング数は

  •  n個のパターンを区別のないちょうど kクラスタに分割する場合の数


でしたので



    \begin{eqnarray}
        \text{B}(n, k) &=& \text{S}(n, 1)+\text{S}(n, 2)+\cdots+\text{S}(n, k)\\
        &=& \displaystyle\sum_{j=1}^{k}{\text{S}(n, j)}\\
        &=& \displaystyle\sum_{j=1}^{k}{\displaystyle\frac{1}{j!}\displaystyle\sum_{i=1}^{j}{(-1)^{j-i}{}_j\mathrm{C}_i\cdot i^n}}
    \end{eqnarray}


と計算できます。ベル数 B_nは「n個のものを分割する方法の総数」つまり「 n個のパターンを区別のない n個以下のクラスタに分割する場合の数」 \text{B}(n, n)に他なりませんので結局



    \begin{eqnarray}
        B_n &=& \text{B}(n, n)\\
        &=& \displaystyle\sum_{j=1}^{n}{\displaystyle\frac{1}{j!}\displaystyle\sum_{i=1}^{j}{(-1)^{j-i}{}_j\mathrm{C}_i\cdot i^n}}
    \end{eqnarray}


と求まります。

具体的な値

ベル数を n=3の場合について計算していくと



    \begin{eqnarray}
        B_3 &=& \displaystyle\sum_{j=1}^{3}{\displaystyle\frac{1}{j!}\displaystyle\sum_{i=1}^{j}{(-1)^{j-i}{}_j\mathrm{C}_i\cdot i^3}}\\
        &=& \displaystyle\frac{1}{1!}\displaystyle\sum_{i=1}^{1}{(-1)^{1-i}{}_1\mathrm{C}_i\cdot i^3}+\displaystyle\frac{1}{2!}\displaystyle\sum_{i=1}^{2}{(-1)^{2-i}{}_2\mathrm{C}_i\cdot i^3}+\displaystyle\frac{1}{3!}\displaystyle\sum_{i=1}^{3}{(-1)^{3-i}{}_3\mathrm{C}_i\cdot i^3}\\
        &=& 1\cdot({}_1\mathrm{C}_1\cdot 1^3)+\displaystyle\frac{1}{2}({}_2\mathrm{C}_2\cdot 2^3-{}_2\mathrm{C}_1\cdot 1^3)+\displaystyle\frac{1}{6}({}_3\mathrm{C}_3\cdot 3^3-{}_3\mathrm{C}_2\cdot 2^3+{}_3\mathrm{C}_1\cdot 1^3)\\
        &=& 1\cdot 1+\displaystyle\frac{1}{2}(8-2)+\displaystyle\frac{1}{6}(27-24+3)\\
        &=& 1+3+1\\
        &=& 5
    \end{eqnarray}


と考察の初めに計算した値と一致します。そのほかの値についてベル数を計算していくと



    \begin{eqnarray}
        B_1 &=& 1\\
        B_2 &=& 2\\
        B_3 &=& 5\\
        B_4 &=& 15\\
        B_5 &=& 52\\
        B_6 &=& 203\\
        B_7 &=& 877\\
        B_8 &=& 4140\\
        B_9 &=& 21147\\
        B_{10} &=& 115975\\
        B_{20} &=& 51724158235372\\
        B_{30} &=& 846749014511809332450147\\
        B_{40} &=& 157450588391204931289324344702531067\\
        B_{50} &=& 185724268771078270438257767181908917499221852770\\
        B_{60} &=& 976939307467007552986994066961675455550246347757474482558637\\
        B_{70} &=& 18075003898340511237556784424498369141305841234468097908227\\
        && 993035088029195\\
        B_{80} &=& 991267988808424794443839434655920239360814764000951599022939\\
        && 879419136287216681744888844\\
        &\text{…}&
    \end{eqnarray}


のように nの増加と共に組み合わせ数は爆発していきます。 B_{10^n}について桁数を考えると



    \begin{eqnarray}
        &&1 && (n=0)\\
        &&6 && (n=1)\\
        &&116 && (n=2)\\
        &&1928 && (n=3)\\
        &&27665 && (n=4)\\
        &&\text{…}
    \end{eqnarray}


のように増加していきます。つまりたった100個のパターンをクラスタリングする場合(つまり B_{10^2})ですら 10^{116 - 1}=10^{115}以上の組み合わせが存在します。この組み合わせ爆発のためにギブスサンプリングを採用しなくてはいけなくなるというわけです。