5.1 Exchangeable Partitions

이 section에서는 $\mathbb N_n$의 가능한 모든 partition들의 collection 위에서 정의된 probability measure에 대해 소개할 것이다. 이와 같은 probability measure는 data를 clustering할 때의 prior distribution으로 사용할 수 있다. Partition은 다음과 같이 정의된다.

A partition $\text{ }{ A_1 , \cdots , A_k }$ of the finite set $\mathbb N_n = { 1, \cdots , n }$ is a decomposition of this set in disjoint (nonempty) subsets:

\[\mathbb N_n = \bigcup_i A_i , \enspace A_i \cap A_j = \emptyset \text{ for }i \neq j.\]

또한, $\mathbb N_n$의 partition으로 얻어진 각 set들의 cardinality $n_i = \vert A_i \vert$는 partition of $n$이라고 부른다.

An unordered set ${ n_1, \cdots , n_k }$ of natural numbers such that $n=\sum_{i=1}^k n_i$ forms a partition of $n$

별다른 언급이 없다면 partition 내의 set $A_i$들은 unordered이다. Ordered partition에 대한 partition of $n$을 composition of $n$이라고 부르고, 모든 composition of $n$의 집합을 $\mathcal C_n$으로 나타낸다.

Partition 내의 각 set들에 대해, 각 set들의 minimal element를 기준으로 오름차순으로 set들을 정렬할 수 있다. 이 순서를 order of apperance라고 한다.

\[\min A_1 < \min A_2 < \cdots < \min A_k\]

$\mathbb N_n$의 random partition은 어떤 확률공간 위에서 정의되고, $\mathbb N_n$의 가능한 모든 partition들의 collection에 속하는 값을 갖는 random element를 의미한다. 또한 random partition의 distribution은 random partition의 induced probability measure로 정의된다. 그 중에서도 우리는 exchangeable partition에 관심이 있다. 그 정의는 아래와 같다. 아래 정의에서 $\sigma(A)$는 $A \subset \mathbb N_n$의 permutation map $\sigma$에 대한 image set이다.

Definition 1

A random partition $\mathcal P_n$ of $\mathbb N_n$ is called exchangeable if its distribution is invariant under the action of any permutation $\sigma : \mathbb N_n \mapsto \mathbb N_n$, i.e. for every partition ${ A_1, \cdots , A_k}$ of $\mathbb N_n$ the probability $\mathbb P(\mathcal P_n = { \sigma (A_1), \cdots , \sigma (A_k) } )$ is the same for every permutation $\sigma$ of $\mathbb N_n$. Equivalently, a random partition $\mathcal P_n$ of $\mathbb N_n$ is exchangeable if there exists a symmetric function $p: \mathcal C_n \rightarrow [0,1]$ such that, for every partition ${ A_1, \cdots , A_k}$ of $\mathbb N_n$,

\[\mathbb P(\mathcal P_n = \{ \sigma (A_1), \cdots , \sigma (A_k) \} ) = p(\vert A_1 \vert, \cdots , \vert A_k \vert).\]

The function $p$ is called the exchangeable partition probability function(EPPF) of $\mathcal P_n$.

이 정의를 다시 찬찬히 읽어보면 exchangeable random partition은 다음과 같이 이해할 수 있다.

• 그 random partition의 distribution이 permutation에 invariant하다.
• 서로 다른 두 partition의 원소들이 같은 수$(n_1, \cdots , n_k)$의 조합으로 이루어졌다면, 두 partition의 확률은 같다.

예를 들어, 다음과 같은 partition과 permutation을 생각해보자.

\[A_1 = \{ 1, 2, 4 \}, A_2=\{ 3 \}, A_3 = \{ 5, 6 \}\] \[\begin{align*} \sigma(k) = &k+2 \enspace \text{ if }k=1,2,3,4 \\ \sigma(k) = &k-4 \enspace \text{ if }k=5,6 \end{align*}\]

이 때 permutation $\sigma$에 대한 partition의 image는 아래와 같다.

\[\sigma (A_1) = \{ 3, 4, 6 \}, \sigma (A_2)=\{ 5 \}, \sigma (A_3) = \{ 1,2 \}\]

만약 이 partition이 생성된 random partition이 $\mathcal P_n$이 exchangeable partition이라면, 다음이 만족할 것이다.

\[\mathbb P \Big( \mathcal P_n = \Big\{ \{ 1, 2, 4 \}, \{ 3 \}, \{ 5, 6 \} \Big\} \Big) = \mathbb P \Big( \mathcal P_n = \Big\{ \{ 3, 4, 6 \},\{ 5 \}, \{ 1,2 \} \Big\} \Big) =p(3,1,2)\]

위에서 정의한 $\sigma$ 외에도 모든 permutation에 대해서도 성립할 것이므로, 두 partition이 같은 수$(n_1, \cdots , n_k)$로 이루어졌다면, 두 partition의 확률은 같다. EPPF는 ordered partition of $n$, 즉 composition of $n$의 collection $\mathcal C_n$에서 정의되었지만, exchangeable random partition의 정의에 의해 symmetric할 것이다. 예를 들면 다음과 같다.

\[p(1,2,3)=p(1,3,2)=\cdots = p(3,2,1)\]

따라서 EPPF는 partition of $n$의 collection에서 정의된 것으로 이해해도 무방하다.

Example 2

만약 어떤 random partition의 EPPF가 다음 조건을 만족하면, 이를 product partition model이라고 부른다.

\[p(\vert A_1 \vert, \cdots , \vert A_k \vert ) = V_{n,k} \prod_{i=1}^k \rho (\vert A_i \vert)\]

이 때, 함수 $\rho : \mathbb N \rightarrow [0,1]$를 product partition model의 cohesion function으로 부른다.

Example 3

Exchangeable random vector로부터 exchangeable random partition을 유도할 수 있다. 먼저 $n$개의 임의의 원소로 이루어진 ordered list $(x_1 , \cdots , x_n)$에 대해, 다음과 같은 equivalence relation을 정의하자.

\[i \sim j \iff x_i = x_j\]

어떤 exchangeable random vector에 대해, 위 equivalence relation으로 얻어진 random partition은 exchangeable하다. (Exchangeable random vector에 대한 정의는 1장 참고.)

Example 4

