11
$\begingroup$

I've read a few classic papers on different architectures of deep CNNs used to solve varied image-related problems. I'm aware there's some paradox in how deep networks generalize well despite seemingly overfitting training data. A lot of people in the data science field that I've interacted with agree that there's no explanation on why deep neural networks work as well as they do.

That's gotten me interested in the theoretical basis for why deep nets work so well. Googling tells me it's kind of an open problem, but I'm not sure of the current state of research in answering this question. Notably, there are these two preprints that seem to tackle this question:

If anyone else is interested in and following this research area, could you please explain the current state of research on this open problem? What are the latest works, preprints or publications that attempt to tackle it?

$\endgroup$
5
+50
$\begingroup$

Introduction

The paper Generalization in Deep Learning provides a good overview (in section 2) of several results regarding the concept of generalisation in deep learning. I will try to describe one of the results (which is based on concepts from computational or statistical learning theory, so you should expect a technical answer), but I will first introduce and describe the general machine learning problem and I will give a definition of the generalisation gap problem. To keep this answer relatively short, I will assume the reader is familiar with certain basic machine learning and mathematical concepts, such as expected risk minimization, but, nonetheless, I will refer the reader to more detailed explanations of the concepts (at least the first time they are mentioned). If you are familiar with the basic concepts of computational learning theory (e.g. hypotheses), you will be advantaged.

Machine Learning Problem

In the following description, unless stated otherwise, I do not make any assumption about the nature of the variables. However, I will occasionally provide examples of concrete values for these variables.

Let $x \in \mathcal{X}$ be an input and let $y \in \mathcal{Y}$ be a target. Let $\mathcal{L}$ be a loss function (e.g. MSE).

Then the expected risk of a function (or hypothesis) $f$ is defined as

\begin{align} R[f] &= \mathbb{E}_{x, y \sim \mathbb{P}(X, Y)} \left[ \mathcal{L}(f(x), y) \right] \\ &= \int \mathcal{L}(f(x), y) d\mathbb{P}(X=x, Y=y), \end{align}

where $\mathbb{P}(X, Y)$ is the true joint probability distribution of the inputs and targets. In other words, each $(x, y)$ is drawn from the joint distribution $\mathbb{P}(X, Y)$, which contains or represents all the information required to understand the relationship between the inputs and the targets.

Let $A$ be a learning algorithm or learner (e.g. gradient descent), which is the algorithm responsible for choosing a hypothesis $f$ (which can e.g. be represented by a neural network with parameters $\theta$). Let

$$S_m = \{(x_i, y_i) \}_{i=1}^m$$

be the training dataset. Let

$$f_{A(S_m)} : \mathcal{X} \rightarrow \mathcal{Y}$$

be the hypothesis (or model) chosen by the learning algorithm $A$ using the training dataset $S_m$.

The empirical risk can then be defined as

$$ R_{S_m}[f] = \frac{1}{m} \sum_{i=1}^m \mathcal{L} (f(x_i), y_i) $$

where $m$ is the total number of training examples.

Let $F$ be the hypothesis space (for example, the space of all neural networks).

Let

$$ \mathcal{L_F} = \{ g : f \in F , g(x, y) = \mathcal{L}(f(x), y)\} $$ be a family of loss functions associated with the hypothesis space $F$.

Expected Risk Minimization

In machine learning, the goal can be framed as the minimization of the expected risk

\begin{align} f^*_{A(S_m)} &= \operatorname{argmin}_{f_{A(S_m)}} R[f_{A(S_m)}] \\ &= \operatorname{argmin}_{f_{A(S_m)}} \mathbb{E}_{x, y \sim \mathbb{P}(X, Y)} \left[ \mathcal{L}(f_{A(S_m)}(x), y) \right] \tag{1}\label{1} \end{align}

However, the expected risk $R[f_{A(S_m)}]$ is incomputable, because it is defined as an expectation over $x, y \sim \mathbb{P}(X, Y)$ (which is defined as an integral), but the true joint probability distribution $\mathbb{P}(X, Y)$ is unknown.

Empirical Risk Minimization

Therefore, we solve the approximate problem, which is called the empirical risk minimization problem

\begin{align} f^*_{A(S_m)} &= \operatorname{argmin}_{f_{A(S_m)} \in F} R_S[f_{A(S_m)}] \\ &= \operatorname{argmin}_{f_{A(S_m)} \in F} \frac{1}{m} \sum_{i=1}^m \mathcal{L} (f_{A(S_m)}(x_i), y_i) \end{align}

Generalization

In order to understand the generalization ability of $f_{A(S_m)}$, the hypothesis chosen by the learner $A$ with training dataset $S_m$, we need to understand when the empirical risk minimization problem is a good proxy for the expected risk minimization problem. In other words, we want to study the following problem

\begin{align} R[f_{A(S_m)}] - R_S[f_{A(S_m)}] \tag{2}\label{2} \end{align}

which can be called the generalization gap problem. So, in generalization theory, one goal is to study the gap between the expected and empirical risks.

