User:XORnado/sandbox

Partial Information Decomposition is an extension of information theory, that aims to generalize the pairwise relations described by information theory to the interaction of multiple variables.

Motivation

Information theory can quantify the amount of information a single source variable $X_{1}$ has about a target variable $Y$ via the mutual information $I(X_{1};Y)$. If we now consider a second source variable $X_{2}$, classical information theory can only describe the mutual information of the joint variable $\{X_{1},X_{2}\}$ with $Y$, given by $I(X_{1},X_{2};Y)$. In general however, it would be interesting to know how exactly the individual variables $X_{1}$ and $X_{2}$ and their interactions relate to $Y$.

Consider that we are given two source variables $X_{1},X_{2}\in \{0,1\}$ and a target variable $Y=XOR(X_{1},X_{2})$. In this case the total mutual information $I(X_{1},X_{2};Y)=1$, while the individual mutual information $I(X_{1};Y)=I(X_{2};Y)=0$. That is, there is synergistic information arising from the interaction of $X_{1},X_{2}$ about $Y$, which cannot be easily captured with classical information theoretic quantities.

Definition for two source variables

Partial information decomposition further decomposes the mutual information between the source variables $\{X_{1},X_{2}\}$ with the target variable $Y$ as

$I(X_{1},X_{2};Y)={\text{Unq}}(X_{1};Y\setminus X_{2})+{\text{Unq}}(X_{2};Y\setminus X_{1})+{\text{Syn}}(X_{1},X_{2};Y)+{\text{Red}}(X_{1},X_{2};Y)$

Here the individual components, called "information atoms", are defined as

• ${\text{Unq}}(X_{1};Y\setminus X_{2})$ is the unique information that $X_{1}$ has about $Y$, which is not in $X_{2}$
• ${\text{Unq}}(X_{2};Y\setminus X_{2})$ is the unique information that $X_{2}$ has about $Y$, which is not in $X_{1}$
• ${\text{Syn}}(X_{1},X_{2};Y)$ is the synergistic information that is in the interaction of $X_{1}$ and $X_{2}$ about $Y$
• ${\text{Red}}(X_{1},X_{2};Y)$ is the redundant information that is in both $X_{1}$ or $X_{2}$ about $Y$

There is, thus far, no universal agreement on how these terms should be defined, with different approaches that decompose information into redundant, unique, and synergistic components appearing in the literature.

General definition

A key principle for generalizing PID to $n$ source variables is the notion of containment of information within different subsets of those variables. For $n=2$, there are three relevant subsets of source indices: $\{1\}$, $\{2\}$, and $\{1,2\}$. Every possible way of how information about the target $Y$ could distributed over subsets of sources can be represented in a containment table, as shown below. This table also includes the empty set $\{\}$ for completeness.

Containment table for $n=2$, showing four distinct information atoms.

Type	$\{\}$	$\{S_{1}\}$	$\{S_{2}\}$	$\{S_{1},S_{2}\}$
Redundancy	0	1	1	1
Unique to $X_{1}$	0	1	0	1
Unique to $X_{2}$	0	0	1	1
Synergy	0	0	0	1

In this table, a 1 indicates that the information atom is contained in that subset of source variables, while a 0 indicates that it is not. Three main constraints ensure the table captures meaningful information relationships:

1. Empty-set constraint: There is no information in the empty set, so the first column must always be 0.
2. Full-set constraint: All the information available from the sources is contained in the full set, so the last column must always be 1.
3. Monotonicity: If an atom is contained in some subset of sources, it must also be contained in any superset of that subset (the table entries cannot “go back” from 1 to 0 as you move to larger sets).

To handle arbitrary $n$ sources, one constructs a larger containment table under these same constraints. Each row corresponds to an information atom characterized by how it is contained in the different subsets of source variables. Mathematically, each row can be seen as a monotonic Boolean function from the power set of sources to {0,1}, and the number of such functions is given by the Dedekind numbers (minus two, since the constant-zero and constant-one functions are prohibited by the first two constraints).

It is conventional to label an information atom by the smallest subsets (in terms of subset relations) from which it can be obtained. This is sufficient because due to the monotonicity constraint it is implied that the atom must be contained in all larger sets as well. For $n=2$, for example:

• The redundancy atom is denoted $\Pi (\{1\}\{2\})$.
• The unique atoms are $\Pi (\{1\})$ and $\Pi (\{2\})$.
• The synergy atom is $\Pi (\{1,2\})$.

Generally, the sets listed in the argument of $\Pi (\ldots )$ form a so called antichain, i.e. a collection of sets where no set is a subset of another one. A generic antichain is denoted by the letter $\alpha$ and the information atom corresponding to it by $\Pi (\alpha )$.

