A Boundary Tilting Persepective on the Phenomenon of Adversarial Examples

Thomas Tanay; Lewis Griffin

Source-linked AI summary

A Boundary Tilting Persepective on the Phenomenon of Adversarial Examples

Thomas Tanay, Lewis Griffin

arXiv:1608.07690v1Aug 27, 2016cs.LGstat.ML

TL;DR

The paper asks why small perturbations can change deep-network classifications and whether the accepted “too linear” account fully explains this phenomenon. It replaces that account with a boundary-tilting analysis, defines adversarial strength and a taxonomy, and shows that regularisation can control especially strong examples. The authors also identify limitations in the linear explanation and constrain the practical regularisation conclusion to pixel-space application.

Problem
The paper addresses limitations of the accepted linear explanation, including an unconvincing formal argument and its failure to predict when adversarial examples occur or how they differ across models.
Method
The paper analyzes adversarial examples geometrically in the linear case, using classification boundaries, nearest-centroid deviation angles, adversarial strength, boundary tilting, and a taxonomy.
Results
The paper shows that boundary tilting can produce adversarial strength of arbitrary magnitude independently of classification performance, while regularisation level controls the observed deviation angle and example type.
Takeaways & Limitations
Type 2 adversarial examples can be avoided with a proper regularisation level, but the paper reports that l2 regularisation helps only when applied directly in pixel space.
Takeaways & Limitations
The linear explanation does not establish which classes suffer from adversarial examples, and the regularisation finding is limited to l2 regularisation applied directly in pixel space.

Abstract

from arXiv · show

Deep neural networks have been shown to suffer from a surprising weakness: their classification outputs can be changed by small, non-random perturbations of their inputs. This adversarial example phenomenon has been explained as originating from deep networks being "too linear" (Goodfellow et al., 2014). We show here that the linear explanation of adversarial examples presents a number of limitations: the formal argument is not convincing, linear classifiers do not always suffer from the phenomenon, and when they do their adversarial examples are different from the ones affecting deep networks. We propose a new perspective on the phenomenon. We argue that adversarial examples exist when the classification boundary lies close to the submanifold of sampled data, and present a mathematical analysis of this new perspective in the linear case. We define the notion of adversarial strength and show that it can be reduced to the deviation angle between the classifier considered and the nearest centroid classifier. Then, we show that the adversarial strength can be made arbitrarily high independently of the classification performance due to a mechanism that we call boundary tilting. This result leads us to defining a new taxonomy of adversarial examples. Finally, we show that the adversarial strength observed in practice is directly dependent on the level of regularisation used and the strongest adversarial examples, symptomatic of overfitting, can be avoided by using a proper level of regularisation.

1 Introduction

Deep networks achieve striking performance yet remain vulnerable to small, non-random perturbations that change classifications. The paper challenges the accepted linear explanation and introduces a boundary-tilting perspective for analyzing the phenomenon.

Motivation: Deep networks can outperform humans on difficult tasks while remaining extremely sensitive to small, non-random input perturbations.Correctly classified images can have adversarial counterparts that appear identical or nearly identical.
Research gap: The paper argues that the accepted linear explanation has an unconvincing formal argument and does not reliably predict when adversarial examples occur.It also reports qualitative differences between adversarial examples affecting linear MNIST classifiers and GoogLeNet on ImageNet.
Proposed perspective: The proposed perspective places adversarial examples near classification boundaries that lie close to the submanifold of sampled data.The paper develops a mathematical analysis of this perspective in the linear case.
Contributions: The paper defines adversarial strength, relates it to deviation from a nearest-centroid classifier, and introduces boundary tilting as a mechanism for arbitrarily strong examples independent of classification performance.It also uses this result to define a taxonomy of adversarial examples.

2 Previous Explanations

Earlier work explained adversarial examples through dense low-probability regions or linear behavior in high-dimensional spaces. The paper reviews these accounts, questions their explanatory scope, and specifies its use of the 2-norm and linear SVM for geometric analysis.

Low-probability pockets: The rational-number analogy models adversarial examples as dense, low-probability points near ordinary test cases, but leaves their mechanism in deep networks unexplained.The analogy does not explain why deep networks would implement similarly strange decision rules.
Linear explanation: The linear explanation attributes adversarial vulnerability to perturbations aligned with model weights, whose activation effect can grow with input dimensionality.Under an infinity-norm constraint, the proposed perturbation is η = ϵ sign(w), and the activation increase is described as ϵmn.
Analytical setup: For its analysis, the paper uses the 2-norm, generating perturbations in the normalized gradient direction, and studies linear-kernel SVM because of its geometric interpretation.This differs from the infinity-norm construction based on sign(w).

3 Limitations with the Linear Explanation

The paper identifies three limitations of the linear explanation: dimensionality is insufficient, linear classifiers need not produce adversarial examples, and their MNIST examples differ qualitatively from deep-network examples.

