# Robust binary classification with the 01 loss

Yunzhe Xue  Meiyan Xie  Usman Roshan

###### Abstract

The 01 loss is robust to outliers and tolerant to noisy data compared to
convex loss functions. We conjecture that the 01 loss may also be more robust
to adversarial attacks. To study this empirically we have developed a
stochastic coordinate descent algorithm for a linear 01 loss classifier and a
single hidden layer 01 loss neural network. Due to the absence of the gradient
we iteratively update coordinates on random subsets of the data for fixed
epochs. We show our algorithms to be fast and comparable in accuracy to the
linear support vector machine and logistic loss single hidden layer network
for binary classification on several image benchmarks, thus establishing that
our method is on-par in test accuracy with convex losses. We then subject them
to accurately trained substitute model black box attacks on the same image
benchmarks and find them to be more robust than convex counterparts. On
CIFAR10 binary classification task between classes 0 and 1 with adversarial
perturbation of 0.0625 we see that the MLP01 network loses 27% in accuracy
whereas the MLP-logistic counterpart loses 83%. Similarly on STL10 and
ImageNet binary classification between classes 0 and 1 the MLP01 network loses
21% and 20% while MLP-logistic loses 67% and 45% respectively. On MNIST that
is a well-separable dataset we find MLP01 comparable to MLP-logistic and show
under simulation how and why our 01 loss solver is less robust there. We then
propose adversarial training for our linear 01 loss solver that significantly
improves its robustness on MNIST and all other datasets and retains clean test
accuracy. Finally we show practical applications of our method to deter
traffic sign and facial recognition adversarial attacks. We discuss attacks
with 01 loss, substitute model accuracy, and several future avenues like
multiclass, 01 loss convolutions, and further adversarial training.

##  1 Introduction

Adversarial attacks present a challenge to machine learning algorithms
typically based on convex losses. State of the art classifiers like the
support vector machine (Cortes & Vapnik, 1995) and neural networks (Krizhevsky
et al., 2012) achieve high accuracies on test data but are also vulnerable to
adversarial attacks based on minor perturbations in the data (Goodfellow et
al., 2014; Papernot et al., 2016b; Kurakin et al., 2016; Carlini & Wagner,
2017; Brendel et al., 2017). To counter adversarial attacks many defense
methods been proposed with adversarial training being the most popular
(Szegedy et al., 2013). This is known to improve model robustness but also
tends to lower accuracy on clean test data that has no perturbations
(Raghunathan et al., 2019; Zhang et al., 2019; Raghunathan et al., 2019).

The robustness of outliers to the 01 loss is well known (Bartlett et al.,
2004). Convex loss functions such as least squares are affected by both
correct and incorrectly classified outliers and hinge is affected by
incorrectly classified outliers whereas the 01 loss is robust to both (Xie et
al., 2019; Nguyen & Sanner, 2013). In addition to being robust to outliers the
01 loss is also robust to noise in the training data (Manwani & Sastry, 2013;
Ghosh et al., 2015) and under this loss minimizing the empirical risk amounts
to minimizing the empirical adversarial risk (Lyu & Tsang, 2019; Hu et al.,
2016) with certain assumptions of noise. We conjecture that these properties
may translate to robustness against black box adversarial attacks that
typically succeed in fooling state of the art classifiers (Papernot et al.,
2017).

To test this we first develop stochastic coordinate descent solvers for 01
loss based upon prior work (Xie et al., 2019). We also extend the previous
work to a non-linear single hidden layer 01 loss network that we call MLP01.
For the task of binary classification on standard image recognition benchmarks
we show that our linear 01 loss solver and the MLP01 loss are both as accurate
as their convex counterparts, namely the linear support vector machine and the
logistic loss single hidden layer network. We then subject all methods to a
substitute model black box attack (Papernot et al., 2017) and find both our 01
loss models (linear and non-linear) to be more robust than hinge and logistic.

We find that on separable image datasets like MNIST our model offers little
advantage and demonstrate under simulation why this happens. We then conduct
adversarial training of our linear model and show it increases its robustness
on MNIST and all other datasets while retaining clean test accuracy. We also
show applications to deter street sign and facial recognition adversarial
attacks. We describe below our methods followed by results and discussion.

##  2 Methods

###  2.1 Background

The problem of determining the hyperplane with minimum number of
misclassifications in a binary classification problem is known to be NP-hard
(Ben-David et al., 2003). In mainstream machine learning literature this is
called minimizing the 01 loss (Shai et al., 2011) as given in Objective 1,

$\frac{1}{2n}\operatorname*{arg\,min}_{w,w_{0}}\sum_{i}(1-sign(y_{i}(w^{T}x_{i}+w_{0})))$
(1)

where $w\in R^{d}$, $w_{0}\in R$ is our hyperplane solution, and $x_{i}\in
R^{d},y_{i}\in\\{+1,-1\\}.\forall i=0...n-1$ are our training data. Popular
linear classifiers such as the linear support vector machine, perceptron, and
logistic regression (Alpaydin, 2004) can be considered as convex
approximations to this problem that yield fast gradient descent solutions
(Bartlett et al., 2004). However, they are also more sensitive to outliers
than the 01 loss (Bartlett et al., 2004; Nguyen & Sanner, 2013; Xie et al.,
2019).

We extend the 01 loss to a simple single hidden layer neural network with $k$
hidden nodes and sign activation that we call the MLP01 loss. This objective
can be given as

$\small\frac{1}{2n}\operatorname*{arg\,min}_{W,W_{0},u,u_{0}}\sum_{i}(1-sign(y_{i}(u^{T}(sign(W^{T}x_{i}+W_{0}))+u_{0})))$
(2)

where $W\in R^{d\times k}$, $W_{0}\in R^{k}$ are the hidden layer parameters,
$u\in R^{k},u_{0}\in R$ are the final layer node parameters, $x_{i}\in
R^{d},y_{i}\in\\{+1,-1\\}.\forall i=0...n-1$ are our training data, and
$sign(v\in R^{k})=(sign(v_{0}),sign(v_{1}),...,sign(v_{k-1}))$.

We solve both problems with stochastic coordinate descent based upon earlier
work (Xie et al., 2019).

#### Other work on 01 loss solvers

Aside from the stochastic coordinate descent (Xie et al., 2019) that we build
upon other attempts have been made to optimize the 0/1 loss. These include
boosting (Zhai et al., 2013), integer programming (Tang et al., 2014), an
approximation algorithm (Shalev-Shwartz et al., 2011), a random coordinate
descent method (Li & Lin, 2007), and a branch and bound method that is the
most recent from 2013 (Nguyen & Sanner, 2013). The above previous works cover
various strategies to solve 01 loss but lack on-par test accuracy with convex
solvers on real data. We obtained a Matlab implementation of the branch and
bound method and found it to be slow - it did not finish after several hours
of runtime, as also cautioned by authors in their code. The random coordinate
descent code (Li & Lin, 2007) requires GNU C compiler (gcc) version 3.0 to
compile whereas current supported versions are above 4.0.

###  2.2 Stochastic coordinate descent (SCD01)

We use the stochastic coordinate descent for 01 loss (Xie et al., 2019) called
SCD01 to drive our linear and non-linear 01 loss solvers. In the Supplementary
Material we fully describe the algorithm for reference including the optimal
threshold algorithm. Briefly, we iteratively randomly select a subset of the
training data in each epoch and run coordinate descent in each iteration. Our
coordinate descent shown in Algorithm 1 differs from previous work in how we
update the coordinates. In previous work (Xie et al., 2019) authors update
each coordinate until there is no change in the objective. We randomly update
a pool of coordinates by one step and pick the one with the greatest decrease
in the objective (with ties decided randomly).

Algorithm 1 Coordinate descent

Input:  Data (feature vectors) $x_{i}\in R^{d}$ for $i=0..n-1$ with labels
$y_{i}\in\\{+1,-1\\}$, $w_{inc}\in R$ (set to 0.17 by default), size of pooled
features to update $k$ (set to 128 by default), vector $w\in R^{d}$ and
$w_{0}\in R$
Output:  Vector $w\in R^{d}$ and $w_{0}\in R$
Procedure:

