鴨川η

not δ

続・わかりやすいパターン認識 演習問題11.1

はじめに

続・わかりやすいパターン認識―教師なし学習入門―の輪講を新配属の学生がやっていてB4も習ってこの本の輪講が始まりました.

とりあえず,第11章 ノンパラメトリックベイズモデルを頭から読み始めました.

演習問題11.1について解答みつつ自分なりに解釈したので,それについて書きます.

ちなみに, Hoppo's urn model から Pitman-Yor Processまでを扱ったページの図は以下のgistにあげてあります.

本題

11.1(1)

最初みたときは,日本語ができないので(3)との違いがわからなかった.

人いてそれをクラスタに分けたい.

解説の言い回しを使うと,これは種類のカードを人の前に1枚ずづ配り方に相当する. なので,カードの順列数を,各カード(テーブル)の種類ごとの枚数の階乗で割ればよい.

\begin{eqnarray} N_{0} = \frac{n!}{n_{1}!n_{2}!…n_{c}!} \end{eqnarray}

  • は,テーブルの番号
  • は,テーブルにいる人数

例えば,人間が4人,テーブルが3つあって,そのときにテーブル1に2人,テーブル2に2人テーブル3に0人座らせる組み合わせ数は以下のとおり.

\begin{eqnarray} N_{0} = \frac{4!}{2!2!0!}=6 \end{eqnarray}

実際にテーブルに割り当ててみる.

ABCDがそれぞれ人,α,β,γの3種類のテーブルがあるとすると

  • α:AB β:CD γ:
  • α:AC β:BD γ:
  • α:AD β:BC γ:
  • α:CD β:AB γ:
  • α:BD β:AC γ:
  • α:BC β:AD γ:

の6通り.

11.1(2)

先の(1)に加えて,テーブルが区別できなくなる.

すべてのテーブルで人数が異なる場合は(1)と同じになる. 一方で同じ人数のテーブルが存在する場合,その個数だけ重複して数えているので,それを考慮する.

\begin{eqnarray} N_{1} = \frac{N_{0}}{c_{1}! c_{2}! … c_{r}!} \end{eqnarray}

はちょっとややこしくて,テーブルに座ってる人数の重複度である.

(1)と同様の人数構成の場合を考えて,例えば,テーブルが3つあって,2つテーブルに2人ずつ座っていて,1つのテーブルは誰も座ってない場合を考える. 2つのテーブルにおいて2人座っているので

\begin{eqnarray} N_{1} = \frac{6}{2!1!}=3 \end{eqnarray}

α,β,γの区別がなくなるので,以下の3通りになる(集合らしく書いたのは順序を考慮しないことを強調するためです).

  • {{AB},{CD}}
  • {{AC},{BD}}
  • {{AD},{BC}}

の3通り

11.1(3)

(2)の状態に対して, テーブルに通し番号を付けるのでにクラスタ数の階乗をかける.

\begin{eqnarray} N_{2} = c! N_{1} \end{eqnarray}

(2)と同じく,例えば,テーブルが3つあって,2つのテーブルに2人ずつ座っていて,1つのテーブルに誰も座ってない場合を考える.

テーブルが3つでそれに(2)の分け方を割り振るので

\begin{eqnarray} N_{2} = 3! \times 3 = 18 \end{eqnarray}

テーブルはα,β,γの3種類あるとすると以下の18通り.

  • α:AB, β:CD, γ:
  • α:AC, β:BD, γ:
  • α:AD, β:BC, γ:
  • α:CD, β:AB, γ:
  • α:BD, β:AC, γ:
  • α:BC, β:AD, γ:
  • α:AB, β:, γ:CD
  • α:AC, β:, γ:BD
  • α:AD, β:, γ:BC
  • α:CD, β:, γ:AB
  • α:BD, β:, γ:AC
  • α:BC, β:, γ:AD
  • α:, β:CD, γ:AB
  • α:, β:BD, γ:AC
  • α:, β:BC, γ:AD
  • α:, β:AB, γ:CD
  • α:, β:AC, γ:BD
  • α:, β:AD, γ:BC

以上です.