## Acknowledgments

First and foremost, I am extremely grateful to my supervisor and mentor,
Professor Naftali Tishby, who passed away recently. His invaluable advice,
continuous support, and patience during my Ph.D. study were so important. His
immense knowledge and plentiful experience have encouraged me in all the time
of my academic research and daily life. He was a remarkable man who gave me so
much, and I learned a lot from him. An incredible scholar and a lovely person.

I would also like to thank Prof. Haim Sompolinsky and Dr. Alex Alemi for their
support and guidance during my study. I wish to thank also my collaborators,
Zoe Piran and Dr. Amichai Painsky. It was a great privilege to work with them.

Finally, I cannot begin to express my gratitude to my wife and children.
Without their tremendous understanding and encouragement in the past few
years, it would be impossible for me to complete my study. There were always
there to support me and encourage me to succeed.

## Abstract

While deep neural networks have been immensely successful, a comprehensive
theoretical understanding of how they work or how they are structured does not
exist. Deep networks are often viewed as black boxes, where the interpretation
of predictions and their reliability are still unclear. Today, understanding
the groundbreaking performance of deep neural networks is one of the greatest
challenges facing the scientific community. To use these algorithms more
effectively and improve them, we need to understand their dynamic behavior and
their ability to learn new representations.

This thesis addresses these issues by applying principles and techniques from
information theory to deep learning models to increase our theoretical
understanding and use it to design better algorithms. The main results and
contributions of this thesis are structured in three parts, as detailed below.

Chapters 2 and 3 present our information-theoretic approach to deep learning
models. As an explanation for deep learning systems, we propose using the
Information Bottleneck (IB) theory. The novel paradigm for analyzing networks
sheds light on their layered structure, generalization capabilities, and
learning dynamics. Based on our analysis, we find that deep networks optimize
each layer’s mutual information on input and output variables, resulting in a
trade-off between compression and prediction for each layer. Our analytical
and numerical study of these networks demonstrated that the stochastic
gradient descent (SGD) algorithm follows the IB trade-off principle by working
in two phases: a fast empirical error minimization phase followed by a slow
representation compression phase. These phases are distinguished by different
signal-to-noise ratios (SNRs) for each layer. Moreover, we demonstrated that
the SGD achieved this optimal bound due to the compression phase, derived a
new Gaussian bound on the representation compression, and related it to the
compression time. Furthermore, our results indicate that the network’s layers
converge to the IB theoretical bound, leading to a self-consistent
relationship between the encoder and decoder distributions.

Chapter 4 deals with one of the most difficult problems of applying the IB to
deep neural networks — estimating mutual information in high dimnesional
space. Despite being an important quantity in data science, mutual information
has historically posed a computational challenge. Computing mutual information
is only tractable for discrete variables or for a limited number of problems
where probability distributions are known. To better estimate information-
theoretic quantities and to investigate generalization signals, we research
several frameworks and utilize recent theoretical developments, such as the
neural tangent kernel (NTK) framework. In our study, we found that for
infinite ensembles of infinitely wide neural networks, we could obtain
tractable computations of many information-theoretic quantities and their
bounds. Many quantities can be described in a closed-form solution by the
network’s kernels. By analyzing these derivations, we can learn the important
information-theoretic quantities of the network and how compression,
generalization, and the sample size are related.

Chapter 5 presents the dual Information Bottleneck (dualIB), a new
information-theoretic framework. Despite the IB framework’s advantages, it
also has several drawbacks: The IB is completely non-parametric and operates
only on the probability space. In addition, the IB formulation does not relate
to the task of prediction over unseen patterns and assumes full access to the
joint probability. Therefore, we developed the dualIB, which resolves some of
the IB’s drawbacks through a mere switch between terms in the distortion
function. The dualIB can account for known features of the data and use them
to make better predictions over unseen examples. We provide dualIB self-
consistent equations, allowing us to obtain analytical solutions. A local
stability analysis revealed the underlying structure of the critical points of
the solutions, resulting in a full bifurcation diagram of the optimal pattern
representations. We discovered several interesting properties of dualIB’s
objective. First, the dualIB retains its structure when expressed in a
parametric form. It also optimizes the mean prediction error exponent, thereby
improving prediction accuracy with respect to sample size. In addition to
dualIB’s analytic solutions, we provided a variational dualIB framework that
optimizes the functional using deep neural networks. The framework enables a
practical implementation of dualIB for real-world datasets. With it, we
empirically evaluated its dynamics and validated the theoretical predictions
in modern deep neural networks.

In conclusion, this thesis proposes a new information-theoretic perspective
for studying deep neural networks that draws upon the correspondence between
deep learning and the IB framework. Our unique perspective can provide a
number of benefits, such as attaining a deeper understanding of deep neural
networks, explaining their behavior, and improving their performance. At the
same time, our study opens up new theoretical and practical research
questions.

## Letter of Contribution

This dissertation includes four manuscripts that summarize Ravid Shwartz-Ziv’s
research under the supervision of Naftali Tishby. The work on this
dissertation was also done in collaboration with Dr. Alex Alemi (Google), Dr.
Amichai Painsky (Tel Aviv University) and Zoe Piran (The Hebrew University).
They provided valuable guidance and contributed to the writing of the papers
as co-authors. The lead author and primary contributor for three of these
manuscripts is Ravid Shwartz-Ziv. Ravid Shwartz-Ziv and Zoe Piran each
contributed equally to the manuscript “The Dual Information Bottleneck.” For
this manuscript, Ravid Shwartz-Ziv did the variational dual IB section and the
numerical experiments. The manuscripts are listed below. One was published in
a peer-reviewed venue, and three are yet to be published.

  1. 1.

“Opening the Black Box of Deep Neural Networks via Information”.
Co-author: Naftali Tishby. 2018.

  2. 2.

“Representation Compression and Generalization in Deep Neural Networks”.
Co-authors: Amichai Painsky and Naftali Tishby. 2019.

  3. 3.

“Information in Infinite Ensembles of Infinitely-Wide Neural Network”.
Co-author: Alex Alemi. Published in the Proceedings of the Symposium on
Advances in Approximate Bayesian Inference, PMLR, 2020.

  4. 4.

“The Dual Information Bottleneck”.
Co-authors: Zoe Piran and Naftali Tishby. 2020.

## Table of Contents

toc

## Introduction

Learning representations is at the core of many problems in computer vision,
natural language processing, cognitive science, and machine learning
(bengio2013representation). A complex data representation is required for
classification and prediction since physical parameters, such as location,
size, orientation, and intensity, are considered (salakhutdinov2013learning).
However, it is unclear what constitutes a good representation and how it is
related to learning and to the specific problem type.

By combining multiple transformations of simple neurons, deep neural networks
(DNNs) can produce a more useful (and, in most cases, more abstract)
representation. Due to their versatility and success across various domains,
these systems have gained popularity over the past few years. The performance
of DNNs demonstrates great improvements over conventional machine learning
methods in various domains, including images, audio, and text (devlin2018bert;
he2016deep; oord2016wavenet). The latest deep learning models are more
complex, and their architectures are becoming more complex with more
parameters that need to be optimized. The ResNet-$52$ network, for example,
contains about $23$ million parameters optimized over millions of images.

However, the reasons for these performances are only partially understood from
a theoretical perspective, and we only have a heuristic understanding of them.
It is unclear why deep models perform so well on real-world data and what
their key components are. In addition, current metrics do not provide insight
into the internal structure of a network or the quality of its layers. As a
result, even if the model is extremely accurate, it is difficult to use it as
a basis for further scientific research. To make these algorithms more
effective and improve them, we must understand their underlying dynamic
behavior and how they learn representations.

In this thesis, we propose studying DNNs from the perspective of information
theory. As an explanation for modern deep learning systems, we propose the
information bottleneck (IB) theory. We hope to shed light on their layered
structures, generalization capabilities, and learning dynamics through this
innovative approach for analyzing DNNs.

To better understand DNNs, the first question is as follows: How can
information theory in general and the IB framework, in particular, be used to
better understand DNNs?

Shannon invented the information theory to determine the number of bits needed
to transmit a message over a noisy channel. This theory has since been shown
to be an invaluable measure of the influence between variables
(shannon1948mathematical). Given two random variables $X$ and $Y$, the mutual
information between them measures the divergence of their joint probability
distribution $P(x,y)$ from the product of their marginals $P(x)P(y)$ to
determine how dependent or independent they are. The notion of mutual
information, unlike correlation, can capture nonlinear statistical
relationships between variables, strengthening our ability to analyze complex
system dynamics (kinney2014equitability). Although mutual information is an
essential quantity in data science, it has historically been challenging to
estimate (paninski2003estimation). Exact computations are tractable only for a
limited number of problems with well-defined probability distributions (e.g.,
the exponential family). The calculation of mutual information is not possible
for finite samples of data or general problems.

This leads us to the following research question: How can we calculate the
mutual information for large-scale DNNs? To derive an exact calculation of
information-theoretic quantities and to search for generalization signals, we
examined several frameworks and utilized current theoretical developments,
including the Neural Tangent Kernel (NTK) framework (lee2019wide). We obtained
tractable calculations of information-theoretic quantities and their bounds
for infinite ensembles of infinitely-wide neural networks. Our analysis
revealed that the kernels described many quantities in a closed form.
Furthermore, we found that the input’s compression contributed to the
generalization in this model family.

Although the IB framework has its advantages, it also has a few disadvantages,
including an inability to preserve the structure of the data and suboptimal
performance with finite data. The final research question concerns whether we
can derive a new framework that can solve these problems and apply it to DNNs.

Therefore, we developed the dual IB (dualIB), which switches between the terms
in the distortion function to solve some of the problems with the IB. A local
stability analysis revealed the underlying structure and optimal pattern
representations. We discovered that the dualIB retains its structure when
expressed in a parametric form. Furthermore, it optimizes the mean prediction
error exponent, improving the predictions’ accuracy with respect to sample
size. dualIB can be applied to real-world datasets using neural networks with
the help of a variational framework. Using this framework, we evaluated the
dynamics of the dualIB and validated the theoretical predictions.

First, we examine some of the information-theoretic principles upon which this
thesis is based. The chapter concludes by highlighting the main contributions
of the thesis.

###  1.1 Information theory

In 1948, Shannon’s paper established the area of information theory
(shannon1948mathematical). Communication, which refers to sending information
with the receiver’s intent, is one of the main topics in information theory.
Shannon’s work served as the basis for quantifying the questions regarding
this information. Let us review the results of information theory relevant to
this thesis. In the present work, we use the following notation: Upper-case
letters denote random variables (e.g., $X$), calligraphic letters denote their
support (e.g., $\mathcal{X}$), and lower-case letters denote specific
realizations (e.g., $x$).

####  1.1.1 Theoretical information quantities

As a formal concept, information is a function of several basic measures based
solely on the probability distribution of random variables without any
particular assumptions.

Consider $X\in\mathcal{X}$ and $Y\in\mathcal{Y}$ as random variables with the
joint distribution function of $p(x,y)$. Our first definition of information
is entropy, which takes into account the amount of uncertainty involved with a
given distribution.

######  Definition 1.1.1.

Entropy

The entropy of $X\sim p(x)$ is defined as

$H(X)=-\sum_{x\in\mathcal{X}}p(x)\log(p(x))$

Shannon axiomatically derived this definition by defining three intuitive
properties of uncertainty measures (continuity, additivity, and monotonicity).
Entropy is the only function that satisfies these requirements. Intuitively,
entropy reflects the minimum description length of $X$ because it is (roughly)
the minimal number of bits or binary questions needed to determine the exact
value of $X$.

If the distribution is uniform, then the entropy reaches its maximum. If it is
deterministic, then it is zero. As $H(X)$ is concave, the more $X$ strays away
from being completely unpredictable, the more it is punished by $H(X)$.

Our next informational measure is the Kullback-Leibler (KL) divergence, also
known as relative entropy, which measures the divergence between two
distributions.

######  Definition 1.1.2.

Kullback Leibler Divergence

The KL divergence between two distributions $p(x)$ and $q(x)$ is defined as

$D[p||q]=\sum_{x\in\mathcal{X}}p(x)\log\left(\frac{p(x)}{q(x)}\right)$

In the case where $p(x)=q(x)$ for some $x$, then it will not contribute to
$D[p||q]$. If for all $x$, $p(x)=q(x)$, then $D(p||q)=0$. When $p$ and $q$
have a low Kullback-Leibler distance, they are similar. Conversely, a high
distance indicates they are dissimilar.

It can be shown that $D[p|q]\geq 0$ and that equality holds if and only if
$p=q$ almost everywhere. Note that the KL divergence is not a metric because
it is not symmetric and does not obey the triangle inequality. However, it is
still useful to think of it as the natural ”distance” between distributions
for several reasons. First, notice that $D[p||q]$ is the expected log-
likelihood ratio between $p(x)$ and $q(x)$. Thus, it controls the
discriminability between these two distributions when $p$ is the true
underlying distribution of $X$. Secondly, the KL divergence reflects the
difference between the minimal description length of $X\sim p(x)$ and the
description length if $q(x)$ is used instead of $p(x)$. To see this, notice
that $D[p|q]=\sum_{x}p(x)log\frac{1}{q(x)}-H(X)$, and recall that $H(X)$ is
the minimal description length. Third, Pinsker’s inequality implies that the
KL divergence upper bounds the $L1$ distance between $p$ and $q$. Therefore,
it also bounds any $L_{\rho}$ distance for $\rho\geq 1$.

The last piece of information we will present is mutual information.

######  Definition 1.1.3.

Mutual Information

Let $(X,Y)\sim p(x,y)$, and let $p(x)$ and $p(y)$ be their marginal
distributions, respectively. The mutual information between $X$ and $Y$ is
defined as

$I(X;Y)=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}$

Mutual information is a useful method for measuring statistical dependence
between variables and has many beneficial properties. For example, it remains
invariant under bijective transformations. Its predecessor, called the
transmission rate, was first introduced by Shannon in 1948
(shannon1948mathematical) for a communication system. Mutual information can
be axiomatically derived as a function satisfying several natural
‘informativeness’ conditions (cover1999elements).