먼저 $\mathcal C_n$ 위에 정의된 distribution으로부터, composition $(n_1, \cdots , n_k)$를 생성한다. 그리고 생성된 $(n_1, \cdots , n_k)$에 대해, 다음 $i$가 $n_i$개 있고, 총 $n$개의 symbol로 이루어진 ordered set을 random하게 permute함으로써 random vector $(X_1, \cdots , X_n)$을 생성한다.

\[(1, \cdots , 1, 2, \cdots, 2, \cdots , k ,\cdots, k)\]

그리고 example 3에서의 equivalence relation을 이용하여 partition of $\mathbb N_n$을 정의한다. 이와 같은 과정으로 임의의 exchangeable random partition of $\mathbb N_n$을 얻을 수 있다.

Proposition 5

$\mathbb N_n$의 partition, $A_1 , \cdots , A_k$의 정보를 partition of $n$, ${ n_1, \cdots , n_k }$으로 나타내는 다른 방법 중 하나는 multiplicity class $(m_1, \cdots , m_n)$을 이용하는 것이다. 여기서 $m_i$는 $A_1 , \cdots , A_k$ 중 cardinality가 $i$인 set의 개수를 의미한다. 또한 다음이 만족한다.

\[\sum_{i=1}^n i m_i = n\]

이와 같은 표현을 이용하면 다음과 같은 proposition을 얻을 수 있다.

The probability that a random exchangeable partition of $\mathbb N_n$ consists of $m_i$ sets of cardinality $i$, for $i=1,\cdots, n$, is equal to, for any composition $(n_1, \cdots, n_k)$ compatible with the multiplicity class $(m_1, \cdots, m_n),$

\[\frac{n!}{\prod_{i=1}^n m_i ! (i!)^{m_i}} p(n_i, \cdots, n_k)\]

Furthermore, the probability that a random exchangeable partition of $\mathbb N_n$ consists of $k$ sets, for $k=1, \cdots, n$, is equal to, with the sum over all compositions $(n_1, \cdots, n_k)$ of $n$ in $k$ elements,

\[\sum_{(n_1, \cdots, n_k)} \frac{1}{k!} \left( \begin{matrix} n \\ n_1 \cdots n_k \\ \end{matrix} \right) p(n_1, \cdots, n_k)\]

어떤 한 composition of $n$ (ordered partition of $n$), $(n_1, \cdots, n_k)$의 확률은 EPPF의 정의에 의해 $p(n_1, \cdots, n_k)$이다. 이 주어진 composition과 같은 multiplicity class$(m_1 , \cdots , m_n)$를 갖는 composition들이 몇 개 있는지 세서 곱해주면 첫 번째 식을 도출한 것이 된다. 만약 $n$개의 symbol이 모두 달랐다면 총 $n!$개의 가능한 ordering이 있을 것이다. 그러나 $i = 1 , \cdots, n$에 대해, cardinality가 $i$인 set이 $m_i$개 있을 것이므로 $n$개의 symbol을 $\cdots, B_{m_1}, \cdots, B_{m_2}, \cdots, B_{m_n}$로 배분한 경우의 수는 다음과 같다.

\[\frac{n!}{\prod_{i=1}^n (i!)^{m_i} }\]

근데 각 multiplicity 내에서는 서로 order가 의미가 없으므로, 불필요한 order가 고려된 것을 상쇄시켜주기 위해 추가로 다음을 나눠주면 첫 번째 식을 얻을 수 있다.

\[\prod_{i=1}^n m_i !\]

두 번째 식에 대한 증명은 다음과 같다. 먼저 ordered random partition of $\mathbb N_n$을 고려해보자. Random exchangeable partition of $\mathbb N_n$이 $k$개의 set으로 이루어져있을 확률은 그 partition이 order가 되어있는지 여부와 상관이 없다. 주어진 composition $(n_1 , \cdots, n_k)$에 대해, ordered partition이 set size가 $n_1 , \cdots, n_k$일 확률은 다음과 같다.

\[\frac{p(n_1 , \cdots, n_k)}{k!}\]

$p(n_1 , \cdots, n_k)$는 unordered partition에 대한 확률이기 때문에 그 중 한 order를 고르려면 $k!$를 나누어 주어야 한다. Ordered partition은 vector $(1, \cdots , n)$을 permute하고, 처음 $n_1$개를 $A_1$, 그 다음 $n_2$개를 $A_2$로 고르는 방식으로 construct할 수 있다. 이 때 처음 $n_1$개 안에서, 그 다음 $n_2$개 안에서 permute하는 것은 같은 composition으로 이어진다. 따라서 주어진 composition $(n_1, \cdots , n_k)$를 만족하는 경우의 수는 아래와 같다.

\[\left( \begin{matrix} n \\ n_1 \cdots n_k \\ \end{matrix} \right)\]

Exchangeability에 의해 각 경우는 모두 같은 확률 $\frac{p(n_1 , \cdots, n_k)}{k!}$를 가지므로, 두번째 식과 같은 식을 얻게 된다. $\square$

Definition 6

An infinite exchangeable random partition (or exchangeable random partition of $\mathbb N$) is a sequence $(\mathcal P_n:n \in \mathbb N)$ of exchangeable random partitions of $\mathbb N_n$ that are consistent in the sense that $\mathcal P_{n-1}$ is equal to the partition obtained from $\mathcal P_n$ by leaving out the element $n$, almost surely, for every $n$. The function $p: \cup_{n=1}^\infty \mathcal C_n \rightarrow [0,1]$ whose restriction to $\mathcal C_n$ is equal to the EPPF of $\mathcal P_n$ is called the exchangeable partition probability function (EPPF) of $(\mathcal P_n:n \in \mathbb N)$

Infinite exchangeable random partition에 대한 정의는 finite의 경우를 위에 서술된 바와 같은 consistent sense로 확장한 것이다. 위와 같은 infinite exchangeable random partition은 infinite exchangeable한 random variable의 sequence, $X_1, X_2, \cdots $ 로부터 얻을 수 있다. 그 방법은 위의 Example 3에 소개된 방법을 임의의 자연수 $n$에 적용하는 것이다. 이 때 random variable의 sequence, $X_1, X_2, \cdots $가 infinite random partition을 generate한다고 표현한다.

Theorem 7

이 정리는 모든 infinite exchangeable random partition이 어떤 exchangeable sequence에 의해 generate된 것으로 볼 수 있다는 사실을 의미한다.

