中華料理店のプロセス

確率論では、中華料理店のプロセスは離散時間 確率過程であり、レストランで顧客をテーブルに着席させることに似ています。無限の数の円形テーブルがあり、それぞれが無限の収容人数を持つレストランを想像してください。顧客 1 は最初のテーブルに座ります。次の顧客は顧客 1 と同じテーブルか、次のテーブルに座ります。これを繰り返し、各顧客は、すでにそこにいる顧客の数に比例した確率で占有されているテーブルに座るか (つまり、少数の顧客よりも多くの顧客がいるテーブルに座る可能性が高い)、空いているテーブルに座るかを選択します。時刻nでは、n 人の顧客はm  ≤  n個のテーブル (またはパーティションのブロック)に分割されています。このプロセスの結果は交換可能であり、つまり、顧客が座る順序は最終的な分布の確率に影響を与えません。この特性により、集団遺伝学、言語分析、画像認識における多くの問題が大幅に簡素化されます。

レストランの例えは、1985年にデイビッド・オルダスが書いた記事^[1]で初めて登場し、ジム・ピットマン（さらにレスター・デュビンズも引用）の功績であるとされた。^[2]

同等の分割プロセスは、ポリアの壷に似た「壷スキーム」を使用して、フレッド・ホッペによって1年前に発表されました^[3]。ホッペの壷モデルと比較して、中華料理店のプロセスには、ランダムな分割を記述することに加えて、サイクル構造を介してランダムな順列を自然に記述するのに適しているという利点があります。

任意の正の整数 に対して、 は集合 のすべての分割の集合を表します。中華料理店のプロセスは、無限直積 の値を取ります。 ${\displaystyle n}$${\displaystyle {\mathcal {P}}_{n}}$${\displaystyle \{1,2,3,...,n\}\triangleq [n]}$${\displaystyle \prod _{n\geq 1}{\mathcal {P}}_{n}}$

時刻 におけるプロセスの値は集合 の分割であり、その確率分布は次のように決定されます。時刻 では、自明な分割が得られます (確率 1)。時刻 では、要素 " " は次のいずれかです。 ${\displaystyle n}$${\displaystyle B_{n}}$${\displaystyle [n]}$${\displaystyle n=1}$${\displaystyle B_{1}=\{\{1\}\}}$${\displaystyle n+1}$${\displaystyle n+1}$

1. パーティションのブロックの1つに追加され、各ブロックは確率で選択されます。ここで、はブロックのサイズ（つまり要素の数）です。または${\displaystyle B_{n}}$${\displaystyle |b|/(n+1)}$${\displaystyle |b|}$
2. 確率 で、新しいシングルトン ブロックとしてパーティションに追加されます。${\displaystyle B_{n}}$${\displaystyle 1/(n+1)}$

このようにして生成されたランダム分割には、いくつかの特別な特性があります。再ラベル付けによって分割の分布が変わらないという意味で交換可能であり、ランダム分割から要素を削除することによって得られるの分割の法則がランダム分割の法則と同じであるという意味で一貫性があります。 ${\displaystyle \{1,...,n\}}$${\displaystyle [n-1]}$${\displaystyle n}$${\displaystyle B_{n}}$${\displaystyle B_{n-1}}$

特定のパーティションに割り当てられる確率（特定のテーブルに顧客が座る順番は無視）は、

${\displaystyle \Pr(B_{n}=B)={\frac {\prod _{b\in B}(|b|-1)!}{n!}},\qquad B\in {\mathcal {P}}_{n}}$

ここで、 はパーティション内のブロックであり、のサイズです。 ${\displaystyle b}$${\displaystyle B}$${\displaystyle |b|}$${\displaystyle b}$

この定義は、新しい顧客が新しいテーブルに座る確率を に変更し、それに応じてその顧客がサイズのテーブルに座る確率を に変更するパラメータを導入することで一般化できます。上で紹介したバニラ プロセスは、 を設定することで復元できます。直感的には、 は最初の空いているテーブルに座っている顧客の有効数として解釈できます。 ${\displaystyle \theta >0}$${\displaystyle {\frac {\theta }{n+\theta }}}$${\displaystyle |b|}$${\displaystyle {\frac {|b|}{n+\theta }}}$${\displaystyle \theta =1}$${\displaystyle \theta}$

