Ensemble Robustness and Generalization of Stochastic Deep Learning
Algorithms
Tom Zahavy and Bingyi Kang and Alex Sivak and Jiashi Feng and Huan Xu and Shie Mannor
arXiv e-Print archive - 2016 via arXiv
Keywords: cs.LG, cs.CV, stat.ML
First published: 2016/02/07 (8 years ago)
Abstract: The question why deep learning algorithms generalize so well has attracted increasing research interest. However, most of the well-established approaches, such as hypothesis capacity, stability or sparseness, have not provided complete explanations (Zhang et al., 2016; Kawaguchi et al., 2017). In this work, we focus on the robustness approach (Xu & Mannor, 2012), i.e., if the error of a hypothesis will not change much due to perturbations of its training examples, then it will also generalize well. As most deep learning algorithms are stochastic (e.g., Stochastic Gradient Descent, Dropout, and Bayes-by-backprop), we revisit the robustness arguments of Xu & Mannor, and introduce a new approach, ensemble robustness, that concerns the robustness of a population of hypotheses. Through the lens of ensemble robustness, we reveal that a stochastic learning algorithm can generalize well as long as its sensitiveness to adversarial perturbations is bounded in average over training examples. Moreover, an algorithm may be sensitive to some adversarial examples (Goodfellow et al., 2015) but still generalize well. To support our claims, we provide extensive simulations for different deep learning algorithms and different network architectures exhibiting a strong correlation between ensemble robustness and the ability to generalize.
more
less
Tom Zahavy and Bingyi Kang and Alex Sivak and Jiashi Feng and Huan Xu and Shie Mannor
arXiv e-Print archive - 2016 via arXiv
Keywords: cs.LG, cs.CV, stat.ML
First published: 2016/02/07 (8 years ago)
Abstract: The question why deep learning algorithms generalize so well has attracted increasing research interest. However, most of the well-established approaches, such as hypothesis capacity, stability or sparseness, have not provided complete explanations (Zhang et al., 2016; Kawaguchi et al., 2017). In this work, we focus on the robustness approach (Xu & Mannor, 2012), i.e., if the error of a hypothesis will not change much due to perturbations of its training examples, then it will also generalize well. As most deep learning algorithms are stochastic (e.g., Stochastic Gradient Descent, Dropout, and Bayes-by-backprop), we revisit the robustness arguments of Xu & Mannor, and introduce a new approach, ensemble robustness, that concerns the robustness of a population of hypotheses. Through the lens of ensemble robustness, we reveal that a stochastic learning algorithm can generalize well as long as its sensitiveness to adversarial perturbations is bounded in average over training examples. Moreover, an algorithm may be sensitive to some adversarial examples (Goodfellow et al., 2015) but still generalize well. To support our claims, we provide extensive simulations for different deep learning algorithms and different network architectures exhibiting a strong correlation between ensemble robustness and the ability to generalize.
[link]
This paper presents the theoretical notion of ensemble robustness and how it might provide an explanation for the success of deep learning algorithms. This work is an extension of some of the author's previous work (see Definition 2), demonstrating a theoretical relationship between a notion of robustness to adversarial examples and generalization performance. One initial observation made in this work is that this previous notion of robustness cannot explain the good performance of deep neural networks, since they have been shown to in fact not be robust to adversarial examples. So in this paper, the authors propose to study a notion of ensemble robustness (see Definition 3), and show that it can also be linked to generalization performance (see Theorem 1 and Corollary 1). The "ensemble" part comes from taking into account the stochasticity of the learning algorithm, i.e. the fact that the models they produce can vary from one run to another, even if applied on the same training set. The stochasticity here can come from the use of dropout, of SGD with random ordering of the training examples or from the random parameter initialization. Other theoretical results are also presented, such as one relating the variance of the robustness to generalization performance and another specific to the use of dropout. Finally, the paper also proposes a semi-supervised learning algorithm inspired from their definition of ensemble robustness, in which a model is trained to classify the perturbed (adversarial) version of an example in the same class as the original (non perturbed) example. On MNIST, they achieve excellent results, matching the performance of the state-of-the-art Ladder Networks. 
Your comment:
|
|
[link]
Zahavy et al. introduce the concept of ensemble robustness and show that it can be used as indicator for generalization performance. In particular, the main idea is to lift he concept of robustness against adversarial examples to ensemble of networks – as trained, e.g. through Dropout or Bayes-by-Backprop. Letting $Z$ denote the sample set, a learning algorithm is $(K, \epsilon)$ robust if $Z$ can be divided into $K$ disjoint sets $C_1,\ldots,C_K$ such that for every training set $s_1,\ldots,s_n \in Z$ it holds:
$\forall i, \forall z \in Z, \forall k = 1,\ldots, K$: if $s,z \in C_k$, then $l(f,s_i) – l(f,z)| \leq \epsilon(s_1,\ldots,s_n)$
where $f$ is the model produced by the learning algorithm, $l$ measures the loss and $\epsilon:Z^n \mapsto \mathbb{R}$. For ensembles (explicit or implicit) this definition is extended by considering the maximum generalization loss under the expectation of a randomized learning algorithm:
$\forall i, \forall k = 1,\ldots,K$: if $s \in C_k$, then $\mathbb{E}_f \max_{z \in C_k} |l(f,s_i) – l(f,z)| \leq \epsilon(s_1,\ldots,s_n)$
Here, the randomized learning algorithm computes a distribution over models given a training set.
Also view this summary at [davidstutz.de](https://davidstutz.de/category/reading/).
Your comment:
You must log in before you can post this comment!
|
You must log in before you can submit this summary! Your draft will not be saved!
Preview:
