Optimizing Bivariate Partial Information Decomposition

Abdullah Makkeh, Dirk Oliver TheisarXiv 2018 · DOI · arXiv

TL;DR

Information theory often struggles with "messy" functions that aren't quite convex or concave, making them a nightmare to optimize. This paper provides the first explicit formulas for the sub-gradients and super-gradients of the BROJA bivariate partial information decomposition measures, turning a difficult optimization problem into a tractable one for researchers.

What Problem Does This Paper Address?

In the world of information theory, Partial Information Decomposition (PID) is a framework used to tease apart how multiple source variables contribute information to a target variable. Specifically, it tries to separate information into four categories: shared (redundant), synergistic, and unique information from each source.

The "BROJA" framework (named after Bertschinger, Rauh, Olbrich, Jost, and Ay) is a popular way to quantify these components. However, there’s a major mathematical hurdle: the BROJA measures—Shared Information (SI), Complementary Information (CI), and Unique Information (UI)—are neither convex nor concave over the space of probability distributions.

This "ill-behaved" nature means that if you want to find a distribution that maximizes shared information or minimizes unique information, standard optimization toolkits often fail. This paper fills that gap by providing the mathematical "compass" (gradients and sub-gradients) needed to navigate these complex functional landscapes.

Methods

The authors employ tools from convex analysis and optimization theory. The core of their approach involves:

  1. Defining a Base Optimization Problem: They define a function $M(p)$ based on maximizing conditional entropy subject to marginal constraints.
  2. Lagrange Multipliers: By analyzing the dual of this entropy maximization problem, they identify Lagrange multipliers ($\lambda$ and $\mu$) that certify optimality.
  3. Deriving Gradients: The breakthrough is Theorem 4, where the authors provide explicit, closed-form expressions for the derivatives (or sub/super-gradients) of all four BROJA measures. These formulas are expressed in terms of the original probability distribution $p$ and the Lagrange multipliers found in the previous step.
  4. Local Behavior Analysis: They prove that while the measures aren't globally well-behaved, they are locally predictable: CI and SI act concavely, while the UI measures act convexly at points where they aren't smooth.

Datasets

As a theoretical paper in mathematical information theory, no empirical datasets were used. The work focuses on proving identities and properties that apply to any finite-range random variables.

Key Insights and Ideas

  • The "Aha" Moment on Differentiability: The authors show that the differentiability of these complex information measures is tied directly to whether the optimal solution of an underlying entropy maximization problem has "full support" (i.e., no zero probabilities).
  • Predictable Non-Smoothness: Even when the functions aren't smooth (differentiable), they aren't chaotic. Knowing that SI is locally concave allows researchers to use specific "ascent" algorithms to find its maximum.
  • Bridging Theory and Extraction: The paper applies these derivatives to the concept of "Extractable Shared Information." This is the idea of finding a simplified version of a variable that retains as much shared information as possible. By providing the gradients, the authors turn this conceptual "search" into a standard continuous optimization problem.

Key Results

  • Theorem 4: This is the centerpiece, providing the exact formulas for $\partial CI(p)$, $\partial SI(p)$, $\partial UIy(p)$, and $\partial UIz(p)$. For example, the gradient of Shared Information is shown to be a combination of log-probabilities and the Lagrange multipliers from the entropy optimization.
  • Corollary 5: Formally categorizes the local convexity/concavity of the measures, providing a roadmap for which optimization algorithms (convex vs. concave) should be applied to which measure.
  • Tractable Shared Information: The authors define $SI^\clubsuit_m(p)$, a version of extractable shared information that is algorithmically tractable, moving it from a theoretical supremum to a solvable optimization problem.

Limitations and Future Work

The authors acknowledge a significant hurdle in the "probabilistically extractable" version of shared information ($SI^{prext}$). Because the dimension of the variable being optimized over can be arbitrary, the problem becomes infinite-dimensional and "basically intractable" from a direct algorithmic standpoint.

Future work will likely involve implementing these gradient formulas into software libraries (like the Discrete Information Theory (dit) package in Python) to allow data scientists to practically optimize PID measures in real-world datasets, such as neural firing patterns or financial time series.

Summary updated

Abstract

None of the BROJA information decomposition measures $\mbox{SI}, \mbox{CI}, \mbox{UIy}, \mbox{UIz}$ are convex or concave over the probability simplex. In this paper, we provide formulas for the sub-gradient and super-gradients of any of the information decomposition measures. Then we apply these results to obtain an optimum of some of these information decomposition measures when optimized over a constrained set of probability distributions.
BibTeX
@misc{makkeh2018optimizing,
  author = {Abdullah Makkeh and Dirk Oliver Theis},
  title = {{Optimizing Bivariate Partial Information Decomposition}},
  year = {2018},
  eprint = {1802.03947},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.03947},
}
Figure