summaries: In computing the gradient of the ELBO, the main challenge lies in computing the gradient of the reconstruction loss with respect to the encoder parameters. VAEs traditionally rely on reparameterization in order to obtain a low-variance estimate, but there are a number of other gradient estimators that one can apply. The authors here proprose to use a trick that is known, but perhaps not widely known: If we introduce an importance sampling distribution, then we can use samples from this distribution to compute an importance-weighted estimate of the gradient. The idea is now that we can compute the gradient w.r.t. the encoder parameters as a simple importance-sampling estimate, which obviates then need for reparameterization, or likelihood-ratio estimators. The authors then apply this trick to train VAEs with discrete latent variables.

summaries: This paper proposes training VAEs with discrete latent variables by importance sampling the expected log likelihood (ELL) term in the ELBO, which is the problematic term since it is not amenable to reparametrization gradients.  For the importance sampling distribution, they choose the variational distribution itself, making the ELL gradient E[(d q(z|x) / d \theta) \log p(x|z) / q(z|x)].  Experiments are reported for MNIST and Fashion-MNIST using Bernoulli and categorical latent variables.

abstractText: The Variational Auto Encoder (VAE) is a popular generative latent variable model that is often applied for representation learning. Standard VAEs assume continuous valued latent variables and are trained by maximization of the evidence lower bound (ELBO). Conventional methods obtain a differentiable estimate of the ELBO with reparametrized sampling and optimize it with Stochastic Gradient Descend (SGD). However, this is not possible if we want to train VAEs with discrete valued latent variables, since reparametrized sampling is not possible. Till now, there exist no simple solutions to circumvent this problem. In this paper, we propose an easy method to train VAEs with binary or categorically valued latent representations. Therefore, we use a differentiable estimator for the ELBO which is based on importance sampling. In experiments, we verify the approach and train two different VAEs architectures with Bernoulli and Categorically distributed latent representations on two different benchmark datasets. 1 THE VARIATIONAL AUTO ENCODER The variational auto encoder (VAE) is a generative model which it is trained to approximate the true data generating distribution p(x) of an observed random vector x from a given training set D = {x1, ...,xN} (Kingma & Welling (2013); Kingma et al. (2016)). It is an especially suited model if x is high dimensional or has highly nonlinear dependent elements. Therefore, the VAE is oftenly used for tasks like density estimation, data generation, data interpolation (White (2016)), outlier and anomaly detection (An & Cho (2015); Xu et al. (2018)) or clustering (Jiang et al. (2016); Dilokthanakul et al. (2016)). As shown in Fig. 1, the VAE is an easy latent variable model, where the observations x ∼ p(x|z) are dependent on latent variables z ∼ p(z).

authors:
Jinwon An
Sungzoon Cho

title: Variational autoencoder based anomaly detection using reconstruction

authors:
Yoshua Bengio
Nicholas Léonard
Aaron C. Courville

title: Estimating or propagating gradients through stochastic neurons for conditional computation

authors:
Xi Chen
Yan Duan
Rein Houthooft
John Schulman
Ilya Sutskever
Pieter Abbeel

title: Infogan: Interpretable representation learning by information maximizing generative adversarial nets

authors:
Nat Dilokthanakul
Pedro A.M. Mediano
Marta Garnelo
Matthew C.H. Lee
Hugh Salimbeni
Kai Arulkumaran
Murray Shanahan

title: Deep unsupervised clustering with gaussian mixture variational autoencoders

authors:
Zhuxi Jiang
Yin Zheng
Huachun Tan
Bangsheng Tang
Hanning Zhou

title: Variational deep embedding: A generative approach to clustering

authors:
D. P Kingma
M. Welling

title: Auto-Encoding Variational Bayes

authors:
Diederik P. Kingma
Tim Salimans
Max Welling

title: Improving variational inference with inverse autoregressive flow

authors: Corinna Cortes. MNIST handwritten digit database.

title: URL http://yann

authors:
V.E. Liong
Jiwen Lu
Gang Wang
P. Moulin
Jie Zhou

title: Deep hashing for compact binary codes learning

venue: In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Aäron van den Oord
Oriol Vinyals
Koray Kavukcuoglu

title: Neural discrete representation learning

title: Sampling generative networks: Notes on a few effective techniques

authors:
Han Xiao
Kashif Rasul
Roland Vollgraf

title: Fashion-mnist: a novel image dataset for benchmarking machine learning

venue: algorithms. CoRR,

authors:
Haowen Xu
Wenxiao Chen
Nengwen Zhao
Zeyan Li
Jiahao Bu
Zhihan Li
Ying Liu
Youjian Zhao
Dan Pei
Yang Feng
Jie Chen
Zhaogang Wang
Honglin Qiao

title: Unsupervised anomaly detection via variational auto-encoder for seasonal kpis in web applications

heading: 1 THE VARIATIONAL AUTO ENCODER

text:
The variational auto encoder (VAE) is a generative model which it is trained to approximate the true data generating distribution p(x) of an observed random vector x from a given training set D = {x1, ...,xN} (Kingma & Welling (2013); Kingma et al. (2016)). It is an especially suited model if x is high dimensional or has highly nonlinear dependent elements. Therefore, the VAE is oftenly used for tasks like density estimation, data generation, data interpolation (White (2016)), outlier and anomaly detection (An & Cho (2015); Xu et al. (2018)) or clustering (Jiang et al. (2016); Dilokthanakul et al. (2016)).
As shown in Fig. 1, the VAE is an easy latent variable model, where the observations x ∼ p(x|z) are dependent on latent variables z ∼ p(z).
During training, the VAE maximizes the probability p(x) to observe the data x. Therefore, the negative evidence lower bound (ELBO)
L(θ) = −Eq(z|x) [ln p(x|z)] + DKL(q(z|x)||p(z)) (1) ≥ − ln p(x) + DKL(q(z|x)||p(z|x)) (2)
is minimized, where p(z|x) = p(x|z)p(z)/ ∫ p(x|z)p(z)dz is the true but intractable posterior distribution the model assigns to z, q(z|x) is the corresponding tractable variational approximation and DKL(q(z|x)||p(z|x)) is the Kullback-Leibler (KL) divergence between p(z|x) and q(z|x). Because DKL(q(z|x)||p(z|x)) > 0, minimizing L(θ) means to maximize the probability p(x) the model assigns to observations x. Therefore, DKL(q(z|x)||p(z|x)) must be as as close as possible to 0, meaning that after training q(z|x) is a very good approximation of the true posterior p(z|x).
Kingma & Welling (2013) proposed to minimize L(θ), using stochastic gradient descent on a training data set, which they called Stochastic Gradient Variational Bayes (SGVB).
The VAE uses parametric distributions that are parametrized by an encoder network with parameters θE and a decoder network with parameters θD for both q(z|x) and p(x|z), respectively. This leads to the well known encoder-decoder structure in Fig. 2. The data likelihood is a distribution with mean x̂, that is the output of the decoder network. Further, we assume in this paper, that the variational posterior q(z|x) is a distribution from the exponential family
q(z|x) = exp(ηT (x;θE)T (z)−A(η(x;θE))) (3) with natural parameters η(x;θE), sufficient statistic T (z) and log partition function A(η(x;θE)). This gives us the flexibility to study training with different q(z|x) in the same mathematical framework. As shown in Fig. 2, the natural parameters η are the output of the encoder network, where we drop the arguments x,θE for shorter notations in the remainder of the paper.
The conventional VAE proposed in (Kingma & Welling (2013); Kingma et al. (2016)) learns continuous latent representations z ∈ Rc. It uses i.i.d. Gaussian distributed z, meaning that η = [µ1/σ 2 1 ,−1/(2σ21), ..., µc/σ2c ,−1/(2σ2c )]T , T (z) = [z1, z21 , ..., zc, z2c ]T and A(η) is chosen such that q(z|x) integrates to one. The likelihood is also Gaussian, with p(x|z) ∼ N(x̂,1). But in many applications learning discrete rather than continuous representations is advantageous. Binary representations z ∈ {0, 1}c can for example be used very efficiently for hashing, what is a powerful method for large-scale visual search (Liong et al. (2015)). Learning Categorical representations z ∈ {e1, ..., ec} is interesting, because this naturally lead to clustering of the data x, as shown in the experiments. Further, for both binary and categorical z it is easy to find entropy based heuristics to choose the size of the latent space, because the entropy is bounded for discrete z.
However, training VAEs with discrete latent representations is problematic, since standard SGVB can not be applied for optimization. Because SGVB is a gradient based method, we need to calculate the derivative of the two cost terms with respect to the encoder and decoder parameters
∂
∂θ LKL(θ) =
∂
∂θ DKL(q(z|x)||p(z)) (4)
∂
∂θ LL(θ) =
∂
∂θ Eq(z|x) [ln p(x|z)] , (5)
where LKL(θ) only depends on the encoder parameters and the expected log likelihood term LL(θ) depends on both encoder and decoder parameters. For a suited choice of p(z) and q(z|x), LKL(θ) can be calculated in closed form. However, LL(θ) contains an expectation over z ∼ q(z|x) that has to be estimated during training. A good estimator L̂L(θ) for LD(θ) that is unbiased, differentiable with respect to θ and that has low variance is the key to train VAEs. SGVB uses an estimator L̂RL(θ) that is based on reparametrization of q(z|x) and sampling (Kingma & Welling (2013)). However, as described in section 2, this method places many restrictions on the form of q(z|x) and fails if q(z|x) can not be reparametrized. This is the case if z is discrete, for example.
In this paper, we propose a simple and differentiable estimator L̂IL(θ) for LL(θ) that is based on importance sampling. Because no reparametrization is needed, it can be used to train VAEs with binary or categorical latent representations. Compared to previously proposed methods like the Vector Quantised-Variational Auto Encoder (VQ-VAE) (van den Oord et al. (2017)), which is based on a straight-through estimator for the gradient of LL(θ) (Bengio et al. (2013)), our proposed estimator has two advantages. It is unbiased and its variance approaches zero the closer we are to the optimum.