(Kingman’s representation) For any infinite exchangeable random partition $(\mathcal P_n:n \in \mathbb N)$ defined on a probability space that is rich enough to support an independent i.i.d. sequence of uniform variables, there exists a random probability measure $P$ on $[0,1]$ and a sequence of random variables $X_1, X_2, \cdots$ defined on the same probability space with $X_1, X_2, \cdots \vert P \stackrel{iid}{\sim} P$ that generates $(\mathcal P_n:n \in \mathbb N)$. Furthermore, the size $N_{(j),n}$ of the $j$th largest set in $\mathcal P_n$ satisfies $n^{-1}N_{(j),n} \rightarrow W_{(j)} \text{ a.s. } $ as $n \rightarrow \infty$, for $W_{(1)} \geq W_{(2)} \geq \cdots $ the sizes of the atoms of $P$ ordered in decreasing size.

그 증명은 다음과 같다. 먼저 $\mathcal P_n$과 같은 확률공간에서 정의되고, $\mathcal P_n$과 독립인 uniform 확률변수의 iid sequence $\xi_1 , \xi_2, \cdots $를 생각하자. Uniform분포를 따르는 확률변수는 연속형 확률변수이므로, null set을 제외한다면 $\xi_1 , \xi_2, \cdots $는 “surely”하게 서로 다른 값을 가질 것이다. 임의의 자연수 $i$에 대해, $i$가 속하는 partitioning set의 가장 작은 원소 $j(i)$를 정의하자. 참고로 $(\mathcal P_n:n \in \mathbb N)$은 위 정리의 조건에서 주어진 것처럼 “consistent”하므로 $j(i)$를 정의할 때는 partition $\mathcal P_i$, $j(i) \leq i$를 생각하면 된다. 왜냐하면 $\mathcal P_n$에서 $\mathcal P_{n+1}$로 확장을 할 때를 생각해보면, 추가되는 $n+1$번째 자연수가 기존의 partitioning set에 들어가거나 혹은 새로운 partitioning set에 들어가더라도, $i$가 속하는 partitioning set의 가장 작은 원소 $j(i)$에는 변함이 없기 때문이다.

$X_i \stackrel{let}{=} \xi_{j(i)}$로 $X_1, X_2, \cdots$를 정의하자. 이 때 $X_i$는 uniform 확률변수의 sequence $(\xi_j)$와 random partition $(\mathcal P_n)$에 영향을 받으므로, 어떤 measurable map $g_i$에 대해 다음과 같이 나타낼 수 있다.

\[X_i = g_i((\xi_j), (\mathcal P_n)).\]

그리고 finite개의 coordinate을 바꾸는 임의의 permutation $\sigma$에 대해,

\[X_{\sigma(i)} = g_i((\xi_{\sigma(j)}), (\sigma \left< \mathcal P_n \right> )).\]

어떤 random partition의 sequence $(\mathcal P_n )$에 대해, $(\sigma \left< \mathcal P_n \right> )$는 $\mathbb N$을 $\sigma$에 의해 swap하고 얻은 $\mathbb N_n$의 partition의 sequence이다. 그런데 $\xi_1 , \xi_2, \cdots $는 uniform 확률변수의 iid sequence이고 $(\mathcal P_n)$은 infinite exchangeable하기 때문에, $((\xi_{\sigma(j)}), (\sigma \left< \mathcal P_n \right> ))$의 distribution은 permutation $\sigma$에 의해 영향을 받지 않는다 (invariant). 따라서, $X_1, X_2, \cdots$는 exchangeable한 확률변수 sequence이다. 따라서 De Finetti 정리에 의해, 다음을 만족하는 random measure $P$가 존재한다.

\[X_1, X_2, \cdots \vert P \stackrel{iid}{\sim} P\]

위와 같이 정의한 $X_i$는 다음을 만족한다.

\[\begin{align*} X_{i_1} = X_{i_2} &\iff \xi_{j(i_1)} = \xi_{j(i_2)} \\ &\iff i_1 \text{ and } i_2 \text{ are in the same partitioning set.} \end{align*}\]

따라서 임의의 infinite exchangeable random partition $(\mathcal P_n:n \in \mathbb N)$에 대해, 이를 generate하는 random variable의 sequence $X_1, X_2 , \cdots$와 그 분포를 $X_1, X_2, \cdots \vert P \stackrel{iid}{\sim} P$와 같이 정의하는 random probability measure $P$가 존재함을 보였다.

마지막 assertion을 증명하기 위해서는 $X_1, X_2, \cdots$에 의해 generate된 partition $\mathcal P_n$들은 다음과 같은 형태의 partitioning set으로 이루어져 있다는 사실을 상기할 필요가 있다.

\[\{ i \in \mathbb N_n : X_i = x \}\]

$N_{(j),n}$은 partition $\mathcal P_n$의 $j$번째로 큰 set의 크기이다. 따라서, 가능한 수많은(엄밀하게는 uncountably many) $x$들에 대해, $N_{(j),n}$은 위와 같은 partitioning set의 cardinality, $N_n(x)$를 크기 내림차순으로 정렬했을 때 그 중 $n$번째 수라는 것을 알 수 있다. 따라서 ergodic law of large numbers에 의해,

\[n^{-1} N_n(x) = n^{-1} \vert \{ i \in \mathbb N_n : X_i = x \} \vert \longrightarrow \mathbb P (X_1 = x \vert P), \text{ a.s. }\]

따라서 두 번째 assertion도 증명되었다. $\square$

From EPPF to an Infinite Exchangeable Random Partition

Theorem 7을 잘 생각해보면, random probability measure $P$를 굉장히 arbitrary하게 잡을 수 있다는 것을 알 수 있다. $X_i$들의 패턴, 또 그에 의해 결정되는 $\mathbb N$의 partition에 영향을 주는 것은 random probability measure $P$의 atom이기 때문이다.

• Atom이란 (random) measure $P$가 $0$보다 큰 measurable set을 의미한다. 즉, $P$가 discrete한 probability mass를 가지는 $x$, 혹은 이를 포함하는 set을 의미한다.

좀더 정확하게는 atom의 size($x$가 갖는 probability mass)가 $X_i$들이 서로 같은 값을 갖거나 다른 값을 갖는 확률, 즉 $\mathbb N$의 partition에 영향을 주는 것이고, atom의 위치는 그저 partition의 label이 될 뿐이다. 또한, $P$의 atomless 부분은 더욱 arbitrary하다. (이 부분 보충 필요. species sampling model로의 연결고리.)

Infinite exchangeable random partition을 marginalize하면, $\mathcal P_{n-1}$과 $\mathcal P_n$의 random exchangeable partition의 EPPF, $p^{(n-1)},p^{(n)}$에 대한 다음 관계식을 얻을 수 있다.

