Understanding Interdependency Through Complex Information Sharing

When the random variables that compose a system are independent, their joint distribution is given by the product of their marginal distributions. In this case, the marginals contain all that is to be learned about the statistics of the entire system. For an arbitrary joint probability density function (pdf), knowing the single variable marginal distributions is not enough to capture all there is to know about the statistics of the system.

To quantify this idea, let us consider the information stored in N discrete random variables $\mathbf{X}=(X_1,\cdots ,X_N)$ with joint pdf $p_{\mathbf{X}}$, where each $X_j$ takes values in a finite set with cardinality ${\Omega }_j$. Here, we refer to a Bayesian interpretation of the Shannon information as described in [14], which corresponds to the state of knowledge that an observer has with respect to a system as described by its probability distribution; in this context, uncertainty in the system corresponds to information that can be extracted by performing measurements. The maximal amount of information that could be stored in $\mathbf{X}$ is $H^{\left(0\right)}={\sum }_{j}log{\Omega }_j$, which corresponds to the entropy of the pdf $p_{\mathbf{U}}≔{\prod }_j{\overline{p}}_{X_j}$, where ${\overline{p}}_{X_j}\left(x\right)=1/{\Omega }_j$ is the uniform distribution for each random variable $X_j$. On the other hand, the joint entropy $H\left(\mathbf{X}\right)$ with respect to the true distribution $p_{\mathbf{X}}$ measures the actual uncertainty that the system possesses. Therefore, the difference corresponds to the decrease of the uncertainty about the system that occurs when one learns its pdf, i.e., the information about the system that is contained in its statistics. This quantity is known as negentropy [15] and can also be computed as where $p_{X_j}$ is the marginal of the variable $X_j$ and $D(·||·)$ is the Kullback–Leibler divergence. In this way, Equation (3) decomposes the negentropy into a term that corresponds to the information given by simple marginals and a term that involves higher-order marginals. The second term is known as the total correlation (TC) [16] (also known as multi-information [17]), which is equal to the mutual information for the case of $n=2$. Because of this, the TC has been suggested as an extension of the notion of mutual information for multiple variables.

An elegant framework for decomposing the TC can be found in [10] (for an equivalent formulation that does not rely on information geometry, see [18]). Let us call k-marginals the distributions that are obtained by marginalizing the joint pdf over $N-k$ variables. Note that the k-marginals provide a more detailed description of the system than the $(k-1)$-marginals, as the latter can be directly computed from the former by marginalizing the corresponding variables. In the case where only the one-marginals are known, the simplest guess for the joint distribution is ${\tilde{p}}_{\mathbf{X}}^{\left(1\right)}={\prod }_j{p}_{X_j}$. One way of generalizing this for the case where the k-marginals are known is by using the maximum entropy principle [14], which suggests choosing the distribution that maximizes the joint entropy while satisfying the constrains given by the partial (k-marginal) knowledge. Let us denote by ${\tilde{p}}_{\mathbf{X}}^{\left(k\right)}$ the pdf that achieves the maximum entropy while being consistent with all of the k-marginals, and let $H^{\left(k\right)}=H\left(\left\{{\tilde{p}}_{\mathbf{X}}^{\left(k\right)}\right\}\right)$ denote its entropy. Note that $H^{\left(k\right)}\ge H^{(k+1)}$, since the number of constrains that are involved in the maximization process that generates $H^{\left(k\right)}$ increases with k. It can therefore be shown that the following generalized Pythagorean relationship holds for the total correlation: Above, $\Delta H^{\left(k\right)}\ge 0$ measures the additional information that is provided by the k-marginals that was not contained in the description of the system given by the $(k-1)$-marginals. In general, the information that is located in terms with higher values of k is due to dependencies between groups of variables that cannot be reduced to combinations of dependencies between smaller groups.

It has been observed that in many practical scenarios, most of the TC of the measured data is provided by the lower marginals. It is direct to see that Therefore, if there exists a $k_0$, such that all $\Delta H^{\left(k\right)}$ are small for $k>k_0$, then ${\tilde{p}}_{\mathbf{X}}^{\left(k_0\right)}$ provides an accurate approximation for $p_{\mathbf{X}}$ from the point of view of the Kullback–Leibler divergence. In fact, it has been shown that pairwise maximum entropy models (i.e., $k_0=2$) can provide an accurate description of the statistics of many biological systems [19,20,21,22] and also some social organizations [23,24].

