johnswentworth comments on johnswentworth’s Shortform

[johnswentworth]

Does The Information-Throughput-Maximizing Input Distribution To A Sparsely-Connected Channel Satisfy An Undirected Graphical Model?

[EDIT: Never mind, proved it.]

Suppose I have an information channel $X\to Y$. The X components $X_1,...,X_m$ and the Y components $Y_1,...,Y_n$ are sparsely connected, i.e. the typical $Y_i$ is downstream of only a few parent X-components $X_{pa\left(i\right)}$. (Mathematically, that means the channel factors as $P\left[Y|X\right]={\prod }_{i}P\left[Y_i|X_{pa\left(i\right)}\right]$.)

Now, suppose I split the Y components into two sets, and hold constant any X-components which are upstream of components in both sets. Conditional on those (relatively few) X-components, our channel splits into two independent channels.

E.g. in the image above, if I hold $X_4$ constant, then I have two independent channels: $(X_1,X_2,X_3)\to (Y_1,Y_2,Y_3,Y_4)$ and $(X_5,X_6,X_7)\to (Y_5,Y_6,Y_7,Y_8)$.

Now, the information-throughput-maximizing input distribution to a pair of independent channels is just the product of the throughput maximizing distributions for the two channels individually. In other words: for independent channels, we have independent throughput maximizing distribution.

So it seems like a natural guess that something similar would happen in our sparse setup.

Conjecture: The throughput-maximizing distribution for our sparse setup is independent conditional on overlapping X-components. E.g. in the example above, we’d guess that $P\left[X\right]=P\left[X_4\right]P[X_1,X_2,X_3|X_4]P[X_5,X_6,X_7|X_4]$ for the throughput maximizing distribution.

If that’s true in general, then we can apply it to any Markov blanket in our sparse channel setup, so it implies that $P\left[X\right]$ factors over any set of X components which is a Markov blanket splitting the original channel graph. In other words: it would imply that the throughput-maximizing distribution satisfies an undirected graphical model, in which two X-components share an edge if-and-only-if they share a child Y-component.

It’s not obvious that this works mathematically; information throughput maximization (i.e. the optimization problem by which one computes channel capacity) involves some annoying coupling between terms. But it makes sense intuitively. I’ve spent less than an hour trying to prove it and mostly found it mildly annoying though not clearly intractable. Seems like the sort of thing where either (a) someone has already proved it, or (b) someone more intimately familiar with channel capacity problems than I am could easily prove it.

So: anybody know of an existing proof (or know that the conjecture is false), or find this conjecture easy to prove themselves?

[johnswentworth]

Proof

Specifically, we’ll show that there exists an information throughput maximizing distribution which satisfies the undirected graph. We will not show that all optimal distributions satisfy the undirected graph, because that’s false in some trivial cases—e.g. if all the $Y$’s are completely independent of $X$, then all distributions are optimal. We will also not show that all optimal distributions factor over the undirected graph, which is importantly different because of the $P\left[X\right]>0$ caveat in the Hammersley-Clifford theorem.

First, we’ll prove the (already known) fact that an independent distribution $P\left[X\right]=P\left[X_1\right]P\left[X_2\right]$ is optimal for a pair of independent channels $(X_1\to Y_1,X_2\to Y_2)$; we’ll prove it in a way which will play well with the proof of our more general theorem. Using standard information identities plus the factorization structure $Y_1-X_1-X_2-Y_2$ (that’s a Markov chain, not subtraction), we get

$MI(X;Y)=MI(X;Y_1)+MI(X;Y_2|Y_1)$

$=MI(X;Y_1)+\left(MI\right(X;Y_2)-MI(Y_2;Y_1)+MI(Y_2;Y_1|X\left)\right)$

$=MI(X_1;Y_1)+MI(X_2;Y_2)-MI(Y_2;Y_1)$