\[p^{(n-1)}(n_1, \cdots, n_k) = \sum_{j=1}^k p^{(n)}(n_1, \cdots, n_j +1 , \cdots , n_k) + p^{(n)}(n_1, \cdots , n_k, 1)\]

참고로, EPPF 내에 들어간 composition의 모든 수를 합하면 그 EPPF가 $\mathbb N_1 , \mathbb N_2 , \cdots, \mathbb N_n , \cdots $ 중 어느 것의 partition에 대한 EPPF인지 확실히 알 수 있으므로, 위첨자로 들어간 $(n-1)$과 $(n)$을 떼고 표현하기도 한다. 또는 아래와 같은 notation을 이용하여 표현하기도 한다.

\[\begin{align*} \text{For given }\mathbf n &=(n_1, \cdots, n_k), \\ \mathbf n^{j+} &= (n_1, \cdots, n_j +1 , \cdots , n_k), \\ \mathbf n^{(k+1)+} &= (n_1, \cdots , n_k, 1) , \\ p(\mathbf n) &= \sum_{j=1}^{k+1} p(\mathbf n^{j+}). \end{align*}\]

위 관계식이 의미하는 바에 대해서 알아보자. EPPF의 정의를 다시 소개하자면 아래와 같다.

\[\mathbb P(\mathcal P_n = \{ \sigma (A_1), \cdots , \sigma (A_k) \} ) = p(\vert A_1 \vert, \cdots , \vert A_k \vert).\]

주어진 random partition of $\mathbb N_{n-1}$, $\mathcal P_{n-1}$에 대해, 새로운 $n$ 번째 원소가 기존 $\mathcal P_{n-1}$에서 나뉘어진 partition의 각 set에 들어갈 수 있고 새로운 partitioning set에 들어갈 수도 있기 때문에, 이 확률을 모두 더해주면 $\mathcal P_{n-1}$의 EPPF와 같다는 것이다. 따라서 위 관계식은 infinite exchangeable partition의 정의에 나타난 random partition의 분포의 “consistency”를 의미한다.

더 나아가, 위 관계식을 만족하는 symmetric function의 sequence $p: \cup_{n=1}^\infty \mathcal C_n \rightarrow [0,1]$가 주어졌을 때, 우리는 그 $p$를 EPPF로 갖는 infinite exchangeable partition을 항상 만들 수 있다. 그 과정은 아래와 같다.

• 위 그림과 같이 반복적으로 $\mathcal P_{n-1}$을 $\mathcal P_n$으로 확장하여, partition of $\mathbb N_n$의 sequence의 joint distribution을 만든다.
• 위 관계식은 그림과 같이 각 node의 확률이 다음 가지의 node들로 나뉠 수 있음을 정당화한다.

\[\text{ex) } \enspace p(1,1) = \{ p(2,1) + p(1,2) \} + p(1,1,1)\]

• 따라서 한 원소씩 recursive하게 partition을 수행하는 방법으로 모든 partition of $\mathbb N_n$을 모아놓은 공간 위의 probability distribution을 정의할 수 있다.
• 또한 우리는 함수 $p$를 symmetric 함수로 가정했으므로, partition의 분포는 exchangeable하다.
• Ionescu-Tulcea extension theorem을 이용하여 주어진 marginal 분포에 대하여, 그와 consistent한 infinite sequence ${ \mathcal P_n : n \in \mathbb N }$의 distribution의 존재성을 얻는다.

Lemma 8

이 Lemma 8과 관련된 내용은 Lee, J. et al. (2013). Defining predictive probability functions for species sampling models.에 기반하여 작성되었다.

지금까지는 infinite exchangeable partition을 partition of $\mathbb N_n$의 sequence로 보고 논의를 전개하였다. 그와는 다르게, 이전의 점들에 의해 만들어진 partition에 점을 하나하나 추가해 나가는 sequential process로서 infinite exchangeable partition을 이해할 수 있다. $n+1$번째 점이, composition $\mathbf n = (n_1, \cdots, n_k)$로 주어진 partition of $\mathbb N_n$의 $j$번째 set에 포함되는 조건부 확률은 다음과 같다. 이를 $p_j (\mathbf n) $으로 나타내겠다.

\[p_j (\mathbf n) = \frac{p(\mathbf n^{j+})}{p (\mathbf n) }, \enspace \enspace j=1,\cdots, k+1\]

이 때, 위와 같이 정의된 함수 $p_j : \cup_n \mathcal C_n \rightarrow [0,1]$, 혹은 composition of $n$의 공간들 위에서 위와 같이 정의된 함수들의 collection을 prediction probability function(PPF)이라고 부른다. 또한, $(p_1(\mathbf n), \cdots, p_{k+1}(\mathbf n))$은 임의의 composition $\mathbf n$에 대해 확률 벡터(probability vector)가 된다. 이 PPF는 위 그림에서 한 node가 다음 node들로 가지가 갈라질 때의 weight 역할을 한다. 하지만 이와 같은 PPF는, infinite exchangeable partition이나 혹은 그 EPPF로부터 PPF를 도출하는 것보다, 어떤 함수들의 collection(PPF)으로부터 infinite exchangeable partition을 순차적인 방법으로 이끌어내는 것에서 더 큰 중요성을 갖는다.

먼저 putative(generally thought to be or to exist) PPF라는 개념을 소개한다. Putative PPF는 다음 성질을 만족하는 composition of $n$, $\forall n$에 대한 함수들의 sequence를 의미한다.

\[p_j(\mathbf n) \geq 0 \text{ and } \sum_{j=1}^{k+1} p_j(\mathbf n) = 1\]

따라서 EPPF로부터 유도된 PPF는 putative PPF의 조건을 항상 만족한다. 하지만 putative PPF는 항상 PPF가 될 수 있는 것이 아니고 추가적인 조건이 필요하다. 우리는 putative PPF를 PPF가 될 수 있는 함수들의 후보로, 그리고 putative PPF로부터 얻어진 $p$를 EPPF의 후보로 삼고, 어떤 조건이 추가되어야 putative PPF로부터 얻어진 $p$가 어떤 infinite exchangeable random partition의 EPPF가 될 수 있는지 알아볼 것이다. putative PPF가 주어졌을 때, 우리는 다음과 같은 방법으로 $p: \mathbb N^\ast \rightarrow [0,1]$을 construct한다.