1\. Initialization: If $w$ is null then let each feature $w_{i}$ of $w$ be
uniformly drawn from $(-1,1)$. We set $\|w\|=1$ and throughout our search
ensure that $\|w\|=1$ by renormalizing each time $w$ changes.

2\. Let the number of misclassified points with negative $w^{T}x_{i}$ be
$errorminus=0$ and those with positive $w^{T}x_{i}$ be $errorplus=0$. These
are later used in the Optimal Threshold algorithm called _Opt_ (see
Supplementary Material) for fast update of our objective.

3\. Compute the initial data projection $w^{T}x_{i},\forall i=0..n-1$, sort
the projection with insertion sort, and initialize
$(w_{0},obj)=Opt(w^{T}x,y,0,n-1)$. We also record the value of $j$ for the
optimal $w_{0}=(w^{T}x_{j}+w^{T}x_{j+1})/2$.

4\. Set $prevobj=\infty$.

while $prevobj-obj>0$ do

Set $prevobj=obj$

Randomly pick $k$ of the $d$ feature indices.

for all selected features $w_{i}$ we update them do

1\. Assume the optimal $w_{0}=(w^{T}x_{j}+w^{T}x_{j+1})/2$

2\. Set $start=w^{T}x_{j-10}$ and $end=w^{T}x_{j+10}$

3\. Modify coordinate $w_{i}$ by $w_{inc}$, compute data projection
$w^{T}x_{i}\forall i=0..n-1$, and sort the projection with insertion sort

4\. Set $(w_{0},obj)=Opt(w^{T}x,y,start,end)$ and record this value for
feature $w_{i}$

5\. Reset $w_{0}$ to try the next coordinate

end for

Pick the coordinate whose update gives the largest decrease in the objective
and set $(w_{0},obj)$ to the values given by the best coordinate with ties
decided randomly.

end while

###  2.3 Single hidden layer 01 loss network (MLP01)

We extend the stochastic coordinate descent solver to a single hidden layer
network with $k$ hidden nodes that we call MLP01 (see Algorithm 2). For each
random batch of the training data we train the final node followed by each
hidden node using our Coordinate Descent algorithm above (Algorithm 1). We set
20 hidden nodes ($h=20$) in our experiments.

Algorithm 2 Stochastic coordinate descent for single hidden layer 01 loss
network

Input:  Data (feature vectors) $x_{i}\in R^{d}$ with labels
$y_{i}\in\\{+1,-1\\}$, number of hidden nodes $h$ (set to 20 by default),
number of votes $rr\in N$ (Natural numbers), number of iterations per vote
$it\in N$ (set to 2000 by default), batch size as a percent of training data
$p\in[0,1]$ (set to 0.75 by default) , $w_{inc}\in R$ (set to 0.1 by default)
and $w_{inc2}\in R$ (set to 0.02)
Output:  Total of $rr$ sets of $(bestW\in R^{k\times d},bestW_{0}\in
R^{k},bestu\in R^{k},bestu_{0}\in R)$ after each vote
Procedure:

1\. Initialize all network weights $W,u$ to random values from the uniform
distribution $(-1,1)$.

2\. Set network thresholds $W_{0}$ and $u_{0}$ to the median projection value
on their corresponding weight vectors.

while $j<rr$ do

Set $bestW=null,bestW_{0}=null,bestw=null,bestw_{0}=null,bestloss=\infty$

for $i=0$ to $it$ do

Randomly pick $p$ percent of rows as input training data.

Run the Coordinate Descent Algorithm 1 for the final output node $u$ to
completion starting with the values of $u$ and $u_{0}$ from the previous call
to it (if $i==0$ we set $u=null$).

for $k=0$ to $h$ do

Run the Coordinate Descent Algorithm 1 to completion starting with the values
of $w_{k}$ ($k^{th}$ column in $W$) and $w_{k0}$ ($k^{th}$ entry in $W_{0}$)
from the previous call to it (if $i==0$ we set $w_{k}=null$).

end for

Calculate Objective 2 on the full input training set

if $objective(W,W_{0},u,u_{0})<objective(bestW,bestW_{0},bestu,bestu_{0})$
then

Set $bestW=W$, $bestW_{0}=W_{0}$, $bestu=u$, $bestu_{0}=u_{0}$, and
$bestloss=objective(bestW,bestW_{0},bestu,bestu_{0})$

end if

end for

Output ($bestW$, $bestW_{0}$, $bestu$, $bestu_{0}$)

Set $j=j+1$.

end while

We output all sets of $(bestW,bestW_{0},bestu,bestu_{0})$ across the votes. We
can use the first set or the majority vote of all sets for predictions.

###  2.4 Majority vote 01 loss

Due to the non-uniqueness of 01 loss and randomness of our solvers both our
methods will return different solutions when initialized with different seeds
for the random number generator. Thus we take the majority vote of multiple
runs which we see as inherently necessary due to the nature of 01 loss. We
call our methods SCD01majvote that has 100 votes and MLPmajvote that has 32
votes (input $rr=32$ in Algorithm 2).

###  2.5 Adversarial training SCD01

We apply the basic iterative adversarial training described earlier (Kurakin
et al., 2016) to our SCD01 algorithm. The adversarial training objective is
actually a min-max objective: we minimize the empirical risk across the
maximum distortion of the input data. The iterative training that has been
proposed earlier and used by us below is a heuristic to the min-max problem.

###  2.6 Black box adversarial attack

Since the 01 loss model has no gradient we cannot use white box gradient based
attacks. Instead we resort to a black box strategy that uses the gradient of a
substitute model to generate adversaries (Papernot et al., 2017). In this
setting we start with a small subset of the test data (200 samples) from which
we iteratively learn the substitute model parameters. In each iteration
(epoch) we generate adversaries from the remaining test and attack the target
model. This strategy can be effective as long as the substitute model is at
least as accurate on the test data as the target model. This indicates that
the substitute model is accurately modeling the target model at least on the
samples it is trained upon and so its gradient is likely to produce effective
adversaries.

For the substitute model we use a two hidden layer neural network each with
200 nodes per layer as in previous work (Galloway et al., 2017). We implement
this using the multilayer perceptron class in the Python scikit-learn toolkit
(Pedregosa et al., 2011). In the Supplementary Material we fully describe our
black box attack model. We set the distortion in the adversarial images to
$\epsilon=0.0625$ for CIFAR10, STL10, ImageNet and $\epsilon=0.3$ for MNIST.
In the Supplementary Material we provide results for lower values of
$\epsilon$ and see similar results as here.

##  3 Results

We study all methods for the task of binary classification of classes 0 and 1
on four popular image classification benchmarks. We compare our 01 loss
methods to their convex counterparts on each benchmark. We run the LinearSVC
algorithm (SVM) in Python scikit-learn toolkit (Pedregosa et al., 2011) with
cross-validated $C$. We use the Python scikit-learn multilayer perceptron with
logistic loss (MLP) and one hidden layer of 20 the same as the MLP01 network.
We train our MLP with stochastic gradient descent and learning parameters set
to optimize the cross-validation accuracy. We also study a majority vote SVM
and MLP by running them a 100 times on bootstrapped samples (bagging) and find
no improvement in robustness compared to the single runs. We obtained the
previous stochastic coordinate descent 01 loss solver (Xie et al., 2019) that
we compare to our new one. All of our code and data are freely available from
our GitHub site https://github.com/zero-one-loss/01loss.

Algorithm 3 Iterative adversarial training for SCD01

Input:  Model vector $w\in R^{d}$ and $w_{0}\in R$ from SCD01, data (feature
vectors) $x_{i}\in R^{d}$ with labels $y_{i}\in\\{+1,-1\\}$ for $i=0..n-1$
Output:  100 adversarially trained models $(w^{\prime},w^{\prime}_{0})$
Procedure:

for each of 100 iterations do

Randomly select 10% of the input training examples and produce adversaries for
each selected datapoint

for each datapoint $x_{i}$ do