中華料理店のプロセスを定義する同等だが微妙に異なる方法は、新しい顧客にテーブルではなく同伴者を選ばせることである。^[4]顧客は、着席している顧客のいずれかと同じテーブルに座ることを確率 で選択するか、新しい空いているテーブルに座ることを確率 で選択する。この定式化では、顧客はテーブルの占有状況を数えなくてもテーブルを選択することに注意してください。つまり、 は必要ないのです。 ${\displaystyle n+1}$${\displaystyle n}$${\displaystyle {\frac {1}{n+\theta }}}$${\displaystyle {\frac {\theta }{n+\theta }}}$${\displaystyle |b|}$

中華料理店のテーブル

パラメータ	${\displaystyle \theta >0}$ ${\displaystyle n\in \{1,2,\ldots \}}$
サポート	${\displaystyle k\in \{1,2,\ldots ,n\}}$
ＰＭＦ	${\displaystyle {\frac {\Gamma (\theta )}{\Gamma (n+\theta )}}|s(n,k)|\theta ^{k}}$
平均	${\displaystyle \theta (\psi (\theta +n)-\psi (\theta ))}$ （ディガンマ関数を参照）

中華料理店のテーブル分布（CRT）は、中華料理店のプロセスにおけるテーブルの数に関する確率分布です。 ^[5]これは、それぞれ異なるパラメータを持つ 独立したベルヌーイ確率変数の合計として理解できます。${\displaystyle n}$

${\displaystyle {\begin{aligned}K&=\sum _{i=1}^{n}b_{i}\\[4pt]b_{i}&\sim \operatorname {ベルヌーイ} \left({\frac {\theta }{i-1+\theta }}\right)\end{aligned}}}$

の確率質量関数は^[6]で与えられる。${\displaystyle K}$

${\displaystyle f(k)={\frac {\Gamma (\theta )}{\Gamma (n+\theta )}}|s(n,k)|\theta ^{k},\quad k=1,\dots ,n,}$

ここで、 は第一種スターリング数を表します。 ${\displaystyle s}$

この構成は、2つのパラメータ、& ^{[2] [7]}を持つモデルに一般化することができ、これらはそれぞれ強度（または集中）パラメータと割引パラメータと呼ばれる。時刻 に、次に到着した顧客は、空いているテーブルが空いていることに気づき、確率 ${\displaystyle \theta}$${\displaystyle \alpha}$${\displaystyle n+1}$${\displaystyle |B|}$

${\displaystyle {\frac {\theta +|B|\alpha }{n+\theta }},}$

または、占有されたテーブルのサイズで確率 ${\displaystyle b}$${\displaystyle |b|}$

${\displaystyle {\frac {|b|-\alpha }{n+\theta }}.}$

有効な確率測度を定義するために、何らかの に対しておよびであるか、または およびであると仮定する必要があります。 ${\displaystyle \alpha <0}$${\displaystyle \theta =-L\alpha }$${\displaystyle L\in \{1,2,,...\}}$${\displaystyle 0\leq \alpha <1}$${\displaystyle \theta >-\alpha }$

このモデルでは、 の任意の特定の分割に割り当てられる確率は、一般的な場合（上記の制約を満たす の任意の値に対して）ポッホハマーk-記号で次のように表すことができます。 ${\displaystyle B}$${\displaystyle [n]}$${\displaystyle \theta,\alpha}$

${\displaystyle \Pr(B_{n}=B\mid \theta ,\alpha )={\frac {(\theta +\alpha )_{|B|-1,\alpha }}{(\theta +1)_{n-1,1}}}\prod _{b\in B}(1-\alpha )_{|b|-1,1}}$

ここで、ポッホハマーk記号は次のように定義される。慣例により、、およびに対して${\displaystyle (a)_{0,k}=1}$${\displaystyle m>0}$

${\displaystyle (a)_{m,k}=\prod _{i=0}^{m-1}(a+ik)={\begin{cases}a^{m}&{\text{if }}k=0,\\\\k^{m}\,({\frac {a}{k}})^{\overline {m}}&{\text{if }}k>0,\\\\\left|k\right|^{m}\,({\frac {a}{\left|k\right|}})^{\underline {m}}&{\text{if }}k<0\end{cases}}}$

ここで、は上昇階乗、 は下降階乗です。 および のパラメータ設定について、 のときは となり、 のときは常に 0 と評価されるため、 はパーティション内のブロック数の上限となります。詳細については、以下のディリクレカテゴリカルモデルのサブセクションを参照してください。 ${\displaystyle x^{\overline {m}}=\prod _{i=0}^{m-1}(x+i)}$${\displaystyle x^{\underline {m}}=\prod _{i=0}^{m-1}(xi)}$${\displaystyle \alpha <0}$${\displaystyle \theta =-L\alpha }$${\displaystyle (\theta +\alpha )_{|B|-1,\alpha }=(|\alpha |(L-1))_{|B|-1,\alpha }}$${\displaystyle |B|>L}$${\displaystyle L}$

