Understanding the groundbreaking performance of Deep Neural Networks is one
 of the greatest challenges to the scientific community today. In this work, we
 introduce an information theoretic viewpoint on the behavior of deep networks
 optimization processes and their generalization abilities. By studying the Information
 Plane, the plane of the mutual information between the input variable and
 the desired label, for each hidden layer. Specifically, we show that the training of
 the network is characterized by a rapid increase in the mutual information (MI)
 between the layers and the target label, followed by a longer decrease in the MI
 between the layers and the input variable. Further, we explicitly show that these
 two fundamental information-theoretic quantities correspond to the generalization
 error of the network, as a result of introducing a new generalization bound that is
 exponential in the representation compression. The analysis focuses on typical
 patterns of large-scale problems. For this purpose, we introduce a novel analytic
 bound on the mutual information between consecutive layers in the network.
 An important consequence of our analysis is a super-linear boost in training time
 with the number of non-degenerate hidden layers, demonstrating the computational
 benefit of the hidden layers. Deep Neural Networks (DNNs) heralded a new era in predictive modeling and machine learning. Their ability to learn and generalize has set a new bar on performance, compared to state-of-the-art methods. This improvement is evident across almost every application domain, and especially in areas that involve complicated dependencies between the input variable and the target label BID19 . However, despite their great empirical success, there is still no comprehensive understanding of their optimization process and its relationship to their (remarkable) generalization abilities.This work examines DNNs from an information-theoretic viewpoint. For this purpose we utilize the Information Bottleneck principle BID37 . The Information Bottleneck (IB) is a computational framework for extracting the most compact, yet informative, representation of the input variable (X), with respect to a target label variable (Y ). The IB bound defines the optimal trade-off between representation complexity and its predictive power. Specifically, it is achieved by minimizing the mutual information (MI) between the representation and the input, subject to the level of MI between the representation and the target label.Recent results BID35 , demonstrated that the layers of DNNs tend to converge to the IB optimal bound. The results pointed to a distinction between two phases of the training process. The first phase is characterized by an increase in the MI with the label (i.e. fitting the training data), whereas in the second and most important phase, the training error was slowly reduced with a decrease in mutual information between the layers and the input (i.e. representation compression). These two phases appear to correspond to fast convergence to a flat minimum (drift) following a random walk, or diffusion, in the vicinity of the training error's flat minimum, as reported in other studies (e.g. BID39 ).These observations raised several interesting questions: (a) which properties of the SGD optimization cause these two training phases? (b) how can the diffusion phase improve generalization perfor-mance? (c) can the representation compression explain the convergence of the layers to the optimal IB bound? (d) can this diffusion phase explain the benefit of many hidden layers?In this work we attempt to answer these questions. Specifically , we draw important connections between recent results inspired by statistical mechanics and information-theoretic principles. We show that the layers of a DNN indeed follow the behavior described by BID35 . We claim that the reason may be found in the Stochastic Gradient Decent (SGD) optimization mechanism. We show that the first phase of the SGD is characterized by a rapid decrease in the training error, which corresponds to an increase in the MI with the labels. Then, the SGD behaves like non-homogeneous Brownian motion in the weights space, in the proximity of a flat error minimum. This non-homogeneous diffusion corresponds to a decrease in MI between the layers and the input variable, in "directions" that are irrelevant to the target label.One of the main challenges in applying information theoretic measures to real-world data is a reasonable estimation of high dimensional joint distributions. This problem has been extensively studied over the years (e.g. BID28 ), and has led the conclusion that there is no "efficient" solution when the dimension of the problem is large. Recently, a number of studies have focused on calculating the MI in DNNs using Statistical Mechanics. These methods have generated promising results in a variety of special cases BID8 , which support many of the observations made by BID35 .In this work we provide an analytic bound on the MI between consecutive layers, which is valid for any non-linearity of the units, and directly demonstrates the compression of the representation during the diffusion phase. Specifically, we derive a Gaussian bound that only depends on the linear part of the layers. This bound gives a super linear dependence of the convergence time of the layers, which in turn enables us to prove the super-linear computational benefit of the hidden layers. Further, the Gaussian bound allows us to study mutual information values in DNNs in real-world data without estimating them directly. In this work we study DNNs using information-theoretic principles. We describe the training process of the network as two separate phases, as has been previously done by others. In the first phase (drift) we show that I(T k ; Y ) increases, corresponding to improved generalization with ERM. In the second phase (diffusion), the representation information, I(X; T k ) slowly decreases, while I(T K ; Y ) continues to increase. We rigorously prove that the representation compression is a direct consequence of the diffusion phase, independent of the non-linearity of the activation function. We provide a new Gaussian bound on the representation compression and then relate the diffusion exponent to the compression time. One key outcome of this analysis is a novel proof of the computational benefit of the hidden layers, where we show that they boost the overall convergence time of the network by at least a factor of K 2 , where K is the number of non-degenerate hidden layers. This boost can be exponential in the number of hidden layers if the diffusion is "ultra slow", as recently reported.1 m m i=1 h (x i , y i ) be the empirical error. Hoeffding's inequality BID12 shows that for every h ∈ H, DISPLAYFORM0 Then, we can apply the union bound and conclude that DISPLAYFORM1 We want to control the above probability with a confidence level of δ. Therefore, we ask that 2 H exp −2 2 m ≤ δ. This leads to a PAC bound, which states that for a fixed m and for every h ∈ H, we have with probability 1 − δ that DISPLAYFORM2 Note that under the definitions stated in Section 1.1, we have that |H| ≤ 2 X . However, the PAC bound above also holds for a infinite hypotheses class, where log |H| is replaced with the VC dimension of the problem, with several additional constants BID38 BID34 BID32 .Let us now assume that X is a d-dimensional random vector which follows a Markov random field structure. As stated above, this means that p(x i ) = i p(x i |P a(x i )) where P a(X i ) is a set of components in the vector X that are adjacent to X i . Assuming that the Markov random field is ergodic, we can define a typical set of realizations from X as a set that satisfies the Asymptotic Equipartition Property (AEP) BID6 . Therefore , for every > 0, the probability of a sequence drawn from X to be in the typical set A is greater than 1 − and |A | ≤ 2 H(X)+ . Hence, if we only consider a typical realization of X (as opposed to every possible realization), we have that asymptotically H ≤ 2 H(X) . Finally, let T be a mapping of X. Then, 2 H(X|T ) is the number of typical realizations of X that are mapped to T . This means that the size of the typical set of T is bounded from above by 2 H(X) 2 H(X|T ) = 2 I(X;T ) . Plugging this into the PAC bound above yields that with probability 1 − δ, the typical squared generalization error of T ,
Introduce an information theoretic viewpoint on the behavior of deep networks optimization processes and their generalization abilities
{"src": "scitldr-AIC_train", "paper_id": "SkeL6sCqK7"}