Cost-Effective Active Learning from Diverse Labelers

1 Introduction

In real-world applications, label acquisition for the abundant of unlabeled data is usually expensive because it requires the participation of human experts. As a result, training an accurate model with as few labeled data as possible has attracted a lot of research interests. One leading approach to this goal is active learning, which reduces the labeling cost by querying only the most valuable instances for their class assignments [Settles, 2009].

In traditional active learning, the algorithm iteratively queries the labels of selected instances from an oracle, which always returns the ground truth. Under this setting with a unique labeler, the labeling cost is measured by the number of queries, and the goal is to train an accurate model with fewest queries. Active learning under this simplified setting has been extensively studied, however, it is not in conformity with the reality. In many real tasks, we usually have multiple labelers offering different qualities of labeling, and need to decide which of them should be queried for the label of the selected instance. The overall quality of labelers can be evaluated based on their previous performance. A labeler who made fewer mistakes receives a higher quality score, and accordingly requires a higher cost for each query. For example, in the task of breast cancer diagnosis from medical images, doctors cannot guarantee 100% accuracy for their classifications, and in general, experienced experts are more likely to make accurate diagnosis than junior doctors. Also, in the crowdsourcing annotation services, such as Amazon's Mechanical Turk, thousands of labelers are available on the Internet to provide noisy annotations, and those labelers who are more reliable tend to receive higher payment.

∗This research was supported by the 973 Program (2014CB340501), JiangsuSF (BK20150754) and NSFC (61333014, 61503182). This research was started when S.-J. Huang was in the LAMDA Group, Nanjing University.

In recent years, learning with multiple labelers has attracted more and more research interests. Most studies focus on obtaining an accurate label from multiple noisy labelers [Donmez et al., 2010; Sheng et al., 2008; Whitehill et al., 2009; Yan et al., 2014; Raykar et al., 2010; Ipeirotis et al., 2014; Lin et al., 2014], ignoring the active selection of instances and labelers. Several approaches are proposed for active learning with multiple labelers [Zheng et al., 2010; Zhao et al., 2011; Zhang et al., 2015]. However, they usually neglect the diverse expertise of different labelers, and globally select the same labeler for all instances. Recently, there are a few attempts to exploit the expertise of labelers for better annotation [Yan et al., 2011; Fang et al., 2014; Dekel et al., 2012; Yan et al., 2012; Ambati et al., 2010; Donmez et al., 2009]. However, they simply assume an identical cost for all labelers, and may get an expensive solution.

One significant difference between our work and existing active learning approaches is that we emphasize the diversity of labelers on both their expertise and query cost. In real tasks, labelers can be different in age, gender, interests and so on, and thus they may have very diverse expertise. As a result, different labelers are good at labeling different instances, which further indicates that a labeler with very low overall quality can still make accurate labeling on some specific instances. For example, in image annotation tasks, a child labeler may make many mistakes on identifying the location of landscape photos, but can easily assign accurate labels to cartoon images; or in evaluation of products, male customers must be more confident on rating a shaver than a skirt. While the overall quality of labeling directly decides the cost of a labeler, it is not necessarily related to the accuracy of the label on a specific instance. And based on this fact, for a given instance, we can hopefully find a right labeler which provides accurate yet cheap annotations.

In this paper, we propose a novel criterion for active selection on both instances and labelers. The criterion evaluates the cost-effectiveness of instance-labeler pairs, and ensures that on one hand, the selected instance is helpful on improving the classification model, and on the other hand, the selected labeler can assign an accurate label for the instance with a low cost. Extensive experimental results validated the superiority of our proposed approach.

The rest of this paper is organized as follows: we first review some related work in Section 2, and then introduce the proposed approach in Section 3. Section 4 presents the experiments, followed by the conclusion in Section 5.

2 RelatedWork

Active learning has been well studied during the past years. Many algorithms are proposed to design different criteria for query selection such that the queried examples are most helpful for improving the classification model. Based on the query criteria used, active learning methods can be roughly categorized into three groups: the methods querying most informative instances (e.g., uncertainty sampling [Balcan et al., 2007; Guo and Schuurmans, 2008] and expected error reduction based sampling [Roy and Mccallum, 2001]); the methods querying most representative instances (e.g., clustering based sampling [Dasgupta and Hsu, 2008; Chattopadhyay et al., 2012] and density based sampling [Zhu et al., 2010]); and the methods simultaneously consider informativeness and representativeness [Huang et al., 2014; Wang and Ye, 2013].