およびの場合、分割確率はガンマ関数を用いて次のよう に書き直すことができる。${\displaystyle \theta >0}$${\displaystyle 0<\alpha <1}$

${\displaystyle \Pr(B_{n}=B\mid \theta ,\alpha )={\frac {\Gamma (\theta )}{\Gamma (\theta +n)}}{\dfrac {\alpha ^{|B|}\,\Gamma (\theta /\alpha +|B|)}{\Gamma (\theta /\alpha )}}\prod _{b\in B}{\dfrac {\Gamma (|b|-\alpha )}{\Gamma (1-\alpha )}}.}$

1パラメータの場合、はゼロであり、これは次のように簡略化される。 ${\displaystyle \alpha }$${\displaystyle \theta >0}$

${\displaystyle \Pr(B_{n}=B\mid \theta )={\frac {\Gamma (\theta )\,\theta ^{|B|}}{\Gamma (\theta +n)}}\prod _{b\in B}\Gamma (|b|).}$

または、がゼロのとき、${\displaystyle \theta }$${\displaystyle 0<\alpha <1}$

${\displaystyle \Pr(B_{n}=B\mid \alpha )={\frac {\alpha ^{|B|-1}\,\Gamma (|B|)}{\Gamma (n)}}\prod _{b\in B}{\frac {\Gamma (|b|-\alpha )}{\Gamma (1-\alpha )}}.}$

以前と同様に、特定のパーティションに割り当てられる確率はブロック サイズのみに依存するため、以前と同様にランダム パーティションは上記の意味で交換可能です。一貫性プロパティは、以前と同様に、構造上保持されます。

の場合、このようにして生成された整数のランダム分割の確率分布は、集団遺伝学および生物多様性の統一中立理論で使用されるパラメータ を持つEwens 分布です。 ${\displaystyle \alpha =0}$ ${\displaystyle n}$${\displaystyle \theta }$

この分割確率を導く一つの方法を示します。が数字が追加されるランダムブロックであるとします。すると ${\displaystyle C_{i}}$${\displaystyle i}$${\displaystyle i=1,2,3,...}$

${\displaystyle \Pr(C_{i}=c\mid C_{1},\ldots ,C_{i-1})={\begin{cases}{\dfrac {\theta +|B|\alpha }{\theta +i-1}}&{\text{if }}c\in {\text{new block}},\\\\{\dfrac {|b|-\alpha }{\theta +i-1}}&{\text{if }}c\in b;\end{cases}}}$

がセットの特定の分割である確率は、が からまでの範囲でこれらの確率の積です。ここで、ブロック のサイズについて考えてみましょう。ブロックに要素を 1 つ追加するたびに、サイズは ずつ増加します。ブロック の最後の要素を追加する場合、ブロック サイズは です。たとえば、次の選択シーケンスについて考えます: (新しいブロック を生成する)( を結合する)( を結合する)( を結合する)。最終的に、ブロック には4 つの要素が含まれ、上記の式の分子の積は になります。このロジックに従うと、上記のようになります。 ${\displaystyle B_{n}}$${\displaystyle \{1,...,n\}}$${\displaystyle i}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle b}$${\displaystyle b}$${\displaystyle |b|-1}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle \theta \cdot 1\cdot 2\cdot 3}$${\displaystyle \Pr(B_{n}=B)}$

1パラメータの場合、およびの場合、テーブルの数は中華料理店のテーブル分布に従って分布します。着席している顧客がいる場合のこのランダム変数の期待値は、 ^[9]です。${\displaystyle \alpha =0}$${\displaystyle 0<\theta <\infty }$${\displaystyle n}$

${\displaystyle {\begin{aligned}\sum _{k=1}^{n}{\frac {\theta }{\theta +k-1}}=\theta \cdot (\Psi (\theta +n)-\Psi (\theta ))\end{aligned}}}$

ここで はディガンマ関数である。2パラメータの場合、 に対して、占有されるテーブルの期待数は^{[7]である。}${\displaystyle \Psi (\theta )}$${\displaystyle \alpha \neq 0}$

${\displaystyle {\begin{aligned}{\frac {(\theta +\alpha )^{\overline {n}}}{\alpha (\theta +1)^{\overline {n-1}}}}-{\frac {\theta }{\alpha }},\end{aligned}}}$

