Kirkwood and Ouroboros Mutual Informations

Both measures in this module are the Kullback-Leibler divergence [CT06] from a joint distribution to a normalized log-linear product of its marginals,

\[D_{KL}\left(p \,\middle\|\, \frac{\tilde{p}}{Z}\right), \qquad \tilde{p}(x) = \prod_S p(x_S)^{c_S}, \qquad Z = \sum_x \tilde{p}(x).\]

They differ only in the exponents \(c_S\). Wherever a marginal used by \(\tilde{p}\) vanishes, \(\tilde{p}\) is set to zero, so the support of \(p\) is always contained in the support of the approximation and the divergence is finite.

Kirkwood Mutual Information

The generalized Kirkwood superposition approximation [Wat60] is the Möbius product over proper subsets of the variables:

\[\tilde{p}(x_{0:n}) = \prod_{\emptyset \neq S \subsetneq \{0, \ldots, n-1\}} p(x_S)^{(-1)^{n-1-|S|}}\]

For three variables this is the classical \(p(x, y) p(x, z) p(y, z) / \left(p(x) p(y) p(z)\right)\), and the divergence from its normalization was introduced by [WYY+10] as a fast screening statistic for gene-gene interactions. The Kirkwood mutual information \(K\) relates to the Co-Information through the log normalizer [KM20]:

\[K[X_0 : \cdots : X_{n-1}] = (-1)^n \I{X_0 : \cdots : X_{n-1}} + \log_2 Z\]

For two variables the approximation is the product of marginals, so \(K\) is the Mutual Information. The giant bit is reproduced exactly by its Kirkwood approximation, and parity carries exactly one bit:

In [1]: from dit.example_dists import giant_bit, n_mod_m

In [2]: from dit.multivariate import kirkwood_mutual_information as K

In [3]: [K(giant_bit(n, 2)) for n in range(3, 6)]
Out[3]: [0.0, 0.0, 0.0]

In [4]: [K(n_mod_m(n, 2)) for n in range(3, 6)]
Out[4]: [1.0, 1.0, 1.0]

Lower Orders

Truncating the Möbius (interaction) expansion of \(\log p\) at subsets of size at most \(k\) gives the order-\(k\) Kirkwood approximation [KYKG07]:

\[\tilde{p}_k(x_{0:n}) = \prod_{1 \leq |S| \leq k} p(x_S)^{c_S}, \qquad c_S = (-1)^{k-|S|} \binom{n-|S|-1}{k-|S|}\]

The order argument selects \(k\), which must lie between \(0\) and \(n-1\). The default, \(k = n-1\), is the standard approximation above. Order \(1\) is the product of marginals, so \(K_1\) is the Total Correlation. Order \(0\) is the uniform distribution. Because \(\hat{p}_k\) is log-linear in the \(k\)-marginals, \(K_k\) upper bounds the divergence from the maximum entropy distribution consistent with those marginals.

In [5]: [K(giant_bit(4, 2), order=k) for k in range(4)]
Out[5]: [3.0, 3.0, 0.0, 0.0]

Ouroboros Mutual Information

For three variables the Kirkwood approximation is a loop of channels, \(p(x \mid y) p(y \mid z) p(z \mid x)\), each variable feeding the next. For \(n \geq 4\) no such reading exists. A product of conditional distributions has exponents summing to zero, but the Kirkwood exponents sum to \(1 + (-1)^n\). Even for odd \(n \geq 5\), the \(\binom{n}{2}\) subsets of size \(n-2\) would each need a distinct channel output among only \(n\) subsets of size \(n-1\).

The order-\(k\) ouroboros approximation instead takes the symmetric geometric mean over every wiring in which each variable is the output of a channel fed by \(k\) of the other variables:

\[\tilde{p}_k(x_{0:n}) = \frac{\prod_{|S| = k+1} p(x_S)^{n / \binom{n}{k+1}}}{\prod_{|S| = k} p(x_S)^{n / \binom{n}{k}}}, \qquad 1 \leq k \leq n - 2\]

For \(n = 3\) and \(k = 1\) this is the Kirkwood approximation. For \(k = 1\) it is the \((n-1)\)-th root of the pairwise conditional composite likelihood [VRF11]. Because the approximation is log-linear in the \((k+1)\)-marginals, \(O_k\) upper bounds the divergence from the maximum entropy distribution consistent with those marginals. No canonical literature source is known for this construction.

Low orders detect structure that the Kirkwood approximation ignores. A triadic distribution alongside an independent bit has no four-way structure, but its pairwise ouroboros approximation misses the triad:

In [6]: from dit import Distribution as D

In [7]: from dit.example_dists import triadic

In [8]: from dit.multivariate import ouroboros_mutual_information as O

In [9]: d = triadic @ D(['0', '1'], [1/2, 1/2])

In [10]: [K(d), O(d, order=1), O(d, order=2)]
Out[10]: [0.0, 1.0, 0.0]

The unnormalized approximation \(\tilde{p}_k\) itself, and its additive Lancaster analogue, are constructed by dit.kirkwood_approximation() and dit.lancaster_approximation() (see Constructors and examples).

API

kirkwood_mutual_information(dist, rvs=None, crvs=None, order=None)[source]

Compute the Kirkwood mutual information: the Kullback-Leibler divergence from the joint distribution to its normalized generalized Kirkwood superposition approximation.

For variables \(X_0, \ldots, X_{n-1}\) the generalized Kirkwood approximation of order \(k\) truncates the Möbius (interaction) expansion of \(\log p\) at subsets of size at most \(k\) [KYKG07, Wat60]:

\[\tilde{p}_k(x) = \prod_{1 \leq |S| \leq k} p(x_S)^{c_S}, \qquad c_S = (-1)^{k-|S|} \binom{n-|S|-1}{k-|S|},\]

which need not sum to one. The default order \(k = n-1\) is the standard Kirkwood approximation, the Möbius product over proper subsets with \(c_S = (-1)^{n-1-|S|}\). Order 1 is the product of marginals and order 0 is the uniform distribution. With \(\hat{p}_k = \tilde{p}_k / Z\) and \(Z = \sum_x \tilde{p}_k(x)\), the measure is \(K_k = D_{KL}(p \| \hat{p}_k)\).

For three variables and the default order this is the divergence from the normalized Kirkwood superposition approximation used by [WYY+10]. At the default order it satisfies

\[K = (-1)^n I[X_0 : \cdots : X_{n-1}] + \log_2 Z,\]

where \(I\) is the coinformation [KM20]. Order 1 gives the total correlation, and order 0 gives \(\sum_i \log_2 |\mathcal{X}_i| - H[X_0, \ldots, X_{n-1}]\). Since \(\hat{p}_k\) is log-linear in the \(k\)-marginals, \(K_k\) upper bounds the divergence to the maximum entropy distribution matching them. For fewer than two variables the result is zero.

Parameters:

dist (Distribution) – The distribution from which the Kirkwood mutual information is calculated.
rvs (list, None) – A list of lists. Each inner list specifies the indexes of the random variables used to calculate the Kirkwood mutual information. If None, then it is calculated over all random variables.
crvs (list, None) – A single list of indexes specifying the random variables to condition on. If None, then no variables are conditioned on.
order (int, None) – The largest marginal size k used by the approximation. Must satisfy 0 <= k <= n - 1. If None, defaults to n - 1.

Returns:

K – The Kirkwood mutual information.

Return type:

float

Raises:

ditException – Raised if order is out of range.

Examples

>>> d = dit.example_dists.giant_bit(3, 2)
>>> dit.multivariate.kirkwood_mutual_information(d)
0.0
>>> d = dit.example_dists.n_mod_m(3, 2)
>>> dit.multivariate.kirkwood_mutual_information(d)
1.0
>>> dit.multivariate.kirkwood_mutual_information(d, order=1)
1.0

ouroboros_mutual_information(dist, rvs=None, crvs=None, order=None)[source]

Compute the order-k ouroboros mutual information: the Kullback-Leibler divergence from the joint distribution to its normalized order-k ouroboros approximation.

The order-k ouroboros approximation of \(X_0, \ldots, X_{n-1}\) is the symmetric geometric mean, over all wirings in which each variable is the output of a channel fed by k other variables, of the resulting products of conditional distributions:

\[\tilde{p}_k(x) = \frac{\prod_{|S| = k+1} p(x_S)^{n / \binom{n}{k+1}}} {\prod_{|S| = k} p(x_S)^{n / \binom{n}{k}}}, \qquad 1 \leq k \leq n - 2.\]

With \(\hat{p}_k = \tilde{p}_k / Z\) the measure is \(O_k = D_{KL}(p \| \hat{p}_k)\). For three variables and k = 1 it coincides with the Kirkwood mutual information. For k = 1 the approximation is the \((n-1)\)-th root of the pairwise conditional composite likelihood [VRF11]. Since \(\hat{p}_k\) is log-linear in the \((k+1)\)-marginals, \(O_k\) upper bounds the divergence to the maximum entropy distribution matching those marginals.

No canonical literature source is known for this construction.