Manitest: Are classifiers really invariant?

Introduction

Due to the huge research efforts that have been recently deployed in computer vision and machine learning, the state-of-the-art image classification systems are now reaching performances that are close to those of the human visual system in terms of accuracy on some datasets [Krizhevsky et al.(2012)Krizhevsky, Sutskever, and Hinton, Taigman et al.(2014)Taigman, Yang, Ranzato, and Wolf]. Questions emerge to what differences remain between human visual system and state-of-the-art classifiers. We focus here on one key difference, namely the problem of invariance to geometric transformations. While the human visual system is invariant to some extent to geometric transformations, it is unclear whether automatic classifiers enjoy the same invariance properties. The importance of invariance in classifiers has been outlined in recent works [Lenc and Vedaldi(2015), Soatto and Chiuso(2015)], and effective solutions for transformation-invariant classifications have been proposed by either adapting the classification rules with proper distance metrics [Simard et al.(1998)Simard, LeCun, Denker, and Victorri, Fawzi and Frossard(2013), Vasconcelos and Lippman(1998), Kokiopoulou and Frossard(2009)], or by improving the features used for classification [Bengio et al.(2013)Bengio, Courville, and Vincent, Mallat(2012), Bruna(2012)]. To validate such new design choices and to understand how to further improve classifiers’ invariance, it becomes however primordial to develop general methods to properly measure the robustness of classifiers to geometric transformations of data samples. Previous works have proposed methods to evaluate the invariance of classifiers, either by controlled changes in simple images [Berkes and Wiskott(2005)], or by specific tests for features of popular neural network architectures [Goodfellow et al.(2009)Goodfellow, Lee, Le, Saxe, and Ng]. These previous studies are however limited, as they are restricted to one-dimensional transformations (e.g., rotations only), to particular types of classifiers (e.g., neural networks) or to simple images (e.g., sinusoidal images), and are based on heuristically-driven quantities. Another approach for measuring invariance consists in generating datasets with transformed images, and measuring the accuracy of classifiers on these datasets [Larochelle et al.(2009)Larochelle, Bengio, Louradour, and Lamblin, Sohn and Lee(2012), LeCun et al.(2004)LeCun, Huang, and Bottou]. This is however laborious and involves building a novel well-designed dataset to compare all classifiers on a common ground.

In this paper, we propose a principled and systematic method to measure the robustness of arbitrary image classifiers to geometric transformations. In particular, we design a new framework that can be applied to any Lie group $\mathcal{T}$ and to any classifier $f$ regardless of the particular nature of the classifier. For a given image, we define the invariance measure as the minimal distance between the identity transformation and a transformation in $\mathcal{T}$ that is sufficient to change the decision of the classifier $f$ on that image. In order to define the transformation metric, our novel key idea is to represent the set of transformed versions of an image as a manifold; the transformation metric is then naturally captured by the geodesic distance on the manifold. Hence, for a given image, our invariance measure essentially corresponds to the minimal geodesic distance on the manifold that leads to a point where the classifier’s decision is changed. A global invariance measure is then derived by averaging over a sufficiently large sample set. Equipped with our generic definition of invariance, we leverage the techniques used in the analysis of manifolds of transformed visual patterns [Donoho and Grimes(2005), Wakin et al.(2005)Wakin, Donoho, Choi, and Baraniuk, Jacques and De Vleeschouwer(2008)] and design the Manitest method built on the efficient Fast Marching algorithm [Kimmel and Sethian(1998), Tsitsiklis(1995)] to compute the invariance of classifiers.