ここで、は上昇階乗です（上記で定義）。 ${\displaystyle x^{\overline {m}}}$

パラメータ選択および（ここで ）の場合、2 パラメータ中華料理店プロセスは、次のように定義できる階層モデルであるディリクレカテゴリモデルと同等です。このパラメータ設定では、すでに占有されているテーブルがある場合に新しいテーブルを占有する確率は 0 であるため、占有されているテーブルの数は によって上限が制限されることに注意してください。内の値を取るラベルを持つテーブルを識別することを選択した場合、セット のランダムなパーティションを生成するために、階層モデルは最初に、集中パラメータ を持つ対称ディリクレ分布 からカテゴリラベル分布 を抽出します。次に、各顧客について独立して、テーブルラベルがカテゴリ から抽出されます。ディリクレ分布はカテゴリ と共役であるため、隠れ変数を周辺化して、前のラベル が与えられた場合に次のラベル状態 の事後予測分布を取得できます。${\displaystyle \alpha <0}$${\displaystyle \theta =-L\alpha }$${\displaystyle L\in \{1,2,3,\ldots \}}$${\displaystyle L}$${\displaystyle L}$${\displaystyle \{1,2,\ldots ,L\}}$${\displaystyle [n]=\{1,2,\ldots ,n\}}$${\displaystyle \mathbf {p} =(p_{1},p_{2},\ldots ,p_{L})}$${\displaystyle \gamma =-\alpha >0}$${\displaystyle n}$${\displaystyle \mathbf {p} }$${\displaystyle \mathbf {p} }$${\displaystyle \ell _{n+1}}$${\displaystyle n}$

${\displaystyle P(\ell _{n+1}=i\mid \ell _{1},\ldots ,\ell _{n})={\frac {\gamma +\left|{b_{i}}\right|}{L\gamma +n}}}$

ここで、 はテーブル にすでに着席している顧客の数です。 および とすると、 のときに占有されているテーブルに着席する確率に関する上記の一般公式 と一致します。 空いているテーブルのいずれかに着席する確率も一般公式と一致し、次のように与えられます。 ${\displaystyle \left|{b_{i}}\right|\geq 0}$${\displaystyle i}$${\displaystyle \alpha =-\gamma }$${\displaystyle \theta =L\gamma }$${\displaystyle {\frac {|b_{i}|-\alpha }{n+\theta }}}$${\displaystyle |b_{i}|\geq 1}$${\displaystyle L-|B|}$

${\displaystyle \sum _{i:|b_{i}|=0}P(\ell _{n+1}=i\mid \ell _{1},\ldots ,\ell _{n})={\frac {(L-|B|)\gamma }{n+L\gamma }}={\frac {\theta +|B|\alpha }{n+\theta }}}$

ラベルの周辺確率は次のように与えられる。

${\displaystyle P(\ell _{1},\ldots ,\ell _{n})=P(\ell _{1})\prod _{t=1}^{n-1}P(\ell _{t+1}\mid \ell _{1},\ldots ,\ell _{t})={\frac {\prod _{i=1}^{L}\gamma ^{\overline {\left|{b_{i}}\right|}}}{(L\gamma )^{\overline {n}}}}}$

ここで、 および は上昇階乗です。ただし、一般に、同じパーティションに対応するラベル状態は複数存在します。ブロックを持つパーティション に対して、このパーティションに対応するラベル状態の数は、下降階乗で与えられます。これを考慮すると、パーティションの確率は次のようになります。 ${\displaystyle P(\ell _{1})={\frac {1}{L}}}$${\displaystyle x^{\overline {m}}=\prod _{i=0}^{m-1}(x+i)}$${\displaystyle B}$${\displaystyle \left|B\right|\leq L}$${\displaystyle L^{\underline {\left|B\right|}}=\prod _{i=0}^{\left|B\right|-1}(L-i)}$

${\displaystyle {\text{Pr}}(B_{n}=B\mid \gamma ,L)=L^{\underline {\left|B\right|}}\,{\frac {\prod _{i=1}^{L}\gamma ^{\overline {\left|{b_{i}}\right|}}}{(L\gamma )^{\overline {n}}}}}$

これは、ポッホハマーの k 記号で上で与えられた分割確率の一般的なバージョンと一致することが検証できます。 がサポートの外側にある場合、つまり、つまり下降階乗は、当然ながら 0 と評価されることに注意してください。( を介して分割の対数確率を評価する実際の実装では、 の 場合は常に、必要に応じてが返されます。) ${\displaystyle B}$${\displaystyle |B|>L}$${\displaystyle L^{\underline {|B|}}}$${\displaystyle \log L^{\underline {|B|}}=\log \left|\Gamma (L+1)\right|-\log \left|\Gamma (L+1-|B|)\right|}$${\displaystyle -\infty }$${\displaystyle |B|>L}$

