text:
# The Hexagonal Property of Pascal's Triangle

Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that:

• the product of non-adjacent vertices is constant.

• the greatest common divisor of non-adjacent vertices is constant.

Below is one such hexagon. As an example, here we have that $$4 \cdot 10 \cdot 15 = 6 \cdot 20 \cdot 5$$, as well as $$\gcd(4, 10, 15) = \gcd(6,20,5)$$.

$$1 \\ 1 \qquad 1\\ 1\qquad 2\qquad 1\\ 1\qquad3\qquad3\qquad1\\ 1\qquad\mathbf{4}\qquad\mathbf{6}\qquad4\qquad1\\ 1\qquad\mathbf{5}\qquad10\qquad\mathbf{10}\qquad5\qquad1 \\ 1\qquad6\qquad\mathbf{15}\qquad\mathbf{20}\qquad15\qquad6\qquad1$$

There is a quick proof here (pdf). The original proof should be in V. E. Hoggatt, Jr., & W. Hansell. "The Hidden Hexagon Squares." The Fibonacci Quarterly 9(1971):120, 133. but I cannot access it.

I am, however, intereseted in a purely combinatorial proof. I do not know how to approach this at all: I cannot see what the non-adjacent vertices represent and/or I do not know how to remodel their meaning. Can anyone help?

EDIT: To specify my question more closely, what I am looking for is some natural bijection between the two sets of triads that create the hexagon.

Thanks.

• The Hoggatt and Hansell article has now been brought online: page 1, page 2. I don't think, however, that it helps with your question. – Will Orrick Jan 28 '14 at 18:08
• About the BOUNTY: Mitch's answer provides a combinatorial interpretation of each side of the identity, showing that each side counts a certain collection of sets. His answer does not, however, show these two collections to be equinumerous, and therefore is NOT A PROOF. His answer asserts that the two collections are, in fact, the same, which would immediately establish that they are equinumerous, but this assertion is INCORRECT, as demonstrated in the comments. I am offering the bounty in hopes that someone will find a bijection between the two collections. – Will Orrick Mar 16 '14 at 14:43

In symbols, the identity is

$$\left({n-1\atop m-1}\right)\left({n\atop m+1}\right)\left({n+1\atop m}\right) = \left({n\atop m-1}\right)\left({n-1\atop m}\right)\left({n+1\atop m+1}\right).$$

The usual combinatorial interpretation of a binomial coefficient $\left({n\atop m}\right)$ is that it counts subsets of size $m$ from a set of size $n$. Multiplication is usually interpreted as mutually exclusive choice ($f(n)g(n)$ counts the process of picking $f(n)$ configurations, then picking (independently) $g(n)$ items.

Putting this together, the LHS counts subsets of size $m-1$ from a set of size $n-1$, then subsets of size $m$ from an (independent) set of size $n+1$, then (again independently) subsets of size $m+1$ from a set of size $n$. This corresponds one-to-one with the RHS because the things counted by the LHS can be counted in a different way by the RHS: For the RHS distinguish an element of the $n$ set and one of the $n+1$ set. What's left over for those two sets can be chosen by $\left({n-1\atop (m+1)-1}\right)$ and $\left({(n+1)-1\atop m-1}\right)$ respectively, and then the two distinguished elements can be included to be (possibly) chosen in the $n-1$ set to account for $\left({(n-1) +2 \atop (m-1)+2}\right)$.

To be clearer about the combinatorial interpretation, there are three sets, of size $n-1$, $n$, and $n+1$, from which you choose subsets of size $m-1$, $m+1$, and $m$, respectively. Another way to count this situation is to, take 1 item each out of the $n$ and $n+1$ sets, and add them to the $n-1$ set. So now you're counting out of sets of size $n+1$, $n-1$, and $n$, from which you choose subsets of size $m+1$, $m$, and $m-1$, respectively.

• @milcak: I added a paragraph stating more clearly the combinatorial part. I am not using the arithmetic of factorials in my proof, simply using the combinatorial interpretation of binomial coefficients as counting subsets and counting one situation in two different ways. – Mitch Feb 7 '11 at 18:11
• @milcak This proof is completely combinatorial: it combinatorially interprets the two sides of the equality you want to prove and then combinatorially establishes the equality. I don't see what more you want. – Alex B. Feb 21 '11 at 5:20
• @milcak: can you give an example of a proof of an identity involving just binomial coefficients that would be sufficient to be called 'combinatorial' by you? You may want to explain to what degree your example is 'pure' or avoids the use of 'how pascal's triangle is constructed'. (before dismissing my example, you should confirm that it does not use Pascal's identity) – Mitch Feb 23 '11 at 3:20
• @AlexB., Mitch : I'm somehow not yet able to see the bijection in this proof. Let's say that the set of size $n-1$ consists of red balls, the set of size $n$ consists of green balls, and the set of size $n+1$ consists of blue balls. On one side, we have selections of $m-1$ balls from a set $n-1$ red balls, $m+1$ balls from a set of $n$ green balls, and $m$ balls from a set of $n+1$ blue balls. On the other, we have selections of... – Will Orrick Jan 20 '14 at 21:41
• … $m+1$ balls from a set containing $n-1$ red balls, one green ball, and one blue ball, $m$ balls from a set of $n-1$ green balls, and $m-1$ balls from a set of $n$ blue balls. The selections on the left all have $m-1$ red, $m+1$ green, and $m$ blue balls, but the selections on the right don't necessarily have this color composition. For instance, a selection on the right might instead have $m+1$ red balls, $m$ green balls, and $m-1$ blue balls. Or $m$ red balls, $m+1$ green balls, and $m-1$ blue balls. Or $m$ red balls, $m$ green balls, and $m$ blue balls. – Will Orrick Jan 20 '14 at 21:44

I've left some questions as comments to Mitch's answer, and am hoping that my confusions about that answer will get cleared up soon. Meanwhile, I started to think about how I would approach this problem. I don't have a satisfying answer yet; the best I've been able to come up with requires introducing an additional factor on both sides of the identity. The modified identity (which is algebraically equivalent to the unmodified one) has a clear combinatorial meaning, but I don't yet see a way to interpret the unmodified identity in combinatorial terms.

It's nice to generalize the identity slightly. Starting with the identity as written in Mitch's answer, $$\binom{n - 1}{m - 1} \binom{n}{m + 1} \binom{n + 1}{m} = \binom{n}{m - 1} \binom{n - 1}{m} \binom{n + 1}{m + 1},$$ we replace the $$1$$ with $$r$$ everywhere to obtain $$\binom{n - r}{m - r} \binom{n}{m + r} \binom{n + r}{m} = \binom{n}{m - r} \binom{n - r}{m} \binom{n + r}{m + r}.$$ This is also an identity, as we show below. Just as in the original identity, the binomial coefficients that appear form the vertices of a hexagon (which we might call the radius-$$r$$ hexagon) centered at $$\binom{n}{m}$$ in Pascal's triangle. Note that the GCD property mentioned in the original post only holds for $$r=1,$$ while the identity holds for all $$r.$$ We concern ourselves only with the identity.

We prove the radius-$$r$$ identity starting from an elementary identity relating different ways of representing the trinomial coefficient as a product of binomial coefficients: $$\binom{n}{k}\binom{k}{a}=\binom{n}{a}\binom{n-a}{k-a}=\binom{n}{n-k,k-a,a}.$$ This has a combinatorial interpretation, as discussed here. The following three variants of this identity are useful here: \begin{aligned} \binom{n}{r}\binom{n-r}{m-r}&=\binom{n-m+r}{r}\binom{n}{m-r}\\ \binom{m+r}{r}\binom{n}{m+r}&=\binom{n}{r}\binom{n-r}{m}\\ \binom{n-m+r}{r}\binom{n+r}{m}&=\binom{m+r}{r}\binom{n+r}{m+r}. \end{aligned} The rightmost factors on the left side of these equations match the three factors on the left side of the identity, while the rightmost factors on the right side of these equations match the three factors on the right side of the identity. Furthermore, the leftmost factors on the left side of these equations are the same, but permuted, as the leftmost factors on the right side of these equations.

These observations suggest the idea of multiplying both sides of the radius-$$r$$ identity by $$\binom{n}{r}\binom{m+r}{r}\binom{n-m+r}{r}$$ to get \begin{aligned} &\binom{n}{r}\binom{n - r}{m - r} \cdot \binom{m+r}{r}\binom{n}{m + r} \cdot \binom{n-m+r}{r}\binom{n + r}{m}\\ &\qquad= \binom{n-m+r}{r}\binom{n}{m - r} \cdot \binom{n}{r}\binom{n - r}{m} \cdot \binom{m+r}{r}\binom{n + r}{m + r}. \end{aligned} The two sides of this identity can be thought of as different ways of answering the following question: there are $$n$$ students, $$n$$ teachers, and $$n+r$$ administrators. A committee is to be formed having $$m$$ students $$m+r$$ teachers, and $$m+r$$ administrators. From this committee, a subcommittee is to be formed having $$r$$ students, $$r$$ teachers, and $$r$$ administrators. In how many ways can this be done?

On the left side, this is accomplished by

• choosing $$r$$ students to be on the subcommittee, then choosing $$m-r$$ additional students to fill out the committee,
• choosing $$m+r$$ teachers to be on the committee, then from these choosing $$r$$ to be on the subcommittee,
• choosing $$m$$ administrators to be on the committee but not the subcommittee, then choosing $$r$$ additional administrators to be on the subcommittee.