An alternative approach to study the interdependencies between many random variables is to analyze the ways in which they share information. This can be done by decomposing the joint entropy of the system. For the case of two variables, the joint entropy can be decomposed as suggesting that it can be divided into shared information, $I(X_1;X_2)$, and into terms that represent information that is exclusively located in a single variable, i.e., $H\left(X_1\right|X_2)$ for $X_1$ and $H\left(X_2\right|X_1)$ for $X_2$.

In systems with more than two variables, one can compute the total information that is exclusively located in one variable as $H_{\left(1\right)}≔{\sum }_{j=1}^{N}H(X_j|{\mathbf{X}}_j^c)$, where ${\mathbf{X}}_j^c$ denotes all of the system’s variables, except $X_j$. The difference between the joint entropy and the sum of all exclusive information terms, $H_{\left(1\right)}$, defines a quantity known [25] as the dual total correlation (DTC):which measures the portion of the joint entropy that is shared between two or more variables of the system (the superscripts and subscripts are used to reflect that $H^{\left(1\right)}\ge H\left(\mathbf{X}\right)\ge H_{\left(1\right)}$). When $N=2$, then $\text{DTC}=I(X_1;X_2)$, and hence, the DTC has also been suggested in the literature as a measure for the multivariate mutual information. Note that the DTC is also known as excess entropy in [26], whose definition differs from its typical use of this term in the context of time series, e.g., [27].

By comparing Equations (4) and (7), it would be appealing to look for a decomposition of the DTC of the form $\text{DTC}={\sum }_{k=2}^N\Delta H_{\left(k\right)}$, where $\Delta H_{\left(k\right)}\ge 0$ would measure the information that is shared by exactly k variables [28]. With this, one could define an internal entropy $H_{\left(j\right)}=H_{\left(1\right)}+{\sum }_{i=2}^j\Delta H_{\left(i\right)}$ as the information that is shared between at most j variables, in contrast to the external entropy $H^{\left(j\right)}=H^{\left(1\right)}-{\sum }_{i=2}^j\Delta H^{\left(i\right)}$, which describes the information provided by the j-marginals. These entropies would form a non-decreasing sequence This layered structure, and its relationship with the TC and the DTC, is graphically represented in Figure 1.

One of the main goals of this paper is to find expressions for $\Delta H_{\left(k\right)}$ for the case of $N=3$. It is interesting to note that even though the TC and DTC coincide for the case of $N=2$, these quantities are in general different for larger system sizes.

Perhaps the most natural approach to decompose the DTC and joint entropy is to apply the inclusion-exclusion principle, using a simplifying analogy that the entropies and areas have similar properties. A refined version of this approach can be found also in the I-measures [29] and in the multi-scale complexity [30]. For the case of three variables, this approach gives The last term is known as the co-information [31] (being closely related to the interaction information [32]) and can be defined using the inclusion-exclusion principle as As $I(X_1;X_2;X_2)=I(X_1;X_2)$, the co-information has also been proposed as a candidate for extending the mutual information to multiple variables. For a summary of the various possible extensions of the mutual information, see Table 1 and also additional discussion in [33].

It is tempting to coarsen the decomposition provided by Equation (9) and associate the co-information with $\Delta H_{\left(3\right)}$ and the remaining terms with $\Delta H_{\left(2\right)}$, obtaining a decomposition similar to the one presented in [30]. This idea is equivalent to building a Venn diagram for the information sharing between three variables as the one shown in Figure 2. However, the resulting decomposition and diagram (which differ from what is presented in Section 3.4) are not very intuitive, since the co-information can be negative.

As part of this temptation, it is appealing to consider the conditional mutual information $I(X_1;X_2|X_3)$ as the information contained in $X_1$ and $X_2$ that is not contained in $X_3$, just as the conditional entropy $H\left(X_1\right|X_2)$ is the information that is in $X_1$ and not in $X_2$. However, the latter interpretation works because conditioning always reduces entropy (i.e., $H\left(X_1\right)\ge H\left(X_1\right|X_2)$), while this is not true for mutual information; that is, in some cases, the conditional mutual information $I(X_1;X_2|X_3)$ can be greater than $I(X_1;X_2)$. This suggests that the conditional mutual information can capture information that extends beyond $X_1$ and $X_2$, incorporating higher-order effects with respect to $X_3$. Therefore, a better understanding of the conditional mutual information is required in order to refine the decomposition suggested by Equation (9).