Obtain prediction of $x_{i}$ as $y^{\prime}_{i}=w^{T}x_{i}+w_{0}$

Create adversary $x_{i}^{\prime}=x_{i}+(-y^{\prime}_{i})\frac{w}{||w||}$

end for

Run SCD01 on the clean plus adversarial samples selected above starting the
search from $w$ in the previous iteration.

end for

We now have 100 SCD01 models on the clean ($x_{i}$) plus adversarial
($x^{\prime}_{i}$) examples

return (all 100 ($w^{\prime},w^{\prime}_{0}$) for majority vote output)

###  3.1 CIFAR10, STL10, and ImageNet

Epoch | SCD01majvote | SVM | MLP01majvote | MLP
---|---|---|---|---
0 | .83 | .82 | .86 | .89
20 | .34 | 0 | .59 | .06

Epoch | SCD01majvote | SVM | MLP01majvote | MLP
---|---|---|---|---
0 | .8 | .76 | .82 | .82
20 | .51 | .03 | .61 | .15

Epoch | SCD01majvote | SVM | MLP01majvote | MLP
---|---|---|---|---
0 | .74 | .66 | .77 | .73
20 | .32 | .02 | .57 | .28

Figure 1: Accuracy of adversarial samples generated at each epoch during
substitute model training on CIFAR10, STL10, and ImageNet. At epoch 0 we have
the accuracy of the target model on clean test data (without adversaries) as
shown in the tables.

We start with results for binary classification of classes 0 and 1 in CIFAR10,
STL10, and ImageNet. Between classes 0 and 1 we have in CIFAR10 (Krizhevsky,
2009) we have 10,000 $32\times 32\times 3$ training images and 2000 test ones
and in STL10 (Coates et al., 2011) we have 1000 $96\times 96\times 3$ training
images and 1600 test. In ImageNet classes 0 and 1 contain about 2580
$256\times 256\times 3$ training images and 100 test ones. We change the split
so as to increase the test data size so that we can better train the black box
attack substitute model. We divide the training set into two parts: the first
containing 1280 for training and 1300 for test.

In Figure 1 we see that both our linear SCD01 and non-linear MLP01 models have
comparable accuracy to the linear SVM and non-linear MLP but are much more
robust. In Figure 2 we show clean and adversarial images generated by
attacking MLP01, MLP, and SVM. We show adversarial images that are correctly
classified by MLP01 and wrongly by MLP and SVM.

Clean | MLP01 majvote | MLP | SVM
---|---|---|---
|  |  |
|  |  |
|  |  |
Figure 2: Clean images from CIFAR10 (top row), STL10 (mid row), and ImageNet
(bottom row) and adversarial images obtained by attacking MLP01, MLP, and SVM
with $\epsilon=0.0625$. The adversarial images shown here fool SVM and MLP but
are correctly classified by MLP01.

###  3.2 MNIST and simulation

Epoch | SCD01majvote | SVM | MLP01majvote | MLP
---|---|---|---|---
0 | 1 | 1 | 1 | 1
20 | .26 | .34 | .42 | .43

Figure 3: Accuracy of adversarial samples on MNIST (see Figure 1 caption for
more)

While the above benchmarks are focused on image classification of arbitrary
objects the MNIST benchmark focuses on digit classification and is easier in
comparison. Its test accuracy is typically above 99% for most classifiers.
Between classes 0 and 1 (also digits 0 and 1) we have 12,665 training images
and 2115 test images each of size $28\times 28$. In Figure 3 we see that SCD01
is not as robust as SVM and MLP01 is the same as MLP. We conjecture that this
may be due to non-uniqueness of 01 loss on easily separable classes like we
see in MNIST. To understand this better we turn to simulated data.

In Figure 4 we show SCD01 and SVM boundaries on simple and complex simulated
datasets. On the simple dataset (shown in Figure 4(a) and (b)) we see that the
SCD01 boundary is close to one class whereas the SVM is centered to maximize
the margin. This is due to the non-uniqueness of the 01 loss function. There
are infinite solutions on the simple dataset and the search ends as soon as
the loss value becomes zero. On the complex dataset however both SCD01 and SVM
boundaries are similar.

|
---|---
(a) SCD01 simple | (b) SVM simple
|
(c) SCD01 complex | (d) SVM complex
(e)
Figure 4: SCD01 and linear SVM boundaries on simple separable data in (a) and
(b), and the same boundaries on complex data in (c) and (d). In (e) we show
the accuracy of adversarial samples generated at each epoch during substitute
model training on the simple and complex datasets. As before at epoch 0 we
have the accuracy of the target model on clean test data (without
adversaries).

We conjecture that attacking SCD01 on a simple dataset would be easy because a
convex substitute model (such as MLP and SVM) would have a boundary similar to
the SVM. Thus adversaries from its boundary are likely to succeed in attacking
SCD01 whose boundary lies close to one class. Indeed we see in Figure 4(e)
that SCD01 falls from 100% to 50% accuracy on the simple dataset after the
first epoch of the black box attack whereas SVM remains at 100%. We now
consider adversarial training to improve SCD01’s robustness particularly on
simple MNIST type datasets.

###  3.3 Adversarial training

In order to increase the robustness of SCD01 we run Algorithm 3 starting with
a single run SCD01 trained on the full training dataset. We then take the
majority vote of all 100 classifiers learnt in each iteration. We also run the
same algorithm by replacing SCD01 with SVM and instead of voting across all
100 we use just the final model as is typical in adversarial training (Kurakin
et al., 2016). We find the adversarially trained SCD01 is more robust than
SCD01 and SCD01 majvote on all datasets while retaining clean test accuracy.
In Figure 5 we see the adversarially trained SCD01 on MNIST and CIFAR10
outperforms the versions trained on the clean data. It is comparable to the
adversarially trained SVM on MNIST $\epsilon=0.3$ and better on MNIST
$\epsilon=0.2$ and CIFAR10.

---
Figure 5: Accuracy of adversarial samples after iterative adversarial training
on MNIST with two different distortions and CIFAR10

###  3.4 Transferability of adversaries between 01 and convex loss

Table 1: Transferability of black box adversaries between 01 and convex loss in CIFAR10 and STL10 (both $\epsilon=0.0625$) | CIFAR10
---|---
Adversarial | Black box target model
accuracy of model | MLP01 (32 votes) | MLP | SVM
MLP01 (32 vo.) | 59.7% | 55.8% | 60.8%
MLP | 52% | 8.1% | 8.4%
SVM | 32.3% | 1.8% | 0.17%
| STL10
Adversarial | Black box target model
accuracy of model | MLP01 (32 votes) | MLP | SVM
MLP01 (32 vo.) | 60.5% | 58.5% | 64.93%
MLP | 52.9% | 14.9% | 13.1%
SVM | 46.6% | 7.2% | 2.5%

Adversarial samples are known to transfer between classifiers (Papernot et
al., 2016a). We find this is not so true for 01 loss adversaries. In Table 1
we see that adversaries targeting MLP01 also attack MLP and SVM but to a lower
extent than if we attacked MLP and SVM directly as the target model.
Adversaries produced by attacking MLP and SVM transfer between each other but
not to MLP01.

###  3.5 Runtimes, stability, and comparison to prior work

In Table 2 we see that our solver with majority vote is considerably faster
than the previous one (Xie et al., 2019) (100 votes) but still slower than the
convex counterparts. These are measured on Intel Xeon Silver 4114 CPUs with
NVIDIA Titan RTX 2080 GPUs.

Table 2: Runtimes of prior work (Xie et al., 2019) denoted by PREV-SCD01 and our methods shown in hours Data | PREV-SCD01 | SCD01 | MLP01 | SVM | MLP
---|---|---|---|---|---
| 100 votes | 100 votes | 32 votes |  |
CIFAR10 | 13.94 | 1.74 | 2.57 | 0.003 | 0.01
STL10 | 12.23 | 1.38 | 0.71 | 0.004 | 0.008
MNIST | 3.1 | 0.26 | 0.68 | 3E-4 | 0.001

We compare the adversarial accuracy of the previous 01 loss solver to ours on
CIFAR10 and STL10 and find the robustness to be similar (see Supplementary
Material for graph). This further supports our hypothesis of 01 loss
robustness over convex ones since we see a high robustness across two
different 01 loss solvers. In Table 3 we see that both SCD01 and MLP01
majority vote on the test data have low deviation suggesting that our results
are stable and reproducible.

Table 3: Mean and standard deviation of 100 votes of SCD01 and 32 votes of MLP01 | SCD01 (100 votes) | MLP01 (32 votes)
---|---|---
| STL10 | CIFAR10 | MNIST | STL10 | CIFAR10 | MNIST
Mean | .75 | .81 | .99 | .76 | .83 | .99
Std dev | .008 | .005 | 8E-3 | .01 | .006 | 8E-3

###  3.6 Applications: street sign and facial recognition adversarial attacks

We now turn to two practical problems where adversarial attacks pose a
problem. First is the task of street sign detection by autonomous vehicles
(Sitawarin et al., 2018) and the second is facial recognition that are used by
government and security systems. We consider 2816 train and 900 test $48\times
48\times 3$ images of street signs of 60 and 120 mph from the GTSRB street
sign dataset (Stallkamp et al., 2011) and 1000 train and 1000 test $96\times
96\times 3$ images of brown and black hair individuals from the CelebA facial
recognition benchmark (Liu et al., 2015). For GTSRB we use a perturbation of
$\epsilon=0.03125$ and for CelebA we use $\epsilon=0.0625$ in the black box
attack. We show other values of $\epsilon$ in the Supplementary Material and
make similar observations as here. In Figure 6 we see that the MLP01 attains
comparable accuracy to SVM and MLP but is more robust as we saw in earlier
benchmarks. We show sample adversarial images in Figure 7.

Epoch | MLP01majvote | SVM | MLP
---|---|---|---
0 | .98 | .99 | .98
20 | .35 | .24 | .24

Epoch | MLP01majvote | SVM | MLP
---|---|---|---
0 | .79 | .76 | .78
20 | .37 | 0 | .02

Figure 6: Accuracy of adversarial samples on GTSRB and CelebA (see Figure 1 caption for more) Clean | MLP01 majvote | MLP | SVM
---|---|---|---
|  |  |
|  |  |
Figure 7: Images from CelebA in the top row and GTSRB in the bottom one (see
Figure 2 caption for more)

##  4 Discussion

Our results show that a convex substitute model (like the multilayer
perceptron that we use) can generate effective adversaries for other convex
ones like SVM and MLP but not so much on 01 loss like our SCD01 and MLP01. We
ask two follow-up questions. (1) Can we attack the 01 loss with a 01 loss
substitute model? (2) Was the multilayer perceptron substitute model in the
black box attack correctly trained? To answer the first question we use SCD01
as the substitute model in our black box attack.

---
Figure 8: Accuracy of adversarial samples generated at each epoch during SCD01
substitute model training on CIFAR10 with distortion $\epsilon=1$. At epoch 0
we have the accuracy of the target model on clean test data (without
adversaries). Also shown is the accuracy of the SCD01 substitute model on test
samples during training to confirm that the substitute model has test accuracy
comparable to the target model.

In Figure 8 we see the results of attacking SCD01 and SVM with SCD01 as the
substitute model in the black box attack. We use the same seed for the random
number generator in SCD01 both for the target and substitute model to avoid
differences due to randomness. We don’t use the majority vote and attack a
single run of SCD01.

We see that the black box attack with SCD01 as the substitute model fails to
attack any of the models even though the accuracy of the substitute on test
data is high during training and the distortion is set to a high value of
$\epsilon=1$. We argue this is because of its non-unique nature: there can be
infinite solutions all yielding the same local minimum in the 01 loss search
space. Thus when we attempt to learn an SCD01 single vote model to generate
adversaries we find it cannot even approximate and successfully attack the
same SCD01 trained on clean data with the same random number generator seed as
the substitute.

Of course we can attack SCD01 if we know its model parameters $(w,w_{0})$. We
simply generate adversaries with
$x_{i}^{\prime}=x_{i}+(-y^{\prime}_{i})\frac{w}{||w||}$ and these will fool
the SCD01 single vote. In Table 4 we see that the SCD01 adversaries generated
in this way fool the SCD01 classifier and also transfer over to the SVM to
some degree. This would be a white box attack though. If the model parameters
are kept hidden or retrained we see that both convex and 01 loss substitute
models find it hard to attack 01 loss.

Table 4: Accuracy of adversarial examples produced by the SCD01 $w$ vector in CIFAR10 (white box attack). In parenthesis are test data accuracies without adversaries. Attack model | SCD01 | SVM | MLP01 | MLP
---|---|---|---|---
SCD01 (white box) | .19 (.83) | .79 (.82) | .86 (.86) | .87 (.89)

For the second question we look at the accuracy of our multilayer perceptron
substitute model in each epoch of the black box attack. An accurately trained
substitute model indicates that our training was successful and its gradient
is likely to be an effective generator of adversaries. Indeed we see in Figure
9 that the black box substitute model accuracy while attacking SCD01, MLP01,
SVM, and MLP on CIFAR10 are similar to the clean test accuracies of the target
model suggesting we have a well-trained substitute. We see the same trend on
all datasets.

Figure 9: Accuracy of the substitute model on CIFAR10 while attacking SCD01,
MLP01, SVM, and MLP

We have shown that substitute model black box attacks are not so effective
against 01 loss models when the substitute model is convex or 01 loss. There
are however other black box attack methods that rely on just labels and try to
estimate the minimum distortion of adversarial examples (an NP-hard problem)
(Chen et al., 2017; Brendel et al., 2017; Chen et al., 2019). We obtained the
implementations of the Boundary Attack (Brendel et al., 2017) and HopSkipJump
attack (Chen et al., 2019) to determine the minimum adversarial distortion of
our SCD01 boundary. Both of these start with an adversarial example and make
incremental changes until the example is just at the boundary of the target
model. In our initial attempts we found both codes to crash before reaching
convergence or their default maximum iterations when we attack our SCD01 and
SCD01 majvote models. While we need to revisit the attacks both are slow even
for a single example. This is not surprising since finding the minimum
distortion is an NP-hard problem and thus hard to solve in practice.

We measure the $L_{2}$ distances between adversarial and clean images shown in
Figure 2 plus the Celeba images in Figure 7 and average them: MLP01=11.54,
MLP=11.5, SVM=11.5. Thus despite MLP01 adversaries have a higher distortion
they are still correctly classified by MLP01.

We have not shown the effect of different parameters on SCD01 and MLP01
because our focus here is on adversarial attacks on 01 loss. We determined our
parameters by optimizing accuracy on the test dataset and then fix them for
the adversarial attacks. While our SCD01 and MLP01 are possibly the fastest 01
solvers that we know of, our runtimes are still higher than SVM and MLP. Thus
speeding up our algorithms by parallelization is a key part of future work.

There are several other future avenues we could explore going forward. The
first is multi-class classification so we can evaluate 01 loss on full image
benchmarks. In previous work (Xie et al., 2019) a one-vs-one strategy of 10
votes showed promising but limited results. We instead plan to add more nodes
to the final layer of MLP01 and rely on majority vote for classification. Even
though our results here are for classes 0 and 1 we expect similar trends on
other pairs of classes in the benchmarks. Besides a multi-class network we may
explore 01 loss convolutions in an attempt to match the accuracy of
convolutional neural networks. This is computationally significantly hard but
perhaps possible by extending the stochastic coordinate descent like we have
in this study.

We briefly touch upon adversarial training in this paper and plan to explore
it separately. In particular we plan to study adversarially trained SVM and
MLP, and explore iterative training for SCD01 more thoroughly. It is unclear
how to generate white box adversaries for MLP01 and so a naive iterative
training like we did for SCD01 will not work there. One strategy is to use
gradient free black box attacks but runtime may be a problem. If we can
successfully adversarially train MLP01 it may become more robust than what we
demonstrate here.