Mutual information could be understood by thinking of the $KL$ divergence
between $p(x,y)$ and the hypothetical joint distribution if $X$ and $Y$ were
independent.

$I(X;Y)=D[p(x,y)||p(x)p(y)]$

It thus follows that $I(X;Y)\geq 0$ and $I(X;Y)=0$ if and only if $X$ and $Y$
are independent. Alternatively, mutual information can be interpreted as
reducing uncertainty regarding one variable due to the knowledge of the other
variable.

$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)$

Since $H(X|Y),H(Y|X)\geq 0$, it holds that $I(X;Y)\leq\min\\{H(X),H(Y)\\}$. If
$H(X|Y)=0$, that is, $X$ is completely known given $Y$, then $I(X;Y)=H(X)$. As
a special case, it holds that $I(X;X)=H(X)$. In this sense, mutual information
is more general than entropy, whereas entropy is sometimes referred to as
self-information.

One of the important properties of mutual information is the data processing
inequality (DPI), which implies that the information about $X$ contained in
$Y$ cannot be increased by processing $Y$. Formally, we say that $(X,Y,Z)$
form a Markov chain if their joint distribution can be decomposed as
$p(x,y,z)=p(x,y)p(z|y)$, $Z$ is a function of $Y$ and given $Y$, it is
independent of $X$. Then, the DPI implies

$I\left(X;Y\right)\geq I(X;Z)$ (1.1)

for any 3 variables that form a Markov chain $X\rightarrow Y\rightarrow Z$.

Mutual information is also invariant with respect to invertible
transformations:

$I\left(X;Y\right)=I\left(\psi(X);\phi(Y))\right)$ (1.2)

for any invertible functions $\phi$ and $\psi$.

###  1.2 Representation learning

Machine learning is a field of Artificial Intelligence (AI) that automatically
learns and improves from experience. These models use an internal
representation of the input based on prior observations or data records to
make better decisions. Learning representations lie at the core of many
computer vision problems, natural language processing, cognitive science, and
machine learning (bengio2013representation). Even so, the question of what
constitutes a good representation or the relationship between representation,
learning process, and specific features of a problem remains unanswered.

David Marr (marr2010vision) defined representation as a formal system for
making explicit particular entities and types of information that an algorithm
can use to process information. In this thesis, we focus on the second part –
the idea that algorithms operate on representations. Representation learning
refers to learning structures in the data. This learning makes it easier to
extract useful information to classify and make predictions based on the data
(Goodfellow-et-al-2016-Book). The question of what a good representation is
has many answers. For probabilistic models, a good representation often
captures the posterior distribution of the underlying explanatory factors for
the observed input (natureDeepLeraning). In their AI-tasks, Bengio and LeCun
(BengioAndLecunMIT) introduced the concept of complex but highly structured
dependencies. In most cases, the tasks require transforming a high-dimensional
input structure into a low-dimensional output or learning low-level
representations. Accordingly, most of the input’s entropy is not relevant for
the output, and it is difficult to extract the input’s relevant features
(TishbyZ15).

####  1.2.1 Large deviation theory and the Sanov theorem

Statisticians, information theorists, and machine learning scientists share
concepts for defining and extracting the optimal representation from
observations. How would we characterize the optimal representation of the
random input variable $X$? In general, we would like to have a representation
that achieves high values for some reward function. In addition, we aim to
learn efficiently these representations by using an empirical sample of the
(unknown) joint distribution, which will enable us to generalize to unknown
datasets.

As we will see in the following section, the large deviation theory can be
used to illustrate the idea that constraining information with the
representation will produce a representation that is more likely to
generalize. This approach is derived from the type analysis and the Sanov
theorem (cover1999elements). It is presented here for an independent and
identically distributed (i.i.d.) process, although a Markov type analysis is
also available (csiszar1987conditional).

With the large deviation theory, we can understand the probability of rare
events, i.e., events with an exponentially small probability. Type analysis is
applied to analyze the most likely samples from a given probability
distribution following a constraint. Sanov’s theorem identifies the rate
function for large deviations of the empirical measure of a sequence of i.i.d.
random variables. The type definition and the Sanov Theorem for i.i.d.
processes (cover1999elements) are presented here with an adaptation of the
annotation to our needs.

Let $T_{1},T_{2},\ldots$ be i.i.d. random variables with values in a finite
set $A=\\{\alpha_{1},\ldots,\alpha_{r}\\}$ and with a distribution $P$. Denote
by $\mathcal{P}$ the set of probabilities on
$\\{\alpha_{1},\ldots,\alpha_{r}\\}$. Let $\hat{P}_{n}$ be the empirical
distribution of $T$:

$\hat{P}_{n}=\frac{1}{n}\sum_{k=1}^{n}\delta_{T_{k}}.$

The law of large numbers states that $\hat{P}_{n}\rightarrow P$ almost surely.
To define a rare event, we fix $E\subseteq\mathcal{P}$ that does not contain
$P$. We are interested in the behavior of probabilities of the form
$\mathcal{P}[\hat{P}_{n}\in E]$, as $n\rightarrow\infty$.

It is a trivial observation that each possible value
$\\{\alpha_{1},\ldots,\alpha_{r}\\}$ must appear an integer number of times
among the samples $\\{T_{1},\ldots,T_{n}\\}$. This implies, however, that the
empirical measure $\hat{P}_{n}$ cannot take arbitrary values.

######  Definition 1.2.1.

Type $P_{t}$ of the sequence $t=t_{1},t_{2},\dots,t_{n}$ is the relative
proportion of occurrences of each value. That is,
$P_{t}(\alpha)=\frac{N(\alpha|t)}{n}$ where $N(\alpha|x)$ is the number of
times $\alpha$ occurs in the sequence t.

By definition, each type contains only information about how often each value
shows up in the sample, discarding the order in which they appear. The
importance of it is that large numbers of sequences are associated with each
type, and each type is associated with a single reward value $\sum_{\alpha\in
A}P(\alpha)R(\alpha)=\bar{R}$. It is always the case that
$\hat{P}_{n}\in\mathcal{P}_{n}$, where we define $\mathcal{P}_{n}$ as the set
of types associated with sequences of samples with length $n$.

######  Theorem 1.2.1.

Sanov Let $t_{1},t_{2},\dots t_{n-1}$ be i.i.d. sequence from $P(t)$. Let
$E\subseteq\mathcal{P}_{n}$ be a set of types that is equal to the closure of
its interior.

$\lim_{n\to\infty}\frac{1}{n}\log P^{n}[\hat{P}_{n}\in
E]=-D_{KL}(P^{\star}|P^{n})$

where $P^{\star}=arg\min_{Q\in E\cap\mathcal{P}_{n}}D_{KL}(Q|P^{n})$.

For our needs, we define the set $E$ to be all the types (and the sequences
that are associated with them) that achieve a reward above the desired
threshold $\theta$; i.e., $E=\sum\\{P_{\alpha\in
A}P(\alpha)R(\alpha)\geq\bar{R}\\}$.

Sanov’s theorem gives us an important insight: the most likely sequence to be
selected as a type that is the closest from the $D_{KL}$ perspective to the
distribution $P(t)$ (denoted as $P^{\star}$). This insight can be formalized
as a trade-off, where on one side, we have the reward $\bar{R}$, and on the
other, we have $D_{KL}$. The selected solution is governed by a parameter
$\beta$, which is the Lagrange multiplier coefficient. Given the nature of the
types, they can be visualized and represented as points of a simplex whose
axes are the probabilities of each symbol to appear. In this space, the two
crucial points are the maximal reward point (a deterministic point at the edge
of the simplex) and $P$. The trade-off parameter $\beta$ defines a set of
distributions that form a line between these points. These are known as
geodesic lines. No two points along this line have the same $\beta$, and
therefore they do not have the same $D_{KL}$ value.

####  1.2.2 Minimal sufficient statistic

An alternative definition of what constitutes a good representation is based
on minimal sufficient statistics.

######  Definition 1.2.2.

Let $(X,Y)\sim P(X,Y)$ . Let $T:=t(X)$ , where $t$ is a deterministic
function. We call T a sufficient statistic of $X$ for $Y$ if $Y-T-X$ forms a
Markov chain.

Therefore, a sufficient statistic captures all the information about $Y$ that
is available in $X$. The following theorem states this property:

######  Theorem 1.2.2.

cover1999elements Let $T$ be a probabilistic function of $X$. Then, $T$ is a
sufficient statistic for $Y$ if and only if (iff ) $I(T(X);Y)=I(X;Y)$

As we can see, the sufficiency definition includes the trivial identity
statistic $T=X$. Such statistics accomplish nothing since all they do is
”copy” rather than ”extract” important information. Therefore, it is necessary
to prevent statistics from using observations in an inefficient manner.

To address this issue, the concept of minimal sufficient statistics was
introduced:

######  Definition 1.2.3.

(Minimal sufficient statistic (MSS)) A sufficient statistic $T$ is minimal if
for any other sufficient statistic $S$ , there exists a function $f$ such that
$T=f(S)$ almost surely (a.s.).

MMS are the simplest sufficient statistics and induce the coarsest sufficient
partition on $X$. MSS try to group the values of $X$ into as few partitions as
possible without sacrificing any information. In addition, MSS can be shown to
be the statistic with all the available information about $Y$ while retaining
as little information about $X$ as possible. Generally, sufficient statistics
are restricted, in the sense that their dimension always depends on the sample
size, unless the data comes from an exponential family distribution
(koopman1936distributions).

####  1.2.3 The Information Bottleneck

Since exact minimal sufficient statistics only exist for special
distributions, tishby2000information relaxed this optimization problem in two
ways: (i) allowing the map to be stochastic, defined as an encoder $p(T|X)$,
and (ii) allowing the map to capture only as much as possible of $I(X;Y)$, but
not necessarily all of it. They introduced the Information Bottleneck (IB) as
a principled approach to extract relevant information from observed signals
related to a target. For a random variable $x\in X$, this framework finds the
best trade-off between the accuracy and the complexity related to another
random variable $y\in Y$ with a joint distribution. The IB has been used in
several fields, including neuroscience (buesing2010spiking;
palmer2015predictive), slow feature analysis (turner2007maximum), speech
recognition (hecht2009speaker) and deep learning (TishbyZ15;
shwartz2017opening; alemi2016deep).

Let $X$ be an input random variable, $Y$ a target variable, and $p(x,y)$ their
joint distribution. A representation $T$ is a stochastic function of $X$
defined by a mapping $p(t|x)$. This mapping can be viewed as transforming
$X\sim P(X)$ into a representation of $T\sim P(T):=\int P_{T\mid
X}\brk*{\cdot\mid x}dP_{X}(x)$ in the $\mathcal{T}$ space.

The triple $Y-X-T$ forms a Markov chain in that order w.r.t. the joint
probability measure $P_{X,Y,T}=P_{X,Y}P_{T\mid X}$ and the mutual information
terms $I(X;T)$ and $I(Y;T)$.

As part of the IB framework, we aim to find a representation $P(T\mid X)$ that
extracts as much information as possible about $Y$ (high performance), while
compressing $X$ maximally (keeping $I(X;T)$ small). We could also interpret it
as extracting only the relevant information that $X$ contains about $Y$.

The DPI implies $I(Y;T)\leq I(X;Y)$, so the compressed representation $T$
cannot convey more information than the original signal. As a result, there is
a tradeoff between compressed representation and the preservation of relevant
information about $Y$. The construction of an efficient representation
variable is characterized by its encoder and decoder distributions, $P(T|X)$
and $P(Y|T)$, respectively. The efficient representation of $X$ means
minimizing the complexity of the representation $I\left(T;X\right)$ while
maximizing $I\left(T;Y\right)$. Formally, the IB optimization involves
minimizing the following objective function:

$\displaystyle\mathcal{F}\brk[s]*{p_{\beta}\brk*{t\mid x};p_{\beta}\brk*{y\mid
t}}=I(X;T)-\beta I(Y;T)\leavevmode\nobreak\ ,$ (1.3)

where $\beta$ is a parameter that controls the trade-off between the
complexity of $T$ and the amount of relevant information it preserves.
Intuitively, we pass the information that $X$ contains about $Y$ through a
“bottleneck” via the representation $T$. It can be shown that

$\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]$ (1.4)

IB representations can be found using the IB method, a variant of the Blatu
Arimoto algorithm (blaArimo). For any $\beta$, the conditions for a stationary
point of equation 1.3, can be expressed via the following self-consistent
equations (tishby2000information):

$\displaystyle\begin{cases}\brk*{i}\ &p_{\beta}\brk*{t\mid
x}=\frac{p_{\beta}\brk*{t}}{Z_{t\mid{\mathbf{x}}}\brk*{x;\beta}}e^{-\beta
D\brk[s]*{p\brk*{y\mid x}\|p_{\beta}\brk*{y\mid t}}}\\\ \brk*{ii}\
&p_{\beta}\brk*{t}=\sum_{x}p_{\beta}\brk*{t\mid x}p\brk*{x}\\\ \brk*{iii}\
&p_{\beta}\brk*{y\mid t}=\sum_{x}p\brk*{y\mid x}{p_{\beta}\brk*{x\mid
t}}\end{cases},$ (1.5)

where $Z_{t\mid{\mathbf{x}}}\brk*{x;\beta}$ is a normalization term. If $X$,
$Y$, and $T$ take values in finite sets, and $P(X,Y)$ is known, then
alternating iterations of 1.5 locally converge to a solution, for any initial
$P(T\mid X)$.

If we denote $I_{X}^{\beta}=I_{\beta}\left(T;X\right)$ and
$I_{Y}^{\beta}=I_{\beta}\left(T;Y\right)$, the optimal information curve is
defined as the optimal values of the trade-off
$\left(I_{X}^{\beta},I_{Y}^{\beta}\right)$ for some $\beta$. The information
plane is the two-dimensional plane in which the IB curve resides. The
equations in 1.5 are satisfied along the information curve, which separates
the feasible and unfeasible regions of the information plane by a monotonic
concave line.