Clearly, we would like the expected risk to be equal to the empirical risk $$R_S[f_{A(S_m)}] = R[f_{A(S_m)}]$$ because this would allow us to measure the performance of the hypothesis (or model) $f_{A(S_m)}$ with the empirical risk, which can be computed. So, if $R_S[f_{A(S_m)}] = R[f_{A(S_m)}]$, the generalization ability of $f_{A(S_m)}$ roughly corresponds to $R_S[f_{A(S_m)}]$.

Therefore, in generalization theory, one goal is to provide bounds for the generalisation gap $R[f_{A(S_m)}] - R_S[f_{A(S_m)}]$.

Dependency on $S$

The hypothesis $f_{A(S_m)}$ is explicitly dependent on the training dataset $S$. How does this dependency affect $f_{A(S_m)}$? Can we avoid this dependency? Several approaches have been proposed to deal with this dependency.

In the following sub-section, I will describe one approach to deal with the generalization gap problem, but you can find a description of the stability, robustness and flat minima approaches in Generalization in Deep Learning.

Hypothesis-space Complexity

In this approach, we try to avoid the dependency of the hypothesis $f_{A(S_m)}$ by considering the worst-case generalization problem in the hypothesis space $F$

$$ R[f_{A(S_m)}] - R_S[f_{A(S_m)}] \leq \sup_{f \in F} \left( R[f] - R_S[f] \right) $$ where $\sup_{f \in F} \left( R[f] - R_S[f] \right)$ is the supremum of a more general generalization gap problem, which is greater or equal to \ref{2}. In other words, we solve a more general problem to decouple the hypothesis (or model) from the training dataset $S$.

Bound 1

If you assume the loss function $\mathcal{L}$ to take values in the range $[0, 1]$, then, for any $\delta > 0$, with probability $1 - \delta$ (or more), the following bound holds

\begin{align} \sup_{f \in F} \left( R[f] - R_S[f] \right) \leq 2 \mathcal{R}_m \left( \mathcal{L}_F \right) + \sqrt{\frac{\log{\frac{1}{\delta}} }{2m}} \tag{3} \label{3} \end{align} where $m$ is the size of the training dataset, $\mathcal{R}_m$ is the Rademacher complexity of $\mathcal{L}_F$, which is the family of loss functions for the hypothesis space $F$ (defined above).

This theorem is proved in Foundations of machine learning (2nd edition, 2018) by Mehryar Mohri et al.

There are other bounds to this bound, but I will not list or describe them here. If you want to know more, have a look at the literature.

I will also not attempt to give you an intuitive explanation of this bound (given that I am also not very familiar with the Rademacher complexity). However, we can already understand how a change in $m$ affects the bound. What happens to the bound if $m$ increases (or decreases)?

Conclusion

There are several approaches to find bounds for the generalisation gap problem \ref{2}

  • Hypothesis-space complexity
  • Stability
  • Robustness
  • Flat minima

In section 2 of the paper Generalization in Deep Learning, bounds for problem \ref{2} are given based on the stability and robustness approaches.

To conclude, the study of the generalization ability of deep learning models is based on computational or statistical learning theory. There are many more results related to this topic. You can find some of them in Generalization in Deep Learning. The studies and results are highly technical, so, if you want to understand something, good knowledge of mathematics, proofs, and computational learning theory is required.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! While it does make sense, I'll continue looking for a concrete example to understand how $P(X,Y)$ contains or represents all the information required to understand the relationship between the inputs and the targets. Maybe I should also try asking this particular follow-up question on stats SE? Or maybe I'll see if I can find info on that in the book you linked to. $\endgroup$ – Shirish Kulhari Nov 24 '19 at 16:23
  • $\begingroup$ @ShirishKulhari $P(X, Y)$ is a probability distribution of both the random variables $X$ and $Y$. In other words, given a specific realisation of $X$ and $Y$, e.g. $X=x$ and $Y=y$, then $P(X=x, Y=y)$ tells you the probability (or density) that the random variables $X$ and $Y$ take the values $x$ and $y$ at the same time, so it tells you how probable these two realisations are, in this sense $P(X, Y)$ contains the way $X$ and $Y$ vary together (see the concept of independence). So, in a certain way, you can find a function $f(x) = y$ based on the probabilities that $x$ and $y$ appear together. $\endgroup$ – nbro Nov 24 '19 at 16:27
  • $\begingroup$ @ShirishKulhari Regarding your second question, where you say "but I'm not sure how the entire hypothesis space can change with change in". In my answer, I am not saying that the entire hypothesis space, denoted by $F$ (capital $f$), depends on $S$. I am just saying that the single hypothesis $f_{A(S_m)} \in F$, where $F$ is the hypothesis space, explicitly depends on the training dataset $S_m$, by definition. Have a look at how $f_{A(S_m)}$ is defined in my answer. So, there are hypothesis $f \in F$, which do not depend on $S_m$, but maybe depend on another dataset. $\endgroup$ – nbro Nov 24 '19 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.