An extended treatment of the conditional mutual information and its relationship to the mutual information decomposition can be found in [34,35]. For presenting these ideas, let us consider two random variables $X_1$ and $X_2$, which are used to predict Y. The predictability of Y, understood as the benefit of knowing the realization of $X_1$ and $X_2$ for performing inference over Y, is directly related to $I(X_1{X}_2;Y)$ if a natural data processing property is to be satisfied [36] (for simplicity, through the paper, we use the shorthand notation $X_1{X}_2=(X_1,X_2)$). Using the chain rule of the mutual information, the predictability can be decomposed as It is natural to think that the predictability provided by $X_1$, which is given by the term $I(X_1;Y)$, can be either unique or redundant with respect of the information provided by $X_2$. On the other hand, due to Equation (12), it is clear that the unique predictability contributed by $X_2$ must be contained in $I(X_2;Y|X_1)$. However, the fact that $I(X_2;Y|X_1)$ can be larger than $I(X_2;Y)$, while the latter contains both the unique and redundant contributions of $X_2$, suggests that there can be an additional predictability that is accounted for only by the conditional mutual information.

Following this rationale, we denote as synergistic predictability the part of the conditional mutual information that corresponds to evidence about the target that is not contained in any single predictor, but is only revealed when both are known. Is to be noticed that this notion is based on the asymmetrical roles played by predictors and the target. As an example of synergistic predictability, consider again the case in which $X_1$ and $X_2$ are independent random bits and $Y=X_1\mathtt{XOR}{X}_2$. Then, it can be seen that $I(X_1;Y)=I(X_2;Y)=0$ but $I(X_1{X}_2;Y)=I(X_1;Y|X_2)=1$. Hence, neither $X_1$ nor $X_2$ individually provide information about Y, although together, they fully determine it.

Further discussions about the notion of synergistic predictability can be found in [11,12,37,38,39].

Let us consider two variables $X_1$ and $X_2$ that are used to predict a target variable $Y:=X_3$. Intuitively, $I(X_1;Y)$ quantifies the predictability of Y that is provided by $X_1$. In the following, we want to find a function $\mathcal{R}(X_1{X}_2\to Y)$ that measures the redundant predictability provided by $X_1$ with respect to the predictability provided by $X_2$, and a function $\mathcal{U}(X_1\to Y|X_2)$ that measures the unique predictability that is provided by $X_1$, but not by $X_2$. Following [11], we first determine a number of desired properties that these functions should have.

The requirement that $\mathcal{R}(X_1{X}_2\to Y)$ and $\mathcal{U}(X_1\to Y|X_2)$ depend only on the pairwise marginals of $(X_1,Y)$ and $(X_2,Y)$, and not on their joint distribution, was first proposed in [39]. Although this property is not required in some of the existent literature (for example, in [38]), most of the predictability decompositions proposed so far respect it [11,37,39]. Furthermore, Axiom (3) states that the sum of the redundant and corresponding unique predictabilities given by each variable cannot be larger than the total predictability —in fact, the difference between the right and left hand terms of Axiom (3) gives the synergistic predictability, whose analysis will not be included in this work to avoid confusing it with the synergistic information, introduced in Section 3.2. Finally, Axiom (4) states that the redundant predictability is independent of the ordering of the predictors.

The following lemma determines the bounds for the redundant predictability (the proof is given in Appendix A).

Above, the subscript MMI corresponds to “minimal mutual information”. Note that ${\mathcal{R}}_{\text{MMI}}$ was introduced in [40] and has also been studied in [12,41].

In principle, the notion of redundant predictability takes the point of view of the target variable and measures the parts that can be predicted by both $X_1$ and $X_2$ when they are used by themselves, i.e., without combining them with each other. It is appealing to think that there should exist a unique function that provides such a measure. Nevertheless, these axioms define only very basic properties that a measure of redundant predictability should satisfy, and hence, in general, they are not enough for defining a unique function. In fact, a number of different predictability decompositions have been proposed in the literature [37,38,39,41].

