To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review β part 2/6
Cleaned-text code points [15958, 31210). Bibliography omitted here; source.md includes it.
The Denoising Autoencoder approach in generative architectures ( Vincent et al., 2008 ; Devlin et al., 2018 ; He et al., 2022 ) using a triplet loss which utilizes a positive sample, which is a vector from the training set that should be reconstructed perfectly, and a contrastive sample consisting of data vectors, one from the training set and the other being a corrupted version of it. In SSL, the combination of JEA models with contrastive learning has proven highly effective. In contrastive learning, the objective is to attract different augmented views of the same image (positive points) while repelling dissimilar augmented views (negative points). Recent self-supervised visual representation learning examples include MoCo ( He et al., 2020 ) and SimCLR ( Chen et al., 2020a ) . The InfoNCE loss is a commonly used objective function in many contrastive learning methods: πΌ x , x + , x β β [ β log β‘ ( e f β ( x ) T β f β ( x + ) β k = 1 K β e f β ( x ) T β f β ( x k ) ) ] \displaystyle\mathbb{E}_{x,x^{+},x^{-}}\left[-\log\left(\frac{e^{f(x)^{T}f(x^{+})}}{\sum{k=1}^{K}{e^{f(x)^{T}f(x^{k})}}}\right)\right] where x + x+ is a sample similar to x x , x k x^{k} are all the samples in the batch, and f f is an encoder.
However, contrastive methods heavily depend on all other samples in the batch and require a large batch size. Additionally, recent studies ( Jing et al., 2021 ) have shown that contrastive learning can lead to dimensional collapse, where the embedding vectors span a lower-dimensional subspace instead of the entire embedding space. Although positive and negative pairs should repel each other to prevent dimensional collapse, augmentation along feature dimensions and implicit regularization cause the embedding vectors to fall into a lower-dimensional subspace, resulting in low-rank solutions.
To address these problems, recent works have introduced JEA models with non-contrastive methods . Unlike contrastive methods, these methods employ regularization to prevent the collapse of the representation and do not explicitly rely on negative samples. For example, several papers use stop-gradients and extra predictors to avoid collapse ( Chen and He, 2021 ; Grill et al., 2020 ) , while Caron et al. (2020) employed an additional clustering step. VICReg ( Bardes et al., 2021 ) is another non-contrastive method that regularizes the covariance matrix of representation. Consider two embedding batches π = [ f β‘ ( π 1 ) , β¦ , f β‘ ( π N ) ] \bm{Z}=\left[f(\bm{x}_{1}),\dots,f(\bm{x}_{N})\right] and π β² = [ f β‘ ( π β² β 1 ) , β¦ , f β‘ ( π β² β N ) ] \bm{Z}^{\prime}=\left[f(\bm{x}^{\prime}1),\dots,f(\bm{x}^{\prime}N)\right] , each of size ( N Γ K ) (N\times K) . Denote by πͺ \bm{C} the ( K Γ K ) (K\times K) covariance matrix obtained from [ π , π β² ] [\bm{Z},\bm{Z}^{\prime}] . The VICReg triplet loss is defined by: β = 1 K β β k = 1 K ( Ξ± β max β‘ ( 0 , Ξ³ β πͺ k , k + Ο΅ ) + Ξ² β β k β² β k ( πͺ k , k β² ) 2 ) + Ξ³ β β π β π β² β F 2 / N . \displaystyle\mathcal{L}\hskip-2.84544pt=\frac{1}{K}\sum_{k=1}^{K}\hskip-2.84544pt\left(\hskip-2.84544pt\alpha\max\left(0,\gamma-\sqrt{\bm{C}_{k,k}+\epsilon}\right)\hskip-2.84544pt+\hskip-2.84544pt\beta\sum_{k^{\prime}\neq k}\hskip-2.84544pt\left(\bm{C}_{k,k^{\prime}}\right)^{2}\hskip-2.84544pt\right)\;\;\;+\gamma\|\bm{Z}-\bm{Z}^{\prime}\|_{F}^{2}/N.
### 2.3 Semi-Supervised Learning
Semi-supervised learning employs both labeled and unlabeled data to enhance the model performance ( Chapelle et al., 2009 ) . Consistency regularization-based approaches ( Laine and Aila, 2016 ; Miyato et al., 2018 ; Sohn et al., 2020 ) ensure that predictions remain stable under perturbations in input data and model parameters. Certain techniques, such as those proposed by Grandvalet and Bengio (2006) and Miyato et al. (2018) , involve training a model by incorporating a regularization term into a supervised cross-entropy loss. In contrast, Xie et al. (2020) utilizes suitably weighted unsupervised regularization terms, while Zhai et al. (2019) adopts a combination of self-supervised pretext loss terms. Moreover, pseudo-labeling can generate synthetic labels based on network uncertainty to further aid model training ( Lee et al., 2013 ) .
### 2.4 Representation Learning
Representation learning is an essential aspect of various computer vision, natural language processing, and machine learning tasks, as it uncovers the underlying structures in data ( Bengio et al., 2013 ) . By extracting relevant information for classification and prediction tasks from the data, we can improve performance and reduce computational complexity ( Goodfellow et al., 2016 ) . However, defining an effective representation remains a challenging task. In probabilistic models, a useful representation often captures the posterior distribution of explanatory factors beneath the observed input ( LeCun et al., 2015 ) . Bengio and LeCun (2007) introduced the idea of learning highly structured yet complex dependencies for AI tasks, which require transforming high-dimensional input structures into low-dimensional output structures or learning low-level representations. As a result, identifying relevant input features becomes challenging, as most input entropy is unrelated to the output ( Shwartz-Ziv and Tishby, 2017 ) . Ben-Shaul et al. (2023) demonstrated that self-supervised learning inherently promotes the clustering of samples based on semantic labels. Intriguingly, this clustering is driven by the objectiveβs regularization term and aligns with semantic classes across multiple hierarchical levels.
#### 2.4.1 Minimal Sufficient Statistic
A possible definition of an effective representation is based on minimal sufficient statistics.
###### Definition 1 .
Given ( X , Y ) βΌ P β‘ ( X , Y ) (X,Y)\sim P(X,Y) , let T := t β‘ ( X ) T:=t(X) , where t t is a deterministic function. We define T T as a sufficient statistic of X X for Y Y if Y β T β X Y-T-X forms a Markov chain.
A sufficient statistic captures all the information about Y Y in X X . Cover (1999) proved this property:
###### Theorem 2 .
Let T T be a probabilistic function of X X . Then, T T is a sufficient statistic for Y Y if and only if I β‘ ( T β‘ ( X ) , Y ) = I β‘ ( X , Y ) I(T(X);Y)=I(X;Y) .
However, the sufficiency definition also encompasses trivial identity statistics that only βcopyβ rather than βextractβ essential information. To prevent statistics from inefficiently utilizing observations, the concept of minimal sufficient statistics was introduced:
###### Definition 3 .
(Minimal sufficient statistic (MSS)) A sufficient statistic T T is minimal if, for any other sufficient statistic S S , there exists a function f f such that T = f β‘ ( S ) T=f(S) almost surely (a.s.).
In essence, MSS are the simplest sufficient statistics, inducing the coarsest sufficient partition on X X . In MSS, the values of X X are grouped into as few partitions as possible without sacrificing information. MSS are statistics with the maximum information about Y Y while retaining the least information about X X as possible ( Koopman, 1936 ) .
#### 2.4.2 The Information Bottleneck
The majority of distributions lack exact minimal sufficient statistics, leading Tishby et al. (1999b) to relax the optimization problem in two ways: (i) allowing the map to be stochastic, defined as an encoder P β‘ ( T | X ) P(T|X) , and (ii) permitting the capture of only a small amount of I β‘ ( X , Y ) I(X;Y) . The information bottleneck (IB) was introduced as a principled method to extract relevant information from observed signals related to a target. This framework finds the optimal trade-off between the accuracy and complexity of a random variable y β π΄ y\in\mathcal{Y} with a joint distribution for a random variable x β π³ x\in\mathcal{X} . The IB has been employed in various fields such as neuroscience ( Buesing and Maass, 2010 ; Palmer et al., 2015 ) , slow feature analysis ( Turner and Sahani, 2007 ) , speech recognition ( Hecht et al., 2009 ) , and deep learning ( Shwartz-Ziv and Tishby, 2017 ; Alemi et al., 2016 ) .
Let X X be an input random variable, Y Y a target variable, and P β‘ ( X , Y ) P(X,Y) their joint distribution. A representation T T is a stochastic function of X X defined by a mapping P β‘ ( T β£ X ) P(T\mid X) . This mapping transforms X βΌ P β‘ ( X ) X\sim P(X) into a representation of T βΌ P ( T ) := β« P T | X ( β
β£ x ) d P X ( x ) T\sim P(T):=\int P_{T\mid X}(\cdot\mid x)dP_{X}(x) . The triple Y β X β T Y-X-T forms a Markov chain in that order with respect to the joint probability measure P X , Y , T = P X , Y β P T | X P_{X,Y,T}=P_{X,Y}P_{T\mid X} and the mutual information terms I β‘ ( X , T ) I(X;T) and I β‘ ( Y , T ) I(Y;T) .
Within the IB framework, our goal is to find a representation P β‘ ( T β£ X ) P(T\mid X) that extracts as much information as possible about Y Y (high performance) while compressing X X maximally (keeping I β‘ ( X , T ) I(X;T) small). This can also be interpreted as extracting only the relevant information that X X contains about Y Y .
The data processing inequality (DPI) implies that I β‘ ( Y , T ) β€ I β‘ ( X , Y ) I(Y;T)\leq I(X;Y) , so the compressed representation T T cannot convey more information than the original signal. Consequently, there is a trade-off between compressed representation and the preservation of relevant information about Y Y . The construction of an efficient representation variable is characterized by its encoder and decoder distributions, P β‘ ( T β£ X ) P(T\mid X) and P β‘ ( Y β£ T ) P(Y\mid T) , respectively. The efficient representation of X X involves minimizing the complexity of the representation I β‘ ( T , X ) I\left(T;X\right) while maximizing I β‘ ( T , Y ) I\left(T;Y\right) . Formally, the IB optimization involves minimizing the following objective function: β = min P β‘ ( t β£ x ) ; p β‘ ( y β£ t ) β‘ I β‘ ( X , T ) β Ξ² β I β ( Y , T ) , \displaystyle\mathcal{L}=\min_{P(t\mid x);p(y\mid t)}I(X;T)-\beta I(Y;T)\penalty\ , (1) where Ξ² \beta is the trade-off parameter controlling the complexity of T T and the amount of relevant information it preserves. Intuitively, we pass the information that X X contains about Y Y through a βbottleneckβ via the representation T T . It has been shown that: I ( T : Y ) = I ( X : Y ) β πΌ x βΌ P β‘ ( X ) , t βΌ P β‘ ( T | x ) [ D [ P ( Y | x ) | | P ( Y | t ) ] ] \displaystyle I(T:Y)=I(X:Y)-\mathbb{E}_{x\sim P(X),t\sim P(T|x)}\left[D\left[P(Y|x)||P(Y|t)\right]\right] (2)
### 2.5 Representation Learning and the Information Bottleneck
Information theory traditionally assumes that underlying probabilities are known and do not require learning. For instance, the optimality of the initial IB work ( Tishby et al., 1999b ) relied on the assumption that the joint distribution of input and labels is known. However, a significant challenge in machine learning algorithms is inferring an accurate predictor for the unknown target variable from observed realizations. This discrepancy raises questions about the practical optimality of the IB and its relevance in modern learning algorithms. The following section delves into the relationship between the IB framework and learning, inference, and generalization.
Let X β π³ X\in\mathcal{X} and a target variable Y β π΄ Y\in\mathcal{Y} be random variables with an unknown joint distribution P β‘ ( X , Y ) P(X,Y) . For a given class of predictors f : π³ β π΄ ^ f:\mathcal{X}\to\mathcal{\hat{Y}} and a loss function β : π΄ β π΄ ^ \ell:\mathcal{Y}\to\mathcal{\hat{Y}} measuring discrepancies between true values and model predictions, our objective is to find the predictor f f that minimizes the expected population risk. β P β‘ ( X , Y ) β ( f , β ) = πΌ P β‘ ( X , Y ) β [ β β‘ ( Y , f β‘ ( X ) ) ] \displaystyle\mathcal{L}_{P(X,Y)}\left(f,\ell\right)=\mathbb{E}_{P(X,Y)}\left[\ell(Y,f(X))\right]
Several issues arise with the population risk. Firstly, it remains unclear which loss function is optimal. A popular choice is the logarithmic loss (or errorβs entropy), which has been numerically demonstrated to yield better results ( Erdogmus, 2002 ) . This loss has been employed in various algorithms, including the InfoMax principle ( Linsker, 1988 ) , tree-based algorithms ( Quinlan, 2014 ) , deep neural networks ( Zhang and Sabuncu, 2018 ) , and Bayesian modeling ( Wenzel et al., 2020 ) . Painsky and Wornell (2018) provided a rigorous justification for using the logarithmic loss and showed that it is an upper bound to any choice of the loss function that is smooth, proper, and convex for binary classification problems.
In most cases, the joint distribution P β‘ ( X , Y ) P(X,Y) is unknown, and we have access to only n n samples from it, denoted by π n := ( x i , y i ) | i = 1 , β¦ , n \mathcal{D}_{n}:={(x_{i},y_{i})\mid i=1,\ldots,n} . Consequently, the population risk cannot be computed directly. Instead, we typically choose the predictor that minimizes the empirical population risk on a training dataset:
β ^ P β‘ ( X , Y ) β ( f , β , π n ) = 1 n β β i = 1 n [ β β‘ ( y i , f β‘ ( x i ) ) ] \displaystyle\mathcal{\hat{L}}_{P(X,Y)}\left(f,\ell,\mathcal{D}_{n}\right)=\frac{1}{n}\sum_{i=1}^{n}\left[\ell(y_{i},f(x_{i}))\right]
The generalization gap, defined as the difference between empirical and population risks, is given by: G β e β n P β‘ ( X , Y ) β ( f , β , π n ) := β P β‘ ( X , Y ) β ( f , β ) β β ^ P β‘ ( X , Y ) β ( f , β , π n ) \displaystyle Gen_{P(X,Y)}\left(f,\ell,\mathcal{D}_{n}\right):=\mathcal{L}_{P(X,Y)}\left(f,\ell\right)-\mathcal{\hat{L}}_{P(X,Y)}\left(f,\ell,\mathcal{D}_{n}\right)
Interestingly, the relationship between the true loss and the empirical loss can be bounded using the information bottleneck term. Shamir et al. (2010) developed several finite sample bounds for the generalization gap. According to their study, the IB framework exhibited good generalizability even with small sample sizes. In particular, they developed non-uniform bounds adaptive to the modelβs complexity. They demonstrated that for the discrete case, the error in estimating mutual information from finite samples is bounded by O β‘ ( | X | β log β‘ n n ) O\left(\frac{|X|\log n}{\sqrt{n}}\right) , where | X | |X| is the cardinality of X X (the number of possible values that the random variable X X can take). The results support the intuition that simpler models generalize better, and we would like to compress our model. Therefore, optimizing eq. 1 presents a trade-off between two opposing forces. On the one hand, we want to increase our prediction accuracy in our training data (high Ξ² \beta ).
On the other hand, we would like to decrease Ξ² \beta to narrow the generalization gap. Vera et al. (2018) extended their work and showed that the generalization gap is bounded by the square root of mutual information between training input and model representation times log β‘ n n \frac{\log n}{n} . Furthermore, Russo and Zou (2019) and Xu and Raginsky (2017) demonstrated that the square root of the mutual information between the training input and the parameters inferred from the training algorithm provides a concise bound on the generalization gap. However, these bounds critically depend on the Markov operator that maps the training set to the network parameters, whose characterization is not trivial.