###  1.3 Deep neural networks

In 1958, Frank Rosenblatt developed the perceptron algorithm, the first
artificial neural network component (rosenblatt1958perceptron). The system was
designed to mimic the way the human brain processes visual data and identifies
recognizable objects. It was extended to pattern recognition in the late
1980s.

Deep learning can perform hierarchical learning of the data by applying
nonlinear transformations, which distinguishes it from traditional neural
networks. The data are cumulatively passed across multiple layers, which may
be fully connected or partially connected. DNNs are multilayer structures
constructed by processing units that are called neurons. Each neuron’s
activation involves the weighted summation of neuron inputs from the previous
layer, followed by the transfer function’s operation. Interconnected layers of
these basic computing blocks are used to build complex deep learning
architectures (DBLP:journals/corr/Schmidhuber14). Using this structure, DNNs
can learn hierarchically sophisticated features directly from raw data without
manually constructing them (salakhutdinov2013learning). Deep architectures are
often more challenging to effectively train. They bring, however, two
significant advantages: (1) they promote the reuse of features, and (2) they
can potentially lead to progressively more abstract features at higher layers
of representation, which hopefully make it easier to separate the explanatory
factors in the data (erhan2009difficulty).

Although deep architectures have long existed, the term “deep learning” was
first used in $2006$ by hinton2006fast. This work showed that a multilayer
feedforward neural network could be more efficient by applying pretraining of
one layer at a time and considering each layer as an unsupervised Restricted
Boltzmann Machine (RBM) by using supervised backpropagation for finetuning. In
2007, bengio2007greedy developed the Stack AutoEncoder (SAE), which comprises
a deep architecture of many AutoeEcoders (AEs).

In 2012, krizhevsky2012imagenet proposed the AlexNet architecture, which won
the ImageNet challenge. This was a significant breakthrough in artificial
neural networks. They proposed a deep convolutional neural network with nine
layers and implemented it over GPUs for the first time. Several extensions of
the vanilla AlexNet network have been developed since then, including deeper
convolutional nets as proposed by simonyan2014very and residual connections as
demonstrated by ren2015faster. DNNs have demonstrated their ability to improve
state-of-the-art results in a wide range of machine learning tasks over the
past few years. In many areas, from visual object recognition to speech
recognition and genomics to drug discovery, they work well and enhance state-
of-the-art results dramatically (DBLP:journals/corr/abs-1303-5778;
DBLP:journals/corr/ZhangL15; DBLP:journals/corr/abs-1207-0580;
DBLP:journals/corr/HeZRS15; natureDeepLeraning).

###  1.4 Information Bottleneck and DNNs

Even though DNN has been highly successful, little is known about its reasons
for success, and no underlying principles have driven its development. DNNs
are often considered black boxes, where the interpretation of predictions and
reliability are still open questions. Additionally, their internal structure
and the optimization process are still not fully understood. To use these
algorithms more efficiently and improve them, we need to understand their
dynamic behavior and their ability to learn representations.

In the literature, two areas of work involve DNNs and the IB. One uses the IB
concept to analyze DNNs, while the other uses the IB to improve the learning
algorithm for DNNs. The rest of this section is divided into these categories.

####  1.4.1 Information Bottleneck as optimization objective

Recently, the IB framework was explored as an objective for deep learning.
This concept was achieved by optimizing the IB Lagrangian using a variational
bound (alemi2016deep; olchinsky2019nonlinear).

The variational information bottleneck (VIB) approach presented in
(alemi2016deep) used DNNs to parameterize the IB model. A variational
approximation of the objective is parametrized using DNN, and an efficient
training algorithm is suggested for obtaining a stochastic network that maps
inputs to randomized representations.

Given a DNN, denote its output representation as $T$, a randomized mapping
operating on the input feature $X$, where the corresponding label is $Y$. The
encoding of $X$ into $T$ is defined through a conditional probability
distribution, which is parametrized as $p^{\theta}_{T\mid X}$. The VIB
optimization objective is

$\mathcal{L}_{\beta}^{\mathsf{\left({VIB}\right)}}\left({\theta}\right)\mathrel{\mathrel{\mathop{:}}=}\max_{\theta\in\Theta}I\big{(}T^{\left({\theta}\right)};Y\big{)}-\beta
I\big{(}X;T^{\left({\theta}\right)}\big{)}.$ (1.6)

However, since the data distributions $P_{X,Y}$ and $P_{T\mid X}$ are unknown,
a direct optimization of Equation 1.6 is intractable. To overcome it,
alemi2016deep suggested to lower bound Equation 1.6 in a form that we can
optimize:

$\mathbb{E}_{P^{\left({\theta}\right)}_{Y,T}}\left[{\log
Q^{\left({\phi}\right)}_{Y|T}\left({Y\Big{|}T^{\left({\theta}\right)}}\right)}\right]-\beta\mathsf{D}_{\mathsf{KL}}\left({P^{\left({\theta}\right)}_{T|X}\Big{\|}P_{T}^{\left({\theta}\right)}}\right),$
(18)