heading: 2 ESTIMATING THE EXPECTED LOG-LIKELIHOOD WITH REPARAMETRIZED SAMPLING

text:
The standard estimator L̂RL(θ) proposed in Kingma & Welling (2013) is based on reparametrized sampling
∂
∂θ LL(θ) =
∂
∂θ Eq(z|x) [ln p(x|z)] (6)
= ∂
∂θ Ep( ) [ln p(x|z = f( ,θ))] (7)
≈ ∂ ∂θ 1 M M∑ m=1 ln p(x|z = f( m,θ)) (8)
= ∂
∂θ L̂RL(θ) (9)
where is a random variable with the distribution p( ), m are samples from this distribution and f( ,θ) is a reparametrization function, such that z = f( ,θ) ∼ q(z|x). This estimator can be used to train VAEs with SGVB if two conditions are fulfilled: I) There exists a distribution p( ) and a reparametrization function f( ,θ), such that z = f( ,θ) ∼ q(z|x). II) The derivative of Eq. 5 must exist. With Eq. 8, we obtain
∂
∂θ L̂RL(θ) =
1
M M∑ m=1 ∂ ∂z ln p(x|z = f( m,θ)) ∂ ∂θ z, (10)
meaning that both the reparametrization function f( ,θ) and ln p(x|z) must be differentiable with respect to z and θ, respectively, to allow direct backpropagation of the gradient through the reparametrized sampling operator. If these conditions are fulfilled, the gradient can flow directly from the output to the input layer of the VAE, as shown in Fig. 3. Distributions over discrete latent representations z can not be reparametrized this way. Therefore, this estimator can not be used to train VAEs with such representations.

heading: 3 ESTIMATING THE EXPECTED LOG-LIKELIHOOD WITH IMPORTANCE SAMPLING

text:
We propose an estimator L̂IL(θ) which is based on importance sampling and can also be used to train VAEs with binary or categorical latent representations z. Expanding Eq. 4 leads to
∂
∂θ LL(θ) =
∂
∂θ
∫ ln p(x|z)q(z|x)dz (11)
= ∂
∂θ
∫ ln p(x|z)q(z|x)
qI(z) qI(z)dz (12)
≈ ∂ ∂θ 1 M
( M∑
m=1
ln p(x|zm) q(zm|x) qI(zm)
) (13)
= ∂
∂θ L̂IL(θ), (14)
where qI(z) is an arbitrary distribution that is of the same form as q(z|x) which is independent from the parameters θ. zm ∼ qI(z) are samples from this distribution. The estimator computes a weighted sum of the log likelihood ln p(x|zm) with the weighting q(zm|x)/qI(z). The benefit is that the log likelihood ln p(x|zm) depends on the decoder parameters θD only and not on the encoder parameters θE whereas the weighting q(zm|x)/qI(z) depends only on θD and not on θE . Therefore, calculation of the gradient of L̂IL(θ) can be separated
∂
∂θ L̂IL(θ) =
[ ∂
∂θE L̂IL(θ),
∂
∂θD L̂IL(θ)
] , (15)
with
∂
∂θE L̂IL(θ) =
1
M M∑ m=1 ln p(x|zm) ∂ ∂θE q(zm|x) qI(zm)
(16)
∂
∂θD L̂IL(θ) =
1
M M∑ m=1 q(zm|x) qI(zm) ∂ ∂θD ln p(x|zm). (17)
As shown in Fig. 4, gradient backpropagation is split into two separate parts. ∂∂θD L̂ I L(θ) backpropagates the error ln p(x|z) from the output of the VAE to the sampling operator and ∂∂θE L̂ I L(θ) backpropagates the error q(z|x)qI(z) from the sampling operator to the input layer of the VAE.
Compared to L̂RL(θ), we do not need to find a differentiable reparametrization for q(z|x), because we do not propagate the gradient through the sampling operator. Therefore, L̂IL(θ) can also be used if no reparametrization function exists for q(z|x), e.g. if it is a Bernoulli or a Categorical distribution.
4 VAE WITH BERNOULLI DISTRIBUTED z (BVAE)
Assume the latent representation z has i.i.d. components that are Bernoulli distributed, i.e. both the variational posterior distribution q(z|x) and qI(z) have the form
q(z|x) = exp(ηT z−A(η)) (18) qI(z) = exp(ξ T z−A(ξ)), (19)
where z ∈ {0, 1}c, η = [ln(q1/(1 − q1)), ..., ln(qc/(1 − qc))] is the output vector of the encoder that contains the logits of the independent Bernoulli distributions and A(η) = 1T ln(1+ eη) are the corresponding log-partition functions.
Hence, Eq. 17 is
∂
∂θE L̂IL(θ) =
1
M M∑ m=1 ln p(x|zm) ∂ ∂η exp ( (η − ξ)T zm − (A(η)−A(ξ)) )( ∂ ∂θE η )
= 1
M M∑ m=1 ln p(x|zm) exp ( (η − ξ)T zm − (A(η)−A(ξ)) ) (z− q)T ( ∂ ∂θE η ) ,
where q = [q1, ..., qc]T = 11+e−η contains the probabilities q(zi = 1|x). The variance of the estimator L̂IL(θ) heavily depends on the choice of the natural parameters ξ of the distribution qI(z). We choose ξ = η, leading to a gradient of the very simple form
∂
∂θE L̂IL(θ) =
1
M M∑ m=1 ln p(x|zm) (zm − q)T ( ∂ ∂θE η ) . (20)
This estimator of the gradient has two desirable properties for training, which can be easily seen in the one dimensional case with z ∈ {0, 1}. The mean of the estimator is
EqI(z)
[ ∂
∂θE L̂IL(θ)
] = EqI(z) [ 1
M M∑ m=1 ln p(x|z) (zm − q) ( ∂ ∂θE η )] (21)
= q(1− q)(ln p(x|z = 1)− ln(p(x|z = 0)) ( ∂
∂θE η
) (22)
= ∂
∂θE LL(θ), (23)
meaning that the estimator is unbiased. Further, the variance of ∂∂θE L̂ I L(θ) reduces to zero, the closer q is to 0 or 1, because q(1− q)→ 0 and hence the variance of the estimator approaches 0. That is desirable, since there are only three interesting cases during training that are shown in Fig. 5:
(a) ln p(x|z = 0) = ln p(x|z = 1): In this case the expected log likelihood Eq(z|x) [ln p(x|z = 0)] = ln p(x|z = 0) we want to maximize is independent of the choice of q.
(b) ln p(x|z = 0) > ln p(x|z = 1): In this case the expected log likelihood Eq(z|x) [ln p(x|z = 0)] = (1− q) ln p(x|z = 0)+ q ln p(x|z = 1) is maximized for q = 0.
(c) ln p(x|z = 0) < ln p(x|z = 1): In this case the expected log likelihood Eq(z|x) [ln p(x|z = 0)] = (1− q) ln p(x|z = 0)+ q ln p(x|z = 1) is maximized for q = 1.
This means, that the only candidate points that maximize the log likelihood are q = 0 or q = 1 lie near q(z = 1|x) = 0/1. Therefore, the longer we train, the more accurate the gradient estimate will be.
5 VAE WITH CATEGORICALLY DISTRIBUTED z (CVAE)
For Categorically distributed z both the variational posterior distribution q(z|x) and qI(z), again have the form
q(z|x) = exp(ηT z−A(η)) (24) qI(z) = exp(ξ T z−A(ξ)), (25)
but now z ∈ {e1, ..., ec} can assume only c different values. The vector of natural parameters is η = [ln(p1/pc), ..., ln(pc−1/pc), 0)] and the log partition function is A(η) = ln1T eη .
With the formulas above, we arrive at the same easy form of the expected gradient of the log likelihood
∂
∂θE L̂IL(θ) =
1
M M∑ m=1 ln p(x|zm) (zm − q)T ( ∂ ∂θE η ) , (26)
but now with q = softmax(η) that consists of the probabilities qi = q(z = ei), where ∑c i=1 qi = 1.

heading: 6 EXPERIMENTS

