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

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

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