On the right side, it is accomplished by

• choosing $$m-r$$ students to be on the committee but not the subcommittee, then choosing $$r$$ additional students to be on the subcommittee,
• choosing $$r$$ teachers to be on the subcommittee, then choosing $$m$$ additional teachers to fill out the committee,
• choosing $$m+r$$ administrators to be on the committee, then from these choosing $$r$$ to be on the subcommittee.

Clearly we get the same set of committee and subcommittee assignments either way, so the two sides must be equal.

This proof is unsatisfactory since we had to multiply the identity by the extraneous factor $$\binom{n}{r}\binom{m+r}{r}\binom{n-m+r}{r}$$ in order to be able to state our combinatorial interpretation. I have not yet been able to find a method that avoids this.

Added 26 January 2014: I should have looked at the linked pdf in the question before posting. There the identity is further generalized to $$\binom{n - r}{m - s} \binom{n}{m + r} \binom{n + s}{m} = \binom{n}{m - s} \binom{n - r}{m} \binom{n + s}{m + r},\qquad\qquad(*)$$ which corresponds to a hexagon with side lengths alternately $$r$$ and $$s.$$ The proof above works with small modifications. Multiply both sides by $$\binom{n}{r}\binom{m+r}{r}\binom{n-m+s}{r}$$ to get \begin{aligned} &\binom{n}{r}\binom{n - r}{m - s} \cdot \binom{m+r}{r}\binom{n}{m + r} \cdot \binom{n-m+s}{r}\binom{n + s}{m}\\ &\qquad= \binom{n-m+s}{r}\binom{n}{m - s} \cdot \binom{n}{r}\binom{n - r}{m} \cdot \binom{m+r}{r}\binom{n + s}{m + r}. \end{aligned} The interpretation of the three "trinomial pairs" that appear on left and on right is similar to before.

Added 8 February 2014: There are, in fact two similar and related, but distinct, proofs along these lines. After permuting factors on both sides of the identity $$(*)$$ in the section above to get $$\binom{n - r}{m - s} \binom{n + s}{m} \binom{n}{m + r} = \binom{n - r}{m} \binom{n}{m - s} \binom{n + s}{m + r},$$ we multiply both sides by $$\binom{n-m-r+s}{s}\binom{m}{s}\binom{n+s}{s}$$ and obtain \begin{aligned} &\binom{n-m-r+s}{s}\binom{n - r}{m - s} \cdot \binom{m}{s}\binom{n + s}{m} \cdot \binom{n+s}{s}\binom{n}{m + r}\\ &\qquad = \binom{m}{s}\binom{n - r}{m} \cdot \binom{n+s}{s}\binom{n}{m - s} \cdot \binom{n-m-r+s}{s}\binom{n + s}{m + r}. \end{aligned} In the previous section, the counting problem had the parameters, $$\begin{array}{l|ccc} & \text{number} & \text{number on} & \text{number on}\\ & \text{in pool} & \text{committee} & \text{subcommittee}\\ \hline \text{students} & n & m+r-s & r\\ \text{teachers} & n & m+r & r\\ \text{administrators} & n+s & m+r & r\\ \end{array}$$ while in this section, the parameters are $$\begin{array}{l|ccc} & \text{number} & \text{number on} & \text{number on}\\ & \text{in pool} & \text{committee} & \text{subcommittee}\\ \hline \text{students} & n-r & m & s\\ \text{teachers} & n+s & m & s\\ \text{administrators} & n+s & m+r+s & s\\ \end{array}$$

The two proofs both relate to the hexagon with side-lengths alternating between $$r$$ and $$s$$. The proof in the previous section is obtained by relating the binomial coefficients corresponding to endpoints of the sides of length $$r,$$ while the proof in this section is obtained by relating the binomial coefficients corresponding to endpoints of the sides of length $$s.$$

Added 10 October 2018: I missed a third proof, which is similar to the previous two in that all three involve converting the binomial coefficients to trinomial coefficients. After permuting factors again to get $$\binom{n}{m + r} \binom{n - r}{m - s} \binom{n + s}{m} = \binom{n}{m - s} \binom{n + s}{m + r} \binom{n - r}{m},$$ we multiply both sides by $$\binom{m+r}{r+s}\binom{n+s}{r+s}\binom{n-m+s}{r+s}$$ and obtain \begin{aligned} &\binom{n}{m + r}\binom{m+r}{r+s} \cdot \binom{n+s}{r+s}\binom{n - r}{m - s} \cdot \binom{n + s}{m}\binom{n-m+s}{r+s}\\ &\qquad= \binom{n}{m - s}\binom{n-m+s}{r+s} \cdot \binom{n + s}{m + r}\binom{m+r}{r+s} \cdot \binom{n+s}{r+s}\binom{n - r}{m}, \end{aligned} In this proof, the parameters of the counting problem are $$\begin{array}{l|ccc} & \text{number} & \text{number on} & \text{number on}\\ & \text{in pool} & \text{committee} & \text{subcommittee}\\ \hline \text{students} & n & m+r & r+s\\ \text{teachers} & n+s & m+r & r+s\\ \text{administrators} & n+s & m+r+s & r+s\\ \end{array}$$ In this version, the two hexagon vertices associated with a given trinomial coefficient are diametrically opposite, rather than adjacent along sides of length $$r$$ or $$s$$.

Added 4 December 2018: I can't resist adding a generalization of the identity for the multinomial coefficients that may shed some light on the structure of the identity in the binomial case and on its three different proofs.

Let $$\ell\ge2$$, let $$k_1$$, $$k_2$$, ..., $$k_\ell$$, $$r_0 be integers such that $$k_i+r_0\ge0$$ for all $$i\in\{1,2,\ldots,\ell\}$$. Set $$n=\sum_{i=1}^\ell k_i+\sum_{i=0}^\ell r_i$$. Use $$\pi$$ to denote a permutation of $$(r_0,r_1,\ldots,r_\ell)$$. Then we have the identity $$\prod_{\text{sgn}(\pi)=1}\binom{n-\pi(r_0)}{k_1+\pi(r_1),\ldots,k_\ell+\pi(r_\ell)}=\prod_{\text{sgn}(\pi)=-1}\binom{n-\pi(r_0)}{k_1+\pi(r_1),\ldots,k_\ell+\pi(r_\ell)}.$$

Proof: Observe that the definition of $$n$$ and the restrictions on the $$r_i$$ guarantee that the multinomial coefficients are well-formed, that is, that the lower numbers in each coefficient sum to the upper number and that the lower numbers are all non-negative. The statement may be proved by observing that if both sides are multiplied by a suitable quantity, then both reduce to the same $$\left(\frac{1}{2}(\ell+1)!\right)$$-fold product of $$(\ell+1)$$-nomial coefficients.

To find a suitable multiplier, choose a pair of indices $$i from the set $$\{0,1,\ldots,\ell\}$$. The multiplier will be a product of binomial coefficients, one associated to each factor in the identity. For each multinomial coefficient in the identity (on either side), the parameter $$r_j$$ will appear in exactly one argument of the coefficient. If it appears in one of the lower arguments, that is, we have $$k_a+r_j$$ as a lower argument, introduce the binomial coefficient $$\binom{k_a+r_j}{k_a+r_i,r_j-r_i}.$$ If it appears in the upper argument, that is, if the upper argument is $$n-r_j$$, then introduce the binomial coefficient $$\binom{n-r_i}{n-r_j,r_j-r_i}.$$ The product of the binomial coefficients so introduced is the same on each of the two sides since each of the binomial coefficients $$\binom{n-r_i}{n-r_j,r_j-r_i},\ \binom{k_1+r_j}{k_1+r_i,r_j-r_i},\ \ldots,\ \binom{k_\ell+r_j}{k_\ell+r_i,r_j-r_i}$$ will be introduced exactly $$\frac{1}{2}\ell!$$ times on the left and the same number of times on the right. Hence we have found equal multipliers for the two sides.

To show that when the multiplier is included, the two sides reduce to the same quantity, observe that for the multinomial coefficient in the identity associated with the permutation $$\pi$$, there is a corresponding multinomial coefficient of opposite parity, obtained by following the permutation $$\pi$$ with the swap $$(r_ir_j)$$. The result now follows from the fact that when the introduced binomial coefficients are included, these $$\ell$$-nomials become equal $$(\ell+1)$$-nomials. Indeed, \begin{align*} &\binom{\ldots}{\ldots, k_a+r_i, \ldots, k_b+r_j, \ldots} \binom{k_b+r_j}{k_b+r_i,r_j-r_i}\\ &\quad=\binom{\ldots}{\ldots, k_a+r_j, \ldots, k_b+r_i, \ldots} \binom{k_a+r_j}{k_a+r_i,r_j-r_i}\\ &\quad=\binom{\ldots}{r_j-r_i, \ldots, k_a+r_i, \ldots, k_b+r_i, \ldots} \end{align*} when $$r_i$$ and $$r_j$$ both appear in lower arguments, while \begin{align*} &\binom{n-r_i}{\ldots, k_a+r_j, \ldots} \binom{k_b+r_j}{k_b+r_i,r_j-r_i}\\ &\quad=\binom{n-r_j}{\ldots, k_a+r_i, \ldots} \binom{n-r_i}{n-r_i,r_j-r_i}\\ &\quad=\binom{n-r_i}{r_j-r_i, \ldots, k_a+r_i, \ldots} \end{align*} when one of them appears in the upper argument. $$\square$$