In this case, we parametrize the decoder $Q^{phi}_{(Y\mid T}$ by a DNN.
However, the main difficulty of this optimization is intractable marginal
distribution $P^{\theta}_{T}$. To circumvent this, we take $p_{T\mid X}$ and
$p_{T}$ distributions with a closed-form KL solution. In this case, we treat
the network output’s encoder as the parameters of $P_{T\mid X}$.

Using the reparametrization trick from kingma2013auto and replacing $P(X,Y)$
with its empirical proxy, the loss function of IB can be approximated as

$\displaystyle\hat{\mathcal{L}}_{\beta}^{\left({\mathsf{VIB}}\right)}\left({\theta,\phi,\mathcal{D}_{n}}\right)\mathrel{\mathrel{\mathop{:}}=}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[{-\log
Q^{\left({\phi}\right)}_{Y|T}\left({y_{n}\big{|}f\left({x_{n},T}\right)}\right)}\right]$
$\displaystyle+\beta\mathsf{D}_{\mathsf{KL}}\left({P^{\left({\theta}\right)}_{T|X}\left({\cdot|x_{n}}\right)\Big{\|}R_{T}\left({\cdot}\right)}\right).$
(19)

$T$ is an auxiliary noise variable, and the expectation is w.r.t to its law.
Note that if $t$ represents the output of a DNN, the first term is cross-
entropy, which is derived from the loss function common in deep learning. The
second term acts as a regularization term that penalizes the dependence of $X$
on $T$, thus encouraging compression. An unbiased estimate of the true
variational lower bound can be obtained through standard stochastic gradient-
based methods by calculating the estimator’s gradient.

Since alemi2016deep, various extensions have been developed, demonstrating
promising attributes (strouse2017deterministic; elad2019direct;
kolchinsky2019nonlinear). Recently, the conditional entropy bottleneck (CEB)
(fischer2020ceb) has been proposed. The CEB provides variational optimizing
bounds on $I(Y;T)$ and $I(X;T)$ using a variational decoder $q(y|x)$,
variational conditional marginal, $q(t|y)$, and a variational encoder,
$p(t|x)$, all implemented by DNNs. alemi2016deep also showed that the
variational auto-encoder (VAE) (kingma2013auto) can be considered as an
estimation for a special case of IB when $Y=X$, $\beta=1$ and the prior
distribution function is fixed.

####  1.4.2 Information Bottleneck theory for deep learning

TishbyZ15 proposed a theoretical framework to analyze DNNs based on the
principle of the IB. They formulated the ultimate goal of the network as a
trade-off between compression and prediction. An optimal point on the
information curve exists for each layer where this trade-off can be addressed
effectively. The layer’s network structure forms a Markov chain, where each
layer processes inputs from the previous layer. Due to DPI, any loss of
information about $Y$ in one layer is not recoverable in higher layers.

Formally, define $t^{i}\in T_{i}$ as the compressed representation of $x$ in
the i-th layer and $\hat{y}$ as the network’s output. $T_{i}$ is uniquely
mapped to a single point in the information-plane with coordinates
$\left(I(X;T_{i}),I(T_{i};Y)\right)$. We map a network with $k$ layers to $K$
monotonic connected points in the plane. For any $k\geq j$, it holds that

$\begin{array}[]{c}H\left(X\right)\geq I\left(X;T_{j}\right)\geq
I\left(X;T_{k}\right)\geq I\left(X;\hat{Y}\right)\\\ I\left(Y;X\right)\geq
I\left(Y;T_{j}\right)\geq I\left(Y;T_{k}\right)\geq I\left(Y;\hat{Y}\right)\\\
I\left(X;T_{j}\right)\geq I\left(Y;T_{j}\right),\end{array}$ (1.7)

and the equality in the second line is achieved IFF each layer is a sufficient
statistic of its input. Using this framework, each layer should extract a
compact representation while preserving the relevant information.

By successively decreasing $\beta$, we shift the network from low
representations and construct higher and more abstract ones. On the one hand,
$I\left(Y;T_{i}\right)$ measures how much of the predictive features in $X$
for $Y$ is captured by the layer and can view it as an upper bound of the
layer’s quality. On the other hand, $I\left(X;T_{i}\right)$ can be interpreted
as the complexity of the layer. As a result, we can assess the performance of
DNNs not just in terms of output, as we do when we use other measures of error
when evaluating DNNs.

Based on the theoretical IB limit and the limitations imposed by the DPI on
the information flow between layers, we can get a good sense of each layer’s
optimality in the network. With each successive layer, the IB distortion level
increases, but it also compresses the inputs, hopefully removing only non-
relevant information (TishbyZ15).

.9

Figure 1.2: A qualitative information plane from TishbyZ15, a hypothesized
path of the layers in a typical DNN (green line) on the training data. The
black line is the optimal achievable IB limit, and the blue lines are sub-
optimal IB bifurcations. The red line corresponds to the upper bound on the
out-of-sample IB distortion when training from a finite sample. We want to
shift the green DNN layers closer to the optimal curve to obtain lower
complexity and better generalization by shifting the last layer to the maximum
of the red curve.

####  1.4.3 Information bounds on the generalization gap

Based on the statistical learning theory, models with many parameters tend to
overfit by modeling learned data too accurately, which reduces their ability
to generalize to new data (boucheron2005theory). In practice, however, we see
that DNNs have a minimal generalization gap between training and testing.
Recently, there has been much interest in understanding implicit
regularization. Researchers’ findings indicate that network size is not the
most important factor involved in the process of learning multilayer
feedforward networks and that some unknown factors are important
(neyshabur2014search). Moreover, conventional statistical learning theories,
such as Rademacher complexity, VC-dimension, and uniform stability (stavac;
bartlett2002rademacher; bousquet2002stability), do not explain all of the
unexpected results of numerical experiments. According to
zhang2016understanding, regularization plays a unique role in deep learning
that differs from empirical risk minimization. However, convincing experiments
have indicated that the generalization gap can be reduced even without
explicit regularization. In recent years, several works have demonstrated that
the mutual information between the training inputs and the inferred parameters
provides a concise bound on the generalization gap (xu2017information;
pensia2018generalization; NIPS2019_9282; NIPS2018_7954; russo2016controlling;
steinke2020reasoning; achille2019information). achille2018emergence
investigated how using an IB objective on network parameters (rather than the
representations) could avoid overfitting while enforcing invariant
representations.

###  1.5 Infinitely-wide neural networks

Neural tangent kernel (NTK) is a powerful theoretical tool for modeling neural
networks. lee2019wide showed that if neural network training is modeled as
gradient flow, the training trajectory can be modeled by ordinary differential
equations (ODEs). Equations like these represent a finite-width tangent kernel
encoded by the network architecture and its current time-dependent weights.
Moreover, they showed that if one scales the learning rate per layer
appropriately (”NTK parametrization”) and lets the width tend to infinity,
this kernel converges to the infinite-width NTK. By being independent of
weights and staying constant throughout training, this model simplifies the
ODE in this limit. They showed that for $l2$ loss, the predictor at
convergence would be produced by a kernel regression using an infinite-width
NTK. Importantly, the NTK depends only on the architecture of the network and
is not learned.

Infinitely-wide neural networks behave as they are linear in their parameters
(lee2019wide):

$z(x,\theta)=z_{0}(x)+\frac{\partial
z_{0}}{\partial\theta}(\theta-\theta_{0})\quad z_{0}(x)\equiv
z(x,\theta_{0}).$ (1.8)

This makes them particularly analytically tractable. An infinitely-wide neural
network, trained by gradient flow to minimize the squared loss, admits a
closed form expression for the evolution of its predictions as a function of
time:

$z(x,\tau)=z_{0}(x)-\Theta(x,\mathcal{X})\Theta^{-1}\left(I-e^{-\tau\Theta}\right)(z_{0}(\mathcal{X})-\mathcal{Y}).$
(1.9)

Here, $z$ denotes the output of our neural network acting on the input $x$.
$\tau$ is a dimensionless representation of the time of our training process.
$\mathcal{X}$ denotes the whole training set of examples, with their targets
$\mathcal{Y}$; $z_{0}(x)\equiv z(x,\tau=0)$ denotes the neural networks output
at initialization. The evolution is governed by $\Theta$ (the NTK). For a
finite width network, the NTK corresponds to $JJ^{T}$, the neural network
gradients’ gram matrix. As the network’s width increases to infinity, this
kernel converges in probability to a fixed value. Tractable ways to calculate
the exact infinite-width kernel for broad classes of neural networks are
available (lee2019wide). The shorthand $\Theta$ denotes the kernel function
evaluated on the train data ($\Theta\equiv\Theta(\mathcal{X},\mathcal{X})$).

Observe that infinitely-wide networks trained with gradient flow and squared
loss behave as affine transformations of their initial predictions. As a
result, for an infinite ensemble of such networks, if the initial weight
configurations are drawn from a Gaussian distribution, the law of large
numbers guarantees the distribution of the output conditioned on the input is
Gaussian. As the evolution is an affine transformation of the initial
predictions, the predictions remain Gaussian throughout.

$\displaystyle p(z|x)$
$\displaystyle\sim\mathcal{N}(\mu(x,\tau),\Sigma(x,\tau))$ (1.10)
$\displaystyle\mu(x,\tau)$
$\displaystyle=\Theta(x,\mathcal{X})\Theta^{-1}\left(I-e^{-\tau\Theta}\right)\mathcal{Y}$
(1.11) $\displaystyle\Sigma(x,\tau)$
$\displaystyle=\mathcal{K}(x,x)+\Theta(x,\mathcal{X})\Theta^{-1}\left(I-e^{-\tau\Theta}\right)\left(\mathcal{K}\Theta^{-1}\left(I-e^{-\tau\Theta}\right)\Theta(\mathcal{X},x)-2\mathcal{K}(\mathcal{X},x)\right).$
(1.12)

Here, $\mathcal{K}$ denotes another kernel, the _neural network gaussian
process_ kernel (NNGP). For a finite width network, the NNGP corresponds to
the expected gram matrix of the output- $\mathbb{E}\left[zz^{T}\right]$. In
the infinite width limit, this concentrates to a fixed value. Just as for the
NTK, the NNGP can be tractably computed (lee2019wide) and should be considered
only a function of the neural network architecture. These results, which give
us a conditional posterior distribution for each time step, enable us to
create a powerful model family to investigate DNNs. These tractable
distributions can be used to derive many intractable information-theoretic
quantities.

###  1.6 The impact of the work

In summary, the IB theory offers a new perspective on DNNs and their
capability to learn meaningful representations. This theory suggests studying
the system by grouping each layer in the network into two information pairs,
one with input and another with output: $(I(X;T_{\ell}),I(T_{\ell};Y))$.

Following this study, which provided a theoretical foundation for
understanding deep learning, several studies have offered further explorations
of DNNs using information theory tools. We now discuss some of these works and
whether they support or challenge our claims. A partial list includes
achille2018emergence; saxe2019information; yu2020understanding;
cheng2018evaluating; goldfeld2018estimating; wickstrom2019information;
amjad2019learning; goldfeld2020convergence; cvitkovic2019minimal.

Following this study, several researchers have analyzed the information plane
using different estimation mechanisms in various DNN datasets, architectures,
and activation functions. They found conflicting results: The authors of
saxe2019information did not observe compression in DNNs with ReLU activation
functions. However, according to chelombiev2019adaptive, compression can occur
earlier in training or later in training, depending on how the DNN parameters
are initialized. goldfeld2018estimating developed a noisy DNNs framework with
a rigorous estimator for $I(X;T)$. Using this estimator, they observed the
input’s compression in various models. The authors related the noisy DNN to an
information-theoretic communication problem, demonstrating that compression is
driven by the progressive clustering of inputs belonging to the same class.
The study clarified the geometric effects of mutual information compression
during training. Other methods that have been proposed for estimating mutual
information in DNNs are generative decoder networks (darlow2020information;
nash2018inverting), the mutual information neural estimator (MINE)
(elad2019direct), ensemble dependency graph estimator (EDGE)
(noshad2018scalable), adaptive approaches for density estimation
(chelombiev2019adaptive), and noisy sounding entropy estimator
(goldfeld2018estimating), and more. For a detailed review of these works, see
geiger2020information.

In another line of research, our idea was used to analyze networks using
information with the weights (achille2018emergence; achille2018critical;
achille2018information). It has been demonstrated that flat minima, which have
better generalization properties, bound the information with the weights,
which bounds the information with the activations. In achille2018critical,
they used Fisher information on the weights to illustrate the two stages of
learning that DNNs go through: increasing the information followed by
progressively decreasing the information. By compressing the information with
the weights, the network also compresses the information with the activations.

As shown in achille2018information, minimizing a stochastic network using an
approximation of the compression term as a regularizer is equivalent to
minimizing cross-entropy over deterministic DNNs with multiplicative noise
(information dropout). In addition, they found that Bernoulli noise is a
special case that leads to the dropout method. elad2019direct shows that the
binned information can be interpreted as a weight decay penalty, which is
typical of DNN training.

Furthermore, many competing information objectives have been proposed for
training DNNs based on the IB principle, which can be difficult to compute for
high dimensions. kirsch2020unpacking examined these quantities and compared,
unified, and related them to surrogate objectives that are more easily
optimized. The unifying view provided insights into IB training limitations
and demonstrated how to avoid the pathological behavior of IB objectives. In
addition, they discussed how simple objectives, based on this intuition, could
capture many desirable features of IB algorithms while also scaling to complex
deep learning problems. Furthermore, they explored how applying practical
constraints to a neural network’s expressivity can provide new insights into
measuring compression and possibly improving regularization.

###  1.7 Overview and main contributions

The purpose of our thesis is to provide an explanation of deep learning by
using an information-theoretic framework, supported by empirical evidence, and
overcoming some of the shortcomings of IB. We have outlined the major results
and contributions of the thesis in three sections below:

  * •

Part 1 – Opening the Black Box of Deep Neural Networks – The first
contribution of this thesis is a presentation of an information-based theory
for DNNs. Combining two papers shows that DNNs can learn to optimize the
mutual information that each layer preserves on the input and output
variables, resulting in a trade-off between compression and prediction. We
present a theoretical and numerical analysis of DNNs in the information plane
and explain how the SGD algorithm follows the information bottleneck trade-off
principle. SGD achieves this optimal bound by compressing each layer to a
maximum conditional entropy state subject to the constraints of the labels’
information. Moreover, we find that the network’s training is characterized by
a rapid increase in the mutual information between the layers and the target
label, followed by a slower decrease in the mutual information between the
layers and the input variable. By introducing a new generalization error
bound, which is exponential in the input representation compression, we
propose a novel analytic bound on the mutual information between successive
layers in the network. Combining these with the empirical case study enables a
comprehensive understanding of optimization dynamics, SGD training properties,
and deep architectures’ computational benefits.

  * •

Part 2 – Information in Infinite Ensembles of Infinitely-wide neural networks
– As previously mentioned, it is often challenging to measure information-
theoretic quantities. We developed tractable computations for a wide range of
information-theoretic quantities using the NTK framework. These results are
used to investigate the critical quantities that correlate with
generalization, dynamics, and optimality during the learning process in high-
dimensional networks.

  * •

Part 3 – The Dual Information Bottleneck – As mentioned before, the IB
framework has several known drawbacks, including that it is not optimal for
training with finite samples and that it does not preserve the problem
structure. We present the dualIB, a framework for addressing some of these
shortcomings. By switching the order between the representation decoder and
data in the IB’s distortion function, the optimal decoding becomes the
geometric mean of input points instead of the arithmetic mean. Whenever the
data can be modeled in a parametric form, this conversion preserves its
structure and, thus, the original properties of the data. Furthermore, the
prediction accuracy is improved by optimizing the mean prediction error
exponent for each data size. By analyzing the framework’s structure, we show
how to solve this new representation learning formulation. A variational
formulation of the dualIB for DNNs, (VdualIB) is presented to address large-
scale problems. We examine its properties using real-world datasets and
compare them to the original IB.

## Opening the Black Box of Deep
Neural Networks via Information

Unpublished
Ravid Shwartz-Ziv and Naftali Tishby (2018)

Opening the Black Box of Deep Neural Networks via Information
Ravid Shwartz-Ziv 1 Naftali Tishby1,2

1 The Edmond and Lilly Safra Center for Brain Sciences, The Hebrew University,

Jerusalem, Israel.

2 School of Computer Science and Engineering,

The Hebrew University,

Jerusalem, Israel.

Abstract

Despite their great success, there is still no comprehensive theoretical
understanding of learning with Deep Neural Networks (DNNs) or their inner
organization. Previous work suggested analyzing DNNs in the Information-Plane;
the plane of the mutual information values that each layer preserves on the
input and output variables. They suggested that the network’s goal is to
optimize the Information Bottleneck (IB) trade-off between compression and
prediction, successively, for each layer. In this work, we demonstrate the
effectiveness of the information-plane visualization of DNNs. We first show
that the stochastic gradient descent (SGD) epochs have two distinct phases:
fast empirical error minimization followed by slow representation compression
for each layer. We then argue that the DNN layers end up very close to the IB
theoretical bound and present a new argument for the hidden layers’
computational benefit.

### Introduction

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 (DBLP:journals/corr/abs-1303-5778;
DBLP:journals/corr/ZhangL15; DBLP:journals/corr/abs-1207-0580;
DBLP:journals/corr/HeZRS15; natureDeepLeraning).

However, despite their success, there is still little understanding of their
internal organization or optimization process. They are often seen as
mysterious ”black boxes” (probes2016).

The authors in TishbyZ15 pointed out that layered neural networks’
representations of input layers form a Markov chain. They suggested studying
these in the information-plane \- The plane of the mutual information values
of any other variable with the input variable $X$ and the desired output
variable $Y$ (Figure 1.20). The rationale for this analysis was based on the
mutual information’s invariance to invertible re-parameterization and the data
processing inequalities (DPI) (Cover:2006) along the Markov chain of the
layers. Moreover, they suggested that optimized DNNs layers should approach
the Information Bottleneck (IB) bound (DBLP:journals/corr/Tishby1999) of the
optimally achievable representations of the input $X$.

Figure 1.4: The DNN layers form a Markov chain of successive internal
representations of the input. Any representation, $T$, is defined through an
encoder, $P(T|X)$, and a decoder $P(\hat{Y}|T)$, and can be quantified by its
_information-plane_ coordinates: $I(X;T)$ and $I(T;Y)$. The IB bound
characterizes the optimal representations, which maximally compress the input
$X$, for a given mutual information on the desired output $Y$.

In this paper, we extend their work and demonstrate the effectiveness of
visualizing DNNs in the information-plane to understand better the training
dynamics, learning processes, and internal representations of deep learning.

Our analysis reveals that the SGD optimization, commonly used in deep
networks, has two different and distinct phases: empirical error minimization
(ERM) and representation compression. Each of these phases displays a very
different signal-to-noise ratio of the stochastic gradients. During the ERM
phase, gradient norms are much larger than their stochastic fluctuations,
leading to a sharp increase in the mutual information on the label variable
$Y$. At the compression phase, the errors fluctuate much more than their
means, causing the weights to change much like Weiner processes, or random
diffusion, with a small influence of error gradients. In this phase, the input
variable $X$ undergoes slow representation compression or reduction of the
mutual information.

In our experiments, most of the optimization iterations are spent on
compressing the internal representations under the training error constraint.
This compression occurs by the SGD without any other explicit regularization
or sparsity imposed. We suspect that this helps avoid overfitting in deep
networks. This observation also suggests that many (exponential in the number
of weights) different randomized networks have essentially optimal
performance. Hence, the interpretation of a single neuron (or weight) in the
layers is practically meaningless.

Then we show that the optimized layers lay on or relatively close to the
optimal IB bound for large enough training samples, resulting in a self-
consistent relationship between each layer’s encoder and decoder distributions
(Figure 1.20). The hidden layers in the optimized model converge along
particular lines in the information-plane and move up as the training sample
size increases. In addition to this, the diffusive nature of the SGD dynamics
explains the computational benefit of the hidden layers.

### Information Theory of Deep Learning

In supervised learning, we are interested in good representations, $T(X)$, of
the input patterns $x\in X$, which enable good predictions of the label $y\in
Y$. Moreover, we want to efficiently learn such representations from an
empirical sample of the (unknown) joint distribution $P(X,Y)$, in a manner
that provides good generalization.

DNNs generate a Markov chain of such representations, the hidden layers, by
minimizing the empirical error over the network’s weights, layer by layer.
This optimization occurs via SGD, using a noisy estimate of the empirical
error gradient at each weight through the backpropagation algorithm
(rumelhart1986learning).

Our first important insight is to treat the whole layer $T$, as a single
random variable, characterized by its encoder, $P(T|X)$, and decoder, $P(Y|T)$
distributions. As we are only interested in the information flowing through
the network, invertible transformations of the representations that preserve
information generate equivalent representations even if the individual neurons
encode entirely different input features. For this reason, we quantify the
representations by two numbers, or order parameters, that are invariant to any
invertible re-parameterization of $T$, the mutual information of $T$ with the
input $X$, $I(X;T)$, and the desired output $Y$, $I(T;Y)$.

Next, the layers’ quality is quantified by comparing them to the information-
theoretic optimal representation - the IB representations. Furthermore, we
explore how the SGD can be used to obtain these optimal representations in
DNNs.

#### Mutual information

Given any two random variables, $X$ and $Y$, with a joint distribution
$p(x,y)$, their mutual information is defined as:

$\displaystyle I(X;Y)$ $\displaystyle=D_{KL}[p(x,y)||p(x)p(y)]$ (1.13)
$\displaystyle=\sum_{x\in X,y\in
Y}p(x,y)\log\left(\frac{p\left(x,y\right)}{p\left(x\right)p\left(y\right)}\right)$
(1.14) $\displaystyle=H(X)-H(X|Y)\leavevmode\nobreak\ ,$ (1.15)

where $D_{KL}[p||q]$ is the Kullback-Liebler divergence of the distributions
$p$ and $q$, and $H(X)$ and $H(X|Y)$ are the entropy and conditional entropy
of $X$ and $Y$, respectively.

The mutual information quantifies the number of relevant bits that the input
variable $X$ contains about the label $Y$, on average. The optimal learning
problem can be cast as the construction of an optimal encoder of that relevant
information via an efficient representation - a minimal sufficient statistic
of $X$ with respect to $Y$. A minimal sufficient statistic can enable the
decoding of the relevant information with the smallest number of binary
questions (on average); i.e., an optimal code. The connection between mutual
information and minimal sufficient statistics is discussed in the next
section.

Among the characteristics of mutual information, two stand out particularly in
relation to DNNs. The first is its invariance to invertible transformations:

$I\left(X;Y\right)=I\left(\psi(X);\phi(Y))\right)$ (1.16)

for any invertible functions $\phi$ and $\psi$.

The second is the DPI – (Cover:2006) For any three variables that form a
Markov chain $X\rightarrow Y\rightarrow Z$,

$I\left(X;Y\right)\geq I(X;Z)\leavevmode\nobreak\ .$

#### The information-plane