## References

  * Alpaydin (2004) Alpaydin, E.  _Machine Learning_.  MIT Press, 2004.
  * Bartlett et al. (2004) Bartlett, P. L., Jordan, M. I., and Mcauliffe, J. D.  Large margin classifiers: Convex loss, low noise, and convergence rates.  In Thrun, S., Saul, L., and Schölkopf, B. (eds.), _Advances in Neural Information Processing Systems 16_ , pp. 1173–1180. MIT Press, 2004\.
  * Ben-David et al. (2003) Ben-David, S., Eiron, N., and Long, P. M.  On the difficulty of approximately maximizing agreements.  _Journal of Computer and System Sciences_ , 66(3):496–514, 2003.
  * Brendel et al. (2017) Brendel, W., Rauber, J., and Bethge, M.  Decision-based adversarial attacks: Reliable attacks against black-box machine learning models.  _arXiv preprint arXiv:1712.04248_ , 2017.
  * Carlini & Wagner (2017) Carlini, N. and Wagner, D.  Towards evaluating the robustness of neural networks.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pp. 39–57. IEEE, 2017.
  * Chen et al. (2019) Chen, J., Jordan, M. I., and Wainwright, M. J.  Hopskipjumpattack: A query-efficient decision-based attack.  _arXiv preprint arXiv:1904.02144_ , 3, 2019.
  * Chen et al. (2017) Chen, P.-Y., Zhang, H., Sharma, Y., Yi, J., and Hsieh, C.-J.  Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models.  In _Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security_ , pp. 15–26, 2017.
  * Coates et al. (2011) Coates, A., Ng, A., and Lee, H.  An analysis of single-layer networks in unsupervised feature learning.  In _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , pp. 215–223, 2011.
  * Cortes & Vapnik (1995) Cortes, C. and Vapnik, V.  Support-vector networks.  _Machine learning_ , 20(3):273–297, 1995.
  * Galloway et al. (2017) Galloway, A., Taylor, G. W., and Moussa, M.  Attacking binarized neural networks.  _arXiv preprint arXiv:1711.00449_ , 2017.
  * Ghosh et al. (2015) Ghosh, A., Manwani, N., and Sastry, P.  Making risk minimization tolerant to label noise.  _Neurocomputing_ , 160:93–107, 2015.
  * Goodfellow et al. (2014) Goodfellow, I. J., Shlens, J., and Szegedy, C.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014.
  * Hu et al. (2016) Hu, W., Niu, G., Sato, I., and Sugiyama, M.  Does distributionally robust supervised learning give robust classifiers?  _arXiv preprint arXiv:1611.02041_ , 2016.
  * Krizhevsky (2009) Krizhevsky, A.  Learning multiple layers of features from tiny images.  2009\.
  * Krizhevsky et al. (2012) Krizhevsky, A., Sutskever, I., and Hinton, G. E.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pp. 1097–1105, 2012.
  * Kurakin et al. (2016) Kurakin, A., Goodfellow, I., and Bengio, S.  Adversarial machine learning at scale.  _arXiv preprint arXiv:1611.01236_ , 2016.
  * Li & Lin (2007) Li, L. and Lin, H.-T.  Optimizing 0/1 loss for perceptrons by random coordinate descent.  In _Neural Networks, 2007. IJCNN 2007. International Joint Conference on_ , pp. 749–754. IEEE, 2007.
  * Liu et al. (2015) Liu, Z., Luo, P., Wang, X., and Tang, X.  Deep learning face attributes in the wild.  In _Proceedings of International Conference on Computer Vision (ICCV)_ , December 2015.
  * Lyu & Tsang (2019) Lyu, Y. and Tsang, I. W.  Curriculum loss: Robust learning and generalization against label corruption.  _arXiv preprint arXiv:1905.10045_ , 2019.
  * Manwani & Sastry (2013) Manwani, N. and Sastry, P.  Noise tolerance under risk minimization.  _IEEE transactions on cybernetics_ , 43(3):1146–1151, 2013.
  * Nguyen & Sanner (2013) Nguyen, T. and Sanner, S.  Algorithms for direct 0–1 loss optimization in binary classification.  In _Proceedings of The 30th International Conference on Machine Learning_ , pp. 1085–1093, 2013.
  * Papernot et al. (2016a) Papernot, N., McDaniel, P., and Goodfellow, I.  Transferability in machine learning: from phenomena to black-box attacks using adversarial samples.  _arXiv preprint arXiv:1605.07277_ , 2016a.
  * Papernot et al. (2016b) Papernot, N., McDaniel, P., Jha, S., Fredrikson, M., Celik, Z. B., and Swami, A.  The limitations of deep learning in adversarial settings.  In _2016 IEEE European Symposium on Security and Privacy (EuroS &P)_, pp. 372–387. IEEE, 2016b.
  * Papernot et al. (2017) Papernot, N., McDaniel, P., Goodfellow, I., Jha, S., Celik, Z. B., and Swami, A.  Practical black-box attacks against machine learning.  In _Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security_ , pp. 506–519. ACM, 2017.
  * Pedregosa et al. (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Raghunathan et al. (2019) Raghunathan, A., Xie, S. M., Yang, F., Duchi, J. C., and Liang, P.  Adversarial training can hurt generalization.  _arXiv preprint arXiv:1906.06032_ , 2019.
  * Shai et al. (2011) Shai, S.-S., Shamir, O., and Sridharan, K.  Learning linear and kernel predictors with the 0-1 loss function.  _IJCAI Proceedings-International Joint Conference on Artificial Intelligence_ , 22(3), 2011.
  * Shalev-Shwartz et al. (2011) Shalev-Shwartz, S., Shamir, O., and Sridharan, K.  Learning linear and kernel predictors with the 0-1 loss function, 2011\.
  * Sitawarin et al. (2018) Sitawarin, C., Bhagoji, A. N., Mosenia, A., Chiang, M., and Mittal, P.  Darts: Deceiving autonomous cars with toxic signs.  _arXiv preprint arXiv:1802.06430_ , 2018.
  * Stallkamp et al. (2011) Stallkamp, J., Schlipsing, M., Salmen, J., and Igel, C.  The German Traffic Sign Recognition Benchmark: A multi-class classification competition.  In _IEEE International Joint Conference on Neural Networks_ , pp. 1453–1460, 2011.
  * Szegedy et al. (2013) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ , 2013.
  * Tang et al. (2014) Tang, Y., Li, X., Xu, Y., Liu, S., and Ouyang, S.  A mixed integer programming approach to maximum margin 0–1 loss classification.  In _2014 International Radar Conference_ , pp. 1–6. IEEE, 2014\.
  * Xie et al. (2019) Xie, M., Xue, Y., and Roshan, U.  Stochastic coordinate descent for 0/1 loss and its sensitivity to adversarial attacks.  In _Proceedings of 18th IEEE International Conference on Machine Learning and Applications - ICMLA 2019_ , pp. to appear, 2019.
  * Zhai et al. (2013) Zhai, S., Xia, T., Tan, M., and Wang, S.  Direct 0-1 loss minimization and margin maximization with boosting.  In Burges, C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), _Advances in Neural Information Processing Systems 26_ , pp. 872–880. Curran Associates, Inc., 2013.
  * Zhang et al. (2019) Zhang, H., Yu, Y., Jiao, J., Xing, E. P., Ghaoui, L. E., and Jordan, M. I.  Theoretically principled trade-off between robustness and accuracy.  _arXiv preprint arXiv:1901.08573_ , 2019.


# Augmented Memory Networks for
Streaming-Based Active One-Shot Learning

Andreas Kvistad, Massimiliano Ruocco, Eliezer de Souza da Silva, Erlend Aune
Department of Computer Science
Norwegian University of Science and Technology
<EMAIL_ADDRESS>
Master Student.

###### Abstract

