Learning to Rank for Active Learning: A Listwise Approach

Most of the active learning strategies are pool-based approaches, which can be further divided into the following categories, depending on the query function: informativeness [16, 17], representativeness [18, 14], hybrid [19, 20] and performance-based [21, 22, 23].

Among all the above approaches, informativeness-based approaches are the most successful ones, with uncertainty being the most used selection criteria used in both bayesian [24] and non-bayesian frameworks [25]. The entropy method [15, 26] calculates the entropy value of class posterior probabilities to define uncertainty, and data with the highest entropy is viewed as the most uncertain. Despite the query strategy is very simple, this method performs remarkably well for classification problems. However, this method is not suitable for regression problems and people need to design specific uncertainty metrics as shown in [9].

The query-by-committee [27, 28] is another popular active learning strategy, which alleviates many disadvantages of uncertainty sampling. For instance, uncertainty sampling tends to be biased towards the actual learner and it may miss important examples which are not in the sight of the estimator. The committee issues multiple hypotheses and the instance with highest consensus is viewed as the most informative. This motivation is simple and clear, however, for current DNNs, training a committee has high computational cost.

In the era of big data and deep learning, it has been proven in [14] that classical approaches as mentioned earlier, do not scale well to large datasets. Therefore, recently, the attention has been shifted towards deep active learning, with adversarial strategies being one of the most popular techniques [29].

The authors of core-set approach [14] define the problem of active learning as core-set selection where the problem becomes a K-center problem which can be solved by using a greedy approximation method. Empirical results showed state-of-the-art performance, but the query strategy is computationally expensive.

Recently, [9] has introduced a novel and task-agnostic active learning method. The authors attach a loss prediction module to the target network, and learn to predict target model’s losses of unlabeled samples. The data with highest predicted loss is viewed as the most uncertain and informative. The experimental results demonstrate that their method consistently outperforms the previous methods over the tasks. They learn the loss prediction module by considering the differences between pairs of loss predictions. However, the batch size of their method must be an even number and they only consider the neighbouring data pairs, neglecting the overall list relationship.

The VAAL (Variational Adversarial Active Learning) approach [30] learns a latent space using a variational autoencoder (VAE) [31] and an adversarial network trained to discriminate between labeled and unlabeled data. Samples predicted as “unlabeled” with the lowest confidence is sent to the oracle. They demonstrate state-of-the-art results. However, training the VAE and the discriminator requires high computational cost, and the hyperparameters may be sensitive.

In our paper, our active learning algorithm is based on the learning loss strategy of [9]. Instead of trying to minimize mean square error of predicted losses and ground-truth losses, we define the problem as a learning to rank problem. We use a listwise approach to train the loss prediction module. Besides, we have further studied the architecture of loss prediction module. The detailed architecture of our algorithm can be seen in the next section.

The central problem of many tasks in information retrieval (IR) and natural language processing (NLP) is ranking, including document retrieval, question answering, meta-search, online advertisement, collaborative filtering, machine translation and so on [32]. Learning to rank means performing a ranking using machine learning techniques. [33] learns to identify a ranked list of related news articles which the user would like to read afterwards. Besides, learning to rank techniques are central to question answering systems for questions are matched against an extensive database to find the most relevant answer [34]. Furthermore, [35] uses learning to rank for fault localization in software debugging.

Learning to rank has two components: a learning system and a ranking system [32]. In the learning system, for each request, there is a set of offerings and there is a true ranking list on the offerings. The ranking system receives a subset of new offerings and assigns scores to them, where the system uses the ranking model trained by the learning system. Then the ranking list is obtained with the scores.

The authors of [36] group learning to rank problems into three approaches: the pointwise approach, the pairwise approach, and the listwise approach. The pointwise approach assumes that each instance in the training data has a numerical or ordinary score, then it can be approximated by a regression problem: given a single query, predict its score. In the pairwise approach, ranking is transformed into a pairwise classification or pairwise regression. A major limitation of the pointwise and pairwise ranking approaches is that the group structure is ignored [32]. The listwise approach instead tries to optimize the value of an evaluation metric. The most commonly used metrics include: mean average precision (MAP), Spearman’s rank correlation [37], normalized discounted cumulative gain (NDCG) [38], etc. The listwise approach is difficult in the context of deep learning end-to-end architecures because most of the metrics are not differentiable with respect to ranking model’s parameters, so surrogate functions are used. In practice, listwise approach often outperforms pairwise and pointwise approaches, and this is supported by a large scale of experiments [39].