Using Manitest, we quantitatively show the following results: (i) The invariance of convolutional neural networks and scattering transforms largely outperform SVM classifiers, (ii) Two classifiers can have a similar accuracy, but have different invariance scores, (iii) The invariance of convolutional neural networks improves with network depth, (iv) On natural images classification task, baseline convolutional networks are not invariant to slight combinations of translations, rotations, and dilations (v) Data augmentation can dramatically increase the invariance of a classifier. The latter result is particularly surprising, as an SVM with RBF kernel trained on augmented samples can outperform the invariance of convolutional neural networks (without data augmentation) on a handwritten digits dataset. Besides these results, we showcase examples illustrating the introduced invariance scores. By providing a systematic tool to assess the classifiers in terms of their robustness to geometric transformations, we bridge a gap towards understanding the invariance properties of different families of classifiers, which will hopefully lead to building new classifiers that perform closer to the human visual system. The code of Manitest is available on the project websitehttp://sites.google.com/site/invmanitest/.

Problem formulation

Consider an image classification task, where the images are assigned discrete labels in $\mathcal{L}=\{1,\dots,L\}$, and let $f$ be an arbitrary image classifier. Formally, $f$ is a function defined on the space of square integrable images $L^{2}$, and takes values in the set $\mathcal{L}$. Our goal in this paper is to evaluate the invariance of $f$ with respect to $\mathcal{T}$. Given an image $I$, we define the invariance score of $f$ relative to $I$, $\Delta_{\mathcal{T}}(I;f)$, to be the minimal normalized distance from the identity transformation to a transformation $\tau$ that changes the classification label, i.e.,

For a given a distribution of datapoints $\mu$, the global invariance score of $f$ to transformations in $\mathcal{T}$ is defined by

The quantity $\rho_{\mathcal{T}}(f)$ depends on $f$ as well as the distribution of datapoints $\mu$. However, to simplify notations, we have omitted the dependence on $\mu$, assuming the distribution is clear from the context. In practical classification tasks, the true underlying distribution $\mu$ is generally unknown. In that case, we estimate the global resilience by taking the empirical averageIn practice, it is sufficient to consider an empirical average over a sufficiently large random subset of the training set. The number of samples is chosen to achieve a small enough confidence interval. over training points: $\hat{\rho}_{\mathcal{T}}(f)=\frac{1}{m}\sum_{j=1}^{m}\Delta_{\mathcal{T}}(I_{j};f)$.

2 Transformation metric

We discuss and introduce the distance used for the invariance score $\Delta_{\mathcal{T}}(I;f)$. It should be noted that $\mathcal{T}$ is possibly a multi-dimensional group (i.e., the transformations in $\mathcal{T}$ are described by many parameters of different nature such as translation, rotation, scale, …); hence, defining a trivial metric that measures the absolute distance between transformation parameters is of limited interest, as it combines parameters possibly of different nature. Instead, a more relevant notion of distance is one that depends on the underlying image $I$. In that case, $d(\tau_{1},\tau_{2})$ quantifies the change in appearance between images $I_{\tau_{1}}$ and $I_{\tau_{2}}$, rather than an absolute distance between the two transformations. Consider for example the image distance $d_{I}(\tau_{1},\tau_{2})=\|I_{\tau_{1}}-I_{\tau_{2}}\|_{L^{2}}$. While $d_{I}$ explicitly depends on the underlying image $I$, it fails to capture the intrinsic geometry of the family of transformed images. To illustrate this point, we consider a simple example of images in Fig. 1 with two transformed versions $I_{\tau_{1}}$ and $I_{\tau_{2}}$ of a reference image $I_{\tau_{0}}$. Note that $d_{I}(\tau_{0},\tau_{1})=d_{I}(\tau_{0},\tau_{2})$, as both transformed objects have no intersection with the reference object. However, it is clear that $I_{\tau_{2}}$ incurred a large rotation and translation, while $I_{\tau_{1}}$ underwent a slight vertical translation. Hence, the distance metric should naturally satisfy $d(\tau_{0},\tau_{1})<d(\tau_{0},\tau_{2})$, which is not the case for the image distance. This is crucial in our setting, as a classifier that recognizes the similarity of the objects in $I_{\tau_{2}}$ and $I_{\tau_{0}}$ is certainly more robust to transformations than a classifier that merely recognizes the similarity between $I_{\tau_{1}}$ and $I_{\tau_{0}}$, and should be given a higher score. This example underlines a well-known fundamental issue with the $L^{2}$ distance that fails to capture the intrinsic distance of the curved manifold of transformed images (see e.g., [Tenenbaum et al.(2000)Tenenbaum, De Silva, and Langford, Donoho and Grimes(2005)]). To correctly capture the intrinsic structure of the manifold, we define $d$ to be the length of the shortest path belonging to the manifold (i.e., the geodesic distance). For illustration, we show in Fig. 2 images along the geodesic path from $\tau_{0}$ to $\tau_{2}$; the geodesic distance is then essentially the sum of local $L^{2}$ distances between transformed images over the geodesic path. We formalize these notions as follows.

