# Asymmetry between high order and low order interaction terms

Suppose we have a distribution for $$\mathbf{x}\in \{-1,1\}^n$$ and are interested in representing $$p(\mathbf{x})$$ as a linear exponential family with sufficient statistics of the form $$1,x_1,x_2,\ldots,x_1 x_2,\ldots,x_1 x_2 \cdots x_n$$

Suppose we know that entropy some measure of complexity of target distribution is bounded. We can view the parameter vector as a probability distribution $$D$$. Can we say anything about how the mass in $$D$$ is distributed among terms of various orders for some interesting complexity measure? Are there complexity measures that force mass onto low-order terms?

Restricting attention to graphical models means discarding 3rd and higher order terms. I'm interested in some explanation why this works so well

This was motivated by a similar question on CSTheory

Edit 11/29

Below is the probability simplex of of distributions over $$\{-1,1\}$$ valued $$x_1,x_2$$, in "probability" coordinates and in "log-linear" coordinates. In second picture, x,y axes correspond to coefficients in front of $$x_1$$ and $$x_2$$, z axis is the coefficient of $$x_1 x_2$$ term. You can see first and second order dimensions are symmetric, so bounding entropy (or any other symmetric function of distribution) is not enough to force mass onto low-order coefficients....

Mathematica source

• This made me discover there is some ML underground on TCS... Neh. – user88 Nov 29 '10 at 15:22
• I am curious: why did you specify the "graphical-model" tag for this question? – whuber Nov 29 '10 at 16:18
• added clarification – Yaroslav Bulatov Nov 29 '10 at 18:31

Under these assumptions any permutation of the monomials leads to exactly the same results, implying there is no inherent distinction between the low order terms and other terms.

If this doesn't seem convincing, let's look at a simple example. Pick any one of the monomials and set $f(\mathbf{x}, \theta)$ proportional to $\exp(\theta t(\mathbf{x}))$ where $t$ evaluates to $1$ for the selected monomial and otherwise equals $0$. In other words, letting $C(\theta) = \left(\exp(\theta) + 2^n - 1\right)^{-1}$ be the normalizing coefficient,

\eqalign{ f &= C(\theta) e^{\theta} &\text{ for this monomial}\cr &= C(\theta) &\text{ for all other monomials.} }

The entropy of this distribution equals

\eqalign{ H(\theta) &= -\mathbb{E}\left[\log(f)\right] \cr &= \frac{\log(2^n-1) + (1+e^x)\log(1+e^x) - x e^x}{1 + e^x} }

(writing $x = \theta - \log(2^n-1)$ to better isolate the dependence on $n$).

As $\theta$ ranges from $0$ to $\infty$, the entropy descends from $n/\log(2)$, which is the maximum attainable for any distribution, to $0$ (asymptotically), making the transition near $\theta = n \log(2)$. At this value of $\theta$ half the mass is concentrated on the chosen monomial and the entropy is approximately one-third of its maximum possible value.

We can play a more complicated game by focusing various amounts of the probability on any subset of the monomials we choose and putting vanishing amounts of probability on the remaining monomials. With such an approach we can meet any feasible lower bound on the entropy with a distribution that is as heavily concentrated on the chosen subset as possible. There is nothing to distinguish one subset from another. Thus, nothing informative can be said in general concerning the concentration of the distribution on the low order terms.

• I think you are right, I may be asking the wrong question – Yaroslav Bulatov Nov 29 '10 at 22:47