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

今回はベル数の求め方を順を追って考えていきます。これも話が長いので読書会7, 8の二回に分けて記載します。読書会7では概要と包除原理の証明を行い、その結果を受けて読書会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

ベル数 1

概要

ベル数はクラスタリングの言葉で言うならば「（区別のある） $n$ 個のパターンを $1\sim n$ 個のクラスタに分ける場合の総数」のことを指し、記号では $B_n$ で表します。例えば3個のパターンを $1\sim 3$ 個のクラスタに分ける場合の総数ならば

一個のクラスタの場合
$\{1, 2, 3\}$

二個のクラスタの場合
$\{1\}\{2, 3\}$
$\{2\}\{1, 3\}$
$\{3\}\{1, 2\}$

三個のクラスタの場合
$\{1\}\{2\}\{3\}$

ですので5つとなります。つまり $B_3=5$ です。これはまさに $\boldsymbol{s}$ の組み合わせの数に他なりません。ベル数を求めるためには

$n=2$ の場合の包除原理を証明する
一般（ $n\gt2$ の場合）の包除原理を証明する
第二種スターリング数を求める
ベル数を求める

という順序で求めていくことになります。

$n=2$ の場合の包除原理の証明

wikipediaによると包除原理は

「有限集合 $A$ と $B$ の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 $|A|$ と $|B|$ を足しあわせた後、それらの共通部分に属する元の数 $|A\cap B|$ を引き去ればよい」

という原理のことを指すとされています。これは集合が二つの場合の話で式・ベン図で表せば

$|A\cup B|=|A|+|B|-|A\cap B|$

f:id:SatoshiWatanabe:20190525215754p:plain

という見慣れたものです。直観的には明らかなこの原理も証明するとなると多少回りくどくなります。この原理の証明のためにまずは真偽値 $T$ を定義します。

真偽値 $T$ の定義

性質Pに対し真偽値 $T$ を

$\begin{eqnarray}T(P) &=& \begin{cases}1 && P\text{が真}\\0 && P\text{が偽}\end{cases}\end{eqnarray}$

と定義する

全体集合 $U$ における有限な部分集合 $S$ の要素数をこの真偽値を用いれば

$|S|=\displaystyle\sum_{x\in U}{T(x\in S)}$

とあらわせます。この表現を用いると $|A\cup B|$ は

$|A\cup B|=\displaystyle\sum_{x\in U}{T(x\in A\cup B)}\quad (*)$

とあらわせます。また真偽値 $T$ において以下が成り立つことが明らかです。

1. $T(\overline{P})=1-T(P)$
2. $T(P\text{かつ}Q)=T(P)T(Q)$

ここで $\overline{P}$ は $P$ の否定を表し、 $Q$ も $P$ 同様性質を表します。この1. 2.を利用し $(*)$ 式の右辺における $T(x\in A\cup B)$ に関して以下を得ます。

$\begin{eqnarray} T(x\in A\cup B) &=& T(x\in A\text{または}x\in B)\\ &=& T(\overline{\overline{x\in A\text{または}x\in B\quad}})\\ &=& 1-T(\overline{x\in A\text{または}x\in B\quad})\\ &=& 1-T(\overline{x\in A}\text{かつ}\overline{x\in B})\\ &=& 1-T(\overline{x\in A})T(\overline{x\in B})\\ &=& 1-\{1-T(x\in A)\}\{1-T(x\in B)\}\\ &=& T(x\in A)+T(x\in B)-T(x\in A)T(x\in B)\\ &=& T(x\in A)+T(x\in B)-T(x\in A\text{かつ}x\in B)\\ &=& T(x\in A)+T(x\in B)-T(x\in A\cap B) \end{eqnarray}$

よって $(*)$ 式は

$\begin{eqnarray} |A\cup B| &=& \displaystyle\sum_{x\in U}{T(x\in A\cup B)}\\ &=& \displaystyle\sum_{x\in U}{\{T(x\in A)+T(x\in B)-T(x\in A\cap B)\}}\\ &=& \displaystyle\sum_{x\in U}{T(x\in A)}+\displaystyle\sum_{x\in U}{T(x\in B)}-\displaystyle\sum_{x\in U}{T(x\in A\cap B)}\\ &=& |A|+|B|-|A\cap B| \end{eqnarray}$

と計算でき、 $n=2$ の場合の包除原理が証明されました。

一般の場合の包除原理の証明

$n=3$ の場合の包除原理は $n=2$ の場合を利用して

$\begin{eqnarray} |A\cup B\cup C| &=& |A\cup (B\cup C)|\\ &=& |A|+|B\cup C|-|A\cap (B\cup C)|\\ &=& |A|+(|B|+|C|-|B\cap C|)-|(A\cap B)\cup(A\cap C)|\\ &=& |A|+|B|+|C|-|B\cap C|\\ && -(|A\cap B|+|A\cap C|-|(A\cap B)\cap(A\cap C)|)\\ &=& |A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C| \end{eqnarray}$

となります。この $n=3$ の場合の式を見ると

部分集合一つのすべての組み合わせについて（共通部分の）要素数を足す
部分集合二つのすべての組み合わせについて共通部分の要素数を引く
部分集合三つのすべての組み合わせについて共通部分の要素数を足す

のように、部分集合を組み合わせる数が一つずつ増えながら共通部分の要素数について可算・減算を交互に繰り返すという形になっていることが分かります。このことから包除原理は一般に

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

となると仮定できそうです。ではこの仮定が事実成り立つことを証明していきます。まずは最後の式における右辺には部分集合の共通部分が何回表れているかを考えます。例えば三個の部分集合 $A_i, A_j, A_k$ のみからなる共通部分についてならば、

一個の部分集合（の共通部分） $|A_i|, |A_j|, |A_k|$
二個の部分集合の共通部分 $|A_i\cap A_j|, |A_j\cap A_k|, |A_k\cap A_i|$
三顧の部分集合の共通部分 $|A_i\cap A_j\cap A_k|$

のように三個以下の部分集合の共通部分にそれぞれ含まれます。これらがそれぞれ順に可算・減算・可算と交互に計算されますので

${}_3\mathrm{C}_1-{}_3\mathrm{C}_2+{}_3\mathrm{C}_3=1$

となります。これを $m\leq n$ 個の共通部分に一般化すると

${}_m\mathrm{C}_1-{}_m\mathrm{C}_2+\cdots+(-1)^{m-1}{}_m\mathrm{C}_m=\displaystyle\sum_{k=1}^{m}{(-1)^{k-1}{}_m\mathrm{C}_k}$

とあらわすことが出来ます。どのような $m$ を選んでもこの値が $1$ となるのであれば包除原理における右辺の式ではすべての共通部分が一度ずつ表れているということなり式が成立している事を証明できます。そこでこの値が $m$ によらず $1$ になることを証明するのですが、帰納的に証明するとなるとだらだら長くなるため二項定理を用いたちょっとしたアイデアを使用します。具体的には $0$ を二項定理で展開したものを使用し下記のように計算していきます。

$\begin{eqnarray} 0 &=& (1-1)^m\\ &=& {}_m\mathrm{C}_0-{}_m\mathrm{C}_1+\cdots+(-1)^{m}{}_m\mathrm{C}_m\\ &=& 1-\displaystyle\sum_{k=1}^{m}{(-1)^{k-1}{}_m\mathrm{C}_k}\\ \therefore\quad\displaystyle\sum_{k=1}^{m}{(-1)^{k-1}{}_m\mathrm{C}_k} &=& 1 \end{eqnarray}$

以上より一般の場合の包除原理の式が成立していることが証明できました。

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