Let $\mathcal{M}(I)$ be the family of transformed images $\mathcal{M}(I)=\{I_{\tau}:\tau\in\mathcal{T}\}$. Equipped with the $L^{2}$ metric, $\mathcal{M}(I)$ defines a metric space and a continuous submanifold of $L^{2}$. Following the works of [Wakin et al.(2005)Wakin, Donoho, Choi, and Baraniuk, Jacques and De Vleeschouwer(2008)] that considered similar manifolds in different contexts, we call $\mathcal{M}(I)$ an Image Appearance Manifold (IAM), and we follow here their approach. Assuming that $\gamma:\mapsto\mathcal{T}$ is a $C^{1}$ curve in $\mathcal{T}$, and that $I_{\gamma(t)}$ is differentiable with respect to $t$, we define the length $L(\gamma)$ of $\gamma$ as

Note that Eq. (3) is expressed in terms of the $L^{2}$ metric in the image appearance manifold and corresponds to summing the local $L^{2}$ distances between transformed images over the path $I_{\gamma}$. We now show that $L(\gamma)$ can be expressed as a length associated to a Riemannian metric on $\mathcal{T}$ that we now derive. Defining the map

where $dF_{\tau}$ denotes the differential of $F$ at $\tau$, and $\gamma^{\prime}$ is derivative of $\gamma$. It follows that

where $g_{\tau}$ is the Riemannian metric (i.e., a positive bilinear form on $T_{\tau}\mathcal{T}$, the tangent space of $\mathcal{T}$ at $\tau$), given by:

Note that $g$ can be equivalently seen as the pullback of the $L^{2}$ metric on $\mathcal{M}(I)$ along $F$. By choosing a basis in the tangent space, the length $L(\gamma)$ can be equivalently written

where $G_{\gamma(t)}$ is the $p\times p$ positive definite matrix associated to the bilinear form $g$.

The transformation group $\mathcal{T}$ is parametrized with a rotation angle $\theta$ ($p=1$). In this case, the matix $G_{\theta}$ is of size $1$ by $1$, and equal to

The group $\mathcal{T}$ has $2$ degrees of freedom; namely a scale parameter $a$, and a rotation angle $\theta$. The Riemannian metric reads

Having defined the length of a curve on $\mathcal{T}$, the geodesic distance between two points $\tau_{1},\tau_{2}$ is defined as the length of the shortest curve joining the two points:

Finally, our problem therefore consists in computing the global invariance score, or equivalently $\Delta_{\mathcal{T}}(I;f)$ defined in Eq. (1), where $d$ is the geodesic distance. In other words, our problem becomes that of computing the minimal geodesic distance from the identity transformation to a transformation that is sufficient to change the estimated label of $f$.

Invariance score computation

The key to an efficient and accurate approximation of $\Delta_{\mathcal{T}}(I;f)$ lies in the effective computation of geodesics on the manifold $(\mathcal{T},G)$ that we address as follows.

Let $u(\tau)=d(e,\tau)$ be the geodesic map that measures the geodesic distance between the (fixed) identity element and $\tau$. The geodesic map satisfies the following Eikonal equation [Peyré et al.(2010)Peyré, Péchaud, Keriven, and Cohen]

