Year: 2018

Abstract:
We formulate an information-based optimization problem for supervised classification. For invertible neural networks, the control of these information terms is passed down to the latent features and parameter matrix in the last fully connected layer, given that mutual information is invariant under invertible map. We propose an objective function and prove that it solves the optimization problem. Our framework allows us to learn latent features in a more interpretable form while improving the classification performance. We perform extensive quantitative and qualitative experiments in comparison with the existing state-of-the-art classification models.

heading: 1 INTRODUCTION
text: Quantities of information are nonlinear measures capable of describing complex relationship between unstructured data and they form the basis of the probabilistic algorithms in the literature of machine learning. Information theoretic methods are also reported to be effective on improving deep generative models (Chen et al. (2016); Kim & Mnih (2018)) and deep learning models for classification (Grandvalet & Bengio (2004); Pereyra et al. (2017)). Information Bottleneck (IB) problem (Tishby et al., 1999) is formulated as:
minimize I(X;T )− λI(Y ;T ) , (1)
where the solution random variable T is interpreted as a minimal sufficient representation of signal X for label Y and the mutual information is defined as
I(X;Y ) = ∫ X ∫ Y p(x, y) log ( p(x, y) p(x)p(y) ) dydx . (2)
The term I(X;T ) has its origins in Lossy Compression and Rate-Distortion Theory (Cover & Thomas, 2006), conveying an simple idea of ”keep only what is relevant”.
However, Saxe et al. (2018) argued that the mutual information I(X;T ) between signal X and feature T in intermediate layer is infinite, as the transformation from X to continuous random variable T is deterministic. In addition they showed experimentally that layers equipped with ReLU actually do not compress too much information, which is supported by many recent work on the invertibility of the neural network (Dosovitskiy & Brox (2015); Jacobsen et al. (2018)). This motivates us to consider a different problem with similar principle idea: we would like to establish a theoretically valid objective that allows the neural network to extract only the relevant information for classification from the data.
We focus on the discrete prediction random variable Ŷ inferred by the probabilistic model P(Ŷ |X) and introduce the following information optimization problem for supervised classification:
maximize I(Y ; Ŷ ) subject to I(X; Ŷ )− I(Y ; Ŷ ) < τ , for some τ > 0 . (3)
The intuition behind this objective lies in twofold:
Information perspective: A good classification model should be robust against irrelevant features of X , and prevent over-fitting in the learning process. In optimization problem (3) we maximize the relevant information I(Y ; Ŷ ), while constraining the irrelevant information I(X; Ŷ ) − I(Y ; Ŷ )
that X has about Ŷ . Although I(X; Ŷ ) − I(Y ; Ŷ ) converges to zero as I(Y ; Ŷ ) approaching its maximum (see Figure 1L), in practice it’s never attained due to the limited capacity of the models or over-fitting. Our proposed constrain addresses the problem of over-fitting: if two models achieve the similar classification accuracy, this constraint prefers the one that does not overfit to spurious factors of variation in X (e.g., pixel-level artifact/noise in the image that accidentally correlates to the labels in the training data).
Prediction confidence perspective: A good classification model should not be certain about its decision which is in fact wrong. However, modern neural networks are too confident in their predictions (Guo et al., 2017; Szegedy et al., 2015; Pereyra et al., 2017). To be more precise, high capacity neural networks mostly assign labels of data with prediction confidence near 0 or 1. In particular, they assign 0 probability to some correct labels and therefore do not have enough flexibility to correct themselves from making the wrong prediction. We propose to compress the irrelevant information I(X; Ŷ ) − I(Y ; Ŷ ), where minimizing I(X; Ŷ ) decreases the confidence on all predictions but maximizing I(Y ; Ŷ ) increases the confidence on the correct predictions. Therefore the overall effect reduces the certainty on the false prediction of Ŷ (see Figure 1L).
To solve this optimization problem, we first present some insights on the dynamics of deep neural network, which can be decomposed into two stages: (i) Transformation stage: samples {Xk}k=1:n of the high dimensional unstructured signal X are transformed under the deep invertible (information preserving) feature map F to become (almost) linearly separable; (ii) Classification stage: the weight matrixw in the last fully connected layer together with the Softmax function, takes structured features {F (Xk)}k=1:n as input and gives predictions.
Invertibility of F allows neural networks to pass the control of I(X; Ŷ ) = I(F (X); Ŷ ) towards F (X) and w in the last layer, where F (X) can be interpreted as transformed signal that preserves information about the original signal X and the inference model becomes conceptually linear with classifier w (see Figure 1R). In Section 2 we derive objective function (7) and prove that it solves the optimization problem (3). We show the classification performance is improved in Section 4.1 and the features F (X) are sculpted into a form with more interpretability entry-wise in Section 4.2.
The invertibility property has been empirically demonstrated for complex non-linear deep neural networks that are widely used in practice. We will discuss the literature in Section 3. In addition, we prove in Proposition C.1 that a lower bound of classification error is minimized if neural network is invertible.
Our contribution: Our contribution lies in the following: (i) we formulated a novel information optimization problem for supervised classification; (ii) we propose a simple objective function that improves supervised deep learning with better performance and interpretability; (iii) we formally
justify the use of `1, `2 regularization from an information perspective. Different from the naive regularization on w, our regularization on wTF (X) is novel and effective.