The standard active learning assumes that there is only one oracle which never makes mistake on its labeling. In realworld tasks, however, multiple noisy labelers are available. Many methods have been proposed to learn from the multiple noisy labelers. Some of them try to model the reliability of labelers, and then select the best ones for labeling all the instances [Donmez et al., 2010]. Some other approaches try to find a best combination of noisy labels given by all labelers [Sheng et al., 2008; Whitehill et al., 2009]. These methods, however, do not consider the active selection of instances. The study in [Giacinto and Roli, 2000] is partially related to dynamic classifier selection in ensemble methods, which dynamically selects one classifier for each test instance.

There are some studies on active learning with multiple noisy labelers. Zhao et. al. [2011] combine uncertainty and inconsistency measures to actively select the most important instances for relabeling. Although this approach assumes the existence of multiple noisy labelers, it only designs the criterion for instance selection, and does not select labelers. The approach in [Zheng et al., 2010] obtains the label from a subset of labelers via majority voting. The labelers are globally selected for all instances, which may result in unnecessary high cost because it neglects the expertise of different labelers. There are a few studies trying to select labelers with matching expertise on the specific instance to be labeled [Dekel et al., 2012; Yan et al., 2012; Donmez et al., 2009; Ipeirotis et al., 2014]. For example, Yan et. al. [2011] propose a probabilistic model to measure the accuracy of each labeler, and select the most confident labeler for each queried instance. Fang et. al. [2014] propose to transfer knowledge from auxiliary domains for estimating labelers expertise. Ambati et. al. [2010] apply the active selection of both instances and labelers to the task of machine translation. A common shortcoming of these algorithms is that they do not consider the difference on the costs of multiple labelers, and thus may get an accurate yet expensive solution. The methods proposed in [Donmez and Carbonell, 2008] and [Zhang and Chaudhuri, 2015] consider a simple case where two labelers exist: one perfect labeler which always returns the ground truth, and one fallible labeler which make mistakes with a probability. Although they assume different costs for the two labelers, the oversimple setting limits its application.

3 The Proposed Algorithm

We study the task of active learning from multiple labelers with diverse expertise and different costs. At each iteration of active learning, we select a cost-effective instance-labeler pair with following properties: 1) the selected instance is useful on improving the classification model; 2) the selected labeler can assign an accurate class label for the instance; and 3) the cost of the selected labeler is low.

We start with a simple example to illustrate our basic idea. Figure 1 shows an extreme case of three labelers with different expertise. The data examples are partitioned into three groups: A, B and C, with decreasing sizes. Labeler 1 is good at labeling examples in group A, but fails on groups B and C. Labeler 2 works well on groups A and B, while labeler 3 favors groups B and C. Obviously, labeler 2 achieves the best accuracy of labeling on the whole data set, and deserves the highest query cost. In contrast, labeler 3's overall labeling quality is the worst, and accordingly receives the lowest cost. While the overall quality of labeling decides the cost of each query from a labeler, it does not necessarily implies the accuracy on a specific instance. For the instances in group B, both labeler 2 and labeler 3 can assign correct labels, and then labeler 3 with lower cost is preferred, though its overall quality is lower. This observation suggests that globally selecting one labeler for all instances may result in unnecessary high cost, and one better choice is to adaptively select the most cost-effective labeler for each instance.

Assume that we have a small labeled set L = {(xi, yi)}nl i=1 with nl examples, where yi is the ground truth label of the i-th instance xi, and a large pool of unlabeled data U = {xj}nl+nu j=nl+1 with nu instances, typically nl ≪ nu. There is a set of candidate labelers A = {a1, · · · , am} with all m labelers offering different qualities of labeling with different prices. We denote by ˆ yij the label given by ai for xj.

At each iteration of active learning, the algorithm selects an instance-labeler pair (x∗ , a∗ ), and queries the label of x∗ from a∗ , where the selection of both the instance and labeler is based on a evaluation function Q:

Then the task is to design the evaluation function Q(x, a) to measure the cost-effectiveness of the pair (x, a). To make it clear how the designed criterion satisfies the previously listed properties, we first separately introduce the usefulness of an instance, the accuracy of the labeling and the cost of the query, and then propose the evaluation function by combining them together.

3.1 Usefulness of the Instance

Evaluating the usefulness of an instance on improving the generalization ability of the classification model is the key task of traditional active learning, and has been well studied. Among the existing criteria for evaluating the usefulness of instances, we choose to employ the uncertainty, which is most widely used. If the current classification model is uncertain about its prediction on an instance, then the instance may be more helpful on improving the model because it contains more information that the model does not know yet.

In the binary classification problem, the instance with probability p(y = 1|x) closest to 0.5 is preferred. Thus the uncertainty of x can be measured as:

In this paper, we employ logistic regression for the classification model, and thus have

where f(x) = w⊤x + b is the prediction of the logistic regression model on x.

