summaries: The paper identifies the gradient vanishing issue in the robustness of binary quantized networks. Therefore, it proposes to use temperature scaling approach in the attack generation. It has two methods for the temperature scale: (1) singular values of the input-output Jacobian and (2) maximizing the norm of the Hessian of the loss.

summaries: **Update**: Thanks to the authors for addressing my comments. As it was pointed out by the authors, temperature rescaling is mostly applicable to non-linear loss functions. For linear loss functions, temperature scaling only linear rescales the gradients. The difference between the proposed PGD++ attack and PGD with linear DLR loss is small (see the author's response to AR4). The improvements are most significant for FGSM but FGSM is not recommended for the robustness evaluation. Given the limited technical novelty and small improvements for linear loss functions, my score remains unchanged.

summaries: This work starts by questioning the apparent robustness of quantized networks and demonstrates that such robustness is more so a failure of the attack algorithm in picking up the gradient signal. The authors address this by tuning a scalar multiplier applied to the network logits, which doesn’t modify the model’s decision boundary. Through analyzing the Jacobian, two approaches are proposed to determine the scalar $\beta$ without tuning it by performing the attack. This approach is quite effective on quantized networks and even provides significant improvement on floating-point networks combining with existing attacks like FGSM and PGD. The proposed modification might seem trivial at first, but it constitutes an important factor the community hasn’t taken notice of, to the best of my knowledge.

abstractText: Neural network quantization has become increasingly popular due to efficient memory consumption and faster computation resulting from bitwise operations on the quantized networks. Even though they exhibit excellent generalization capabilities, their robustness properties are not well-understood. In this work, we systematically study the robustness of quantized networks against gradient based adversarial attacks and demonstrate that these quantized models suffer from gradient vanishing issues and show a fake sense of robustness. By attributing gradient vanishing to poor forward-backward signal propagation in the trained network, we introduce a simple temperature scaling approach to mitigate this issue while preserving the decision boundary. Despite being a simple modification to existing gradient based adversarial attacks, experiments on CIFAR-10/100 datasets with multiple network architectures demonstrate that our temperature scaled attacks obtain near-perfect success rate on quantized networks while outperforming original attacks on adversarially trained models as well as floating-point networks.

authors:
Thalaiyasingam Ajanthan
Puneet K Dokania
Richard Hartley
Philip HS Torr

title: Proximal mean-field for neural network quantization

authors:
Thalaiyasingam Ajanthan
Kartik Gupta
Philip HS Torr
Richard Hartley
Puneet K Dokania

title: Mirror descent view for neural network quantization

venue: arXiv preprint arXiv:1910.08237,

authors:
Maksym Andriushchenko
Francesco Croce
Nicolas Flammarion
Matthias Hein

title: Square attack: a query-efficient black-box adversarial attack via random search

venue: In European Conference on Computer Vision,

authors:
Anish Athalye
Nicholas Carlini
David Wagner

title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

venue: arXiv preprint arXiv:1802.00420,

authors:
Yu Bai
Yu-Xiang Wang
Edo Liberty

title: Proxquant: Quantized neural networks via proximal operators

authors:
Rémi Bernhard
Pierre-Alain Moellic
Jean-Max Dutertre

title: Impact of low-bitwidth quantization on the adversarial robustness for embedded neural networks

venue: In 2019 International Conference on Cyberworlds (CW),

authors:
Wieland Brendel
Jonas Rauber
Matthias Kümmerer
Ivan Ustyuzhaninov
Matthias Bethge

title: Accurate, reliable and fast robustness evaluation

venue: In Advances in Neural Information Processing Systems,

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: In IEEE Symposium on Security and Privacy,

authors:
Anirban Chakraborty
Manaar Alam
Vishal Dey
Anupam Chattopadhyay
Debdeep Mukhopadhyay

title: Adversarial attacks and defences: A survey

venue: arXiv preprint arXiv:1810.00069,

authors:
Matthieu Courbariaux
Yoshua Bengio
Jean-Pierre David

title: Binaryconnect: Training deep neural networks with binary weights during propagations

venue: NeurIPS,

authors:
Francesco Croce
Matthias Hein

title: Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks

authors:
Chris Finlay
Aram-Alexandre Pooladian
Adam Oberman

title: The logbarrier adversarial attack: making effective use of decision boundary information

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Angus Galloway
Graham W. Taylor
Medhat Moussa

title: Attacking binarized neural networks

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: In Proceedings of the thirteenth international conference on artificial intelligence and statistics,

title: Gradient masking causes clever to overestimate adversarial perturbation size

venue: arXiv preprint arXiv:1804.07870,

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Chuan Guo
Geoff Pleiss
Yu Sun
Kilian Q Weinberger

title: On calibration of modern neural networks

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Itay Hubara
Matthieu Courbariaux
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Quantized neural networks: Training neural networks with low precision weights and activations

authors:
Elias B Khalil
Amrita Gupta
Bistra Dilkina

title: Combinatorial attacks on binarized neural networks

authors:
Ji Lin
Chuang Gan
Song Han

title: Defensive quantization: When efficiency meets robustness

authors:
Yao Lu
Stephen Gould
Thalaiyasingam Ajanthan

title: Bidirectional self-normalizing neural networks

venue: arXiv preprint arXiv:2006.12169,

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,

title: Training wide residual networks for deployment using a single bit for each weight

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

title: Deepfool: a simple and accurate method to fool deep neural networks

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Jonathan Uesato
Pascal Frossard

title: Robustness via curvature regularization, and vice versa

authors:
Maria-Irina Nicolae
Mathieu Sinn
Minh Ngoc Tran
Beat Buesser
Ambrish Rawat
Martin Wistuba
Valentina Zantedeschi
Nathalie Baracaldo
Bryant Chen
Heiko Ludwig

title: Adversarial robustness toolbox

venue: arXiv preprint arXiv:1807.01069,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in PyTorch

authors:
Jeffrey Pennington
Samuel Schoenholz
Surya Ganguli

title: Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice

venue: In Advances in neural information processing systems,

authors:
Chongli Qin
James Martens
Sven Gowal
Dilip Krishnan
Krishnamurthy Dvijotham
Alhussein Fawzi
Soham De
Robert Stanforth
Pushmeet Kohli

title: Adversarial robustness through local linearization

title: Xnor-net: Imagenet classification using binary convolutional neural networks

authors:
Jonas Rauber
Wieland Brendel
Matthias Bethge

title: Foolbox: A python toolbox to benchmark the robustness of machine learning models

venue: arXiv preprint arXiv:1707.04131,

authors:
Andrew M Saxe
James L McClelland
Surya Ganguli

title: Exact solutions to the nonlinear dynamics of learning in deep linear neural networks

venue: arXiv preprint arXiv:1312.6120,

authors:
Sanchari Sen
Balaraman Ravindran
Anand Raghunathan

title: Empir: Ensembles of mixed precision deep networks for increased robustness against adversarial attacks

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

title: Intriguing properties of neural networks

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:
Florian Tramer
Nicholas Carlini
Wieland Brendel
Aleksander Madry

title: On adaptive attacks to adversarial example defenses

venue: arXiv preprint arXiv:2002.08347,

authors:
Tsui-Wei Weng
Huan Zhang
Pin-Yu Chen
Jinfeng Yi
Dong Su
Yupeng Gao
Cho-Jui Hsieh
Luca Daniel

title: Evaluating the robustness of neural networks: An extreme value theory approach

authors:
Zhewei Yao
Amir Gholami
Peng Xu
Kurt Keutzer
Michael W Mahoney

title: Trust region based

title: Both our variants outperform stronger attacks

title: 2019)) on BNN-WAQ trained on CIFAR-10 dataset in Table 9

