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$
4
+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.

$\endgroup$
  • $\begingroup$ Thanks for the amazing answer and clear explanation! I have a few follow-up doubts that hopefully shouldn't take too long to clarify. I've edited my question to include those. Could you look at them and clarify, if you don't mind? $\endgroup$ – Shirish Kulhari Nov 24 at 15:07
  • $\begingroup$ @ShirishKulhari Please, ask your first question in a separate post and tag it with "learning-theory". You can ask your question as "What is the difference between a hypothesis and a learning algorithm, in computational learning theory?". This question is already too long. Also, please, ask your last question in its separate post too! $\endgroup$ – nbro Nov 24 at 15:12
  • $\begingroup$ Will do and link to those questions in a comment! $\endgroup$ – Shirish Kulhari Nov 24 at 15:16
  • 1
    $\begingroup$ I've branched the first follow-up question into a separate one here: ai.stackexchange.com/questions/16746/…. And the last question here: ai.stackexchange.com/questions/16744/… $\endgroup$ – Shirish Kulhari Nov 24 at 15:35
  • $\begingroup$ @ShirishKulhari Ok, thanks for splitting the questions. I will have a look at the other questions and I will try to provide an answer later. However, note that I am not an expert on these topics. I understand the concepts (e.g. the ones I explain in this answer), but I don't have a very good knowledge of all of them and I don't think many people here will have a better knowledge of these concepts than me. $\endgroup$ – nbro Nov 24 at 15:43

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.