{'fraction_non_alphanumeric': 0.036748746351321006, 'fraction_numerical': 0.008532295486864756, 'mean_word_length': 4.683538919608677, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Adversarially-Enhanced k-Nearest Neighbors

Recent works have theoretically and empirically shown that deep neural networks (DNNs) have an inherent vulnerability to small perturbations. Applying the Deep k-Nearest Neighbors (DkNN) classifier, we observe a dramatically increasing robustness-accuracy trade-off as the layer goes deeper. In this work, we propose a Deep Adversarially-Enhanced k-Nearest Neighbors (DAEkNN) method which achieves higher robustness than DkNN and mitigates the robustness-accuracy trade-off in deep layers through two key elements. First, DAEkNN is based on an adversarially trained model. Second, DAEkNN makes predictions by leveraging a weighted combination of benign and adversarial training data. Empirically, we find that DAEkNN improves both the robustness and the robustness-accuracy trade-off on MNIST and CIFAR-10 datasets.


I. INTRODUCTION
Deep learning has become the backbone of many applications, such as machine translation [1], image classification [2], and object detection [3]. Advanced deep neural network (DNN) models like convolutional neural network (CNN) [4] and recurrent neural network (RNN) [5] result in superiority over conventional models [6]. As a side effect, these DNNbased applications only perform well when the input is similar to the examples in the training set, i.e., when the covariate shift of the representation is small compared with the training distribution. A large shift will result in a significant accuracy degradation [7]. More seriously, recent studies have shown that DNNs are easily fooled by adversarial examples, which are well-designed with imperceptible (to the human eyes) perturbations on benign inputs [8; 9]. The lacking of robustness and the big trade-off between the standard performance and the robustness have become bottlenecks of deep learning.
To tackle the problems, various approaches have been proposed. One category of methods is robust training, which mainly focuses on hardening model weights [10; 11; 12] via augmenting benign examples with adversarial perturbations in the training process. This type of method is often tailored to a certain level of attack power, and is restricted to p constraint perturbations. Another category of methods is the adversarial detection [13; 14; 15] assuming that the adversarial distribution is significantly different from the benign data distribution, which is not always true in practice [16]. Strikingly, k-Nearest Neighbors (kNN)-based deep learning methods are recently demonstrated to have natural robustness defending against adversarial attacks [17; 18; 19] and can be leveraged to tackle other types of data quality issues beyond adversarial examples [20]. However, the Deep k-Nearest Neighbors (DkNN) method on a standard CIFAR-10 model suffers from poor robustness and big robustness-accuracy trade-off as the layer goes deeper, as illustrated by the blue curves in Figure 1. In this work, we analyze the reasons for the failure of DkNN, and propose a novel robust classifier -Deep Adversarially-Enhanced k-Nearest Neighbors (DAEkNN) that combines the kNN with the adversarial training [21] and a benign-adversarial joint prediction mechanism. We show that DAEkNN can achieve higher robustness and alleviate the robustness-accuracy tradeoff compared with DkNN, as illustrated by the red curves in Figure 1.
We make the following contributions in our paper.
• We show that the robustness-accuracy trade-off measured by the Deep k-Nearest Neighbors (DkNN) increases dramatically when the layer goes deeper. • We propose a Deep Adversarially-Enhanced k-Nearest Neighbors (DAEkNN) method that is based on an adversarially trained [21] model and a benign-adversarial joint prediction mechanism. • We demonstrate that DAEkNN enhances robustness and alleviates the robustness-accuracy trade-off. Specifically, on MNIST and CIFAR-10 datasets, DAEkNN improves DkNN robustness against PGD attack by 68.2% and 50.42% with 0.88% and 13.34% standard accuracy degradation.

II. DAEKNN DESIGN A. Preliminaries
Throughout this paper, we evaluate different classifiers by measuring three key indices: (i) Standard Accuracy (SA) on benign test examples (ii) Adversarial Accuracy (AA) on the adversarial test examples generated by 10-step Projected Gradient Descent (PGD) attack [21] and (iii) Harmonic Mean (HM) of AA and SA, which can be calculated by 2SA×AA SA+AA . HM is determined by both SA and AA, reflecting the robustnessaccuracy trade-off to a certain extend. a) Projected Gradient Descent (PGD) attack: PGD attack generates adversarial examples x δ = x + δ to flip the prediction via maximizing the cross-entropy loss L. The generator implements gradient ascent with projection, with the ith iterations defined as where f θ is the mapping from DNN input to output. κ is the gradient step size. denotes a projection operator, and Here is a positive constant, and we use · p = · ∞ in this paper. If not otherwise specified, we use the attack power = 8/80 for CIFAR-10/MNIST. d is the input dimension.
[v lb , v ub ] is the constraint on the data domain. In this paper, we consider x δ as an image vector, thereby b) Deep k-Nearest Neighbors (DkNN): Different from DNN classifiers, DkNN [17] combines kNN classifiers that are embedded into selected layers of a DNN, and makes predictions via majority vote among all kNNs. For any test input x, DkNN classifies it to where L is the set of the selected layers and l ∈ L is the l-th layer of a DNN. f θ l denotes the mapping from input to layer l. Here p c l (x) denotes the confidence score assigned to class c predicted by the corresponding kNN in layer l. We use tr . Let K l c be the number of data points belonging to class c among the K nearest neighbors found via measuring dist f θ l (x), f θ l (X b tr (j)) , ∀j ∈ |X b tr |, where | · | means the cardinality of a set. We use 2 distance for dist(·, ·) by default. The confidence score can be calculated by p c l (x; D b tr ) = K l c K . By default, DkNN is applied on a model trained by standard training. From Figure 1, one can see that the adversarial accuracy obtained by DkNN drops dramatically as the layer goes deeper. As the standard accuracy obtained by DkNN monoton-ically increases, the robustness-accuracy trade-off also rises. To improve both the robustness and robustness-accuracy tradeoff, we introduce a Deep Adversarially-Enhanced k-Nearest Neighbors (DAEkNN) method containing two key components: (i) A DNN model obtained by adversarial training (ii) A joint prediction mechanism leveraging benign and adversarial training data. We introduce each of them in detail below. In the training phase, a DNN is trained with adversarial data augmentation [21]. In the inference phase, the prediction is made by a joint classifier applied on deep layers of the adversarially trained DNN and combined the k-nearest neighbors (kNN) classifiers based on benign training data and its adversarial counterpart.

