Enhancing Label Sharing Efficiency in Complementary-Label Learning with Label Augmentation

CLL is a weakly-supervised learning problem on multi-class classification. Typical multi-class classification assumes that the feature vector $x_{i}$’s and the corresponding labels $y_{i}$’s in the training dataset $D=\{(x_{i},y_{i})\}_{i=1}^{N}$ are i.i.d. sampled from an unknown distribution. In CLL, $D$ is not accessible to the learning algorithm. Instead, a complementary dataset $\bar{D}=\{(x_{i},\bar{y}_{i})\}_{i=1}^{N}$ is provided to the learner, where $\bar{y}_{i}$ denotes a complementary label, a class to which the instance $x_{i}$ does not belong. The goal of the complementary learning algorithm is to find a classifier $f$ that can predict unseen instances correctly. Typically, classifier $f$ is implemented by a decision function $g:\mathbb{R}^{d}\to\mathbb{R}^{K}$ and taking argmax on $g$, i.e., $f(x)=\operatorname*{arg\,max}_{k\in[K]}g(x)_{k}$, where $g(x)_{k}$ denote the $k$-th element of $g(x)$ and $[K]=\{1,\dotsc,K\}$ denote the set of labels.

In the CLL literature, some assumptions on the generation of complementary labels (CL) are made. The most simple one is called uniform generation. Firstly proposed in the pioneering work [9], it assumes that each complementary label $\bar{y}_{i}$ is independently and uniformly selected from all the labels except the correct one. This assumption is also utilized in some subsequent works [10, 2].

A further generalization to the uniform case is called class-conditional assumption. It assumes that the generation process of the CLs depends only on their underlying ordinary labels, i.e., there is $T_{ij}=P(\bar{y}=j\mid y=i)$ for each ordinary label $i$ and complementary label $j$. When $T_{ij}=\tfrac{1}{K-1}$ for each $i\neq j$, this falls back to the uniform generation. CLL under such assumption is further analyzed in [17]. This type of generation is also called biased generation when $T_{ij}$ is not always $\frac{1}{K-1}$ whenever $i\neq j$ to distinguish it from the uniform one. The generation process mentioned above is noiseless, meaning there are no CLs that actually belong to the ordinary class. In the noiseless case, $T_{ii}=0$ holds for each $i\in[K]$, whereas in noisy CLL [11], the diagonal elements of the transition matrix $T_{ii}$ are a small positive number.

In our work, the augmented CLs using the proposed method are not generated with respect to the class-conditional assumption. Nevertheless, we will show in the experimental section that the proposed method still improves the learning algorithms that rely on them.

In this section, we proposed complementary-label augmentation for the existing loss-based complementary learning algorithms. The main idea of the complementary-label augmentation is to add new complementary labels from a data instance’s neighbors. The idea utilizes the smoothness of the representation space, i.e., if two instances have similar features, then they are likely to belong to the same class. That implies that the complementary labels from the neighboring instances can be shared to each other.

To do so, given a feature extractor $v(\cdot)$, let $v_{i}=v(x_{i})$ denote the feature of the $i$th instance in the complementary dataset, and let $V=\{v_{i}\}_{i=1}^{N}$ denote the collection of extracted features. For each data instance $x_{i}$ in $\{x_{i}\}_{i=1}^{N}$, let $\bar{y}_{i,k}$ denote the complementary label from $v_{i}$’s $k$th nearest neighbor in $V\backslash\{v_{i}\}$.

In a loss-based complementary learning algorithm, there is a loss function $\ell:[K]\times\mathbb{R}^{K}\to\mathbb{R}$ that takes a complementary label $\bar{y}_{i}$ and the model’s prediction $g(x_{i})$ as input. The learning algorithm minimizes the loss function $\ell$ with respect to the complementary dataset $\bar{D}$, i.e., the learning algorithm optimizes $g$ with respect to the following empirical risk:

A naive way to utilize the augmented labels is to directly add them to the loss function as follows:

where $\alpha$ is a hyperparameter that controls how much weight to put on the augmented labels and $N_{K}$ is the hyperparameter that denotes the number of neighbors to consider. This simple approach, however, neglects the fact that the complementary labels augmented from the neighboring instances are noisy. To overcome the issue, traditional $k$NN methods typically associate a weight to the neighbors [5]. We follow the idea, and propose to use a weight $w_{i,k}$ for the pair $(x_{i},\bar{y}_{i,k})$ when training with a complementary learning algorithm. The loss function then becomes:

The above loss function can be interpreted as training with respect to soft complementary labels as follows. Let $z_{i}=\alpha e_{\bar{y}_{i}}+(1-\alpha)\sum_{i=1}^{N_{k}}w_{i,k}e_{\bar{y}_{i,k}}$, where $e_{k}$ denotes the one-hot vector of label $k$, then the loss function is equivalent to

To simplify the notations, we use an $N\times N$ matrix $W$ to denote the weight, where $W_{i,j}$ is the weight from instance $j$ to instance $i$. In addition, we define $N\times K$ matrices $Y$ and $Z$ by setting the $i$th row of $Y$ to the one-hot vector of $\bar{y}_{i}$, i.e., $Y_{i}=e_{\bar{y}_{i}}$ and setting the $i$th row of $Z$ to $z_{i}$, i.e., $Z_{i}=z_{i}$, for each $i$. Then, the process of complementary-label augmentation can be simplified to calculating the matrix $Z$ with the following equation: $Z=\alpha\bar{Y}+(1-\alpha)W\bar{Y}$, then optimize the model $g$ with respect to the loss function $R_{\text{LA}}$ defined in Equation 4.

Label Propagation [20, 18] is a method in semi-supervised learning that also leverages the smoothness assumption. The proposed multi-step complementary-label augmentation shares a similar form to the label propagation method; however, complementary-label augmentation is different from label propagation in two aspects. First, label propagation in semi-supervised learning and complementary-label augmentation propagates different labeling information and for different goals. The former propagates the ordinary labels to the unlabeled data with the goal of obtaining pseudo labels for the unlabeled instances. On the other hand, the latter propagates the complementary labels to the neighboring instances in order to enrich the complementary labels of all the instances in the dataset. Second, the two methods are different in their roles in the training process. Label propagation is typically part of a training process [8], where the labels and the model parameters are updated in an alternating manner. In contrast, complementary-label augmentation is a technique to enrich the labeling information that is independent of the training process and is applied before the whole training process.

In this subsection, we discuss how the number of neighbors, the hyperparameter $K$ in Algorithm 1, affects the testing accuracy. To do so, for each baseline method, we fix the training hyperparameters, including the learning rate and weight decay, to the best one in Section 4 and vary the number of neighbors only. The results are reported in Figure 4. From the figure, we first observe that the best number of neighbors for the multi-step augmentation is smaller than the best number of neighbors for the single-step augmentation. The results distinguished the label sharing mechanism between the single-step and multi-step augmentation. The former propagates the label information to distant instances by performing augmentation multiple times, whereas the single-step augmentation propagates the label information to more instances by increasing the number of neighbors. Hence, the multi-step augmentation requires less number of neighbors while the single-step augmentation requires more. Despite the single-step augmentation can be improved by augmenting with more neighboring instances, we still observe that the multi-step augmentation outperforms the single-step augmentation if the number of neighbors can be tuned.

Besides the proposed complementary-label augmentation, there are some alternative ways to utilize the information from the feature space:

1. 1.

   Fine-tuning from a self-supervised model with the loss-based CLL algorithms is also a way to utilize the feature space of the self-supervised models. Fine-tuning from a pretrained model can be faster or have better accuracy than training from scratch for some downstream tasks. It could potentially be useful for CLL as well.

2. 2.

   Using a $k$NN method to obtain a local estimate of the distribution of the complementary labels, then decoding the results by predicting the target label with the least-likely complementary labels. This method follows the intuition that the least-likely complementary labels should correspond to the most-likely ordinary labels. It corresponds to the decoding methods proposed by Lin and Lin [14] when the transition matrix is uniform.

The results are reported in Table 4. As we can see from the table, fine-tuning from a self-supervised model improved the testing accuracies of the models in three of the datasets. Nevertheless, label augmentation still improved the fine-tuning method. This implies that label augmentation can provide an orthogonal benefit to fine-tuning. On the other hand, as suggested in the table, $k$NN is a strong baseline for utilizing the information from the self-supervised models, with superior performance to training from scratch and fine-tuning. Still, fine-tuning the self-supervised model with label augmentation outperforms the baseline across all the datasets we consider.