Note that the original hexagonal identity is the case $$\ell=2$$, $$r_1=-1$$, $$r_2=0$$, $$r_3=1$$ and that the generalized hexagonal identity is the case $$\ell=2$$, $$r_1=-s$$, $$r_2=0$$, $$r_3=r$$. That there are three binomial coefficients on each side of the hexagonal identity reflects the fact that there are $$\frac{1}{2}(\ell+1)!=3$$ even permutations and the same number of odd permutations.

The proof of the multinomial version of the identity involved the arbitrary choice of the two indices $$i$$ and $$j$$. This means that there are, in fact $$\binom{\ell+1}{2}$$ different ways of constructing this proof, each with its own combinatorial interpretation. As before, these are not combinatorial proofs, since they involve the introduction of the multiplier. That there were three similar proofs in the hexagonal case reflects that fact that, when $$\ell=2$$, there are are $$\binom{\ell+1}{2}=3$$ ways of choosing $$i$$ and $$j$$.

It is worth pointing out that the hexagonal formation in the original Pascal's triangle identity is a translation of the permutohedron of $$\{r_0,r_1,r_2\}$$. The higher multinomial identities are associated with formations in Pascal's pyramid or its higher-dimensional generalizations taking the shape of some higher-dimensional polytope. When $$\ell=3$$, for example, the permutations of $$\{r_0,r_1,r_2,r_3\}$$ form the vertices of a truncated octahedron.

Finally, observe that there is a redundancy in the parameters that appear in the statement of the general identity. In particular $$r_0$$ may be eliminated by defining \begin{aligned} r'_0&:=0 \\ r'_1&:=r_1-r_0 & k'_1&:=k_1+r_0\\ &\vdots & &\vdots\\ r'_\ell&:=r_\ell-r_0 & k'_\ell&:=k_\ell+r_0 \end{aligned} so that $$n':=\sum_{i=1}^\ell k'_i+\sum_{i=0}^\ell r'_i=n-r_0$$, and rewriting the identity by replacing original parameters with primed parameters.

We can prove the equality of $$\binom{n-1}{m-1}\binom{n}{m+1}\binom{n+1}{m}=\binom{n}{m-1}\binom{n-1}{m}\binom{n+1}{m+1}$$ by counting lattice paths. In order to do so, we consider paths from $$(0,0)$$ to $$(X,Y)$$ with certain properties corresponding to the LHS of the equation and paths from $$(0,0)$$ to $$(X,Y)$$ corresponding to the RHS and show that there is a $$1$$-$$1$$ correspondence due to the symmetry between these.

To see the symmetry easier, we rewrite the equation using multinomial coefficients and exchange variables. We get

$$\binom{n-1}{m-1,n-m}\binom{n}{m+1,n-m-1}\binom{n+1}{m,n-m+1}=\binom{n}{m-1,n-m+1}\binom{n-1}{m,n-m-1}\binom{n+1}{m+1,n-m}$$ Using the substitution $$y=n-m,x=m$$ with $$x+y=n$$ gives

$$\binom{x+y-1}{x-1,y}\binom{x+y}{x+1,y-1}\binom{x+y+1}{x,y+1}=\binom{x+y-1}{x,y-1}\binom{x+y}{x-1,y+1}\binom{x+y+1}{x+1,y}$$

The factors of the RHS are rearranged by increasing length of paths corresponding to the LHS.

Now we analyse the LHS: The leftmost factor $$\binom{x+y-1}{x-1,y}$$ is the number of paths of length $$x+y-1$$ from $$(0,0)$$ to $$(x-1,y)$$, the next one is the number of paths of length $$x+y$$ from $$(0,0)$$ to $$(x+1,y-1)$$ and the third one is the number of paths of length $$x+y+1$$ from $$(0,0)$$ to $$(x,y+1)$$.

Now we concatenate these paths, so that the endpoint of the previous part is the starting point of the next one. So, the first part consists of all paths of length $$x+y-1$$ from $$(0,0)$$ to $$(x-1,y)$$. The second part consists of all paths of length $$x+y$$ starting in $$(x-1,y)$$ and ending in $$(2x,2y-1)$$. The third part consists of all paths of length $$x+y+1$$ starting in $$(2x,2y-1)$$ and ending in $$(3x,3y)$$.

To formulate it simpler: The LHS gives the number of all paths of length $$3x+3y$$ from $$(0,0)$$ to $$(3x,3y)$$ going through $$(x-1,y)$$ and $$(2x,2y-1)$$.

$$LHS: (0,0)\longrightarrow(x-1,y)\longrightarrow(2x,2y-1)\longrightarrow(3x,3y)$$

The RHS is now the symmetric pendant to the LHS. It shares the same properties and the same arguments hold. Therefore, the RHS gives the number of all paths of length $$3x+3y$$, starting from $$(0,0)$$ to $$(3x,3y)$$ and passing through $$(x,y-1)$$ and $$(2x-1,2y)$$.

$$RHS: (0,0)\longrightarrow(x,y-1)\longrightarrow(2x-1,2y)\longrightarrow(3x,3y)$$

Since the passing points of the paths from LHS and RHS are symmetric with respect to the line $$x=y$$ and start point and end point are on this diagonal the number of paths is the same, showing that RHS and LHS are equal.

Note: Some generalisations which are adressed by Will Orrick can presumably also be shown using the symmetries of corresponding paths. :-)

Added 2014-03-19: Attention - This proof is not correct. The reasoning is only valid for the special case $$x=y$$. In case of $$x\ne y$$ an explicit description of a bijection between the paths of LHS and RHS is missing (see comments below).

Added 2014-03-21: Outline for a proof. Here is an outline how a bijection between the paths of the LHS and RHS for the general case including $$x \ne y$$ could be created.

The plan is to show that all paths of the LHS can be mapped to a path from RHS and vice versa.

A geometrical representation of all paths of LHS, resp. RHS is given by a graph consisting of three rectangular grids having a vertex in common.

More precisely, all paths of LHS $$L$$ are within three rectangular grids $$L=L_1L_2L_3$$ with lower left and upper right points: $$L_1: (0,0) \rightarrow (x-1,y)$$, $$L_2: (x-1,y) \rightarrow (2x,2y-1)$$, and $$L_3: (2x,2y-1) \rightarrow (3x,3y)$$. All paths start in $$(0,0)$$, pass through the vertices $$(x-1,y)$$ and $$(2x,2y-1)$$ and end in $$(3x,3y)$$.

Since we cannot completely cover the RHS rectangles with the LHS rectangles we add an additional step, which preserves bijection and is therefore admissible.

An admissible action is to perform one or more cyclic shifts on a path. So, a path $$P=(P_1P_2)$$ becomes $$(P_2P_1)$$ after a cyclic shift right of $$length(P_2)$$. This implies that we can extend the LHS grid $$L=L_1L_2L_3$$ by placing a copy of $$L$$ to the right and also to the left, symbolically: $$LLL=L_1L_2L_3L_1L_2L_3L_1L_2L_3$$.

We are now free to cover parts from RHS $$R=R_1R_2R_3$$ with parts of $$LLL=L_1L_2L_3L_1L_2L_3L_1L_2L_3$$ and identify pathes this way. We may also use different coverings by moving $$LLL$$ in $$x$$- and $$y$$-direction.

Each covering identifies all paths for which the following holds: They are completely within $$R$$ and $$LLL$$, they have length $$3x+3y$$ and whenever the path crosses rectangular regions $$L_iL_j, L_iR_j, R_iL_j$$ or $$R_iR_j$$, the path has to pass through the corresponding vertex joining these regions.

Since the rectangles in LHS and RHS differ at most by $$2$$ in $$x$$- and $$y$$- direction, a few coverings should be sufficient to cover all paths of RHS by these transformed copies of LHS.

In the same way LHS should be covered by transformed copies of RHS. Maybe some special cases ($$x=1,y=1$$) have to be considered separately.

• Thank you for this wonderful answer. – Will Orrick Mar 17 '14 at 1:56
• Thanks for your friendly comment. It was fun to work on this problem :-) – Markus Scheuer Mar 17 '14 at 7:23
• In going through the details of your solution, I am only able to see how to make things work when $x=y.$ In that case, mirror symmetry about the line $y=x$ maps the LHS paths to the RHS paths. This takes care of the particular case I asked about, $n=2,$ $m=1,$ since then $x=y=1.$ In general, it takes care of $n=2m.$ But what about $x\ne y?$ In that case, the endpoint is not on the line of symmetry, so it wouldn't seem that things could work the same way. – Will Orrick Mar 17 '14 at 19:13
• Oh, Will! You are right and I'm wrong! The symmetry is not a valid argument for the general case. A bijection between the pathes of LHS and RHS for the general case seems now to be a little bit more challenging ... I will think about it ... – Markus Scheuer Mar 17 '14 at 22:08
• Thanks for placing the bounty to draw more attention to this question. It's an interesting one, and it's unfortunate that there haven't been more answers posted. I thought your idea merited the original bounty, so it wasn't really necessary to "return" it, although I do appreciate the points. It's been a while since I thought about it deeply, but I recall that your idea for extending the proof to the non-symmetric case seemed promising at the time. – Will Orrick Oct 10 '18 at 20:27