一方では、 および を伴う 1 パラメータの中華料理店のプロセス (と表記)を考えます。他方では、を正の整数、 を伴うディリクレ カテゴリカル モデル ( を選択) を考えます。これは、上で示したように と同等です。これは、 を大きくすることで、ディリクレ カテゴリカル モデルを に任意に近づけることができることを示しています。 ${\displaystyle \alpha =0}$${\displaystyle \theta >0}$${\displaystyle {\text{CRP}}(\alpha =0,\theta )}$${\displaystyle L}$${\displaystyle \gamma ={\frac {\theta }{L}}}$${\displaystyle {\text{CRP}}(\alpha =-{\frac {\theta }{L}},\theta )}$${\displaystyle {\text{CRP}}(0,\theta )}$${\displaystyle L}$

2パラメータの中華料理店のプロセスは、棒折れプロセスとして定義することもできます。^[10]および の場合、棒折れプロセスは、上記のディリクレカテゴリモデルと同様に、階層モデルとして記述できますが、ラベル状態の数は無限です。表のラベルは、無限カテゴリ分布 とは独立に描画され、その成分は棒折れを使用してサンプリングされます。長さ1の棒から始めてランダムに2つに折ります。左半分の長さは で、右半分は となるように再度再帰的に折ります。より正確には、 -番目の折り目の左側の分数 は、ベータ分布からサンプリングされます。 ${\displaystyle 0\leq \alpha <1}$${\displaystyle \theta >-\alpha }$${\displaystyle \mathbf {p} =(p_{1},p_{2},\ldots )}$${\displaystyle p_{1}}$${\displaystyle p_{2},p_{3},\ldots }$${\displaystyle f_{k}}$${\displaystyle k}$

${\displaystyle f_{k}\sim B(1-\alpha ,\theta +k\alpha ),\;{\text{for }}k\geq 1{\text{ and }}0\leq \alpha <1}$

カテゴリ確率は次のとおりです。

${\displaystyle p_{k}=f_{k}\prod _{i=1}^{k-1}(1-f_{k}),\;{\text{where the empty product evaluates to one.}}}$

パラメータ設定および（ は正の整数、カテゴリカルは有限： ）の場合、上で説明したように通常のディルシュレー分布からサンプリングできますが、切り捨てスティックブレイクレシピを使用してサンプリングすることもできます。この場合、分数をサンプリングする式は次のように変更されます。 ${\displaystyle \alpha <0}$${\displaystyle \theta =-\alpha L}$${\displaystyle L}$${\displaystyle \mathbf {p} =(p_{1},\ldots ,p_{L})}$${\displaystyle \mathbf {p} }$

${\displaystyle f_{k}\sim B(-\alpha ,\theta +k\alpha ),\;{\text{for }}1\leq k\leq L-1{\text{ and }}\alpha <0}$

そして。 ${\displaystyle f_{L}=1}$

各データ ポイントがクラスに一意に関連付けられないように (つまり、パーティションを構築しないように)、クラスの任意の組み合わせに関連付けられるようにモデルを適応させることも可能です。これはレストランのテーブルの例えに反するため、代わりに、ビュッフェで提供されている無限の料理の選択肢のサブセットから一連のダイナーがサンプルを試すプロセスに例えられます。特定のダイナーが特定の料理を試食する確率は、ダイナーの間でのその料理の人気度に比例し、さらにダイナーはテストされていない料理を試食することもあります。これはインド ビュッフェ プロセスと名付けられ 、データの潜在的な特徴を推測するために使用できます。^[11]

中華レストランプロセスはディリクレ過程やポリアの壷スキームと密接に関連しているため、ノンパラメトリックベイズ法を含むベイズ統計の応用に有用である。一般化中華レストランプロセスはピットマン・ヨール過程と密接に関連している。これらのプロセスは、テキストモデリング、生物学的マイクロアレイデータのクラスタリング、^[12]生物多様性モデリング、画像再構成^{[13] [14]}など、多くのアプリケーションで使用されている。

• エウェンスサンプリング式
• 優先的添付
• グランドホテルのヒルベルトのパラドックス

• Frigyik、Kapila、Gupta によるディリクレ分布と関連過程の紹介
• CRP に関する Michael I. Jordanの講演:
  • http://videolectures.net/icml05_jordan_dpcrp/