To be more general for multi-class setting, the uncertainty r(x) can be rewritten as:

where p(y|x) is the probability of that x belongs to class y, and Y is the set of all possible classes.

3.2 Accuracy of the Labeling

As discussed before, the accuracy of a labeler on a specific instance cannot be estimated by its overall labeling quality. Because each labeler has its own expertise, it is reasonable to assume that a labeler will have similar performance on similar instances. We thus try to exploit the label assignments of the labelers on the initial labeled set with ground truth. Intuitively, given an instance x, if a labeler assigns correct labels for most of the neighbors of x in the initial labeled set, then its labeling on x is expected to be reliable. Formally ,we estimate the labeling accuracy of the annotator ai on instance xj by:

where N(xj, t) returns a set consists of t nearest neighbors of xj in the initial labeled set, S(xj, xk) measures the similarity between xj and xk, and I[·] is the indicator function which returns 1 if the argument is true and 0 otherwise. In our experiments, we simply select the neighbors based on Euclidean distance. Obviously, among the t neighbors, the instances which are more similar to xj contribute more to the estimation of qi(xj).

3.3 Cost of the Query

Typically, if a labeler provides high quality of labeling, it requires a high price for answering each query. So the cost of each query from a labeler may be decided by the accuracy of its previous labeling. We denote by ci the cost of querying one label from labeler ai, and define it as

where 1 nl ∑nl j=1 I[yj == ˆ yij] calculates the overall accuracy of labeler ai on L, and g(·) is the function describing the relation between the cost and accuracy. For simplicity, one can implement it as any increasing function, e.g. g(z) = z.

3.4 Cost-Effectiveness

Based on the previous definitions, we then try to propose the evaluation function Q for active selection. To select a costeffective instance-labeler pair (xj, ai), we want the usefulness r(xj) to be large, the accuracy qi(xj) to be high, and at the same time the cost ci to be low. A straightforward criterion for estimating the cost-effectiveness of the pair (xj, ai) can be defined as Eq. 5.

And the most cost-effective instance-labeler pair is selected as:

At last, let us revisit the three properties of the selection we discussed at the beginning of this section. Obviously, an instance-labeler pair violating either of the three properties will receive a small score of Eq. 5, and thus the proposed active selection is cost-effective.

It is worth noting that though the simple implementation of the proposed approach achieves good results to demonstrate our idea, we can have other choices for each of the three components in Eq. 5. For example, the usefulness r(xj) can be designed as in [Huang et al., 2014] to consider both informativeness and representativeness of the instances; the labeling accuracy qi(xj) can be estimated by a individual model for each labeler; and the cost ci can be specified by users according to actual situations.

The pseudo-code of the proposed algorithm, termed CEAL (Cost-Effective Active Learning), is summarized in Algorithm 1. At each iteration of active learning, the algorithm selects the most cost-effective pair (x∗ , a∗ ), and queries the label of x∗ from a∗ . Then x∗ is removed from the unlabeled set U, and is added into L along with its queried label ˆ y∗ from a∗ . After that, the classification model is retrained on the expanded labeled set L. At last, the updated model is evaluated on a hold out test set. This active querying and model updating process is repeated until meets a specific condition, e.g., the given cost budget is exhausted or the required classification accuracy is reached.

4 Experiments

We compare CEAL with the following baseline approaches:

• ALC: the method proposed in [Yan et al., 2011], which actively select one instance and query its label from the most reliable labeler.
• RR: randomly select one instance and query its label from one randomly selected labeler.
• RA: actively select one instance and query its label from one randomly selected labeler.
• CR: randomly select one instance and always query the labeler with lowest cost.
• CA: actively select one instance and always query the labeler with lowest cost.
• QR: randomly select one instance and always query the labeler with highest overall quality.
• QA: actively select one instance and always query the labeler with highest overall quality.

For all the compared approaches, uncertainty sampling is used for instance selection, where the uncertainty is measured based on the logistic regression model trained on the labeled data. We also evaluate the performance on test data by the logistic regression model implemented with LIBLINEAR [Fan et al., 2008] with default parameters.

4.1 Study on UCI data sets

We first perform the experimental study on 12 data sets from the University of California-Irvine (UCI) repository [Bache and Lichman, 2013]: austra, german, krvskp, spambase, splice, titato, vehicle and ringnorm. Letter is a multi-class data set, from which we select four pairs of letters that are relatively difficult to distinguish, i.e., D vs O, E vs F, U vs V, V vs Y, and construct a binary class data set for each pair. The size of the data sets varies from 435 to 7400.