This is not an answer, but rather, an explanation of the problems with the top-voted (as of 28 September 2018) answer (by Mitch). Although comments explaining the issues have been in place for many years, the answer has not been corrected or deleted, and continues to accumulate up-votes (two within the last couple of months), which leads me to believe that a more visible and detailed explanation is needed. I would also take this opportunity to urge readers to up-vote Markus Scheuer's answer, which is the only answer posted to date that provides a proof that is both correct and combinatorial.

The simplest kind of combinatorial proof counts a finite set in two different ways, leading to an equality between two counting formulas. A more complicated kind of combinatorial proof counts two different sets and then does the additional step of establishing a bijection between the two sets. The bijection shows that the two sets have the same size. Once again, an equality of two counting formulas follows. The first kind of proof can be thought of as a special case of the second kind in which the identity map serves as the bijection.

Mitch's answer claims to provide the former kind of proof, that is, to count the same set in two different ways, but, in fact, does not do this. It correctly interprets the two sides as enumeration formulas, but these enumeration formulas are for different sets, not the same set. To prove the equality, one would have to show that the sets have the same size, but the answer does not attempt to do this. The answer contains the phrases "This corresponds one-to-one with the RHS because the things counted by the LHS can be counted in a different way by the RHS" and "Another way to count this situation is...", but this is either wrong—the formulas count manifestly different things—or incoherent—what does it mean to count a situation?

Detailed explanation: One way of interpreting Mitch's argument is that both sides of the identity count sets of ordered triples of subsets taken from sets of specified sizes. The problem is that the two sides do not count the same set of ordered triples of subsets, but rather, two different sets of ordered triples of subsets. And, more importantly, no bijection is established between the two sets of ordered triples. To make this concrete, look at the hexagon surrounding the $$2$$ in the third row of the triangle. This corresponds to $$n=2$$, $$m=1$$, and the identity, $$\binom{n-1}{m-1}\binom{n}{m+1}\binom{n+1}{m}=\binom{n+1}{m+1}\binom{n-1}{m}\binom{n}{m-1},$$ becomes $$\binom{1}{0}\binom{2}{2}\binom{3}{1}=\binom{3}{2}\binom{1}{1}\binom{2}{0}.$$ (If you compare with Mitch's formulation, you will see that I have reordered the factors on the right to make them coincide with the order in which the sets in Mitch's prescription below get used in his argument.) Now Mitch observes that the formula on the left counts ways of forming an ordered triple of subsets by drawing no elements from the first set (of size $$1$$), two elements from the second set (of size $$2$$), and one element from the third set (of size $$3$$). Mitch then says to remove one element from the second set and one element from the third set, and to place these elements into the first set. The right side counts ways of forming an ordered triple of subsets by drawing two elements from this new first set, one element from this new second set, and no elements from this new third set.

If we somehow knew that the number of ways of forming ordered triples of subsets of the original three sets equalled the number of ways of forming ordered triples of subsets of the three new sets, then we would have a proof. The numbers of ordered triples on the two sides are, in fact, equal---the identity is true---but the question is how to demonstrate this.

To understand what's going on, let's look what the ordered triples on each side are in our concrete example. For the left side, let the first set be $$\{R\}$$, the second set $$\{G_1,G_2\}$$, and the third set $$\{B_1,B_2,B_3\}$$. The left side of the identity is computed to be $$3$$, and there are, indeed, three ordered triples of subsets: \begin{aligned} &(\{\},\{G_1,G_2\},\{B_1\})\\ &(\{\},\{G_1,G_2\},\{B_2\})\\ &(\{\},\{G_1,G_2\},\{B_3\}). \end{aligned} Following Mitch's prescription for the right side, an element is removed from each of sets $$2$$ and $$3$$, say elements $$G_1$$ and $$B_1$$, and these elements are placed in set $$1$$, giving sets $$\{R,G_1,B_1\}$$, $$\{G_2\}$$, $$\{B_2,B_3\}$$. The right side of the identity also equals $$3$$, and there are, again, three ordered triples of subsets: \begin{aligned} &(\{G_1,B_1\},\{G_2\},\{\})\\ &(\{R,B_1\},\{G_2\},\{\})\\ &(\{R,G_1\},\{G_2\},\{\}). \end{aligned}

Clearly we don't expect the same ordered triples on the two sides since we've moved elements around. I surmise that the expectation in Mitch's answer was that the content of the triples, that is, the union of the three subsets composing the triple, would match up on the two sides. But the example shows that this doesn't happen either. Thinking of $$R$$ as a red object, $$G_i$$ as green objects, and $$B_j$$ as blue objects, we have a fixed color composition (no red, two greens, one blue) for all of the triples on the left, but not for the triples on the right. Of the triples on the right, only the triple $$(\{G_1,B_1\},\{G_2\},\{\})$$ has the same content as a triple on the left.

To complete a proof along these lines, some rule would have to be formulated for matching up triples on the two sides, and it would have to be proved that this rule works for arbitrary $$n$$ and $$m$$. This has not been done. In fact, I don't believe that the proof can be patched up, for the following reason: nothing in the logic of the argument seems to rely on only one element being removed from each of the second and third sets and placed in the first set. Why not two elements from each, or one element from the second and two elements from the third, or some other combination of numbers from each? But if that is right, we should get many additional identities, namely $$\binom{n-1}{m-1}\binom{n}{m+1}\binom{n+1}{m}=\binom{n-1+k+\ell}{m-1+k+\ell}\binom{n-k}{m+1-k}\binom{n+1-\ell}{m-\ell},$$ for arbitrary $$k$$ and $$\ell$$. There is, however, no such general identity, as one can check by plugging in numbers. For example, let $$n=4$$, $$m=3$$, $$k=\ell=2$$. Then $$\binom{n-1}{m-1}\binom{n}{m+1}\binom{n+1}{m}=\binom{3}{2}\binom{4}{4}\binom{5}{3}=30,$$ while $$\binom{n-1+k+\ell}{m-1+k+\ell}\binom{n-k}{m+1-k}\binom{n+1-\ell}{m-\ell}=\binom{7}{6}\binom{2}{2}\binom{3}{1}=21.$$ On the other hand, $$k=\ell=1$$ does work: $$\binom{5}{4}\binom{3}{3}\binom{4}{2}=30.$$ Generalizations of the identity that actually hold are given in the cited article, as I note in my other answer. These generalizations do contain additional parameters, but they enter in a different way than do the $$k$$ and $$\ell$$ in the formula above. And understanding the role of these additional parameters actually gives insight into what makes the identity tick.

A TV channel will broadcast six multi-part TV dramas which have the following numbers of parts:

• A: $$m-1$$ parts
• B: $$n-m$$ parts
• C: $$m+1$$ parts
• D: $$n-m-1$$ parts
• E: $$m$$ parts
• F: $$n-m+1$$ parts

The $$3n$$ time-slots when they will be broadcast are on $$n-1$$ Mondays, $$n$$ Wednesdays and $$n+1$$ Fridays. There are two possible schedules, which are as follows:

Schedule 1:

• A and B on Mondays
• C and D on Wednesdays
• E and F on Fridays

Schedule 2:

• D and E on Mondays
• A and F on Wednesdays
• B and C on Fridays

