Maximum Entropy Function

The Maximum Entropy Function of Salamatian, Cohen, and Médard [SCMedard16] is an approximate Gács-Körner Common Information that admits a small “helper” rate. It captures the largest entropy of a binary function \(\phi_X(X) \in \{-1, +1\}\) of one source whose agreement with a binary function \(\phi_Y(Y) \in \{-1, +1\}\) of the other source costs at most \(\epsilon\) bits to repair:

\[M_\epsilon(X; Y) = \max_{\phi_X, \phi_Y} \H{\phi_X(X)} \quad \text{s.t.} \quad \H{\phi_X(X) \mid \phi_Y(Y)} \le \epsilon.\]

When the bipartite graph of \(p_{X,Y}\) has disjoint components, the optimal pair is the connected-component indicator and \(M_0 = \K{X : Y}\). Allowing \(\epsilon > 0\) lets the optimizer commit to a “near”-Gács-Körner partition that misses agreement on a small fraction of joint outcomes (an “almost” common variable that a helper of rate \(\epsilon\) can patch up).

Algorithms

dit exposes both the exact optimization (Definition 3 in the paper) and the spectral approximation (Section IV-A) through a single function with a method argument.

  • method="spectral" (default) — the paper’s spectral algorithm. Compute \(Q = D_X^{-1/2}\, P\, D_Y^{-1/2}\) where \(D_X, D_Y\) are diagonal matrices of marginals. Subtract the trivial rank-one component \(\sqrt{p_X}\sqrt{p_Y}^T\) (which always carries the unit singular value of \(Q\)) and take the leading left/right singular vectors \(u, v\) of the residual. For a real threshold \(t\), set \(\phi_X(i) = \mathrm{sign}(u_i - t)\) and \(\phi_Y(j) = \mathrm{sign}(v_j - t)\). Sweep \(t\) across every distinct cut of \(u\) and return the largest feasible \(\H{\phi_X(X)}\).

  • method="exact" — brute force over every binary partition of \(\mathcal{X}\) and \(\mathcal{Y}\). Refuses to run when the alphabets would generate more than \(2^{20}\) partition pairs.

Worked example

The paper’s two leading examples both live on a \(4 \times 4\) joint with two disjoint blocks, optionally connected by a small “leak” edge.

The clean block-diagonal joint has Gács-Körner \(= 1\) bit; the binary indicator \(\phi_X(i) = +1\) iff \(i \in \{0, 1\}\) (and the same for \(\phi_Y\)) achieves \(\H{\phi_X(X)} = 1\) and \(\H{\phi_X(X) \mid \phi_Y(Y)} = 0\).

In [1]: from dit import Distribution as D

In [2]: from dit.multivariate import maxent_function

In [3]: outcomes = ['00', '01', '10', '11', '22', '23', '32', '33']

In [4]: pmf = [1/8] * 8

In [5]: d = D(outcomes, pmf)

In [6]: maxent_function(d, epsilon=0.0, method='exact')
Out[6]: 1.0

In [7]: maxent_function(d, epsilon=0.0, method='spectral')
Out[7]: 1.0

Moving the \((1, 1)\) atom to \((1, 2)\) joins the two blocks; Gács-Körner drops to \(0\) and \(M_0\) follows it. But once the helper is allowed enough rate to repair the leaked outcome, the original block partition becomes feasible again and \(M_\epsilon\) jumps back to \(1\) bit.

In [8]: from dit.multivariate import gk_common_information

In [9]: leak = D(['00', '01', '10', '12', '22', '23', '32', '33'], [1/8] * 8)

In [10]: gk_common_information(leak)
Out[10]: 0.0

In [11]: maxent_function(leak, epsilon=0.0, method='exact')
Out[11]: 0.0

In [12]: maxent_function(leak, epsilon=0.6, method='exact')
Out[12]: 1.0

Threshold sweep

The spectral threshold \(t\) parameterises the binary partitions returned by the algorithm; plot_maxent_function() plots \(\H{\phi_X(X))}\) at every distinct threshold position.

In [13]: from dit.multivariate import plot_maxent_function

In [14]: ax = plot_maxent_function(leak)

API

maxent_function(dist, epsilon, rvs=None, crvs=None, method='spectral')[source]

The Salamatian-Cohen-Médard Maximum Entropy Function:

\[M_{\epsilon}(X; Y) = \max_{\phi_X, \phi_Y} H(\phi_X(X)) \quad \text{s.t.} \quad H(\phi_X(X) \mid \phi_Y(Y)) \le \epsilon\]

where the maximization is over binary-valued functions \(\phi_X: \mathcal{X} \to \{-1, +1\}\) and \(\phi_Y: \mathcal{Y} \to \{-1, +1\}\). This is an approximate Gács-Körner common information that admits a helper of rate up to \(\epsilon\).

Parameters:

  • dist (Distribution) – The distribution from which to compute the measure.

  • epsilon (float) – The maximum allowed helper rate \(H(\phi_X(X) \mid \phi_Y(Y))\).

  • rvs (list, None) – A list selecting exactly two random variables (by index or name). If None, all variables of dist are used; dist must therefore be bivariate.

  • crvs (list, None) – Not supported; passing a non-empty crvs raises ditException.

  • method ({"spectral", "exact"}) –

    • "spectral" (default): the paper’s §IV-A approximation. Thresholds the second left/right singular vectors of \(Q = D_X^{-1/2} P D_Y^{-1/2}\) across all distinct cuts and returns the largest feasible \(H(\phi_X(X))\).

    • "exact": brute force over every binary partition of \(\mathcal{X}\) and \(\mathcal{Y}\). Refuses to run when the alphabets would produce more than ~:math:2^{20} partition pairs.

Returns:

M – The Maximum Entropy Function value (in bits when units are off).

Return type:

float

Raises:

ditException – If crvs is provided, rvs does not select exactly two variables, the method is unknown, or method=”exact” is requested on an alphabet that is too large to enumerate.

plot_maxent_function(dist, rvs=None, crvs=None, ax=None, **plot_kwargs)[source]

Plot the spectral Maximum Entropy Function value \(H(\phi_X(X))\) as a function of the threshold \(t\).

At each distinct threshold position on the second left singular vector \(u\) of \(Q = D_X^{-1/2} P D_Y^{-1/2}\), the binary function \(\phi_X(i) = \mathrm{sign}(u_i - t)\) (and similarly \(\phi_Y\) from the second right singular vector \(v\)) is constructed per Salamatian et al. 2016 §IV-A, and \(H(\phi_X(X))\) is plotted at each \(t\).

Parameters:

  • dist (Distribution) – The distribution from which to compute the curve.

  • rvs (list, None) – A list selecting exactly two random variables (by index or name). If None, all variables of dist are used; dist must therefore be bivariate.

  • crvs (list, None) – Not supported; passing a non-empty crvs raises ditException.

  • ax (matplotlib.axes.Axes, None) – The axis to draw on. A new figure and axis are created if None.

  • **plot_kwargs – Forwarded to matplotlib.axes.Axes.plot().

Returns:

ax – The axis containing the plot.

Return type:

matplotlib.axes.Axes

Raises:

ditException – If crvs is provided, rvs does not select exactly two variables, or the joint pmf is too degenerate for a spectral sweep (one of the alphabets has size < 2).