heading: 2 MAIN RESULTS
text: Consider a classification problem where the training data D = {(xk, yk)}k=1:n are sampled from random variable pair (X,Y ) with unknown joint distribution. Each xk is fed into a deep probabilistic model, which outputs probability densities and predicts ŷk, a realization of the prediction random variable Ŷ . Let C denote the label class and X denote the signal space, then the mutual information between random variables, e.g., continuous X and discrete Ŷ , is defined as I(X; Ŷ ) = ∑ ŷ∈C ∫ X p(x, ŷ) log ( p(x,ŷ) p(x)p(ŷ) ) dx, and the entropy of Y is defined as H(Y ) =
− ∑ y∈C p(y) log p(y).
We first call out our assumptions used throughout our analysis. (I): we assume the marginal densities of Y, Ŷ are uniform over C; (II): there exists a unique true label for every sample of X . Mutual information is bounded and its gradient with respect to logits is approximately zero over a large domain. In particular if the logits are initially small for true labels, gradient updates cannot effectively correct them. Therefore it’s not practical to train mutual information terms directly. In this section we introduce alternative terms and prove that they are feasible for our purpose. We show in Proposition 2.2 that I(Y ; Ŷ ) is maximized if the classical cross entropy objective is minimized. On the other hand, we show in Proposition 2.1 that for invertible F , I(X; Ŷ ) = I(F (X); Ŷ ) is minimized if ‖wTF (X)‖ is minimized. We derive our objective function (7) in Section 2.2. Our experimental result in Section 4.1 verifies that the proposed objective function does compress the irrelevant information I(X; Ŷ )− I(Y ; Ŷ ).

heading: 2.1 SOLVING OPTIMIZATION PROBLEM WITH FEASIBLE TERMS
text: Without loss of generality, we consider the binary classification problem, i.e. the label class C = {±1}. To tract the population quantities I(F (X);Y ) and I(Y ; Ŷ ), we decompose each of them into an empirical part and a probabilistic bound, which is negligible if sample size n is large. In Proposition 2.1, we show that in order to compress I(F (X);Y ), we need to compress the norm of classifier w and feature F (X). In particular, smaller |wTF (X)| represents lower confidence of the model on its predictions Ŷ , indicating a smaller amount of mutual information I(F (X); Ŷ ). The proof is provided in Appendix A. Proposition 2.1. I(X; Ŷ ) = I(F (X);Y ) is well estimated by its empirical version∑n k=1 ∑ ŷ∈C p(ŷ|xk) log(2p(ŷ|xk))/n with high probability, which shares the same unique (global)
minimum with ∑n k=1 |wTF (xk)| at wTF (xk) = 0, for all k ∈ {1, ..., n}.
Denote the sigmoid function with σ(a) = 1/(1 + e−a). Proposition 2.2 establishes the relationship between maximization over mutual information I(Y ; Ŷ ) and minimization over cross entropy − ∑n k=1 log σ(ykw
TF (xk)); higher confidence of the model on its correct predictions over the samples indicates a larger value of I(Y ; Ŷ ). The proof is provided in Appendix B.
Proposition 2.2. I(Y ; Ŷ ) is well estimated by its empirical version ∑ yŷ π̂yŷ log ( π̂yŷ
π̂y+π̂+ŷ
) with
high probability, which shares the same unique (global) maximum with ∑n k=1 log σ(ykw
TF (xk)) given that ykwTF (xk) > 12 , for all k ∈ {1, ..., n}. Here π̂yŷ = 1 2ny ∑ny i=1 σ(ŷw
TF (xi)) is an unbiased estimate of p(y, ŷ) and π̂y+ = ∑ ŷ∈C π̂yŷ, π̂+ŷ = ∑ y∈C π̂yŷ .

heading: 2.2 DERIVATION OF OBJECTIVE FUNCTION
text: In Lagrangian form of optimization problem (3), the constant τ can be dropped and the objective becomes
maximize (1 + λ)I(Y ; Ŷ )− λI(F (X); Ŷ )⇐⇒ maximize I(Y ; Ŷ )− λ 1 + λ I(F (X); Ŷ ) . (4)
Consider a single signal xk and its true label yk, we propose the following objective function for binary supervised classification problem:
Lk = αR ( |wTF (xk)| ) − log σ(ykwTF (xk)) , (5)
where R is some regularizer. According to results in Section 2.1, minimizing (5) allows us to maximize I(Y ; Ŷ ) while constraining I(X; Ŷ ). We typically choose the hyper-parameter α > 0 to be a reasonably small number. The intuition comes from the observation that λ/(1 + λ) is upper bounded by one. If we compress I(X; Ŷ ) harshly, then neural networks may choose to minimize I(F (X); Ŷ ) at a cost of minimizing I(Y ; Ŷ ).
Recall from the information theoretic perspective of our proposed optimization problem, our regularizer should prefer a model that does not overfit among all the ones with high training accuracy. In this case neural networks assign only large logits wTykF (xk) to true label yk for each signal xk, and generalization of (5) to multi-class case for I(F (X); Ŷ ) can be simplified to constraining wTykF (xk)− w T j F (xk), where wj is the jth column of w, assigning feature F (xk) a probability to label j. We propose to simply constrain wTykF (xk) and does not encourage increasing w T j F (xk):
Lk = αR ( |wTykF (xk)| ) − log
( ew T yk F (xk)
ew T yk F (xk) + ∑ j 6=yk e wTj F (xk)
) . (6)
In our experiment, we take the Elastic Net approach by Zou & Hastie (2005) using a combination of `2 and `1 regularizers: we use Holder’s inequality to bound |wTykF (xk)| with both supF (X) · ‖wyk‖1 and ‖wyk‖2 · ‖F (xk)‖2. In practice we assume supF (X) to be a constant and is absorbed into the hyper-parameter. Our proposed objective function is of the form:
L = α1||w||1 + 1
n n∑ k=1 { α2‖wyk‖2 · ‖F (xk)‖2 − log ( ew T yk F (xk) ew T yk F (xk) + ∑ j 6=yk e wTj F (xk) )} . (7)
Notice that classical training methods maximize cross entropy and therefore I(Y ; Ŷ ), but do not compress I(X; Ŷ ) explicitly. In Equation (7), we explicitly encourage the compression of irrelevant information I(X; Ŷ )− I(Y ; Ŷ ). As we demonstrate in Section 4.3, the proposed objective function does encourage a smaller amount of I(X; Ŷ )− I(Y ; Ŷ ) throughout the training process.

