{'fraction_non_alphanumeric': 0.02773801571396762, 'fraction_numerical': 0.007411648694213824, 'mean_word_length': 4.8609246830723345, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Active Refinement for Multi-Label Learning: A Pseudo-Label Approach

The goal of multi-label learning (MLL) is to associate a given instance with its relevant labels from a set of concepts. Previous works of MLL mainly focused on the setting where the concept set is assumed to be fixed, while many real-world applications require introducing new concepts into the set to meet new demands. One common need is to refine the original coarse concepts and split them into finer-grained ones, where the refinement process typically begins with limited labeled data for the finer-grained concepts. To address the need, we formalize the problem into a special weakly supervised MLL problem to not only learn the fine-grained concepts efficiently but also allow interactive queries to strategically collect more informative annotations to further improve the classifier. The key idea within our approach is to learn to assign pseudo-labels to the unlabeled entries, and in turn leverage the pseudo-labels to train the underlying classifier and to inform a better query strategy. Experimental results demonstrate that our pseudo-label approach is able to accurately recover the missing ground truth, boosting the prediction performance significantly over the baseline methods and facilitating a competitive active learning strategy.


Introduction
Multi-label learning (MLL) is an important learning problem with a wide range of applications [6,1,37]. Traditionally, the problem has often been tackled under the fully-supervised setting [28,36], where an annotated training set that consists of fully-labeled examples is required to learn an accurate multi-label classifier. While the traditional setting covers the scenario where the label classes are fixed before learning, many real-world applications face different situations. One scenario that is common in many applications is the growing number of classes [39], where the growth splits high-level concepts to finer-grained ones [5]. For example, the set of classes might start from high-level concepts such as tAnimal, . . ., Food u, and then grow to include finer-grained concepts like tCat, . . ., Dog, . . ., Apple, . . ., Bananau. In fact, this hierarchical label collection process is considered by Deng et al. [5] as a scalable and efficient way to build large benchmark multi-label data sets, such as the MS COCO data set [15]. Typical applications may have collected sufficient number of labeled data for learning the high-level concepts in a fully supervised manner, but it can be challenging for the applications to efficiently adapt the classifier from the high-level (coarse-grained) concepts to the finer-grained ones. Conquering such refinement challenge calls for two components: one is an effective learning model to exploit the fine-grained labels that have been collected, and the other is a strategic algorithm to actively collect a few more fine-grained and informative labels within a limited budget. In this work, we approach the problem, which we term Active Refinement Learning for multi-label learning, by first focusing on the design of the former component-learning an accurate fine-grained classifier with only limited supervision. Having an underlying learner that could most effectively exploit the limited labels, we then design an active learning method tailored to couple the proposed learner. Finally, combining the two components, we present a total algorithm solution to most efficiently tackle the refinement problem.
Refinement Learning with Limited Supervision To learn the newly introduced finegrained concepts efficiently, an indispensable key is to have a learner that could maximally exploit the limited information on hand. In this work, we assume that the refinement process starts with a very limited number of fine-grained labels to warm start the classifier. In particular, the refinement starts with the model receiving a data set that contains all the coarse-grained labels and a few fine-grained ones, as shown in the left-hand side of Figure 1. Then, the problem of constructing a predictive fine-grained model with the presented data set falls under the big umbrella of weakly supervised learning [38]. Specifically, when we focus on leveraging the coarse-grained labels to build a fine-grained classifier, the problem resembles learning with inexact supervision considered by Zhou [38], where the coarsegrained labels are not in the exact form for the desired output and could only provide weak information about the target fine-grained labels. On the other hand, if we focus on using the fine-grained part of the labels to train the classifier, the problem can be viewed as a multi-label variant of learning with incomplete supervision as some instances receive their exact fine-grained ground-truth labels whereas some do not have labels at all [38]. While both the aforementioned problems have attracted much research attention, the combination of them (inexact and incomplete supervision) which our problem of interest can be cast as, has not yet been carefully investigated to the best of our knowledge.
There are some possible solutions in the literature that might be directly used to tackle the problem. Somehow those solutions are, however, not particularly designed for the problem and hence all carry some caveats. One possible solution is to take the hierarchical relationship between the coarse-and fine-grained labels to assign the "knowingly irrelevant" fine-grained labels, partially filling up the fine-grained label vectors as shown in the righthand side of Figure 1. Then, those assigned labels can be fed in to a one-class multi-label learning model [34,35] to learn a fine-grained (irrelevance) classifier. The caveat of the solution is that the weak supervision from the relevant coarse-grained labels is not exploited. In fact, the distribution of the relevant fine-grained labels is typically not modeled in the original one-class setting [34,35], but only through some heuristic assumption. Another solution is to view the unassigned labels as "missing entries" of the label vectors, and apply techniques to recover the missing entries via low-rank assumptions on the label distribution [8,31,33]. Nonetheless, different from typical assumption made by this line of methods, the unassigned fine-grained labels in our problem are missing structurally rather than randomly, making it hard to recover the missing entries with general low-rank assumptions.
In this work, we propose a new model that undertakes the challenges posed by inexact and incomplete supervision through a novel learning to learn method which jointly exploits the hierarchical relationship between the coarse-and fine-grained labels, as well as the benefits of all available data in hand. The key idea within our model is to take into account all available information to learn the labeling assignments for the unlabeled entries, called pseudo-labels, and use them to guide the decent direction of the parameter updates on the underlying classifier. To seek for the best assignment of the pseudo-labels, conceptually, we hope the model trained according to the pseudo-labels could achieve the best classification performance on a set of disjoint validation data. Inspired by recent works in few-shot meta-learning literature [20,21,22], we treat the handful of data points that receive their fine-grained annotations as the validation set, and view the classification performance on the set as the meta-objective to optimize for. Finally, we adopt an iterative strategy that tunes the pseudo-labels locally on the fly at each gradient descent step of the model parameters to mitigate the computationally prohibiting expense of the meta-optimization problem [29,7]. Finally, we experimentally demonstrate that the proposed method not only assigns accurate pseudo-labels to the unknown entries but also enjoys significantly better performance than other methods for learning fine-grained classifiers under the limited supervision setting.
Query Strategy for Refinement Learning With a label-efficient classifier in hand, a natural follow-up question is how to further improve the classifier's performance given a bit more annotation budget available. Answering this question is not new to the literature of Active Learning [24], where the goal is to strategically query the most informative labels such that the classifier trained on these examples could achieve the best performance. However, as the query strategies are often designed to complement the underlying learner, it is unclear how well off-the-shelf sampling strategies could fit with the proposed pseudo-label learning algorithm specially designed for the refinement setting. As a result, to take into account how the underlying learner are trained with pseudo-labels, we customized a new query strategy that follows the spirit of the classic uncertainty sampling strategy [14], but designed to leverage more of the information provided by pseudo-labels. Specifically, our proposed strategy takes into account how the classifier would change after updated by the pseudo-labels. Unlike the classic vanilla uncertainty sampling method that queries the data lying closest to the current classifier's decision boundary or those having the highest prediction entropy [14,3,27,2], our proposed method quantifies the notion of uncertainty by the expected difference in the classifier's prediction before and after an update led by the estimated pseudo-labels. With the explicit consideration of pseudo-labels,   we experimentally show that the proposed sampling strategy indeed better benefits the underlying learner comparing to classic query methods.
Contributions To summarize our contributions: 1. We formalize the problem of active refinement for multi-label learning to address a common setting faced by many real-world applications.
2. We propose a pseudo-label method for efficiently learning a fine-grained classifier with limited supervision.
3. We combine the pseudo-label learning method with a tailored query strategy to form a total solution for the problem considered.

Problem Setup: Refinement Learning for Multi-Label Learning
Formally, we denote an instance by a feature vector x P R d , and its relevant labels by a bit vector y P t0, 1u K to indicate whether the labels in a pre-defined set Y " ty 1 , ..., y K u are relevant, i.e., yrks " 1 if and only if y k is relevant. In this work, rather than assuming that the set Y is fixed, we consider the problem of splitting the original high-level concepts into finer-grained ones, refining the label set of interest from Y c " ty 1 , ..., y C u into Y f " ty 11 , y 12 , ..., y C1 , y C2 , ...u as shown in Figure 2. Let y c and y f be the corresponding label vectors for Y c and Y f respectively. Assume that we receive a data set D tr " tpx n , y c n qu N n"1 consisting of N examples that are annotated only with the high-level (coarse-grained) labels, and an additional small warm-up set D 1 tr " tpx 1 m , y 1f m qu M m"1 of M examples with their fine-grained labels annotated, our first goal is to leverage these examples to learn an accurate fine-grained classifier Φpθ, xq : R d Ñ t0, 1u K where θ is the model parameter and K is the total number of fine-grained classes.

Related Work and Possible Existing Solutions
Fully-Supervised Learning A straightforward way to learn a fine-grained classifier is to utilize only the fully-annotated training examples in D 1 tr through standard supervised approaches. Nevertheless, the small number of examples in this set might be unable to train a strong classifier. Moreover, it completely ignores the (weak) supervision provided by the abundant coarse labels.
Multi-Label Learning with Missing Labels One way to make use of the higher-level supervision on learning the fine-grained concepts is to leverage the hierarchical relationship where the irrelevance of a parent (coarse) concept implies the irrelevance of all of its children (fine) concepts. Leveraging the relationship, we are able to infer the corresponding entries in the fine-grained label vectors of the examples in D tr , making Y f " ry f 1 , ..., y f N s J partially observable, and reduce the original problem into a multi-label version of the negative-unlabeled learning problem [17,23] with very few positive examples, as shown in the right-hand side of Figure 1.
To tackle the reduced problem, one way is to treat the unknown fine-grained labels as missing entries, and apply MLL algorithms that can learn with the presence of missing labels [8,31,33]. Yu et al. [33] proposed a classic empirical risk minimization styled method LEML, attempting to solve the optimization problem that arrives at the model parameters which can most accurately recover the observed training labels. Roughly, their objective is formulated as: where Ω is the set of indices of the observed entries in Y f and L is a loss function that measures the discrepancy between the predicted and ground-truth labels. We use binary cross entropy loss for L throughout the paper if not otherwise mentioned. From the objective, however, we note that only the observed entries contribute to the learning of model parameters, and the unobserved ones are basically ignored in the model training process. Unfortunately, in our setting, as the observed fine-grained labels are mostly deduced from the irrelevance of their parent labels, LEML is thus unable to exploit the weak supervision provided by the relevant coarse labels.
One-Class Multi-Label Learning Another plausible direction to approach the reduced problem is through one-class multi-label learning methods [34,35]. These methods are designed to handle the setup where the observed entries all hold the same values. A common approach took in these methods is to assume the values of the unobserved entries to be the opposite class of the observed ones, and train a cost-sensitive classifier with different weights given to the observed and unobserved entries. Namely, assume that the observed entries are all negative (as in the deduced fine-grained matrix Y f ), the one-class methods optimize the following objective function: where w ij is the corresponding weight on the loss of each entry, and is typically set to make w ij ą w kl for pi, jq P Ω and pk, lq R Ω, i.e., the observed entries have higher weights than the unobserved ones. Note that the unobserved entries are set to some default value (in this case, 1) in the objective function. Nonetheless, as the underlying ground truths for the missing entries are not necessarily the presumed class, without careful algorithm redesign or label distribution estimation, these methods may suffer from the introduced label bias that results in suboptimal performances [18,19,13].

A Pseudo-Label Method for Refinement Learning
While existing solutions have developed different ways of treating the unknown entries during the learning process, they somehow do not delicately exploit the benefits of the unlabeled entries as mentioned in the previous section. In light of this, we seek for a method that could more properly leverage the missing entries with a key assumption that: When the missing entries are all correctly recovered and used in the training process, the classifier learned could achieve the best performance. Based on the assumption, we attempt to find the best labeling assignment to the unknown entries, called pseudo-labels, which when the model is trained accordingly, can lead to best classification performance on the fine-grained concepts. Towards this goal, we propose to use the few examples that receive their fully-annotated fine-grained labels in D 1 tr as a validation set to evaluate the classifier's performance on the fine-grained concepts. Formally, we aim to train our fine-grained classifier using the examples in D tr with a pseudo fine-grained label matrix Y pseudo where: where every p ij is a pseudo label to be determined and the objective is: LpΦpθ, x n qrks, rY pseudo s n,k q.
Note that with different pseudo-labels assigned to the missing entries, we arrive at different optimal model parameter θ˚pY pseudo q. From our assumption, the optimal assignment of the pseudo-labels should be based on the validation performance of the resulting classifier: LpΦpθ˚pY pseudo q, x 1 m qrks, y 1f m rksq.
However, solving Eq. 5 to find the optimal pseudo-label assignment requires a computationally prohibiting bi-level optimization procedure [29]. To conquer the optimization challenge, inspired by recent works in meta-learning literature [7,22], we attempt to tackle the problem with an iterative approach which dynamically find the best pseudo-label assignments locally at each optimization step. Specifically, consider a typical gradient descent update step: LpΦpθ, x n qrks, rY pseudo s n,k qˇˇˇˇθ where α is the step size and t is the current timestep. Then, at each iteration t, we aim to learn the pseudo-label assignment which leads to the model parameters that minimize the validation loss after a single update step: Solving Eq. 7 at each timestep t could, nevertheless, still be very expensive. As a result, we propose a simple approximation of pY pseudo qt by looking at the gradient direction (sign) of

Algorithm 1 Refinement Learning with Pseudo-Labels
Input: D tr and D 1 tr Initialize θ 0 and Y pseudo ; for t " 0 . . . T´1 do Sample an example x n and its currently assigned pseudo-labels Y pseudo rn, :s; Perform pseudo-update step on θ t and obtain a temporary θ t`1 by Eq. 6; Calculate partial derivatives of Y pseudo and obtain Y pseudo t by Eq. 8; Perform real parameter update θ t`1 Ð θ t using the above obtained Y pseudo t ; end the validation loss wrt. the pseudo-labels. Particularly, we assign pseudo-labels at timestep t by: where I is the indicator function. After obtaining the newly assigned pseudo-labels Y pseudo t , which could be viewed as approximately the best label assignment locally at step t, we could utilize them to guide real parameter update on θ t . We outline the complete learning algorithm with pseudo-labels in Algorithm 1.

Active Refinement Learning with Pseudo-Label
In the previous section, we have discussed about how to design a strategic algorithm that could learn to predict accurately given only a handful of supervision. In practice, however, in addition to an effective algorithm that can sufficiently exploit all the information residing in the limited data, another critical component is how to efficiently gather new labels that could in turn boost the prediction accuracy the most if we are allowed a little bit more budget on obtaining fine-grained annotations. As a result, in this section, we complement the proposed algorithm by further leveraging the concept of pseudo-label to design an efficient active learning strategy that together yields a total solution for the proposed problem of active refinement learning for multi-label classification.
To start with, consider that we are initially given M fully-annotated examples. Our goal of the active learning algorithm is to query as few as possible the ground truth of the unknown fine-grained labels in the remaining N examples, i.e. the white entries in the right-hand side of Figure 1, such that the classifier could learn to achieve the highest accuracy. Of course, one naive query strategy is to simply query the unknown labels randomly without taking into account the data distribution and the current model behavior. Another commonly adopted strategy is uncertainty sampling which has an underlying assumption that the most informative data are those that the model is most uncertain with, and thus suggests to query the labels that lie closest to the decision boundary of the current model [14]. While comparing to the random baseline, uncertainty sampling benefits from considering the current model behavior and seek to improve the model's prediction confidence by selecting to query the labels with the highest prediction uncertainty. A main caveat of such strategy is that it might lead to over-confidence of the model, resulting in suboptimal prediction accuracy in the end. For example, uncertainty sampling is prone to ignore the examples that lie far away from the current decision boundary which in fact have the opposite ground-truth labels to what the model predicts them to be [11]. In such cases, the model ultimately only optimizes for the accuracy in a rather local region around its initial decision boundary. To look further into such problem, the reason why uncertainty Algorithm 2 Active Refinement Learning with Pseudo-Labels Input: D tr , D 1 tr , and Query Budget B Compute the current prediction of the unknown entries with θ t by Eq. 9; Calculate pseudo-labels for the unknown entries according to Eq. 8; Perform pseudo-updateθ t Ð θ t with the above pseudo-labels; Compute the look-ahead prediction of the unknown entries withθ t by Eq. 10; Query for the ground truth label of rY f s i,j according to Eq. 11; Initialize Y pseudo ; Learn the classifier with Algorithm 1; end sampling could not take into account the existence of overly confident predictions (which are actually wrong) might be due to the fact that the model's prediction itself seems to be the only guess of the ground-truth label of the data. If there is other more precise way to estimate the ground truth of the labels, we might be able to take into account this information and in turn adjust our query strategy. This idea then naturally leads to leveraging our proposed pseudo-labels to design a more sophisticated active learning strategy.
Our proposed method closely follows the concept of uncertainty sampling in the sense that we select the most uncertain labels to query. However, instead of determining the uncertainty merely based on its distance to the current decision boundary, or similarly, the entropy of the predictive distribution, we quantify the notion of uncertainty by measuring how large the label prediction would change after the model is updated accordingly. But how can we know how the model will change before actually querying and obtaining the ground truth labels? This thus leads to the use of the proposed pseudo-labels. Specifically, in each active learning iteration with current model parameter θ t , we first obtain each unknown entry's label prediction by: Then, we apply Eq. 8 to obtain the pseudo-labels of the unknown entries and perform a pseudo parameter update by using the pseudo-labels as the ground truths, and arrive at model parameterθ t . By looking ahead on the updated parametersθ t , we could obtain new predictions for the unknown entries by: Finally, we compute the cross-entropy betweenŷ i,j andŷ 1 i,j to measure the uncertainty of each entry. Our algorithm then selects to query for the ground truth label of rY f s i,j , where the entry pi, jq has the highest uncertainty: We note that our method also resembles the design of Expected Model Change [25,24], in a sense that we utilize the pseudo-labels to look a step ahead into how the model will change (and hence its prediction) and leverage that information to inform our query selection. We outline the complete algorithm for active refinement learning with pseudo-labels in Algorithm 2.

Experiments
To justify the effectiveness of the proposed methods, we test our methods on two multi-label image datasets, MS COCO [15] and MirFlickr [12]. The MS COCO data set contains in total 82081 training instances and 40137 testing instances, with 12 coarse-grained concepts and 80 fine-grained concepts; the MirFlickr data set consists of 14753 training instances and 9828 testing instances, with 10 and 38 coarse-and fine-grained concepts respectively.
In the experiments, we utilize the image features of size 2048 extracted with a deep residual network, ResNet-50 [9], pre-trained on the ImageNet data set [4].

Refinement Learning with Limited Fine-Grained Labels
In the first part of the experiments, we validate how the proposed pseudo-label approach could be used to learn an accurate classifier with only limited fine-grained supervision. We compare the proposed method with three baselines, namely, (a) a standard fully-supervised (FS) learning model, (b) LEML, a classic approach in handling typical missing-label setup [33], and (c) an exemplar method that tackles the problem of one-class classification (OCC) [35]. As discussed in Section 2, these selected baselines serve as representative methods in different families that can be more easily adapted to approach the refinement problem considered. We thus choose to restrict our focus on benchmarking the proposed solution with these representative methods, and leave further exploration and comparison with their more complicated variants as future direction. For fair comparison, we fix the base model architecture to be a multi-layer fully-connected neural network across all methods considered such that we could focus on the effect of different training strategies. Specifically, for the base model, we employ a network consists of an input layer with size 2048, two hidden layers each with size 512, and an output layer of size corresponding to the total number of fine-grained labels of interest.
To evaluate the performances of the learned multi-label classifiers, we utilize the commonly adopted criterion Precision@k (P@k) [32,30,16]: whereŷ P R K is the predicted score vector, y P t0, 1u K is the ground truth label vector, and rank k pŷq returns the top-k largest indices ofŷ. Precision@k measures a multi-label model's ability to correctly rank the relevance of each label with respect to a given instance. Evaluation on the ranking avoids the requirement of selecting some hard threshold to bipartite relevant and irrelevant labels, where the best threshold value could vary drastically across different methods. We provide results of precision@k at different values of k, which in essence correspond to the average precision. We fine-tune the hyper-parameters for all methods using a held-out validation set, and report the average performance of each method over 10 different runs.
Comparison with baseline methods In Table 1 and 2, we show the results of different methods with varying size of fully-annotated warm-up set D 1 tr . Note that we especially focus on the regime when the ratio of D 1 tr : D tr is particularly low to match the realistic scenario when only very scarce fine-grained supervision is available. From the Tables, it can be seen that our method consistently achieves the best performances across different settings. It is worthwhile to note that although the standard fully-supervised approach does not leverage the partially labeled examples in D tr , it surprisingly outperforms the other two baseline methods in many cases. To investigate the reasons for so, we plot the learning curves of different methods in Figure 3. From the figure, we see that although LEML and OCC achieve comparable, or even better, performances than the fully-supervised approach at the very beginning of the learning process, the two approaches then quickly suffers from overfitting that results in the performance drop. For LEML, we conjecture that the performance degrading comes from the overwhelming number of negative entries   dominating the learning dynamic. And arguably, the severe overfitting of OCC results from the over-simple assumption on the missing entries which brings label bias into the learning objective.
Recover rate of our method To understand the benefits of the pseudo-labels learned in our approach, we show how our method is capable of correctly recovering the missing entries, as well as the correlation between the recover rate and model performance. In Figure 4, we plot the recover performance of the learned pseudo-labels measured by F1-loss (1´F1-score), and the horizontal bars are the corresponding F1-loss by simply treating all missing entries as ones and assigning them random labels. We can see from the figure that the pseudo-labels learned from our method could much more correctly recover the missing entries than the two naive baselines. In addition, there is a strong correlation between the recover rate and model classification performance. With more accurate assignment of pseudo-labels on the unknown entries, the trained model is able to achieve stronger classification performance.

Active Refinement Learning
In this part of the experiments, we evaluate the effectiveness of different sampling strategies when coupled with the proposed pseudo-label learning algorithm. We compare our proposed strategy that leverages pseudo-labels in the query process as described in Section 3.2 against other two baselines: (a) random sampling (RS), that is, to query for the ground truth uniformly over all unlabeled entries; and (b) uncertainty sampling (US), namely, to sample the unknown labels with largest model's classification entropy [3]. In the experiments, we follow the common batch setting where we update the model periodically after querying a batch of labels [26,10]; in our setting, the learner queries 1000 labels per batch on MS COCO and queries 100 labels per batch on MirFlickr. Then, the classifier performs 1-epoch update on the data set augmented with the newly queried labels. To prevent the classifier overfits the initial data set, we reinitialize the model per 10 queries. The performance of the classifier is evaluated with Precision@k after each query. As the goal is to achieve the best prediction accuracy with as least queries as possible, we plot the progression of the classifier performance as more labels are queried as shown in Figure 5. To compare between different progression curves, we follow common setup to aggregate the performance by computing the area under progression curves (AUC). We list the AUCs of different methods in Table 3.
Comparison with baseline methods From Table 3, we observe that both uncertainty sampling and our proposed active learning strategy outperforms the naive random sampling baseline in most scenarios, which can mainly be attributed to the fact that random sampling ignores the relationship between the unlabeled data and the current model behavior. We also see a slightly better performance of our active learning strategy over the pure uncertainty sampling baseline. We conjecture such improvement comes from the utilization of pseudolabels which allows our method to look ahead into how the model would change after a single iteration of update and further leverage this information to query the labels that would still remain highly uncertain to the model, instead of selecting the labels to query based directly on the current uncertainty level.

Conclusion
We formalize the problem of active refinement learning for multi-label classification to address a common need faced by many real-world applications. We develop a novel pseudolabel learning method through a meta-learning strategy which could efficiently learn an accurate classifier with very limited fine-grained supervision. Moreover, we design a tailored active learning strategy for the pseudo-label learner to query for the most informative labels that further improve the classifier's performance. Experimental results show that the proposed approaches compare favorably against existing possible methods, constituting a promising solution for the active refinement learning problem.