(I have for the most part taken the 6 terms in the order Mitch put them in his equation, but have swapped his RHS's first two terms so as to make the RHS's numerator-sequence match the LHS's.)

The parts of each drama must be broadcast in their correct order. However, the parts of different dramas may be interleaved at will.

Let $$S_i$$ be the set of broadcast-orders that fit Schedule $$i$$. Mitch's LHS is $$|S_1|$$. His RHS is $$|S_2|$$.

Choose an order that fits Schedule 1. This determines the order in which the $$n-1$$ D- and E-parts (collectively) are broadcast. This is a valid order for Schedule 2's Monday time-slots. Similarly for Schedule 2's Wednesday time-slots, and for its Friday time-slots. This thus determines a unique order that fits Schedule 2.

A similar argument, with the schedules swapped, also applies. Thus there is a bijection between $$S_1$$ and $$S_2$$. Thus $$|S_1|=|S_2|$$ which proves the identity specified by Mitch.

• I'm a bit worried about how we know these mappings are one-to-one. If we take $n=3$, $m=2$ as an example, then we have episodes $A_1$, $B_1$, $C_1$, $C_2$, $C_3$, $E_1$, $E_2$, $F_1$, $F_2$. Following Schedule $1$, two possible broadcast orders are $A_1C_1E_1\ B_1C_2E_2\ C_3F_1\ F_2$ and $A_1C_1E_1\ B_1C_2F_1\ C_3E_2\ F_2$, if I understand the setup correctly. (Since there is one more Wednesday than Monday, and one more Friday than Wednesday, there will be no Monday broadcast in the last two weeks, and no Wednesday broadcast in the last week.) The... – Will Orrick Jan 15 '19 at 19:34
• ... image of both of these broadcast orders would seem to be the Schedule-$2$ order $E_1A_1C_1\ E_2F_1B_1\ F_2C_2\ C_3$, again assuming that I am understanding the mapping correctly. Please let me know if I am misinterpreting something or have made an error somewhere. – Will Orrick Jan 15 '19 at 19:34
• @WillOrrick You're right and I was wrong. I thought the functions would be each other's inverses but they're not. Your schedule 1 orders map to the same schedule 2 order, which maps back to the first of your schedule 1 orders. So your second schedule 1 order proves that the mappings are not each other's inverses. So no bijection. It's harder than I thought, to find a pure combinatorial proof, i.e. where LHS and RHS count items in 2 sets, not quotients of 2 larger sets by some "equivalence" criterion which would entail some algebra. – Rosie F Jan 16 '19 at 7:49


text:
## anonymous one year ago Which variable expression matches the word phrase?

1. anonymous

2. anonymous

1 is a 2 is c and 3 is b

3. anonymous

@isaac4321 explain plz

4. anonymous

Oh yea sorry well with 1 and 2 the sum and difference gives it away

5. anonymous

6. Nnesha

sum + add difference - subtract quotient / divide product x multiply

7. Nnesha

quotient of x and y is $\rm \frac{ x }{ y}$ so quotient of 9 and a number is ?

8. Nnesha

|dw:1440539402656:dw| let number = x

9. Nnesha

i mean y*

10. anonymous

|dw:1440540211678:dw|

11. anonymous

|dw:1440540235040:dw|

12. Nnesha

yes right quotient means divide if quotient of x and y is x/y then quotient of 9 and a number would be ??

13. anonymous

9 /12? right ?

14. Nnesha

no number would be a variable given is quotient of 9 and a number we don't know what number it would be so we use variables like x , y or z in this question there is y

15. anonymous

i dont get it

16. Nnesha

|dw:1440540471153:dw| that's right 12+ now we don't need another 12 quotient of a 9 and a number  is here is i'll give you example quotient of 4 and a number would b e 4/x we represent a number  by variable

17. anonymous

number 3 is b right ?

18. Nnesha

yes right

19. Nnesha

difference means subtract

20. anonymous

okay my mom said that number 4 dont have a answer to it

21. Nnesha

there is a answer for number 4 how would you write quotient of 9 and a number ?

22. anonymous

y/9

23. Nnesha

hmm 9 /y quotient of 9 and y not y and 9

24. Nnesha

|dw:1440541039418:dw| that's what you should write there

25. anonymous

im guessing its B then ?

26. Nnesha

more than = sum both means add

27. anonymous

so A?

28. Nnesha

yep

29. anonymous

thanks can you help with 1 more ?

30. Nnesha

i'll try

format: plain


text:
### Authors: Noah Goodman; Timothy J. O’Donnell; Josh Tenenbaum

In the chapter on Mixture Models we saw a simple way to construct a model with an unbounded number of categories—simply place uncertainty over the number of categories that are ‘actually’ in the world. In this section we describe another approach which instead posits an infinite number of (mostly unused) categories actually in the world. The non-parametric, or infinite, models have a number of useful mathematical properties.

# Prelude: sampling from a discrete distribution

In WebPPL the discrete distribution is a primitive, e.g. Discrete({ps: [0.2, 0.3, 0.1, 0.4]}). If it wasn’t built-in and the only random primitive you could use was flip, how could you sample from discrete? One solution is to recursively walk down the list of probabilities, deciding whether to stop on each step. For instance, in Discrete({ps: [0.2, 0.3, 0.1, 0.4]}) there is a 0.2 probability of stopping on the first flip, a 0.3/0.8 probability of stopping on the second flip (given that we didn’t stop on the first), and so on. We can start by turning the list of probabilities into a list of residual probabilities—the probability we will stop on each step, given that we haven’t stopped yet:

var residuals = function(probs) {
if(probs.length == 0) {
return [];
} else {
return [first(probs) / sum(probs)].concat(residuals(rest(probs)));
}
};

residuals([0.2, 0.3, 0.1, 0.4])

Now to sample from the discrete distribution we simply walk down this list, deciding when to stop:

var residuals = function(probs) {
if(probs.length == 0) {
return [];
} else {
return [first(probs) / sum(probs)].concat(residuals(rest(probs)));
}
};

var mySampleDiscrete = function(resid) {
if(resid.length == 0) {
return 0;
} else if(flip(first(resid))) {
return 1;
} else {
return 1 + mySampleDiscrete(rest(resid));
}
}

viz.auto(repeat(5000, function(){
return mySampleDiscrete(residuals([0.2, 0.3, 0.1, 0.4]))
}))

# Infinite Discrete Distributions: The Dirichlet Processes

We have seen several examples of mixture models where the mixture components are chosen from a multinomial distribution and the weights of the mixture components are drawn from a Dirichlet prior. Both multinomial and Dirichlet distributions are defined for fixed numbers of categories—now, imagine generalizing the combination of Dirichlet and multinomial, to a multinomial over infinitely many categories of components. This would solve the problem of “running out of categories,” because there would always be more categories that hadn’t yet been used for any observation.

Just as the Dirchlet distribution defines a prior on parameters for a multinomial with $K$ possible outcomes, the Dirichlet process defines a prior on parameters for a multinomial with $K = \infty$—an infinite number of possible outcomes.

First, we imagine drawing an infinite sequence of samples from a beta distribution with parameters $1,\ \alpha$ (recall that a beta distribution defines a distribution on the interval $[0,1]$). We write this infinite set of draws as $\left\{\beta'_k\right\}_{k=1}^{\infty}$. $\beta'_k \sim \text{Beta}\left(1,\alpha\right)$ Ultimately we would like to define a distribution on an infinite set of discrete outcomes that will represent our categories or mixture components, but we start by defining a distribution on the natural numbers. The probability of the natural number $k$ is given by: $\beta_k = \prod_{i=1}^{k-1}\left(1-\beta'_i\right)\cdot\beta'_k$ How can this be interpreted as a generative process? Imagine “walking” down the natural numbers in order, flipping a coin with weight $\beta'_i$ for each one; if the coin comes up false, we continue to the next natural number; if the coin comes up true, we stop and return the current natural number. Convince yourself that the probability of getting natural number $k$ is given by $\beta_k$ above.

To formalize this as a WebPPL program, we define a procedure, pickStick, that walks down the list of $\beta'_k$s (called sticks in the statistics and machine learning literatures) and flips a coin at each one: if the coin comes up true, it returns the index associated with that stick, if the coin comes up false the procedure recurses to the next natural number.

var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var sticks = mem(function(index) {
return beta(1, alpha)
});

pickStick is a higher-order procedure that takes another procedure called sticks, which returns the stick weight for each stick. pickStick is also a recursive function—one that calls itself.

Notice that sticks uses mem to associate a particular draw from beta with each natural number. When we call it again with the same index we will get back the same stick weight. This (crucially) means that we construct the $\beta'_k$s only “lazily” when we need them—even though we started by imagining an infinite set of “sticks” we only ever construct a finite subset of them.

We can put these ideas together in a procedure called makeSticks which takes the $\alpha$ parameter as an input and returns a procedure which samples stick indices.

var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}
var mySticks = makeSticks(1);

viz(repeat(1000, mySticks))

mySticks samples from the natural numbers by walking down the list starting at 1 and flipping a coin weighted by a fixed $\beta'_k$ for each $k$. When the coin comes up true it returns $k$ otherwise it keeps going. It does this by drawing the individual $\beta'_k$ lazily, only generating new ones when we have walked out further than furthest previous time.

This way of constructing a Dirichlet Process is known as the stick-breaking construction and was first defined in @Sethuraman1994. There are many other ways of defining a Dirichlet Process, one of which—the Chinese Restaurant Process—we will see below.

## Stochastic Memoization with DPmem

The above construction of the Dirichlet process defines a distribution over the infinite set of natural numbers. We quite often want a distribution not over the natural numbers themselves, but over an infinite set of samples from some other distribution (called the base distribution): we can generalize the Dirichlet process to this setting by using mem to associate to each natural number a draw from the base distribution.

var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}
var DPthunk = function(alpha, baseDist) {
var augmentedProc = mem(function(stickIndex) {return sample(baseDist)});
var DP = makeSticks(alpha);
return function() {return augmentedProc(DP())}
}

var memoizedGaussian = DPthunk(1, Gaussian({mu: 0, sigma: 1}));
viz(repeat(10000, function() {return gaussian(0, 1)}));
viz(repeat(10000, memoizedGaussian));

We can do a similar transformation to any WebPPL procedure: we associate to every argument and natural number pair a sample from the procedure, then use the Dirichlet process to define a new procedure with the same signature. In WebPPL this useful higher-order distribution is called DPmem:

var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}

var geometric = function(p) {
return flip(p) ? 0 : 1 + geometric(p);
}

var memoizedGeometric = DPmem(1, geometric);
viz(repeat(10000, function() {geometric(.5)}));
viz(repeat(10000, function() {memoizedGeometric(.5)}))

In a probabilistic setting a procedure applied to some inputs may evaluate to a different value on each execution. By wrapping such a procedure in mem we associate a randomly sampled value with each combination of arguments. We have seen how this is useful in defining random world style semantics, by persistently associating individual random draws with particular mem‘d values. However, it is also natural to consider generalizing the notion of memoization itself to the stochastic case. Since DPmem is a higher-order procedure that transforms a procedure into one that sometimes reuses its return values we call it a stochastic memoizer [@Goodman2008].

TODO: The order of these sections doesn’t make sense. The reader (or at least me) has already spent quite some time puzzling over the output of the above code boxes, and it’d be helpful to fold this exposition in above. Especially since it’s literally the same output…

## Properties of DP Memoized Procedures

A procedure in WebPPL defines a distribution. When we wrap such a procedure in DPmem the resulting procedure defines a new Dirichlet process distribution. The underlying distribution associated with proc in the code above is called the base measure of the Dirichlet process and is often written $\mu$ or sometimes $G_0$. In the following example we stochastically memoize a normal distribution.