In this paper, we will demonstrate that the loss prediction based active learning algorithm actually is a learning to rank problem, which can be seen in subsection III-A. The proposed active learning algorithm adopts a listwise approach to train the loss prediction module. In the subsection III-B, we will describe the surrogate method we use in the listwise approach.

The query strategy of [9] consists of choosing a set of samples with high predicted losses. Learning the loss prediction module by mean square error (MSE) with the ground-truth losses is a simple idea. However, the authors said they failed to learn a good loss prediction module with MSE: the scale of the real loss decreases overall with target model’s learning, so the loss prediction module would adapt roughly to the scale rather than fitting to the exact value. Their solution is to calculate the loss of loss prediction module by comparing pairs of values, i.e. they adopt a pairwise ranking approach. For a mini-batch whose size is $d$, they make $d/2$ data pairs and consider the difference between each pair of predicted losses and ground-truth losses thus discarding the overall scale changes [9].

However, we demonstrate that the problem is not only that the scale of loss changes, but also that the loss prediction module should be trained with ranking loss. Fig. 2 shows an example of why MSE is not optimal for training the learning loss module (G-T represents ground-truth). The ‘Active learning system 1’ has lower MSE value but it recommends wrong data with highest uncertainty, whereas the ‘Active Learning system 2’ recommends right data although its MSE value is higher. This is because ‘System 2’ predicts the right ranks for the unlabeled data. This scenario motivates us to use a better ranking scheme, based on the listwise approach.

Many tasks are evaluated using non-differentiable metrics such as mean average precision or Spearman’s rank correlation [37]. However, it is hard for us to use them as objective functions to train learning models for they are not differentiable. There are surrogate approaches but it is not easy to propose good surrogate functions [40].

Recently, [40] proposes a method to learn to optimize such non-differentiable metrics. They use a deep neural network as a sorter to approximate the ranking function. It is pretrained with synthetic values and their ground-truth ranks. This sorter can then be combined with an existing model (e.g. loss prediction module) and converts the value list given by the model into ranking list. Then the ranking loss between the predicted ranks and ground-truth ranks can be calculated and backpropagated through the differentiable sorter and used to update the weights of the model.

As demonstrated above, we want to minimize the ranking error between the predicted losses and ground-truth losses. Let us consider $rk$ the ranking function which converts the ground-truth losses into ground-truth ranks $rk(l_{\Theta_{tg}})=\{rk(l_{1}),rk(l_{2}),\dots,rk(l_{d})\}$. The function $rk$ also converts the predicted losses into predicted ranks $rk(\hat{l}_{\Theta_{pre}})=\{rk(\hat{l}_{1}),rk(\hat{l}_{2}),\dots,rk(\hat{l}_{d})\}$. For a mini-batch of input data with size $d$, the aim is to learn the parameters $\Theta_{pre}$ for:

$$\min_{\Theta_{pre}}{Error(rk(l_{\Theta_{tg}}),rk(\hat{l}_{\Theta_{pre}}))}$$

(1)

where $Error$ is a metric that calculates the error between two ranking loss lists.

However, the ranking function is not differentiable so the error as shown in (1) cannot be backpropagated to update $\Theta_{pre}$. As described in III-B, [40] proposes a differentiable sorter to learn approximations of the rank vector $rk(\hat{l}_{\Theta_{pre}})$. In this paper, we adopt this method to active learning, aiming to minimize the error between predicted losses and ground-truth losses in the ranking space. Fig. 3 shows the solution to this problem.

Fig. 1 shows the whole architecture of the proposed algorithm for image classification problems, where the predicted loss, ranking loss and ground-truth loss consist of Fig. 3. The architectures for other kinds of problems are similar, i.e. for regression.

In [9], they take the features that are extracted between the mid-level blocks of the target model. However, we use the outputs of last block before the fully-connected layer from the target model as the features of input instances, as we find this method is more effective than using features from all mid-level blocks, and extracting and concatenating features from all blocks is not efficient for very deep neural networks. Besides, using the output of last block as feature is widely adopted in applications, e.g., image captioning [41].