One of the major challenges in training deep architectures for predictive
tasks is the scarcity and cost of labeled training data. Active Learning (AL)
is one way of addressing this challenge. In stream-based AL, observations are
continuously made available to the learner that have to decide whether to
request a label or to make a prediction. The goal is to reduce the request
rate while at the same time maximize prediction performance. In previous
research, reinforcement learning has been used for learning the AL
request/prediction strategy. In our work, we propose to equip a reinforcement
learning process with memory augmented neural networks, to enhance the one-
shot capabilities. Moreover, we introduce Class Margin Sampling (CMS) as an
extension of the standard margin sampling to the reinforcement learning
setting. This strategy aims to reduce training time and improve sample
efficiency in the training process. We evaluate the proposed method on a
classification task using empirical accuracy of label predictions and
percentage of label requests. The results indicates that the proposed method,
by making use of the memory augmented networks and CMS in the training
process, outperforms existing baselines.

##  1 Introduction

Traditionally, deep learning architectures have been successfully employed in
the data regime where labeled data is abundant – meaning that the cost of
obtaining the labels can be ignored in the training process. This includes
applications such as large scale object recognition, classification of images,
videos or texts, as well as other situations where large labeled data sets are
available.

In practice there are many situations where labels are scarce and the cost of
obtaining the labels is non-negligible. In AL, this problem has been tackled
for settings where, during the training process of the model, minimization of
training error and cost of querying for the label a given data point is
performed. Typically a set of heuristics are employed, for example by looking
at the expected information gain of querying for the label, uncertainty
sampling (looking for regions of the data space where there is more
uncertainty about the label), exploration-exploitation of the data space,
among others. Recent advances in neural architectures for Active Learning have
explored the possibilities of learning AL strategy, which means using neural
networks for learning _how to_ active learn. Models that are capable of
learning with only a handful examples is also of great interest. This is
generally associated with the one-shot learning problem (Koch et al., 2015).

Leveraging both scarcity of data and labels calls for one-shot active
learning. We approach this as a stream-based problem, where a learning agent
is confronted with new data in a sequential way, where whenever a data point
is received, the model needs to decide on whether to predict the label or to
request a label from an oracle - preferably with as few requests as possible.
Starting from the work in (Woodward & Finn, 2017) we propose a memory-
augmented neural architecture, based on the intuition that gradient based
predictive learning should be equipped with memory capabilities (allowing
transfer and retention of information) and active learning strategies through
reinforcement learning with a reward associated with the actions of requesting
labels, or classifying a given point. The main contributions of this work can
be summarized as follows: 1) we propose and test an active one-shot learning
system equipped with memory augmented architectures, 2) we introduce the novel
Class Margin Sampling (CMS), as an extension of standard margin sampling to
the reinforcement learning setting, with the goal of improving sampling
efficiency for AL.

##  2 Related Work

AL has been extensively studied in the past decade (Settles, 2009) and several
heuristics for data selection process have been proposed. Mostly, these
selection criteria include uncertainty sampling (Tong & Koller, 2002), query-
by-committee (Seung et al., 1992), expected model change (Cai et al., 2017)
and expected error reduction (Roy & McCallum, 2001). AL has previously been
applied in different domains, such as natural language processing (Zhang et
al., 2017; Asghar et al., 2017; Shen et al., 2017; Buck et al., 2017),
computer vision (Sener & Savarese, 2018; Wang et al., 2017; Beluch et al.,
2018) and in recommender systems (Elahi et al., 2016). One of the major
limitations is in the selection of the heuristic for data ranking and
selection, whose performance can differ over different datasets. To address
this shortcoming recent research has proposed methods for learning the
selection heuristics themselves. One way of doing this is casting the problem
as a reinforcement learning problem, where the learned policy takes the place
of the predefined heuristics (Fang et al., 2017; Woodward & Finn, 2017; Pang
et al., 2018). In the context of stream-based AL, the work of (Woodward &
Finn, 2017) employs an LSTM to act as function approximator for a Q-network,
and the output of the LSTM is connected to a fully connected linear layer
producing the actual Q-values. The setup is very similar to the one in
(Vinyals et al., 2016) where they address the problem in the few-shot learning
setting. In (Pang et al., 2018; Bachman et al., 2017; Ravi & Larochelle,
2018), the process of learning the active learner is framed in a meta-learning
setting. In (Pang et al., 2018) deep reinforcement learning is used to learn
the active learning policy that generalize over different dataset, by using a
generic embedding layers that maps dataset-dependent features to embeddings.

##  3 Methodology

In this section we describe the baseline model for active one-shot learning
and the proposed extensions memory-augmented extensions. In particular we
propose to augment the baseline with two different Memory Augmented Neural
Networks (MANNs), the Neural Turing Machine (NTM) (Graves et al., 2014) and
the Least Recently Used Access (LRUA) (Santoro et al., 2016a) memory.

###  3.1 Proposed Models

#### LSTM Baseline Model

The baseline, (Woodward & Finn, 2017), consists of a method for learning the
active learner within a deep reinforcement learning framework. The model
learn, with few examples per class, to make labelling decision online. The
Q-function is approximated by an LSTM connected to a fully connected linear
output layer (Figure 1(a)). The model trains on short episodes, in which it
either predicts a class for an item received, or request the true label for
it. Consequently, the output space of the model is $C+1$, where $C$ is the
number of classes. The items for the given episode are randomly drawn from the
training set, and are given a random slot in a one-hot vector indicating which
class is associated with, for the given episode. In other words, the
activation applied to the model will be episode specific, and should not force
it to learn item-class binding dependencies. The number of items from every
class in an episode vary, since the items are randomly drawn. Following the
original work, we use Adam optimizer (Kingma & Ba, 2014) with default
parameters, with the task of minimizing the Bellman error in the Q-network

#### NTM-based Augmentation

As the LSTM is relying solely on its internal state for representing the
previous states, adding an external more explicit memory-structure could be
helpful in increasing the accuracy of the system, similar to (Santoro et al.,
2016b). We employed a Neural Turing Machine (NTM) as in (Graves et al., 2014)
as the Q-network with an LSTM as memory controller (Figure 1(b) in the
Appendix). As reported in (Santoro et al., 2016b), the NTM outperform the
basic LSTM in a similar task setup, especially increasing accuracy on one-shot
predictions Given that the NTM is a fully differentiable memory-structure, the
model doesn’t require a different task setup. For every episode, given the
current state $h_{t}$, the LSTM controller produces an output which in turn is
presented to all the read- and write-heads in the model. The read-heads
returns a memory $r_{t}$ which together with the output from the controller,
serves as input to the final fully connected layer producing the Q-values. It
is important to note that the write-heads are not used when estimating the
future discounted rewards - only the read-heads. This is because the model
only simulates the next state and which Q-values it possibly would produce,
and therefore shouldn’t write anything to memory in this procedure.

#### LRUA-based Augmentation

The authors of (Santoro et al., 2016b) propose a different strategy for
writing to memory using an NTM named LRUA (Least Recently Used Access). This
strategy mainly differs in the writing-to-memory process. Instead of only
using the read-weights to determine where to write to memory, several
additional weight-vectors are introduced. The LRUA is a more specialized
version of the NTM with a pure content-based memory writer, with two main
choices when writing: 1) write to the least recently used memory location, 2)
write to the most recently used memory location. The main difference between
the two choices is that the former approach is resetting the memory location
before writing, successfully replacing the memory, and the latter is updating
the most recently used memory location with possibly more relevant
information. In this way, important information is kept (i.e. information that
has been used recently), as well as the memory is constantly updated with new
information. Thus for our task setup, the inclusion of new classes will most
likely be written to the currently least used slot, while samples of already
existing slots will either update the most recently used slot (if the previous
sample was of the same class), or be written to a least used slot.

###  3.2 Episode Construction by Class Margin Sampling