From all of the candidates that are compatible with the axioms, the decomposition given in Corollary 1 gives the largest possible redundant predictability measure. It is clear that in some cases, this measure gives an over-estimate of the redundant predictability given by $X_1$ and $X_2$; for an example of this, consider $X_1$ and $X_2$ to be independent variables and $Y=(X_1,X_2)$. Nevertheless, Equation (14) has been proposed as a adequate measure for the redundant predictability of multivariate Gaussians [41] (for a corresponding discussion, see Section 6).

Let us now introduce an additional axiom, which will form the basis for our proposed information decomposition.

The role of Axiom (5) can be related to the role of the fifth of Euclid’s postulates, as, while seeming innocuous, their addition has interesting consequences in the corresponding theory. The following lemma explains why this decomposition is denoted as symmetrical and also shows fundamental bounds for these information functions (note that equivalent bounds for predictability decompositions can also be derived using Lemma 1). The proof is presented in Appendix C.

The strong symmetry property was first presented in [40], where it was shown that it is not compatible with the axioms presented in [11]. Regardless of this, strong symmetry is a highly desirable property when looking for a decomposition of the joint entropy. Discussions about strong symmetry can also be found in [34,38].

A symmetrical information decomposition can be used to decompose the following mutual information as In contrast to a decomposition based on the predictability, these measures address properties of the system $(X_1,X_2,X_3)$ as a whole, without being dependent on how it is divided between target and predictor variables (for a parallelism with respect to the corresponding predictability measures, see Table 2). Intuitively, $I_{\cap }(X_1;X_2;X_3)$ measures the shared information that is common to $X_1$, $X_2$ and $X_3$; $I_{\text{priv}}(X_1;X_3|X_2)$ quantifies the private information that is shared by $X_1$ and $X_3$, but not $X_2$, and $I_{\text{S}}(X_1;X_2;X_3)$ captures the synergistic information that exist between $(X_1,X_2,X_3)$. The latter is a non-intuitive mode of information sharing, whose nature we hope to clarify through the analysis of particular cases presented in Section 4 and Section 6.

Note also that the co-information can be expressed as Hence, strictly positive (resp. negative) co-information is a sufficient, although not necessary, condition for the system to have non-zero shared (resp. synergistic) information.

At this point, it is important to clarify a fundamental distinction that we make between the notions of predictability and information. The main difference between the two notions is that, in principle, the predictability only considers the predictable parts of the target, while the shared information also considers the joint statistics of the predictors. Although this distinction will be further developed when we address the case of Gaussian variables (cf. Section 6.3), let us for now present a simple example to help develop the intuitions about this issue.

In the following lemma, we will generalize the previous construction, whose simple proof is omitted.

May be the most remarkable property of symmetrized information decompositions is that, in contrast to directed ones, as defined in Section 3.1, they are uniquely determined by Axioms (1)–(5) for a number of interesting cases.

Pairwise independent variables and Markov chains are analyzed in Section 4 and Section 5.1, respectively.

Now, we use the notions of redundant, private and synergistic information functions for developing a non-negative decomposition of the joint entropy, which is based on a non-negative decomposition of the DTC. For the case of three discrete variables, by applying Equations (18) and (19) to Equation (9), one finds that From Equations (7) and (25), one can propose the following decomposition for the joint entropy: where In contrast to Equation (9), here, each term is non-negative because of Lemma 2. Therefore, Equation (26) yields a non-negative decomposition of the joint entropy, where each of the corresponding terms captures the information that is shared by one, two or three variables. Interestingly, $H_{\left(1\right)}$ and $\Delta H_{\left(2\right)}$ are homogeneous (being the sum of all of the exclusive information or private information of the system), while $\Delta H_{\left(3\right)}$ is composed by a mixture of two different information sharing modes. Interestingly, it can be seen from Equations (18) and (19) that the co-information is sometimes negative for compensating the triple counting of the synergy due to the sum of the three conditional mutual information terms.

