Separable Computation of Information Measures

Xiangxiang Xu and Lizhong Zheng · 2025

Read Separable Computation of Information Measures by Xiangxiang Xu and Lizhong Zheng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-15301.txt.

Introduction

Xiangxiang Xu and Lizhong Zheng wrote this paper in two thousand twenty-five. It shows that many gauges of information can be computed from learned traits of the data, not from the raw data at all.

Under mild terms on the traits, a class of gauges splits in this way. The list runs from mutual information and f-information to two forms of common information and the information bottleneck. The work draws fresh links between these gauges and the web of dependence in the data. It also gives theory cover for the hands-on designs that gauge information through representation learning.

Catalog record

CREATORXiangxiang Xu and Lizhong Zheng
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-15301

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Separable Computation of Information Measures Xiangxiang Xu and Lizhong Zheng Abstract We study a separable design for computing information measures, where the information measure is computed from learned feature representations instead of raw data. Under mild assumptions on the feature representations, we demonstrate that a class of information measures admit such separable computation, including mutual information, f f -information, Wyner’s common information, Gács–Körner common information, and Tishby’s information bottleneck. Our development establishes several new connections between information measures and the statistical dependence structure. The characterizations also provide theoretical guarantees of practical designs for estimating information measures through representation learning. I Introduction The computation of information measures, e.g., mutual information, is a fundamental task in information theory [ 1 ] and its applications. In machine learning tasks, for example, computing information measures becomes a key step when using information-theoretic tools for algorithm analyses and designs. Due to the unknown statistical model behind practical data, information measures cannot be directly computed from the definitions. The high dimensionality and complicated structures of data also lead to an enormous computation complexity of non-parametric approaches. Recent developments employed deep learning techniques in designing information measure estimators [ 2 , 3 ] , leveraging the capability of deep neural networks in effectively processing high-dimensional and structured data. For instance, [ 3 ] proposed an approach to estimate mutual information by using deep neural networks to extract features from data and then applying a non-parametric mutual information estimator on the extracted features. Despite their performance gains on empirical evaluations, such designs are often heuristic without guarantees, where the learned features may fail to carry useful information for the estimation tasks [ 3 , Sec. 3.3] . In this paper, we formulate the problem of computing information measures from extracted features, which allows separable computation and implementation. We restrict to the bivariate case and consider computing an information measure \theta(X,Y) from a pair of random variables X and Y , where X or Y correspond to possibly high-dimensional data in practical applications. As illustrated in Fig. 1 , the separable computation is conducted by first learning features s(X) , t(Y) from X,Y , and then applying \theta -estimator on the extracted features. Our focus is on establishing the theoretical conditions such that the features contain the necessary information for estimating the \theta , i.e., \theta(X,Y)=\theta(s(X),t(Y)) . In particular, we assume that s(X) and t(Y) can be any sufficient statistics of X and Y , i.e., we have the Markov relations X-s(X)-Y and X-t(Y)-Y . This assumption allows flexible feature learning designs. Moreover, the statistical sufficiency allows feature extractors to discard irrelevant information while capturing the statistical dependence between X and Y [ 4 ] . Under this assumption, we establish several classical information measures admitting the separable computation, including mutual information and its variants using f -divergence, Wyner’s common information [ 5 ] , Gács–Körner common information [ 6 ] , and Tishby’s information bottleneck [ 7 ] . Our results provide theoretical guarantees of modular designs in applying deep neural networks for information measure estimations, which can lead to more systematic designs and improve implementation efficiency. Estimator \theta(X,Y) X \circ s(X) Y \circ t(Y) s t Feature Learning Fig. 1: Computing an information measure \theta(X,Y) in two steps: (1) obtain transformed variables s(X),t(Y) and (2) apply an estimator on s(X),t(Y) . For high-dimensional X , Y with unknown probability structures, the first step can be implemented by data-driven approaches, e.g., deep neural network training, corresponding to the feature learning process, where s(X) and t(Y) are the learned feature representations. II Preliminaries and Notations For a random variable Z , we denote the corresponding alphabet by \mathcal{Z} , use z to denote a specific value in \mathcal{Z} , and use P_{Z} to denote the probability distribution. Throughout our development, we restrict to a pair of discrete random variables X , Y on finite alphabets \mathcal{X},\mathcal{Y} . Without loss of generality, we assume P_{X} and P_{Y} have positive probability masses, i.e., P_{X}(x)>0 for all x\in\mathcal{X} and P_{Y}(y)>0 for all y\in\mathcal{Y} , since otherwise we can remove the zero-probability symbols from the alphabets. For n\geq 1 , we denote [n]\triangleq\{1,2,\dots,n\} . II-A Canonical Dependence Kernel and Modal Decomposition Given (X,Y)\sim P_{X,Y} the associated canonical dependence kernel (CDK) function [ 8 ] is defined as a joint function \mathfrak{i}_{X;Y} : \displaystyle\mathfrak{i}_{X;Y}(x,y)\triangleq\frac{P_{X,Y}(x,y)}{P_{X}(y)P_{Y}(y)}-1. (1) By applying the singular value decomposition (SVD) in the space of joint function, we can write CDK \mathfrak{i}_{X;Y} as a superposition of rank-one singular modes, referred to as its modal decomposition [ 9 ] : \displaystyle\mathfrak{i}_{X;Y}(x,y)=\sum_{i=1}^{K}\sigma_{i}\cdot f^{*}_{i}(x)g^{*}_{i}(y), (2) In particular, \sigma_{1}\geq\sigma_{2}\geq\dots\geq\sigma_{K}>0 are the singular values, where K\geq 0 denotes the rank of \mathfrak{i}_{X;Y} . Analogous to the orthogonality of singular vectors in matrix SVD, f^{*}_{i},g^{*}_{i} satisfy {\mathbb{E}}\left[f^{*}_{i}(X)f^{*}_{j}(X)\right]={\mathbb{E}}\left[g^{*}_{i}(Y)g^{*}_{j}(Y)\right]=\delta_{i,j} , for all i,j\in[K] . For convenience, we also define functions \displaystyle f^{*}\triangleq(f^{*}_{1},\dots,f^{*}_{K})^{\mathrm{T}},\quad g^{*}\triangleq(g^{*}_{1},\dots,g^{*}_{K})^{\mathrm{T}}. (3) For convenience, we further define \sigma_{0}\triangleq 1 , f^{*}_{0}\colon\mathcal{X}\ni x\mapsto 1 and g^{*}_{0}\colon\mathcal{Y}\ni y\mapsto 1 . Then, we can write the SVD of the density ratio as [cf. ( 1 )]: \displaystyle\frac{P_{X,Y}(x,y)}{P_{X}(x)P_{Y}(y)}=\sum_{i=0}^{K}\sigma_{i}\cdot f^{*}_{i}(x)g^{*}_{i}(y). II-B Sufficiency and Minimal Sufficiency Definition 1 Given X,Y , S=s(X) is a sufficient statistic of X for inferring Y if we have the Markov relation X-s(X)-Y . We call f(X) a minimal sufficient statistic if f(X) is sufficient, and for each given sufficient statistic S of X , f(X) is a function of S . We have the following useful characterization of sufficient statistics. A proof is provided in Section V-A . Proposition 1 Given X,Y and S=s(X),T=t(Y) , the following statements are equivalent: • X-S-Y , X-T-Y ; • X-S-T-Y ; • \displaystyle\frac{P_{X,Y}(x,y)}{P_{X}(x)P_{Y}(y)}=\frac{P_{S,T}(s(x),t(y))}{P_{S}(s(x))P_{T}(t(y))} for all x\in\mathcal{X},y\in\mathcal{Y} . From such equivalences, the Markov relation X-S-T-Y is equivalent to X-S-Y and X-T-Y , i.e., both S and T are sufficient statistics. In addition, the following result demonstrates a useful connection between minimal sufficiency and the modal decomposition of CDK. Proposition 2 (​​​​​ [ 4 , Proposition 2] ) The features f^{*}(X),g^{*}(Y) as defined by ( 2 )–( 3 ) are minimal sufficient statistics of X and Y . III Main Results Throughout our development in the paper, we will assume that S=s(X),T=t(Y) are sufficient statistics of given X,Y , i.e., X-s(X)-t(Y)-Y . We demonstrate several common examples of information measures \theta(X,Y) that can be evaluated from S and T , i.e., \theta(X,Y)=\theta(S,T) . III-A Mutual Information and f -Information It is straightforward to verify that the mutual information \displaystyle I(X;Y)\triangleq\sum_{x\in\mathcal{X},y\in\mathcal{Y}}P_{X,Y}(x,y)\log\frac{P_{X,Y}(x,y)}{P_{X}(x)P_{Y}(y)} satisfies I(X;Y)=I(S;T) . To see this, note that we have S-X-Y-T since S and T are deterministic functions of X and Y , respectively. Then, the data processing inequality [cf. Lemma 1 ] implies that I(S;T)\leq I(X;Y) . Also, the sufficiency of S and T implies that X-S-T-Y and I(X;Y)\leq I(S;T) . We can extend the above result to the general class of f -information, defined as \displaystyle I_{f}(X;Y)\triangleq\sum_{\begin{subarray}{c}x\in\mathcal{X}\\ y\in\mathcal{Y}\end{subarray}}P_{X}(x)P_{Y}(y)\cdot f\left(\frac{P_{X,Y}(x,y)}{P_{X}(x)P_{Y}(y)}\right), (4) where f is a convex function defined on [0,\infty) with f(1)=0 . In particular the mutual information I(X;Y) corresponds to the specific f(u)=u\cdot\log u . Then we have the following characterization, as a straightforward corollary of Proposition 1 . We omit the proof. Corollary 1 For each f -information defined by ( 4 ), we have I_{f}(X;Y)=I_{f}(S;T) . III-B Common Information We

Read the complete text