text:
In the following section, we show our preliminary experiments on the MNIST and Fashion MNIST datasets LeCun & Cortes (2010); Xiao et al. (2017). Two different kinds of VAEs have been evaluated:
1. The BVAE with Bernoulli distributed z ∈ {0, 1}c. 2. The CVAE with Categorically distributed z ∈ {e1, ..., ec}.
To train both architectures, the estimator L̂IL(θ) derived in Sec. 5 is used. Both BVAE and CVAE are tested with two different architectures given in Tab. 1. The fully connected architecture has 2 dense encoder and decoder layers. The encoder and decoder networks of the convolutional architecture consist of 4 convolutional layers and one dense layer each.
In our first experiment we train a FC BVAE with c = 50, i.e. z ∈ {0, 1}50 and a FC CVAE with c = 100, i.e. z ∈ {z1, ..., z100}. We train them for 300 epochs on the MNIST dataset, using
SGVB with our proposed estimator L̂IL(θ), to estimate the expected log likelihood, and ADAM as optimizer. Fig. 6 shows the convergence of the loss, the log likelihood the VAEs assign to the training data ln p(x|z) and the variance of the estimator L̂IL(θ), for a learning rate of 1e − 3 and a batch size of 2048. During training, the loss decreases steadily without oscillation. We observe that the variance of the estimator L̂IL(θ) decreases the longer we train and the closer we get to the optimum. This is consistent with our theoretically considerations in Sec. 4. The results of the corresponding simulations with the CNN BVAE and the CNN CVAE are shown in Fig. 9, in the appendix.
The performance of the FC CVAE is worse than the performance of the FC BVAE. Training converges to a lower log likelihood ln p(x|z), because the maximal information content HCV AE(z) ≤ ln(100) of the latent variables of the FC CVAE is much less than the maximal information content HBV AE(z) ≤ c ln(2) of the latent variables of the FC BVAE. The FC CVAE can at maximum learn to generate 100 different handwritten digits, what is a small number compared to the 250 different images that the FC CVAE can learn to generate.
Fig. 7 shows handwritten digits that are generated by the FC BVAE and the FC CVAE if we sample z from the variational posterior q(z|x). To draw samples from q(z|x), we feed test data which has not been seen during training to the encoders. The test data is shown in Fig. 7a and Fig. 7c. The corresponding reconstructions generated by the decoders are shown in Fig. 7b and Fig. 7d. Both input and reconstructed images are very similar in case of the FC BVAE, meaning that it can approximate the data generating distribution p(x) well. However, in case of the FC CVAE, the generated are blurry and look very different than the input of the encoder. In some cases, the class of the generated digit is even flipped. This happens because of the the very limited model capacity. Similar results for the CNN BVAE and CNN CVAE are shown in Fig. 10 in the appendix.
Fig. 8a shows generated images of the FC BVAE if we sample z ∼ p(z) from the prior distribution. A few generated images look like templates of handwritten digits and the remaining generated images seem to resemble mixtures of different digits. This is similar to the behaviour of a VAE with continuous latent variables, where we can interpolate between or generate mixtures of different
digits by traveling through the latent space Kingma & Welling (2013). However, in comparison to VAEs with continuous latent variables, we can only generate discrete mixtures for VAEs if the latent variables z are Bernoulli.
Fig. 8b shows generated images of the FC CVAE if we sample z ∼ p(z) from the prior distribution. Since the FC CVAE can only learn to generate 100 different images, its decoder learns to generate template images that fit well to all the training images. We observe that some latent representations are decoded to meaningless patterns that just fit well to the data in avarage. However, the decoder also learned to generate at least one template image for each class of handwritten digits. Hence, the categorical latent representation can be interpreted as the cluster affiliation and the encoder of the FC CVAE automatically learns to cluster the data. Similar results for the CNN BVAE and CNN CVAE are shown in Fig. 11 in the appendix.
A major drawback of the FC CVAE is, that the latent space of the FC CVAE can encode only very little information and thus its generative capabilites are poor. However, we think that they can be increased considerably if we allow a hybrid latent space with some continuous latent variables, as proposed in Chen et al. (2016). This could lead to a powerfull model for nonlinear clustering.

heading: 7 CONCLUSION

text: In this paper, we derived an easy estimator for the ELBO, which does not rely on reparametrized sampling and therefore can be used to obtain differentiable estimates, even if reparametrization is not possible, e.g. if the latent variables z are Bernoulli or Categorically distributed. We have shown theoretically and in experiments, close to the optimal parameter configuration, the variance of the estimator approaches zero. This is a very desirable property for training.

heading: B RESULTS FOR CNN BVAE ON FASHION MNIST

text: As shown in Fig. 12, the gradient variance approaches 0, the closer we get to the optimum. This is the same behaviour as for the MNIST dataset. As shown in Fig. 13, the FC BVAE can correctly reconstruct the shape of the given clothes with high accuracy. However, details like texture are lost. This is due to the limited model capacity, i.e. the latent representation z ∈ {0, 1}50 of the given VAE can at most encode 50Bits of information.


summaries: Authors propose a novel combination of RBM feature extractor and CNN classifiers to gain robustness toward adversarial attacks. They first train a small mean field boltzmann machine on 4x4 patches of MNIST, then combine 4 of these into a larger 8x8 feature extractor. Authors use the RBM 8x8 feature representation as a fixed convolutional layer and train a CNN on top of it. The intuition behind the idea is that since RBMs are generative, the RBM layer will act as a denoiser.

summaries: The recent work of Schott et al (which the authors compare results to) proposed the use of Bayes rule inversion as a more robust mechanism for classification under different types of adversarial attacks. The probabilities are approximated with variational autoencoders. During training the inference network is used, but during testing optimization based inference is carried out to compute loglikelihoods.

abstractText: We train a feed forward neural network with increased robustness against adversarial attacks compared to conventional training approaches. This is achieved using a novel pre-trained building block based on a mean field description of a Boltzmann machine. On the MNIST dataset the method achieves strong adversarial resistance without data augmentation or adversarial training. We show that the increased adversarial resistance is correlated with the generative performance of the underlying Boltzmann machine.

authors:
Battista Biggio
Fabio Roli

title: Wild patterns: Ten years after the rise of adversarial machine learning

venue: Pattern Recognition,

authors:
Wieland Brendel
Jonas Rauber
Matthias Bethge

title: Decision-based adversarial attacks: Reliable attacks against black-box machine learning models

title: Training Restricted Boltzmann Machines Using High-Temperature Expansions

authors:
Marylou Gabrié
Eric W. Tramel
Florent Krzakala

title: Training restricted boltzmann machines via the thouless-anderson-palmer free energy

authors:
A Georges
J S Yedidia

title: How to expand around mean-field theory using high-temperature expansions

venue: J. Phys. A. Math. Gen.,

authors:
Shixiang Gu
Luca Rigazio

title: Towards deep neural network architectures robust to adversarial examples

authors:
Geoffrey E. Hinton
Geoffrey E

title: Training Products of Experts by Minimizing Contrastive Divergence

venue: Neural Comput.,

authors:
Geoffrey E. Hinton
Simon Osindero
Yee-Whye Teh

title: A Fast Learning Algorithm for Deep Belief Nets

authors: Moritz Helias. Expansion of the effective action around non-Gaussian theories.

title: ISSN 1751-8113

authors:
Alexey Kurakin
Ian J. Goodfellow
Samy Bengio
Yinpeng Dong
Fangzhou Liao
Ming Liang
Tianyu Pang
Jun Zhu
Xiaolin Hu
Cihang Xie
Jianyu Wang
Zhishuai Zhang
Zhou Ren
Alan L. Yuille
Sangxia Huang
Yao Zhao
Yuzhe Zhao
Zhonglin Han
Junjiajia Long
Yerkebulan Berdibekov
Takuya Akiba
Seiya Tokui
Motoki Abe

title: Adversarial attacks and defences

venue: competition. CoRR,

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Omar Fawzi
Pascal Frossard

title: Universal adversarial perturbations

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Seyed-Mohsen Moosavi-Dezfooli
Ashish Shrivastava
Oncel Tuzel

title: Divide, denoise, and defend against adversarial attacks

authors:
Mohammad Norouzi
Mani Ranjbar
Greg Mori

title: Stacks of convolutional restricted boltzmann machines for shift-invariant feature learning

venue: IEEE Computer Society Conference on Computer Vision and Pattern Recognition

authors:
L. Schott
J. Rauber
W. Brendel
M. Bethge

title: Towards the first adversarially robust neural network model on mnist

authors:
low
Rob Fergus

title: Intriguing properties of neural networks

heading: 1 INTRODUCTION

text:
In an adversarial attack on a classification system one seeks inputs that lie very close (according to some norm or measure) to a regular input, but give a completely different classification result. Adversarial attacks on machine learning systems have been studied for over a decade, starting from the study of attacks on spam filtering systems (for a historical review see Biggio and Roli (2018)). Adversarial attacks on deep learning image recognition models have first been discussed by Szegedy et al. (2013). In addition to highlighting security implications adversarial images have acquired a new meaning in this context, presenting us with a fundamental conundrum: How can deep learning systems succesfully generalise and at the same time be extremely vulnerable to minute changes in the input? The topic of adversarial images in neural nets has been studied intensely with attacks and defences leapfrogging each other (for an overview see Kurakin et al. (2018)). All common neural network models suffer from susceptibility to adversarial attacks. It has even been shown by Moosavi-Dezfooli et al. (2017) that adversarial attack patterns can be transferred between different models, suggesting some common underlying mechanism. Despite the intense study of the subject a solution remains elusive, with Jetley et al. (2018) suggesting that classification performance and vulnerability to adversarial attacks are correlated, while Gilmer et al. (2018) present evidence for the opposite in a simple model. The difficulty in finding neural networks robust against adversarial attacks suggest that the standard discriminative neural network training procedure and the resulting networks’ vulnerability are linked. Making use of generative methods (e.g variational autoencoders, introduced in this context by Gu and Rigazio (2014)) has resulted in creating the most adversarially robust classifications but with added computational cost at inference time (Schott et al. (2018)). Another state of the art approach to increasing adversarial resistance applies denoising to image patches to achieve strong robustness (Moosavi-Dezfooli et al. (2018)).
In this article we concentrate on one common generative model, Boltzmann machines, and the impact of its use on adversarial resistance. We examine the adversarial resistance on the standard MNIST dataset. Boltzmann machines are a stochastic model with binary units (see e.g. Hinton (2007)). A number of “hidden” units form a model for the data distribution over the “visible” units. In a classification scenario one would fix the visible units and use the probability distribution over the hidden units for further processing. In a restricted Boltzmann machine the hidden units are independent and therefore the distribution over the hidden units in a classification scenario becomes a product distribution fully characterised by the average values of the individual hidden units. Pretraining using restricted Boltzmann machines has been used in early neural networks (Hinton et al. (2006)) but was abandoned as it became clear that good training can be achieved without it. Here we follow a slightly different path. We will use a Boltzmann machine to model image patches only. We do the modelling in a hierarchical fashion: train one Boltzmann machine for small image patches,
then add more hidden units to model the joint distribution over larger patches, similar to the stacked RBM approach of Norouzi et al. (2009). This forces us to depart from a simple restricted Boltzmann machine model and therefore we cannot obtain the hidden probability distribution as easily as for a restricted Boltzmann machine. Extended mean field methods developed for the description of spin glasses in physics (Thouless et al. (1977); Georges and Yedidia (1991); Kühn and Helias (2017)) have been applied succesfully to train a restricted Boltzmann machine by Gabrié et al. (2015) and Budzianowski (2016). We use these methods to arrive at a description of the hidden units in terms of their average values, where now we replace the single neural network layer resulting from the restricted Boltzmann machine with a many-layer iteration derived from the mean field description. This pre-trained building block can be used as a fixed input layer in a neural network trained in the usual discriminatory fashion.
In summary the contributions of this article are as follows:
• We construct a new neural network building block, based on the mean field description of a Boltzmann machine. The result is a deep feed forward neural network with shared weights and a structure derived from the energy function of the underlying Boltzmann machine.
• We use this building block in a neural network to achieve state of the art resistance to adversarial attacks on MNIST and show a correlation between the loss function of the Boltzmann machine (i.e. it’s generative capability) and the adversarial resistance of the resulting neural network.
• We show that the function mapping visible unit inputs to hidden unit outputs implemented by the new building block is strongly dependent on the input. A ball of random distortions around a training example gets mapped to a smaller output volume compared to the same mapping starting from a random input.

heading: 2 BOLTZMANN MACHINES AS FEATURE EXTRACTORS

text:
Let us review the the mean field description of a Boltzmann machine (Budzianowski (2016); Gabrié et al. (2015)). Boltzmann machines are stochastic, energy based models derived from the statistical physics of interacting spins. Boltzmann machines are a generative model, the generated probability distribution being the thermal equilibrium probability distribution over all possible spin combinations s = (s1, s2, . . . , sN ) with sn = ±1, as determined by the energy function through its parameters θ = (b, J)
E(θ, s) = s · J · s+ b · s, so that the probability of realising the configuration s is proportional to the Boltzmann factor
p(θ, s) ∝ e−E(θ,s).
The spins are divided into two sets, the visible units v and the hidden units h. When training a Boltzmann machine we want to generate a target probability distribution p0(v) over the visible units, as defined by example configurations v(0)j , j = 1, . . . , nJ . This can be achieved by adjusting the parameters of the energy function to minimise the relative entropy between the marginal distribution over the visible units
p(v,θ) = Trh p(v,h,θ).
and the target distribution:
D(p0||p) = nJ∑ j=1 p0(v (0) j ) log p0(v (0) j )− p0(v (0) j ) log p(θ,v (0) j ). (1)
The gradient of the relative entropy with respect to the parameters of the energy function θ can be expressed in terms of expectation values of spins
dD(p0||p) dbk = nJ∑ j=1 p0(v (0) j ) p(θ,v (0) j ) 〈sk〉C(j) − 〈sk〉F , (2)
and spin-spin correlators
dD(p0||p) dJkl = nJ∑ j=1 p0(v (0) j ) p(θ,v (0) j ) 〈sksl〉C(j) − 〈sksl〉F , (3)
where 〈. . .〉F denotes the expectation value of the model without constraints (free) and 〈. . .〉C(j) the expectation value if the visible units are fixed to example vj (clamped). This gradient can be used in a first order optimisation method to arrive at an optimal parameter configuration θ0. While the expression for the gradient looks simple, evaluating the probabilities and expectation values is not, and some approximation scheme needs to be used. Two schemes are usually used, one based on sampling (Hinton and E. (2002)), the other one based on a mean field approximation. Here we will concentrate on the mean field approximation.
The central quantity in mean field theory is the free energy. We can obtain the free energy of our model as an expansion in the order of the coupling J as derived by a number of authors (Georges and Yedidia (1991); Kühn and Helias (2017)).
F = ∑ n Fn
To lowest order the free energy is given by the entropy of independent spins.
F0 = N∑ i=1 ( 1−mi 2 ) log ( 1−mi 2 ) + ( 1 +mi 2 ) log ( 1 +mi 2 ) ,
where mi is the magnetisation of spin i. Up to second order we obtain F1 = ∑ 〈ij〉 Jijmimj + ∑ i bimi,
F2 = ∑ 〈ij〉 J2ij ( 1−m2i ) ( 1−m2j ) ,
where the notation 〈ij〉 denotes summation over unequal indices. For orders up to four see appendix A. From the free energy we can derive an equation to obtain the mean field values mi in the approximation up to order N
mi = tanh
( N∑
n=1
R (n) i
) (4)
with
R (n) i = dFn dmi .
In particular, the first two orders are
R (1) i = bi + 2 ∑ j Jijmj
and R
(2) i = −4mi ∑ j J2ij(1−m2j ).
Higher orders can be found in the appendix A. In the free case, the transcendental equation, Eq. 4 can be solved by iteration, starting from zero or random magnetisations, until the magnetisations converge. In the clamped case we keep the visible magnetisations fixed, while iterating over the hidden units. This results in two sets of distinct magnetisations: the free magnetisations mF and the clamped magnetisations mC(j), where example j is fixed on the visible units. We also get a set of corresponding free energies FF and FC(j). The correlation functions can be obtained from the free energies
〈sksl〉F/C(j) = 1
2 dFF/C(j) dJkl ,
and the expectation values are given directly by
〈sk〉F/C(j) = mF/C(j),k.
These expectation values can be inserted in the expressions for the gradient, Eqs. 2 and 3, and used to minimise the relative entropy Eq. 1. Probabilities can be estimated from the free energies
p(θ,v (0) j ) = e FC(j)−FF .
The training of a Boltzmann machine emphasises the main task of the machine as generating examples from the target distribution, but one can look at the machine from a different point of view: using the hidden units for constructing a model of the example data. The probability distribution over the hidden units if an example is fixed on the visible units then tells us something about the model required to describe the example. In a restricted Boltzmann machine (RBM) the probability distribution is a product distribution over the hidden units and features, but one can imagine introducing couplings between hidden units to account for correlations between individual features to arrive at a better/simpler description of the data. In the remaining article we will discuss machines that have bipartite connectivity between visible and hidden units and full connectivity between hidden units.
During inference we want to obtain the hidden magnetisations given the magnetisations of the visible units. We split the magnetisations into visible and hidden parts m = (mv,mh). Similarly we split the magnetic fields b = (0, bh) and the couplings
J = ( 0 W W Jh ) ,
where W now describes the bipartite connectivity between visible and hidden units and Jh the coupling between hidden units. Keeping terms to second order the mean field equations become
mh = tanh [ 2W ·mv + bh + 2Jh ·mh − 4mhJ2h · ( 1−m2h )] . (5)
Solving the mean field equation Eq. 5 requires iteration, e.g. starting from the initial magnetisations mh = 0. The iteration can be unrolled into an r layer neural network, where r is greater than the number of iterations necessary for convergence (see Fig. 1). We will refer to this neural network as the mean field Boltzmann network.

heading: 3 TRAINING THE MEAN FIELD BOLTZMANN NETWORK

text:
The Boltzmann machine underlying the mean field Boltzmann network is trained on data derived from the standard MNIST training set. We binarize the MNIST images with a threshold (50/255) and create two datasets. The first dataset contains 4 x 4 patches cut from the binarised images, the second contains 8 x 8 patches. We start by training a Boltzmann machine for the 4 x 4 patches. Of all 216 possible patches, 679 patches contain over 98% of all occurences in the dataset. We use these 679 to train a mean field Boltzmann machine with 32 hidden units (see Fig. 2). Four of
these trained small machines are then combined with 128 hidden units to model the 8 x 8 patches. The dataset of 8 x 8 patches contains approximately 600000 examples. For the calculation of the gradient we use batches of 10000 examples. To calculate the free expectation values we use the mean field expansion up to fourth order, for the clamped expectation values it suffices to go to second order. The magnetisations in the free case are calculated using 100 mean-field iterations, for the clamped magnetisation we use 20 iterations. In the late stage of the training the value for the free partition function is underestimated. This can lead to the sum of individual sample probabilities exceeding one. We adjust the free partition function in calculation of the relative entropy and the gradient so that the probabilities within one batch are normalised to one. Similar results to the staged training can be obtained by training a Boltzmann machine of identical connectivity directly on the 8x8 patches.

heading: 4 ADVERSARIALLY ROBUST NEURAL NETWORKS

text:
The trained mean field Boltzmann network constitutes a new neural network building block that takes in 8 x 8 patches and outputs a vector of 128 hidden magnetisations. This building block has identical input/output dimensions to a standard convolutional layer with 8 x 8 filter size and 128 filters. We can use this building block as an input layer in an identical fashion to a standard convolutional layer, sweeping it over the two input image dimensions. Starting from the 28 x 28 MNIST images, this results in an intermediate representation of 128 x 21 x 21 dimensions. On top of this representation we build a standard three layer convolutional neural network with ReLU activations. We add 3 convolution layers (kernel size 3 x 3, stride 2) with 128 filters, 64 filters and 32 filters, respectively, followed by a fully connected layer and a softmax function). The input
layer parameters are kept fixed during training and the remaining layers are trained in a standard discriminative fashion.
Let us establish the connection between better generative pre-training and increased adversarial resistance. We initialize the mean field Boltzmann network with parameters from various stages of the generative pre-training. As a measure for the generative training process we can use the relative entropy of the generated and target probability distribution, Eq. 1. To assess adversarial resistance we use an iterative gradient based (white box) method with L2 constraints and record the mean squared error for the first image iteration that is misclassified. We average the mean squared error for 1000 randomly chosen images from the MNIST test set. We also calculate the test error for the whole clean MNIST test set for a given neural network. The results are presented in Fig. 3. We see that a smaller relative entropy in the pre-training phase correlates with a higher adversarial resistance. For comparison we apply the same procedure to a standard LeNet network as well as a neural network where the mean field Boltzmann network is based on an RBM with 64 visible and 128 hidden units trained in the same mean field approximation. Both LeNet and RBM pre-trained network do not show the strong adversarial resistance observed in the neural network using the mean field Boltzmann network as input layer. On the other hand we see that the classification error of the robust neural network on the clean test set, while above the LeNet and RBM error, is independent of the pre-training. We find no evidence for a strong correlation of classification error and adversarial resistance in our model.
One reason for the apparent robustness of neural networks are obfuscated gradients (Athalye et al. (2018)). Therefore we also evaluate the robust network using a gradient free (black box) method: the Boundary Method (Brendel et al. (2017)), implemented in Foolbox. For evaluation we use the network that showed the highest adversarial resistance to the iterated gradient method. The Bound-
ary Method, using 1200 iterations, spherical_step=0.1 and otherwise default parameters achieves an average L2 distance of
We have added two more attacks to our evaluation. The first attack is a transfer attack using a gradient based method on LeNet to obtain a perturbation. The amplitude of the perturbation is then increased until the network under test misclassifies the image. The second attack is a random Gaussian noise attack, where the variance of the added noise is increased until the network under test misclassifies the image. Using all four attacks we can construct a compound attack as suggested by Schott et al. (2018) by considering the attack with the smallest L2 norm for each image. Combining all four attacks reduces the adversarial robustness below the robustness of any single attack.
Another reason for the apparent robustness of our model could be the very deep (20 layers) preprocessing stage leading to vanishing gradients. To investigate this further we remove the last, fully connected layer in our neural network and train a second, shallower network with the 32 x 6 x 6 dimensional activation data. The distilled network consists of 5 convolution layers: (8 x 8, stride 1, 256 filters), (1 x 1, stride 1, 256 filters), (3 x 3, stride 2, 128 filters, padding 1), (3 x 3, stride 2, 128 filters, padding 1), (3 x 3, stride 1, 32 filters, padding 1), with ReLU activations. Putting back the fully connected layer from the full network we can measure the adversarial resistance in the same way as earlier. We obtain an average L2 distance of 3.35 and an error rate over the clean dataset of 1.35%, compared to an average L2 distance of 3.9 for the original network. Although the distilled network is showing a loss of robustness, the average L2 distance is still more than twice than the average L2 distance for LeNet. This shows that some robustness can be transferred from the network structure used for learning to a relatively simple network and suggests that the robustness is not an artefact of a too deep network structure.
A comparison of our results with currently the most adversarially robust method, the Analysis By Synthesis (ABS) model of Schott et al. (2018), is shown in Tab. 1. For results from other methods see table 1 in Schott et al. (2018). Our model achieves comparable robustness results.

heading: 5 PROPERTIES OF MEAN FIELD BOLTZMANN NETWORKS

text: To understand the emerging adversarial robustness as a function of improved generative capability we examine the response of the mean field Boltzmann network around different input vectors. For one set of input vectors we will consider sample patterns from the training set, for the other set we select random binary patterns. We then add uniform random noise of amplitude to the input vectors and evaluate the different outputs of the network. The measure ∆r/t, presented in Fig. 4, is the L2 norm of the average difference of clean and noisy output of a set of 1000 random and training set patterns respectively with 10000 random noise patterns for each input pattern. Training set patterns are much more resistant to noise than random patterns and the resistance increases as the Boltzmann machine training progresses, particularly for small amplitude noise.

heading: 6 DISCUSSION

text:
We have shown that we can construct a feed forward neural network that shows strong adversarial resistance. This is achieved by incorporating a generatively pre-trained building block derived from the mean field description of a Boltzmann machine, which we called the mean field Boltzmann network. The resulting adversarial resistance strongly correlates with the effectiveness of the generative pre-training. We believe that the increased adversarial resistance can be traced to how the mean field Boltzmann network rejects noise around training example patches. The noise rejection does not happen for randomly selected examples. The rejection behaviour is an indication of the local non-linear behaviour of the mean field Boltzmann network. Compare this with the properties of a random matrix as feature extractor, where the restricted isometry property tells us that distances are preserved in the mapping with high probability. Too weak non-linearity of neural networks has been suggested as one reason for the existence of adversarial images and the increased non-linearity in our model correlates with increased adversarial resistance. On the level of individual image patches we can still find noise patterns that result in a large response when added to a training example, but they are much less likely. Take this together with the convolutional way that the mean field Boltzmann network is deployed. To get a large adversarial response from a given image region all overlapping image patches have to have a large response to the particular adversarial pattern. With the probability of large response supressed for one pattern, it becomes even smaller for all the overlapping pattern, resulting in strong adversarial resistance for the full neural network.
Our results, while encouraging, leave a number of questions open. First we have to ask ourselves if the success is due to the simplicity of the MNIST dataset. Will we be able to find typical image elements and model them with a Boltzmann machine for real image data? Second, while the adversarial images we find show a large deviation from the original image most do not resemble other image classes (for example images see appendix C). The algorithm still confidently places them in a particular class. We would prefer a behaviour where images unrecognisable by a human would result in a low confidence of the prediction.

heading: A HIGHER ORDER TERMS IN THE MEAN FIELD EXPANSION

text:
The third and fourth order term in the free energy becomes
F3 = ∑ 〈ijk〉 JijJjkJki ( 1−m2i ) ( 1−m2j ) ( 1−m2k ) + 8
3 ∑ 〈ij〉 J3ijmi ( 1−m2i ) mj ( 1−m2j ) ,
F4 = 2 ∑ 〈ijkl〉 JijJjkJklJli ( 1−m2i ) ( 1−m2j ) ( 1−m2k ) ( 1−m2l ) +
+ 16 ∑ 〈ijk〉 J2ijJikJkjmi ( 1−m2i ) mj ( 1−m2j ) ( 1−m2k ) − 2
3 ∑ 〈ij〉 J4ij ( 1−m2i ) ( 1−m2j ) ( 1 + 3m2i + 3m 2 j − 15m2im2j )
The third and fourth order terms for the mean field iteration are
R (3) i = −8 ∑ 〈jk〉 JijJjkJkimi ( 1−m2j ) ( 1−m2k ) + 2
3 ∑ j J3ij ( 1− 3m2i ) mj ( 1−m2j ) ,
R (4) i = −16 ∑ 〈jkl〉 JijJjkJklJlimi ( 1−m2j ) ( 1−m2k ) ( 1−m2l ) +
− 32 ∑ 〈jk〉 J2kjJijJkimimj ( 1−m2j ) mk ( 1−m2k ) + 32
∑ 〈jk〉 J2ijJkjJki ( 1− 3m2l ) mj ( 1−m2j ) ( 1−m2k ) − 16
3 ∑ j J4ijmi ( 1−m2j ) [ 1− 3m2i + 3m2j ( 5m2i − 3 )]

heading: B HISTOGRAMS OF L2 DISTANCES

heading: C EXAMPLE ADVERSARIAL IMAGES

heading: D MEAN FIELD TRAINING VS. EXACT SOLUTION

text:
For a very small Boltzmann machine we can examine how the mean field training procedure used in the main part of the article compares to the exact solution. We select a Boltzmann machine of 16 units, which we divide into 5 visible units and 11 hidden units. We choose the connectivity to have bipartite connections between visible and hidden units and full connectivity between the hidden units. To examine the training behaviour we choose two example states out of 32 possible input states, (1, -1, -1, -1, 1) and (-1, -1, 1, 1, -1), to be realised with equal probability. For the training we use the mean-field derived relative entropy and its gradient from section 2. First, we can examine how the relative entropies from the mean field approach and the exact calculation compare during the training procedure. The results are presented in Fig. 7a. For most of the training the mean field derived relative entropy tracks the exact entropy very closely, only to be underestimated towards the end of the training. This is due to the underestimation of the partition function / free energy, resulting in the overestimation of probabilities. The probabilities are presented in Figs. 7b, 7c and their ratio in Fig. 7d. We see that although the probabilities are overestimated, their ratio is reproduced almost exactly.
We can now consider the noise rejection property for the small machine, using the same procedure as in the main article. For this small machine we can calculate the averages over the input states for all possible combination. To evaluate the noise rejection we used 1000 random noise patterns for each example. The results are shown in Fig. 8 and show again the same noise rejection behaviour for the example states. In contrast, if we use a simple RBM connected machine of the same size, we don’t see any noise rejection behaviour (see Fig. 9).

title: IMPROVED RESISTANCE OF NEURAL NETWORKS TO ADVERSARIAL IMAGES THROUGH GENERATIVE PRE- TRAINING


summaries: Ullman et al. showed that slight changes in location or size of visible regions in minimal recognizable images can significantly impair human ability to recognize objects. This paper is a  follow-up of Ullman et al. paper, with focus on sensitivity of DNNs to certain regions in images. In other words, slight change of such regions’ size or location in the image can significantly affect DNN ability in recognizing them, even-though these changes are not noticeable for humans.

summaries: This paper is a more thorough follow-up to e a previous work by Ullman et al that was comparing minimally recognizable patches by humans compared to deep neural network. This paper exhibits that a wide range of architectures features the same fragility and that these effects can combated by better training methodology and different pooling architectures. Still even with those changes deep CNNs still posses more fragile behavior than human vision. One of my criticism is that human vision is kind of different: it makes multiple passes over the same images at multiple scales, so this might contribute significantly to these differences. Still this paper makes a lot of interesting observations and analyses and represents a first methodological study of this phenomenon.

abstractText: The human ability to recognize objects is impaired when the object is not shown in full. "Minimal images" are the smallest regions of an image that remain recognizable for humans. Ullman et al. (2016) show that a slight modification of the location and size of the visible region of the minimal image produces a sharp drop in human recognition accuracy. In this paper, we demonstrate that such drops in accuracy due to changes of the visible region are a common phenomenon between humans and existing state-of-the-art deep neural networks (DNNs), and are much more prominent in DNNs. We found many cases where DNNs classified one region correctly and the other incorrectly, though they only differed by one row or column of pixels, and were often bigger than the average human minimal image size. We show that this phenomenon is independent from previous works that have reported lack of invariance to minor modifications in object location in DNNs. Our results thus reveal a new failure mode of DNNs that also affects humans to a much lesser degree. They expose how fragile DNN recognition ability is for natural images even without adversarial patterns being introduced. Bringing the robustness of DNNs in natural images to the human level remains an open challenge for the community.

authors:
Fabio Anselmi
Lorenzo Rosasco
Tomaso Poggio

title: On invariance and selectivity in representation learning

venue: arXiv preprint arXiv:1503.05938v1,

authors:
Aharon Azulay
Yair Weiss

title: Why do deep convolutional networks generalize so poorly to small image transformations

venue: arXiv preprint arXiv:1805.12177,

authors:
Guy Ben-Yosef
Shimon Ullman

title: Image interpretation above and below the object level

venue: Journal of the Royal Society Interface Focus,

authors:
Michael Buhrmester
Tracy Kwang
Samuel D Gosling

title: Amazon’s mechanical turk: A new source of inexpensive, yet high-quality, data

venue: Perspectives on psychological science,

authors:
Francis X Chen
Gemma Roig
Leyla Isik
Xavier Boix
Tomaso Poggio

title: Eccentricity dependent deep neural networks: Modeling invariance in human

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Fei-Fei Li

title: Imagenet: a large-scale hierarchical image database

authors:
Gamaleldin F Elsayed
Shreya Shankar
Brian Cheung
Nicolas Papernot
Alex Kurakin
Ian Goodfellow
Jascha Sohl-Dickstein

title: Adversarial examples that fool both human and computer vision

venue: arXiv preprint arXiv:1802.08195,

authors:
Logan Engstrom
Dimitris Tsipras
Ludwig Schmidt
Aleksander Madry

title: A rotation and a translation suffice: Fooling cnns with simple transformations

venue: arXiv preprint arXiv:1712.02779,

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

title: Learning multiple layers of features from tiny images

venue: Technical report,

authors:
Yanpei Liu
Xinyun Chen
Chang Liu
Dawn Song

title: Delving into transferable adversarial examples and black-box attacks

venue: arXiv preprint arXiv:1611.02770,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: arXiv preprint arXiv:1706.06083,

authors:
Joseph Redmon
Ali Farhadi

title: Yolo9000: Better, faster, stronger

venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

venue: arXiv preprint arXiv:1312.6199,

authors:
Christian Szegedy
Wei Liu
Yangqing Jia
Pierre Sermanet
Scott Reed
Dragomir Anguelov
Dumitru Erhan
Vincent Vanhoucke
Andrew Rabinovich

title: Going deeper with convolutions

venue: arXiv preprint arXiv:1409.4842v1,

authors:
Florian Tramèr
Alexey Kurakin
Nicolas Papernot
Ian Goodfellow
Dan Boneh
Patrick McDaniel

title: Ensemble adversarial training: Attacks and defenses

venue: arXiv preprint arXiv:1705.07204,

authors:
Shimon Ullman
Liav Assif
Ethan Fetaya
Daniel Harari

title: Atoms of recognition in human and computer vision

venue: Proceedings of the National Academy of Sciences,

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

venue: arXiv preprint arXiv:1611.03530,

authors:
Zhuotun Zhu
Lingxi Xie
Alan L Yuille

title: Object recognition with and without objects

venue: arXiv preprint arXiv:1611.06596,

heading: 1 INTRODUCTION

text:
Deep neural networks (DNNs) have reached tremendous success in recognizing and localizing objects in images. The fundamental approach that led to DNNs consists of building artificial systems based on the brain and human vision. Yet in many important aspects, the capabilities of DNNs are inferior to those of human vision. A promising strand of research is to investigate the similarities and differences, and by bridging the gaps, further improve DNNs (Hassabis et al., 2017).
Studying cognitive biases and optical illusions is particularly revealing of the function of a visual system, whether natural or artificial. Ullman et al. (2016) present such a striking phenomenon of human vision, called "minimal images" (Ullman et al., 2016; Ben-Yosef et al., 2018; Ben-Yosef & Ullman, 2018). Minimal images are small regions of an image (e.g. 10x10 pixels) in which only a part of an object is observed, and a slight adjustment of the visible area produces a sharp drop in human recognition accuracy. Figure 1 provides examples of human minimal images.
Ullman et al. (2016) show that DNNs are unable to recognize human minimal images, and the DNN drop in accuracy for these minimal images is gradual rather than sharp. This begs the question of whether the sharp drop in accuracy for minimal images is a phenomenon exclusive to human vision, or there exist distinct but analogous images that produce a sharp drop in DNN accuracy.
In this paper, we provide evidence for the latter hypothesis by showing that there is a large set of analogs to minimal images that affect DNNs. These are different from the minimal images for humans in several aspects, namely region size and location, and frequency and sharpness of the drop in accuracy. We find that a slight adjustment of a one-pixel shift or two-pixel shrink of the visible
∗Equal Contribution
image region produces a drop in DNN recognition accuracy in many image regions. Figure 2 shows several examples of minimal image analogs of state-of-the-art DNNs.
The adjustments of the visible area that affect DNNs are almost indistinguishable to humans and can occur in larger regions than the “human minimal” region. To describe this phenomenon we introduce fragile recognition images (FRIs) for DNNs, which are more general than minimal images:
Fragile Recognition Image (FRI): A fragile recognition image is a region of an image for which a slight change of the region’s size or location in the image produces a large change in DNN recognition output.
This definition is more general than the definition of minimal images for humans, as the latter is included in the definition for DNNs. Minimal images are the case of fragile recognition in which the slight change is a reduction in the size of the region, and the minimal image is one of the smallest possible FRIs. In human vision, the more general definition of fragile recognition that we are introducing here is not useful because human minimal images appear only when the visible area of the object is small.
Object recognition
modelCabbage butterfly
Since FRIs are hardly distinguishable to humans but cause DNNs to fail, there is a connection with so-called adversarial examples presented by Szegedy et al. (2013). Adversarial examples are images with small synthetic perturbations that are imperceptible to humans, but produce a sharp drop in DNN recognition accuracy. There are several types, eg. (Goodfellow et al., 2014; Liu et al., 2016), and the strategies to alleviate them are not able to fully protect DNNs (Tramèr et al., 2017; Madry et al., 2017). Furthermore, humans may suffer from adversarial attacks; human recognition ability is shown to be impaired by perturbations under rapid image presentation (Elsayed et al., 2018). Unlike these adversarial examples, fragile recognition arise in natural images without introducing synthetic perturbation. This causes new concerns for use of DNNs in computer vision applications.
We evaluate FRIs in ImageNet (Deng et al., 2009) for state-of-the-art DNNs, specifically VGG16 (Simonyan & Zisserman, 2015), Inception (Szegedy et al., 2014), and ResNet (He et al., 2016). Results show that FRIs are abundant and can occur for any region size. Furthermore, we investigate whether fragile recognition is related to the lack of invariance to small changes in the object location, which has been recently reported in the literature to affect DNNs (Engstrom et al., 2017; Azulay & Weiss, 2018). Our results demonstrate that fragile recognition is independent from this phenomenon: bigger pooling regions reduce most of the lack of invariance to changes in object location, while pooling only marginally reduces fragile recognition. We also show that known strategies to increase network generalization, i.e. adding regularization and data augmentation, reduce the number of FRIs but still leave far more than humans have. These results highlight how much more fragile current DNN recognition ability is than human vision.