title: sign(∂`(β)/∂x)‖2 are larger for our NJS and HNS variant (for most of the networks) as compared with network with no β, which clearly indicates better gradients for performing gradient based attacks. β, even for robust (locally linear) (Moosavi-Dezfooli et al

heading: 1 INTRODUCTION

text:
Neural Network (NN) quantization has become increasingly popular due to reduced memory and time complexity enabling real-time applications and inference on resource-limited devices. Such quantized networks often exhibit excellent generalization capabilities despite having low capacity due to reduced precision for parameters and activations. However, their robustness properties are not wellunderstood. In particular, while parameter quantized networks are claimed to have better robustness against gradient based adversarial attacks (Galloway et al. (2018)), activation only quantized methods are shown to be vulnerable (Lin et al. (2019)).
In this work, we consider the extreme case of Binary Neural Networks (BNNs) and systematically study the robustness properties of parameter quantized models, as well as both parameter and activation quantized models against gradient based adversarial attacks. Our analysis reveals that these quantized models suffer from gradient masking issues (Athalye et al. (2018)) (especially vanishing gradients) and in turn show fake robustness. We attribute this vanishing gradients issue to poor forward-backward signal propagation caused by trained binary weights, and our idea is to improve signal propagation of the network without affecting the prediction of the classifier.
There is a body of work on improving signal propagation in a neural network (e.g., Glorot & Bengio (2010); Pennington et al. (2017); Lu et al. (2020)), however, we are facing a unique challenge of improving signal propagation while preserving the decision boundary, since our ultimate objective is to generate adversarial attacks. To this end, we first discuss the conditions to ensure informative gradients and then resort to a temperature scaling approach (Guo et al. (2017)) (which scales the logits before applying softmax cross-entropy) to show that, even with a single positive scalar the vanishing gradients issue in BNNs can be alleviated achieving near perfect success rate in all tested cases.
Specifically, we introduce two techniques to choose the temperature scale: 1) based on the singular values of the input-output Jacobian, 2) by maximizing the norm of the Hessian of the loss with respect to the input. The justification for the first case is that if the singular values of input-output Jacobian are concentrated around 1 (defined as dynamical isometry (Pennington et al. (2017))) then the network is said to have good signal propagation and we intend to make the mean of singular
values to be 1. On the other hand, the intuition for maximizing the Hessian norm is that if the Hessian norm is large, then the gradient of the loss with respect to the input is sensitive to an infinitesimal change in the input. This is a sufficient condition for the network to have good signal propagation as well as informative gradients under the assumption that the network does not have any randomized or non-differentiable components.
We evaluated our improved gradient based adversarial attacks using BNNs with weight quantized (BNN-WQ) and weight and activation quantized (BNN-WAQ), floating point networks (REF), and adversarially trained models. We employ quantized and floating point networks trained on CIFAR10/100 datasets using several architectures. In all tested BNNs, both versions of our temperature scaled attacks obtained near-perfect success rate outperforming gradient based attacks (FGSM (Goodfellow et al. (2014)), PGD (Madry et al. (2017))). Furthermore, this temperature scaling improved gradient based attacks even on adversarially trained models (both high-precision and quantized) as well as floating point networks, showing the significance of signal propagation for adversarial attacks.

heading: 2 PRELIMINARIES

text: We first provide some background on the neural network quantization and adversarial attacks.

heading: 2.1 NEURAL NETWORK QUANTIZATION

text:
Neural Network (NN) quantization is defined as training networks with parameters constrained to a minimal, discrete set of quantization levels. This primarily relies on the hypothesis that since NNs are usually overparametrized, it is possible to obtain a quantized network with performance comparable to the floating point network. Given a dataset D = {xi,yi}ni=1, NN quantization can be written as:
min w∈Qm L(w;D) := 1 n n∑ i=1 `(w; (xi,yi)) . (1)
Here, `(·) denotes the input-output mapping composed with a standard loss function (e.g., crossentropy loss), w is them dimensional parameter vector, andQ is a predefined discrete set representing quantization levels (e.g., Q = {−1, 1} in the binary case). Most of the NN quantization approaches (Ajanthan et al. (2019a;b); Bai et al. (2019); Hubara et al. (2017)) convert the above problem into an unconstrained problem by introducing auxiliary variables and optimize via (stochastic) gradient descent. To this end, the algorithms differ in the choice of quantization set (e.g., keep it discrete (Courbariaux et al. (2015)), relax it to the convex hull (Bai et al. (2019)) or convert the problem into a lifted probability space (Ajanthan et al. (2019a))), the projection used, and how differentiation through projection is performed. In the case when the constraint set is relaxed, a gradually increasing annealing hyperparameter is used to enforce a quantized solution (Ajanthan et al. (2019a;b); Bai et al. (2019)). We refer the interested reader to respective papers for more detail. In this paper, we use BNN-WQ obtained using MD-tanh-S (Ajanthan et al. (2019b)) and BNN-WAQ obtained using Hubara et al. (2017).

heading: 2.2 ADVERSARIAL ATTACKS

text:
Adversarial examples consist of imperceptible perturbations to the data that alter the model’s prediction with high confidence. Existing attacks can be categorized into white-box and black-box attacks where the difference lies in the knowledge of the adversaries. White-box attacks allow the adversaries access to the target model’s architecture and parameters, whereas black-box attacks can only query the model. Since white-box gradient based attacks are popular, we summarize them below.
First-order gradient based attacks can be compactly written as Projected Gradient Descent (PGD) on the negative of the loss function (Madry et al. (2017)). Formally, let x0 ∈ IRN be the input image, then at iteration t, the PGD update can be written as:
xt+1 = P ( xt + η gtx ) , (2)
where P : IRN → X is a projection, X ⊂ IRN is the constraint set that bounds the perturbations, η > 0 is the step size, and gtx is a form of gradient of the loss with respect to the input x evaluated at xt. With this general form, the popular gradient based adversarial attacks can be specified:
• Fast Gradient Sign Method (FGSM): This is a one step attack introduced in Goodfellow et al. (2014). Here, P is the identity mapping, η is the maximum allowed perturbation magnitude, and
gtx = sign (∇x`(w∗; (xt,y))), where ` denotes the loss function, w∗ is the trained weights and y is the ground truth label corresponding to the image x0. • PGD with L∞ bound: Arguably the most popular adversarial attack introduced in Madry et al. (2017) and sometimes referred to as Iterative Fast Gradient Sign Method (IFGSM). Here, P is the L∞ norm based projection, η is a chosen step size, and gtx = sign (∇x`(w∗; (xt,y))), the sign of gradient same as FGSM. • PGD with L2 bound: This is also introduced in Madry et al. (2017) which performs the standard PGD in the Euclidean space. Here, P is the L2 norm based projection, η is a chosen step size, and gtx = ∇x`(w∗; (xt,y)) is simply the gradient of the loss with respect to the input.
These attacks have been further strengthened by a random initial step (Tramèr et al. (2017)). In this paper, we perform this single random initialization for all experiments with FGSM/PGD attack unless otherwise mentioned.

heading: 3 ROBUSTNESS EVALUATION OF BINARY NEURAL NETWORKS

text:
We start by evaluating the adversarial accuracy (i.e. accuracy on the perturbed data) of BNNs using the PGD attack with L∞ bound.
• PGD attack details: perturbation bound of 8 pixels (assuming each pixel in the image is in [0, 255]) with respect to L∞ norm, step size η = 2 and the total number of iterations T = 20. The attack details are the same in all evaluated settings unless stated otherwise.
We perform experiments on CIFAR-10 dataset using ResNet-18 and VGG-16 architectures and report the clean accuracy and PGD adversarial accuracy with 1 and 20 random restarts in Table 1. It can be clearly and consistently observed that binary networks have high adversarial accuracy compared to the floating point counterparts. Even with 20 random restarts, BNNs clearly outperform floating point networks in terms of adversarial accuracy. Since this result is surprising, we investigate this phenomenon further to understand whether BNNs are actually robust to adversarial perturbations or they show a fake sense of security due to some form of obfuscated gradients (Athalye et al. (2018)).

heading: 3.1 IDENTIFYING OBFUSCATED GRADIENTS

text:
Recently, it has been shown that several defense mechanisms intentionally or unintentionally break gradient descent and cause obfuscated gradients and thus exhibit a false sense of security (Athalye et al. (2018)). Several gradient based adversarial attacks tend to fail to produce adversarial perturbations in scenarios where the gradients are uninformative, referred to as gradient masking. Gradient masking
can occur due to shattered gradients, stochastic gradients or exploding and vanishing gradients. We try to identify gradient masking in binary networks based on the empirical checks provided in Athalye et al. (2018). If any of these checks fail, it indicates gradient masking issue in BNNs.
To illustrate this, we analyse the effects of varying different hyperparameters of PGD attack on BNNs trained on CIFAR-10 using ResNet-18 architecture. Even though varying PGD perturbation bound does not show any signs of gradient masking, varying attack iterations and black-box vs white-box results (on ResNet-18 and VGG-16) clearly indicate gradient masking issues as depicted in Fig. 1. The black-box attack outperforming white-box attack for BNNs certainly indicates gradient masking issues since the black-box attack do not use the gradient information from model being attacked. Here, our black-box model to a BNN is the analogous floating point network trained on the same dataset and the attack is the same PGD with L∞ bound.
These checks demonstrate that BNNs are prone to gradient masking and exhibit fake robustness. Note, shattered gradients occur due to non-differentiable components in the defense mechanism and stochastic gradients are caused by randomized gradients. Since BNNs are trainable from scratch and does not have randomized gradients1, we narrow down gradient masking issue to vanishing or exploding gradients. Since, vanishing or exploding gradients occur due to poor signal propagation, by introducing a single scalar, we discuss two approaches to mitigate this issue, which lead to almost 100% success rate for gradient based attacks on BNNs.

heading: 4 SIGNAL PROPAGATION OF NEURAL NETWORKS

text:
We first describe how poor signal propagation in neural networks can cause vanishing or exploding gradients. Then we discuss the idea of introducing a single scalar to improve the existing gradient based attacks without affecting the prediction (i.e., decision boundary) of the trained models.
We consider a neural network fw for an input x0, having logits aK = fw(x0). Now, since softmax cross-entropy is usually used as the loss function, we can write:
`(aK ,y) = −yT log(p) , p = softmax(aK) , (3)
where y ∈ IRd is the one-hot encoded target label and log is applied elementwise. For various gradient based adversarial attacks discussed in Sec. 2.2, gradient of the loss ` is used with respect to the input x0, which can also be formulated using chain rule as,
∂`(aK ,y) ∂x0 = ∂`(aK ,y) ∂aK ∂aK ∂x0 = ψ(aK ,y)J , (4)
where ψ denotes the error signal and J ∈ Rd×N is the input-output Jacobian. Here we use the convention that ∂v/∂u is of the form v-size × u-size. Notice there are two components that influence the gradients, 1) the Jacobian J and 2) the error signal ψ. Gradient based attacks would fail if either the Jacobian is poorly conditioned or the error signal has saturating gradients, both of these will lead to vanishing gradients in ∂`/∂x0.
The effects of Jacobian on the signal propagation is studied in dynamical isometry and mean-field theory literature (Pennington et al. (2017); Saxe et al. (2013)) and it is known that a network is said to satisfy dynamical isometry if the singular values of J are concentrated near 1. Under this condition, error signals ψ backpropagate isometrically through the network, approximately preserving its norm and all angles between error vectors. Thus, as dynamical isometry improves the trainability of the floating point networks, a similar technique can be useful for gradient based attacks as well.
In fact, almost all initialization techniques (e.g., Glorot & Bengio (2010)) approximately ensures that the Jacobian J is well-conditioned for better trainability and it is hypothesized that approximate isometry is preserved even at the end of the training. But, for BNNs, the weights are constrained to be {−1, 1} and hence the weight distribution at end of training is completely different from the random initialization. Furthermore, it is not clear that fully-quantized networks can achieve well-conditioned Jacobian, which guided some research activity in utilizing layerwise scalars (either predefined or learned) to improve BNN training (McDonnell (2018); Rastegari et al. (2016)). We would like to point out that the focus of this paper is to improve gradient based attacks on already trained BNNs. To
1BNN-WQ have binary weights, but there is no non-differentiable or randomized component once trained.
this end learning a new scalar to improve signal propagation at each layer is not useful as it can alter the decision boundary of the network and thus cannot be used in practice on already trained model.

heading: 4.1 TEMPERATURE SCALING FOR BETTER SIGNAL PROPAGATION

text:
In this paper, we propose to use a single scalar per network to improve the signal propagation of the network using temperature scaling. In fact, one could replace softmax with a monotonic function such that the prediction is not altered, however, we will show in our experiments that a single scalar with softmax has enough flexibility to improve signal propagation and yields almost 100% success rate with PGD attacks. Essentially, we can use a scalar, β > 0 without changing the decision boundary of the network by preserving the relative order of the logits. Precisely, we consider the following:
p(β) = softmax(āK) , āK = β aK . (5)
Here, we write the softmax output probabilities p as a function of β to emphasize that they are softmax output of temperature scaled logits. Now since in this context, the only variable is the temperature scale β, we denote the loss and the error signal as functions of only β. With this simplified notation the gradient of the temperature scaled loss with respect to the inputs can be written as:
∂`(β) ∂x0 = ∂`(β) ∂āK ∂āK ∂aK ∂aK ∂x0 = ψ(β)β J . (6)
Note that β affects the input-output Jacobian linearly while it nonlinearly affects the error signal ψ. To this end, we hope to obtain a β that ensures the error signal is useful (i.e., not all zero) as well as the Jacobian is well-conditioned to allow the error signal to propagate to the input.
We acknowledge that while one can find a β > 0 to obtain softmax output ranging from a uniform distribution (β = 0) to one-hot vectors (β → ∞), β only scales the Jacobian. Therefore, if the Jacobian J has zero singular values, our approach has no effect in those dimensions. However, since most of the modern networks consist of ReLU nonlinearities (generally positive homogeneous functions), the effect of a single scalar would be equivalent (ignoring the biases) to having layerwise scalars such as in McDonnell (2018). Thus, we believe a single scalar is sufficient for our purpose.