3.1 An unconvincing argument: The activation-change argument is unconvincing because perturbation effects and original activations both grow with dimensionality, leaving their ratio constant.The paper argues that w⊤·η and w⊤·x both scale linearly when weight and pixel distributions remain unchanged.
3.1 An unconvincing argument: Increasing MNIST image resolution from 28 × 28 to 200 × 200 does not increase the perceptual magnitude of adversarial perturbations.The two linear SVM models have a 2.7% error rate, while perturbations causing 99% test-set misclassification use ϵ28 = 4.6 and ϵ200 = 31.
3.1 An unconvincing argument: High dimensionality therefore does not necessarily make classification problems more prone to adversarial examples.The paper presents this as a direct rejection of the dimensionality argument.
3.2 Linear behaviour is not sufficient to cause adversarial examples: The linear explanation cannot predict which image classes will suffer from adversarial examples, because a linear SVM can perfectly separate classes without producing them.In the toy problem, classes I and J differ by black versus white right half-images, and the trained SVM generalizes perfectly.
3.2 Linear behaviour is not sufficient to cause adversarial examples: For the toy classes, gradient-based boundary and mirrored images remain perceptually intermediate or belong to the opposite class, rather than being adversarial examples.The boundary image has a grey right half, while continuing the same movement yields an image perceived as belonging to the new class.
3.3 Linear classification on MNIST. Are these examples really adversarial?: On MNIST, linear-model perturbations are visually perceptible, low-frequency, and resemble the nearest-centroid weight vector, unlike imperceptible deep-network perturbations.The paper concludes that linear classification on MNIST does not explain why deep networks can be fooled by perturbations resembling random noise.

4 The Boundary Tilting Perspective

The boundary tilting perspective resolves the paradox by locating sampled data on a submanifold whose nearby classification boundary may be crossed by small, directed perturbations.

4 The Boundary Tilting Perspective: The paradox is how well-separated image classes can have every element close to an element of the other class.The paper frames this question after rejecting high dimensionality and the linear explanation as sufficient accounts.
4.1 Pictorial solution to the adversarial examples paradox: Training and test data occupy a submanifold of image space, while the classification boundary extends beyond that sampled region.The boundary can intersect the submanifold while still separating the classes.
4.1 Pictorial solution to the adversarial examples paradox: Adversarial examples arise when the boundary lies close to the data, allowing small perturbations directed toward it to cross the boundary.This mechanism differs from the alternative explanation based on densely distributed low-probability adversarial pockets.
4.1 Pictorial solution to the adversarial examples paradox: In higher dimensions, random perturbations are unlikely to move exactly toward the boundary, so boundary-near images can remain robust to random noise.The low-dimensional schematic may show random crossings, but the paper says this becomes unlikely in higher dimension.

4.2 Adversarial examples in linear classification

The paper replaces the “too linear” explanation with boundary tilting: adversarial examples arise when a classification boundary lies close to sampled data. In linear classification, adversarial strength is characterized geometrically and can become arbitrarily high without reducing classification performance.

