続・わかりやすいパターン認識 ひとり読書会 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
第二種スターリング数
- 個のパターンを区別のないちょうど個のクラスタに分割する場合の数
を表す数でなどとあらわします。この第二種スターリング数を求めるためにまず
- 個のパターンを区別のあるちょうど個のクラスタに分割する場合の数
を求めます。これは個のパターンが個のクラスタのいずれかに属する場合の数から、いずれかのクラスタに誰も属さない場合の数をすべて引くことで求めることが出来ます。まず個のパターンが個のクラスタのいずれかに属する場合の数を考えると、各パターンはのクラスタのどれかに任意に割り当てることが出来るのでとなります。ではいずれかのクラスタに誰も属さない場合の数はどのように考えればよいでしょうか。これを考えるために各クラスタにどのパターンも属さない場合を要素とする集合をそれぞれとします。このそれぞれの集合の要素数はのようにあらわされ、いずれかのクラスタに誰も属さない場合の数はであらわすことが出来ます。ここで読書会7で証明した包除原理を用いると
が成り立ちます。ではやなどはどのようにして求めればよいでしょうか。まずはについて考えます。はクラスタに誰も属さない場合の数です。これは個のパターンがを除いた個のクラスタのいずれかに属する場合の数のことですので前述と同じ考え方でとなります。続いてつまりクラスタにもにも誰も属さない場合の数について同じように考えるととなります。これらの考えを進めていくと、
となります。また、から個の集合を選ぶ組み合わせはですので結局包除原理の式は
となります。このを個のパターンが個のクラスタのいずれかに属する場合の数から引けばよいので
と結果が出ました。求めていたものを思い出すとこれは
- 個のパターンを区別のあるちょうど個のクラスタに分割する場合の数
でしたので区別のない場合はここからクラスタの区別による重複分を削除することを考慮すればよいことになります。つまりで割ることになりますので第二種スターリング数は
と求まります。
ベル数
ベル数は「n個のものを分割する方法の総数」のことを指します。このベル数を考えるにあたって
- 個のパターンを区別のない個以下のクラスタに分割する場合の数
を考えていきます。これをとあらわすこととします。第二種スターリング数は
- 個のパターンを区別のないちょうど個のクラスタに分割する場合の数
でしたので
と計算できます。ベル数は「n個のものを分割する方法の総数」つまり「個のパターンを区別のない個以下のクラスタに分割する場合の数」に他なりませんので結局
と求まります。
具体的な値
ベル数をの場合について計算していくと
と考察の初めに計算した値と一致します。そのほかの値についてベル数を計算していくと
のようにの増加と共に組み合わせ数は爆発していきます。について桁数を考えると
のように増加していきます。つまりたった100個のパターンをクラスタリングする場合(つまり)ですら以上の組み合わせが存在します。この組み合わせ爆発のためにギブスサンプリングを採用しなくてはいけなくなるというわけです。
参照サイト
ベル数の考察にあたっては以下のサイトを参照しています。ここでは記述できなかったトピックも豊富ですので興味のある方はご一読ください。
(1.)包除原理 - Wikipedia
(2.)集合4つの包除原理と真偽値 | saitei.net
(3.)包除原理の2通りの証明 | 高校数学の美しい物語
(4.)全射の個数の証明とベル数 | 高校数学の美しい物語
(5.)Bell Number -- from Wolfram MathWorld
今回はここまでにして次回はの導出をしていきます。
続パタ読書会 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