T_kML-AP: Adversarial Attacks to Top-$k$ Multi-Label Learning

Let us assume a general multi-label classification problem with a total of $m>1$ possible labels. For an input $\mathbf{x}\in\mathbb{R}^{d}$, its true labels are represented by a binary label vector $\mathbf{y}=[y_{1},y_{2},\cdots,y_{m}]^{\top}\in\{0,1\}^{m}$, with $y_{j}=1$ indicating that $\mathbf{x}$ is associated with the $j$-th label. We also use $Y=\{j|y_{j}=1\}$ to represent the set of true labels of $\mathbf{x}$. Note that $Y$ and $\mathbf{y}$ are equivalent notations of the truth labels of $\mathbf{x}$.

We introduce a continuous multi-label prediction function $F(\mathbf{x})=[f_{1}(\mathbf{x}),f_{2}(\mathbf{x}),\cdots,f_{m}(\mathbf{x})]^{\top}$, with each $f_{j}(\mathbf{x})\in[0,1]$ corresponding to the prediction score of $\mathbf{x}$ with regards to the $j$-th class¹¹1Here we assume the prediction scores are calibrated, i.e., taking values in the range of $[0,1]$. For $f\in\mathbb{R}$, we can use simple transforms such as ${1\over 1+e^{-f}}$ to map it to the range of $[0,1]$ without changing their ranking.. We denote $[f_{[1]}(\mathbf{x}),f_{[2]}(\mathbf{x}),\cdots,f_{[m]}(\mathbf{x})]^{\top}$ as the sorted values of $F(\mathbf{x})$ in descending order, i.e., $f_{[1]}(\mathbf{x})$ is the largest (top-$1$) score, $f_{[2]}(\mathbf{x})$ is the second largest (top-$2$) score, and so on. Furthermore, $[j]$ corresponds to the label index of the top-$j$ prediction score, i.e., $j^{\prime}=[j]$ if $f_{j^{\prime}}(\mathbf{x})=f_{[j]}(\mathbf{x})$. In ranking the values, ties can be broken in any consistent way. For input $\mathbf{x}$, the top-$k$ multi-label classifier returns the set $\hat{Y}_{k}(\mathbf{x})=\{[1],\cdots,[k]\}$ for $1\leq k<m$. In other words, we can convert a general multi-label predictor $F$ to a top-$k$ multi-label classifier by returning the set of labels corresponding to the set of top-$k$ prediction scores from $F(\mathbf{x})$. This problem is related to many types of learning problems. If $|Y|=1$, $k=1$, it becomes the conventional multi-class problem. If $|Y|=1$, $k\geq 1$, it becomes top-k multi-class problem [10]. If $k=|Y|$, $|Y|\geq 1$, it becomes the conventional multi-label problem. The top-$k$ setting is often implicitly used in applications of multi-label learning. For instance, in image annotation, when the number of possible labels is large, the system often returns a fixed number of top annotations that are most relevant to the image²²2Another strategy in multi-label learning is to return all labels with prediction score above a preset threshold. The result will be a list of labels of varying length. The top-$k$ multi-label classification can be regarded as using a varying threshold to fix the number of the returned labels..

A successful top-$k$ multi-label classification should lead to consistency between the true labels ($Y$) and the predicted labels $\hat{Y}_{k}(\mathbf{x})$ of the input. The situation is complicated by the difference in size of $Y$ and $\hat{Y}_{k}(\mathbf{x})$, so we use the following criterion: when $k\geq|Y|$, it corresponds to $Y\subseteq\hat{Y}_{k}(\mathbf{x})$; when $k\leq|Y|$, it is the case $\hat{Y}_{k}(\mathbf{x})\subseteq Y$. In other words, one is the subset of the other depending on the relation of $k$ and the number of the truth labels. We define the top-$k$ label consistency score as:

where $\mathbb{I}_{c}$ is the indicator function that takes value $1$ when condition $c$ is true and $0$ otherwise. As such, $E(Y,\hat{Y}_{k}(\mathbf{x}))$ is $1$ for a successful multi-label classification of input $\mathbf{x}$ and $0$ otherwise.

Top-$k$ ranking emerges as a natural element in the learning objectives in various problems such as multi-class learning and robust binary classification [10, 13, 8]. However, as a function of all elements in a set, the top-$k$ ranking function is non-continuous, non-differentiable, and non-convex. This makes the optimization involving top-$k$ ranking challenging.