We assume that there are in all 5 labelers offering different qualities of labeling: a1, a2, a3, a4 and a5. Table 1 presents the accuracy of labeling on the initial labeled set L given by each labeler. In increasing order of labeling accuracy, we set the costs of each query from the labelers as 1 to 5, respectively. For each data set, 5% of the examples are sampled to initialize the labeled set L, 30% examples are hold out as the test set for evaluating the classification model at each iteration, and the rest 65% data are taken as the pool of unlabeled data for active selection. The random partition of test data and unlabeled data are repeated for 30 times for each data set. And we report the average results over the 30 runs of experiments.

Figure 2 plots the accuracy curves with the total cost increasing for all the compared approaches. Note that we did not plot the full curve because the performances of most methods have converged after a number of queries. Generally speaking, by paying the same query cost, the methods actively select instances (which are plotted with solid lines) usually achieve higher accuracy than the methods randomly select instances (plotted with dashed lines). This validated the effectiveness of uncertainty sampling. As expected, querying all instances from labeler with minimal cost leads to the worst performance since it receives too many noisy labels. Querying the labeler with highest overall quality may get most instances correctly labeled, but also results in a high cost. Random selection of labelers receives a middle performance. We observe that ALC achieves decent performance on most of the data sets, and fails on the others. Because ALC selects the most confident labeler for each instance, but does not consider cost, it is likely to get accurate labels with high cost, making it less cost-effective. At last, our proposed approach CEAL consistently achieves higher accuracy than other methods with the same query cost.

After the comparison on the cost-effectiveness, we further examine the difference between the compared methods on labeler selection. Table 2 presents the average cost of each query for all the compared methods. Because the counterparts that select instances actively or randomly have similar results, we do not report the results for RR, CR and QR. First, the cost of CA and QA exactly equals 1 and 5, respectively, because they always query the labels from the same labeler. The cost of our proposed method CEAL is much lower than ALC and RA by actively selecting the cost-effective labeler.

Similarly, we present in Table 3 the accuracy of queried labels for all approaches, i.e., the percentage of queried instances that have been correctly labeled. CA selects the labeler with lowest cost, and thus has an accuracy close to the accuracy of a5 in Table 1. Similarly, QA has the accuracy of the most accurate labeler. It is not surprising to observe that ALC achieves a high accuracy because it selects to query the most confident labeler for each instance. The advantage of ALC to QA validates that adaptively selecting a labeler for each instance is superior to the global selection for all instances. Our proposed approach CEAL also achieves a high accuracy, only slightly worse than ALC. Noticing the significant lower cost of our approach, it is obvious that our approach CEAL selects the most cost-effective queries.

4.2 Study on CrowdFlower data

CrowdFlower is a data set for sentiment analysis. The crowdsourced labelers are asked to judge the sentiment of tweets discussing the weather. The data set consists of 98979 tweets, each was labeled by multiple labelers from 5 candidate answers: 0 = negative, 1 = neutral, 2 = positive, 3 =

not related, 4 = cannot tell.

By removing the labelers who have labeled less than 10 tweets, and tweets labeled by less than 3 labelers, we obtain a data set with 10976 tweets and 41 labelers. For each tweet, we extract a bag-of-words feature vector with 43395 dimensions. Among the tweets, only 269 tweets are given with the ground truth. We take 10 of them as the initial labeled set, and take the rest 259 examples as the test set for evaluating the classification model. The rest 10707 tweets are randomly partitioned into 10 folds. At each run of the experiment, we take one fold as the unlabeled pool of active learning. The average results over the 10 runs are recorded. In usual case, we estimate the cost of each labeler on the initial labeled set. However, there is too few examples with ground-truth. We instead estimate the cost on the test set, which is less than 5% of the whole dataset. Note that since we have a relative large number of labelers, the cost is set to equal the overall accuracy for each labeler, i.e., we set g(z) = z in Eq. 4. The cost of the 41 labelers varies from 0.067 to 0.500.

Figure 3 plots the accuracy curve on CrowdFlower with the total cost increasing. The result is generally consistent with that on UCI data sets. One exception is that the performance of QR and QA get worse, probably because that even the labeler with highest quality is not very accurate on this data set. As we can see, again our CEAL approach achieves high cost-effectiveness.

5 Conclusion

This paper studies active learning under a novel setting, where multiple noisy labelers with diverse expertise and different labeling costs are available. We observe that a labeler with low quality of overall labeling can still assign accurate labels for some specific instances. Based on this fact, we propose the CEAL approach to perform cost-effective selection for both instances and labelers. Experimental results on both UCI and real data sets demonstrate that the proposed approach is able to achieve higher accuracy with lower query cost. While our current study assumes the cost of querying different instances from the same labeler is identical, we plan to incorporate instance-dependent query cost into our CEAL approach in the future.