Question about implementing nested Chinese Restaurant Process (nCRP)

Question

I am trying to follow the original paper on nCRP by Blei et al., 2010 and am confused with it's implementation.

The authors describe the analogy for an nCRP as follows:

A tourist arrives at the city for an culinary vacation.On the first evening, he enters the root Chinese restaurant and selects a table using the CRP distribution in Eq. (1). On the second evening, he goes to the restaurant identified on the first night’s table and chooses a second table using a CRP distribution based on the occupancy pattern of the tables in the second night’s restaurant. He repeats this process forever. After M tourists have been on vacation in the city, the collection of paths describes a random subtree of the infinnite tree; this subtree has a branching factor of at most M at all nodes.

If I understand this right, a sample from an nCRP is a vector $c = [c_1, c_2, c_3]$ where $c_i$ stands for table index at $i^{th}$ level of the tree.

Given that,

On the second evening, he goes to the restaurant identified on the first night’s table and chooses a second table

are the samples $c_i$ and $c_{i-1}$ dependent?

How is the information about sampling $c_i$ based on $c_{i-1}$ encoded in an nCRP? Why is there no parameter identifying the dependence between the tables at each level?

... or am I not understanding nCRP properly?

Answer 1

A sample from an nCRP is an $L$-depth path through the infinitely branching, infinitely deep tree: Each element of $\textbf{c}_d$ refers to a metaphorical restaurant. From Blei et al 2010:

More formally, consider the infinite tree defined by the nCRP and let $\textbf{c}_d$ denote the path through that tree for the $d$th customer (i.e., document).

Each of those restaurants has an infinite number of tables referring to other restaurants aren't shared across restaurants. This answers the question of how dependence is encoded, though I find this clearer when reading from Blei et al 2003, emphasis mine:

Suppose that there are an infinite number of infinite-table Chinese restaurants in a city. One restaurant is determined to be the root restaurant and on each of its infinite tables is a card with the name of another restaurant. On each of the tables in those restaurants are cards that refer to other restaurants, and this structure repeats infinitely. Each restaurant is referred to exactly once; thus, the restaurants in the city are organized into an infinitely-branched tree.

[...]

1. Let $c_1$ be the root restaurant.
2. For each level $\ell \in \left\{2, . . . , L\right\}$: (a) Draw a table from restaurant $c_{\ell - 1}$ using Eq. (1). Set $c_{\ell}$ to be the restaurant referred to by that table.
3. Draw an $L$-dimensional topic proportion vector $\theta$ from Dir($\alpha$).
4. For each word $n \in \left\{1, . . . , N\right\}$: (a) Draw $z \in \left\{1, . . . , L\right\}$ from Mult($\theta$). (b) Draw $w_n$ from the topic associated with restaurant $c_z$.

Put another way, you can think of each restaurant as being associated with two distributions:

1. A distribution over words, i.e. a "topic."
2. A distribution over an infinite number of other restaurants, none of which are referred to by other restaurants' distributions.

I myself find it more intuitive to think through the second point using the topic intuition. Take this path through the tree in Fig. 5 of Blei et al 2003 for example: The top node is English function words; the right node of the second level are terms related to machine learning; the right-most on the third level holds reinforcement learning terms.

In that example, you can only get to the topic of reinforcement learning by going through that of machine learning. Much like how it's difficult to imagine writing a document about reinforcement learning without using terms from machine learning.