where $\|x\|_{A}=\sqrt{\left\langle x,x\right\rangle_{A}}$ with $\left\langle x,y\right\rangle_{A}=x^{T}Ay$. Moreover, it was proved in [Crandall and Lions(1983)] that the geodesic map $u$ is the unique viscosity solution of the Eikonal equation, provided that $\tau\rightarrow G(\tau)$ is continuous. Many numerical schemes rely on the Eikonal equation characterization to approximate the geodesic map. We use here the popular Fast Marching (FM) method [Kimmel and Sethian(1998)], a fast front propagation approach that computes the values of the discrete geodesic map in increasing order. We only provide here a brief description of FM due to space constraints, and focus on the case where the manifold $\mathcal{T}$ is two-dimensional (i.e., $p=2$). The extension to arbitrary dimensions is straightforward, and we refer to [Peyré et al.(2010)Peyré, Péchaud, Keriven, and Cohen, Sethian and Vladimirsky(2003)] for more complete explanations and computations.

We assume that the manifold $\mathcal{T}$ is sampled using a regular grid; let $\mathcal{T}_{*}$ be the sampling of $\mathcal{T}$, and $U$ be the discrete vector that approximates $u$ at the nodes. The structure of Fast Marching is almost identical to Dijkstra’s algorithm for computing shortest paths on graphs [Dijkstra(1959)]. The main difference lies in the update step, which bypasses the constraint of propagation along edges. For a given node $\tau$, define $\mathcal{N}(\tau)$ to be the set of neighbours of $\tau$ (see illustration in Fig. 3). In the FM algorithm, each grid point is tagged either as Known (nodes for which distance is frozen), or Unknown (nodes for which distance can change in subsequent iterations). Initially, the grid points are set to Unknown, and $U$ is set to $\infty$, except $U(e)$ that is set to zero. At each iteration of FM, the unknown node $\tau_{\text{min}}$ with smallest $U$ is selected, and tagged as Known. Then, each unknown neighbour $\tau\in\mathcal{N}(\tau_{\min})$ is visited, and $U(\tau)$ is updated as follows: $U(\tau)$ is set to be the minimum of itself, $U(\tau_{\min})+\|\tau-\tau_{\min}\|_{G_{\tau}}$ and

The Manitest method, which applies FM algorithm to compute $\Delta_{\mathcal{T}}(I;f)$, is given in Algorithm 1 in the two dimensional case. The algorithm is stopped whenever a transformation that changes the classification label is found.To ensure the termination of the algorithm (even if no successful transformation is found) we limit the number of iterations $N$ to $50,000$. However, in all our experiments, this limit was never reached, and the algorithm terminated by successfully finding a transformation that satisfies $f(I_{\tau})\neq f(I)$. The nodes and metrics are generated on-the-fly in order to avoid spending unnecessary ressources on far-away nodes that might be farther than the minimal transformation that satisfies $f(I)\neq f(I_{\tau})$ and therefore never visited.

The complexity of Manitest is $O(N\log(N))$, where $N$ is the number of visited nodes if a min-heap structure is used [Peyré et al.(2010)Peyré, Péchaud, Keriven, and Cohen] (for constant $p$, and constant cost for evaluation of $f$). It is important to note however that the complexity of the algorithm has an exponential dependence on the dimension $p$ since our method involves the enumeration of simplices in dimension $p$; this is however not a big limitation as our main focus goes to low-dimensional transformation groups (e.g., $p\leq 6$ for affine transformations).