var memoizedGaussian = DPmem(1, gaussian);
viz(repeat(10000, function() {return memoizedGaussian(0,1)}));

The DP is said to concentrate the base measure. Draws from a normal distribution are real-valued. However, draws from a DP are discrete (with probability one). By probabilistically memoizing a normal distribution we take the probability mass that the Gaussian spreads across the real line and concentrate it into a countable number of specific points. Compare the result of the previous computation with the result of sampling from a normal distribution itself.

var memoizedGaussian = DPmem(1, gaussian);
viz(repeat(10000, function() {return gaussian(0, 1)}));
viz(repeat(10000, function() {return memoizedGaussian(0,1)}));

The way that the DP concentrates the underlying base measure is illustrated in the following figure.

In the stick-breaking construction stick heights become shorter on average as we walk further down the number line. This means that earlier draws from the DP are more likely to be redrawn than later draws. When we use the DP to construct DPmem the memoized function will therefore tend to favor reuse of earlier computed values. Intuitively, we will use DPmem when we need to model reuse of samples in a scenario where we do not know in advance how many samples we need.

## Infinite Mixture Models

We now return to the problem of categorization with an unknown number of categories. We can use the Dirichlet process to construct a distribution over an infinite set of (potential) bags:

///fold:
var getProbs = function(vector) {
return map(function(i) {return T.get(vector,i)}, _.range(vector.length))
}

var observeBag = function(bag, values) {
return sum(map(function(v) {return bag.score(v)}, values));
}

var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
///
var colors = ['blue', 'green', 'red'];

var predictives = Infer({method: 'MCMC', samples: 30000}, function(){
var phi = dirichlet(ones([3, 1]))
var alpha = 0.1
var prototype = T.mul(phi, alpha)

var makeBag = mem(function(bag){
return Categorical({vs: colors, ps: getProbs(dirichlet(prototype))});
})

// the prior distribution on bags is simply a DPmem of a gensym function:
var getBag = DPmem(1, uuid);

// each observation comes from one of the bags:
var obsToBag = mem(function(obsName) {return getBag()});

factor(observeBag(makeBag(obsToBag('obs1')), ['red']) +
observeBag(makeBag(obsToBag('obs2')), ['red']) +
observeBag(makeBag(obsToBag('obs3')), ['blue']) +
observeBag(makeBag(obsToBag('obs4')), ['blue']) +
observeBag(makeBag(obsToBag('obs5')), ['red']) +
observeBag(makeBag(obsToBag('obs6')), ['blue']))

return {sameBag12: obsToBag('obs1') == obsToBag('obs2'),
sameBag13: obsToBag('obs1') == obsToBag('obs3')}
});

viz.marginals(predictives);

A model like this is called an infinite mixture model; in this case an infinite Dirichlet-multinomial mixture model, since the observations (the colors) come from a multinomial distribution with Dirichlet prior. The essential addition in this model is that we have DPmem‘d a uuid (Universally Unique IDentifier) function to provide a collection of reusable category (bag) labels:

///fold:
var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
///
var reusableCategories = DPmem(1, uuid)
viz(repeat(20, reusableCategories));

To generate our observation in this infinite mixture model we first sample a category label from the memoized uuid. Since the Dirichlet process tends to reuse earlier choices (more than later ones), our data will tend to cluster together in earlier components. However, there is no a priori bound on the number of latent classes, rather there is just a bias towards fewer classes. The strength of this bias is controlled by the DP concentration parameter $\alpha$. When $\alpha$ is high, we will tolerate a larger number of classes, when it is low we will strongly favor fewer classes. In general, the number of classes grows proportional to $\alpha \log(N)$ where $N$ is the number of observations.

We can use this basic template to create infinite mixture models with any type of observation distribution. For instance here is an infinite Gaussian mixture model:

///fold:
var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
///
var classDistribution = DPmem(1, uuid);
var objectToClass = mem(function(obj) {return classDistribution()});
var classToGaussianParams = mem(function(classID) {
return {mu: gaussian(65, 10), sigma: gaussian(0, 8)}
});
var observe = function(obj) {
var params = classToGaussianParams(objectToClass(obj));
return gaussian({mu: params.mu, sigma: params.sigma});
}

map(observe, ['tom', 'dick', 'harry', 'bill', 'fred']);

There are, of course, many possible observation models that can be used in the infinite mixture. One advantage of using abstract objects to represent our data is that we can associate different observation models with different aspects of the data. For instance, we could have a model which both models height and propensity to smoke for the same set of individuals, based on their sex.

# Another View of the DP: The Chinese Restaurant Process

If you have looked at the literature on Bayesian models of cognition in the last few years, you will have seen many uses of a prior distribution known as the Chinese Restaurant Process. The Chinese Restaurant Process is an alternate, but equivalent, way to construct the Dirichlet process. The CRP is usually described as a sequential sampling scheme using the metaphor of a restaurant.

We imagine a restaurant with an infinite number of tables. The first customer enters the restaurant and sits at the first unoccupied table. The ($N+1$)th customer enters the restaurant and sits at either an already occupied table or a new, unoccupied table, according to the following distribution. $\tau^{(N+1)} | \tau^{(1)},..., \tau^{(N)},\alpha \sim \sum_{i=1}^{K} \frac{ y_i }{ N + \alpha } \delta_{\tau_{i}} + \frac{ \alpha }{ N + \alpha } \delta_{\tau_{K+1}}$ $N$ is the total number of customers in the restaurant. $K$ is the total number of occupied tables, indexed by $1 \geq i \geq K$. $\tau^{(j)}$ refers to the table chosen by the $j$th customer. $\tau_i$ refers to $i$th occupied table in the restaurant. $y_i$ is the number of customers seated at table $\tau_i$; $\delta_{\tau}$ is the $\delta$-distribution which puts all of its mass on table $\tau$. $\alpha \geq 0$ is the concentration parameter of the model.

In other words, customers sit at an already-occupied table with probability proportional to the number of individuals at that table, or at a new table with probability controlled by the parameter $\alpha$.

Each table has a dish associated with it. Each dish $v$ is a label on the table which is shared by all the customers at that table. When the first customer sits at a new table, $\tau_i$, a dish is sampled from another distribution, $\mu$, and placed on that table. This distribution, $\mu$, is called the base distribution of the Chinese restaurant process, and is a parameter of the model. From then on, all customers who are seated at table $\tau_i$ share this dish, $v_{\tau_i}$.

The following animation demonstrates the Chinese restaurant process (click on it).

The CRP can be used to define a stochastic memoizer just as the Dirichlet process. We let the dish at each table be drawn from the underlying procedure. When we seat a customer we emit the dish labeling the table where the customer sat. To use a CRP as a memoization distribution we associate our underlying procedure with a set of restaurants—one for each combination of a procedure with its arguments. We let customers represent particular instances in which a procedure is evaluated, and we let the dishes labeling each table represent the values that result from those procedure applications. The base distribution which generates dishes corresponds to the underlying procedure which we have memoized.

When we seat a customer at an existing table, it corresponds to retrieving a value from the memory. Every customer seated at an existing table always returns the dish placed at that table when it was created. When we seat a customer at a new table it corresponds to computing a fresh value from our memoized random function and storing it as the dish at the new table. Another way of understanding the CRP is to think of it as defining a distribution over ways of partitioning $N$ items (customers) into $K$ partitions (tables), for all possible $N$ and $K$.

The probability of a particular partition of $N$ customers over $K$ tables is the product of the probabilities of the $N$ choices made in seating those customers. It can easily be confirmed that the order in which elements are added to the partition components does not affect the probability of the final partition (i.e. the terms of the product can be rearranged in any order). Thus the distribution defined by a CRP is exchangeable.

The probability of a particular CRP partition can also be written down in closed form as follows. $P(\vec{y})=\frac{\alpha^{K}\Gamma[\alpha]\prod_{j=0}^{K}\Gamma[y_{j}]}{\Gamma[\alpha+\sum_{j=0}^{K}y_{j}]}$ Where $\vec{y}$ is the vector of counts of customers at each table and $\Gamma(\cdot)$ is the gamma function, a continuous generalization of the factorial function. This shows that for a CRP the vector of counts is sufficient.

As a distribution, the CRP has a number of useful properties. In particular, it implements a simplicity bias. It assigns a higher probability to partitions which (1) have fewer customers, (2) have fewer tables, and (3) for a fixed number of customers $N$, assign them to the smallest number of tables.

Thus the CRP favors simple restaurants and implements a rich-get-richer scheme. Tables with more customers have higher probability of being chosen by later customers. These properties mean that, all else being equal, when we use the CRP as a stochastic memoizer we favor reuse of previously computed values.

## Example: Goldwater Model 1

///fold:
var getProbs = function(vector) {
return map(function(i) {return T.get(vector,i)}, _.range(vector.length))
}

var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
///

var phoneVals = ['a', 'e', 'i', 'o', 'u',
'k', 't', 'p', 'g', 'd', 'b', 's', 'th', 'f'];
var phoneProbs = getProbs(dirichlet(ones([phoneVals.length, 1])));
var phones = Categorical({vs: phoneVals, ps: phoneProbs});
var numWords = 10;

var samplePhoneSequence = function() {
return repeat(poisson(3), function() {return sample(phones)});
};

samplePhoneSequence()
var sampleWord = DPmem(1, function() {return samplePhoneSequence()})
var sampleUtterance = repeat(numWords, sampleWord);

