Natural latent maximizes sum of mutual information with each observable 

Claim: Given constraints on the entropy of a latent variable $\Lambda$, the redundancy and mediation errors are optimized exactly when the sum of mutual information ${\sum }_{i}I(X_i;\Lambda )$ is maximized.

Why is this useful?

• Early works on natural abstractions often talk about throwing away information while maintaining predictive power, but how should predictive power be measured? If you have multiple observables, you want to maximize predictive power for each of the observables you care about. In particular, you want your latent variable to include “shared information” that allows you to predict multiple variables at once. This is similar to maximizing ${\sum }_{i}I(X_i;\Lambda )$ while minimizing  $H\left(\Lambda \right)$ (as we’re trying to throw away information).
• Maximizing the sum of mutual information is likely computationally easier than directly optimizing for the mediation and redundancy conditions, so this framing could be helpful for anyone trying to find natural latents computationally 

Mediation

Mediation is one of the main conditions for naturality of latent variables. Intuitively, an (approximate) mediator $\Lambda$ captures (approximately) all the correlation between a collection of observables $X_1\dots X_n$. We will prove that a latent variable $\Lambda$ is an (optimal) approximate mediator $⟺$ it maximizes the sum of mutual information ${\sum }_{i}I(X_i;\Lambda )$ given constraint on entropy $H\left(\Lambda \right)\le k$
 

Intuition: To maximize the sum of mutual information ${\sum }_{i}I(X_i;\Lambda )$, it is beneficial to include information that is shared among multiple $X_i$ in $\Lambda$  (as that would increase multiple mutual information term). A mediator is a latent variable that captures all the shared information among the $X_i$s, so it will be selected for when maximizing ${\sum }_{i}I(X_i;\Lambda )$.

Proof:

1.  Note that the mediation error of $\Lambda$ is equivelant to the conditional total correlation $TC\left(X|\Lambda \right)=D_{KL}\left(P\right(X_1\dots X_n|\Lambda )\parallel P(X_1|\Lambda )\dots P(X_n|\Lambda \left)\right)$
2. We have  ${\sum }_{i}I(X_i;\Lambda )={\sum }_{i}H\left(X_i\right)-H\left(X_i|\Lambda \right)$, since each $H\left(X_i\right)$ term is fixed relative to $\Lambda$, maximizing the sum of mutual information is equivalent to minimizing the sum of conditional entropies ${\sum }_{i}H\left(X_i|\Lambda \right)$
3. We have  $D_{KL}\left(P\right(X_1\dots X_n|\Lambda )\parallel P(X_1|\Lambda )\dots P(X_n|\Lambda \left)\right)=TC\left(X|\Lambda \right)={\sum }_{i}H\left(X_i|\Lambda \right)-H\left(X|\Lambda \right)$, which means
   ${\sum }_{i}H\left(X_i|\Lambda \right)=H\left(X|\Lambda \right)+TC\left(X|\Lambda \right)=H\left(X\right)-I(X;\Lambda )+TC\left(X|\Lambda \right)\ge H\left(X\right)-H\left(\Lambda \right)+TC\left(X|\Lambda \right)$. For the last inequality we used $H\left(X\right)\ge I(X;\Lambda )$, we can obtain equality if $\Lambda$ is a deterministic function of $X$.  