heading: 3 RELATED WORK
text: Recent experimental work reported that neural networks with invertible structure have better performance. Dosovitskiy & Brox (2015) showed that images can be resconstructed from the latent features in AlexNet through an inverting process; this reconstruction is further improved by Zhang et al. (2016), where they built an encoder-decoder structure to encourage invertibility and showed reconstructive objective is beneficial to the performance of the neural network (e.g., VGGNet). Shang et al. (2016) proposed an invertible activation scheme named CReLU to preserve information; Gilbert et al. (2017) analyzed theoretically the invertibility of CNN; Jacobsen et al. (2018) built a theoretic invertible structure whose performance is comparable to ResNet He et al. (2015). Invertibility seems to be an intriguing property or design principle that often emerges in the recent state-of-the-art deep architectures.
Information theoretic methods are reported to be effective attacking machine learning problems. In deep learning, IB was first introduced in Tishby & Zaslavsky (2015) and the follow-up experimental work Shwartz-Ziv & Tishby (2017). They argued that DNN structure forms a markov chain and information is compressed layer by layer. The theoretical breakthrough by Achille & Soatto (2017) established a connection between the IB objective and the generalization in deep learning, carrying along with the notion of sufficiency and invariance of representations. Strouse & Schwab (2016),Slonim & Tishby (1999) used IB objectives for clustering problems. Alemi et al. (2017), Gao et al. (2018),Kim & Mnih (2018) established information theoretic approaches based on VAE to encourage disentangled and informative latent representations; Grandvalet & Bengio (2004) introduced entropy regularizer in semi-supervised learning; Krause et al. (2010) took Regularized
Information Maximization(RIM) approach for classification problems; Chen et al. (2016) proposed to add information ingredients to the objective of GANs, encourage to learn disentangled representations.
Our framework decomposes deep neural network into a composition of nonlinear transformation map and a linear probablistic model; this idea was originated in Bell & Sejnowski (1995) where they considered the blind separation problem and decompose the prediction Ŷ to be the sum of an invertible deterministic part and a stochastic part. Amjad & Geiger (2018) and Kolchinsky et al. (2017) also studied the IB problem in a stochastic setting. Our idea of explicit regularization on w and F (X) is related to the margin based and stability based interpretations of generalization in deep learning respectively, studied by Arora et al. (2018), Bartlett & Mendelson (2003), Neyshabur et al. (2017), Sun et al. (2015).

heading: 4 EXPERIMENTS
text: In our experiments we build the feature map F with ResNet or InvNet (introduced in Section 4.2). In Appendix D we prove that ResNet by He et al. (2015) is invertible under mild assumptions. We prefix the name of the model trained under our objective with ”Reg”, i.e. RegResNet/RegInvNet.

heading: 4.1 PERFORMANCE
text: We report the accuracy of ResNet on test data of CIFAR100 in Table 1.1
We compare the performance between our proposed regularization on wTykF (xk) and the naive regularization on w. In both form of regularization we take α1 = 0 and test over different choices of α2. We pick smaller α2 for naive regularization because it’s applied to the full matrix. We observe the performance of ResNet-32 under naive regularization drops monotonically as α2 increases.
Under a suitable choice of hyperparameters, RegResNet outperforms ResNet by a noticeable margin. It implies that our proposed constrain on the irrelevant information I(X; Ŷ )− I(Y ; Ŷ ) is beneficial to the classification performance. However, if the hyperparameters are too large, the performance drops, i.e. α2 = 0.05 for ResNet-32 and α2 = 0.15 for ResNet-Wide; this matches the discussion in Section 2.2 that the model may try to reduce the relevant information I(Y ; Ŷ ). Our approach addresses the problem of over-fitting; ResNet-Wide is improved by a larger margin compared to
1We use the open source code implemented by Xin Pan at https://github.com/tensorflow/ models/tree/master/research/resnet and build our objective function based upon it. Our results for the baseline models match the reported ones on the website.
ResNet-32 because ResNet-Wide has higher capacity and is therefore over-fits more to the training data.

heading: 4.2 ANALYSIS ON FEATURES
text: We introduce another invertible structured neural network on MNIST dataset and analyze the feature F (X) learned in the last layer qualitatively. The feature map F is built to be LeNet-300-100 and the decoder D has the opposite structure. At each step during the training process, we update the autoencoder F +D and the InvNet F +w alternatively; our regularization is applied to w as usual. In this section we report our result with α1 = α2 = 0.002.

