Griffiths 2011 - Equivalence Classes and the Infinite Limit

Summary

Binary matrices are identified up to column permutation via the left-ordered form $\text{lof}(Z)$. The limit $K\to \infty$ of $P([Z])$ exists and equals $\frac{{\alpha }^{K_{+}}}{{\prod }_{h=1}^{2^N-1}{K}_h!}\exp (-\alpha H_N){\prod }_{k=1}^{K_{+}}\frac{(N-m_k)!(m_k-1)!}{N!}$.

Main Content

History and left-ordered form

The history of feature $k$ at object $i$ is $(z_{1k},\dots ,z_{(i-1)k})$; the full history is $(z_{1k},\dots ,z_{Nk})$, identified with its decimal value $h\in \{0,\dots ,2^N-1\}$ (first row most significant). $K_h$ = number of columns with history $h$; $K_0$ = number of empty columns; $K_{+}={\sum }_{h\ge 1}{K}_h$; $K=K_0+K_{+}$. $\text{lof}(Z)$ orders columns left to right by the magnitude of the binary number each column expresses (first row most significant), so columns with $z_{1k}=1$ are grouped at the left (the paper’s text also describes this as ordering by history); two matrices are lof-equivalent if $\text{lof}(Y)=\text{lof}(Z)$. The class is $[Z]$.

The class $[Z]$ is preserved by permuting rows or columns (with the same permutation applied across class members). Class matrices generated by assignment vectors correspond exactly to partitions, so lof-classes are to binary matrices what partitions are to assignment vectors. Cardinality: $|[Z]|=\frac{K!}{{\prod }_{h=0}^{2^N-1}{K}_h!}$ (fewer if columns repeat).

Infinite limit (Eqs. 12-14)

$$P([Z])=\frac{K!}{{\prod }_{h=0}^{2^N-1}{K}_h!}\prod _{k=1}^K\frac{\frac{\alpha }{K}\Gamma (m_k+\frac{\alpha }{K})\Gamma (N-m_k+1)}{\Gamma (N+1+\frac{\alpha }{K})}$$

and as $K\to \infty$

$$P([Z])\to \frac{{\alpha }^{K_{+}}}{{\prod }_{h=1}^{2^N-1}{K}_h!}\exp \{-\alpha H_N\}\prod _{k=1}^{K_{+}}\frac{(N-m_k)!(m_k-1)!}{N!},H_N=\sum _{j=1}^N\frac{1}{j}.$$

Proof sketch (Eqs. 13-14, Appendix A): with $x=\alpha /K$, an empty column has probability $x\Gamma (x)\Gamma (N+1)/\Gamma (N+1+x)=N!/{\prod }_{j=1}^N(j+x)$; a used column differs from this by the factor $x(N-m_k)!{\prod }_{j=1}^{m_k-1}(j+x)/N!$. Hence $P(Z)=[N!/{\prod }_j(j+x){]}^K{\prod }_{k\le K_{+}}x(N-m_k)!{\prod }_{j<m_k}(j+x)/N!$. As $K\to \infty$: $[{\prod }_{j=1}^N(1+\frac{\alpha }{jK}){]}^{-K}\to e^{-\alpha H_N}$; ${\prod }_{j<m_k}(j+x)\to (m_k-1)!$; and $K!/(K_0!K^{K_{+}})\to 1$ cancels the $K^{-K_{+}}$ left in $x^{K_{+}}$ to give ${\alpha }^{K_{+}}$. The result is exchangeable: only the multiset of histories matters.

Examples

Left-ordering a 3x4 matrix

Columns with histories $(1,0,1)=5$, $(0,1,0)=2$, $(1,1,1)=7$, $(1,0,1)=5$. Sorted descending by binary value: $7,5,5,2$. Here $K_7=1,K_5=2,K_2=1$, so $|[Z]|=4!/(1!2!1!)=12$ distinct column orderings.

Connections

Binary-matrix analogue of partitions, see Griffiths 2011 - Infinite Mixtures and the CRP Review. Generative description of the same law: Griffiths 2011 - The Indian Buffet Process and Its Properties.

See Also

Griffiths 2011 - The Indian Buffet Process - Overview