\[\begin{align*} p(1) &= 1 \\ p(\mathbf n^{j+}) &= p_j(\mathbf n)p(\mathbf n) \\ &\text{for all } \mathbf n \in \mathbb N \text{ and } j=1,\cdots, k(\mathbf n) +1 \end{align*}\]

다음 보조정리는 위와 같이 putative PPF $p_j$로부터 construct된 함수 $p$가 어떤 infinite exchangeable partition의 EPPF가 될 필요충분조건을 제시한다.

A collection of functions $p_j$ is a PPF of an infinite exchangeable partition if and only if the following holds:

• For every composition $\mathbf n=(n_1, \cdots , n_k)$, $(p_1(\mathbf n), \cdots, p_{k+1}(\mathbf n))$ is a probability vector.
• For all $i,j \in \mathbb N_n$,

\[p_i(\mathbf n)p_j(\mathbf n^{i+}) = p_j(\mathbf n)p_i(\mathbf n^{j+}).\]

• For every permutation $\sigma$ of $\mathbb N_k$,

\[p_i(n_1, \cdots, n_k) = p_{\sigma^{-1}(i)}(n_{\sigma(1)} , \cdots, n_{\sigma(k)}).\]

이 보조정리의 증명은 다음과 같다.

Necessity

먼저 $p_j$가 어떤 infinite exchangeable partition의 prediction probability function(PPF)일 때 위 세 조건이 만족하는 것을 보이자.

• $(p_1(\mathbf n), \cdots, p_{k+1}(\mathbf n))$이 probability vector가 되는 것은 자명하다.
• 두 번째 조건이 만족하는 것은 다음과 같이 보일 수 있다.

\[\begin{align*} p_i(\mathbf n)p_j(\mathbf n^{i+}) &= \frac{p(\mathbf n^{i+})}{p (\mathbf n) }\frac{p( (\mathbf n^{i+})^{j+} )}{p (\mathbf n^{i+}) }= \frac{p( (\mathbf n^{i+})^{j+} )}{p (\mathbf n) } \\ p_j(\mathbf n)p_i(\mathbf n^{j+}) &= \frac{p(\mathbf n^{j+})}{p (\mathbf n) }\frac{p( (\mathbf n^{j+})^{i+} )}{p (\mathbf n^{j+}) }= \frac{p( (\mathbf n^{j+})^{i+} )}{p (\mathbf n) } \\ \Big( \because \enspace (\mathbf n^{j+})^{i+} = (n_1,&\cdots, n_i +1, \cdots, n_j+1, \cdots, n_k) =(\mathbf n^{i+})^{j+} \Big) \end{align*}\]

• 세 번째 조건은 다음과 같이 보일 수 있다.

\[\begin{align*} p_i(n_1, \cdots, n_k) &= \frac{p(n_1, \cdots, n_i+1 ,\cdots, n_k)}{p(n_1, \cdots, n_i ,\cdots, n_k)} \\ &\stackrel{let}{=} \frac{p(\tilde n_1, \cdots, \tilde n_i ,\cdots, \tilde n_k)}{p(n_1, \cdots, n_i ,\cdots, n_k)} \\ \end{align*}\] \[\begin{align*} \text{where } \tilde n_j &= n_j \enspace \enspace \enspace \enspace \text{ if }j \neq i \\ &= n_j +1 \enspace \text{ if }j=i \end{align*}\]

• EPPF인 $p$는 permutation에 대해 symmetric하므로,

\[\begin{align*} p_i(n_1, \cdots, n_k) &= \frac{p(\tilde n_{\sigma(1)}, \cdots, \tilde n_{\sigma(i)} ,\cdots, \tilde n_{\sigma(k)})}{p(n_{\sigma(1)}, \cdots, n_{\sigma(i)} ,\cdots, n_{\sigma(k)})} \end{align*}\]

• 분자를 자세히 보면 $\tilde n_j$의 정의에 의해, $\sigma(j)=i$가 되는 $j$ 번째 argument, 즉 $j= \sigma^{-1}(i)$ 번째 argument에서 1이 더해지는 것을 볼 수있다. 왜냐하면 $\tilde n_{\sigma(j)}=n_\sigma(j)+1, \text{ if } \sigma(j)=i$, i.e., $j= \sigma^{-1}(i)$이기 때문이다. 따라서,

\[p_i(n_1, \cdots, n_k) = p_{\sigma^{-1}(i)}(n_{\sigma(1)} , \cdots, n_{\sigma(k)})\]

Sufficiency

Putative PPF, $p_j$에 대하여 위 세 조건이 만족할 때, 그를 바탕으로 construct된 $p$가 어떤 infinite exchangeable random partition의 EPPF가 됨을 보이자. 먼저 위 과정에 의해 주어진 putative PPF로부터 함수 $p$가 유일하게 잘 정의되는지를 확인하자. 그를 위해 몇 가지 필요한 notation이 있는데 다음과 같다. 어떤 partition of $\mathbb N_n$, $\Pi = { A_1, \cdots , A_k }$에 대해,

• $\Pi_m$은 $\Pi$의 $\mathbb N_m$ 위에서의 restriction이다.
• $\mathbf n (\Pi) = (n_1, \cdots , n_k)$는 partition $\Pi$의 결과로 얻어진 composition of $n$이다. $n_i$는 $i$번째 set의 cardinality를 의미한다.
• $\Pi(i)$는 partition $\Pi$ 하에서 원소 $i$의 class index를 나타낸다.

같은 composition $\mathbf n = n (\Pi) = n (\tilde \Pi) = (n_1, \cdots , n_k)$을 갖는 $\mathbb N_n$의 두 partition, $\Pi$와 $\tilde \Pi$를 생각해보자. 다음과 같이 함수 $p^\Pi(\mathbf n)$과 $p^{\tilde \Pi}(\mathbf n)$를 정의하자.

\[p^\Pi(\mathbf n) = \prod_{i=2}^{n} p_{\Pi(i)}\Big(\mathbf n(\Pi_{i-1}) \Big) = p_{\Pi(2)}\Big(\mathbf n(\Pi_1) \Big) \cdot p_{\Pi(3)}\Big(\mathbf n(\Pi_2) \Big) \cdot \text{ } \cdots \text{ }\cdot p_{\Pi(n)}\Big(\mathbf n(\Pi_{n-1}) \Big)\] \[p^{\tilde \Pi}(\mathbf n) = \prod_{i=2}^{n} p_{ \tilde \Pi (i)}\Big(\mathbf n(\tilde \Pi_{i-1}) \Big) = p_{ \tilde \Pi (2)}\Big(\mathbf n(\tilde \Pi_1) \Big) \cdot p_{ \tilde \Pi (3) }\Big(\mathbf n(\tilde \Pi_2) \Big) \cdot \text{ } \cdots \text{ }\cdot p_{ \tilde \Pi (n) }\Big(\mathbf n(\tilde \Pi_{n-1}) \Big)\]