Any representation variable, $T$, defined as a (possibly stochastic) map of
the input $X$, is characterized by its joint distributions with $X$ and $Y$,
or by its encoder and decoder distributions, $P(T|X)$ and $P(Y|T)$,
respectively. Given $P(X;Y)$, $T$ is uniquely mapped to a point in the
information-plane with coordinates $\left(I(X;T),I(T;Y)\right)$. When applied
to the Markov chain of a K-layers DNN, with $T_{i}$ denoting the $i^{th}$
hidden layer as a single multivariate variable (Figure 1.20), the layers are
mapped to $K$ monotonic connected points in the plane. Therefore, a unique
information path which satisfies the following DPI chains:

$\displaystyle I(X;Y)$ $\displaystyle\geq I(T_{1};Y)\geq
I(T_{2};Y)\geq...I(T_{k};Y)\geq I(\hat{Y};Y)$ $\displaystyle H(X)$
$\displaystyle\geq I(X;T_{1})\geq I(X;T_{2})\geq...I(X;T_{k})\geq
I(X;\hat{Y}).$

Layers related by invertible re-parametrization appear at the same point,
meaning that each information path in the plane corresponds to a multitude of
different DNNs, possibly corresponding to very different architectures.

#### The Information Bottleneck optimal bound

What characterizes the optimal representations of $X$ w.r.t. $Y$? The
classical notion of minimal sufficient statistics provides good candidates for
optimal representations. Sufficient statistics, in our context, are maps or
partitions of $X$, $S(X)$, capturing all the information that $X$ has on $Y$.
Namely, $I(S(X);Y)=I(X;Y)$ (Cover:2006).

Minimal sufficient statistics, $T(X)$, are the simplest sufficient statistics
and induce the coarsest sufficient partition on $X$. Thus, they are functions
of any other sufficient statistic. A simple way of formulating this is through
the Markov chain: $Y\rightarrow X\rightarrow S(X)\rightarrow T(X)$, which
should hold for a minimal sufficient statistics $T(X)$ with any other
sufficient statistics $S(X)$. Using DPI, we can cast it into a constrained
optimization problem:

$T(X)=\arg\min_{S(X):I(S(X);Y)=I(X;Y)}I(S(X);X)\leavevmode\nobreak\ .$

Since exact minimal sufficient statistics only exist for special distributions
(i.e., exponential families), DBLP:journals/corr/Tishby1999 relaxed this
optimization problem by first allowing the map to be stochastic, defined as an
encoder $P(T|X)$, and then, by enabling the map to capture _as much as
possible_ of $I(X;Y)$, not necessarily all of it.

This leads to the IB trade off (DBLP:journals/corr/Tishby1999), which provides
a computational framework for finding approximate minimal sufficient
statistics, or the optimal trade-off between compression of $X$ and prediction
of $Y$. In that sense, efficient representations are approximate minimal
sufficient statistics.

If we define $t\in T$ as the compressed representations of $x\in X$, the
representation of $x$ is now defined by the mapping $p\left(t|x\right)$. This
IB trade-off is formulated by the following optimization problem, carried
independently for the distributions, $p(t|x),p(t),p(y|t)$, with the Markov
chain: $Y\rightarrow X\rightarrow T$,

$\min_{p\left(t|x\right),p\left(y|t\right),p\left(t\right)}\left\\{I\left(X;T\right)-\beta
I\left(T;Y\right)\right\\}\leavevmode\nobreak\ .$ (1.17)

The Lagrange multiplier $\beta$ determines the level of relevant information
captured by the representation $T$, $I(T;Y)$, which is bounding the error in
the label prediction from this representation. The local optimal solution to
this problem is given by three self-consistent equations, the IB equations:

$\begin{cases}p\left(t|x\right)=\frac{p\left(t\right)}{Z\left(x;\beta\right)}\exp\left(-\beta
D_{KL}\left[p\left(y|x\right)\parallel p\left(y|t\right)\right]\right)\\\
p\left(t\right)=\sum_{x}p\left(t|x\right)p\left(x\right)\\\
p\left(y|t\right)=\sum_{x}p\left(y|x\right)p\left(x|t\right)\leavevmode\nobreak\
,\end{cases}$ (1.18)

where $Z\left(x;\beta\right)$ is the normalization function. These equations
must be satisfied along the _information curve_ which is a monotonic concave
line that separates the achievable and unachievable regions in the
information-plane. For smooth $P(X,Y)$ distributions; i.e., when $Y$ is not a
completely deterministic function of $X$, the information curve is strictly
concave with a unique slope, $\beta^{-1}$, at every point, and a finite slope
at the origin. In these cases, $\beta$ determines a single point on the
information curve with specified _encoder_ , $P^{\beta}(T|X)$, and _decoder_ ,
$P^{\beta}(Y|T)$, distributions that are related through Eq.(1.18).

#### Visualizing DNNs in the information-plane

As proposed by TishbyZ15, we study the _information paths_ of DNNs in the
information-plane. It is possible to do so when the underlying distribution,
$P(X,Y)$, is known and the encoder and decoder distributions, $P(T|X)$ and
$P(Y|T)$, can be derived directly. In ”real-world” problems, these
distributions and mutual information values should be estimated from samples
or other modeling assumptions. We use two order parameters, $I(T;X)$ and
$I(T;Y)$, to visualize and compare different network architectures in terms of
their efficiency in preserving the relevant information in $P(X;Y)$.

By visualizing the paths of different networks in the information-plane, we
explore the following fundamental issues:

  1. 1.

The SGD layer’s dynamics in the information-plane.

  2. 2.

The effect of the training sample size on the layers.

  3. 3.

The benefit of the hidden layers.

  4. 4.

The final location in the information-plane of the hidden layers.

  5. 5.

The optimality of the layers’ representation.

### Experiments

This section is organized as follows; First, we describe the experimental
settings. Next, we discuss the results of our experiments, including the
dynamics of the optimization process in the information-plane, the stochastic
gradients, and the computational benefit of the hidden layers. In the last
part, we present the layers’ optimality and their evolution with the training
size.

#### Experimental setup

The numerical studies in this paper explore fully connected feed-forward
neural networks with no further architecture constraints. The activation
function of all hidden layers is the hyperbolic tangent function. For the
final layer, we use a sigmoidal function. The networks train using SGD and the
cross-entropy loss function (with no explicit regularization). Unless
otherwise noted, the DNNs use up to seven fully connected hidden layers, with
widths of $12-10-7-5-4-3-2$ neurons (see Figure LABEL:fig:gradients). In our
results below, layer one is the hidden layer closest to the input and the
highest is the output layer.

To simplify our analysis, the tasks were chosen as binary decision rules,
which are invariant under $O(3)$ rotations of the sphere. We define the input
$X$ to be $12$ binary inputs representing uniformly distributed points on a
$2D$ sphere (for other, non-symmetric rules, see Supplementary material). The
$4096$ different patterns of the input variable $X$ are divided into $64$
disjoint orbits of the rotation group. These orbits form a minimal sufficient
statistics for spherically symmetric rules (Kazhdan2003).

Given a function $f$ defined on the sphere, we can obtain a rotation and
reflection invariant representation $\psi\left(f\right)$ by computing the
spherical harmonic decomposition of the function.

$f\left(\theta,\phi\right)=\sum_{l\geq{0}}\sum_{m=-l}^{l}{a_{l}^{m}Y_{l}^{m}\left(\theta,\phi\right)}$

and calculate the energy ($L_{2}$ norms) of the frequency components.

$\psi\left(f\right)=\sqrt{\|a_{0}\|^{2}+\|a_{1}\|^{2}\dots}$ (1.19)

We refer the reader to Kazhdan2003 for a good exposition on the above. To
generate the input-output distribution, $P(X,Y)$, we consider spherically
symmetric real valued function of the pattern $f(x)$ minus a threshold,
$\theta$, and apply a sigmoidal function, $\Omega(u)=1/(1+\exp(-\gamma u))$:

$p(y=1|x)=\Omega\left(\psi\left(f_{x}\right)-\theta\right))\leavevmode\nobreak\
.$ (1.20)

The threshold $\theta$ was selected such that
$p(y=1)=\sum_{x}p(y=1|x)p(x)\approx 0.5$, with uniform $p(x)$. The sigmoidal
gain $\gamma$ was high enough to keep the mutual information $I(X;Y)\approx
0.99$ bits.

##### Estimating the mutual information of the layers

As mentioned above, we model each layer in the network as a single variable
$T_{i},1\leq i\leq K$ , and calculate its mutual information with the input
and the labels.

To calculate the mutual information of the networks’ layers with the input and
output variables, we binned the neuron’s $arctan$ output activation into $30$
equal intervals between $-1$ and $1$. These discretized values for each neuron
in the layer, $t\in T_{i}$, are used to directly calculate the joint
distributions, over the $4096$ equally likely input patterns $x\in X$,
$P(T_{i},X)$ and $P(T_{i},Y)=\sum_{x}P(x,Y)P(T_{i}|x)$, using the Markov chain
$Y\rightarrow X\rightarrow T_{i}$ for every hidden layer. Using the above
discrete joint distributions, we calculate the decoder mutual information,
$I(Y;T_{i})$, and the encoder mutual information, $I(T_{i};X)$, for each
hidden layer. Note that $I(T_{i};Y)$ is calculate with the full data
distribution; thus, it corresponds to the generalization error.

We repeat these calculations with $50$ different randomized initialization of
the network’s weights and different random selections of the training samples,
randomly distributed according to the rule $P(X,Y)$ in Eq.(1.20).

#### The dynamics of the optimization process

To understand the network’s SGD optimization dynamics, we evaluate and
visualize pairs of $I(X;T_{i})$ and $I(T_{i};Y)$ for each layer along the
learning process. We repeat this process for $50$ different randomized
initializations with different randomized training samples. Figure 1.22
depicts the layers (each one in a different color) of all the $50$ networks,
trained with a randomized $85$ percents of the input patterns, in the
information-plane, at various times during the training.

As can be seen, the deeper layers of the randomly-initialized network do not
preserve the relevant information at the beginning of the optimization, and
$I(T;Y)$ decreases sharply along the path. During the SGD optimization, the
layers first increase $I(T;Y)$, then significantly decrease $I(X;T)$ –
compressing the representation. One striking observation is that the different
randomized networks’ layers follow similar paths through the optimization
process and eventually converge to nearby points in the information-plane. The
randomized networks are thus averaged over, and the average layer trajectory
plot is shown in Figure 1.8.

Figure 1.6: Snapshots of layers (different colors) of 50 randomized networks
during the training process in the information-plane: left \- At the
initialization time; center \- After 400 epochs; right \- After 9000 epochs.

Figure 1.8: The evolution of layers during the learning process - the
information-plane. Left \- Paths of layers trained with only 5% of the
patterns. Right \- Paths of the layers, trained with 85% of the input
patterns. The line color indicates the number of epochs. There are 6 points
for each path’s different hidden layers, averaged over all 50 randomized
networks. The layer with the smallest $I(X;T)$ is the output layer, and the
one with the highest $I(X;T)$ is the first hidden layer. The green paths
correspond to the SGD phase transition grey line on Figure LABEL:fig:gradients

The graph on the left shows those same trajectories when trained with $85$
percent of all patterns, whereas on the right, the same trajectories when
trained with only $5$ percent. Note that the mutual information is calculated
with the full rule distribution. Thus, $I(T;Y)$ corresponds to the test or
generalization error. In each case, the two optimization phases are visible.
During the fast - ERM phase, which lasts a few hundred epochs, the layers
increase the information on the labels (increase $I(T;Y)$). However, the
layers’ information on the input, $I(X;T)$, decreases in the second phase of
training, resulting in loss of irrelevant information until converging (yellow
points). We call this phase the _representation compression_ phase. Because of
the cross-entropy loss approximate $I(T;Y)$ up to a constant (see
shwartz2018representation), the increase of $I(T;Y)$ in the ERM phase is
expected. However, the compression phase is surprising. There is no explicit
regularization that could simplify the representations, such as $L1$
regularization, and there is no sparsification or norm reduction of the
weights (see supplementary).

While both the small ($5\%$) and large ($85\%$) training sample sizes exhibit
the same ERM phase, the compression phase drastically reduces the layers’
label information for a small number of examples. However, with large sample
sizes, the layers’ label information increases. Those results seem very much
to be caused by overfitting the small sample noise, a problem that can be
eliminated by early stopping methods (Larochelle:2009:EST:1577069.1577070).
This overfitting is mainly the consequence of the compression phase. It
simplifies the layers’ representations and loses relevant information.
Understanding what determines the convergence points of the layers in the
information-plane for different training data sizes is an interesting
theoretical goal.

(b)

(d)

Figure 1.10:  The Two Phases of SGD Optimization

#### The two phases of SGD optimization

By examining the stochastic gradients’ behavior along the epochs, a better
understanding of the ERM and the representation-compression phases can be
gained. For each layer, we look at the mean and standard deviations of the
weights’ stochastic gradients (in the sample batches). Namely,
$M_{i}=\left\|\braket{\frac{\partial L}{\partial W_{k}}}\right\|_{F}$ and
$S_{i}=\left\|\text{STD}\left(\frac{\partial L}{\partial
W_{k}}\right)\right\|_{F},$ where $\braket{\cdot}$ and $\text{STD}(\cdot)$ are
the mean and the element-wise standard deviation respectively, and
$\left\|\cdot\right\|_{F}$ denotes the Frobenius norm. Figure
LABEL:fig:gradients shows the mean and standard deviation of the weights’
gradients for one layer in our network, as a function of the iterations (in
log-log scale). As can be seen, there is a transition between two distinct
phases (the vertical line). The phases are defined by the ratio between the
means of the gradients and their standard deviations. We refer to this ratio
as the signal-to-noise ratio (SNR). The first phase is an _drift phase_ , when
the gradient means are much larger than the standard deviations, indicating
relatively small gradient stochasticity (high SNR). Gradient means are very
small compared to batch-to-batch fluctuations (low SNR) in the second phase,
which we call the _diffusion phase_. This transition is generally expected
when the empirical error becomes saturated, and SGD is dominated by its
fluctuations (bertsekas2011incremental). We claim that these distinct SGD
phases (grey line in Figure LABEL:fig:gradients), correspond and explain the
ERM and compression phases we observe in the information plane (marked green
paths in Figure 1.8).