sampleUtterance

# Example: Infinite Hidden Markov Models

Just as when we considered a mixture model over an unknown number of latent categories, we may wish to have a hidden Markov model over an unknown number of latent symbols. We can do this by again using a reusable source of state symbols:

///fold:
var getProbs = function(vector) {
return map(function(i) {return T.get(vector,i)}, _.range(vector.length))
}

var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
///
var vocabulary = ['chef', 'omelet', 'soup', 'eat', 'work', 'bake'];
var getState = function() {return DPmem(0.5, uuid)};

var stateToTransitionModel = mem(function(state) {return DPmem(1, getState())});
var transition = function(state) {return stateToTransitionModel(state)()};

var stateToObservationModel = mem(function(state) {return dirichlet(ones([vocabulary.length, 1]))});
var observation = function(state) {return categorical({vs: vocabulary,
ps: getProbs(stateToObservationModel(state))})};
var sampleWords = function(lastState) {
return flip(.2) ? [] : [observation(lastState)].concat(sampleWords(transition(lastState)));
}
sampleWords('start')

This model is known as the “infinite hidden Markov model”. Notice how the transition model uses a separate DPmemoized function for each latent state: with some probability it will reuse a transition from this state, otherwise it will transition to a new state drawn from the globally shared source or state symbols—a DPmemoized uuid.

# Example: The Infinite Relational Model

Much semantic knowledge is inherently relational. For example, verb meanings can often be formalized as relations between their arguments. The verb “give” is a three-way relation between a giver, something given, and a receiver. These relations are also inherently typed. For example, the giver in the relation above is typically an agent. In a preceding section, we discussed the infinite mixture models, where observations were generated from a potentially unbounded set of latent classes. In this section we introduce an extension of this model to relational data: the infinite relational model (IRM).

Given some relational data, the IRM learns to cluster objects into classes such that whether or not the relation holds depends on the pair of object classes. For instance, we can imagine trying to infer social groups from the relation of who talks to who:

///fold:
var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
///
var results = Infer({method: "MCMC", samples: 10000}, function() {
var classDistribution = DPmem(1, uuid);
var objectToClass = mem(function(obj) {return classDistribution()});
var classesToParams = mem(function(class1, class2) {
return {p: beta(.5, .5)}
});
var talkScore = function(person1, person2, val) {
var params = classesToParams(objectToClass(person1), objectToClass(person2));
return Bernoulli({p: params.p}).score(val);
}

factor(talkScore('tom', 'fred', true) +
talkScore('tom', 'jim', true) +
talkScore('jim', 'fred', true) +
talkScore('mary', 'fred', false) +
talkScore('mary', 'jim', false) +
talkScore('sue', 'fred', false) +
talkScore('sue', 'tom', false) +
talkScore('ann', 'jim', false) +
talkScore('ann', 'tom', false) +
talkScore('mary', 'sue', true) +
talkScore('mary', 'ann', true) +
talkScore('ann', 'sue', true))

return {tomVsFred: objectToClass('tom') == objectToClass('fred'),
tomVsMary: objectToClass('tom') == objectToClass('mary')};
})

viz.marginals(results)

We see that the model invents two classes (the “boys” and the “girls”) such that the boys talk to each other and the girls talk to each other, but girls don’t talk to boys. Note that there is much missing data (unobserved potential relations) in this example.

# Example: CrossCat

Often we have data where each object is associated with a number of features. In many cases, we can predict how these features generalize by assigning the objects to classes and predicting feature values on a class-by-class basis. In fact, we can encode this kind of structure using the IRM above if we interpret the relations as the presence of absence of a feature. However, in some cases this approach does not work because objects can be categorized into multiple categories, and different features are predicted by different category memberships.

For example, imagine we have some list of foods like: eggs, lobster, oatmeal, etc., and some list of features associated with these foods, such as: dairy, inexpensive, dinner, eaten with soup, etc. These features depend on different systems of categories that foods fall into, for example, one set of features may depend on the time of day that the foods are eaten, while another set may depend on whether the food is animal or vegetable based. CrossCat is a model designed to address these problems. The idea behind CrossCat is that features themselves cluster into kinds. Within each kind, particular objects will cluster into categories which predict the feature values for those objects in the kind. Thus CrossCat is a kind of hierarchical extension to the IRM which takes into account multiple domains of featural information.

TODO: this is a pretty uninformative example without some kind of inference or distributional result to look at

///fold:
var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function(key) {
return function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return key + s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
}
///
var kindDistribution = DPmem(1, uuid('kind'))
var featureToKind = mem(function(feature) {return kindDistribution()});
var kindToClassDistribution = mem(function(kind) {return DPmem(1, uuid("class"))});
var featureKindObjectToClass = mem(function(kind, object) {return kindToClassDistribution(kind)()});
var classToParameters = mem(function(objectClass) {return {p: beta(1,1)}});
var observe = function(object, feature) {
var params = classToParameters(featureKindObjectToClass(featureToKind(feature), object));
return flip(params.p)
}

observe('eggs', 'breakfast')

# Other Non-Parametric Distributions

The Dirichlet Process is the best known example of a non-parametric distribution. The term non-parametric refers to statistical models whose size or complexity can grow with the data, rather than being specified in advance (sometimes these are called infinite models, since they assumes an infinite, not just unbounded number of categories). There a number of other such distributions that are worth knowing.

## Pitman-Yor Distributions

Many models in the literature use a small generalization of the CRP known as the Pitman-Yor process (PYP). The Pitman-Yor process is identical to the CRP except for having an extra parameter, $a$, which introduces a dependency between the probability of sitting at a new table and the number of tables already occupied in the restaurant.

The process is defined as follows. The first customer enters the restaurant and sits at the first table. The ($N+1$)th customer enters the restaurant and sits at either an already occupied table or a new one, according to the following distribution. $\tau^{(N+1)} | \tau^{(1)},...,\tau^{(N)}, a, b \sim \sum_{i=1}^{K} \frac{ y_i - a }{ N + b } \delta_{\tau_{i}} + \frac{ Ka + b }{ N + b } \delta_{\tau_{K+1}}$ Here all variables are the same as in the CRP, except for $a$ and $b$. $b \geq 0$ corresponds to the CRP $\alpha$ parameter. $0 \leq a \leq 1$ is a new discount parameter which moves a fraction of a unit of probability mass from each occupied table to the new table. When it is $1$, every customer will sit at their own table. When it is $0$ the distribution becomes the single-parameter CRP. The $a$ parameter can be thought of as controlling the productivity of a restaurant: how much sitting at a new table depends on how many tables already exist. On average, $a$ will be the limiting proportion of tables in the restaurant which have only a single customer. The $b$ parameter controls the rate of growth of new tables in relation to the total number of customers $N$ as before.

Like the CRP, the sequential sampling scheme outlined above generates a distribution over partitions for unbounded numbers of objects. Given some vector of table counts $\vec{y}$, A closed-form expression for this probability can be given as follows. First, define the following generalization of the factorial function, which multiples $m$ integers in increments of size $a$ starting at $x$. $% 0 \end{cases} %]]>$ Note that $[1]_{m,1} = m!$. The probability of the partition given by the count vector, $\vec{y}$, is defined by: $P( \vec{y} \mid a, b) = \frac{[b+a]_{K-1,a}}{[b+1]_{N-1,1}} \prod_{i=1}^{K}[1-a]_{y_i-1,1}$ It is easy to confirm that in the special case of $a = 0$ and $b >0$, this reduces to the closed form for CRP by noting that $[1]_{m,1} = m! = \Gamma[m+1]$. In what follows, we will assume that we have a higher-order function PYmem which takes three arguments a, b, and proc and returns the PYP-memoized version of proc.

## The Indian Buffet Process

The Indian Buffet Process is an infinite distribution on sets of draws from a base measure (rather than a single draw as in the CRP).

# Hierarchical Combinations of Non-parametric Processes

In the Hierarchical Models chapter, we explored how additional levels of abstraction can lead to important effects in learning dynamics, such as transfer learning and the blessing of abstraction. In this section, we talk about two ways in which hierarchical non-parametric models can be built.

## The Nested Chinese Restaurant Process

We have seen how the Dirichlet Process/CRP can be used to learn mixture models where the number of categories is infinite. However, the categories associated with each table or stick in the DP/CRP are unstructured, whereas real life categories have complex relationships with one another. For example, they are often organized into hierarchies: a German shepherd is a type of dog, which is a type of animal, which is type of living thing, and so on.

In Example: One-shot learning of visual categories, we saw how such hierarchies could lead to efficient one-shot learning, but we did not talk about how such a hierarchy itself could be learned. The Nested Chinese Restaurant Process (nCRP) is one way of doing this [@Blei2003b]. The idea behind the nCRP is that tables in a CRP, which typically represent categories, can refer to other restaurants that represent lower-level categories.

///fold:
var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function(key) {
return function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return key + s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
}
///
var topUUID = uuid("t");
var topLevelCategory = DPmem(1, topUUID)

var subordinateUUID = uuid("s");
var subordinateCategory = DPmem(1, function(parent) {
return {sub: subordinateUUID().slice(0, 2),
top: parent.slice(0,2)}});

var sampleCategory = function() {return subordinateCategory(topLevelCategory())};

viz.table(repeat(20, sampleCategory))

Each call to sampleCategory returns a list that consists of a subordinate-level category followed by the corresponding top-level category. These categories are represented by UUIDs, and, because they are drawn from a DP-memoized version of UUID, there is no a priori limit on the number of possible categories at each level.