To mitigate these problems of the top-$k$ operator, we can use the average of top-$k$ function [5], which is defined for a set $F=\{f_{1},\cdots,f_{m}\}$ as

It is not difficult to show that (i) $\phi_{k}(F)\geq f_{[k]}$, and (ii) $\phi_{k}(F)=f_{[k]}$ when $f_{[1]}=\cdots=f_{[k]}$. As such, the average of top-$k$ is a tight upper-bound of the top-$k$. It can be proved that $\phi_{k}(F)$ is a convex function of the elements of $F$ [2]. More importantly, it affords an equivalent form as an optimization problem [18].

For completeness, we include the proof of Lemma 1 in Appendix A.1. Lemma 1 enables us to incorporate the average top-$k$ function in conventional sub-gradient based optimization.

Due to the limit of space, we only provide a brief overview of relevant works. A full survey of adversarial attacks on deep learning models can be found in [1]. The major differences between the work in this paper and the related works are summarized in Table 1.

Most existing adversarial attacking methods target multi-class classification problems (corresponding to the special case of T_kML with $k=1$ and $|Y|=1$ for all inputs). As such, these methods often target the top prediction and aim to change it with perturbations. For untargeted attacks, DeepFool [17] is a generalization of the minimum attack under general decision boundaries by swapping labels from the top-$2$ prediction. The work of [16] (UAP) aims to find universal adversarial perturbations that are independent of individual input images. Both DeepFool and UAPs are top-1 multi-class adversarial attack methods. For targeted attacks, FGSM [6] and I-FGSM [9] are two popular attack schemes that use the gradient of the DNN models with regards to the input to generate adversarial samples. The CW method [3] improves on the previous method by using regularization and modified constraints.

Realizing that only attacking the top predictions may not be effective, several works introduce attacks to the top-$k$ (for $k>1$) predictions in a multi-class classification system. $k$Fool [25] and CW^k [26] extend the original DeepFool [17] and CW [3] methods to exclude the truth label out of the top-$k$ predictions. $k$Fool is based on a geometry view of the decision boundary between $k$ labels and the truth label in the multi-class problem. The UAP method is extended in [25] to top-$k$ Universal Adversarial Perturbations ($k$UAPs). In addition, the CW method is extended to a top-$k$ version known as CW^k in [26]. However, all these methods are still designed for multi-class classification (i.e.$|Y|=1$), and cannot be directly adapted to the attacks to the more general top-$k$ multi-label learning.

The authors of [22] describes an adversarial attack to multi-label classification extending existing attacks to multi-class classification. This method is further studied in [27], which transfers the problem of generating attack to a linear programming problem. To make the predictions of adversarial examples lying inside of the training data distribution, [15] proposed a multi-label attack procedure with an additional domain knowledge-constrained classifier. These are all for multi-label learning without the top-$k$ constraint. Our experiments in Section 4 show that they are not effective for the top-$k$ setting.

As shown in Section 2.2, we have the following bound of the top-$k$ value using the average of $\{t_{1},\cdots,t_{m}\}$, as ${1\over m-k}\sum_{j=1}^{m-k}t_{[j]}\geq t_{[m-k]}=[\max_{y\in Y}f_{y}(\mathbf{x}+\mathbf{z})-f_{[k+1]}(\mathbf{x}+\mathbf{z})]_{+}$. Furthermore, using Lemma 1, we can rewrite the average of top-$(m-k)$ elements of $\{t_{1},\cdots,t_{m}\}$ as ${1\over m-k}\sum_{j=1}^{m-k}t_{[j]}=\min_{\lambda\in[0,1]}\lambda+{1\over m-k}\sum_{j=1}^{m}[t_{j}-\lambda]_{+}$. Replacing the definition of $t_{j}$, the inner term $[[\max_{y\in Y}f_{y}(\mathbf{x}+\mathbf{z})-f_{[m+1-j]}(\mathbf{x}+\mathbf{z})]_{+}-\lambda]_{+}$ can be further simplified by removing the double hinge function to $[\max_{y\in Y}f_{y}(\mathbf{x}+\mathbf{z})-f_{[j]}(\mathbf{x}+\mathbf{z})-\lambda]_{+}$, according to the following result.