An analogous decomposition can be developed for the case of continuous random variables. Nevertheless, as the differential entropy can be negative, not all of the terms of the decomposition can be non-negative. In effect, following the same rationale that leads to Equation (26), the following decomposition can be found: Above, $h\left(X\right)$ denotes the differential entropy of X, $\Delta H_{\left(2\right)}$ and $\Delta H_{\left(3\right)}$ are as defined in Equations (28) and (29), and Hence, although both the joint entropy $h(X_1,X_2,X_3)$ and $h_{\left(1\right)}$ can be negative, the remaining terms conserve their non-negative condition.

It can be seen that the lowest layer of the decomposition is always trivial to compute, and hence, the challenge is to find expressions for $\Delta H_{\left(2\right)}$ and $\Delta H_{\left(3\right)}$. In the rest of the paper, we will explore scenarios where these quantities can be characterized. Note that in general, $\Delta H_{\left(k\right)}\ne \Delta H^{\left(k\right)}$, although it is appealing to believe that there should exist a relationship between them. These issues are explored in the following sections.

Let us assume that $X_1$ and $X_2$ are pairwise independent, and hence, the joint pdf of $X_1$, $X_2$ and $X_3$ has the following structure: It is direct to see that in this case $p_{X_1{X}_2}={\sum }_{x_3}{p}_{X_1{X}_2{X}_3}=p_{X_1}{p}_{X_2}$, but $p_{X_1{X}_2|X_3}\ne p_{X_1|X_3}{p}_{X_2|X_3}$. Therefore, as $I(X_1;X_2)=0$, it is direct from Axioms (1) and (2) that any redundant predictability function satisfies $\mathcal{R}(X_1{X}_3\to X_2)=\mathcal{R}(X_2{X}_3\to X_1)=0$. However, the axioms are not enough to uniquely determine $\mathcal{R}(X_1{X}_2\to X_3)$, as the only restriction that the bound presented in Lemma 2 provides is $min\{I(X_1;X_3),I(X_2;X_3)\}\ge \mathcal{R}(X_1{X}_2\to X_3)\ge 0$ (note that in this case $I(X_1;X_2;X_3)=-I(X_1;X_2|X_3)\le 0$). Nevertheless, the symmetrized decomposition is uniquely determined, as shown in the next corollary that is a consequence of Theorem 1.

With this corollary, the unique decomposition of the $\text{DTC}=\Delta H_{\left(2\right)}+\Delta H_{\left(3\right)}$ that is compatible with Equations (28) and (29) can be found to be

Note that the terms $\Delta H_{\left(2\right)}$ and $\Delta H_{\left(3\right)}$ can be bounded as follows: The bound for $\Delta H_{\left(2\right)}$ follows from the basic fact that $I(X;Y)\le min\left\{H\right(X),H(Y\left)\right\}$. The second bound follows from

Let us focus in this section on the special case where $X_3=F(X_1,X_2)$ is a function of two independent random inputs and study its corresponding entropy decomposition. We will consider $X_1$ and $X_2$ as inputs and $F(X_1,X_2)$ to be the output. Although this scenario fits nicely in the predictability framework, it can also be studied from the shared information framework’s perspective. Our goal is to understand how F affects the information sharing structure.

As $H\left(X_3\right|X_1,X_2)=0$, we have The term $H_{\left(1\right)}$ hence measures the information of the inputs that is not reflected by the output. An extreme case is given by a constant function $F(X_1,X_2)=k$, for which $\Delta H_{\left(2\right)}=\Delta H_{\left(3\right)}=0$.

The term $\Delta H_{\left(2\right)}$ measures how much of F can be predicted with knowledge that comes from one of the inputs, but not from the other. If $\Delta H_{\left(2\right)}$ is large, then F is not “mixing” the inputs too much, in the sense that each of them is by itself able to provide relevant information that is not given also by the other. In fact, a maximal value of $\Delta H_{\left(2\right)}$ for given marginal distributions for $X_1$ and $X_2$ is given by $F(X_1,X_2)=(X_1,X_2)$, where $H_{\left(1\right)}=\Delta H_{\left(3\right)}=0$, and the bound provided in Equation (41) is attained.