Boundary tilting: Linear behavior is necessary but not sufficient: adversarial examples require a tilted class boundary lying close to the data.The authors present this as an alternative to explanations based on nonlinear, low-probability pockets.
Formal condition: A boundary has no adversarial examples exactly when reflecting class I through it produces J and reflecting J produces I.Equivalently, the two classes are mirror classes through the boundary.
Strength measure: Adversarial strength is defined over the full phenomenon spectrum, avoiding the standard perturbation magnitude’s limitation to small perturbations.The standard magnitude ϵ is meaningful for small values but becomes ambiguous as perturbations grow.
Geometric analysis: Adversarial strength is maximized as ∥i −m(i, C)∥ tends to 0 and minimized as ∥j −m(i, C)∥ tends to 0.The nearest-centroid boundary B minimizes the phenomenon, even when it still suffers from adversarial examples.
Class asymmetry: The parameter rc controls the relative strengths affecting I and J, allowing strong adversarial examples to concentrate on one class at a time.The limiting strengths differ as rc approaches either separation boundary.
Geometric analysis: When C passes near the mean of the class centroids, adversarial strength is approximately equal across classes and reduces to the deviation angle |δc|.It is minimized at δc = 0, corresponding to C ≈B, and maximized as |δc| tends to π/2.
Boundary tilting: For rotations Cθ with θc + θ in ]−π/2, π/2[, every element of S retains its classification and roc(θ) = 0.More generally, the rate of change is small when data variance along the tilt direction is small.
Boundary tilting: Tilting a boundary along a low-variance direction can produce arbitrarily strong adversarial examples while preserving or nearly preserving classification performance.When the variance is zero, the original and tilted boundaries perform exactly the same; with small variance, their rate of change remains small.

4.3 Return to the toy problem

The toy problem shows that regularisation controls boundary tilting: slight overfitting produces weak adversarial examples, whereas complete overfitting produces strong ones.

4.3 Return to the toy problem: The nearest-centroid classifier correctly mirrors images between the two classes, providing a boundary without adversarial examples in the uncorrupted toy problem.The SVM weight vector equals the nearest-centroid weight vector, and mirroring an image from either class through the boundary produces an image from the other class.
4.3 Return to the toy problem: With 5% corrupted images, soft-margin SVM slightly overfits and yields very weak adversarial examples.The minimum error is ermin = 2.5%, training error is 2.2%, and the deviation angle is δ(wsoft) = 0.032 π/2.
4.3 Return to the toy problem: Without regularisation, hard-margin SVM completely overfits and yields very strong type 2 adversarial examples.Training error falls to 0%, while the weight vector deviates strongly from the nearest-centroid direction.
4.3 Return to the toy problem: Boundary tilting explains how fitting corrupted data can maximise the margin while reducing average class separation, enabling strong adversarial examples.The hard-margin boundary finds a direction that separates corrupted training data completely, but this separation does not generalise to novel test data.

4.4 Return to MNIST

On 3s-versus-7s MNIST, weaker regularisation increases the SVM boundary's deviation from the nearest-centroid direction and eventually produces overfitting and type 2 adversarial examples.

4.4 Return to MNIST: The SVM weight vector moves from near the nearest-centroid direction to near orthogonality as regularisation weakens.For high regularisation, δ = 0.048 π/2; for low regularisation, δ = 0.92 π/2.
4.4 Return to MNIST: The test error is minimised at an intermediate regularisation level, while low regularisation drives training error toward 0% and increases test error.Overfitting occurs for log10(C) = −1, 0 and 1; the test error is minimised at log10(C) = −2.
4.4 Return to MNIST: As regularisation weakens, the SVM direction shifts from the nearest-centroid direction through low-frequency directions toward higher-frequency, noise-like directions.The decomposition confirms that overfitting tilts the boundary along low-variance components, while flat directions are not used because they contain no variance.
4.4 Return to MNIST: The toy-problem figures contrast soft-margin and hard-margin SVM: slight deviation corresponds to weak adversarial examples, while large deviation corresponds to strong ones.The reported deviations are δ(wsoft) = 0.032 π/2 and δ(whard) = 0.97 π/2.
4.4 Return to MNIST: Standard preprocessing does not uniformly prevent type 2 adversarial examples: pixelwise regularisation works, but feature-space regularisation after PCA whitening does not effectively prevent them.The paper reports this limitation for l2 regularisation when the feature space does not directly reflect pixel distance.

5 Conclusion

The paper reframes adversarial examples as a boundary-geometry phenomenon, formalizes adversarial strength through boundary tilting, and distinguishes multiple adversarial-example types. Experiments connect strong type 2 examples to regularization and show that pixel-space l2 regularization can avoid them.

A classification boundary close to the submanifold of sampled data produces adversarial examples.
In linear classification, adversarial strength is measured by the deviation angle from the nearest-centroid bisecting boundary.
Boundary tilting can preserve similar classification performance while producing adversarial examples of arbitrary strength when low-variance directions exist.
On 3s versus 7s MNIST, regularization controls the deviation angle, and type 2 examples can be avoided with an appropriate level of regularization.
The taxonomy distinguishes adversarial examples associated with limited linear expressiveness from type 2 examples associated with overfitting and high-frequency perturbations.

A Expression of the adversarial strength as a function of the deviation angle

This appendix derives geometric expressions for distances from class points to their mirrored points under a classification boundary. The derivation introduces normalized boundary-offset notation after applying geometric identities.

Choosing the origin at the midpoint between i and j establishes symmetric boundary coordinates for the geometric derivation.
Assuming C lies between i and j yields bounds on c0/cos(δc) and explicit distances to the mirrored points.
The derivation applies the law of cosines to the triangles formed by i, j, and their mirrored points.
The appendix introduces rc as a normalized boundary offset to rewrite the resulting geometric expressions.

B Expression of the sets of all classification scores through C and Cθ

This appendix treats S as a data matrix to express the classification scores associated with C and Cθ.

Regard S as a data matrix to write the classification-score expressions for the boundaries C and Cθ.

C Expression of roc(θ) when P follows a bivariate normal distribution

Under a bivariate normal distribution with covariance Σ1 = diag(1, 1), the appendix expresses roc(θ) as the difference between the scores of Cθ and C.

With covariance Σ1 = diag(1, 1), the appendix specifies the isotropic bivariate-normal setting for roc(θ).
roc(θ) is written as roc(Z, Cθ, Σ1) − roc(Z, C, Σ1), yielding the expression θc + θ.