To further improve sample efficiency and model performance, we introduce Class
Margin Sampling (CMS). As opposed to standard margin sampling, CMS estimates
the margin between $T>1$ samples of the same class, for a specified number of
classes (usually $C_{cms}=C\times 2$). In the context of a one-shot problem,
with the added possibility to request a label instead of making a prediction,
the standard margin sampling offers limited information. This is because the
first sample in every episode shouldn’t have considerable bias towards a
specific class, which anyhow should be considered noise. By this particular
design, all first-instance Q-values provide little but no information about
the model, as we always want the model to execute a label request to maximize
the expected reward. Thus, instead of calculating the smallest margin in a
pool of samples, we change the method to better fit our task setup, using a
pool of classes. The procedure starts by randomly drawing a specified number
$C_{cms}$ of classes from the training set, which will act as the pool of
classes. From each class, it draws $T$ samples which are processed, and fed to
the model in sequence, meaning that all T samples from a class is used as an
episode. This process is performed one class at a time, and then followed by a
reset operation of both memory and hidden state. The margin for each drawn
class is then calculated based on the sum of the minimum absolute111The
absolute value of the Q-values are calculated after the maximum values are
selected. Q-values generated by the $T$ samples. Thus it’s more likely that
classes the model easily recognizes after the initial observation are not
selected as a training sample. This procedure serves to reduce the likelihood
of the following previously occurring problems during training:

  1. 1.

If a sample’s class is assigned the same random label multiple times, it
starts creating inter-episode sample-class bindings, which can result in
unfortunate class-biases.

  2. 2.

The sample classes that are easily recognizable or distinguish themselves most
from others, given the model’s current parameters, don’t provide optimal
information gain during training, and thus can be rejected.

The first problem is addressed in (Santoro et al., 2016b). The authors argue
that the NTM and LRUA overfits on the one-hot vector class-encodings, and
propose a more robust encoding scheme for reducing this phenomenon. Our task
structure is not compatible with a similar scheme, and we employ CMS to help
reduce the likelihood of overfitting. The second problem is usually addressed
by employing margin sampling, and is also the main reason for our use of CMS.
By evaluating a pool of classes, CMS will select the sample classes that
provide the most valuable information from the pool, given the models current
parameters. CMS will thus in a certain sense select the most difficult samples
to classify. Increasing the number of classes drawn $C_{cms}$ could
potentially enhance performance further, but will also result in slower data
collection, and thus finding an equilibrium will be beneficial. The sampling
procedure will increase the training time, but at the same time enhance the
generality of the models.

Since the models are trained by RL, any added bias in the task setup - e.g.
conditioning the data sampling procedure - can be viewed as ”unnatural” and
potentially inhibit the exploration done by the model. We believe that since
CMS consider the value of all output nodes, the inherent exploration in the
model is still maintained.

##  4 Results and Discussion

We first evaluate the average classification accuracy in the given task as
well as the percentage of label requests for both, the baseline LSTM-based
model (LSTM) and the proposed models with Reinforced-NTM (NTM) and Reinforced-
LRUA (LRUA), with CMS and without. The models were trained on $100.000$
episode batches from the training set, and then evaluated on $10.000$ episode
batches. A summary of such results for both training and test set is presented
in Figure 2(a) and 2(b) in the Appendix. A detailed summary of the results is
reported in Table 1.

| Instance (% Correct) | Instance (% Requested)
---|---|---
Model | 1st | 2nd | 5th | 10th | 1st | 2nd | 5th | 10th
LSTM (Baseline) | 51.6 | 78.6 | 81.4 | 82.4 | 62.8 | 8.30 | 1.2 | 0.7
NTM | 52.5 | 77.9 | 81.8 | 83.0 | 63.3 | 8.4 | 1.6 | 1.1
LRUA | 58.0 | 79.2 | 81.8 | 83.2 | 62.3 | 6.9 | 0.7 | 0.4
LSTM $C_{cms}=2$ | 53.3 | 78.8 | 82.6 | 83.2 | 63.3 | 9.9 | 1.2 | 0.5
NTM $C_{cms}=2$ | 50.8 | 77.7 | 83.0 | 84.2 | 62.2 | 9.3 | 1.7 | 1.1
LRUA $C_{cms}=2$ | 63.7 | 79.4 | 82.6 | 83.7 | 63.9 | 8.9 | 0.8 | 0.5
LSTM $C_{cms}=3$ | 52.7 | 77.9 | 83.1 | 83.7 | 61.6 | 11.0 | 1.1 | 0.5
NTM $C_{cms}=3$ | 52.9 | 78.6 | 83.0 | 84.1 | 62.7 | 11.5 | 1.92 | 1.04
LRUA $C_{cms}=3$ | 69.1 | 78.4 | 82.2 | 83.1 | 64.9 | 11.7 | 0.6 | 0.3
Table 1: Class instance accuracies on test set. Accuracies are only calculated
from predictions made.

For both baseline and proposed approaches, we observe a drop in the actual
average accuracy values from the training set to the test set. In particular
observe a drop of $~{}7\%$ in LRUA-based model (Figure 2(a), right side), due
to an overfitting on the training set. This was an expected behavior, also
reported in (Woodward & Finn, 2017), on the same task, by using LRUA as
external memory for one-shot classification. For the LSTM and NTM, the drop in
the average accuracy is instead between $2-3\%$ (Figure Figure 2(a), left side
and middle). In the comparison between the baseline model and the reinforced
ones (NTM and LRUA), we observed that LRUA model has a tendency of requesting
less labels than both the LSTM and NTM, outperforming both of them in both
accuracy and percentage of requested labels. This can be explained by the
capabilities of learning more meta-information about the episodic structure
than the other models, that turns in a behavior characterized by: 1)
requesting more first class-instances in episodes, 2) requesting less late
class-instances in episodes. For example, we can notice that the reinforced-
LRUA based models is requesting instance $62.3\%$ (similar to the baseline and
the reinforced-NTM based) but with an accuracy of $58\%$. This trend is kept
for late-class prediction ($2nd$, $5th$ and $10th$), but with less instance
requested (i.e. $0.7\%$ at $5th$ instance against $1.2\%$ of the baseline)
suggesting that the reinforced-LRUA based model is learning a better active
learning strategy for zero-shot classification of images than the other
models. In the same Table we reported also the results of further experiments
with augmenting each model with CMS, either with $C_{cms}=C*2$ or
$C_{cms}=C*3$, hereby written $C_{cms}=2$ and $C_{cms}=3$, and a margin time
$T=4$. We observe that augmenting the models with CMS increase the percentages
of label requests done in general by the reinforced-NTM based model.

##  5 Conclusion

In this work we have proposed and test a memory-augmented model for deep one-
shot active learning. This model intend to advance the capabilities of neural
architectures for the data regime where data is scarce and the labeling has a
non-negligible cost. The proposed model consists in a crafted combination of
deep reinforcement learning for learning an active learning sampling
heuristics with augmented memory networks to account for the necessary fast
adaptability and information distilling necessary for one-shot learning. To
improve the training process we introduce a modification of margin sampling,
denominated Class Margin Sampling (CMS) in order to leverage to the known
class information in the margin sampling process.