Finally, we note that when the metric is isotropic (i.e., $G_{\tau}$ is proportional to the identity matrix for all $\tau$), FM provides a consistent scheme. That is, as the discretization step tends to zero, the solution computed by the algorithm tends towards the viscosity solution of the Eikonal equation. Unfortunately, for arbitrary anisotropic metrics, consistency is however not guaranteed, and the exact computation of the geodesics becomes much more difficult and computationally demanding (see [Sethian and Vladimirsky(2000), Benmansour and Cohen(2011), Lin(2003), Mirebeau(2014)]). However, we observed that the anisotropy of the considered metric is generally not very large in the vicinity of $e$ (although it exceeds the theoretical limit of guaranteed consistency). This leads to empirically accurate estimates of the geodesic distance using Manitest, when the discretization step is sufficiently small. Finally, we stress that that all previous methods addressing the metric anisotropy can readily be applied to our setting, and we leave that as future work.

Experiments

We propose now a set of experiments to study the invariance of classifiers in different settings. In particular, we consider the following transformation groups:

$\mathcal{T}_{\text{trans}}$: in-plane translations of the image ($p=2$),

$\mathcal{T}_{\text{dil+rot}}$: dilations and rotations around the center of the image ($p=2$),

$\mathcal{T}_{\text{sim}}$: similarity transformations that describe combinations of translations, dilations and rotations around the center of the image ($p=4$).

In all experiments, we used a discretization step of $0.5$ pixels for translations, $\pi/20$ radians for rotation, and $0.1$ for dilation for Manitest. Finally, the transformed images have the same size as the original image, and we use a zero-padding boundary condition.

We first compare the invariance of different classifiers on the MNIST handwritten digits dataset [LeCun et al.(1998)LeCun, Bottou, Bengio, and Haffner]. We consider the following classifiers:

Linear SVM [Fan et al.(2008)Fan, Chang, Hsieh, Wang, and Lin],

SVM with RBF kernel [Chang and Lin(2011)],

Convolutional Neural Network [Vedaldi and Lenc(2014)]: we employ a baseline architecture with two hidden layers containing each a convolution operation ($5\times 5$ filters with 32 feature maps for the first layer and $64$ for the second layer), a rectified linear unit nonlinearity, and a max pooling over $2\times 2$ windows followed by a subsampling. The architecture is trained with stochastic gradient descent, with a softmax loss.

Scattering transform followed by a generative PCA classifier. We used the same settings as in [Bruna and Mallat(2013)], and we refer to that paper for more details.

Table 1 reports the performance of the different classifiers under study, and their invariance scores $\hat{\rho}_{\mathcal{T}}(f)$ using Manitest. As expected, the linear and RBF-SVM classifiers compare poorly to other classifiers in terms of invariance. This is due to the construction of the CNN and Scat. PCA, which explicitly take into account the invariance through pooling operations, while others do not. Moreover, it can be noted that Scat. PCA outperforms CNN in terms of robustness to translations, and global similarity transformations, even if the two classifiers have similar test error. This result is in agreement with the theoretical evidence [Bruna and Mallat(2013), Mallat(2012)] showing that scattering classifiers are invariant to deformations.

To further get an insight on the invariance of the classifiers, we focus on the two-dimensional group $\mathcal{T}_{\text{dil+rot}}$, and show in Fig. 4 (a) the geodesic distance map for an example image of digit “4” computed starting from the identity transformation (shown by a red dot at the center). Moreover, we overlay the minimally transformed images that change the labels of each of the classifiers, along with the corresponding geodesic paths. On this example, the Scat. PCA classifier is the most robust: a large dilation, accompanied with a rotation is required to change the classification label. In contrast, the linear SVM is easily “fooled” with a slight dilation. In Fig. 4 (b) we illustrate in white the region of the Rotation-Scale plane, where the classifier outputs the correct label “4”. Interestingly, the CNN and Scat. PCA classifiers are largely invariant to dilations (indicated by the vertical shape of the white region), while being moderately robust to rotations.