The full containment table for $n=3$ showing 18 distinct atoms and their antichain representation is shown in the following collapsible table:

Containment table for $n=3$

#	Atom $\Pi (\alpha )$	$\{\}$	$\{S_{1}\}$	$\{S_{2}\}$	$\{S_{3}\}$	$\{S_{1},S_{2}\}$	$\{S_{1},S_{3}\}$	$\{S_{2},S_{3}\}$	$\{S_{1},S_{2},S_{3}\}$
1	$\Pi (\{1,2,3\})$	0	0	0	0	0	0	0	1
2	$\Pi (\{1\})$	0	1	0	0	1	1	0	1
3	$\Pi (\{2\})$	0	0	1	0	1	0	1	1
4	$\Pi (\{3\})$	0	0	0	1	0	1	1	1
5	$\Pi (\{1,2\})$	0	0	0	0	1	0	0	1
6	$\Pi (\{1,3\})$	0	0	0	0	0	1	0	1
7	$\Pi (\{2,3\})$	0	0	0	0	0	0	1	1
8	$\Pi (\{1\}\{2\})$	0	1	1	0	1	1	1	1
9	$\Pi (\{1\}\{3\})$	0	1	0	1	1	1	1	1
10	$\Pi (\{2\}\{3\})$	0	0	1	1	1	1	1	1
11	$\Pi (\{1\}\{2,3\})$	0	1	0	0	1	1	1	1
12	$\Pi (\{2\}\{1,3\})$	0	0	1	0	1	1	1	1
13	$\Pi (\{3\}\{1,2\})$	0	0	0	1	1	1	1	1
14	$\Pi (\{1,2\}\{1,3\})$	0	0	0	0	1	1	0	1
15	$\Pi (\{1,2\}\{2,3\})$	0	0	0	0	1	0	1	1
16	$\Pi (\{1,3\}\{2,3\})$	0	0	0	0	0	1	1	1
17	$\Pi (\{1\}\{2\}\{3\})$	0	1	1	1	1	1	1	1
18	$\Pi (\{1,2\}\{1,3\}\{2,3\})$	0	0	0	0	1	1	1	1

For an arbitrary set of $n$ sources $X_{1},\ldots ,X_{n}$, a partial information decomposition is a collection of atoms $\Pi (\alpha )$, one per antichain, so that for every subset $\mathbf {b} \subseteq \{1,\ldots ,n\}$, the following condition is satisfied

$I(\mathbf {X} ^{\mathbf {b} };Y)\;=\;\sum _{\exists \,\mathbf {a} \in \alpha :\mathbf {a} \subseteq \mathbf {b} }\Pi (\alpha ).$

where $I(\mathbf {X} ^{\mathbf {b} };Y)$ is the mutual information provided by the sources indexed by $\mathbf {b}$. Intuitively, this condition simply says that the mutual information provided by $\mathbf {b}$ should be the sum of atoms that are contained in it, i.e. those with a 1 on $\mathbf {b}$ in the containment table. By construction, these are exactly the atoms $\Pi (\alpha )$ with a subset $\mathbf {a} \subseteq \mathbf {b}$ in their antichain representation.

For $\mathbf {b} =\{1,\dots ,n\}$, the condition states that all atoms have to sum up to the joint mutual information. This is because the sets contained in any $\alpha$ are always subsets of the full set $\{1,\dots ,n\}$ and therefore the condition under the summation sign is always fulfilled.

The condition above specifies a linear system of equations relating the information atoms to mutual information. However, since the number of subsets of sources $\mathbf {X} ^{\mathbf {b} }$ grows exponentially in $n$ while the number of information atoms grows super-exponentially, the system becomes more and more underdetermined as $n$ grows. Already for $n=2$ it provides three equations for four unknowns. Hence, there is no unique solution for the information atoms $\Pi (\alpha )$.

Various proposals have been made to resolve this underdetermination by imposing additional constraints on the information atoms. Typically, these constraints tie the atoms to other information-theoretic quantities besides the mutual information. For instance, the original approach by Williams and Beer introduced a "redundancy function," while other authors have used "union information" or synergy functions. Importantly, these quantities are in general (i.e. for $n>2$) themselves composed of multiple information atoms and should not be confused with a single "redundancy atom" or "synergy atom."

Applications

Despite the lack of universal agreement, partial information decomposition has been applied to diverse fields, including climatology, neuroscience sociology, and machine learning Partial information decomposition has also been proposed as a possible foundation on which to build a mathematically robust definition of emergence in complex systems and may be relevant to formal theories of consciousness.

See also

• Mutual information
• Total correlation
• Dual total correlation
• Interaction information