즉, $p^\Pi(\mathbf n)$과 $p^{\tilde \Pi}(\mathbf n)$은 주어진 putative PPF를 이용하여 위의 과정대로 $p$를 만들되, 같은 composition $\mathbf n$으로 이어지는 서로 다른 두 partition에 대해 그 과정을 수행한 것이다. Composition에 대한 함수들의 sequence $p$가 unique하게 정의되려면 $p^\Pi(\mathbf n)$과 $p^{\tilde \Pi}(\mathbf n)$가 같은 값을 가져야 한다. 일반성을 잃지 않고 우리는 두 partition을 다음과 같이 나타낼 수 있다.

\[\Pi(\mathbb N_n) = (1, \cdots, 1, 2, \cdots, 2,\cdots, k, \cdots, k) \\ \tilde \Pi(\mathbb N_n) = \sigma(\Pi(\mathbb N_n) ) \text{ for some permutation }\sigma\]

그런데 우리는 두 번째 조건에 의해 “$j$번째 class에 원소 한 개를 추가하는 작업”과 “$k$번째 class에 원소 한 개를 추가하는 작업”이 서로 순서를 바꾸어도 $p$의 값은 같다는 것을 알고 있다. 임의의 permutation은 transposition을 finite번 수행하는 것으로 나타낼 수 있으므로 다음 사실이 증명되었다. 즉 위 과정에 의해 함수 $p$가 유일하게 정의된다.

\[p^\Pi(\mathbf n)=p^{\tilde \Pi}(\mathbf n), \enspace \text{ for any partition of }\mathbb N_n, \Pi, \tilde \Pi\]

이제 위 과정에 의해 putative PPF로부터 정의된 함수 $p$가 exchangeable, 즉 group index의 permutation에 invariant하다는 것을 보이자. 임의의 composition $\mathbf n= (n_1, \cdots , n_k)$과 permutation $\sigma$가 주어졌다고 하자. 우리는 다음을 보이고자 한다.

\[p(n_1, \cdots , n_k)=p(n_{\sigma(1)}, \cdots , n_{\sigma(k)})\]

다음을 만족하는 partition of $\mathbb N_n$, $\Pi$를 생각하자. 아래의 두 번째 식의 우변은, 처음 $k$개의 원소는 $1,\cdots, k$이고, 그 뒤로는 $i$가 $n_i-1$번씩 연달아 나타났음을 의미한다.

\[\begin{align*} \mathbf n (\Pi) &= (n_1, \cdots , n_k) \\ \Pi(\mathbb N_n) &= (1,2,\cdots, k, 1,\cdots, 1, 2,\cdots,2,\cdots, k,\cdots,k) \end{align*}\]

위에서와 같은 방법으로 함수 $p$를 construct하면 아래와 같다.