In vision tasks, it is common practice to augment the training data with artificial examples obtained by slightly distorting the original examples to achieve invariance. Although this practice is known to improve the classification performance of the classifiers on many tasks, its effect on the invariance of the classifier is not quantitatively understood. Fig. 5 illustrates the Manitest invariance scores for L-SVM and RBF-SVM classifiers trained on augmented training sets obtained by randomly generating transformationsRandom transformations are constrained as follows: translation of at most $3$ pixels in each direction, a scaling parameter between $0.7$, and $1.3$, and a rotation of at most $0.2$ radians. from the similarity group $\mathcal{T}_{\text{sim}}$, on the MNIST dataset. Both classifiers improve their invariance score as more transformed samples are added to the training set. This result has moreover an element of surprise, as RBF-SVM succeeds in improving its invariance score by around $50\%$ with mere additions of artificial examples in the training set, and outperforms the invariance of CNN (without data augmentation). Moreover, the obtained score is comparable to Scat. PCA classifier, which is carefully designed to satisfy invariance properties. This experiment permits to characterize the actual power of data augmentation for learning the invariance from the data.

2 Natural images

In this second experimental section, we perform experiments on the CIFAR-10 dataset [Krizhevsky and Hinton(2009)]. We focus on baseline CNN classifiers, and learn architectures with $1$, $2$ and $3$ hidden layers. Specifically, each layer consists of a successive combination of convolutional, rectified linear units and pooling operations. The convolutional layers consist of $5\times 5$ filters with respectively $32,32$ and $64$ feature maps for each layer, and the pooling operations are done on a window of size $3\times 3$ with a stride parameter of $2$. We build the three architectures gradually, by successively stacking a new hidden layer on top of the previous architecture (kept fixed). The last hidden layer is then connected to a fully connected layer, and the softmax loss is used. Moreover, the different architectures are trained with stochastic gradient descent. On the test set, the error of the three architectures are respectively $35.6\%$, $25.0\%$ and $22.7\%$.

We show in Fig. 6 the Manitest invariance scores of the three architectures. Our approach captures the increasing invariance with the number of layers of the network, for the three groups under study. This result is in agreement with empirical studies and previous known belief [Goodfellow et al.(2009)Goodfellow, Lee, Le, Saxe, and Ng, Bengio et al.(2013)Bengio, Courville, and Vincent] that invariance increases with the depth of the network. However, while previous results were measuring the invariance with respect to a one dimensional transformation group (e.g., rotation only), Manitest provides a systematic and principled way of verifying the increased invariance of CNNs with depth on more complex Lie groups (e.g., similarity transformations). Interestingly enough, it should be noted that despite the relatively small difference in performance between the two and three layers architectures, the invariance score strongly increases. This highlights again that invariance and performance measures capture two different properties of classifiers.

Compared to the handwritten digits task, note that the Manitest scores obtained on the CIFAR task are generally much smaller, which suggests that it is harder to achieve invariance on this task. To visualize the level of invariance of the 3-layer CNN on the CIFAR-10 dataset, we show in Fig. 7 sorted example images. For images with an average invariance score or less, note that the distinction between the transformed and original images are hardly perceptible. This suggests that the CNN is not robust to combinations of translations, rotation and dilation, even if it achieves a high accuracy. On the other hand, the difference between the original and the minimally transformed images are clearly perceptible for the top-scored images, even though a human observer is likely to correctly recognize the class of the transformed images.

Conclusion

In this paper, we proposed a systematic and rigorous approach for measuring the invariance of any classifier to low-dimensional transformation groups. Using a manifold perspective, we were able to convert the problem of assessing the classifier’s invariance to that of computing geodesic distances. Using Manitest, we quantified the increasing invariance of CNNs with depth, and highlighted the importance of data augmentation for learning invariance from data. We believe Manitest will be used to perform an in-depth empirical analysis of different classification architectures, in order to have a better understanding of the building blocks that best preserve invariance, and potentially build more robust classifiers.

Acknowledgments. We are grateful for the comments provided by the anonymous reviewers. We also thank Laurent Jacques and Gabriel Peyré for their insights on Fast Marching. We thank Luca Baroffio and Hamza Fawzi for their comments on the paper draft.

References