Functional Common Information

The functional common information captures the minimum amount of information neccessary to capture all of a distribution’s share information using a function of that information. In other words:

\[\begin{split}\F{X_{0:n} \mid Y_{0:m}} = \min_{\substack{\ind X_{0:n} \mid Y_{0:m}, W \\ W = f(X_{0:n}, Y_{0:m})}} \H{W}\end{split}\]

It was introduced in [JC17].

Computation

A function \(W\) is a partition of the support, and \(X_{0:n}\) are independent given \(W = w\) (and \(Y_{0:m}\)) exactly when the outcomes in that block carry a product distribution on a combinatorial rectangle. Because \(\H{W}\) is a sum of per-block costs \(-p(w) \log_2 p(w)\), the functional common information is a minimum-weight exact cover of the support by such blocks, which dit solves exactly as an integer program. Without conditioning, every block lies within one connected component of the support (the blocks of the Gács-Körner common variable), so each component is solved independently.

Relationship To Other Measures of Common Information

Since this is an additional constraint on the Exact common information, it is generally larger than it, and since its constraint is weaker than that of the MSS Common Information, it is generally less than it:

\[\G{X_{0:n}} \leq \F{X_{0:n}} \leq \M{X_{0:n}}\]

API

functional_common_information(dist, rvs=None, crvs=None, return_partition=False)[source]

Compute the functional common information, F, of dist. It is the entropy of the smallest random variable W such that all the variables in rvs are rendered independent conditioned on W (and crvs), and W is a function of rvs and crvs.

Parameters:

  • dist (Distribution) – The distribution from which the functional common information is computed.

  • rvs (list, None) – A list of lists. Each inner list specifies the indexes of the random variables used to calculate the total correlation. If None, then the total correlation is calculated over all random variables, which is equivalent to passing rvs=dist.rvs.

  • crvs (list, None) – A single list of indexes specifying the random variables to condition on. If None, then no variables are conditioned on.

  • return_partition (bool) – If True, also return the optimal W as a partition of the outcomes of dist: a frozenset of blocks, each a frozenset of outcomes.

Returns:

  • F (float) – The functional common information.

  • partition (frozenset of frozensets) – The optimal W, only if return_partition is True.

functional_variable(dist, rvs=None, crvs=None)[source]

Return dist with the optimal functional common variable W appended.

W is the least-entropy function of rvs and crvs rendering rvs independent given crvs, so entropy(d, [d.outcome_length() - 1]) is the functional common information. Its values are block labels 0, 1, ... (as strings when the outcomes of dist have string symbols).

Parameters:

  • dist (Distribution) – The distribution of interest.

  • rvs (list, None) – A list of lists. Each inner list specifies the indexes of the random variables to render independent. If None, all random variables are used.

  • crvs (list, None) – A single list of indexes specifying the random variables to condition on. If None, then no variables are conditioned on.

Returns:

d – The support of dist with W appended as its last variable.

Return type:

Distribution