4. Hence, if we have a constraint on entropy $H\left(\Lambda \right)\le k$, then we have the lower bound${\sum }_{i}H\left(X_i|\Lambda \right)\ge H\left(X\right)-H\left(\Lambda \right)+TC\left(X|\Lambda \right)\ge H\left(X\right)-k+TC\left(X|\Lambda \right)$. 
5. We can achieve equality on the lower bound by choosing a deterministic (w.r.t $X$) latent $\Lambda$ with entropy $H\left(\Lambda \right)=k$. For such $\Lambda$ we have ${\sum }_{i}H\left(X_i|\Lambda \right)=H\left(X\right)-k+TC\left(X|\Lambda \right)$, which means ${\sum }_{i}H\left(X_i|\Lambda \right)$ is minimized exactly when $TC\left(X|\Lambda \right)$ is minimized (as that's the only term which depends on $\Lambda$)
6. Since $TC\left(X|\Lambda \right)$ is nonnegative and equivalent to the mediation error, we conclude that ${\sum }_{i}H\left(X_i|\Lambda \right)$ is minimized exactly when the mediation error is minimized, and an exact mediator ($TC\left(X|\Lambda \right)=0$) with entropy $k$ always achieves minimal ${\sum }_{i}H\left(X_i|\Lambda \right)$ (hence maximal ${\sum }_{i}I(X_i;\Lambda )$) among latent variables with entropy $\le k$

Redundancy

The correspondence with the redundancy condition is quite simple: The sum of the redundancy errors are ${\sum }_{i}H\left(\Lambda |X_i\right)=nH\left(\Lambda \right)-{\sum }_{i}I(X_i;\Lambda )$, so if we have a constraint of the form $H\left(\Lambda \right)\ge k$, then we have ${\sum }_{i}H\left(\Lambda |X_i\right)=nH\left(\Lambda \right)-{\sum }_{i}I(X_i;\Lambda )\ge nk-{\sum }_{i}I(X_i;\Lambda )$, and the sum of redundancy errors are minimized exactly when ${\sum }_{i}I(X_i;\Lambda )$ is maximized and $H\left(\Lambda \right)=k$.

Putting it together

We've shown that given constraints on $H\left(\Lambda \right)$, both the mediation and the redundancy conditions are minimized exactly when the sum of mutual information ${\sum }_{i}I(X_i,\Lambda )$ is maximized, we can use this to simplify the search for natural latents, and while optimizing for this quantity there is no tradeoff between the redundancy and mediation errors.

However, note that mediation error increases as $H\left(\Lambda \right)$ decreases (the mediation error for the empty latent is simply total correlation), while the redundancy error increases with $H\left(\Lambda \right)$ (which is why we imposed $H\left(\Lambda \right)\le k$ for mediation but $H\left(\Lambda \right)\ge k$ for redundancy). So the entropy of the latent is exactly the parameter that represents the tradeoff between the mediation and redundancy errors.

In summary, we can picture a pareto-frontier of latent variables with maximal ${\sum }_{i}I(X_i;\Lambda )$ and different entropies, by ramping up the entropy of $\Lambda$ along the pareto-frontier we gradually increase the redundancy errors while reducing the mediation errors, and these are the only parameters relevant for latent variables that are pareto-optimal w.r.t the naturality conditions.

Preserving mutual information terms $⟹$ ( Stochastic  $⟹$ Deterministic Natural latent)

(See this post for background about the stochastic $\to$ deterministic natural latent conjecture)

We've shown that given fixed $H\left(\Lambda \right)$, both the redundancy and mediation errors of a latent $\Lambda$ are minimized when ${\sum }_{i}I(X_i,\Lambda )$ is maximized, while $H\left(\Lambda \right)$ is exactly the parameter the determines the tradeoff between redundancy and mediation errors (among pareto-optimal latent). We'll discuss how this could open up new angles of attack for the stochastic $\to$ deterministic natural latent conjecture.

Suppose that we have a stochastic natural latent $\Lambda$ that satisfies:

$I(X_2;\Lambda |X_1)\le ϵ$

$I(X_1;\Lambda |X_2)\le ϵ$

$TC\left(X|\Lambda \right)=I(X_1;X_2|\Lambda )\le ϵ$

From our result, we know that to construct a deterministic natural latent ${\Lambda }^{\prime }$, all we have to do is to determine the entropy $H\left({\Lambda }^{\prime }\right)$ and then select the latent that maximizes ${\sum }_{i}I(X_i,{\Lambda }^{\prime })$. The latter ensures that the latent is pareto-optimal w.r.t the mediation and determinism conditions, while the former selects a particular point on the pareto-frontier. 

Now suppose that our stochastic natural latent has a particular amount of mutual information with the joint observables $I(X_1,X_2;\Lambda )$. If the stochastic natural latent was a deterministic function of the observables, then we would have: 

$H\left(\Lambda \right)=I(X_1,X_2;\Lambda )$ (as that would imply $H(\Lambda |X_1,X_2)=H\left(\Lambda \right)-I(X_1,X_2;\Lambda )=0$)

So one heuristic for constructing a deterministic natural latent is to just set $H\left({\Lambda }^{\prime }\right)=I(X_1,X_2;\Lambda )$ and maximize  ${\sum }_{i}I(X_i,{\Lambda }^{\prime })$ given the entropy constraint (so that ${\Lambda }^{\prime }$ hopefully captures all the mutual info between $\Lambda$ and $X$). We will show that if ${\Lambda }^{\prime }$ preserves the mutual information with each observable (i.e. $I(X_i;{\Lambda }^{\prime })=I(X_i;\Lambda ),i=1,2$), then the mediation condition is conserved and the stochastic redundancy conditions implies the deterministic redundancy conditions

Preserving mutual information terms $⟹$ Mediation is conserved

Note that the mediation error is $TC\left(X|\Lambda \right)={\sum }_{i}H\left(X_i|\Lambda \right)-H\left(X|\Lambda \right)={\sum }_{i}H\left(X_i\right)-I(X_i;\Lambda )-H\left(X\right)+I(X;\Lambda )$

Since all $H\left(X_i\right)$ and $H\left(X\right)$ terms are fixed relative to $\Lambda$, the mediation error is completely unchanged if we replace $\Lambda$ with a deterministic latent ${\Lambda }^{\prime }$ that satisfies $I(X;{\Lambda }^{\prime })=H\left({\Lambda }^{\prime }\right)=I(X;\Lambda )$ and $I(X_i;{\Lambda }^{\prime })=I(X_i,\Lambda )$ for each $i$.

Preserving mutual information terms $⟹$ Redundancy is conserved

Note that using partial information decomposition^[1], we can decompose the stochastic redundancy errors as the following:

$I(X_1;\Lambda |X_2)=\text{Syn}(X_1,X_2;\Lambda )+\text{Uniq}(X_1;\Lambda )<ϵ⟹\text{Uniq}(X_1;\Lambda )<ϵ$

$I(X_2;\Lambda |X_1)=\text{Syn}(X_1,X_2;\Lambda )+\text{Uniq}(X_2;\Lambda )<ϵ⟹\text{Uniq}(X_2;\Lambda )<ϵ$

where $\text{Syn}(X_1,X_2;\Lambda )$ represents synergistic information of $X_2$ and $\Lambda$ w.r.t $\Lambda$  while $\text{Uniq}(X_1;\Lambda )$ represents unique information of $X_1$ w.r.t $\Lambda$. Intuitively, $I(X_1;\Lambda |X_2)$ represents the information that $X_1$ has about $\Lambda$ when we have access to $X_2$, which should include unique information that we can only derive from $X_1$ but not $X_2$, but also synergistic information that we can only derive when we have both $X_1$ and $X_2$.

We also have:

$I(X_1;\Lambda )=\text{Red}(X_1,X_2;\Lambda )+\text{Uniq}(X_1;\Lambda )$

$I(X_2;\Lambda )=\text{Red}(X_1,X_2;\Lambda )+\text{Uniq}(X_2;\Lambda )$

Intuitively, this is because $I(X_1;\Lambda )$ contains both the unique information about $\Lambda$ that you can only derive from $X_1$ but not $X_2$, and also the redundant information that you can derive from either $X_1$ or $X_2$. Note that since$0\le \text{Uniq}(X_1;\Lambda )\le ϵ$ and $0\le \text{Uniq}(X_2;\Lambda )\le ϵ$, we have

$\text{Red}(X_1,X_2;\Lambda )\le I(X_1;\Lambda )\le \text{Red}(X_1,X_2;\Lambda )+ϵ$

$\text{Red}(X_1,X_2;\Lambda )\le I(X_2;\Lambda )\le \text{Red}(X_1,X_2;\Lambda )+ϵ$

Similarly, we have:

$I(X_1,X_2;\Lambda )=\text{Red}(X_1,X_2;\Lambda )+\text{Uniq}(X_1;\Lambda )+\text{Uniq}(X_2;\Lambda )+\text{Syn}(X_1,X_2;\Lambda )$

where

 $\text{Uniq}(X_1;\Lambda )+\text{Uniq}(X_2;\Lambda )+\text{Syn}(X_1,X_2;\Lambda )\le 2ϵ⟹\text{Red}(X_1,X_2;\Lambda )\le I(X_1,X_2;\Lambda )\le \text{Red}(X_1,X_2;\Lambda )+2ϵ$

As a result, both $I(X_1,X_2;\Lambda )-I(X_1;\Lambda )$ and $I(X_1,X_2;\Lambda )-I(X_2;\Lambda )$ are bounded by $2ϵ$. This means that if we can find a deterministic latent ${\Lambda }^{\prime }$ that conserves all the relevant mutual information terms $I(X_1,X_2;|\Lambda )$, $I(X_1;|\Lambda )$ and $I(X_2;|\Lambda )$, then we can bound the deterministic redundancy errors:

$H\left({\Lambda }^{\prime }|X_1\right)=H\left({\Lambda }^{\prime }\right)-I(X_1;{\Lambda }^{\prime })=I(X_1,X_2;\Lambda )-I(X_1;\Lambda )<2ϵ$$H\left({\Lambda }^{\prime }|X_2\right)=H\left({\Lambda }^{\prime }\right)-I(X_2;{\Lambda }^{\prime })=I(X_1,X_2;\Lambda )-I(X_2;\Lambda )<2ϵ$

Conclusion

We've shown that a sufficient condition for mediation and redundancy to transfer from the stochastic to deterministic case is if the deterministic latent preserves the mutual information of the stochastic latent with both the joint observable $X$ as well as the individual observables $X_1$ and $X_2$. Given this, the remaining task would be to prove that such a deterministic latent always exists, or that it can preserve the mutual information terms up to some small error. In particular, if existence is guaranteed, then a tractable way to find the deterministic latent ${\Lambda }^{\prime }$ given a stochastic latent $\Lambda$ is to just set $H\left({\Lambda }^{\prime }\right)=I(X;\Lambda )$ and maximize  ${\sum }_{i}I(X_i;{\Lambda }^{\prime })$

1. ^{^}

   Note that PID depends on a choice of redundancy measure, but our proof holds for any choice that guarantees non-negativity of PID atoms

Maximum redund=Maximal redund, Minimum mediator=Minimal mediator, & Naturality=Shrinking regimes of tradeoffs

Previously, we've shown that given constraints on the entropy of a natural latent variable $\Lambda$, the mediation and redundancy errors are minimized exactly when the sum of mutual information with observables ${\sum }_{i}I(X_i;\Lambda )$ is maximized. In addition, the entropy $H\left(\Lambda \right)$ of the latent variable is exactly the parameter that represents the tradeoff between the mediation and redundancy condition. In particular, the mediation error can only reduce with $H\left(\Lambda \right)$ while the redundancy errors can only increase with $H\left(\Lambda \right)$.

However, there may be regimes where changes in $H\left(\Lambda \right)$ can reduce the mediation error without increasing the redundancy errors or vice versa. For instance:

• If we gradually increase $H\left(\Lambda \right)$ while perfectly preserving the redundancy conditions $H\left(\Lambda |X_i\right)=0,\forall i$, then we can reduce the mediation error (as it can only reduce with increasing $H\left(\Lambda \right)$) without increasing the redundancy errors (as they stay 0). Increasing $H\left(\Lambda \right)$ therefore becomes a weak pareto-improvement over the naturality conditions
• Similarly, if we gradually reduce $H\left(\Lambda \right)$ while perfectly preserving the mediation condition $TC\left(X|\Lambda \right)=0$, then we can reduce the redundancy errors without increasing the mediation error (as it stays 0)

If we define a maximum redund ${\Lambda }_{\ast }$ as a latent variable that satisfies the redundancy conditions $H\left({\Lambda }_{\ast }|X_i\right)=0$ and has the maximum entropy among redunds, then $H\left(\Lambda \right)\le H\left({\Lambda }_{\ast }\right)$ represents the regime where we can increase $H\left(\Lambda \right)$ without increasing the redundancy errors, since increasing $H\left(\Lambda \right)$ beyond $H\left({\Lambda }_{\ast }\right)$ would necessarily violate the redundancy condition given our assumption of maximum entropy

Similarly, define a minimum mediator ${\Lambda }^{\ast }$ as a mediator with minimal entropy (among mediators). Then $H\left(\Lambda \right)\ge H\left({\Lambda }^{\ast }\right)$ represents the regime where we can reduce entropy without increasing the mediation error, since reducing $H\left(\Lambda \right)$ below $H\left({\Lambda }^{\ast }\right)$ necessarily violates the mediation condition.

Combining these ideas, $H\left({\Lambda }_{\ast }\right)\le H\left(\Lambda \right)\le H\left({\Lambda }^{\ast }\right)$ represents the regime where changing $H\left(\Lambda \right)$ actually presents a tradeoff between the mediation and redundancy errors; the minimum mediator and maximum redund marks the boundaries for when weak pareto-improvements are possible.

Maximal redunds and minimal mediators

In natural latents we care about the uniqueness of latent variables, which is why we have concepts like minimal mediators and maximal redunds:

•  A minimal mediator is a mediator $\Lambda$ such that for any other mediator ${\Lambda }^{\prime }$ we have $H\left(\Lambda |{\Lambda }^{\prime }\right)<ϵ$. So a minimal mediator is an approximately deterministic function of any other mediator
• A maximal redund is a redund $\Lambda$ such that for any other redund ${\Lambda }^{\prime }$ we have $H\left({\Lambda }^{\prime }|\Lambda \right)<ϵ$. So any redund is approximately a deterministic function of the maximal redund

Through a universal-property-flavored proof, we can show approximate isomorphism among any pair of minimal mediators $X,Y$: Since $X$ is a minimal mediator and $Y$ is a mediator, $Y$ approximately determines $X$, and using a similar argument we conclude $X$ determines $Y$. The same reasoning also allows us to derive uniqueness of any pair of maximal redunds. Naturality occurs when the maximal redund converge with the minimal mediator.

However, note that the concepts of minimal mediators and maximal redunds are at least conceptually distinct from minimum mediators and maximum redunds. We shall therefore prove that these concepts are mathematically equivalent. This can be useful because it's much easier to find minimum mediators and maximum redunds computationally, but we ultimately care about the unqiueness property offered by minimal mediators and maximal redunds, proving an equivalence enables the former to have the uniqueness guarantees of the latter.

Minimum mediator = Minimal mediator (when minimal mediator exists)

Proof:

•  Let $Y$ be a minimal mediator and $Z$ be a minimum mediator
• Since $Y$ is a minimal mediator and $Z$ is a mediator, we have $H\left(Y|Z\right)<ϵ$ which means $I(Y;Z)\ge H\left(Y\right)-ϵ$
•  $H\left(Z|Y\right)=H\left(Z\right)-I(Z;Y)\le H\left(Z\right)-H\left(Y\right)+ϵ$
• Since $Z$ has minimal entropy, we have $H\left(Z\right)-H\left(Y\right)<0$ which means $H\left(Z|Y\right)<ϵ$
• For any other latent $\Lambda$, we have $H\left(Z|\Lambda \right)\le H\left(Z|Y\right)+H\left(Y|\Lambda \right)<2ϵ$, which means $Z$ is also a minimal mediator (up to error $2ϵ$)

In addition, we have $H\left(Y\right)\le H(Y,Z)=H\left(Z\right)+H\left(Y|Z\right)\le H\left(Z\right)+ϵ$ so $Y$ is also an approximate minimum mediator 

Maximum redund= Maximal redund

Proof:

• Suppose that $Z$ is maximum redund of $X_1\dots X_n$ and $Y$ is any other redund
•  $(Z,Y)$ is a redund since both $Z$ and $Y$ are deterministic functions of any $X_i$, since $Z$ is maximum redund we have $H\left(Z\right)\ge H(Z,Y)$
• $H(Z,Y)=H\left(Z\right)+H\left(Y|Z\right)$ hence we have $H\left(Z\right)\ge H\left(Z\right)+H\left(Y|Z\right)$. Since $H\left(Y|Z\right)$ is nonegative, we must have $H\left(Y|Z\right)=0$
• As a result, $H\left(Z\right)$ is also a maximal redund

Similarly, suppose that $Y$ is a maximal redund, then $H\left(Z\right)\le H(Z,Y)=H\left(Y\right)+H\left(Z|Y\right)\le H\left(Y\right)+ϵ$, which means $H\left(Y\right)\ge H\left(Z\right)-ϵ$ and $Y$ is also an approximate maximum redund.

Naturality as shrinking regime of tradeoffs

Recall that $H\left({\Lambda }_{\ast }\right)\le H\left(\Lambda \right)\le H\left({\Lambda }^{\ast }\right)$ (where ${\Lambda }^{\ast }$ is the minimum mediator and ${\Lambda }_{\ast }$ is the maximum redund) represents the regime where changing $H\left(\Lambda \right)$ actually presents a tradeoff between the mediation and redundancy errors. Due to the equivalence we proved, we can also think of  ${\Lambda }^{\ast }$ as the minimal mediator and ${\Lambda }_{\ast }$ as the maximal redund. 

We also know that naturality occurs when the minimal mediator converges with the maximal redund (as a natural latent satisfies both mediation and redundancy, and mediator determines redund); we can picture this convergence as if we're shrinking the gap between $H\left({\Lambda }_{\ast }\right)$ and $H\left({\Lambda }^{\ast }\right)$. In other words, naturality occurs exactly when the regime of tradeoff ($H\left({\Lambda }_{\ast }\right)\le H\left(\Lambda \right)\le H\left({\Lambda }^{\ast }\right)$) between the redundancy and mediation error is small. If we have exact naturality $H\left({\Lambda }_{\ast }\right)=H\left({\Lambda }^{\ast }\right)$, then pareto-improvements on the naturality conditions can always be made by nudging $H\left(\Lambda \right)$ closer to $H\left({\Lambda }^{\ast }\right)$. 

Combining this with our previous result, we conclude that that maximizing ${\sum }_{i}I(X_i,\Lambda )$ represents strong pareto-improvements over the naturality conditions; $H\left(\Lambda \right)\le H\left({\Lambda }_{\ast }\right)$ and $H\left(\Lambda \right)\ge H\left({\Lambda }^{\ast }\right)$ represents the regime where we can have weak pareto-improvements by nudging $H\left(\Lambda \right)$ closer to the boundary of $H\left({\Lambda }_{\ast }\right)$ or $H\left({\Lambda }_{\ast }\right)$; whereas $H\left({\Lambda }_{\ast }\right)\le H\left(\Lambda \right)\le H\left({\Lambda }^{\ast }\right)$ represents the regime of real tradeoffs between naturality conditions. An approximate natural latent exist exactly when the regime of real tradeoffs is small and we can pareto-improve towards naturality