Finally, due to Equation (34), there is no shared information, and hence, $\Delta H_{\left(3\right)}$ is just proportional to the synergy of the system. By considering Equation (42), one finds that F needs to leave some ambiguity about the exact values of the inputs in order for the system to possess synergy. For example, consider a 1-1 function F for which for every output $F(X_1,X_2)=x_3$; one can find the unique values $x_1$ and $x_2$ that generate it. Under this condition $H\left(X_1\right|X_3)=H\left(X_2\right|X_3)=0$, and hence, because of Equation (42), it is clear that a 1-1 function does not induce synergy. On the other extreme, we showed already that constant functions have $\Delta H_{\left(3\right)}=0$, and hence, the case where the output of the system gives no information about the inputs also leads to no synergy. Therefore, synergistic functions are those whose output values generate a balanced ambiguity about the generating inputs. To develop this idea further, the next lemma studies the functions that generate a maximum amount of synergy by generating for each output value different 1-1 mappings between their arguments.

Now, consider $F^{*}$ to be the function given in Equation (48) and assume that $X_1$ and $X_2$ are uniformly distributed. It can be seen that for each $z\in \mathcal{K}$, there exist exactly K ordered pairs of inputs $(x_1,x_2)$, such that $F^{*}(x_1,x_2)=z$, which define a bijection from $\mathcal{K}$ to $\mathcal{K}$. Therefore, and hence showing that the upper bound presented in Equation (52) is attained. ☐

The synergistic nature of the addition over finite fields helps to explain the central role it has in various fields. In cryptography, the one-time-pad [44] is an encryption technique that uses finite-field additions for creating a synergistic interdependency between a private message, a public signal and a secret key. This interdependency is completely destroyed when the key is not known, ensuring no information leakage to unintended receivers [45]. Furthermore, in network coding [46,47], nodes in the network use linear combinations of their received data packets to create and transmit synergistic combinations of the corresponding information messages. This technique has been shown to achieve multicast capacity in wired communication networks [47] and has also been used to increase the throughput of wireless systems [48].

It is tempting to associate the synergistic information with that which is only in the joint pdf, but not in the pairwise marginals, i.e., with $\Delta H^{\left(3\right)}$. However, the following result states that there can exist some synergy defined by the pairwise marginals themselves.

The previous corollary shows that $\Delta H^{\left(3\right)}$ measures only one part of the information synergy of a system, the part that can be removed without altering the pairwise marginals. Therefore, by considering Equations (29) and (60), one can find that for systems of three variables Note that PME systems with non-zero synergy, i.e., systems where the above inequality is strict, are easy to find. For example, consider $X_1$ and $X_2$ to be two independent equiprobable bits, and $X_3=X_1\mathtt{AND}{X}_2$. It can be shown that for this case, one has $\Delta H^{\left(3\right)}=0$ [18]. On the other side, as the inputs are independent, the synergy can be computed using Equation (37), and therefore, a direct calculation shows that

From the previous discussion, one can conclude that only a special class of pairwise distributions $p_{X_1{X}_2},p_{X_1{X}_3}$ and $p_{X_2{X}_3}$ is compatible with having null synergistic information. This is a remarkable result, as the synergistic information is usually considered to be an effect purely related to high-order marginals. For example, in [39] property $(\ast \ast )$ is introduced, which states that for given $p_{X_1{X}_3}$ and $p_{X_2{X}_3}$ there exists a joint pdf that is compatible with them while having zero synergistic predictability. In contrast, the above discussion has shown that in our framework, a symmetrized extension of $(\ast \ast )$ is not true, i.e., it is not always possible to find a joint pdf with zero synergistic information when the three pairwise marginals are given.

It would be interesting to have an expression for the minimal information synergy that a set of pairwise distributions requires, or equivalently, a symmetrized information decomposition for PME distributions. A particular case that allows a unique solution is discussed in the next section.

Markov chains maximize the joint entropy subject to constraints on only two of the three pairwise distributions. In effect, following the same rationale as in the proof of Theorem 2, it can be shown that Then, for fixed pairwise distributions $p_{X_1{X}_2}$ and $p_{X_2{X}_3}$, maximizing the joint entropy is equivalent to minimizing the conditional mutual information. Moreover, the maximal entropy is attained by the pdf that makes $I(X_1;X_3|X_2)=0$, which is precisely the Markov chain $X_1-X_2-X_3$ with joint distribution For the binary case, it can be shown that a Markov chain corresponds to an Ising distribution, like Equation (56), where the interaction term $J_{1,3}$ is equal to zero.