The ranking loss backpropagates to the loss prediction module and updates its parameters $\Theta_{pre}$. In [9], the ranking loss and the target model’s loss are combined with a hyperparameter, and the gradient from ranking loss backpropagates to the target model for some epochs. This will influence the target model’s performance because the loss prediction module and target model are two different optimization problems. Besides, searching for an optimal hyperparameter is also difficult.

In this paper, we stop the ranking loss gradient to the target model and we separate the two losses, removing the hyperparameter, so the loss prediction module and target model are trained separately. The loss prediction module is only used to choose the most uncertain unlabeled instances to be labeled by the oracle. This is another difference with respect to [9].

The loss prediction module consists (see Fig. 1, the blue box) of a global average pooling (GAP) layer, a fully-connected layer, a Leaky ReLU activation function and another fully-connected layer. The GAP is used to decrease the feature scale, as many CNNs do, e.g., ResNet [42] also contains a GAP before the fully-connected layer. We use a Leaky ReLU activation function as this is effective and converges faster. The two fully-connected layers are the core of this module, and they are learned to predict the losses of unlabeled instances by minimizing the ranking loss. [9] also uses a GAP layer and a fully-connected layer to decrease the feature scale, then concatenate them to another fully-connected layer to predict the loss.

For a mini-batch with size $d$, the loss of target model is:

$$loss_{\Theta_{tg}}^{bat}=\frac{1}{d}\sum_{i=1}^{d}{l_{i}}$$

(2)

For the loss prediction module, we use a pretrained differentiable sorter to convert the predicted losses to ranking list, and use MSE as the metric to calculate the error of the predicted ranks and ground-truth ranks. As shown in [40], this method approximates the Spearman’s rank correlation, which is a metric that measures the differences between two lists in ranking space.

For the predicted loss list $\hat{l}_{\Theta_{pre}}$ and the ground-truth loss list $l_{\Theta_{tg}}$, each with size $d$. The Spearman’s rank correlation [37] is defined as:

$$r_{s}=1-\frac{6\|rk(l_{\Theta_{tg}})-rk(\hat{l}_{\Theta_{pre}})\|_{2}^{2}}{d(d^{2}-1)}$$

(3)

The range of this metric is from -1 to 1. If the predicted ranks are same as the ground-truth ranks in every dimension, the value is 1, otherwise -1. Our aim is to maximize (3), this equals to:

$$\min_{\Theta_{pre}}{\|rk(l_{\Theta_{tg}})-rk(\hat{l}_{\Theta_{pre}})\|_{2}^{2}}$$

(4)

As discussed, we use an pretrained differentiable sorter to approximate $rk(\hat{l}_{\Theta_{pre}})$. Let $f_{\Theta_{sort}}$ represent the sorter, then the ranking loss of $f_{\Theta_{pre}}$ becomes:

$$loss_{\Theta_{pre}}={\|rk(l_{\Theta_{tg}})-f_{\Theta_{sort}}(\hat{l}_{\Theta_{pre}})\|_{2}^{2}}$$

(5)

Note that the sorter is pretrained independently on specific synthetic data.

For a mini-batch with size $d$, then the ranking loss of this batch is:

$$loss_{\Theta_{pre}}^{bat}=\frac{1}{d}\sum_{i=1}^{d}{(rk(l_{i})-f_{\Theta_{sort}}(\hat{l}_{i}))^{2}}$$

(6)

So maximizing the Spearman’s rank correlation amounts to minimizing the loss in (6), and this is the mean square error (MSE). Here we can see as Fig. 3 shows, that the Spearman’s rank correlation becomes differentiable and the loss prediction module $f_{\Theta_{pre}}$ can be trained by minimizing an MSE.

In this work we adopt the standard methodology used in active learning literature, i.e. we divide the available labeling budget in cycles. After the loss prediction module is trained in each cycle, it is used to select the unlabeled samples which are sent to the oracle for labeling. Since we are only interested in predicted losses, the query strategy does not require the ranking procedure. Thus, for a given mini-batch, the loss prediction module outputs a list of predicted losses. The higher the loss is, the higher the rank is in this list. The query strategy of the proposed algorithm is choosing the instances with highest predicted losses, which equals to highest predicted ranks (i.e. highest uncertainty)