B. Improving Robustness Through Adversarially Trained Model
From Figure 1, one can see that the adversarial accuracy of DkNN drops dramatically as the layer goes deeper, indicating the features learned by DNN lack robustness. In order to robustify k-nearest neighbor classifiers in deep layers, we need the features extracted from those layers to be robust beforehand. Recent works have demonstrated that models trained by standard training tend to learn non-robust features, while models trained by adversarial training [21] are able to extract more robust features [22; 23; 24].
As shown in Figure 2, the adversarial training is performed by updating model weights with adversarial examples generated from benign data in each epoch, and can be characterized by the following optimization problem.
where tr is the attack power of the adversarial generator in the training process, and in this paper we fix it to tr = 4 and tr = 60 for CIFAR-10 and MNIST, respectively. S denotes a subset of D b tr . We remark that there are different robust training methods [21; 11] that can be leveraged to harden DNNs, and we only focus on the adversarial training method [21].

C. Improving Robustness Trough Adversarial Training Data
Note that adversarial perturbations are intended to enlarging the gap between the adversarial test distribution and the distribution of the original benign class. Using benign training distribution as the baseline, the covariate shift of the adversarial test distribution is larger than the covariate shift of the benign test distribution. For this reason, when all k-nearest neighbors are found from benign training data, the kNN classifiers are not able to correctly capture the information of the adversarial distribution. Spurred by that, we ask: Is it possible to better handle the covariate shift as well as obtaining more robust classifiers by changing the baseline (benign) distribution to a benign-adversarial combined distribution (in other words, by adding adversarial examples into the kNN searching space)?
Instead of using (2), we propose a benign-adversarial joint prediction mechanism that robustifies classifiers through incorporating the adversarial training data, as illustrated in the inference stage in Figure 2. Mathematically, the benign-adversarial joint prediction is expressed by the following formula.
where D a tr denotes the adversarial training data obtained by applying PGD attack on D b tr .
Here D a tr serves as the hardening dataset. We therefore call r the hardening strength. We remark that r is not as larger as better. For DAEkNN to be useful, we need to ensure that the features extracted by deep layers contain useful class information. For example, a model trained by standard training cannot tolerate large perturbations, and therefore using a large r will hurt the performance. In contrast, an adversarially trained model can extract class-relevant features from both benign data and perturbed data. In this sense, an adversarially trained model results in narrower gap between the representations of benign examples and the adversarial examples. ω l a and ω l b are weights of the two classifiers. Note that (4) is not a simple mixed up of the benign and adversarial training data. Instead, the new classifier in a single layer is a weighted combination of two classifiers. The weights ω l a , ω l b are calculated based on the relative distance of the kNN found by the two classifiers. , where X b l denotes the kNN of x found from D b tr on layer l, and similarly, X a l denotes the kNN of x found from D a tr on layer l. We use the softmax version of the distance-based weights. One can see that the weight is large when the corresponding distance is small, and ω l a + ω l b = 1.
(4) refines the decision boundaries of (2) by leveraging the combined and weighted classifiers. The implementation details can be viewed in Algorithm 1. We also refer readers to Section III for the ablation study and comparisons.

Algorithm 1 Deep Adversarially-Enhanced k-Nearest Neighbors (DAEkNN)
Input: Model θ trained by adversarial training with tr ; the selected layers L; hardening strength r ; test input x ; number of nearest neighbors K. Generate D a tr from D b tr through (5). for All l ∈ L do Find K nearest neighbors X b l and X a l from D b tr and D a tr , respectively. Count the number of data belonging to class c (K l c ) among each of X b l and X a l . Calculate p c l (x ; D b tr ) and p c l (x ; D a tr ) using (6). end for Obtain the final prediction by (4). Output: y.
We also consider leave-one-out versions of DAEkNN, which can be viewed as an ablation study. The two variants of DAEkNN are DAEkNN without adversarial training component (DAEkNN-WAT) and DAEkNN without adversarial training data (DAEkNN-WAD). As explained in Section II-C, the hardening strength r needs to be set small for a model trained by standard training. We therefore set r = 2 for DAEkNN-WAT. One can see from Table II that      adversarial training data, DAEkNN improves the robustness of DAEkNN-WAD by 3.82%. We then study how the hardening strength r affects the performance of DAEkNN. As shown in Figure 3, increasing r from 0−8 improves the robustness without appreciable loss of standard accuracy.

IV. CONCLUSION
In this work, we propose a new deep neural network (DNN)-based classifier, called Deep Adversarially-Enhanced k-Nearest Neighbors (DAEkNN), which enjoys high robustness and can mitigate the robustness-accuracy trade-off. We first study the performance of single-layer Deep k-Nearest neighbors (DkNN) on each layer of a DNN. The results indicate that DkNN has poor robustness and big robustnessaccuracy trade-offs. The proposed DAEkNN improves robustness through two key adversarial components. DAEkNN extracts features from an adversarially trained model that can provide more robust features. DAEkNN utilizes both the benign training data and adversarial training data in a benign-adversarial joint prediction classifier. The experiments on MNIST and CIFAR-10 demonstrate the effectiveness of DAEkNN.
In future work, we will (i) consider more attack types; (ii) explore the combinations of adversarial training data generated by different hardening strength and different attack types, which could potentially improve the robustness under stronger and unforeseen attacks; (iii) provide a theoretical analysis of the DAEkNN.