This dynamic phase transition occurs in the same number of iterations as in
the layers’ trajectories in the information plane. To relate the transition
phase in the information plane to the gradients, we examine the mini-batch
size effect on them. For each mini-batch size, we find both the starting point
of the information compression and the gradient phase transition (the
iteration where the derivative of the SNR is maximal). This is given in Figure
LABEL:fig:gradeints_batchs1. The $X$-axis is the iteration where compression
is started, and $Y$-axis is the iteration at which a phase transition occurs
in the gradient. There is a linear trend between the two.

In the drift phase, $I(T;Y)$ increases for every layer, as it rapidly reduces
the empirical error. Conversely, the diffusion phase adds random noise to the
weights, which evolve like Wiener processes under the training error or label
information constraint. A Focker-Planck equation can describe such diffusion
processes (see, e.g., risken1989fokker), whose stationary distribution
maximizes the entropy of the distribution of the weight under the training
error constraint. That, in turn, maximizes the conditional entropy,
$H(X|T_{i})$, or minimizes the mutual information
$I(X;T_{i})=H(X)-H(X|T_{i})$, because the input entropy, $H(X)$ is constant.
This entropy maximization by additive noise, also known as stochastic
relaxation, is constrained by the empirical error or equivalently (for small
errors) by $I(T;Y)$.

It remains unclear why different hidden layers converge to different points in
the information-plane. Our analysis suggests that different layers have
different noise levels in the gradients during the compression phase,
explaining why they end up in different maximum entropy distributions.
However, the gradient noises appear to vary and eventually decrease when the
layers converge, suggesting that the convergence points are related to the
_critical slowing down_ of stochastic relaxation near phase transitions on the
IB curve.

An interesting outcome of _compression by diffusion_ is the randomized nature
of the network’s final weights. The correlations between the in-weights of
different neurons in the same layer, which converge to essentially the same
point in the plane, are very small. This indicates that there are many
different networks with essentially optimal performance, and attempts to
interpret single weights or even single neurons in such networks are
meaningless.

#### The benefit of the hidden layers

(b)

(d)

Figure 1.12: The computational benefit of the layers

What is the benefit of the hidden layers? This question is one of the
fundamentals of deep learning. For this reason, we train networks with a
different number of layers ($1-5$) and determine the minimum iteration for
which the network converges. As before, we repeat each training $50$ times
with randomized initial weights and training samples. Figure 1.34 shows the
information-plane paths for these six architectures during the training
epochs, while Figure 1.11(d) shows the iteration number that the different
networks reached 98% accuracy.

There are several important results from this experiment:

  1. 1.

_The addition of hidden layers dramatically reduces the number of training
iterations required for good generalization._ As more layers are added, the
convergence time decreases by a factor of $k^{\frac{1}{\alpha}}$ where
$alpha=0.55$.

  2. 2.

_When starting from previously compressed layers, each compression phase will
be shorter._ By comparing the time to good generalization with four hidden
layers and five hidden layers, we can see that convergence with four layers is
much slower than with five or six hidden layers, where it takes half the time
to reach the endpoints.

  3. 3.

_The compression rate is faster for the deeper (narrower) layers, which are
located closer to the output._ While in the drift phase, the lower layers move
first (as a result of DPI), in the diffusion phase, the top layers compress
first and pull the lower ones after them. Adding more layers seems to
accelerate the compression.

##### The IB optimality of the layers

Finally, to quantify the IB optimality of the layers, we test whether the
converged layers satisfy the encoder-decoder relations of Eq. (1.18), for some
value of the Lagrange multiplier $\beta$. With the encoder and decoder
distributions based on quantized values of layer neurons,
$p_{i}\left(t|x\right)$ and $p_{i}\left(y|t\right)$, respectively, we compute
the information values for each converged layer.

To test the IB optimality of the layers, we calculate the optimal IB encoder,
$p_{i,\beta}^{IB}\left(t|x\right)$ using the $i^{th}$ layer decoder,
$p_{i}\left(y|t\right)$, through Eq.(1.18). This can be done for any value of
$\beta$, with the known $P(X,Y)$. Then, we find the optimal $\beta_{i}$ for
each layer, by minimizing the average KL divergence between the IB and the
layer’s encoders,

$\beta_{i}^{\star}=\arg\min_{\beta}\mathbb{E}_{x}{D_{KL}\left[p_{i}\left(t|x\right)||p_{\beta}^{IB}\left(t|x\right)\right]}\leavevmode\nobreak\
.$

In figure 1.14 we see the information plotted over the layers together with
the IB curve (blue line). The five empirical layers (trained with SGD) lie
remarkably close to the theoretical IB limit. Furthermore, the slope of the
curve, $\beta^{-1}$, matches their estimated optimal $\beta_{i}^{\star}$.

Figure 1.14: The DNN layers are fixed-points of the IB equations. The error
bars represent standard error measures for $N=50$. In each line, there are $5$
points for the different layers. For each point, $\beta$ is the optimal value
tof that layer.

Hence, the DNN layers’ encoder-decoder distributions satisfy the IB self-
consistent equations within our numerical precision, decreasing $\beta$ as we
go deeper in the network. The error bars are calculated over $50$ randomized
networks. As predicted by the IB equations, near the information curve $\Delta
I_{Y}\sim\beta^{-1}\Delta I_{X}$.

##### The evolution of the layers with training size

Another problem in machine learning, which we just briefly discuss in this
paper, is the importance of the training data size (cho2015much). It is useful
to visualize the hidden layers’ converged locations for different training
data sizes in the information-plane (Figure 1.16).

Figure 1.16: The effects of different training data sizes on the layers in the
information-plane. Each line represents a converged network that had different
training data sizes.

As before, we train the network using six hidden layers, with different sample
sizes ranging from 3 percent to 85 percent of the data. As expected, the
layer’s true label information, $I(T;Y)$ pushed up and gets closer to the
theoretical IB bound on the rule distribution with increasing training size.

Despite the randomizations, the converged layers for different training sizes
line up on a smooth line with remarkable regularity for each layer. We claim
that the layers converge to specific points on the finite sample information
curves, which can be calculated using the IB self-consistent equations (Eq.
(1.18)), with the decoder replaced by the empirical distribution. This finite
sample IB bound also explains the bounding shape on the left of Figure 1.8.
Since the IB information curves are convex for any distribution, the layers
converge to a convex curve in the plane even with very small samples.

However, the layers’ training size effect is different for $I(T;Y)$ and
$I(X;T)$. The training size hardly changes the information in the lower layers
since even random weights keep most of the mutual information on both $X$ and
$Y$. However, for deeper layers, the network learns to preserve the relevant
information about $Y$ and compress the irrelevant information in $X$. More
details on $X$ are relevant for $Y$ with a larger training set, and $I(X;T)$
increases in the middle layers.

### Related Work

Recently, the IB theory of deep learning has received much attention,
including criticism of its rationale. Follow-up works attempt to address
several points:

##### Information compression

saxe2018information constructed several experiments to explore and refute the
IB interpretation. They claim that the compression phase is an artifact of the
quantization used to approximate $I(X;T)$ and the activation function
(saturating nonlinearity). They observed no compression for the nonsaturating
ReLU activation function.

Getting a reasonable estimate of mutual information between joint
distributions in high-dimensional contexts is one of the main challenges in
applying information-theoretic measures to real-world data. This problem has
been extensively studied over the years (e.g.,
Paninski:2003:EEM:795523.795524), showing that there is no “efficient”
solution when the dimension of the problem is large and known approximations
do not scale well with dimension and sample size (gao2015efficient).

Several recent works have attempted to develop novel and efficient methods for
estimating mutual information for DNNs. One line of works uses a generative
decoder network (PixelCNN++) to estimate a lower bound on the mutual
information (darlow2020information; nash2018inverting). In
darlow2020information, the authors observed compression in the hidden layers
during learning on the ImageNet dataset, using both ResNet and autoencoder
architectures. This work confirms our two-stage learning for both
classification and autoencoding tasks, characterized by (1) an initial short
increase phase (2) following by a longer decrease in the mutual information
with the input. Further, they observe that when the information is maximally
compressed, the input images’ class-irrelevant features are discarded; Namely,
conditionally generated samples vary more while retaining information relevant
to classification. nash2018inverting reproduced our work using a similar
approach. They observed a compression phase when using a convolution network
with ReLU activation on the MNIST dataset. A two-phase behavior including a
compression phase on the MNIST dataset with both fully-connected networks and
convolutional networks was also reported by Noshad & Alfred
(noshad2018scalable). The authors introduced a new mutual information
estimator, the ensemble dependency graph estimator (EDGE), which combines
locality-sensitive hashing with dependency graphs and ensemble bias-reduction
methods. The authors of chelombiev2019adaptive proposed adaptive approaches to
estimating mutual information. These adaptive approaches compared the behavior
of different activation functions and observed compression in DNNs with
nonsaturating activation functions. It was observed that unlike saturating
activation functions, compression does not always happen, and it is sensitive
to initialization. They also observed that DNNs with L2 regularization
strongly compress information.

In 2018Estimating, the authors propose a new theoretical noisy entropy
estimator to estimate mutual information. With both ReLU and linear
activations, they observed the compression phase on our dataset and the MNIST
dataset and related this compression behavior to geometric clustering. They
also found that the behavior of $I(X;T)$ is strongly influenced by the
”binning size,” which is used for estimating the mutual information.

In elad2018effectiveness, the authors utilized the mutual information neural
estimator (MINE) (Belghazi2018MutualIN), which estimates the KL divergence
through the maximization of the dual representation of Donsker & Varadhan
(donsker1975asymptotic). They showed that for the MNIST dataset with ReLU
activation, the compression phase did not appear for “vanilla” cross-entropy
training but did appear for training with weight decay regularization.

The authors in achille2017critical used Fisher information on the weights to
demonstrate a two-phase learning process, involving an initial short increase,
followed by a longer phase of decreasing information. Their paper described
the reduction in information in the weights as implying a reduction in
information in the activation. An additional confirmation on the two-phase
behavior of DNNs can found in li2017convergence, who investigated shallow
neural networks with residual connections and normal input distribution and
showed that the SGD has two phases; (1) search and (2) convergence.
Additionally, in dieuleveut2017bridging they presented transient and
stationary phases by looking at the inner product between successive mini-
batch gradients in the network.

##### Generalization and compression

Another claim ofsaxe2018information is that the generalization does not
require compression. They constructed a deep linear network toy example to
illustrate generalization without compression.

The authors in chelombiev2019adaptive found that generalization accuracy was
positively correlated with the degree of compression of the last layer. The
connection of the generalization to compression is also discussed in
shwartz2018representation. They showed that the generalization error depends
exponentially on $I(X;T)$, once $I(T;X)$ becomes smaller than $\log 2n$ \- the
query sample complexity. Moreover, They showed that M bits of compression of
$X$ are equivalent to an exponential factor of $2^{M}$ training examples.
Furthermore, achille2017emergence proved that flat minima, which have better
generalization properties, bound information with the weights, and the
information in the weights bound information in the activations.

##### Information in deterministic networks

Several works (saxe2018information; amjad2018not; 2018Estimating), state that
the term $I(X;T)$ in the IB functional is theoretically either infinite or a
constant for deterministic DNNs with continuous input. Thus, they wonder about
the meaning of measuring it.

This problem was addressed in the literature by (1) training stochastic DNNs,
which ensure the information is finite, and by (2) using a tractable
variational approximation of the mutual information (alemi2016deep;
kolchinsky2017estimating; chalk2016relevant; achille2018information;
belghazi2018mine). These works inject stochasticity by adding noise (or
quantizing the input), only for quantifying the mutual information between the
input and the hidden layer and not into the DNN itself. 2018Estimating
introduced an auxiliary (noisy) DNN framework and showed that it is a good
proxy for the original (deterministic) DNN both regarding performance and the
learned representations.

To add noise, we can inject it directly into the representation (the
activation values) and get a noisy variable we can measure.
saxe2018information used a non-parametric KDE estimator outlined by
kolchinsky2017estimating, which directly adds small Gaussian noise to the
data. However, all the training processes had a fixed level of noise, which
led to failure due to the huge variation in the activation values (See
(chelombiev2019adaptive) for detailed explanation).

It is also possible to add noise by discretizing the continuous variables into
bins and approximating the representation as a discrete variable. In
2018Estimating, they claimed that this estimation injects noise that is not
present in the actual network, which is highly sensitive to selecting bin size
and does not track $I(X;T)$ for different choices of the bin size. They
developed a noisy DNNs framework and a rigorous estimator for $I(X;T)$. Using
this estimator, they observed compression in various models. By relating
$I(X;T)$ in the noisy DNN to an information-theoretic communication problem,
they showed that compression is driven by the progressive clustering of hidden
representations of inputs from the same class. They also proved that the
estimator of $I(X;T)$ using binning is a measure for clustering.

Binning saturating activation functions facilitates mutual information
estimation since all hidden activity is bounded within a predetermined range.
However, with nonsaturating functions, the estimation procedure’s noise level
must be adapted for every layer of the network each time. In
saxe2018information, the activation values are binned using a single range for
the whole training, which is terminated by the maximum value across all epochs
and all layers. However, since the network at every epoch is different, by
this binning procedure, the network’s estimation mixes unrelated factors
(chelombiev2019adaptive).

achille2018information stated that minimizing a stochastic network with an
approximate compression term from the IB functional as a regularizer is
equivalent to minimizing cross-entropy over deterministic DNNs with
multiplicative noise (information dropout). Moreover, they proved that the
special case of a Bernoulli noise results in the dropout method. In
elad2018effectiveness, the authors showed that the binned information could be
interpreted as a weight decay penalty, which aligns with common practice in
DNN training.

##### Invertible convolutional neural networks