heading: 5 IMPROVED GRADIENTS FOR ADVERSARIAL ATTACKS

text:
Now we discuss strategies to choose a scalar β such that the gradients with respect to input are informative. Let us first analyze the effect of β on the error signal. To this end,
ψ(β) = ∂`(β)
∂p(β)
∂p(β)
∂āK = −(y − p(β))T . (7)
where y is the one-hot encoded target label, and p(β) is the softmax output of scaled logits.
For adversarial attacks, we only consider the correctly classified images (i.e., argmaxj yj = argmaxj pj(β)) as there is no need to generate adversarial examples corresponding
to misclassified samples. From the above formula, it is clear that when p(β) is one-hot encoding then the error signal is 0. This is one of the reason for vanishing gradient issue in BNNs. Even if this does not happen for a given image, one can increase β →∞ to make this error signal 0. Similarly, when p(β) is the uniform distribution, the norm of the error signal is at the maximum. This can be obtained by setting β = 0. However, this would also make ∂`(β)/∂x0 = 0 as the singular values of the input-output Jacobian would all be 0. How error signal is affected by β is illustrated in Fig. 2.
This analysis indicates that the optimal β cannot be obtained by simply maximizing the norm of the error signal and we need to balance both the Jacobian as well as the error signal. To summarize, the scalar β should be chosen such that the following properties are satisfied:
1. ‖ψ(β)‖2 > ρ for some ρ > 0. 2. The Jacobian β J is well-conditioned, i.e., the singular values of β J is concentrated around 1.

heading: 5.1 NETWORK JACOBIAN SCALING (NJS)

text:
We now discuss a straightforward, two-step approach to attain the aforementioned properties. Firstly, to ensure βJ is well-conditioned, we simply choose β to be the inverse of the mean of singular values
of J. This guarantees that the mean of singular values of βJ is 1. After this scaling, it is possible that the resulting error signal is very small. To ensure that ‖ψ(β)‖2 > ρ > 0, we ensure that the softmax output pk(β) corresponding to the ground truth class k is at least ρ away from 1. We now state it as a proposition to derive β given a lowerbound on 1− pk(β). Proposition 1. Let aK ∈ IRd with d > 1 and aK1 ≥ aK2 ≥ . . . ≥ aKd and aK1 − aKd = γ. For a given 0 < ρ < (d− 1)/d, there exists a β > 0 such that 1− softmax(βaK1 ) > ρ, then β < − log(ρ/(d− 1)(1− ρ))/γ. Proof. This is derived via a simple algebraic manipulation of softmax. Please refer to Appendix. This β can be used together with the one computed using inverse of mean Jacobian Singular Values (JSV). We provide the pseudocode for our proposed PGD++ (NJS) attack in Appendix. Similar approach can also be applied for FGSM++. Notice that, this approach is simple and it adds negligible overhead to the standard PGD attacks. However, it has a hyperparameter ρ which is hand designed. To mitigate this, next we discuss a hyperparameter-free approach to obtain β.

heading: 5.2 HESSIAN NORM SCALING (HNS)

text:
We now discuss another approach to obtain informative gradients. Our idea is to maximize the Frobenius norm of the Hessian of the loss with respect to the input, where the intuition is that if the Hessian norm is large, then the gradient ∂`/∂x0 is sensitive to an infinitesimal change in x0. This means, the infinitesimal perturbation in the input is propagated in the forward pass to the last layer and propagated back to the input layer without attenuation (i.e., the returned signal is not zero), assuming there are no randomized or non-differentiable components in the network. This clearly indicates that the network has good signal propagation as well as the error signals are not all zero. This objective can now be written as:
β∗ = argmax β>0 ∥∥∥∥∂2`(β)∂(x0)2 ∥∥∥∥ F = argmax β>0 ∥∥∥∥∥β [ ψ(β) ∂J ∂x0 + β ( ∂p(β) ∂āK J )T J ]∥∥∥∥∥ F . (8)
The derivation is provided in Appendix. Note, since J does not depend on β, J and ∂J/∂x0 are computed only once, β is optimized using grid search as it involves only a single scalar. In fact, it is easy to see from the above equation that, when the Hessian is maximized, β cannot be zero. Similarly, ψ(β) cannot be zero because if it is zero, then the prediction p(β) is one-hot encoding (Eq. (7)), consequently ∂p(β)/∂āK = 0 and this cannot be a maximum for the Hessian norm. Hence, this ensures that ‖ψ(β∗)‖2 > ρ for some ρ > 0 and β∗ is bounded according to Proposition 1. Therefore, the maximum is obtained for a finite value of β. Even though, it is not clear how exactly this approach
would affect the singular values of the input-output Jacobian (β J), we know that they are finite and not zero. How Hessian norm is influenced by β is illustrated in Fig. 3.
Furthermore, there are some recent works (Moosavi-Dezfooli et al. (2019); Qin et al. (2019)) show that adversarial training makes the loss surface locally linear around the vicinity of training samples and enforcing local linearity constraint on loss curvature can achieve better robust to adversarial attacks. On the contrary, our idea of maximizing the Hessian, i.e., increasing the nonlinearity of `, could make the network more prone to adversarial attacks and we intend to exploit that. The psuedocode for PGD++ attack with HNS is summarized in Appendix.

heading: 6 EXPERIMENTS

text:
We evaluate robustness accuracies of BNNs with weight quantized (BNN-WQ), weight and activation quantized (BNN-WAQ) floating point networks (REF), and adversarially trained networks. We evaluate our two PGD++ variants corresponding to Hessian Norm Scaling (HNS) and Network Jacobian Scaling (NJS) on CIFAR-10 and CIFAR-100 datasets with multiple network architectures. Briefly, our results indicate that both of our proposed attack variants yield attack success rate much higher than original PGD attacks not only on L∞ bounded attack but also on L2 bounded attacks on both floating point networks and binarized networks. Our proposed PGD++ variants also reduce PGD
adversarial accuracy of adversarially trained floating point and adversarially trained binarized neural networks while outperforming much stronger attacks such as DeepFool (Moosavi-Dezfooli et al. (2016)) and Brendel & Bethge Attack (BBA) (Brendel et al. (2019)). Among our variants, even though they perform similarly in our experiments, Hessian based scaling (HNS) outperforms Jacobian based scaling (NJS) in majority of the cases and this difference is significant for one step FGSM attacks. This indicates that nonlinearity of the network indeed has some relationship to its adversarial robustness.
We use state of the art models trained for binary quantization (where all layers are quantized) for our experimental evaluations. We provide adversarial attack parameters used for FGSM/PGD in Appendix and for other attacks, we use default parameters used in Foolbox (Rauber et al. (2017)). For our HNS variant, we sweep β from a range such that the hessian norm is maximized for each image, as explained in Appendix. For our NJS variant, we set the value of ρ = 0.01. In fact, our attacks are not very sensitive to ρ and we provide the ablation study in the Appendix. The PyTorch (Paszke et al. (2017)) implementation of our algorithm will be released upon publication.

heading: 6.1 RESULTS

text:
We first compared the original PGD (L2/L∞) and FGSM attack with both versions (NJS and HNS) of improved PGD++ and FGSM++ attack, on CIFAR-10/100 datasets with ResNet-18/50, VGG-16, DenseNet-121 and MobileNet-V2 network architectures and the adversarial accuracies for different BNN-WQ are reported in Table 2. Our PGD++ variants consistently outperform original PGD on all networks on both datasets. Even being a gradient based attack, our proposed PGD++ (L2/L∞) variants can in fact reach adversarial accuracy close to 0 on CIFAR-10 dataset, demystifying the fake robustness binarized networks tend to exhibit due to poor signal propagation.
Similarly, for one step FGSM attack, our modified versions outperform original FGSM attacks by a significant margin consistently for both datasets on various network architectures. We would like to point out such an improvement in the above two attacks is considerably interesting, knowing the fact that FGSM, PGD with L∞ attacks only use the sign of the gradients so improved performance indicates, our temperature scaling indeed makes some zero elements in the gradient nonzero. We would like to point out here that one can use several random restarts to increase the success rate of original form of FGSM/PGD attack further but to keep comparisons fair we use single random restart for both original and modified attacks. Nevertheless, as it has been observed in Table 1 even with 20 random restarts PGD adversarial accuracies for BNNs cannot reach zero, whereas our proposed PGD++ variants consistently achieve perfect success rate.
ImageNet. For other large scale datasets such as ImageNet, BNNs are hard to train with full binarization of parameters and result in poor performance. Thus, most existing works (Yang et al. (2019)) on BNNs keep the first and the last layers floating point and introduce several layerwise scalars to achieve good results on ImageNet. In such experimental setups, according to our experiments, trained BNNs do not exhibit gradient masking issues or poor signal propagation and thus are easier to attack using original FGSM/PGD attacks with complete success rate. In such experiments, our modified versions perform equally well compared to the original forms of these attacks.
The adversarial accuracies of REF and BNN-WAQ trained on CIFAR-10 using ResNet-18/50, VGG-16 and DenseNet-121 for our variants against original counterparts are reported in Table 3. Overall, for both REF and BNN-WAQ, our variants outperform the original counterparts consistently. Particularly interesting, PGD++ variants improve the attack success rate on REF networks. This effectively expands the applicability of our PGD++ variants and encourages to consider signal propagation of any trained network to improve gradient based attacks. PGD++ with L∞ variants achieve near-perfect success rate on all BNN-WAQs, again validating the hypotheses of fake robustness of BNNs.
To further demonstrate the efficacy, we first adversarially trained the BNN-WQs (quantized using BC (Courbariaux et al. (2015)), GD-tanh/MD-tanh-S (Ajanthan et al. (2019b))) and floating point networks in a similar manner as in Madry et al. (2017), using L∞ bounded PGD with T = 7
iterations, η = 2 and = 8. We report the adversarial accuracies of L∞ bounded attacks and our variants on CIFAR-10 using ResNet-18 in Table 4. These results further strengthens the usefulness of our proposed PGD++ variants. Moreover, with a heuristic choice of β = 0.1 to scale down the logits before performing gradient based attacks performs even worse. Finally, even against stronger attacks (DeepFool (Moosavi-Dezfooli et al. (2016)), BBA (Brendel et al. (2019))) under the same L∞ perturbation bound, our variants outperform consistently on these adversarially trained models. We would like to point out that our variants have negligible computational overhead over the original gradient based attacks, whereas stronger attacks are much slower in practice requiring 100-1000 iterations with an adversarial starting point (instead of random initial perturbation).
To illustrate the effectiveness of our proposed variants in improving signal propagation, we compare against gradient based attacks performed using recently proposed Difference of Logits Ratio (DLR) loss (Croce & Hein (2020)) that aims to avoid the issue of saturating error signals. We show these experimental comparisons performed on ResNet-18 models trained on CIFAR-10 dataset in Table 5. The attack parameters are same as used for the other experiments. It can be clearly observed that in almost all cases our proposed variants are much better than original form of gradient based attacks performed with DLR loss. The margin of difference is significant in case of FGSM attack and adversarial trained models. Infact, it is important to note that gradient based attacks with DLR loss perform worse on adversarially trained models than the original form of gradient based attacks.

heading: 7 RELATED WORK

text:
Adversarial examples are first observed in Szegedy et al. (2014) and subsequently efficient gradient based attacks such as FGSM (Goodfellow et al. (2014)) and PGD (Madry et al. (2017)) are introduced. There exist recent stronger attacks such as Moosavi-Dezfooli et al. (2016); Carlini & Wagner (2017); Yao et al. (2019); Finlay et al. (2019); Brendel et al. (2019), however, compared to PGD, they are much slower to be used for adversarial training in practice. For a comprehensive survey related to adversarial attacks, we refer the reader to Chakraborty et al. (2018).
Some recent works focus on the adversarial robustness of BNNs (Bernhard et al. (2019); Sen et al. (2020); Galloway et al. (2018); Khalil et al. (2019); Lin et al. (2019)), however, a strong consensus on the robustness properties of quantized networks is lacking. In particular, while Galloway et al. (2018) claims parameter quantized networks are robust to gradient based attacks based on empirical evidence, (Lin et al. (2019)) shows activation quantized networks are vulnerable to such attacks and proposes a defense strategy assuming the parameters are floating-point. Differently, Khalil et al. (2019) proposes a combinatorial attack hinting that activation quantized networks would have obfuscated gradients issue. Sen et al. (2020) shows ensemble of mixed precision networks to be more robust than original floating point networks; however Tramer et al. (2020) later shows the presented defense method can be attacked with minor modification in the loss function. In short, although it has been hinted that there might be some sort of gradient masking in BNNs (especially in activation quantized networks), a thorough understanding is lacking on whether BNNs are robust, if not what is the reason for the inferior performance of most commonly used gradient based attacks on binary networks. We answer this question in this paper and introduce improved gradient based attacks.

heading: 8 CONCLUSION

text: In this work, we have shown that both BNN-WQ and BNN-WAQ tend to show a fake sense of robustness on gradient based attacks due to poor signal propagation. To tackle this issue, we introduced our two variants of PGD++ attack, namely NJS and HNS. Our proposed PGD++ variants not only possess near-complete success rate on binarized networks but also outperform standard L∞ and L2 bounded PGD attacks on floating point networks. We finally show improvement in attack success rate on adversarially trained REF and BNN-WQ against stronger attacks (DeepFool and BBA). In future, we intend to focus more on improving the robustness of the BNNs with provable robustness guarantees.

heading: A PSEUDOCODE

text:
We provide pseudocode for PGD++ with NJS in Algorithm 1 and PGD++ with HNS in Algorithm 2.
Algorithm 1 PGD++ with NJS with L∞, T iterations, radius , step size η, network fw∗ , input x0, label k, one-hot y ∈ {0, 1}d, gradient threshold ρ. Require: T, , η, ρ,x0,y, k Ensure: ‖xT+1 − x0‖∞ ≤
1: β1 = (M d)/ (∑M
i=1 ∑d j=1 µj(Ji) ) . β1 computed using Network Jacobian.
2: x1 = P ∞(x 0 + Uniform(−1, 1)) . Random Initialization with Projection 3: for t← 1, . . . T do 4: β2 = 1.0 5: p′ = softmax(β1(fw∗(xt))) 6: if 1− p′k ≤ ρ then . ρ = 0.01 7: β2 = − log(ρ/(d− 1)(1− ρ))/γ . γ computed using Proposition 2 8: ` = −yT log(softmax(β2β1(fw∗(xt)))) 9: xt+1 = P ∞(x t + η sign(∇x`(xt))) . Update Step with Projection
Algorithm 2 PGD++ with HNS with L∞, T iterations, radius , step size η, network fw∗ , input x0, label k, one-hot y ∈ {0, 1}d, gradient threshold ρ. Require: T, , η,x0,y, k Ensure: ‖xT+1 − x0‖∞ ≤
1: x1 = P ∞(x 0 + Uniform(−1, 1)) . Random Initialization with Projection 2: β∗ = argmaxβ>0 ∥∥∂2`(β)/∂(x0)2∥∥ F . Grid Search 3: for t← 1, . . . T do 4: ` = −yT log(softmax(β∗(fw∗(xt)))) 5: xt+1 = P ∞(x t + η sign(∇x`(xt))) . Update Step with Projection