heading: 4.2.1 LEARNING TO OVERLOOK IRRELEVANT INFORMATION
text: We feed 1k testing samples of digit 9 into the neural network to get 1k samples of features F (X). Recall that the features F (X) are vectors of dimension 100 and w is a matrix of size 100× 10. We calculate the mean and standard deviation of each entry of the features from these 1k samples. From Figure 2 we see that under our regularization, the entry-wise products w10Ti F (X)i becomes sparse as only a few entries have large values for both feature and weight. This implies that the information needed to compute the logits for classification is encoded into only a few entries of the feature, which we regard as relevant entries. Our regularization forces small w10 on irrelevant entries, so the logits it outputs are not sensitive to variations in these entries; on the other hand, we do encourage largew10 on the relevant entries. This matches our motivation that a neural network should be robust against irrelevant information I(F (X); Ŷ )− I(Y ; Ŷ ) and focus on the relevant information I(Y ; Ŷ ).

heading: 4.2.2 LEARNING TO EXTRACT RELEVANT INFORMATION
text: It had been argued by Szegedy et al. (2013) that it is the space but not individual units in high level features that encodes interpretable information. Under our regularization, a meaningful basis of the informative space is found; in particular, the features of 9 are encoded into 10 entries (see Figure 2). On the other hand, features that have high values in these entries are expected to be the features of digit 9.
To validate this conjecture, for each digit, we find the entry of its feature mean with the highest value. We use the micro and macro average ROC metric on these feature entries and compare the results from InvNet and RegInvNet in Figure 3. The curve with larger area underneath indicates higher representative power of individual entries learned in the features. We conclude that under our regularization, relevant information for classification is encoded into only a few key entries of the features, and these entries are highly indicative and interpretable.

heading: 4.3 RELATIONSHIP TO LINEAR REGRESSION
text: We trained ResNet-32 on CIFAR10, the feature F (X) is a vector of size 64, the classifier w is a matrix of size 64 × 10. Note that the product wTF (X) is a vector of size 10 representing the probability assigned by the model for each class.
Under our framework, deep learning can be conceptually simplified to regularized linear regression if we regard F (X) as input data. However, F (X) depends on the model parameters in the previous layers so it’s not fixed like real data. Moreover we observe in our experiments that naive regularization on w alone will upscale the norm of F (X), which neutralizes the effect of regularization. In Figure 4 we show that as under our regularization, the `2-norm of w is suppressed while the `2- norms of feature F (X) remain similar. In addition, several rows of w are trained to be zero, which implies that many entries of the feature F (X) are regarded by the network as irrelevant information for classification, since any variance in the entries of F (X) where the corresponding rows of w are zero has no influence on the probability assigned to each label class by the model.

heading: 5 THE ROLE OF INVERTIBILITY
text: Invertibility allows us to treat F (X) as transformed data that preserves all the information from X , and therefore work on the information regularization problem under a linear scheme.
In Appendix D we prove that ResNet is fairly invertible due to the intrinsic invertibility of the operator I+L given ‖L‖ < 1. In this section we build a PlainNet by using only L as the operator for each building block, so the theoretical guarantee for invertibility is not present for PlainNet. In Table 2,
we see that PlainNet-32 can still benefit from our regularization, however, it’s performance is less stable compared to ResNet-32 if the hyper-parameters are too large. The reason is for PlainNet, the feature in the last layer F (X) does not preserve information about X very well, so it has a higher demand on the capacity of the classifer w and is therefore more sensitive to our regularization.

heading: 6 CONCLUSION
text: We give an interpretation of the deep learning dynamics by decomposing it into an signal transformation stage and feature classification stage, where we emphasis importance of the classifier w in the last fully connected layer given that the feature map F is invertible. Then we take the advantage of the fact that mutual information quantities are invariance under invertible mapping to attack our proposed information optimization problem for supervised classification in deep learning. Our theory justifies the use of direct regularization terms on w,F (X) for neural networks with invertibility property. Our regularization improves the performance of neural networks by a noticeable margin and is capable of encouraging the interpretability of the entries of features learned in the last layer.