\[p(\mathbf n) = \left( \prod_{i=2}^k p_i( \mathbf 1_{(i-1)}) \right) \left( \prod_{i=k+1}^n p_{\Pi(i)}\Big(\mathbf n(\Pi_{i-1}) \right)\]

이제 $\sigma$로 group index를 permute한 composition인 $(n_{\sigma(1)}, \cdots , n_{\sigma(k)})$을 composition으로 갖는 partition, $\Xi$를 생각해보자. 아래 두 번째 식의 우변은, 처음 $k$개의 원소는 $1,\cdots, k$이고, 그 뒤로는 $\sigma^{-1}(i)$가 $n_i-1$번씩 연달아 나타났음을 의미한다.

\[\begin{align*} \mathbf n (\Xi) &= (n_{\sigma(1)}, \cdots , n_{\sigma(k)}) \\ \Xi(\mathbb N_n) &= (1,2,\cdots, k, \sigma^{-1}(1),\cdots, \sigma^{-1}(1), \sigma^{-1}(2),\cdots,\sigma^{-1}(2),\cdots,\sigma^{-1}(k),\cdots,\sigma^{-1}(k)) \end{align*}\]

마찬가지로 함수 $p$를 construct하면, 다음과 같다. 두 번째 등호는 보조정리의 세 번째 조건에 의해 성립한다.

\[\begin{align*} p(n_{\sigma(1)}, \cdots , n_{\sigma(k)}) &= \left( \prod_{i=2}^k p_i( \mathbf 1_{(i-1)}) \right) \left( \prod_{i=k+1}^n p_{\Xi(i)}\Big(\mathbf n(\Xi_{i-1}) \right) \\ &= \left( \prod_{i=2}^k p_i( \mathbf 1_{(i-1)}) \right) \left( \prod_{i=k+1}^n p_{\sigma^{-1}(\Xi(i))}\Big(\mathbf n(\sigma(\Xi_{i-1})) \right) \\ &= \left( \prod_{i=2}^k p_i( \mathbf 1_{(i-1)}) \right)\left( \prod_{i=k+1}^n p_{\Pi(i)}\Big(\mathbf n(\Pi_{i-1}) \right) \\ &= p(\mathbf n) \end{align*}\]

따라서 위 세 조건을 만족하는 putative PPF로부터 construct된 $p$는 EPPF의 성질을 만족한다.

Conclusion of the lemma

Putative PPF가 위 세 조건을 만족한다는 사실은, putative PPF로부터 EPPF를 construct할 수 있다는 사실과 동치이다. $\square$

어떤 주어진 EPPF에 대해, 이를 EPPF로 갖는 infinite exchangeable random partition이 존재한다는 것은 위의 Theorem 7과 From EPPF to an Infinite Exchangeable Random Partition에서 소개한 내용이다.

5.1.1 The Chinese Restaurant Process

Definition

The infinite exchangeable random partition generated by a sample from the Dirichlet process $\text{DP}(\alpha_0 G_0)$ with atomless center measure $G_0$ is called the Chinese restaurant process(CRP) with parameter $\alpha_0$

Chinese restaurant process란 Dirichlet process에서 generate된 sample, 정확히는 $P \sim \text{DP}(\alpha_0 G_0)$, $X_1, \cdots , X_N \vert P \stackrel{iid}{\sim} P$로부터 생성된 sample로부터 generate된 infinite exchangeable random partition이다.

Exchangeable Partition Probability Function

Chinese restaurant process의 EPPF는 다음과 같다.

A random sample $X_1, \cdots , X_n$ from a Dirichlet process with atomless base measure of strength $\vert \alpha \vert = \alpha_0$ induces a given partition of $\mathbb N_n$ into $k$ sets of sizes $n_1, \cdots, n_k$ with probability equal to

\[p(n_1, \cdots, n_k) = \frac{\alpha_0^k \prod_{i=1}^{k}(n_i-1)!}{\alpha_0^{[n]}}= \frac{\alpha_0^k \Gamma(\alpha_0) \prod_{i=1}^{k}\Gamma(n_i)}{\Gamma(\alpha_0 +n)},\]

where $a^{[k]}=a(a+1) \cdots (a+k-1)$ stands for the ascending factorial.

그 증명은 다음과 같다. Dirichlet process로부터 생성된 sample의 joint 분포는 exchangeable하기 때문에, 확률은 각 partitioning set의 size에만 영향을 받는다. 따라서 $(n_1, \cdots, n_k)$을 composition으로 갖는 partition $\Pi$를 다음과 같이 설정한다.

\[\Pi(\mathbb N_n) = (1, \cdots , 1 , 2, \cdots, 2, \cdots, k, \cdots, k)\]

Dirichlet process의 marginal & conditional distribution에 대해 소개할 때, Dirichlet process의 predictive distribution의 sequence를 다음과 같이 나타낼 수 있다는 것을 확인했다.

\[X_i \vert X_1 , \cdots , X_{i-1} = \begin{cases} \delta_{X_{1}} &\quad\text{with probability } \frac{1}{\alpha_0 +i-1}\\ \enspace \vdots &\quad \enspace \enspace \enspace \vdots\\ \delta_{X_{i-1}} &\quad\text{with probability } \frac{1}{\alpha_0 +i-1}\\ G_0 &\quad\text{with probability } \frac{\alpha_0}{\alpha_0 +i-1}\\ \end{cases}\]

따라서, 위의 $\Pi(\mathbb N_n)$을 순서대로 뽑는 확률은 다음과 같다.

\[\begin{align*} &P(X_1 = x_1, \cdots, X_{n_1} = x_1, X_{n_1+1} = x_2, \cdots, X_{n_1+n_2} = x_2, \cdots, X_n = x_k) \\ =&\frac{\alpha_0}{\alpha_0}\frac{1}{\alpha_0 + 1} \cdots \frac{n_1-1}{\alpha_0+n_1-1} \times \cdots \times \frac{\alpha_0}{\alpha_0 + \sum_{i=1}^{k-1}n_i} \frac{1}{\alpha_0 + \sum_{i=1}^{k-1}n_i+ 1} \cdots \frac{n_k-1}{\alpha_0+ \sum_{i=1}^{k-1}n_i+n_k-1} \\ = &\frac{\alpha_0^k \prod_{i=1}^{k}(n_i-1)!}{\alpha_0^{[n]}} \\ = &p(n_1, \cdots, n_k). \enspace \square \end{align*}\]

Prediction Proability Function

PPF, $p_j (\mathbf n)$의 정의는 다음과 같이 composition $\mathbf n$이 주어졌을 때 $j$ 번째 partitioning set에 $n+1$ 번째 원소가 들어갈 조건부 확률이다.

\[p_j (\mathbf n) = \frac{p(\mathbf n^{j+})}{p (\mathbf n) }, \enspace \enspace j=1,\cdots, k+1\]

따라서 증명할 필요도 없이, Dirichlet process의 conditional distribution에 따라 Chinese restaurant process의 PPF는 다음과 같은 generalized Polya urn scheme의 결과를 따른다.

\[p_j(\mathbf n) = \frac{n_j}{\alpha_0 + n}, \enspace \enspace p_{k+1}(\mathbf n) = \frac{\alpha_0}{\alpha_0 + n}\]

이 식의 의미를 살펴보자면 새 원소가 이미 있는 partitioning set에 속할 확률은 이미 그 partitioning set에 속해있는 원소들의 수에 비례한다. 이미 많은 원소를 가진 partitioning set은 새 원소에 더 큰 포함확률을 갖고, 이는 새 원소가 들어올 수록 더욱 커지기 때문에 이와 같은 성질을 “The rich get richer”라고도 표현한다. 또한, 새 원소가 새로운 partitioning set에 속하게 될 확률은 CRP의 parameter $\alpha_0$의 지배를 받는다.

“Chinese restaurant” process라는 이름은 다음과 같은 비유에서 유래했다. 무한개의 테이블이 있는 중국음식점에 손님들이 한 명 씩 들어오는 상황을 가정하자. 각 테이블에 앉을 수 있는 최대 사람 수의 제한은 없다. 첫 손님은 임의의 테이블을 고른다. 두 번째와 그 이후의 손님들은 위의 PPF 식의 확률에 따라 다른 손님들이 이미 앉아있는 테이블에 앉을지 새로운 테이블에 앉을지 결정한다. 이 그림을 통해 예를 들면, 여덟명의 손님이 어디앉았는지 주어졌을 때, 새로운 아홉 번째 손님이 첫 번째 테이블에 앉을 확률은 $\frac{3}{\alpha_0 + 8}$, 두 번째 테이블에 앉을 확률은 $\frac{4}{\alpha_0 + 8}$, 세 번째 테이블에 앉을 확률은 $\frac{1}{\alpha_0 + 8}$, 그리고 새로운 테이블에 앉을 확률은 $\frac{\alpha_0}{\alpha_0 + 8}$이 된다.

Proposition 9

Proposition 9과 관련된 내용은 Lemma 8과 마찬가지로, Lee, J. et al. (2013). Defining predictive probability functions for species sampling models.에 기반하여 작성되었다.

PPF, $p_j$가 $j$번째 partitioning set의 cardinality $n_j$에만 depend하는 어떤 함수 $f(n_j)$에 비례하고, 새로운 partitioning set에 대한 PPF, $p_{k+1}$은 $n_1, \cdots, n_k$에 영향을 받지 않는 함수 형태라면, 그로부터 generate된 infinite exchangeable random partition은 항상 Chinese restaurant process가 된다.

The Chinese restaurant process is the only exchangeable random partition with PPF $(p_j : j \in \mathbb N)$ of the form, for some function $f: \mathbb N \rightarrow (0,\infty)$ not depending on $j$, some $\alpha_0 >0$, and every composition $(n_1, \cdots, n_k)$,

\[p_j(n_1, \cdots, n_k) \propto \begin{cases} f(n_j), &\quad j=1,\cdots, k \\ \alpha_0, &\quad j = k+1 \\ \end{cases}\]

증명은 다음과 같다. 조건에서 주어진 비례관계를 이용해, 실제 PPF의 식을 써보면 다음과 같다.

\[p_j(n_1, \cdots, n_k) = \begin{cases} \frac{f(n_j)}{\sum_{u=1}^{k} f(n_u) + \alpha_0}, &\quad j=1,\cdots, k \\ \frac{\alpha_0}{\sum_{u=1}^{k} f(n_u) + \alpha_0}, &\quad j = k+1 \\ \end{cases}\]

우리는 PPF가 만족하는 조건 세 가지를 Lemma 8에서 확인했는데, 그 중 두 번째 조건을 이용하면 모든 $1 \leq i \neq j \leq k, k \in \mathbb N$에 대해 다음이 만족하는 것을 알 수 있다.

\[\begin{align*} p_i(\mathbf n)p_j(\mathbf n^{i+}) &= p_j(\mathbf n)p_i(\mathbf n^{j+}) \\ \frac{f(n_i)}{\sum_{u=1}^{k} f(n_u) + \alpha_0} \frac{f(n_j)}{\sum_{u=1,u \neq i}^{k} f(n_u) + f(n_i + 1 )+ \alpha_0} &= \frac{f(n_j)}{\sum_{u=1}^{k} f(n_u) + \alpha_0} \frac{f(n_i)}{\sum_{u=1,u \neq j}^{k} f(n_u) + f(n_j + 1 )+ \alpha_0} \\ \sum_{u=1,u \neq j}^{k} f(n_u) + f(n_j + 1 )+ \alpha_0 &= \sum_{u=1,u \neq i}^{k} f(n_u) + f(n_i + 1 )+ \alpha_0 \\ f(n_j+1) - f(n_j) &= f(n_i+1)-f(n_i) \\ \end{align*}\]

따라서 모든 $1 \leq i \neq j \leq k, k \in \mathbb N$에 대해 위 식을 만족하는 $f(m)$은 다음과 같은 선형 함수이다.

\[f(m) = am+b, \text{ for some }a,b \in \mathbb R\]

같은 방법으로 $i=k+1, 1 \leq j \leq k, k \in \mathbb N$에 대해 Lemma 8의 두 번째 조건을 적용하면,

\[\begin{align*} p_{k+1}(\mathbf n)p_j(\mathbf n^{(k+1)+}) &= p_j(\mathbf n)p_{k+1}(\mathbf n^{j+}) \\ \frac{\alpha_0}{\sum_{u=1}^{k} f(n_u) + \alpha_0} \frac{f(n_j)}{\sum_{u=1}^{k} f(n_u) + f(1 )+ \alpha_0} &= \frac{f(n_j)}{\sum_{u=1}^{k} f(n_u) + \alpha_0} \frac{\alpha_0}{\sum_{u=1,u \neq j}^{k} f(n_u) + f(n_j + 1 )+ \alpha_0} \\ \sum_{u=1,u \neq j}^{k} f(n_u) + f(n_j + 1 )+ \alpha_0&= \sum_{u=1}^{k} f(n_u) + f( 1 )+ \alpha_0 \\ f(n_j+1) - f(n_j) &= f(1) \\ \end{align*}\]

이 결과와 위의 결과를 종합하면 $f(m)$은 다음과 같다. $b=0$이기 때문에 $f(m)>0$이기 위해서 $a>0$의 조건이 추가되었다.

\[f(m) = am, \text{ for some }a >0\]

따라서 우리의 PPF는 다음과 같다.

\[p_j(n_1, \cdots, n_k) = \begin{cases} \frac{an_j}{\sum_{u=1}^{k} an_u + \alpha_0}, &\quad j=1,\cdots, k \\ \frac{\alpha_0}{\sum_{u=1}^{k} an_u + \alpha_0}, &\quad j = k+1 \\ \end{cases}\]

이로부터 EPPF를 construct하면 다음과 같다. EPPF는 exchangeable random partition의 composition of $n$에 대한 함수이고, 각 partition의 원소의 개수에만 영향을 받기 때문에, 임의로 다음과 같이 $i$가 $n_i$번 연달아 나오는 partition $\Pi$를 설정하고 EPPF를 도출해도 무방하다.

\[\Pi(\mathbb N_n) = (1, \cdots, 1,2,\cdots, 2, \cdots, k,\cdots, k)\] \[\begin{align*} &p(n_1, n_2, \cdots, n_k) \\ &= \frac{\alpha_0}{\alpha_0} \frac{a \cdot 1}{\alpha_0 + a \cdot 1} \cdots \frac{a(n_1-1)}{\alpha_0+a (n_1-1)} \times \cdots \times \frac{\alpha_0}{\alpha_0 + \sum_{i=1}^{k-1} a \cdot n_i} \frac{a \cdot 1}{\alpha_0 + \sum_{i=1}^{k-1} a \cdot n_i+ a \cdot 1} \cdots \frac{a (n_k-1)}{\alpha_0+ \sum_{i=1}^{k-1} a \cdot n_i+ a (n_k-1)} \\ &= \frac{\frac{\alpha_0}{a}}{\frac{\alpha_0}{a}}\frac{1}{\frac{\alpha_0}{a} + 1} \cdots \frac{n_1-1}{\frac{\alpha_0}{a} +n_1-1} \times \cdots \times \frac{\frac{\alpha_0}{a}}{\frac{\alpha_0}{a} + \sum_{i=1}^{k-1}n_i} \frac{1}{\frac{\alpha_0}{a} + \sum_{i=1}^{k-1}n_i+ 1} \cdots \frac{n_k-1}{\frac{\alpha_0}{a}+ \sum_{i=1}^{k-1}n_i+n_k-1} \\ &= \frac{(\frac{\alpha_0}{a})^k \prod_{i=1}^{k}(n_i-1)!}{(\frac{\alpha_0}{a})^{[n]}}\\ \end{align*}\]

이는 ${\alpha_0}/{a}$를 parameter로 갖는 Chinese restaurant process의 EPPF라는 것을 알 수 있다. $\square$