heading: 2 METHODS: EXTRACTING FRAGILE RECOGNITION IMAGES

text:
In this Section we introduce the method for extracting FRIs for DNNs. The method for extracting human minimal images employs a tree search strategy (Ullman et al., 2016). The full object is presented to human subjects and they are asked to recognize it. If at least 50% of subjects recognize it correctly, smaller crops of the object, called descendants, are tested. If any of the smaller region is recognizable, the crop size is further reduced and tested. Once an image crop is found such that it is recognizable and all of its descendants are not recognizable, it is considered a human minimal image.
Our FRI extraction method for DNNs relies on an exhaustive grid search. This is possible in DNNs due to parallelization across multiple GPUs, and would be prohibitively time-consuming to replicate with humans. The grid search consists on a two-step process: first, every possible square region is classified by the DNN and the correctness is annotated in the correctness map. From the correctness map, each region’s correctness is compared with the region’s slightly changed location or size in order to determine if there has been a change of the correctness. FRIs are regions that are classified correctly and a small change causes failure, as well as regions that are classified incorrectly and a small change causes success.
The two step process to detect FRIs is summarized in Figure 3. We now detail the two steps:
1. Correctness map generation. An exhaustive grid search is performed to see if each possible square image region of a fixed size is classified correctly by a given DNN. After extracting the
region from the image, the region is resized to be of the size required by the network. The region size is parametrized by P , which is defined as the proportion of the image occupied by the region, i.e. P = S/min(h,w) where h and w are the height and width of the input image, and S is the region’s side length. The results are arranged in a map such that a given map pixel contains the binary correctness for the square region centered at the corresponding pixel in the original image. The resulting map is of dimension (h− S)× (w − S) due to padding loss. The first two panels of Figure 3 show a visualization of the correctness map generation process.
2. Fragile recognition image (FRI) extraction from correctness maps. We define different variations of FRIs, depending if they are based on changes on the location or size of the image region, and on how strict we are when evaluating the changes in the correctness of DNN:
–Shift or Shrink: we define two types of "small changes" of the region that affect DNN correctness. "Shift" is a one-pixel translation of the region location; "shrink" is a two-pixel reduction of the region side length within the region’s original boundaries, in a fixed full image size.
–Strict or Loose: the visible region can be shifted in various directions, or shrunk in different ways while remaining within its original boundaries. "Loose" FRIs are regions such that there exists a small change that flip network correctness. "Strict" FRIs are regions such that network correctness is flipped for all small changes.
These definitions yield four fragile recognition types: loose shift, loose shrink, strict shift, and strict shrink. Note that strict shrink is the most analogous to human minimal images. The correctness maps are used to detect fragile recognition due to shifts by comparing neighbouring pixels in a correctness map, and due to shrinks by comparing correctness maps at two slightly different region sizes. We use fragile recognition image (FRI) maps to visually represent the result of the grid search that extracts FRIs. As shown in the FRI map of Figure 3, each pixel of the map indicates whether the corresponding window in the original image is an FRI. The second and third panel show a visualization of the FRI map generation process. Figure 4 shows an ImageNet image and each of its FRI maps.

heading: 3 FRAGILE RECOGNITION IMAGES OF STATE-OF-THE-ART DNNS

text:
In this Section, we will first discuss occurrence of fragile recognition for state-of-the-art object recognition models through results based on ImageNet (Deng et al., 2009). Then, we analyze if data
augmentation and regularization help reduce fragile recognition through experiments in CIFAR-10 Krizhevsky (2009).

heading: 3.1 FRAGILE RECOGNITION IMAGES FOR STATE-OF-THE-ART DNNS IN IMAGENET

text:
The following experiments are performed on 500 images, randomly sampled from ImageNet’s validation set, which consists of 50, 000 images and ground-truth object bound-in boxes (Deng et al., 2009). The images are sampled from 10 supercategories (dog, snake, monkey, fish, vegetable, musical instrument, boat, land vehicle, drinks, furniture), each of which covers a set of ImageNet categories. Correctness is measured as top-5 accuracy, which is commonly used in ImageNet. FRIs are extracted for three architectures: VGG-16 (Simonyan & Zisserman, 2015), Inception (Szegedy et al., 2014), and ResNet (He et al., 2016). Experiments are run in eight K80 NVIDIA GPUs. The exhaustive grid search takes about 5 minutes for one image using all eight GPUs. In the following paragraphs, we report the results of the experiments.
We evaluate how much a DNN is affected by fragile recognition by quantifying the proportion of possible image regions that are FRIs, i.e. we quantify the amount of regions affected by a shift or shrink. Recall that we consider a region to be an FRI when the classification changes from correct to incorrect, and also from incorrect to correct. As expected, we found that both of these cases are approximately equally probable under all tested conditions.
In Figure 5, we show the percentage of shrink FRIs in the image for a given region size, P ; in Figure A.1 we show the same for shift FRIs. All networks are significantly affected by FRIs, with ResNet being the most: almost one out of 50 regions of a size that covers almost the entire image (P = 80%) can affect ResNet. When the size of the image region is P = 20%, FRIs are even more frequent (8 times more), i.e. almost two out of 25 regions in the image is a loose FRI for ResNet.
Comparing Figure 5a and Figure 5b, we see that the proportion of strict FRIs is less than that of loose FRIs because of the more stringent definition. The results show that there are many regions in an image for which the network is very sensitive to slight changes in the region, eg. one out of 250 image regions of size P = 20% will be misclassified by ResNet when the region is slightly shrunk. Recall that strict shrink FRIs are the equivalent case of minimal images in humans. Thus, these results demonstrate the existence of many minimal images analogs in DNNs.
Note that smaller FRIs (lower P ) are much more frequent than larger ones, as observed across the different network architectures and types of FRIs. This trend is expected: one-pixel shifts and two-pixel shrinks are proportionally larger changes for smaller regions, and larger regions generally allow for more high-level features to be included.
We verified that FRIs are not an artifact of the algorithm that resizes the region to the size required by the DNN (224× 224 pixels for VGG-16). We took regions of side length 224 and removed any resizing before input, and we observed that this procedure produces the same results we reported.
Besides the qualitative examples in Figure 1 and Figure 2, we display a more varied set of qualitative examples in Figure A.10. We observe that FRIs are usually located within object boundaries but can also be found in the background. This is because DNNs are able to recognize regions that only contain background (Zhu et al., 2016), as they have been shown to exploit dataset biases.
In Figure A.9 we display the DNN’s output confidence in the true class for individual regions in map form. We see that sharp drops in confidence are frequent within an image, providing a basis for minimal images. Finally, in Figure A.11 we show qualitative examples of the activation maps at different layers of the DNN of the correctly classified crop and its shifted version. These examples show what we have observed in all cases: the activation maps are imperceptibly similar at the first layers but are clearly different at the last layers.
Finally, we show qualitative examples to illustrate that FRIs are a concern for computer vision systems based on similar DNNs architectures. We conducted a test on detection algorithms, to validate that FRIs dramatically affect both the location and the label of the detected objects. In Figure A.12 we show FRIs for the widely used object detector called “YOLO” (Redmon & Farhadi, 2017).

heading: 3.2 FRAGILE RECOGNITION WITH DATA AUGMENTATION AND REGULARIZATION