Now, suppose you hand me some supposedly-optimal distribution $P\left[X\right]$. From $P$, I construct a new distribution $Q\left[X\right]:=P\left[X_1\right]P\left[X_2\right]$. Note that $MI(X_1;Y_1)$ and $MI(X_2;Y_2)$ are both the same under $Q$ as under $P$, while $MI(Y_2;Y_1)$ is zero under $Q$. So, because $MI(X;Y)=MI(X_1;Y_1)+MI(X_2;Y_2)-MI(Y_2;Y_1)$, the $MI(X;Y)$ must be at least as large under $Q$ as under $P$. In short: given any distribution, I can construct another distribution with as least as high information throughput, under which $X_1$ and $X_2$ are independent.

Now let’s tackle our more general theorem, reusing some of the machinery above.

I’ll split $Y$ into $Y_1$ and $Y_2$, and split $X$ into $X_{1-2}$ (parents of $Y_1$ but not $Y_2$), $X_{2-1}$ (parents of $Y_2$ but not $Y_1$), and $X_{1\cap 2}$ (parents of both). Then

$MI(X;Y)=MI(X_{1\cap 2};Y)+MI(X_{1-2},X_{2-1};Y|X_{1\cap 2})$

In analogy to the case above, we consider distribution $P\left[X\right]$, and construct a new distribution $Q\left[X\right]:=P\left[X_{1\cap 2}\right]P\left[X_{1-2}|X_{1\cap 2}\right]P\left[X_{2-1}|X_{1\cap 2}\right]$. Compared to $P$, $Q$ has the same value of $MI(X_{1\cap 2};Y)$, and by exactly the same argument as the independent case $MI(X_{1-2},X_{2-1};Y|X_{1\cap 2})$ cannot be any higher under $Q$; we just repeat the same argument with everything conditional on $X_{1\cap 2}$ throughout. So, given any distribution, I can construct another distribution with at least as high information throughput, under which $X_{1-2}$ and $X_{2-1}$ are independent given $X_{1\cap 2}$.

Since this works for any Markov blanket $X_{1\cap 2}$, there exists an information thoughput maximizing distribution which satisfies the desired undirected graph.

[testingthewaters]

I suppose another way to look at this is the overlapping components are the blanket states in some kind of time dependent markov blanket setup, right?

In the scenario you created you could treat $x_1,x_2,x_3$as the some shielded state at time step $t$, so $i_t$. Then $x_5,x_6,x_7$ are states outside of the blanket, so $e_t$ (which group of states is $i$ and which is $e$ don’t really matter, so long as they are on either side of the blanket). $y_1,y_2,y_3,y_4$ ^[1]become $i_{t+1}$, and $y_5,y_6,y_7,y_8$ become $e_{t+1}$.

Then $x_4$ becomes the blanket $b_t$ such that

$I(i_{t+1},e_{t+1}|b_t)\approx 0$

and

$P(i_{t+1},e_{t+1}|i_t,e_t,b_t)=P(i_{t+1}|i_t,b_t)\cdot P(e_{t+1}|e_t,b_t)$

With all that implies. In fact you can just as easily have three shielded states, or four, using this formulation.

(the setup for this is shamelessly ripped off from @Gunnar_Zarncke ’s unsupervised agent detection work)

1. ^

   Did you miss an arrow going to $y_4$ ?

[Daniel C]

(Was in the middle of writing a proof before noticing you did it already)

I believe the end result is that if we have $Y=(Y_1,Y_2)$, $X=(X_1,X_2,X_3)$ with $P\left(Y|X\right)=P(Y_1|X_1,X_3)P(Y_2|X_2,X_3)$ ($X_1$ upstream of $Y_1$, $X_2$ upstream of $Y_2$, $X_3$ upstream of both),

then maximizing $I(X;Y)$ is equivalent to maximizing $I(Y_1;X_1,X_3)$$+I(Y_2;X_2,X_3)$$-I(Y_1;Y_2)$.

& for the proof we can basically replicate the proof for additivity except substituting the factorization $P(X_1,X_2,X_3)=P\left(X_3\right)P\left(X_1|X_3\right)P\left(X_2|X_3\right)$ as assumption in place of independence, then both directions of inequality will result in $I(Y_1;X_1,X_3)$$+I(Y_2;X_2,X_3)$$-I(Y_1;Y_2)$.

[EDIT: Forgot $-I(Y_1;Y_2)$ term due to marginal dependence $P(Y_1,Y_2)\ne P\left(Y_1\right)P\left(Y_2\right)$]