Dual total correlation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In information theory, dual total correlation (Han 1978) or excess entropy (Olbrich 2008) is one of the two known non-negative generalizations of mutual information. While total correlation is bounded by the sum entropies of the n elements, the dual total correlation is bounded by the joint-entropy of the n elements. Although well behaved, dual total correlation has received much less attention than the total correlation. A measure known as "TSE-complexity" defines a continuum between the total correlation and dual total correlation (Ay 2001).

Definition[edit]

Venn diagram of information theoretic measures for three variables x, y, and z. The dual total correlation is represented by the union of the three mutual informations and is shown in the diagram by the yellow, magenta, cyan, and gray regions.


For a set of n random variables \{X_1,\ldots,X_n\}, the dual total correlation D(X_1,\ldots,X_n) is given by

 D(X_1,\ldots,X_n) = H\left( X_1, \ldots, X_n \right) - \sum_{i=1}^n H\left( X_i | X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_n \right) ,

where H(X_{1},\ldots,X_{n}) is the joint entropy of the variable set \{X_{1},\ldots,X_{n}\} and H(X_{i}| ... ) is the conditional entropy of variable X_{i}, given the rest.

Normalized[edit]

The dual total correlation normalized between [0,1] is simply the dual total correlation divided by its maximum value H(X_{1}, \ldots, X_{n}),

ND(X_1,\ldots,X_n) = \frac{D(X_1,\ldots,X_n)}{H(X_1,\ldots,X_n)} .

Bounds[edit]

Dual total correlation is non-negative and bounded above by the joint entropy H(X_1, \ldots, X_n).

 0 \leq D(X_1, \ldots, X_n) \leq H(X_1, \ldots, X_n) .

Secondly, Dual total correlation has a close relationship with total correlation, C(X_1, \ldots, X_n). In particular,

 \frac{C(X_1, \ldots, X_n)}{n-1} \leq D(X_1, \ldots, X_n) \leq (n-1) \; C(X_1, \ldots, X_n) .

Relation to other quantities[edit]

In measure theoretic terms, by the definition of dual total correlation:


D(X_1, \ldots, X_n) = \mu\left(\bigcup_i \tilde{X}_i \backslash \left(\bigcup_j \tilde{X}_j \backslash \bigcup_{k\neq j} \tilde{X}_k) \right)\right)

which is equal to the union of the pairwise mutual informations:


D(X_1, \ldots, X_n) = \mu\left(\bigcup_{i}\bigcup_{j\neq i} \left(\tilde{X}_i\cap\tilde{X}_j\right)\right)

History[edit]

Han (1978) originally defined the dual total correlation as,


\begin{align}
& {} \qquad  D(X_1,\ldots,X_n) \\[10pt]
& \equiv \left[ \sum_{i=1}^n H(X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_n ) \right] - (n-1) \; H(X_1, \ldots, X_n) \; .
\end{align}

However Abdallah and Plumbley (2010) showed its equivalence to the easier-to-understand form of the joint entropy minus the sum of conditional entropies via the following:


\begin{align}
& {} \qquad  D(X_1,\ldots,X_n) \\[10pt]
& \equiv \left[ \sum_{i=1}^n H(X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_n ) \right] - (n-1) \; H(X_1, \ldots, X_n) \\
& = \left[ \sum_{i=1}^n H(X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_n ) \right] + (1-n) \; H(X_1, \ldots, X_n) \\
& = H(X_1, \ldots, X_n) + \left[ \sum_{i=1}^n H(X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_n ) - H(X_1, \ldots, X_n) \right] \\
& = H\left( X_1, \ldots, X_n \right) - \sum_{i=1}^n H\left( X_i | X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_n \right)\; .
\end{align}

See also[edit]

References[edit]

  • Han T. S. (1978). Nonnegative entropy measures of multivariate symmetric correlations, Information and Control 36, 133–156.
  • Fujishige Satoru (1978). Polymatroidal Dependence Structure of a Set of Random Variables, Information and Control 39, 55–72. doi:10.1016/S0019-9958(78)91063-X.
  • Olbrich, E. and Bertschinger, N. and Ay, N. and Jost, J. (2008). How should complexity scale with system size?, The European Physical Journal B - Condensed Matter and Complex Systems. doi:10.1140/epjb/e2008-00134-9.
  • Abdallah S. A. and Plumbley, M. D. (2010). A measure of statistical complexity based on predictive information, ArXiv e-prints. arXiv:1012.1890v1.
  • Nihat Ay, E. Olbrich, N. Bertschinger (2001). A unifying framework for complexity measures of finite systems. European Conference on Complex Systems. pdf.