In each active learning cycle, the active learning algorithms query instances for labeling from a random subset rather than the whole unlabeled pool. Subset size is set to 10000 for CIFAR-10. We begin the active learning cycle with 1000 labeled instances, and in each cycle, we continue to train the target model by adding 1000 labeled instances. We train the target model for 10 cycles.

We use the SGD optimizer to train the target model ResNet-18 of all the active learning algorithms for 150 epochs on training set, with initial learning rate of 0.1. After 120 epochs, the learning rate is decreased to 0.01. The momentum and the weight decay are 0.9 and 0.0005 respectively. We train the loss prediction modules of our algorithm and learning loss approach [9] with Adam optimizer with a learning rate of 1e-3 for 150 epochs. The parameter $\alpha$ of Leaky ReLU is 0.01.

For core-set approach, we use the $K$-Center-Greedy algorithm in [14] in accordance with [9]. For VAAL approach, we use their official released code, and the VAE latent dimension is 32. We train the VAE with Adam optimizer with a learning rate of 5e-4 as the authors do.

We use the same augmentation scheme as shown in [9], including 32$\times$32 size random crop from 36$\times$36 zero-padded images, random horizontal flip, and normalize images using the channel mean and standard deviation vectors estimated over the training set.

Our algorithm is noted as L2R-AL and it shows higher image classification accuracies than others. In the last active learning cycle, the random query strategy obtains a 87.72% accuracy while the VAAL method achieves 87.11%. We use the default hyperparameters of the VAAL official code but fail to get a better result. LL4AL achieves a higher result than the core-set approach: 90.45% and 89.47% respectively. In the last several cycles, the entropy method performs similarly good as our algorithm. In the last cycle, the entropy method achieves 90.64% and our algorithm achieves a 90.95% result. The results shows that the proposed learning to rank active learning algorithm achieves better results than the other state-of-the-art comparing algorithms for CIFAR-10 problem.

Besides, we want to show the ranking comparisons of our approach and LL4AL for each cycle. We use the Spearman’s rank correlation [37] to calculate the ranking effect of predicted losses and the ground-truth losses on the test set, as Fig. 5 shows. The ‘Rank-all-features’ represents the active learning method that uses the same loss prediction module as the LL4AL approach with features from all mid-level blocks but trained with our proposed ranking method. We can see that our approach achieves the highest ranking result on the test set, especially in the beginning cycles. In the last cycle, it achieves 0.977 compared with 0.971 of the learning loss approach and 0.975 of the ‘Rank-all-features’. This result shows that the proposed L2R-AL not only has better loss function for training, but also has better architecture of loss prediction module.

We train the target model and loss prediction modules with SGD optimizer for 100 epochs with initial learning rate of 0.1. After 80 epochs, the learning rate is decreased to 0.01.

The results of these two image classification tasks demonstrate that our algorithm outperforms the other state-of-the-art approaches and the random baseline. However, in the case of entropy, the results show it dominates all other active learning approaches (including ours). It’s worth to mention this aspect, since entropy method is seldomly used as a baseline in the active learning literature. This could be explained by the fact that entropy is a very good measure for uncertainty of classification.

We use the standard evaluation metric for this problem: [email protected] [12] which measures the percentage of predicted key-points falling within a threshold distance 0.5 to the ground truth, where the distance is normalized by a fraction of the head size. We begin with 200 labeled instances, and in each cycle, we add another 200 labeled instances, and stop training after 1000 labeled instances. The batch size is 32. The other settings are in accordance with the image classification tasks.

For entropy method, we use the same approach as [9]: applying the softmax to each heatmap to get an entropy for each body part, then averaging all of the entropy values.

As the training set only has 400 images, the active learning algorithms query from the set directly without using subset. The target model and loss prediction module are trained for 100 epochs with the open source code’s default optimizer: Adam optimizers with initial learning rate 1e-5. We choose the pretrained ResNet-50 based target model which is changed after the third layer with decoder and deonvolutional layers, as the authors [45] have shown its good results. The features are extracted before the decoder layers of the target model and input to the loss prediction module.

We begin with 20 labeled instances, and in each cycle, we add another 20 labeled instances, and stop training after 100 labeled instances. The batch size is 4. The other settings are in accordance with the image classification problems.

The above experiment results show that entropy method is still the outstanding approach for classification problems, but our algorithm also can match with it and outperforms the other algorithms. For regression problems, the entropy method fails and our algorithm achieves the best results.