The invertible DNN (jacobsen2018irevnet) is a network’s architecture that
achieves state-of-the-art performance. The authors claimed that in such
networks, $I(X;T_{k})$ is never discarded regardless of the network
parameters, and it is possible to reconstruct the input from each layer.
However, although reversible networks do not discard the input’s irrelevant
components, we hypothesize that these networks progressively separate the
irrelevant components from the relevant, allowing the final classification
mapping to discard this information.

### Discussion and Conclusions

Motivated by the IB framework, our numerical experiments demonstrate that the
visualization of the layers in the information-plane reveals many - so far
unknown, details about the inner working of DNNs. They reveal the distinct
phases of the SGD optimization, drift, and diffusion, explaining the ERM and
the representation compression trajectories of the layers’ information. The
stochasticity of SGD methods is usually motivated by escaping local minima of
the training error. In this paper, we give it a new, perhaps much more
important role: It generates highly efficient internal representations through
_compression by diffusion_. This is consistent with other recent suggestions
on the role of noise in DNNs (achille2018information; Kadmon2016OptimalAI).

We also argue that SGD seems an overkill during the diffusion phase, which
consumes most of the training epochs, and that much simpler optimization
algorithms, such as Monte-Carlo relaxations (geman1988stochastic), can be more
efficient. However, the IB framework may provide even more. If the layers
converge to the IB theoretical bounds, there is an analytic connection between
the encoder and decoder distributions for each layer, which can be exploited
during training. Combining the IB iterations with stochastic relaxation
methods may significantly boost DNN training.

To conclude, our analysis suggests that SGD with DNNs is, in essence, learning
algorithms that effectively find efficient representations approximate minimal
sufficient statistics in the IB sense.

#### Acknowledgments

This work is partially supported by the Gatsby Charitable Foundation, The
Israel Science Foundation, and Intel ICRI-CI center.

## Representation Compression
and Generalization in Deep Neural Networks

Unpublished
Ravid Shwartz-Ziv, Amichai Painsky and Naftali Tishby (2019)

Representation Compression and Generalization in Deep Neural Networks
Ravid Shwartz-Ziv 1 Amichai Painsky 2 Naftali Tishby1,2

1 The Edmond and Lilly Safra Center for Brain Sciences, The Hebrew University,

Jerusalem, Israel.

2 School of Computer Science and Engineering,

The Hebrew University,

Jerusalem, Israel.

Abstract

Understanding the groundbreaking performance of Deep Neural Networks (DNNs) is
one of the most significant challenges to the scientific community today. In
this work, we introduce an information-theoretic viewpoint on the behavior of
deep network optimization processes and their generalization abilities.
Specifically, we study DNNs on the information plane, the plane of the MI
between each layer with the input variable, and the desired label, during the
training dynamics. We show that we can characterize the network’s training 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.

Furthermore, we explicitly show that these two fundamental information-
theoretic quantities govern the network’s generalization error by introducing
a new generalization gap bound that is exponential in the input representation
compression. The analysis focuses on typical patterns of large-scale problems.
For this purpose, we introduce a novel analytic bound on the MI between
consecutive layers in the network. An important consequence of our analysis is
a superlinear boost in training time with the number of non-degenerate hidden
layers, demonstrating the hidden layers’ computational benefit.

### Introduction

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, especially in areas involving
complicated dependencies between the input variable and the target label
(natureDeepLeraning). 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 (IB) principle
(DBLP:journals/corr/Tishby1999). The 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 tradeoff 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 (shwartz2017opening), demonstrated that the layers of DNNs tend
to converge to the IB optimal bound. The results pointed to a distinction
between the 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 slowly reduces the MI 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., (DBLP:journals/corr/abs-1801-02254)).

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 the generalization performance? (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 shwartz2017opening. We claim that the reason
is the Stochastic Gradient Descent (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 a nonhomogeneous Brownian motion in the weights
space, in the proximity of a flat error minimum. This nonhomogeneous 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.,
(Paninski:2003:EEM:795523.795524)) and has led to the conclusion that there is
no “efficient” solution when the dimension of the problem is large. Recently,
several studies have focused on calculating the MI in DNNs using statistical
mechanics. These methods have generated promising results in various special
cases (gabrie2018entropy).

In this work, we provide an analytic bound on the MI between consecutive
layers, which is valid for any nonlinearity of the units and directly
demonstrates the representation’s compression during the diffusion phase.
Specifically, we derive a Gaussian bound that only depends on the linear part
of the layers. This bound gives a superlinear dependence of the layers’
convergence time, which enables us to prove the superlinear computational
benefit of the hidden layers. Furthermore, the Gaussian bound allows us to
study the MI in DNNs in real-world data without estimating it directly.

#### Preliminaries and Notations

Ravid Shwartz-Ziv
The Edmond and Lilly Safra Center for Brain Sciences,
School of Computer Science and Engineering
The Hebrew University,
Jerusalem, Israel.
<EMAIL_ADDRESS>
Naftali Tishby
The Edmond and Lilly Safra Center for Brain Sciences,
School of Computer Science and Engineering
The Hebrew University,
Jerusalem, Israel.
<EMAIL_ADDRESS>Ravid Shwartz-Ziv

Let $X\in\mathcal{X}$ and $Y\in\mathcal{Y}$ be a pair of random variables of
the input patterns and their target label (respectively). We consider the
practical setting where $X$ and $Y$ are continuous random variables
represented in a finite precision machine throughout this work. This means
that both $X$ and $Y$ are practically binned (quantized) into a finite number
of discrete values. Alternatively, $X,Y$, may be considered as continuous
random variables measured in the presence of small independent additive
(Gaussian) noise, corresponding to their numerical precision. We use these two
interpretations interchangeably, at the limit of infinite precision, where the
limit is applied at the final stage of our analysis.

We denote the joint probability of $X$ and $Y$ as $p(x,y)$, whereas their
corresponding MI is defined as
$I(X;Y)=D\left[p(y|x)||p(y)\right]=D\left[p(x|y)||p(x)\right].$ We use the
standard notation $D[p||q]$ for the Kullback-Liebler (KL) divergence between
the probability distributions $p$ and $q$. Let $f_{W^{K}}(x)$ denote a DNN,
with $K$ hidden layers, where each layer consists of $d_{k}$ neurons, each
with some activation function $\sigma_{k}(x)$, for $k=1,\dots,K$. We denote
the values of the $k^{th}$ layer by the random vector $T_{k}$. The DNN mapping
between two consecutive layers is defined as
$T_{k}=\sigma_{k}\left(W_{k}T_{k-1}\right)$, where $W_{k}$ is a $d_{k}\times
d_{k-1}$ real weight matrix. Note that we consider both the weights, $W_{k}$
and the layer representations, $T_{k}$, as stochastic entities because they
depend on the network’s stochastic training rule and the random input pattern
(as described in the next section). However, when the network weights are
given, the weights are fixed realizations of the random training process
(i.e., they are “quenched”). Note that given the weights, the layers form a
Markov chain of successive internal representations of the input variable $X$:
$Y\rightarrow X\rightarrow T_{1}\rightarrow...\rightarrow T_{K}$, and their MI
values obey a chain of Data Processing Inequalities (DPI), as discussed by
shwartz2017opening.

We denote the set of all $K$ layers weight matrices as
$W^{K}=\\{W_{1},\dots,W_{K}\\}$. Let the _training sample_ ,
$S^{n}=\\{\left(x_{1},y_{1}\right),\dots,$ $\left(x_{n},y_{n}\right)\\}$ be a
collection of $n$ independent samples from $p(x,y)$. Let
$\ell_{W^{K}}\left(x_{i},y_{i}\right)$ be a (differentiable) loss function
that measures the discrepancy between a prediction of the network
$f_{W^{K}}(x_{i})$ and the corresponding true target value $y_{i}$, for a
given set of weights ${W^{K}}$. Then, the empirical error is defined as
$\mathcal{L}_{W^{K}}\left(S^{n}\right)=\frac{1}{n}\sum_{i=1}^{n}\ell_{W^{K}}\left(x_{i},y_{i}\right)\leavevmode\nobreak\
.$ The corresponding error gradients (with respect to the weights) are denoted
as $\nabla_{W^{K}}\mathcal{L}_{W^{K}}\left(S^{n}\right)$. %ֿ

#### Opening the Black Box of Deep Neural Networks via Information

Ravid Shwartz-Ziv
The Edmond and Lilly Safra Center for Brain Sciences,
School of Computer Science and Engineering
The Hebrew University,
Jerusalem, Israel.
<EMAIL_ADDRESS>
Naftali Tishby
The Edmond and Lilly Safra Center for Brain Sciences,
School of Computer Science and Engineering
The Hebrew University,
Jerusalem, Israel.
<EMAIL_ADDRESS>Ravid Shwartz-Ziv

#### Representation compression and
generalization in Deep Neural Networks

Ravid Shwartz-Ziv
The Edmond and Lilly Safra Center for Brain Sciences,
School of Computer Science and Engineering
The Hebrew University,
Jerusalem, Israel.
<EMAIL_ADDRESS>
Naftali Tishby
The Edmond and Lilly Safra Center for Brain Sciences,
School of Computer Science and Engineering
The Hebrew University,
Jerusalem, Israel.
<EMAIL_ADDRESS>Ravid Shwartz-Ziv

#### Deep Neural Networks

In (shwartz2017opening), the authors noted that layer’s structure in neural
networks form a Markov chain of successive representations of the input layer
and empirically studied them in the information plane \- the plane of the MI
values of any other variable with the input variable $X$ and desired output
variable $Y$. This analysis’s rationale was based on two proprieties -
invariance of the MI to invertible re-parameterization and the layer’s
structure that forms a Markov chain of successive representations. In their
work, they showed that DNN’s layers converged to the Information Bottleneck
(IB) optimal bound (DBLP:journals/corr/Tishby1999)] of the optimal achievable
representations of the input $X$. Moreover, they showed that the training
optimization has two distinct phases: empirical error minimization (ERM) and
representation compression. These phases are characterized by very different
signal-to-noise ratios of the stochastic gradients in every layer. In the ERM
phase, the gradient norms are much larger than their stochastic fluctuations,
resulting in a rapid increase in the MI on the label variable $Y$. In the
compression phase, the gradients’ fluctuations are much larger than their
means, with a minimal influence of the error gradients. This phase is marked
by a slow representation’s compression or reduction of the MI on the input
variable $X$. DNNs opened a new era of machine learning capabilities. They
dramatically improved predictive abilities as they outperform state-of-the-art
methods in a wide variety of fields, ranging from visual object recognition,
speech recognition to drug discovery, genomics, and automatic game playing
(DBLP:journals/corr/abs-1303-5778). DNNs are multilayer data structures, where
each layer consists of multiple simple processing units called neurons (as an
analogy to the structure of a biological brain). Each layer’s neurons are
defined as a linear function of the neurons of the previous layer, followed by
a nonlinear activation function.

#### Training the Network – the SGD Algorithm

Training a DNN corresponds to setting the weights $W^{K}$ from a given set of
samples $S^{n}$. It is typically done by minimizing the empirical error, which
approximates the expected loss. The SGD algorithm is a standard optimization
method for this purpose (robbins1951stochastic).

Let $S^{(m)}$ be a random set of $m$ samples drawn (uniformly, with
replacement) from $S^{n}$, where $m<n$. We refer to $S^{(m)}$ as a mini-batch
of $S^{n}$. Define the corresponding empirical error and gradient of the
minibatch as
${\mathcal{L}}_{W^{K}}\left(S^{(m)}\right)=\frac{1}{m}\sum_{\\{x_{i},y_{i}\\}\in
S^{(m)}}\ell_{W^{K}}\left(x_{i},y_{i}\right)$ and
$\nabla_{W^{K}}{\mathcal{L}}_{W^{K}}\left(S^{(m)}\right)=\frac{1}{m}\sum_{\\{x_{i},y_{i}\\}\in
S^{(m)}}\nabla_{W^{K}}\ell_{W^{K}}\left(x_{i},y_{i}\right)$ respectively.
Then, the SGD algorithm is defined by the update rule:
$W^{K}(l)=W^{K}(l-1)-\eta\nabla_{W^{K}(l-1)}{\mathcal{L}}_{W^{K}(l-1)}\left(S^{(m)}\right)$,
where $W^{K}(l)$ are the weights after $l$ iterations of the SGD algorithm and
$\eta\in\mathbb{R}_{+}$ is the learning rate.

#### The Different Phases of SGD Optimization

The SGD algorithm plays a key role in the astonishing performance of DNNs. As
a result, it has been extensively studied in recent years, especially in the
context of flexibility and generalization (chee2017convergence). Here, we
examine the SGD as a stochastic process that can be decomposed into two
separate phases. This idea has been studied in several works
(murata1998statistical; jin2017escape; hardt2015train). Murata argued that
stochastic iterative procedures are initiated at some starting state and then
move through a fast transient phase towards a stationary phase, where the
distribution of the weights becomes time-independent. However, this may not be
when the SGD induces non-isotropic state-dependent noise, as argued, for
example, by DBLP:journals/corr/abs-1710-11029. Specifically, the SGD process
consists of a short transient phase in which it locates a neighborhood of
(local) minimum. Then, it oscillates around that point during a longer second
phase. The gradient of the process characterizes these phases; in the
transient phase, the gradients are typically in the same direction with low
variance, while in the second phase, they point to different directions with a
corresponding high variance (chee2017convergence).

In contrast, shwartz2017opening described the transient phase of the SGD as
having two very distinct dynamic phases. The first is a drift phase, where the
means of the error gradients in every layer are large compared to their batch-
to-batch fluctuations. This behavior indicates small variations in the
gradient directions, or _high-SNR gradients_. In the second part of the
transient phase, which they refer to as diffusion, the gradient means become
significantly smaller than their batch-to-batch fluctuations – _low-SNR
gradients_. The transition between the two phases occurs when the training
error saturates and the weights growth is dominated by the gradient batch-to-
batch fluctuations. Typically, most SGD updates are expended in the diffusion
phase before reaching Murata’s stationary phase. In this work, we rigorously
argue that this diffusion phase causes the representation compression, the
observed reduction in $I(T_{k};X)$, for most hidden layers.

