Decision boundary | EPFL Graph Search

NOTOC In a statistical-classification problem with two classes, a decision boundary or decision surface is a hypersurface that partitions the underlying vector space into two sets, one for each class. The classifier will classify all the points on one side of the decision boundary as belonging to one class and all those on the other side as belonging to the other class. A decision boundary is the region of a problem space in which the output label of a classifier is ambiguous. If the decision surface is a hyperplane, then the classification problem is linear, and the classes are linearly separable. Decision boundaries are not always clear cut. That is, the transition from one class in the feature space to another is not discontinuous, but gradual. This effect is common in fuzzy logic based classification algorithms, where membership in one class or another is ambiguous. Decision boundaries can be approximations of optimal stopping boundaries. The decision boundary is the set

Robustness and invariance properties of image classifiers

Apostolos Modas

Deep neural networks have achieved impressive results in many image classification tasks. However, since their performance is usually measured in controlled settings, it is important to ensure that their decisions remain correct when deployed in noisy environments. In fact, deep networks are not robust to a large variety of semantic-preserving image modifications, even to imperceptible image changes -- known as adversarial perturbations -- that can arbitrarily flip the prediction of a classifier. The poor robustness of image classifiers to small data distribution shifts raises serious concerns regarding their trustworthiness. To build reliable machine learning models, we must design principled methods to analyze and understand the mechanisms that shape robustness and invariance. This is exactly the focus of this thesis.First, we study the problem of computing sparse adversarial perturbations, and exploit the geometry of the decision boundaries of image classifiers for computing sparse perturbations very fast. We evaluate the robustness of deep networks to sparse adversarial perturbations in high-dimensional datasets, and reveal a qualitative correlation between the location of the perturbed pixels and the semantic features of the images. Such correlation suggests a deep connection between adversarial examples and the data features that image classifiers learn.To better understand this connection, we provide a geometric framework that connects the distance of data samples to the decision boundary, with the features existing in the data. We show that deep classifiers have a strong inductive bias towards invariance to non-discriminative features, and that adversarial training exploits this property to confer robustness. We demonstrate that the invariances of robust classifiers are useful in data-scarce domains, while the improved understanding of the data influence on the inductive bias of deep networks can be exploited to design more robust classifiers. Finally, we focus on the challenging problem of generalization to unforeseen corruptions of the data, and we propose a novel data augmentation scheme that relies on simple families of max-entropy image transformations to confer robustness to common corruptions. We analyze our method and demonstrate the importance of the mixing strategy on synthesizing corrupted images, and we reveal the robustness-accuracy trade-offs arising in the context of common corruptions. The controllable nature of our method permits to easily adapt it to other tasks and achieve robustness to distribution shifts in data-scarce applications.Overall, our results contribute to the understanding of the fundamental mechanisms of deep image classifiers, and pave the way for building more reliable machine learning systems that can be deployed in real-world environments.

EPFL2022

Geometry of adversarial robustness of deep networks: methods and applications

Seyed Mohsen Moosavi Dezfooli