heading: A PROOF OF PROPOSITION 2.1
text: Proposition 2.1 establishes a connection between I(X, Ŷ ) and the absolute value of the logits |wTF (X)| for the binary case. Intuitively, decreasing the confidence of the model on its predictions will decrease the mutual information I(X; Ŷ ).
Proposition 2.1. I(X; Ŷ ) = I(F (X);Y ) is well estimated by its empirical version (Montecarlo approximation) with high probability, which shares the same unique (global) minimum with∑n k=1 |wTF (xk)| at wTF (xk) = 0, for all k ∈ {1, ..., n}.
The mutual information I(X; Ŷ ) is given as
I(X; Ŷ ) = ∫ X ∑ ŷ∈C p(x, ŷ) log ( p(x, ŷ) p(x)p(ŷ) ) dx . (8)
Apply the assumption (II), the marginal distribution of Ŷ is uniformly distributed: p(x, ŷ)
p(x)p(ŷ) = p(ŷ|x) p(ŷ) = 2p(ŷ|x) . (9)
Substituting (9) into (8) yields
I(X; Ŷ ) = ∫ X p(x) ∑ ŷ∈C p(ŷ|x) log ( p(x, ŷ) p(x)p(ŷ) ) dx
= ∫ X p(x) ∑ ŷ∈C p(ŷ|x) log(2p(ŷ|x))dx . (10)
According to the Hoeffding’s inequality for bounded random variables [Proposition 2.2.6, Vershynin (2018)], let M,m denote upper and lower bounds of the integrand of (10) correspondingly, we have
P  ∣∣∣∣∣∣ n∑ k=1 ∑ ŷ∈C p(ŷ|xk) log(2p(ŷ|xk))− I(X; Ŷ ) ∣∣∣∣∣∣ ≥ t  ≤ 2e− 2t2n(M−m)2 . (11)
Equivalently, with probability at least 1− δ,∣∣∣∣∣ ∑n k=1 ∑ ŷ∈C p(ŷ|xk) log(2p(ŷ|xk)) n − I(X; Ŷ ) ∣∣∣∣∣ < √ − log( δ2 )(M −m)2 2n . (12) Here ∑n k=1 ∑ ŷ∈C p(ŷ|xk) log(2p(ŷ|xk))/n is a Monte carlo estimation of RHS of I(X; Ŷ ).
Recall that, for the binary case p(ŷ|x) = p(ŷ|F (x)) can expressed as p(ŷ = 1|F (x)) = σ(wTF (x))
p(ŷ = −1|F (x)) = 1− σ(wTF (x)) . (13)
Then we have∑ ŷ∈C p(ŷ|F (xk)) log(2p(ŷ|F (xk))) = σ(wTF (x)) log(2σ(wTF (x)))
+ (1− σ(wTF (x))) log(2− 2σ(wTF (x)))) , (14) which is bounded by [0, log(2)].
Take M = log(2),m = 0, we have
I(X; Ŷ ) =
∑n k=1 ∑ ŷ∈C p(ŷ|xk) log(2p(ŷ|xk))
n + O √− log( δ2 ) log(2)2 2n  . (15) hold with probability at least 1− δ. The conclusion follows from the fact that ∑n k=1 ∑ ŷ∈C p(ŷ|xk) log(2p(ŷ|xk))/n has a unique global minimum at wTF (xk) = 0 for each xk.

heading: B PROOF OF PROPOSITION 2.2
text: Consider the training samples {(xk, yk)}k=1:n, each xk is fed into a deep probabilistic model which outputs probability densities and predicts ŷk, a realization of the prediction Ŷ . Let C = {±1} be the binary class and ny be the counts of observed occurrences of k satisfying yk = y ∈ C, then n = ∑ y∈C ny = ∑ y ny , where we omit the range over C for convenience. We denote the true joint probability with πyŷ = p(y, ŷ), the marginal probabilities with πy+ =∑ ŷ πyŷ and π+ŷ = ∑ y πyŷ . The mutual information I(Y ; Ŷ ) can be expressed as
I(Y ; Ŷ ) = I(π) = ∑ yŷ πyŷ log ( πyŷ πy+π+ŷ ) . (16)
Our empirical mutual information I(π̂) is defined as I(π̂) = ∑ yŷ π̂yŷ log ( π̂yŷ π̂y+π̂+ŷ ) , (17)
where π̂yŷ = 12ny ∑ny i=1 σ(ŷw TF (xi)).
Proposition 2.2 establishes a connection between I(Y ; Ŷ ) and the cross-entropy objective for the binary case. Intuitively, increasing the confidence of the model on its correct predictions will establish a more deterministic relationship between Y and Ŷ and thus increase the mutual information I(Y ; Ŷ ).
Proposition 2.2. I(Y ; Ŷ ) is well estimated by I(π̂) with high probability, which shares the same unique (global) maximum with ∑n k=1 log σ(ykw
TF (xk)) at ykwTF (xk) → ∞ given that ykw TF (xk) > 1 2 , for all k ∈ {1, ..., n}.
Proposition 2.2 follows from Proposition B.1 and Proposition B.2, where Proposition B.1 shows that I(Y ; Ŷ ) is well approximated by I(π̂) with high probability and Proposition B.2 shows the remaining claims in Proposition 2.2.
As shown in Lemma B.1, π̂yŷ = 12ny ∑ny i=1 σ(ŷw
TF (xi)) is an unbiased estimate of πyŷ . Here σ to represent the sigmoid function defined by σ(x) = ex/ (ex + 1). By leveraging the concentration property of bounded variables, i.e., σ(ŷwTF (xi)), the estimation error can be bounded with high probability (Lemma B.2). Lemma B.1. The empirical joint probability, defined as
π̂yŷ = 1
2ny ny∑ i=1 σ(ŷwTF (xi)) , (18)
is an unbiased estimate of the true joint distribution πyŷ . Lemma B.2. With probability at least 1− δ, we have
|∆yŷ| := |π̂yŷ − πyŷ| ≤ 1
2
√ log( 2δ ) min{ 1 4 supx(w
TF (x))2, 1} 2ny . (19)
Proposition B.1. With probability at least 1− δ,
I(Y ; Ŷ ) = I(π) = I(π̂)−O √ log( 8δ ) min{ 14 supx(wTF (x))2, 1} n  . (20) Proof. To estimate the empirical mutual information given fixed samples, we use the approach by Hutter & Zaffalon (2005). In particular, taylor expansion gives
I(π̂) = I(π) + ∑ yŷ log ( πyŷ πy+π+ŷ ) ∆yŷ + O(∆ 2) , (21)
where ∆yŷ = π̂yŷ−πyŷ . Hence, Eq (21) together with Lemma B.2 yield, with probability exceeding 1− |C|2δ,
I(π) = I(π̂)−O √ log( 2δ ) min{ 14 supx(wTF (x))2, 1} n  . (22) Notice that, in the binary case the cardinality |C| = 2.
Next we prove the intermediate results, Lemmas B.1 and B.2.
Proof of Lemma B.1. Direct derivation on the true joint distribution πyŷ gives
πyŷ = p(y, ŷ) = ∫ X p(y, ŷ, x)dx = ∫ X p(y|ŷ, x)p(ŷ|x)p(x)dx
= ∫ X p(y|x)p(ŷ|x)p(x)dx
= ∫ X p(x|y)σ(ŷwTF (x))p(y)dx . (23)
Given assumption (I) which states that the marginal density of Y is uniform over C, for every true label y ∈ C we have p(y) = 12 . We can therefore rewrite (23) as
πyŷ = 1
2 ∫ X σ(ŷwTF (x))p(x|y)dx . (24)
According to assumption (II), p(x|y) is a probability density over space of signal x with true label y.
The Monte Carlo estimation of (24) gives the empirical joint probability which is unbiased:
π̂yŷ = 1
2ny ny∑ i=1 σ(ŷwTF (xi)) . (25)
Proof of Lemma B.2. Again, by leveraging the Hoeffding’s inequality for bounded random variables [Proposition 2.2.6 of Vershynin (2018)], we have
P  ∣∣∣∣∣∣ ny∑ ky=1 ( σ(ŷwTF (xky ))− EXy [ σ(ŷwTF (Xy)) ])∣∣∣∣∣∣ ≥ t  ≤ 2e− 2t2ny(M−m)2 , (26)
where Xy is the data random variable whose true label is y.
Equivalently, with probability at least 1− δ,∣∣∣∣∣ ∑ny ky=1 σ(ŷwTF (xky )) ny − EXy [ σ(ŷwTF (Xy)) ]∣∣∣∣∣ < √ log( 2δ )(M −m)2 2ny , (27)
where M,m are upper and lower bounds of random variable σ(ŷwTF (Xy)), respectively.
Substitute (24) and (25) into (27), with probability at least 1− δ,
|π̂yŷ − πyŷ| ≤ 1
2
√ log( 2δ )(M −m)2
2ny . (28)
To estimate the upper and lower bounds M,m for σ(ŷwTF (X)), we use the Taylor’s theorem:
sup x σ(ŷwTF (x)) = σ(0) + sup x σ′(c)(ŷwTF (x))
≤ 1 2 + 1 4 sup x |wTF (x)| (29)
and
inf x σ(ŷwTF (x)) = σ(0) + inf x σ′(c)(ŷwTF (x))
≥ 1 2 − 1 4 sup x |wTF (x)| , (30)
given that the derivative of sigmoid function is bounded by 14 .
It follows that
|M −m| = sup x σ(ŷwTF (x))− inf x σ(ŷwTF (x))
≤ 1 2 sup x |wTF (x)| . (31)
Also notice that M,m are the bounds for sigmoid function, so their difference is at most 1.
From derivations above, we can rewrite (28) as
|π̂yŷ − πyŷ| ≤ 1
2
√ log( 2δ ) min{ 1 4 supx(w
TF (x))2, 1} 2ny , (32)
and the lemma follows.
Proposition B.2. The empirical mutual information I(π̂) shares the same unique (global) maximum with ∑n k=1 log σ(ykw
TF (xk)) as ykwTF (xk) → ∞ given that ykwTF (xk) > 12 , for all k ∈ {1, ..., n}.
Proof. The empirical information I(π̂) is defined by
I(π̂) = ∑ ij π̂yŷ log ( π̂yŷ π̂y+π̂+ŷ ) , (33)
where the empirical joint probability is given by
π̂yŷ = 1
2ny ny∑ i=1 σ(ŷwTF (xi)) . (34)
It then follows that for any y ∈ C,
π̂y+ = 1
2ny ny∑ i=1 σ(wTF (Xi)) + 1 2ny ny∑ i=1 σ(−wTF (Xi))
= 1
2ny ny∑ i=1 (σ(wTF (Xi)) + σ(−wTF (Xi)))
= 1
2ny ny∑ i=1 1 = 1 2 . (35)
In binary case it means that
π̂1(−1) = 1
2 − π̂11 , π̂(−1)1 =
1 2 − π̂(−1)(−1) (36)
and the empirical mutual information can decomposed as
I(π̂) = π̂11 log
( π̂11
π̂11 + 1 2 − π̂(−1)(−1)
) + ( 1
2 − π̂11
) log ( 1 2 − π̂11
1 2 − π̂11 + π̂(−1)(−1)
) +
( 1
2 − π̂(−1)(−1)
) log ( 1 2 − π̂(−1)(−1)
π̂11 + 1 2 − π̂(−1)(−1)
) + π̂(−1)(−1) log ( π̂(−1)(−1)
1 2 − π̂11 + π̂(−1)(−1)
) + log(2) .
(37)
We differentiate (37) with respect to π̂11 and π̂(−1)(−1), and calculate the critical points over the domain [0, 12 ] for both variables, which gives
π̂11 = π̂(−1)(−1) = 1
4 . (38)
Observe that (38) is a global minimum over [0, 12 ] × [0, 1 2 ]. Since this is the unique critical point where the derivative vanishes, the global maximums can only be obtained on the boundaries. In particular, if we restrict (π̂11, π̂(−1)(−1)) on [ 14 , 1 2 ]× [ 1 4 , 1 2 ], (37) is a strictly increasing function over π̂11, π̂(−1)(−1) and the unique global maximum is obtained at
π̂11 = π̂(−1)(−1) = 1
2 . (39)
The proposition follows from the definition (34) of π̂yŷ that (39) is only approached when ykw TF (xk)→∞, for all k ∈ {1, ..., n}.
C INVERTIBILITY IS BENEFICIAL
We show in Proposition C.1 that the lower bound for the classification error is itself lower bounded by a constant, which is attained if F is invertible. Although the performance of the model also depends on the classifier w, our bound claims that an invertible feature map F could provide a better environment for the classifier w to perform well. Intuitively, invertibility preserves the information of the signalX as it flows through the neural network and reaches the classifierw; on the other hand, w potentially performs better on the input that preserves all information of the data compared to the one that doesn’t. Proposition C.1. (Fano’s Inequality) The classification error is lower bounded as follows:
P(Y 6= Ŷ ) ≥ H(Y |F (X))− log(2) log(|C| − 1) . (40)
The lower bound satisfies
H(Y |F (X))− log(2) log(|C| − 1) ≥ H(Y |X)− log(2) log(|C| − 1)
(41)
for all F , and the equality is attained if F is invertible.
Let Z = F (X) and the machinery of deep learning can be decribed by the following Markov Chain:
Y → X → Z → Ŷ . (42)
Lemma C.1 is a technical result that helps to prove Proposition C.1. The information Z = F (X) has about the true labels Y is maximized when F is invertible, which is beneficial in the sense that the key information influential for classification can be well preserved. Lemma C.1 (Chain Rule). Given the Markov Chain assumption equation 42, we have
I(Y ; Ŷ ) ≤ I(Y ;Z) ≤ I(Y ;X) , (43)
and the second equality is attained if F is invertible.
Proof. We will only prove the second inequality and the first inequality follows by a similar argument. Consider the decomposition
I(Y ;X,Z) = ∫ X ∑ y ∫ Z p(x, y, z) log p(x, y, z) p(y)p(x, z) dxdz
= ∫ X ∑ y ∫ Z p(x|y, z)p(y, z) log p(x|y, z)p(y, z) p(y)p(x|z)p(z) dxdz
= I(Y ;Z) + ∫ X ∑ y ∫ Z p(x|y, z)p(y, z) log p(x|y, z) p(x|z) dxdz
= I(Y ;Z) + ∫ X ∑ y ∫ Z p(x, y|z)p(z) log p(x, y|z) p(x|z)p(y|z) dxdz
= I(Y ;Z) + I(X;Y |Z) . (44)
Similarly we obtain
I(Y ;X,Z) = I(X;Y ) + I(Y ;Z|X) . (45)
equation 44 together with equation 45 yields
I(Y ;Z) + I(X;Y |Z) = I(X;Y ) + I(Y ;Z|X) . (46)
According to the Markov Chain setting, Y and Z are conditionally independent given X , hence I(Y ;Z|X) = 0; in addition, the mutual information I(X;Y |Z) is nonnegative. It follows from (46) that
I(Y ;Z) ≤ I(Y ;X) . (47)
Next we present a lower bound for the classification error. This lower bound is negatively related to the mutual information I(Y ;F (X)), and it attains its minimum if F is invertible. Although the performance also depends on the classifier w, Proposition C.1 implies that an invertible feature map F allows more chances for the classifier w to perform well.
Proof of Proposition C.1. Consider the random variable E defined as:
E = { 1, if Y 6= Ŷ 0, otherwise .
(48)
By the Chain Rule following from similar arguments presented in Lemma C.1, we have
H(E, Y |Ŷ ) = H(Y |Ŷ ) +H(E|Y, Ŷ ) H(E, Y |Ŷ ) = H(E|Ŷ ) +H(Y |E, Ŷ ) . (49)
Note that H(E|Y, Ŷ ) = 0, since the value of E is determined given the knowledge of Y, Ŷ . It then follows that
H(Y |Ŷ ) = H(E|Ŷ ) +H(Y |E, Ŷ ) ≤ log(2) +H(Y |E = 0, Ŷ )P(E = 0) +H(Y |E = 1, Ŷ )P(E = 1) = log(2) +H(Y |E = 1, Ŷ )P(Y 6= Ŷ ) ≤ log(2) + log(|C| − 1)P(Y 6= Ŷ ) . (50)
On the other hand, Lemma C.1 shows that
H(Y )−H(Y |Ŷ ) = I(Y ; Ŷ ) ≤ I(Z;Y ) = H(Y )−H(Y |Ẑ) , (51)
which gives
H(Y |Z) ≤ H(Y |Ŷ ) . (52)
Substitute it into (50) yields the result
H(Y |Z) ≤ log(2) + log(|C| − 1)P(Y 6= Ŷ ) . (53)
As for the second statement, Lemma C.1 shows that
H(Y )−H(Y |Z) = I(Y ;Z) ≤ I(Y ;X) = H(Y )−H(Y |X) . (54)
It then follows that,
H(Y |Z) = H(Y |F (X)) ≥ H(Y |X) = 0 , (55)
where the equality is attained if F is invertible.
D INVERTIBILITY OF RESNET
ResNet is designed to allow the model to ”learn” the identity map easily. Specifically, the input vector x and output vector y of a building block are related by
y = L(x) + x = (L+ I)(x) , (56)
where the operator L could be a composition of activation functions, convolutions, dropout(Srivastava et al. (2014)) and batch normalization(Ioffe & Szegedy (2015)). It’s shown in Lemma D.1 below that if the operator norm |L| < 1, then L + I is theoretically guaranteed to have an inverse, which enables information preservation among intermediate layers. In Figure 5 we experimentally verify that |L| < 1 for all building blocks during the training process. In general, operations such as ReLU, pooling, drop-out are not invertible(Dosovitskiy & Brox, 2015); it’s challenging to build a strictly invertible network (Jacobsen et al., 2018). From this point of view, the beauty of ResNet lies in the fact that it’s guaranteed to be invertible regardless how L evolves during the training process, as long as |L| < 1. Although the usual design of ResNet does involve non-invertible components such as pooling, we argue that ResNet still has descent invertible property compared to the majority of other neural network designs. We also experimentally verify that our regularization does not improve a very deep ResNet on its performance by a clear margin; we speculate that information will lose more as it goes deeper.
Lemma D.1. Consider Holder Space C0,1(U), where U is the closure of some bounded open set U , with equiped Holder norm |L| = α supx∈U |L(x)| + supx,y∈U,x 6=y { |L(x)−L(y)| |x−y| } , here α is some
positive scalar. If L ∈ C0,1(U) and |L| < 1, then there exists B such that B(I+L) = (I+L)B = I .
Proof. It’s well known that C0,1(U) is a Banach space (Lax).
Define
B = ∞∑ n=0 (−L)n . (57)
Since |L| < 1, (57) is a Cauchy sequence and coverges in Banach space. Convergence sequences can be multiplied termwise, it follows that
BL = L ∞∑ n=0 (−L)n = − ∞∑ n=1 (−L)n = −(B − I) . (58)
So B(I + L) = I . The other equality (I + L)B = I can be shown to hold in the same fashion.
E IMPLEMENTATION DETAILS
We implement all models using Tensorflow. We modify the ResNet based on the code provided at https://github.com/tensorflow/models/tree/master/research/resnet. We follow the same learning rate scheme proposed in the original code. For the InvNet on MNIST, we train the network with initial learning rate 0.1, and decay it by 0.7 every 10 epochs. For both InvNet and ResNet, we apply the `1 norm regularization every 30 iterations.

heading: F RESULTS FOR ALL DIGITS ON INVNET
text: This is a reproduction of the feature statistical results of InvNet on MNIST for all digits for Figure 2.
We observe that each digits have their specific entries with high value assigned to both weights and feature means. An additional observation is that typically the feature entry with low mean also has low standard deviation, such entry rarely contributes to the logits for classification if the corresponding value of weight is also small.

heading: G RESULTS ON I-REVNET
text: We reproduce the results in Section 4.2 on i-RevNet (Jacobsen et al. (2018)). The statistics and ROC curves of the features produced by i-RevNet and Reg-i-RevNet on CIFAR10 is similar to those presented in Section 4.2.

heading: H HISTOGRAM ON FEATURES OF DIGIT 9
text: The histogram for values of feature entries of Digit 9 has a decaying shape but with a heavier tail compared to that of Gaussian with small variance. The spasity of w depends on our choice of hyperparameters. For example in Figure 4 we measure the sparsity of the learned w of RegResNet for CIFAR10: about 60% entries of w are precisely zero.

heading: I THE USE OF SURROGATE FUNCTIONS TO MINIMIZE MUTUAL INFORMATION
text: Our objective is
I(X, Ŷ ) = H(Ŷ )−H(Ŷ |X) . (59)
Assume Ŷ is uniformly distributed on C, H(Ŷ ) becomes a constant and we have −H(Ŷ |X) = − ∫ X ∑ ŷ∈C p(x, ŷ) log p(x, ŷ) p(x)
= − ∫ X p(x) ∑ ŷ∈C p(ŷ|x) log p(ŷ|x)
≈ − ∑ x∈Bat ∑ ŷ∈C p(ŷ|x) log p(ŷ|x) (60)
Note that (60) is composed of functions in the form a log a where a is the output of a softmax function on logits. For simplicity we consider the binary case where a = ( 1 + e−w TF (x) )−1 . The
derivative of it with respect to w takes the form
e−w TF (x)F (x)( 1 + e−wTF (x) )2 . (61)
Assume |wTF (x)| is large, if wTF (x) > 0 then the numerator decays exponentially with respect to |wTF (x)| and the denominator converges to 1; if wF (x) < 0 then the denonimator grows exponentially with respect to |wTF (x)| and dominates the numerator. To conclude, for large |wTF (x)| the gradient is decaying to zero exponentially. So the effect of punishing large logits |wTF (x)| by this objective is not clear as the gradient vanishes for large |wTF (x)|. We also analyzed the general softmax functions for multi-labels and found they exhibit similar properties.
We propose to use a surrogate function wTF (X) to minimize this objective to make the regularization effect more clear. We prove that our regularizer achieves the same goal compared to the mutual information objective but provides a better gradient for training.

Review summaries:
In this paper, the authors propose to train a model from the point of view of maximizing mutual information between the predictions and the true outputs, with a regularization term that minimizes irrelevant information while learning. They show that the objective can be minimized by looking to make the final layer vectors be as uncorrelated as possible to the final layer representations, and simplify the same by applying Holder’s inequality to make the optimization tractable. They also apply an L1 penalty on the final layer. Experiments on CIFAR and MNIST show that using their regularizer to train DNN models yield  gains in performance. The presence of the L1 penalty also makes the results more interpretable (to the extend possible by looking at a subset of features in the last layer of a DNN).