The nCRP gives us a way of constructing unbounded sets of hierarchically nested categories, but how can we use such structured categories to generate data? The code below shows one way:

///fold:
var getProbs = function(vector) {
return map(function(i) {return T.get(vector,i)}, _.range(vector.length))
}

var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function(key) {
return function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return key + s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
}
///
var possibleObservations = ['a', 'b', 'c', 'd', 'e', 'f', 'g']

var topUUID = uuid("t");
var topLevelCategory = DPmem(1, topUUID)
var topLevelCategoryToParams = mem(function(cat) {
return dirichlet(ones([possibleObservations.length, 1]));
});

var subordinateUUID = uuid("s");
var subordinateCategory = DPmem(1, function(parent) {
return {sub: subordinateUUID().slice(0, 2),
top: parent.slice(0,2)}});

var subordinateCategoryToParams = mem(function(cat) {
var params = getProbs(dirichlet(topLevelCategoryToParams(cat.top)));
return params
})

var sampleCategory = function() {return subordinateCategory(topLevelCategory())};

var sampleObservation = function() {
var cat = sampleCategory()
var probs = subordinateCategoryToParams(cat)
return categorical({vs: possibleObservations,
ps: probs})
}

viz.table(repeat(20, sampleObservation))

This code shows a model where each category is associated with a multinomial distribution over the following possible observations: ['a', 'b', 'c', 'd', 'e', 'f', 'g']. This distribution is drawn from a Dirichlet prior for each subordinate-level category. However, the pseudocounts for the Dirichlet distribution for each subordinate-level category are drawn from another Dirichlet distribution which is associated with the top-level category—all of the subordinate level categories which share a top-level category also have similar distributions over observations.

In fact, the model presented in Example: One-shot learning of visual categories works in the same way, except that each category is associated with Gaussian distribution and the mean and variance parameters are shared between subordinate level categories.

## The Hierarchical Dirichlet Process

In the last section, we saw an example where subordinate-level categories drew their hyperparameters from a shared Dirichlet distribution. It is also possible to build a similar model using a Dirichlet Process at each level [@Teh2012]. This model is known as the Hierarchical Dirichlet Process (HDP).

///fold:
var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function(key) {
return function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return key + s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
}
///
var baseMeasure = function() {return poisson(20)};
var topLevel = DPmem(10, baseMeasure)

print("Draws from Base Measure (poisson 20)")
viz(repeat(1000,  baseMeasure))
print("Draws from Top Level DP")
viz(repeat(1000, topLevel))
print("Draws from Component DP 1")
viz(repeat(1000, function() {return sampleObservation('component1')}));
print("Draws from Component DP 2")
viz(repeat(1000, function() {return sampleObservation('component2')}));
print("Draws from Component DP 2")
viz(repeat(1000, function() {return sampleObservation('component2')}));

In an HDP, there are several component Dirichlet Processes (labeled here as component1, component2, etc.). These component DPs all share another DP (called topLevel) as their base measure.

In the example above, we have used a poisson distribution as the base measure. The top-level DP concentrates this distribution into a number of points. Each of the component DPs then further concentrate this distribution—sharing the points chosen by the top-level DP, but further concentrating it, each in their own way.

A natural move is to combine the nCRP and HDP: the nCRP can be used to sample an unbounded set of hierarchically structured categories, and the HDP can be used to make these categories share observations in interesting ways.

Note: I’m pretty sure that was an error in the old probmods (they printed “sampleObservation(category)” and labeled it both “Root category” and “top level: …, subordinate level:…” I just printed the root category for “Root category”…

///fold:
var pickStick = function(sticks, J) {
return flip(sticks(J)) ? J : pickStick(sticks, J+1);
};

var makeSticks = function(alpha) {
var sticks = mem(function(index) {return beta(1, alpha)});
return function() {
return pickStick(sticks,1)
};
}

var DPmem = function(alpha, baseDist) {
var augmentedProc = mem(function(args, stickIndex) {return apply(baseDist, args)});
var DP = mem(function(args) {return makeSticks(alpha)});
return function(argsin) {
var stickIndex = DP(argsin)()
return augmentedProc(argsin, stickIndex);
}
}
var uuid = function(key) {
return function() {
var s4 = function() {
return (Math.floor((1 + Math.random()) * 0x10000)
.toString(16)
.substring(1));
}
return key + s4() + s4() + '-' + s4() + '-' + s4() + '-' +
s4() + '-' + s4() + s4() + s4();
}
}
///
var topUUID = uuid('t');
var topLevelCategory = DPmem(1, topUUID)

var rootCategory = DPmem(10.0, function(){return poisson(20)});
var sampleFromTop = DPmem(1, function(cat) {return rootCategory()});
var subordinateUUID = uuid('s');
var subordinateCategory = DPmem(1, function(parent) {
return {sub: subordinateUUID().slice(0, 2),
top: parent.slice(0,2)}});

var sampleCategory = function() {subordinateCategory(topLevelCategory())}

var sampleObservation = DPmem(1, function(cat){return sampleFromTop(cat.top)});

print("Root Category");
viz(repeat(1000, function() {rootCategory()}));
repeat(10, function() {
var category = sampleCategory();
var subordinate = category.sub;
var top = category.top;
print("Top level: " + top + ", Subordinate Level: " + subordinate);
viz(repeat(1000, function() {sampleObservation(category)}));
print("Top level: " + top);
viz(repeat(1000, function() {sampleFromTop(top)}));
})

Note that the nCRP and the HDP represent very different ways to construct distributions with hierarchically arranged non-parametric distributions. The nCRP builds a hiearchy of category types, while the HDP shares observations between multiple DPs.

## Example: Prototypes and Exemplars

An important debate in psychology and philosophy has concerned the nature of concepts. The classical theory of concepts holds that they can defined in terms of necessary and sufficient conditions. For example, the concept dog might consist of a list of features— such as furry, barks, etc. If an object in the world matches the right features, then it is a dog.

However, it appears that, at least for some concepts, the classical theory faces some difficulties. For example, some concepts appear to be family resemblance categories (FRC). Members of a FRC share many features in commone, but the overlap is not total, and there is the possibility that two members of the category can share no feature in common, instead, each sharing features with other members of the category.

The philosopher Wittgenstein—who introduced the concept of Family Resemblance Categories—famously discussed the example of games. There are many different kinds of games: ball games, drinking games, children’s playground games, card games, video games, role-playing games, etc. It is not clear that there is a single list of features which they all share and which can uniquely identify them all as game. See @Murphy2004 for an in-depth discussion of many issues surrounding concepts.

Two theories have emerged to explain FRCs (and other related phenomena): prototype theories and exemplar theories. In prototype theories, concepts are considered to be based on a single stored prototype. People judge whether something is an example of a concept by comparing to this stored representation. For example, the prototype for dog might include features such as furry, barks, etc. An object is a member of a category (concept) to the degree that it matches the single stored prototype.

In exemplar theories, by contrast, it is assumed that people store all examples of a particular concept, rather than a single summary representation in prototype forms. A new object is classified by comparison with all of these forms.

Both prototype and exemplar theories are based on similarity, and the probability that an observation is assigned to category $c_{N}$ can be given by $p(c_{N} \mid x_N, \vec{x}_{N-1}, \vec{c}_{N-1}) = \frac{\eta_{N,j}\beta_{N,j}}{\sum_{c} \eta_{N,c}\beta_{N,c}}$ where $\eta_{N,i}$ is the similarity between observation $N$ and category $i$, and $\beta_{N,i}$ is the response bias for the category (i.e., its prior weight).

Exemplar models treat the similarity between observation $N$ and a category as a sum over all members of the category: $\eta_{N,i} = \sum_{i \mid c_{i} = j } \eta_{N,i}$ Prototype models treat the similarity as the similarity between observation $N$ and the single stored prototype: $\eta_{N,i} = \eta_{N,p_i}$ Notice that these two models can be seen as opposite ends of a spectrum; one estimates the category based on every member, while the other estimates based on a single member. There are clearly many intermediate points where each category can be viewed as a mixture over $K$ clusters.

@Griffiths2007 show how a large number of different models of categorization can be unified by viewing them all as special cases of a HDP which learns how many clusters each category should be represented by.

In particular, @Griffiths2007 examine the data from @Smith1998, which shows how learners undergo a transition from ptototype to exemplar representations during the course of learning.

The results are shown below.


text:
• # question_answer The equation of the common tangent to the curves ${{y}^{2}}=8x$ and $\mathbf{xy}\text{=}-\mathbf{1}$is- A)  $2y=x+8$                   B)  $y=x+2$      C)  $y=2x+1$       D)  $3y=9x+2$

[b] Equation of the tangent of the curve ${{y}^{2}}=8x\,be\,y=mx+\frac{2}{m}$ And it must satisfy the equation $-xy=-1$ $\Rightarrow x\left( mx+\frac{2}{m} \right)=-1\Rightarrow m{{x}^{2}}+\frac{2}{m}x+1=0$ Which is quadratic equation in x and its roots be equal. i.e. D=0 $\Rightarrow {{b}^{2}}-4ac=0{{\left( \frac{2}{m} \right)}^{2}}-4.m.1=0$ $\Rightarrow {{m}^{3}}=1$ $\therefore m=1$ Hence, equation of the comment tangent be $y=x+2$ Hence option [b] is correct.