text:
We now investigate if data augmentation and regularization help alleviate fragile recognition. In this experiment we use the CIFAR-10 dataset (Krizhevsky, 2009), which contains 10 object categories, 50, 000 training images and 10, 000 testing images of size 32 × 32 pixels. The evaluation criteria is top-1 accuracy. We use CIFAR-10 for convenience and without loss of generality, since the data augmentation and regularization we test are used in the models tested in ImageNet.
We reproduce the AlexNet version for CIFAR-10 introduced by Zhang et al. (2016), which consists of two convolutional-pooling-normalization layers followed by two fully connected layers. In the following, all regularizers and data augmentation are turned off unless stated otherwise. We will analyze the impact of each to fragile recognition.
For data augmentation, we augment the training dataset with FRI regions of at least a given size. For regularizers, we add weight decay, dropout, and distortions (e.g. reflections, altered brightness, altered contrast). Both the data augmentation and the regularizers improve the accuracy of the DNN for the different crop sizes (Figure A.2). Figure 6 shows results for loose shift FRIs (see Figure A.3 for shrink FRIs); both data augmentation and regularization have a clear impact on FRI occurrence in all cases. The largest general improvement comes for the 12-pixel region size, as data augmentation and regularization both lead to decrease of more than 12% of FRIs. For regularizers specifically, dropout provides the most individual improvement. However, all of these generalization efforts still allow a high failure rate. They are also unable to bring the FRI effect to the human level, as the DNN FRIs are indistinguishable for humans. This is further discussed in Section 5.
In ImageNet, smaller region sizes lead to higher FRI occurrence. In CIFAR-10, FRI occurrence in very small regions (smaller than 20 pixels) decreases with size. This is because 12- and 16-pixel
regions are prohibitively small, so the number of correctly classified regions is severely reduced; consequently, there are fewer opportunities for FRIs to occur at all.

heading: 4 FRAGILE RECOGNITION IS NOT LACK OF OBJECT LOCATION INVARIANCE

text:
We now focus on the relationship of fragile recognition with recent works that show that DNNs are affected by small changes of the object location, scale and orientation (Engstrom et al., 2017; Azulay & Weiss, 2018). The phenomenon described in previous works is referred to as lack of invariance due to affine transformations of the object. Here, we focus only on location changes, as it will allow to distinguish FRIs and these previous works.
The procedure to evaluate location invariance is the following, quoting from Azulay & Weiss (2018): “we embed the original image in a larger image and shift it in the image plane (while filling in the rest of the image with a simple inpainting procedure)”. The embedding of the image can also be done with a black empty background as in (Engstrom et al., 2017), or using videos in which the background is static and only the object is moving (Azulay & Weiss, 2018). In fragile recognition, both the object and the background, i.e. the entire image, change due to the shift or shrink of the image region. In previous works, only the object changes location. We introduce an experiment that reveals that this subtle difference makes fragile recognition an independent and more complex phenomenon than lack of location invariance.
Pooling induces location invariance. DNN architectures with large pooling regions are known to induce invariance to the object location, cf. (Anselmi et al., 2015). A pooling layer operates independently for each feature by extracting the maximum activation across the spatial dimensions. For a pooling region of the same size as the full image, the network response is invariant to the object position within the image frame. This is under the assumption that there is enough spatial resolution in the responses in order to guarantee that the responses after the shift do not vary except for the shift. See (Azulay & Weiss, 2018) for a detailed explanation. Note that this assumption is not fulfilled in FRIs, as a shift of the image region introduces and removes patterns in the borders of the image, which can produce changes in the responses after pooling. We now show this experimentally.
Experimental results. We evaluate the network trained on CIFAR-10 and introduced in the previous section with different pooling region sizes for the second pooling layer. These sizes range from three pixels to the entire image; theoretically, this should produce full location invariance. In order to guarantee sufficient spatial resolution to obtain location invariance, we use a stride of one pixel for the convolutional layers and add padding. Adding larger pooling regions does not reduce network accuracy (see Figure A.5a), but as we show next, it massively reduces the lack of location invariance.
We evaluate the DNN by embedding the object in a black background at all possible locations, and we quantify for how many locations a one-pixel shift of the object location produces a change in the output of the DNN (similar to the method in Section 2). In this experiment we evaluate changes to the output label and not correctness, in order to accurately match the definition of invariance.
Figure 7a shows that as expected, the lack of invariance is dramatically reduced when using large pooling regions. For embedded 12-pixel images, 75% of the one-pixel shifts affect the network with small pooling regions, while only 10% of the one-pixel shifts affect the output of the network. Pooling is not completely location invariant due to boundary effects near the perimeter of the image. We show qualitative examples of this reduction in Figure A.7.
In Figure 7b, we see that increasing the pooling size only slightly decreases FRIs. The region size with a larger decrease is 12 pixels (note that the embedding size can not be directly compared with the region size of FRIs). For this region size, there are approximately 10% less FRIs, but a significant amount still remain (about 65% of the regions are FRIs). Since the pooling mechanisms that largely reduced the lack of invariance are not effective for fragile recognition, we can conclude that FRIs are a more complex phenomenon than lack of location invariance.
Note that for small region sizes the amount of FRIs increases, which is different from what we observe in the data augmentation and regularization experiment in the previous section. This is because in Figure 7b we report change in the output label rather than change in the correctness as in previous experiments. See Figure A.5b for the effect of pooling on FRI occurrence, which is in accordance to previous results.
Finally, we control that the differences we observe between lack of invariance and FRIs are not caused by use of zero-padding in one case and not the other. In Figure A.6, we evaluate FRIs with zero-padding instead of up-scaling the cropped region. The results support the same conclusions as for FRIs with up-scaling.

heading: 5 COMPARING FRAGILE RECOGNITION IN HUMANS AND DNNS

text:
In this section, we further compare the FRIs found for DNNs with the human minimal images found by Ullman et al. (2016). Recall that minimal images are equivalent to strict shrink FRIs of small size. Both humans and DNNs are susceptible to small image changes, but these two sets of fragile images are not necessarily the same in humans and in DNNs. As shown by Ullman et al. (2016); Ben-Yosef et al. (2018), when DNNs are trained and tested on human minimal images, i.e. images that humans can still recognize, DNNs are unable to recognize the objects.
Here we show the converse, namely that when humans are tested on DNN fragile recognition images, they do not exhibit the same fragile response. This can be seen in our qualitative examples: DNN fragile recognition images and their incorrectly-classified counterparts are difficult to distinguish. To verify this, we randomly sample 40 DNN shrink FRIs generated from ImageNet. We present the correctly-classified FRI and the slightly changed image (both resized to 100× 100 pixels) to separate groups of 20 subjects in Mechanical Turk (Buhrmester et al., 2011). The subjects annotate the images using one of our 10 supercategory labels. The results show a small gap in correct recognition: on average, success rates among humans for DNN fragile recognition images and incorrect counterparts differ by 14.5%. DNNs experience an average gap in confidence of 56% for the same pairs.
Furthermore, we directly compare human and DNN minimal images of the same image. We use six of the original images from Ullman et al. (2016) that were used to find human minimal images. We identify the DNN FRIs for these. Comparing DNN FRIs and human minimal images of the same region size, P , we find two additional differences: first, DNNs have more FRIs (5.3 minimal images per image for humans on average, 13.4 for DNNs). Second, DNN FRIs differ in location within the object region (Intersection Over Union between human minimal image maps and DNN FRI maps was small, < 6% for all tested images). For example, while human minimal images are centered in meaningful object parts (e.g. the eagle head and wing in Figure A.8 row 1, column 1), DNN FRIs contain mostly a background set of pixels (see Figure A.8 row 1, column 2).
Finally, we control that current DNNs architectures that are based on human vision are also severely affected by FRIs. This is shown in Figure A.4 for the recently introduced multi-scale eccentricity dependent DNN that mimics these aspects of human vision (Chen et al., 2017).

heading: 6 CONCLUSIONS

text: We have demonstrated that both humans and DNNs are affected by slight changes of the visible region. Since the human visual system also exhibits similar fragile recognition behavior, this might be expected or even desired. Our results have revealed that the fragile recognition level in humans is fundamentally different from the one in DNNs in terms of size, position and frequency. Furthermore, data augmentation, regularization and larger-size pooling regions alleviate fragile recongition in DNNs, but are not sufficient to close the gap with humans. Thus, making DNNs robust like humans remains a challenge for the community. Finally, we have shown that fragile recognition is a more complex phenomenon than object location invariance, which exposes new concerns of the recognition ability of DNNs in natural images, even without adversarial patterns being introduced.

heading: ACKNOWLEDGMENTS

text: We are grateful to Tomaso Poggio and Shimon Ullman for helpful feedback and discussions. This work is supported by the National Science Foundation Science and Technology Center Award CCF123121, the MIT-IBM Brain-Inspired Multimedia Comprehension project, and the MIT-Sensetime Alliance on Artificial Intelligence.

heading: A APPENDIX

text:
Loose shift FRIs; P = 0.2, ResNet
sturgeon pirate ship rocking chair
macaque accordion pool table
Loose shift FRIs; P = 0.6, ResNet
langur artichoke beer bottle
Loose shrink FRIs; P = 0.2, ResNet
Maltese terrier lionfish ocean liner
macaque barber chair Indian cobra
Loose shrink FRIs; P = 0.6, Resnet
boat paddle fire truck pirate ship
Loose shrink FRIs; P = 0.2, VGG-16

title: MINIMAL IMAGES IN DEEP NEURAL NETWORKS: FRAGILE OBJECT RECOGNITION IN NATURAL IMAGES