We are witnessing a rise in the popularity of using artificial neural networks in many fields of science and technology. Deep neural networks in particular have shown impressive classification performance on a number of challenging benchmarks, generally in well controlled settings. However it is equally important that these classifiers satisfy robustness guarantees when they are deployed in uncontrolled (noise-prone) and possibly hostile environments. In other words, small perturbations applied to the samples should not yield significant loss to the performance of the classifier. Unfortunately, deep neural network classifiers are shown to be intriguingly vulnerable to perturbations and it is relatively easy to design noise that can change the estimated label of the classifier. The study of this high-dimensional phenomenon is a challenging task, and requires the development of new algorithmic tools, as well as theoretical and experimental analysis in order to identify the key factors driving the robustness properties of deep networks. This is exactly the focus of this PhD thesis. First, we propose a computationally efficient yet accurate method to generate minimal perturbations that fool deep neural networks. It permits to reliably quantify the robustness of classifiers and compare different architectures. We further propose a systematic algorithm for computing universal (image-agnostic) and very small perturbation vectors that cause natural images to be misclassified with high probability. The vulnerability to universal perturbations is particularly important in security-critical applications of deep neural networks, and our algorithm shows that these systems are quite vulnerable to noise that is designed with only limited knowledge about test samples or classification architectures. Next, we study the geometry of the classifier's decision boundary in order to explain the adversarial vulnerability of deep networks. Specifically, we establish precise theoretical bounds on the robustness of classifiers in a novel semi-random noise regime that generalizes both the adversarial and the random perturbation regimes. We show in particular that the robustness of deep networks to universal perturbations is driven by a key property of the curvature of their decision boundaries. Finally, we build on the geometric insights derived in this thesis in order to improve the robustness properties of state-of-the-art image classifiers. We leverage a fundamental property in the curvature of the decision boundary of deep networks, and propose a method to detect small adversarial perturbations in images, and to recover the labels of perturbed images. To achieve inherently robust classifiers, we further propose an alternative to the common adversarial training strategy, where we directly minimize the curvature of the classifier. This leads to adversarial robustness that is on par with adversarial training. In summary, we demonstrate in this thesis a new geometric approach to the problem of the adversarial vulnerability of deep networks, and provide novel quantitative and qualitative results that precisely describe the behavior of classifiers in adversarial settings. Our results in this thesis contribute to the understanding of the fundamental properties of state-of-the-art image classifiers that eventually will bring important benefits in safety-critical applications such as in self-driving cars, autonomous robots, and medical imaging.

EPFL2019

Robust image classification

Alhussein Fawzi

In the past decade, image classification systems have witnessed major advances that led to record performances on challenging datasets. However, little is known about the behavior of these classifiers when the data is subject to perturbations, such as random noise, structured geometric transformations, and other common nuisances (e.g., occlusions and illumination changes). Such perturbation models are likely to affect the data in a widespread set of applications, and it is therefore crucial to have a good understanding of the classifiers' robustness properties. We provide in this thesis new theoretical and empirical studies on the robustness of classifiers to perturbations in the data. Firstly, we address the problem of robustness of classifiers to adversarial perturbations. In this corruption model, data points undergo a minimal perturbation that is specifically designed to change the estimated label of the classifier. We provide an efficient and accurate algorithm to estimate the robustness of classifiers to adversarial perturbations, and confirm the high vulnerability of state-of-the-art classifiers to such perturbations. We then analyze theoretically the robustness of classifiers to adversarial perturbations, and show the existence of learning-independent limits on the robustness that reveal a tradeoff between robustness and classification accuracy. This theoretical analysis sheds light on the causes of the adversarial instability of state-of-the-art classifiers, which is crucial for the development of new methods that improve the robustness to such perturbations. Next, we study the robustness of classifiers in a novel semi-random noise regime that generalizes both the random and adversarial perturbation regimes. We establish precise theoretical bounds on the robustness of classifiers in this general regime, which depend on the curvature of the classifier's decision boundary. Our bounds show in particular that we have a blessing of dimensionality phenomenon: in high-dimensional classification tasks, robustness to random noise can be achieved, even if the classifier is extremely unstable to adversarial perturbations. We show however that, for semi-random noise that is mostly random and only mildly adversarial, state-of-the-art classifiers remain vulnerable to such noise. We further perform experiments and show that the derived bounds provide very accurate robustness estimates when applied to various state-of-the-art deep neural networks and different datasets. Finally, we study the invariance of classifiers to geometric deformations and structured nuisances, such as occlusions. We propose principled and systematic methods for quantifying the robustness of arbitrary image classifiers to such deformations, and provide new numerical methods for the estimation of such quantities. We conduct an in-depth experimental evaluation and show that the proposed methods allow us to quantify the gain in invariance that results from increasing the depth of a convolutional neural network, or from the addition of transformed samples to the training set. Moreover, we demonstrate that the proposed methods identify ``weak spots'' of classifiers by sampling from the set of nuisances that cause misclassification. Our results thus provide insights into the important features used by the classifier to distinguish between classes. Overall, we provide in this thesis novel quantitative results that precisely describe the behavior of classifiers under perturbations of the data. We believe our results will be used to objectively assess the reliability of classifiers in real-world noisy environments and eventually construct more reliable systems.

EPFL2016