The proof of Lemma 2 is deferred to Appendix A.2. Putting all results together, we get the objective function for finding adversarial perturbation in an untargeted attack to the top-$k$ multi-label learning as:

This optimization problem can be solved with an iterative gradient descent approach [8, 5]. We initialize $\mathbf{z}$ and $\lambda$, then update them with the following steps:

where $\eta_{l}$ is the step size and $y^{\prime}\in\max_{y\in Y}$. This iterative process continues until the termination conditions are met. The overall procedure is described in detail in Algorithm 1.

On the two datasets, we train deep neural network-based top-$k$ multi-label classifiers as baseline models. For the PASCAL VOC 2012 dataset, similar to [22], we adopt the inception-v3 [23] model pre-trained on ImageNet [21] and fine-tuned on PASCAL VOC 2012. For MS COCO 2014 datasets, we use a ResNet50 [7] based model. Both models are originally designed for multi-class classification, so we convert them to multi-label models by replacing the softmax layer with sigmoid classification layer as in [20]⁶⁶6After retraining the models, we get 0.934 mAP performance for PASCAL VOC 2012 and 0.867 mAP performance for MS COCO 2014 on the corresponding validation datasets, which are close to the state-of-the-art performance [22, 20].. We further modify the model to output the top-$k$ predicted labels.

We select 1,000 images from the validation set in PASCAL VOC 2012 and MS COCO 2014 datasets respectively as the test set to test the untargeted and targeted attack methods. These images are correctly predicted by the baseline T_kML models, i.e., the predicted top-$k$ labels either contain or are completely from the true labels. For the universal untargeted attack, however, we need a training dataset to find the universal perturbation. Therefore, we select 3,000 images from the validation set of MS COCO 2014 as the training set and evaluate the attack performance on another different 1,000 images from the same validation set. For the targeted attacks, we choose the target labels as in [3, 26], where we consider three different strategies (see Fig.4 for more details).

• •

  Best Case. In this case, we select $k$ labels that are not true labels and have the highest prediction scores. These labels are the runner-ups and the regarded as the easiest labels to attack.

• •

  Random Case. In this case, we randomly select $k$ labels that are not true labels following a uniform distribution.

• •

  Worst Case. In this case, we select $k$ labels that are not true labels with the lowest prediction scores. These labels are the most difficult to attack.

The performance of untargeted attacks is shown in Table 2. Note that for different $k$ values, the T_kML-AP-U method achieves a nearly complete obviation (with very high ASR values) on both the PASCAL VOC 2012 dataset and the MS COCO 2014 dataset with small perturbation scales (indicated by the smaller Pert values). On the other hand, the simple adoption of the DeepFool method ($k$Fool) is much less effective. This could be attributed to the explicit consideration of the top-$k$ prediction in T_kML-AP-U. The quantitative results are corroborated with an example from the PASCAL VOC 2012 shown in Fig.2. Although both $k$Fool and T_kML-AP-U show effectiveness in attacking the top-$k$ predictions from the baseline method, $k$Fool introduces larger perturbations in general. In many cases, the perturbations are visible as shown in Fig.2.

When deployed in practice, it is possible that the attack is designed for top-$k$ predictions but the actual system is used to find the top-$k^{\prime}$ outputs. In other words, there can be a mismatch between the cutoff rank that is used in the attack $k$ from that used in the system $k^{\prime}$. Note that by the definition of T_kML-AP-U, a successful attack to a top-$k$ multi-label learning system is necessarily a successful attack to the same system for the case of top-$k^{\prime}$ for $k^{\prime}\leq k$. This is because the top $k^{\prime}$ set is a subset of the top $k$ set. On the other hand, we perform a set of experiments to validate the case when $k^{\prime}>k$. Specifically, in Table 3, we show the results of running T_kML-AP-U for $k=3$ and $k^{\prime}=5,10$, respectively. Note that in these cases, the effectiveness of the effect significantly reduces from the case of $k=k^{\prime}$. This is expected since a successful top-$k$ attack will move the original top-$k$ labels to ranks greater than $k$. However, our objective Eq.(8) cannot avoid the case when some of the original labels are placed between $k$ and $k^{\prime}$, so a successful attack to the top-$k$ case may not generalize to a successful attack to the case of top-$k^{\prime},(k<k^{\prime})$.