(b)

(d)

Figure 1.18: The two phases of the training process - transition between the
drift phase to the diffusion.

#### Drift and Diffusion with SGD

It is well known that the discrete-time SGD can be considered as an
approximation of a continuous-time stochastic gradient flow if the discrete-
time iteration parameter $l$ is replaced by a continuous parameter $\tau$.
li2015stochastic showed that when the minibatch gradients are unbiased with
bounded variance, the discrete-time SGD is an approximation of a continuous-
time Langevin dynamics, Lemma 1.7.1 introduces an important property that
results from this approximation. Gradient over the minibatch is unbiased with
respect to the full gradient and has bounded variance. If the examples in a
minibatch are sampled with replacement, the variance of minibatch gradients is
$var\left(\nabla_{W}\hat{\mathcal{L}}^{S}\left(w_{1\dots
K}\right)\right)=\frac{D\left(w_{1\dots K}\right)}{|S|}$ where

$\displaystyle
D\left(w_{1,\dots,K}\right)=\left(\frac{1}{m}\sum_{i=1}^{m}{\nabla_{W}\ell_{i}\left(w_{1\dots
K}\right){\nabla_{W}\ell_{i}\left(w_{1\dots
K}\right)}}^{T}\right)-{\nabla_{W}\mathcal{L}\left(w_{1\dots
K}\right){\nabla_{W}\mathcal{L}\left(w_{1\dots K}\right)}}^{T}\succeq 0$
(1.21)

is the sample covariance matrix.

Note that $D(w_{1\dots K})$ is independent of the learning rate and the batch
size. It only depends on the weights, architecture and loss.

######  Lemma 1.7.1.

(li2015stochastic)

Assume that the mini-batches are sampled with replacement. Then, the update
rule of the SGD processes (Training the Network – the SGD Algorithm) may be
viewed as a discretization of the following continuous-time equation

$\displaystyle
dW^{K}(\tau)=-\nabla_{W^{K}(\tau)}\mathcal{L}_{W^{K}(\tau)}\left(S_{n}\right)d\tau+\sqrt{2\beta^{-1}C\left(W^{K}(\tau)\right)}dB\left(\tau\right)$
(1.22)

$\displaystyle dw_{1\dots
K}\left(\tau\right)=-\nabla\mathcal{L}\left(w_{1\dots
K}\left(\tau\right)\right)d\tau+\sqrt{2\beta^{-1}D\left(w_{1,\dots
K}\right)}dB\left(\tau\right)$ (1.23)

where $C\left(W^{K}(\tau)\right)$ is the sample covariance matrix of the
weights, $B(\tau)$ is a standard Brownian motion (Wiener process) and $\beta$
is the Langevin temperature constant. The first term in (1.23) is called the
gradient flow or drift component, and the second term corresponds to random
diffusion. Although this stochastic dynamics holds for the entire SGD training
process, the first term dominates the process during the high SNR gradient
phase, while the second term becomes dominant when the gradients are small,
due to the saturation of the training error in the low SNR gradient phase.
Hence, these two SGD phases are referred to as drift and diffusion.

The mean $L_{2}$ displacement (MSD) measures the Euclidean distance from a
reference position over time, which is used to characterize a diffusion
process. Normal diffusion processes are known to exhibit a power-law MSD in
time,
$\mathbb{E}\left[\left\|W^{K}(\tau)-W^{K}(0)\right\|_{2}\right]\sim\gamma
t^{\alpha}$, where $t$ is the diffusion time, $\gamma$ is related to the
diffusion coefficient, and $0<\alpha\leq 0.5$ is the diffusion exponent. For a
standard flat space diffusion, the MSD increases as a square root of time
($\alpha=0.5$). hu2017diffusion showed (empirically) that the weights’ MSD in
a DNN trained with SGD, indeed behaves (asymptotically) like a normal
diffusion, where the diffusion coefficient $\gamma$ depends on the batch size
and learning rate. In contrast, hoffer2017train showed that the weights’ MSD
demonstrates a much slower logarithmic increase. This type of dynamics is also
called ”ultra-slow” diffusion.

### Information Plane Analysis

Following DBLP:journals/corr/TishbyZ15 and shwartz2017opening, we study the
layer representation dynamics in the two-dimensional plane
$(I(X;T_{k}),I(T_{k};Y))$. Specifically, for any input and target variables,
$X,Y$, let $T\triangleq T(X)$ denote a representation, or an encoding (not
necessarily deterministic), of $X$. Clearly, $T$ is fully characterized by its
_encoder_ , the conditional distribution $p(t|x)$. Similarly, let $p(y|t)$
denote any (possibly stochastic) _decoder_ of $Y$ from $T$. Given a joint
probability function $p(x,y)$, the information plane is defined the set of all
possible pairs $I(X;T)$ and $I(T;Y)$ for any possible representation,
$p(T|X)$.

It is evident that not all points on the plane are feasible (achievable), as
there is a tradeoff between these quantities; the more we compress $X$ (reduce
$I(X;T)$), the less information can be maintained about the target, $I(T;Y)$.

Our analysis is based on the fundamental role of these two MI quantities. We
argue that for large-scale (high dimensional $X$) learning, for almost all
(_typical_) input patterns, with mild assumptions (ergodic Markovian input
patterns): (i) the MI values concentrate with the input dimension, (ii) the
minimal sample complexity for a given generalization gap is controlled by
$I(X;T)$, and (iii) the accuracy - the generalization error - is governed by
$I(T;Y)$, with the Bayes optimal decoder representation.

We argue that these two MI quantities characterize the sample-size and the
accuracy tradeoff of large-scale representation learning. For DNNs, this
amounts to a dramatic reduction in the complexity of the analysis of the
problem. We discuss these ideas in the following sections and prove the
connection between the input representation compression, the generalization
gap (the difference between training and generalization errors), and the
minimal sample complexity (Theorem 1 below).

#### Label Information and Generalization Error

The optimization of MI quantities is not a new concept in supervised or
unsupervised learning (deco2012information; linsker1988self;
painsky2016generalized). This is not surprising, as it can be shown that
$I(T;Y)$ corresponds to the irreducible error when minimizing the logarithmic
loss (painsky2018universality; harremoes2007information). Here, we emphasize
that $I(T;Y)$, for the optimal decoder of the representation $T$, governs all
reasonable generalization errors (under the mild assumption that label $y$ is
not entirely deterministic; $p(y|x)$ is in the interior of the simplex,
$\Delta(Y)$, for all typical $x\in X$). First, note that for the Markov chain
$Y-X-T$, $I(T;Y)=I(X;Y)-\mathbb{E}_{X,T}D\left[p(y|x)||p(y|t)\right]$. By
using the Pinsker inequality (cover2012elements), the variation distance
between the optimal and the representation decoders can be bounded by their KL
divergence,

$\displaystyle
D\left[p(y|x)||p(y|t)\right]\geq\frac{1}{2\ln{2}}\big{|}p(y|x)-p(y|t)\big{|}_{1}^{2}.$
(1.24)

Hence, by maximizing $I(T;Y)$ we minimize the expected variation risk between
the representation decoder $p(y|t)$ and $p(y|x)$. For more similar bounds on
the error measures see (painsky2018bregman).

#### Representation Compression and Sample Complexity

The Minimum Description Length (MDL) principle (rissanen1978modeling) suggests
that the best representation for a given set of data is the one that leads to
the minimal code length needed to represent the data. This idea has inspired
the use of $I(X;T)$ as a regularization term in many learning problems (e.g.,
chigirev2004optimal; painsky2018information). Here, we argue that $I(X;T)$
plays a much more fundamental role; we show that for large scale learning
(high dimensional $X$) and typical input patterns, $I(X;T)$ controls the
sample complexity of the problem, given a generalization error gap.

######  Theorem 1 (Input Compression bound).

Let $X$ be a $d$-dimensional random variable that obeys an ergodic Markov
random field probability distribution, asymptotically in $d$. Let $T\triangleq
T(X)$ be a representation of $X$ and denote by
$T_{m}=\\{(t_{1},y_{1}),\dots,(t_{m},y_{m})\\}$ an $m$-sample vector of $T$
and $Y$, generated with $m$ independent samples of $x_{i}$, with $p(y|x_{i})$
and $p(t|x_{i})$. Assume that $p(x,y)$ is bounded away from 0 and 1 (strictly
inside the simplex interior). Then, for large enough $d$, with probability
$1-\delta$, the typical expected squared generalization gap satisfies

$\big{|}\mathcal{L}\left(T_{m}\right)-\mathbb{E}_{T_{m}}\left[\mathcal{L}\left(T_{m}\right)\right]\big{|}^{2}\leq\frac{2^{I(X;T)}+\log{\frac{2}{\delta}}}{2m}.$
(1.25)

where the typicality follows the standard Asympthotic Equipartition Property
(AEP) (cover2012elements).

The proof of this theorem is given in Appendix A. This theorem is also related
to the bound proved by SHAMIR20102696, with the typical representation
cardinality, $|T(X)|\approx 2^{I(T;X)}$. The ergodic Markovian assumption is
common in many large-scale learning problems. It means that
$p(x)\approx\prod_{i=1:d}p(x_{i}|Pa(x_{i}))$, where $Pa(x_{i})$ is a finite
set of adjacent ”parents” of $x_{i}$ in the $d$ dimensional pattern $X$.

The consequences of this input-compression bound are quite striking: the
generalization error decreases exponentially with $I(X;T)$, once $I(T;X)$
becomes smaller than $\log{2m}$ \- the query sample-complexity. Moreover, it
means that $M$ bits of representation compression, beyond $\log{2m}$, are
equivalent to a factor of $2^{M}$ training examples. The tightest bound on the
generalization bound is obtained for the most compressed representation or the
last hidden layer of the DNN. The input-compression bound can yield a tighter
and more realistic sample complexity than any of the worst-case PAC bounds
with any reasonable estimate of the DNN class dimensionality, as typically,
the final hidden layers are compressed to a few bits.

Nevertheless, two important caveats are in order. First, the layer
representation in deep learning is learned from the training data; hence, the
encoder, the partition of the typical patterns $X$, and the _effective
”hypothesis class”_ , depend on the training data. This can lead to
considerable overfitting. Training with SGD avoids this potential overfitting
because of the way the diffusion phase works. Second, for low $I(T;Y)$, there
are exponentially (in $d$) many random encoders (or soft partitions of $X$)
with the same value of $I(T;X)$. This seems to suggest that there is a missing
exponential factor in our estimate of the hypothesis class cardinality.
However, note that the vast majority (almost all) of these possible encoders
are never encountered during a typical SGD optimization. Moreover, as $I(T;Y)$
increases, the number of such random encoders rapidly collapses to $O(1)$ when
$I(T;Y)$ approaches the optimal IB limit, as we show next.

#### The Information Bottleneck Limit

As presented above, we are interested in the boundary of the achievable region
in the information plane, or encoder-decoder pairs that minimize the sample
complexity (minimize $I(X;T)$) and generalize well (maximize $I(T;Y)$).

These optimal encoder-decoder pairs are given precisely by the IB framework
(DBLP:journals/corr/Tishby1999), which is formulated by the following
optimization problem: $\min_{p(t|x)}I\left(X;T\right)-\beta
I\left(T;Y\right),$ over all possible encoders-decoders pairs that satisfy the
Markov condition $Y-X-T$. Here, $\beta$ is a positive Lagrange multiplier
associated with the decoder information on $I(T;Y)$, which determines the
representation’s complexity.

The IB limit defines the set of optimal encoder-decoder pairs for the joint
distribution $p(x,y)$. Furthermore, it characterizes the achievable region in
the information plane, similar to Shannon’s rate-distortion theory
(cover2012elements). This analysis, also determines the optimal tradeoff
between sample complexity and generalization error. The IB can only be solved
analytically in exceptional cases (e.g., jointly Gaussian $X,Y$
(chechik2005information)). In general, a (locally optimal) solution can be
found by iterating the self-consistent equations, similar to the Blahut-
Arimoto algorithm in rate-distortion theory (DBLP:journals/corr/Tishby1999).
For general distributions, no efficient algorithm for solving the IB is known,
though there are several approximation schemes (chalk2016relevant;
painsky2017gaussian). Besides, several important approximation techniques were
introduced in recent years (chalk2016relevant; painsky2017gaussian).

The self-consistent equations are satisfied along the information curve. This
monotonic curve separates between the achievable and non-achievable regions on
the information plane. Notice that for smooth joint distributions $p(x,y)$,
the information curve is strictly concave with a unique slope, $\beta^{-1}$,
at every point, and a finite slope at the origin. In these cases of interest
(where $Y$ is not a deterministic function of $X$), every value of $\beta$
corresponds to a single point on the information curve with a corresponding
optimal encoder-decoder pair.

Two properties of the MI are fundamental in the context of DNNs. The first is
its invariance to invertible transformations:

$I\left(X;Y\right)=I\left(\psi(X);\phi(Y)\right)$ (1.26)

for any invertible functions $\phi$ and $\psi$.

The second is the Data Processing Inequality (DPI) [(Cover:2006)]: for any 3
variables that form a Markov chain $X\rightarrow Y\rightarrow Z$,

$I\left(X;Y\right)\geq I(X;Z)$

### The Information Plane and SGD Dynamics for DNNs

By applying the DPI to the Markov chain of the DNN’s layers, we obtain the
following chains:

$\displaystyle I(X;Y)$ $\displaystyle\geq I(T_{1};Y)\geq
I(T_{2};Y)\geq...I(T_{k};Y)\geq I(\hat{Y};Y)$ $\displaystyle H(X)$
$\displaystyle\geq I(X;T_{1})\geq I(X;T_{2})\geq...I(X;T_{k})\geq
I(X;\hat{Y}).$

where $\hat{Y}$ is the output of the network.

The pairs $(I(X;T_{k}),I(T_{k},Y))$, for each SGD update, form a unique
concentrated information path for each layer of a DNN, as demonstrated by
shwartz2017opening.

As we are only interested in the information that flows through the network,