heading: B DERIVATIONS

text:
B.1 DERIVING β GIVEN A LOWERBOUND ON 1− pk(β)
Proposition 2. Let aK ∈ IRd with d > 1 and aK1 ≥ aK2 ≥ . . . ≥ aKd and aK1 − aKd = γ. For a given 0 < ρ < (d− 1)/d, there exists a β > 0 such that 1− softmax(βaK1 ) > ρ, then β < − log(ρ/(d− 1)(1− ρ))/γ.
Proof. Assuming aK1 − aKd = γ, we derive a condition on β such that 1− softmax(βaK1 ) > ρ.
1− softmax(βaK1 ) > ρ , (9) softmax(βaK1 ) < 1− ρ ,
exp(βaK1 )/ d∑ λ=1 exp(βaKλ ) < 1− ρ ,
1/ ( 1 + d∑ λ=2 exp(β(aKλ − aK1 )) ) < 1− ρ .
Since, aK1 − aKλ ≤ γ for all λ > 1,
1/ ( 1 + d∑ λ=2 exp(β(aKλ − aK1 )) ) ≤ 1/ ( 1 + d∑ λ=2 exp(−βγ) ) . (10)
Therefore, to ensure 1/ ( 1 + ∑d λ=2 exp(β(a K λ − aK1 )) ) < 1− ρ, we consider,
1/ ( 1 + d∑ λ=2 exp(−βγ) ) < 1− ρ , aK1 − aKλ ≤ γ for all λ > 1 , (11)
1/ ( 1 + (d− 1) exp(−βγ) ) < 1− ρ ,
exp(−βγ) > ρ/(d− 1)(1− ρ) , −βγ > log(ρ/(d− 1)(1− ρ)) , exp is monotone ,
β < − log(ρ/(d− 1)(1− ρ))/γ .
Therefore for any β < − log(ρ/(d− 1)(1− ρ))/γ, the above inequality 1− softmax(βaK1 ) > ρ is satisfied.
B.2 DERIVATION OF HESSIAN
We now derive the Hessian of the input mentioned in Eq. (8) of the paper. The input gradients can be written as:
∂`(β) ∂x0 = ∂`(β) ∂p(β) ∂p(β) ∂āK(β) βJ = ψ(β)βJ . (12)
Now by product rule of differentiation, input hessian can be written as:
∂2`(β) ∂(x0)2 = β
[ ψ(β) ∂J
∂x0 +
( ∂ψ(β)
∂x0
)T J ] , (13)
= β [ ψ(β) ∂J
∂x0 +
( ∂p(β)
∂x0
)T J ] , ψ(β) = −(y − p(β))T ,
= β [ ψ(β) ∂J
∂x0 + β
( ∂p(β)
∂āK J
)T J ] .

heading: C ADDITIONAL EXPERIMENTS

text:
In this section we first provide more experimental details and then some ablation studies.
C.1 EXPERIMENTAL DETAILS
We first mention the hyperparameters used to perform FGSM and PGD attack for all the experiments in the paper in Table 6. To make a fair comparison, we keep the attack parameters same for our proposed variants of FGSM++ and PGD++ attacks. For PGD++ with HNS variant, we maximize Frobenius norm of Hessian with respect to the input as specified in Eq. (8) of the paper by grid search for the optimum β. We would like to point out that since only ψ(β) and p(β) terms are dependent on β, we do not need to do forward and
backward pass of the network multiple times during the grid search. This significantly reduces the computational overhead during the grid search. We can simply use the same network outputs aK and network jacobian J (as computed without using β) for the grid search, while computing the other terms at each iteration of grid search. We apply grid search to find the optimum beta between 100 equally spaced intervals of β starting from β1 to β2. Here, β1 and β2 are computed based on Proposition 1 in the paper where ρ = 1e− 72 and ρ = 1− (1/d)− (1e− 2) respectively, where d is number of classes and γ = aK1 − aK2 so that 1− softmax(βaK1 ) < ρ. Also, note that we estimate the optimum β for each test sample only at the start of the first iteration of an iterative attack and then use the same β for the next iterations.
Computational Overhead of NJS and HNS. Our Jacobian calculation takes just a single backward pass through the network and thus adds a negligible overhead. Our NJS approach for scaling estimates β as inverse of mean JSV using 100 random test samples, which is similar to 100 backward passes. For HNS, in Eq. (8) Jacobian J can be computed in single backward pass. Moreover, for piecewise linear networks (eg, relu activations), ∂J/∂x0 = 0 almost everywhere (Yao et al. (2018)). Thus PGD++ with NJS and HNS is almost as efficient as PGD.
C.2 COMPARISONS AGAINST AUTO-PGD ATTACK AND GRADIENT FREE ATTACK
We also compared our proposed PGD++ variants against recently proposed Auto-PGD (APGD) with Difference of Logits Ratio (DLR) loss (Croce & Hein (2020)) and gradient free Square Attack (Andriushchenko et al. (2020)) on different networks trained using ResNet-18 and VGG-16 on CIFAR-10 dataset and the results are reported in Table 7. The attack parameters for this experiment are the same as reported in the paper. It can be clearly seen that our proposed variants perform much better than both APGD with DLR loss and Square Attack, consistently achieving 0% adversarial accuracy. Infact, much computationally expensive Square attack is unable to achieve 0% adversarial accuracy in any of the cases under the enforced L∞ bound.
C.3 OTHER EXPERIMENTS
We provide adversarial accuracy comparisons for different attack methods on CIFAR-100 using ResNet18, VGG-16, ResNet-50 and DenseNet-121 in Table 8. Again similar to the results in the paper, our proposed PGD++ and FGSM++ outperform original form of PGD and FGSM consistently in all the experiments on floating point networks. We also provide adversarial accuracy comparison of our proposed variants against stronger attacks namely DeepFool (Moosavi-Dezfooli et al. (2016)) and
BBA (Brendel et al. (2019)) on BNN-WAQ trained on CIFAR-10 dataset in Table 9. In this experiment, our proposed variants again outperform even the stronger attacks which take 100-1000 iterations with adversarial start point (instead of random initial perturbation). It should be noted that although BBA performs much better than DeepFool and PGD, it still has inferior success rate than ours considering the fact that it takes multiple hours to run BBA whereas our proposed variants are almost as efficient as PGD attack.
Step Size Tuning for PGD attack. We would like to point out that step size η and temperature scale β have different effects in the attacks performed. Notice, PGD and FGSM attack under L∞ bound only use the sign of input gradients in each gradient ascent step. Thus, if the input gradients are completely saturated (which is the case for BNNs), original forms of PGD or FGSM will not work irrespective of the step size used. To illustrate this, we performed extensive step size tuning for original form of PGD attack on different ResNet-18 models trained on CIFAR-10 dataset and the adversarial accuracies are reported in Fig. 4. It can be observed clearly that although tuning the step size lowers adversarial accuracy a bit in some cases but still cannot reach zero for BNNs unlike our proposed variants.
Adversarial training using PGD++. We also investigate the potential application of PGD++ for adversarial training to improve the robustness of neural networks. PGD++ attack is most effective when applied to a network with poor signal propagation. However, adversarial training is performed from random initialization (Glorot & Bengio (2010)) exhibiting good signal propagation. Thus, PGD and PGD++ perform similarly for adversarial training. We infer these conclusions from our experiments on adversarial training using PGD++.
CLEVER Scores. Recently CLEVER Scores (Weng et al. (2018)) have been proposed as an empirical estimate to measure robustness lower bounds for deep networks. It has been later shown that gradient masking issues cause
CLEVER to overestimate the robustness bounds (Goodfellow (2018)). Here we try to improve the CLEVER scores using different ways of choosing β in temperature scaling. For this experiment, we use CLEVER implementation of Adversarial Training Toolbox2 (Nicolae et al. (2018)). We set
2https://github.com/Trusted-AI/adversarial-robustness-toolbox
number of batches to 50, batch size to 10, radius to 5, and chose L1 norm as hyperparameters (based on the Weng et al. (2018)). We compare our variants namely NJS and HNS against heuristic choice of small β = 0.01 and original CLEVER Scores for BNN-WQ and BNN-WAQ (trained on CIFAR-10 using ResNet-18) in Table 10. It can be clearly seen that our proposed variants improve the robustness bounds computed using CLEVER whereas a heuristic choice of β = 0.01 performs even worse.
C.4 STABILITY OF PGD++ WITH NJS WITH VARIATIONS IN ρ
We perform ablation studies with varying ρ for PGD++ with NJS in Table 11 for CIFAR-10 dataset using ResNet-18 architecture. It clearly illustrates that our NJS variant is quite robust to the choice of ρ as we are able to achieve near perfect success rate with PGD++ with different values of ρ. As long as value of ρ is large enough to avoid one-hot encoding on softmax outputs (in turn avoid ‖ψ(β)‖ to be zero) of correctly classified sample, our approach with NJS variant is quite stable.
C.5 SIGNAL PROPAGATION AND INPUT GRADIENT ANALYSIS USING NJS AND HNS
We first provide an example illustration in Fig. 5 to better understand how the input gradient norm i.e., ‖∂`(β)/∂x0‖2, and norm of sign of input gradient, i.e., ‖sign(∂`(β)/∂x0)‖2 is influenced by β. It clearly shows that both the plots have a concave behavior where an optimal β can maximize the input gradient. Also, it can be quite evidently seen in Fig. 5 (b) that within an optimal range of β, gradient vanishing issue can be avoided. If β → 0 or β →∞, it changes all the values in input gradient matrix to zero and inturn ‖sign(∂`(β)/∂x0)‖2 = 0. We also provide the signal propagation properties as well as analysis on input gradient norm before and after using the β estimated based on NJS and HNS in Table 12. For binarized networks as well floating point networks tested on CIFAR-10 dataset using ResNet-18 architecture, our HNS and NJS variants result in larger values for ‖ψ‖2, ‖∂`(β)/∂x0‖2 and ‖sign(∂`(β)/∂x0)‖2. This reflects the efficacy of our method in overcoming the gradient vanishing issue. It can be also noted that our variants also improves the signal propagation of the networks by bringing the mean JSV values closer to 1.
C.6 ABLATION FOR ρ VS. PGD++ ACCURACY
In this subsection, we provide the analysis on the effect of bounding the gradients of the network output of ground truth class k, i.e. ∂`(β)/∂āKk . Here, we compute β using Proposition 1 for all correctly classified images such that 1− softmax(βaKk ) > ρ with different values of ρ and report the PGD++ adversarial accuracy in Table 13. It can be observed that there is an optimum value of ρ at which PGD++ success rate is maximized, especially on the adversarially trained models. This can also be seen in connection with the non-linearity of the network where at an optimum value of
β, even for robust (locally linear) (Moosavi-Dezfooli et al. (2019); Qin et al. (2019)) networks such as adversarially trained models, non-linearity can be maximized and better success rate for gradient based attacks can be achieved. Our HNS variant essentially tries to achieve the same objective while trying to estimate β for each example.


summaries: The authors propose ProtoryNet,  a prototype-based model for paragraph classification that associates each sentence in the paragraph with a relevant prototypical sentence from the training data. The idea is interesting and the ability to decompose sentiment scores over each sentence + find prototypes for each helps to build user understanding of the model prediction. Thank you to the authors for the submission.

summaries: this paper presents an RNN sequence classifying model that generates a prototype for each sentence in a paragraph. The generated prototypes help explain the model's prediction. The method embeds each sentence, matches to prototypes, then runs through an LSTM before making a prediction. Experiments found improved accuracy compared to a previous model that generates only one prototype for a paragraph. A user evaluation also found improvement in interpretability.

summaries: This paper presents ProtoryNet, a framework for text data that classifies and explains the prototypes' results.   The key concept, that is the novelty of the work, is that this framework is based on sentence prototypes, called prototype trajectory in the paper. In particular, instead of working at the entity of the text level, the text is split into sentences and each sentence is analyzed by itself.  The structure of the framework is composed of a layer that encodes a text's sequences, followed by a prototype layer in which is computed the similarity among each sentence and the prototype trajectories. At this point, the sentences are represented in one-hot encoding: for each sentence, there is a bunch of zero and then a one for the most similar sentence prototype. This representation is used for the classification of the sentence, done using an LSTM structure. In this setting, the interpretation is given by exploiting the prototypes matched for the text under analysis.

abstractText: We propose a novel interpretable recurrent neural network (RNN) model, called ProtoryNet, in which we introduce a new concept of prototype trajectories. Motivated by the prototype theory in modern linguistics, ProtoryNet makes a prediction by finding the most similar prototype for each sentence in a text sequence and feeding an RNN backbone with the proximity of each of the sentences to the prototypes. The RNN backbone then captures the temporal pattern of the prototypes, to which we refer as prototype trajectories. The prototype trajectories enable intuitive, fine-grained interpretation of how the model reached to the final prediction, resembling the process of how humans analyze paragraphs. Experiments conducted on multiple public data sets reveal that the proposed method not only is more interpretable but also is more accurate than the current state-of-the-art prototype-based method. Furthermore, we report a survey result indicating that human users find ProtoryNet more intuitive and easier to understand, compared to the other prototype-based methods.

title: Philosophy of language

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: arXiv preprint arXiv:1409.0473,

authors:
Chaofan Chen
Oscar Li
Daniel Tao
Alina Barnett
Cynthia Rudin
Jonathan K Su

title: This looks like that: Deep learning for interpretable image recognition

venue: In Advances in Neural Information Processing Systems,

authors:
Edward Choi
Mohammad Taha Bahadori
Jimeng Sun
Joshua Kulas
Andy Schuetz
Walter Stewart

title: Retain: An interpretable predictive model for healthcare using reverse time attention mechanism

authors:
James M Cupello
David J Mishelevich

title: Managing prototype knowledge/expert system projects

venue: Communications of the ACM,

authors:
Fahim Dalvi
Nadir Durrani
Hassan Sajjad
Yonatan Belinkov
Anthony Bau
James Glass

title: What is one grain of sand in the desert? analyzing individual neurons in deep nlp models

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Richard Fikes
Tom Kehler

title: The role of frame-based representation in reasoning

authors:
Tian Guo
Tao Lin
Yao Lu

title: An interpretable LSTM neural network for autoregressive exogenous model

venue: arXiv preprint arXiv:1804.05251,

authors:
Aya Abdelsalam Ismail
Mohamed Gunady
Luiz Pessoa
Hector Corrada Bravo
Soheil Feizi

title: Input-cell attention reduces vanishing saliency of recurrent neural networks

authors:
Sarthak Jain
Byron C Wallace

title: Attention is not explanation

venue: arXiv preprint arXiv:1902.10186,

authors:
Xisen Jin
Zhongyu Wei
Junyi Du
Xiangyang Xue
Xiang Ren

title: Towards hierarchical importance attribution: Explaining compositional semantics for neural sequence models

authors:
Andrej Karpathy
Justin Johnson
Li Fei-Fei

title: Visualizing and understanding recurrent networks

venue: arXiv preprint arXiv:1506.02078,

authors:
Been Kim
Cynthia Rudin
Julie A Shah

title: The Bayesian case model: A generative approach for case-based reasoning and prototype classification

authors:
Diederik P Kingma
Jimmy Ba

title: ADAM: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Scott M Lundberg
Su-In Lee

title: A unified approach to interpreting model predictions

authors:
Yao Ming
Panpan Xu
Huamin Qu
Liu Ren

title: Interpretable and steerable sequence learning via prototypes

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
W James Murdoch
Peter J Liu
Bin Yu

title: Beyond word importance: Contextual decomposition to extract interactions from lstms

venue: arXiv preprint arXiv:1801.05453,

authors:
Klaus-Uwe Panther
Klaus-Michael Köpcke

title: A prototype approach to sentences and sentence types

venue: Annual Review of Cognitive Linguistics,

authors:
Jeffrey Pennington
Richard Socher
Christopher D Manning

title: GloVe: Global vectors for word representation

venue: In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP),

authors:
Nils Reimers
Iryna Gurevych

title: Sentence-bert: Sentence embeddings using Siamese BERTnetworks

venue: arXiv preprint arXiv:1908.10084,

authors:
Marco Tulio Ribeiro
Sameer Singh
Carlos Guestrin

title: why should i trust you?” explaining the predictions of any classifier

venue: In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,

authors:
Tim Rocktäschel
Edward Grefenstette
Karl Moritz Hermann
Tomáš Kočiskỳ
Phil Blunsom

title: Reasoning about entailment with neural attention

venue: arXiv preprint arXiv:1509.06664,

title: Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead

venue: Nature Machine Intelligence,

authors:
Victor Sanh
Lysandre Debut
Julien Chaumond
Thomas Wolf

title: DistilBERT, a distilled version of BERT: Smaller, faster, cheaper and lighter

authors:
Lesia Semenova
Cynthia Rudin
Ronald Parr

title: A study in rashomon curves and volumes: A new perspective on generalization and model simplicity in machine learning

authors:
Avanti Shrikumar
Peyton Greenside
Anshul Kundaje

title: Learning important features through propagating activation differences

venue: arXiv preprint arXiv:1704.02685,

authors:
Hendrik Strobelt
Sebastian Gehrmann
Hanspeter Pfister
Alexander M Rush

title: LSTMVis: A tool for visual analysis of hidden state dynamics in recurrent neural networks

venue: IEEE Transactions on Visualization and Computer Graphics,

authors:
Mukund Sundararajan
Ankur Taly
Qiqi Yan

title: Axiomatic attribution for deep networks

venue: arXiv preprint arXiv:1703.01365,

authors:
Michael Tsang
Youbang Sun
Dongxu Ren
Yan Liu

title: Can i trust you more? model-agnostic hierarchical explanations

venue: arXiv preprint arXiv:1812.04801,

authors:
Zizhao Zhang
Yuanpu Xie
Fuyong Xing
Mason McGough
Lin Yang

title: MDNet: A semantically and visually interpretable medical image diagnosis network

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

text:
1 INTRODUCTION
Recurrent neural networks (RNN) have been widely adopted in natural language processing. RNNs achieve the state-ofthe-art performance by utilizing the contextual information in a “memory” mechanism modeled via hidden/cell states. Albeit the benefit, however, the memory mechanism obstructs the interpretation of model decisions: as hidden states are carried over time, various pieces of information get intertwined across time steps, making RNN models a “black box” inherently.
The black box nature of RNNs has motivated a body of research works aiming to achieve the interpretability. One approach is to leverage certain architecture design in the DNNs such as Attention-based methods. As will be discussed in Section 2, the attention-based approaches (Karpathy et al., 2015; Strobelt et al., 2017; Choi et al., 2016; Guo et al., 2018) visualize the RNN using the attention mechanism, which weighs the importance of each hidden state element. However, while a few of them could be quite illuminative, the attention weights are, in fact, not always intelligible. Rather, they often turn out to be a gibberish collection of numbers that does not possess much sensical interpretations. In fact, recent research has been considering attention weights as not explanations (Jain & Wallace, 2019). Furthermore, the analysis of attention weights requires a certain level of understanding of how RNNs work in theory. Hence, a novice user may find it difficult to understand and, thus, the broader use in real-world applications might not be so feasible.
The other is prototype-based approaches (Ming et al., 2019), which use prototypes to explain the decision more intuitively. The process is analogous to how, for example, human doctors and judges make decisions on a new case by referring to similar previous cases: for a given sequence, a prototypebased approach looks up a few representative examples, or prototypes, from the data set and deduces a decision. From the interpretability standpoint, such prototypes then provide intuitive clues and evidences of how the model has reached a conclusion in a form that even a layperson can understand.
However, the existing prototype-based methods find the prototypes at the whole-paragraph level, making it difficult to break down the analysis at the individual sentence level, e.g., the connections and flows of individual sentences constituting a paragraph. Moreover, there may not be a suitable prototype when the length of a sequence is too large (e.g. a long paragraph), as longer sequences have greater degrees of freedom and, thus, harder to find a matching prototype, as evidenced later in Section 4.
Here, we advocate the idea that the sentence level prototyping (as opposed to the paragraph level prototyping in the previous literature) produce more desirable outcomes, namely better interpretability and higher prediction accuracy. We propose a novel architecture, called ProtoryNet, in which we introduce a new concept of the prototype trajectory. Given one or more paragraphs, ProtoryNet looks up the nearest prototype for each sentence and computes the proximity. The prototype proximity values are then fed into an RNN backbone, which then captures the latent patterns across sentences by means of the trajectory of prototypes. The prototype trajectory, therefore, illuminates the semantic structure of a text sequence and the logical flow therein, and, hence, provides highly intuitive, useful interpretation of how the model has predicted an output, as can be witnessed in Figure 1.
In fact, the prototype theory in modern linguistics supplies a strong justification for the proposed idea of prototype trajectory. In the prototype theory, linguists view “a sentence as the smallest linguistic unit that can be used to perform a complete action,” (Alston, 1964) and analyze texts with individual sentences as building blocks. Linguists assume that the sentences of a category are distributed along a continuum: at one extreme of this continuum are sentences having a maximal number of common properties; while on the other extreme are sentences that have only one or very few of such properties (Panther & Köpcke, 2008). Here, the “ideal” sentence that possesses the maximally shared common properties can be considered as a prototypical sentence, or a prototype of the category. Thus, in some sense, this paper takes a meaningful first step towards mathematically formalizing the prototype theory in modern linguistics and its analysis methods by incorporating the above view in a computational framework and emulating how linguists analyze a text.
As such, ProtoryNet permits a fine-grained understanding of sequence data alongside an intuitive explanation of the dynamics of the subsequences. In addition, since the technical details are hidden in the prototypes, a non-technical user can comprehend the interpretation. However, when necessary, technical users, i.e., the ones that are more knowledgeable about RNNs, can still look at the coefficients in RNN, similar to how the attention approaches visualize RNNs, as the proximity vectors feeding the RNN backbone are essentially one-hot encoded (i.e., zero everywhere except the k-th position for prototype k), making it convenient to trace how coefficients are related to each prototype.

heading: 2 RELATED WORK

text:
In addition to model-agnostic black-box explainers such as LIME (Ribeiro et al., 2016) and SHAP(Lundberg & Lee, 2017), various post hoc explanation methods have been proposed for DNN models, such as Integrated Gradients (Sundararajan et al., 2017), DeepLift (Shrikumar et al., 2017) and NeuroX (Dalvi et al., 2019). Specifically, to understand RNN models, Tsang et al. (2018) proposes a hierarchical explanations for neural networks to capture interactions and Jin et al. (2019) adapts the idea to text classification to quantify the importance of each word and phrase. For sentiment analysis, Murdoch et al. (2018) proposes contextual decomposition method for analyzing individual predictions made by standard LSTMs, and the method is able to reliably identify words and phrases of contrasting sentiment, and how they are combined to yield the LSTMs final prediction.
In addition to the external explanation methods, the prior efforts to bring interpretability to RNNs can be categorized as attention-based and prototype-based approaches. Bahdanau, Cho, and Bengio (Bahdanau et al., 2014) proposed an encoder-decoder type machine translation algorithm, in which they implemented an attention mechanism in the decoder. By the means of the alignment probabilities and the association energy, reflecting the importance of a given word in predicting a translated word, they let the attention mechanism to weigh which part of the source sentence the model needs to pay attention to. This not only improved the performance of the model by relieving the burden of the encoder having to compress all the information about the source sentence into a fixed-length vector, but also inherently visualized how the translation was conducted through the alignment matrix (e.g., Figure 3 of Bahdanau et al. (2014)). Similarly, Rocktäschel et al. (2015) analyzed word-to-word attention weights for achieving insights into how a long short term memory (LSTM) classifier reasons about entailment. Zhang et al. (2017) proposed a language model to read and explore discriminative
image feature descriptions from reports to learn a direct mapping between lexical components and image pixels via attention. Similar strategies can be found in a number of other works (e.g. Ismail et al. (2019); Choi et al. (2016)) that employ the idea of the attention mechanism. However, the attention-based approaches are mostly intended for expert users. Many non-technical users in the real world, who lack basic knowledge of how RNNs work (or even neural networks in general), may find them difficult to understand.
Instead, prototype-based approaches argue that the intuitiveness of interpretation can be significantly enhanced by visualizing the reasoning process in terms of prototypes. In fact, prototype-based reasoning has a long history as a fundamental interpretability mechanism in traditional models (Cupello & Mishelevich, 1988; Fikes & Kehler, 1985; Kim et al., 2014). More recently, the idea of prototype-based interpretation attracted several authors in neural network research. For instance, Chen et al. (2019) incorporated the concept of prototypes to convolutional neural networks. A prototype layer was added after convolutional layers to compare the convolution responses at different locations with prototypes. From this, users can understand, for example, a bird is classified as a ‘red-bellied woodpecker’ because it has the typical prominent red tint at the belly and the top of its head as well as the black and white stripes on its wings.
More closely related to the present work, ProSeNet (Ming et al., 2019) added a prototype layer in RNN. ProSeNet computed the similarities between an input sequence (usually a short prose) and prototypes and produced the final prediction as a linear combination of the similarities. Despite the built-in interpretability of ProSeNet, however, an issue might arise when the sequence was too long. The original paper (Ming et al., 2019) validates ProSeNet only on paragraphs shorter than 25 words. However, it is easily fathomable that ProSeNet may fail to assimilate a long paragraph data, due to large degrees of freedom that complicate matching of a prototypical example. This may render some practical concerns. For instance, in sentiment classification, even if a paragraph is classified as “negative,” it could consist of several twists of sentiments along sentences (e.g., sarcastic use of positive proses). With an increased length, such kinds of twists can get harder to be represented with a prototype, thus making the interpretation difficult and the explanation less credible. This claim is further supported by findings in modern linguistics, which suggests that sentences, instead of paragraphs, should be regarded as the basic elements for text analysis (Panther & Köpcke, 2008).
Nonetheless, we share our view with ProSeNet in that the prototype based method is worth paying attention to. The benefit of prototype-based reasoning resides in the fact that it hides technical details by encapsulating them with prototypical examples while being still tractable numerically when desired. Hence, novice users can understand how the reasoning was achieved in RNNs so long as they can comprehend the prototypes, lowering the barrier for those numerous non-technical users who may use RNN-based applications in the real world. On the other hand, numerical weights assigned to prototypes alongside their association with the “nuts and bolts” of RNNs still allow experts to perform in-depth analyses of how a model has drawn a prediction.

heading: 3 METHOD

heading: 3.1 THE PROTORYNET ARCHITECTURE

text:
Suppose a data set D = { (X(i), y(i)) : i = 1, . . . , N } of size N , comprised of text sequences X(i)
and the corresponding labels y(i). Here, note that the superscript (i) may be dropped for notational convenience hereinafter, unless necessary. Each instance X can be understood as a sequence of sentences xt ∈ RV at t-th position, yielding the representation X = (xt)Tt=1, where V is the size of vocabulary and T := |X| is the number of sentences in the sequence X. y ∈ RC is a multi-hot encoded vector representing the class labels associated with the sequence X, i.e., the c-th element yc of y equals 1 if the label c is associated with X or 0 otherwise. C is the total number of classes.
ProtoryNet interfaces with text data via a sentence encoder (Figure 2a) modeled as a mapping r : RV → RJ , where J is the dimension of sentence encoding specified by the user. That is, the encoder takes each sentence xt ∈ X and produces a sentence embedding et = r(xt). In this paper, the development of the encoder r is beyond the scope of this paper and, hence, we employ a pre-trained BERT-based sentence encoder with mean-tokens pooling (Reimers & Gurevych, 2019), where J = 768 by default.
The sentence embeddings et are fed into the prototype layer (Figure 2b), in which a set of trainable prototypes P = { pk ∈ RJ : k = 1, . . . ,K } are compared with et, where K := |P| is the number of prototypes specified by the user. Then, given a distance metric d : RJ → R+, the proximity st,k of the sentence embedding et to a given prototype pk is measured as st,k := s(et,pk) = exp ( −d(et,pk)ψ2 ) , where ψ ∈ R is a user-specified constant. Between two popular choices for the distance metric d, namely the cosine distance and the Euclidean distance, we find that there is no significant difference between the two. Hence, we use the Euclidean distance in our experiments for convenience.
Note here that the intermediate throughput of the prototype layer is the similarity matrix S̃ = [st,k] of the size T ×K, associating the t-th sentence with the k-th prototype. The rows of the similarity matrix S̃ then constitute the input to the LSTM backbone at time step t (Figure 2c), which then finally produces an output prediction. Here, the sparsity transformation is performed on the similarity matrix S̃ before feeding it into the LSTM backbone by setting each row to zero except for the position where st,k is the maximum. That is, each row of the transformed similarity matrix S would be of the same topology as the one-hot encoded vector, whose elements equal st,k∗ at k∗ := argmaxk st,k and 0 otherwise. The sparsity transformation of S̃ to S enhances the interpretability of the architecture, by enforcing each sentence be matched with no more than a single prototype and, thus, disentangling the information. This is accomplished only at a small cost of accuracy, as observed from an ablation study in Appendix. Motivating Example The text data in Figure 2 exemplifies the use of ProtoryNet for sentiment analysis (text classification). In this example, the task is to predict whether the review of a restaurant is positive or not. The input text data X is comprised of T = 4 sentences, in this particular case, and the label y is the binary sentiment label of the review, either “positive” ([1, 0]) or “negative” ([0, 1]). To this, ProtoryNet converts the text data into sentence embeddings, each of which are then matched with the closest prototype. Observe, in the figure, that the prototypes that ProtoryNet produced are, indeed, morphosyntactically equivalent to the corresponding input sentences, well-exemplifying them semantically. The one-hot-like similarity vectors between the sentences and the prototypes are then fed into the LSTM backbone, which captures the patterns and trends in the trajectory of prototypes and, finally, predicts the final sentiment label, which, in this case, is “negative.” 3.2 OBJECTIVE FUNCTIONS
The training objectives of ProtoryNet entail four different terms aiming to achieve both the prediction accuracy and the interpretability. Below are the details of their definitions.
Accuracy The accuracy loss is defined as the square loss between the predicted value and the ground truth label, promoting the model to make accurate predictions:
Lacc(D) := 1
N N∑ i=1 ∥∥∥y(i) − ŷ(i)∥∥∥2. (1)
Diversity To ensure diverse and non-overlapping prototypes, we define the diversity loss term added to enforce the minimum mutual distance δ among the prototypes:
dmin := min k1,k2 d(pk1 ,pk2), (2)
Ldiv(D) := σ (η(δ − dmin)) , (3) where σ(·) is the sigmoid function and η is a smoothing constant, which we set η = 1 empirically. The constant δ ∈ R+∗ is a positive real number defined by the user, to enforce the minimum separation among prototypes. Hence, when the distances among the prototypes do not meet the minimum separation requirement i.e., dmin < δ, the η(δ − dmin) term will have some positive value, making the diversity loss term Ldiv active; on the other hand, when the minimum separation requirement is met and thus, dmin > δ, then the sigmoid function will pull the loss term to zero. Note that a smaller η will make such a transition by the sigmoid function smoother.
Prototypicality The accuracy and the diversity terms alone, it is observable a prominent tendency of prototypes diverging away from the sentences during training. Such a behavior introduces overfitting, in which prototypes become less generalizable, as the prototypes lose their representativity of a category. Hence, we introduce the prototypicality loss, which promotes each sentence in the database to have a representative prototype close to it:
Lproto = 1
S ∑ X∈D ∑ xt∈X min k d(r(xt),pk), (4)
where S is the total number of sentences in the data set.
Final loss The final loss function combines the above loss terms:
L = Lacc + αLdiv + βLproto (5)
Empirically, coefficients values of α = 0.1 and β = 1e−4 are used in this paper.
Remarks on Prototype Interpretability The diversity and prototypicality terms are designed for improving the interpretability. Here, to achieve good explanations, prototypes need to be different from each other to avoid redundancy, thus the diversity term. In addition, each input sentence needs to be mapped to a prototype that is similar enough to make the explanation convincing, thus the prototypicality term. These two loss terms can be considered regularization terms to serve interpretability purposes. Similar loss terms have been introduced in other prototype based DNN models (Ming et al., 2019; Chen et al., 2019). We will later show in experiments that these two terms do not hurt the predictive performance. This can be explained by the recent research on Rashomon Set (Semenova et al., 2019; Rudin, 2019), that there exist many models with very similar performance, so one can add customized constraints to the model to achieve additional benefits, such as interpretability.

heading: 3.3 TRAINING

text:
For the training of ProtoryNet, the adaptive moment estimation (ADAM) optimizer (Kingma & Ba, 2014) was employed. The learning rate was set to be 1e−4 and the exponential decay rates for the first and the second moment estimates were 0.9 and 0.999, respectively. Below are further details used for generating the results in this paper.
Differentiability Training of ProtoryNet requires the computation of the index where the similarity matrix S̃ is maximum for the sparsity transformation in the prototype layer. This operation, unfortunately, is not differentiable and may lead to an unexpected training behavior during autodifferentiation in deep learning packages. We get around this issue by the following approximation technique. Suppose the similarity matrix S̃ = [s̃1, . . . , s̃T ] where s̃t ∈ RK is a column vector whose elements indicate how similar the t-th sentence is to each of the prototypes. If we let Softmax(·) to denote the softmax function, then for some large constant γ,
Γ = [Softmax(γ · s1), ...,Softmax(γ · sT )] (6) approximates the selection matrix whose element equals to 1 at the position corresponding to where st is the maximum for each column t and 0 elsewhere. Here, we find γ ≥ 1e6 gives a reasonable
approximation empirically. With the selection matrix, the sparsity transformation can be approximated as follows without explicitly computing the maximum:
S ≈ Γ S̃ (7) where is the Hadamard product. Note that the softmax function is differentiable and, thus, is S.
Prototype Initialization The training of ProtoryNet can benefit from the initialization method described below. We first embed all sentences separately in the training data set. Then, in the embedding space, all sentences in the data set are clustered using the k-medoids clustering algorithm to categorize sentences by their semantic meaning. The medoids obtained from the k-medoids algorithm can be considered as the representative examples of each cluster and, hence, plausible candidates for prototypes. Thus, for the training of ProtoryNet, we use these medoids to initialize prototypes, which in turn accelerates the convergence.
Prototype Projection It should be noted that the numerical solutions for the prototypes are found in the embedding space. These numerical solutions are not automatically intelligible to human users and need to be deciphered. To this end, we project the prototypes to the closest sentence in the embedding space every 10 epochs during the training process, similar to the technique proposed in Ming et al. (2019); Chen et al. (2019):
pk = argmin xt∈X(i),∀X(i)∈D
d(r(xt),pk), k ∈ [1,K] (8)
Sentiment Scores for Prototypes Once the training is done, ProtoryNet returns a set of K prototypes. We then feed them back into the trained ProtoryNet one at a time, to evaluate the sentiment score of each individual prototype. These sentiment scores will later be used to provide quantitative visualizations of how the tones and sentiments change within a text data.

heading: 4 EXPERIMENTS

text: In this section, we evaluate our model on five different data sets. A vanilla LSTM method, a stateof-the-art black-box model (DistilBERT Sanh et al. (2019)), and a state-of-the-art prototype-based interpretable model (ProSeNet Ming et al. (2019)) are compared against our method.We also compare with a classic non-neural baseline bag-of-words, which provide explanations at word level.

heading: 4.1 PREDICTION ACCURACY

text:
Reported in Table 1 are the means and the standard deviations of accuracy evaluated from 5-fold cross validations. It is clear that the state-of-the-art black box model (DistilBERT) outperforms the interpretable models (ProSeNet and ProtoryNet) in all data sets used. Note, however, that DistilBERT was pre-trained on a massive corpus of text data before being transferred to each specific data set. Hence, the performance metrics of DistilBERT should only be used for sanity check. Compared against the vanilla LSTM, the prediction performance of the interpretable models were on par. ProtoryNet is slightly better than Bag-of-words on average.
Between ProSeNet and ProtoryNet, ProtoryNet outperformed ProSeNet for all five cases overall. In particular, the performance difference was clearer when long text data were analyzed. In Table 2, we split each data set into short and long samples—paragraphs that were less than 25 words were classified as short samples, following the criterion used in the ProSeNet paper Ming et al. (2019). As
shown in the table, ProSeNet and ProtoryNet were on par when short proses were analyzed, while ProtoryNet was always better than ProSeNet when long paragraphs were concerned. In fact, this can be a substantial advantage of ProtoryNet as instances with less than 25 words are quite rare in real-world data sets. Note, in Table 2, more than 90% of instances are more than 25 words, with an exception of the Rotten Tomatoes data set.
In addition, we investigated how the number of prototypes, K, influences the performance of ProtoryNet. In Figure 3, the performance of ProtoryNet on the Amazon Review data set is plotted with respect to different values of K. Other hyperparameters were controlled to be the same and the performance measures (accuracy) were averaged over 5-fold cross validation experiments (the whiskers in the figure represent the standard deviation). Compared to the ProSeNet baseline, ProtoryNet
reaches high accuracy much quicker with only a few prototypes and shows a steady increase of performance afterwards. The same analyses on the other data sets are available in Appendix.
Furthermore, we conducted an ablation study on the sparsity transformation. We measured the change in prediction accuracy when the sparsity transformation step had been removed and the dense similarity matrix S̃ had been used directly. The result revealed that there was only a small drop of accuracy (approx. 1%) caused by the sparsity transformation, while the benefit of interpretability was huge (see Appendix for the detail).

heading: 4.2 PROTOTYPE TRAJECTORIES

text:
Prototypes and their trajectory play a critical role in ProtoryNet. Here, we show four examples of prototype trajectories in Figure 4, two for positive sentiment data and two for negative ones curated from the Yelp Review data. Observe that the trajectories can be drastically different even for the
same sentiment class. For example, review (c) starts off with a negative sentence and changes the tone in the middle to positive and then ends with a negative sentence while (d) maintains the negative tone from the beginning to the end. As such, interpretation of ProtoryNet can be more fine-grained, generating a deeper insights to users.

heading: 4.3 THE EFFECT OF DIVERSITY AND PROTOPYPICALITY TERMS

text:
The diversity and prototypicality terms are designed to improve interpretability since it forces each sentence to be mapped to a prototype that is close enough to it and prototypes to be sufficiently different from each other. Therefore, in this section, we examine whether the two terms serve such purposes, and meanwhile, whether these two terms hurt the predictive performance.
Effect on Interpretability We plot two types of distances for hotel dataset. First, since the explanations are based on prototypes, we need the prototypes to be similar enough to the input sentences mapped to them in order to make the explanation convincing. Thus we compute the Euclidean distances between each sentence and the prototypes they are mapped to. Second, we want prototypes to be at
least dmin (in this experiment we choose dmin = 8) away from each other, since if prototypes are too similar, then similar sentences may be mapped to different prototypes, causing confusion to users. Therefore, we compute the Euclidean distances between each pair of prototypes. Figure 5 shows, when setting α, β non-zero, the distances between sentences and their prototypes are closer and prototypes are sufficiently away from each other, compared to when α, β = 0, proving the effect of the diversity and prototypicality terms on interpretability.
Effect on Accuracy We performed a sensitivity analysis to understand the effect of the two terms on predictive performance. We trained ProtoryNet on the Amazon dataset with different combinations of α = 0, 1e−3, 1e−2, 1e−1, 1, and β = 0, 1e−5, 1e−4, 1e−3, 1e−2. As seen in Figure 6, our experiment revealed that the performance of ProtoryNet is not so sensitive to the selection of the parameters α and β. Between α and β, ProtoryNet was more sensitive to β, which may reveal the trade-off between the different loss terms. The results also illustrate how different loss terms impact the overall performance - when α = 0 or β = 0. The best performance was achieved when α and β are
set to small values instead of 0. A possible explanation would be that, having some constraints on the prototypes’ diversity (Ldiv) and their representativeness (Lproto) prevents overfitting as these terms “regulate” prototypes. Sensitivity analysis for other datasets are included in the Appendix.

heading: 4.4 USER EVALUATION

text:
The interpretability of ProtoryNet was further validated via a survey conducted on 111 individuals, among which 42 identified themselves as non-technical users. Subjects were recruited through two different channels. Individuals from the authors’ home institution holding a master’s degree or above having advanced knowledge of RNNs have been recruited as technical users. Non-technical users were recruited from Amazon Mechanical Turk. The summary statistics of the subjects as well as the survey design are disclosed in Appendix.
We first evaluated the interpretability of the explanation by testing whether the model-selected prototypes were indeed representative of the input text to the human users. We asked the users to choose the most appropriate prototype for a given sentence out of four options presented to them, one of which was the actual prototype matched by the model, other two were randomly selected from the rest of the prototypes, and the other was “None of the above.” We created 10 such questions by sampling reviews from the Yelp Review data set, each for ProtoryNet and ProSeNet. As reported in
Figure 7a, ProtoryNet showed a more significant agreement between the model-selected prototype and the prototype that the human users found the most appropriate. For both technical users and non-technical users, ProtoryNet was significantly better than ProSeNet, as was validated by the t-test. The difference between technical users and non-technical users was insignificant, suggesting that non-technical users can comprehend prototypes equally well as technical users.
The survey also included self-report questions to assess how easy it was for them to select a prototype in a score ranging between 1 (very difficult) and 5 (very easy). As reported in Figure 7b, subjects found that ProtoryNet was easier to interpret in general, and the improvement in interpretaiblity was more significant for technical users. Again, the difference between technical users and non-technical users was insignificant.
Finally, we measured how easily the users can learn to interpret the results of ProtoryNet. For this, each subject was randomly assigned to either ProtoryNet or ProSeNet and trained on how the model that they are assigned to makes predictions. Then, their proficiency was measured by showing them three examples on which the model had made an incorrect prediction and asking them to diagnose the problem by pointing out an inappropriately matched prototype. The problematic prototype (i.e., the “correct answer” for the survey question) was determined via a discussion among the authors, which later turned out to be aligned with the consensus in the survey responses as well. As in Figure 7c, the both subject groups were more accurate at diagnosing ProtoryNet in general. An explanation to this should be that ProtoryNet uses shorter prototypes than ProSeNet and, thus, is easier to comprehend. We notice that the while technical users find ProtoryNet easier to debug, such difference was not significant for non-technical users. In fact, there was no significant difference between technical users and non-technical users when they use ProSeNet since it was almost equally difficult to these two groups of users.

heading: 5 CONCLUSION

text:
In this paper, we introduced a novel idea of prototype trajectory in RNNs. Our model, ProtoryNet, utilizes the prototype trajectories to map a text data into a sequence of prototypical sentences, illuminating the underlying dynamics of semantics within the text data. We showed that ProtoryNet could achieve a predictive performance higher than the current state-of-the-art. In addition, sentence level prototype trajectory allowed fine-grained analysis of paragraphs. Moreover, the survey result suggested that ProtoryNet provided more intuitive prototypes than the state-of-the-art method and that the novice users were able to interpret ProtoryNet equally well as the expert users.
Our immediate future work would be to apply ProtoryNet to other types of sequence data, such as medical data, longitudinal data, etc. In a more theoretical context, it would be interesting to mathematically formalize some of the well-established requirements to be a prototype in the linguistics literature. For example, Panther and Köpcke (Panther & Köpcke, 2008) assert several conditions that a prototype must possess—a prototypical sentence is an affirmative declarative sentence; the subject is in the nominative case; the verb in a prototype is in the active voice and in the indicative mood; to list a few. Albeit non-trivial, the mathematical translation of such conditions should bring more interpretability and, perhaps, a better performance of ProtoryNet.

heading: 6 APPENDIX

heading: 6.1 REPRODUCIBILITY

heading: 6.1.1 DATA SETS

text:
IMDB Movie Reviews The IMDB Movie Reivews data set is a standard benchmark data set for binary sentiment classification and is available at https://ai.stanford.edu/˜amaas/ data/sentiment/. The data set is comprised of 25,000 movie reviews, divided equally into 12,500 positive and 12,500 negative reviews. The total of 332,541 sentences are found in the data set. All of those reviews samples were included in our experiments.
Amazon Product Reviews The Amazon Product Review data set is publicly available on Kaggle: https://www.kaggle.com/bittlingmayer/amazonreviews. In our experiment, we took random samples of a similar size to the IMDB data set—30,001 reviews were randomly selected from the original Amazon data set, among which 15,429 were positive and 14,572 were negative. The total of 192,709 sentences were found.
Yelp Reviews The Yelp Reviews data set was obtained from http://goo.gl/JyCnZq. The data set is comprised of 555,000 Yelp review samples and their corresponding labels. The authors of the data set has binarized the sentiment scores by assuming 1 and 2 stars as a negative sentiment and 3 and 4 stars as a positive sentiment. The total of 30,000 review samples were extracted via random sampling, in which the number of positive reviews were 14,389 and the number of negative reviews were 15,611.
Rotten Tomatoes The Rotten Tomatoes Movie Review data set is a corpus of movie reviews used for sentiment analysis and is available at https://github.com/nicolas-gervais/ rotten-tomatoes-dataset. The total of 30,000 reviews were randomly selected, in which the proportion between the positive reviews and the negative reviews was exactly 1:1.
Hotel Reviews The Hotel Reviews data set is comprised of 20,000 review samples evaluating 1,000 hotels and is available on Kaggle: https://www.kaggle.com/datafiniti/ hotel-reviews. In this paper, we assumed a positive sentiment for reviews of 4 and 5 star ratings and a negative sentiment for reviews of 1 and 2 stars. Reviews with 3 stars were ignored. This assignment yields 17,746 positive reviews and 2,254 negative ones. To balance out the data set, we randomly picked 2,254 positive reviews to make them equal, making the total of 4,508 reviews used in our experiments.

heading: 6.1.2 MODELS

text:
Vanilla LSTM We used 300-dimensional GloVe word embeddings Pennington et al. (2014) to encode words in sentences. An LSTM model with 2 hidden layers of size 128 each was used. The final prediction was made by a fully connected layer of size 256. A dropout layer of the rate 0.5 was used immediately before the fully connected layer.
DistilBERT DistilBERT Sanh et al. (2019) is considered as a light-weight version of the state-ofthe-art BERT model with smaller, faster, and less expensive deployment time and resources. In our experiments, a pre-trained DistilBERT model was transferred to each target data set.
ProSeNet ProSeNet Ming et al. (2019) is a state-of-the-art prototype-based interpretable RNN. For the implementation of ProSeNet, we used an LSTM layer with 2 hidden layers of size 128 and the dropout rate 0.5 for the sequence encoder. This is the same configuration as the ProtoryNet’s RNN layer. We fixed K = 200 for all experiments for both ProSeNet and ProtoryNet, with an exception of Figure 3.
For fair comparison, we used the fixed constant K = 200 for both ProtoryNet and ProSeNet. In addition, the LSTM layer in ProtoryNet was implemented to have the same architecture as the baseline methods to eliminate the bias.
We used TensorFlow v1.151 to implement ProtoryNet and the other benchmark models including standard LSTM and ProSeNet. For DistilBERT, we used an implementation that was available in the Hugging Face Transformers Library (https://github.com/huggingface/transformers), which was implemented in PyTorch and TensorFlow 2.0.
For pre-processing, the period (‘.’), the question mark (‘?’), and the exclamation mark (‘!’) were used as delimiters to define the boundary between sentences. All words were then converted to the lowercase and punctuations were removed using the definition in string.punctuation constant in Python 3.5. In all experiments, we used pre-trained BERT-based language model with mean-tokens pooling Reimers & Gurevych (2019) to convert the raw sentence data to sentence embeddings.

heading: 6.2 ABLATION STUDY

heading: 6.2.1 SPARSITY TRANSFORMATION

text:
In this paper, the sparsity transformation from S̃ to S was used to enhance the interpretability of the model. However, the effect of the sparsity transformation on the model performance has not been investigated in the main text. Hence, we compare ProtoryNet’s performance with and without the sparsity transformation.
As reported in Table 3, ProtoryNet without the sparsity transformation exhibits a better performance than when the sparsity transformation was used. Although the margin was narrow, such a trend was statistically significant. This should be an inevitable cost paid in exchange of the enhanced interpretability. A future investigation may include representing a sentence with more than a single prototype, to balance between the interpretability and the increased accuracy.
1https://www.tensorflow.org/

heading: 6.2.2 DISTANCE METRICS

text: One of the design decisions we made for ProtoryNet architecture was between the cosine distance and the Euclidean distance metrics. However,as reported in Table 4, a comparative study revealed that there was no significant difference in performance.

heading: 6.2.3 INFLUENCE OF THE NUMBER OF PROTOTYPES ON ACCURACY

text: Here, we provide additional results to show how the number of prototypes K impacts the model performance.

heading: 6.3 SENSITIVITY ANALYSIS

text: We provide sensitivity analysis on all datasets except the one in the main paper. The sensitivity analysis studies how the predictive performance varies with different values of α and β

heading: 6.3.1 LIST OF PROTOTYPES IN SECTION 4.2

text: Figure 10 shows the prototypes and their sentiment scores used in the main text Section 4.2 and the main text Figure 4. Note that several sentences could be mapped to one prototype.

heading: 6.3.2 SURVEY QUESTIONS

text:
Figures below show a few examples of the survey questions we used for the user evaluation study.
For the prototype selection, we created 10 questions each, for ProSeNet and ProtoryNet. Here we only show one example in Figure 11.
Figure 12 and Figure 13 show how we educated the subjects about how ProtoryNet or ProSeNet work.
For diagnosing the ProSeNet and ProtoryNet, we create 3 questions for each model. We show one example for each model in Figure 14 and Figure 15.

title: INTERPRETABLE SEQUENCE CLASSIFICATION VIA PROTOTYPE TRAJECTORY