## References

  * Asghar et al. (2017) Nabiha Asghar, Pascal Poupart, Xin Jiang, and Hang Li.  Deep active learning for dialogue generation.  In _Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017)_ , pp. 78–83. Association for Computational Linguistics, 2017.  doi: 10.18653/v1/S17-1008.  URL http://www.aclweb.org/anthology/S17-1008.
  * Bachman et al. (2017) Philip Bachman, Alessandro Sordoni, and Adam Trischler.  Learning algorithms for active learning.  In Doina Precup and Yee Whye Teh (eds.), _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pp. 301–310, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.  URL http://proceedings.mlr.press/v70/bachman17a.html.
  * Beluch et al. (2018) William H. Beluch, Tim Genewein, Andreas Nürnberger, and Jan M. Köhler.  The power of ensembles for active learning in image classification.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * Buck et al. (2017) Christian Buck, Jannis Bulian, Massimiliano Ciaramita, Andrea Gesmundo, Neil Houlsby, Wojciech Gajewski, and Wei Wang.  Ask the right questions: Active question reformulation with reinforcement learning.  _CoRR_ , abs/1705.07830, 2017.  URL http://arxiv.org/abs/1705.07830.
  * Cai et al. (2017) Wenbin Cai, Yexun Zhang, Ya Zhang, Siyuan Zhou, Wenquan Wang, Zhuoxiang Chen, and Chris Ding.  Active learning for classification with maximum model change.  _ACM Trans. Inf. Syst._ , 36(2):15:1–15:28, August 2017.  ISSN 1046-8188.  doi: 10.1145/3086820.  URL http://doi.acm.org/10.1145/3086820.
  * Elahi et al. (2016) Mehdi Elahi, Francesco Ricci, and Neil Rubens.  A survey of active learning in collaborative filtering recommender systems.  _Comput. Sci. Rev._ , 20(C):29–50, May 2016.  ISSN 1574-0137.  doi: 10.1016/j.cosrev.2016.05.002.  URL http://dx.doi.org/10.1016/j.cosrev.2016.05.002.
  * Fang et al. (2017) Meng Fang, Yuan Li, and Trevor Cohn.  Learning how to active learn: A deep reinforcement learning approach.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pp. 595–605. Association for Computational Linguistics, 2017.  URL http://aclweb.org/anthology/D17-1063.
  * Graves et al. (2014) Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural turing machines.  _CoRR_ , abs/1410.5401, 2014.  URL http://arxiv.org/abs/1410.5401.
  * Kingma & Ba (2014) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _CoRR_ , abs/1412.6980, 2014.  URL http://dblp.uni-trier.de/db/journals/corr/corr1412.html#KingmaB14.
  * Koch et al. (2015) Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov.  Siamese neural networks for one-shot image recognition.  In _ICML Deep Learning Workshop_ , volume 2, 2015.
  * Lake et al. (2015) Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum.  Human-level concept learning through probabilistic program induction.  _Science_ , 350(6266):1332–1338, 2015.  ISSN 0036-8075.  doi: 10.1126/science.aab3050.  URL http://science.sciencemag.org/content/350/6266/1332.
  * Pang et al. (2018) K. Pang, M. Dong, Y. Wu, and T. Hospedales.  Meta-Learning Transferable Active Learning Policies by Deep Reinforcement Learning.  _ArXiv e-prints_ , June 2018.
  * Ravi & Larochelle (2018) Sachin Ravi and Hugo Larochelle.  Meta-learning for batch mode active learning, 2018.  URL https://openreview.net/forum?id=r1PsGFJPz.
  * Roy & McCallum (2001) Nicholas Roy and Andrew McCallum.  Toward optimal active learning through sampling estimation of error reduction.  In _Proceedings of the Eighteenth International Conference on Machine Learning_ , ICML ’01, pp. 441–448, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.  ISBN 1-55860-778-1.  URL http://dl.acm.org/citation.cfm?id=645530.655646.
  * Santoro et al. (2016a) Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap.  Meta-learning with memory-augmented neural networks.  In _Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48_ , ICML’16, pp. 1842–1850. JMLR.org, 2016a.  URL http://dl.acm.org/citation.cfm?id=3045390.3045585.
  * Santoro et al. (2016b) Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy P. Lillicrap.  One-shot learning with memory-augmented neural networks.  _CoRR_ , abs/1605.06065, 2016b.  URL http://arxiv.org/abs/1605.06065.
  * Sener & Savarese (2018) Ozan Sener and Silvio Savarese.  Active learning for convolutional neural networks: A core-set approach.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=H1aIuk-RW.
  * Settles (2009) Burr Settles.  Active learning literature survey.  Computer Sciences Technical Report 1648, University of Wisconsin–Madison, 2009.  URL http://axon.cs.byu.edu/~martinez/classes/778/Papers/settles.activelearning.pdf.
  * Seung et al. (1992) H. S. Seung, M. Opper, and H. Sompolinsky.  Query by committee.  In _Proceedings of the Fifth Annual Workshop on Computational Learning Theory_ , COLT ’92, pp. 287–294, New York, NY, USA, 1992. ACM.  ISBN 0-89791-497-X.  doi: 10.1145/130385.130417.  URL http://doi.acm.org/10.1145/130385.130417.
  * Shen et al. (2017) Yanyao Shen, Hyokun Yun, Zachary Lipton, Yakov Kronrod, and Animashree Anandkumar.  Deep active learning for named entity recognition.  In _Proceedings of the 2nd Workshop on Representation Learning for NLP_ , pp. 252–256. Association for Computational Linguistics, 2017.  URL http://aclweb.org/anthology/W17-2630.
  * Tong & Koller (2002) Simon Tong and Daphne Koller.  Support vector machine active learning with applications to text classification.  _J. Mach. Learn. Res._ , 2:45–66, March 2002.  ISSN 1532-4435.  doi: 10.1162/153244302760185243.  URL https://doi.org/10.1162/153244302760185243.
  * Vinyals et al. (2016) Oriol Vinyals, Charles Blundell, Tim Lillicrap, koray kavukcuoglu, and Daan Wierstra.  Matching networks for one shot learning.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), _Advances in Neural Information Processing Systems 29_ , pp. 3630–3638. Curran Associates, Inc., 2016.  URL http://papers.nips.cc/paper/6385-matching-networks-for-one-shot-learning.pdf.
  * Wang et al. (2017) Keze Wang, Dongyu Zhang, Ya Li, Ruimao Zhang, and Liang Lin.  Cost-effective active learning for deep image classification.  _IEEE Trans. Cir. and Sys. for Video Technol._ , 27(12):2591–2600, December 2017.  ISSN 1051-8215.  doi: 10.1109/TCSVT.2016.2589879.  URL https://doi.org/10.1109/TCSVT.2016.2589879.
  * Woodward & Finn (2017) Mark Woodward and Chelsea Finn.  Active one-shot learning.  _CoRR_ , abs/1702.06559, 2017.  URL http://arxiv.org/abs/1702.06559.
  * Zhang et al. (2017) Ye Zhang, Matthew Lease, and Byron C. Wallace.  Active discriminative text representation learning.  In _AAAI_ , pp. 3386–3392. AAAI Press, 2017.

##  Appendix A Appendix

###  A.1 LSTM baseline and NTM-augmented architectures

(a)

(b)

Figure 1: LSTM (Figure 1(a)) and NTM (figure 1(b)) architectures for active
learning task

###  A.2 Experimental Setting

Our experiments have an episodic stream-based setup. Each episode is composed
by $10$ items for each class, with $C$ number of classes. The $C$ different
classes are randomly sampled from the dataset before every episode and the
$10$ samples are randomly drawn for each of the $C$ classes. At the initial
time-step in every episode, the model receives an example from the dataset,
concatenated with a zero-vector of size equal to the number of classes $C$.
The output space of the model can be divided into two choices: classify the
example as one of $C$ possible classes or request the label of the example. As
in (Woodward & Finn, 2017), we use a LSTM with $200$ hidden units and a single
hidden layer. The hidden layer is connected with a fully connected linear
layer which outputs the Q-values. For training LSTM we use non-truncated BPTT
(Back-Propagation Through Time). Both the input size and output size depend on
the chosen number of classes per episode, with the notation $C$. The network
has an input size of $20\times 20+C=400+C$, and the output size of the fully
connected layer is $C+1$, where the last node always represents the ”request
label” -action.

Additionally, the model employs an epsilon-greedy exploration strategy, with
$\epsilon=0.05$. If the model chooses to explore, there are three possible
actions, each with $1/3$ probability. During the training process of the
reinforcement learning agent, following (Woodward & Finn, 2017), we assign a
reward of $r_{t}=-0.05$ for each label request, $r_{t}=1.0$ for correct
predicted label and $r_{t}=-1.0$ for wrong predicted label. We perform our
test on a Image Classification task by using the Omniglot dataset (Lake et
al., 2015), an image classification dataset consisting of $1623$ classes of
different characters from $50$ different alphabets where each class consist of
$20$ hand-drawn characters. We preprocess the dataset by following the same
procedure of (Vinyals et al., 2016). All the code of our experiments, for the
sake of reproducibility is available on github 222http:.

###  A.3 Training and Test

(a)

(b)

Figure 2: Average classification accuracy (Figure 2(a)) and request percentage
(Figure 2(b)) for k-shot predictions in LSTM (left side), NTM (middle) and
LRUA (right side). The red line indicates the switch between training and the
test set for validation