Active Learning from Crowds with Unsure Option

1 Introduction

It is often very costly (e.g., time consuming) to label an instance in a real-world application. By carefully choosing a subset of instances to label, active learning is expected to result in a good learner with less labeling cost than traditional learning techniques. Specifically, such a subset is chosen iteratively with query heuristics, which may query instances that are informative [Settles et al., 2008], representative [Nguyen and Smeulders, 2004], or both [Huang et al., 2010].

Existing active learning approaches can be categorized as using a single annotator [Roy and McCallum, 2001] or using multiple annotators [Dekel et al., 2012]. The former is regarded as traditional active learning and the latter, which is essentially a kind of ensemble method [Zhou, 2012], is often referred to as Active Learning from Crowds (ALC) and is attracting increasing research interests thanks to the development of crowdsourcing techniques, e.g., the Amazon Mechanical Turk platform.

∗Corresponding author

Since multiple annotators are involved, an ALC algorithm needs to identify not only the instances to query, but also the appropriate annotators for the chosen instances. Yet choosing annotators is a non-trivial task, as it is unknown in advance what instances an annotator will label correctly. Hence, estimating the expertise of candidate annotators plays a key role in ALC algorithms. So far, much effort has been made toward this purpose [Long et al., 2013] [Yan et al., 2011]. However, all the existing methods try to address this challenging task in a passive way, assuming all annotators must provide labels. This paper goes a step further, the annotators are allowed to express that they are unsure about the assigned instances. The "unsure" feedback is safer than the labels from reluctant annotators because the latter has more chance to be misleading. Moreover, different annotators may feel difficulty in different instances, and thus the unsure option provides a valuable ingredient for modeling crowds' expertise.

Motivated by this consideration, a variant of ALC, namely Active Learning from Crowds with Unsure option (ALCU), is formulated and investigated in this work. In ALCU, an annotator not only may provide either labels to queried instances (just like in standard ALC), but also may express that he/she is unsure about the instances' labels. Specifically, the contributions of this work include:

• 1). The ALCU problem is formulated.
• 2). A Support Vector Machine (SVM) approach, namely ALCU-SVM, is proposed to tackle the ALCU problem.
• 3). Empirical studies on both simulated and real crowdsourcing data are conducted, which demonstrate that ALCU-SVM can significantly enhance the effectiveness of ALC. Thus, the importance of providing the unsure option in ALC is justified.

The rest of the paper is organized as follows. The related work of ALCU is reviewed in Section 2. In Section 3, the problem description of ALC and ALCU are presented. The analysis of ALCU and the proposed approach ALCU-SVM

are introduced in Section 4. Section 5 presents experimental studies. Finally, the paper concludes with some discussions in Section 6.

2 RelatedWork

As mentioned above, one of the most important issues of learning from crowds is to model the expertise of annotators. According to different assumptions they offer regarding annotators' expertise, existing works on ALC can be categorized into 3 groups:

First, in their pioneering work, Sheng and Provost [Sheng et al., 2008] assume that an annotator gives correct labels with a certain probability, and the probability is assumed to be the same for all annotators in all instances. Albeit overly simplified, this assumption facilitates understanding some of the most fundamental issues of ALC.

The second type of ALC methods [Long et al., 2013] [Donmez et al., 2009] [Zhao et al., 2014] does not assume all annotators will behave exactly the same. Instead, the probability that an annotator provides the correct label of an instance is characterized as a function of two factors, namely the reliability of the annotator and the difficulty of the instance. The reliability of an annotator is assumed to be the same over all instances, but reliability of one annotator may differ from that of another. In [Donmez et al., 2009] and [Long et al., 2013], all instances are assumed to be of the same difficulty, and different methods are proposed to estimate the reliability of annotators. Zhao et al. [Zhao et al., 2014] go one step further by introducing different difficulties of instances and developing an approach to estimate both reliability of annotators and difficulties of instances.

If the reliability of an annotator is assumed to be the same over all instances, annotators with higher reliability will be more likely to be chosen for all the instances. This may lead to choosing inappropriate annotators. Alternatively, the reliability of annotators could also be formulated as joint probabilistic models of instances and annotators [Yan et al., 2011] [Yan et al., 2012]. In each iteration, the joint probabilistic models are first estimated, and then the instance to query as well as the optimal annotator are chosen simultaneously based on the models. This type of methods directly estimates the probability that each annotator provides the correct label for each instance and thus does not suffer from the drawbacks induced by the assumptions made in the previous two categories. On the other hand, it involves a more challenging intermediate task, i.e., estimating the accuracy of each annotator in each instance, which is non-trivial to solve.

In addition to the research on ALC, it is also noteworthy that the term "unsure option" has also been considered in research on abstaining classifiers [Kwok, 1999] [Pietraszek, 2005] [Friedel et al., 2006]. However, these works concern learning a classifier that can output an "unsure" label. In ALCU, the learned classifier is not allowed to output such a label. Instead, it is the input of a learning algorithm (i.e., training data) that may consist of "unsure" labels. Thus, albeit relevant to each other, ALCU and training abstaining classifiers actually consider different learning problems.

3 ProblemDescription and Analyses

Let {x1, x2, . . . xN} denote N instances and T denote the number of annotators. Without loss of generality, a binary classification problem is considered in this work. The correct label of the j-th instance is denoted by zj, i.e., zj = {+1,-1}. Let yt j denote the label of annotator t on the jth instance. By providing annotators the unsure option, yt j can be +1, -1 or 0 in ALCU, where 0 indicates that the annotator is unsure in that instance. It should be noted that in a real-world ALCU scenario, a zero yt j is substantially different from the case that the value of yt j is missing, because the reason for the latter case might be multi-folds rather than that the annotator is unsure about the label. Since ALCU is a variant of ALC with a new option for annotators' feedback, a unified view that we take on ALC is first described below. The proposed algorithm for tackling ALCU will be detailed in the next section.

We denote the target classifier to be achieved by active learning as f(x) and the classifier obtained after i rounds of queries as fi(x). An active learning algorithm relies on the query heuristic to identify the instance x to query in each iteration. For many commonly-used active learning algorithms (e.g., [Lewis and Catlett, 1994] [Dagan and Engelson, 1995]), the query heuristics can be viewed as maximizing some reward functions that take the form H(x|Li, fi, θi)(H > 0), i.e., the queried instances is picked in the (i + 1)-th iteration according to Eq. (1):

where Ui is the current set of unlabeled instances, Li is the current labeled data, and θi is the parameter of H.

In the context of ALC, a query would be beneficial only if a correct label is obtained. We further introduce gt(x), a function over x, to denote the true reliability of annotator t. Also, a function of gt(x), denoted by Ω(x), is used to represent the reliability of the crowds (i.e., the set of all annotators). Following this viewpoint, Eq. (1) can be re-written as Eq. (2) for ALC.

The advantage of viewing ALC as Eq. (2) is that the selection of annotator is not involved at this stage. That is, the selection of queried instance and annotator can be tackled separately. On the other hand, the challenge is that Ω(x) needs to be specified such that it can be calculated with gt(x). One way to address this issue is to take a binary view on Ω(x) and gt(x). Concretely, Ω(x) = 1 if x can be correctly labeled by at least one annotator in the crowds and Ω(x) = 0 otherwise. Similarly, let gt(x) > 0 if annotator t can label x correctly and otherwise gt(x) ≤ 0. Finally, Eq. (3) can be obtained.

where ∨ is the disjunction function, for any x1, x2 ∈ {0, 1}, x1 ∨ x2 = 0 if and only if x1 = 0 and x2 = 0, x1 ∨ x2 = 1 otherwise. δ(x) is the sign function, δ(x) = 1 if x > 0 and δ(x) = 0 otherwise. T = {1, 2, . . . , T}.

Eq. (3) requires gt(x) to be known. In practice, however, it is unlikely that gt(x) is known in advance. Alternatively, it can be iteratively learned from the responses of annotators. When learning gt(x), an instance is treated as negative if the t-th annotator chooses the unsure option, and positive otherwise. When a response is received from annotator t, gt(x) is updated and then Ω(x) is recalculated with the updated gt(x).

For an instance x selected using Eq. (2), an annotator with gt(x) > 0 can be queried. If multiple such annotators exist, the one with the largest gt(x) is chosen, i.e., with Eq. (4)

The above idea builds up a general framework for tackling ALCU. Albeit simple, it might not be the optimal one. Other potential approaches are discussed in Section 6.

4 ALCU-SVM

The basic idea of ALCU-SVM is modeling gt(x) as a binary classifier. We assume in ALCU-SVM that the target classifier and reliability model of annotators take the following forms:

where K(·, ·) and Kt(·, ·) are the kernel functions of target classifier and annotator t's reliability model respectively.

Further, ALCU-SVM employs uncertainty sampling [Settles, 2010] as the query strategy. The reward function used in this paper can be defined as follows:

where P(z = 1|x, fi) is estimated using Eq. (8):

Since maximizing (7) is equivalent to minimizing |fi(x)| [Yan et al., 2011], Eqs. (2) and (4) can be rewritten as Eqs. (9)-(10), respectively.

where C is a sufficiently large constant that all the instances x , which is subject to Ω(x) ̸= 1, would not be selected.

It is note-worthy that Eq. (9) explicitly biases toward the instances in which at least one annotator is deemed to be sufficiently reliable, i.e., Ω(x) = 1. However, the reliability models of annotators might not be accurate enough, especially in the early stages of learning. Hence, it is possible that the most informative instance with respect to Eq. (1), would not be chosen to be queried even if there exist some annotators who can label it correctly. To overcome this problem, the most informative instance x′ is chosen using Eq. (11)(maximizing (1) is equivalent to minimizing (11) for ALCU-SVM), and if x′ is different from the instance chosen using Eq. (9),

Algorithm 1: ALCU-SVM

Data: Max number of queries Num, initial data X0 , initial observed label Y0, unlabeled data Xu Result: classifier f, reliability models of annotators {gt} begin

1

2

4

5

6

7

8

9

10

11

12

13

14

15

16

Initialize f and {gt} with X0 and Y0 i = -1 3 while i < Num-1 do i = i +1 Using Eq. (11) to get the x′ Using Eq. (9) and (10) to get xi+1 and ti+1 Query the label of xi+1 from ti+1 Remove xi+1 from unlabeled set Update f, wti+1 and gti+1 if xi+1 ̸= x′&i < Num - 1 then i = i +1 xi+1 = x′ Using Eq. (10) to get annotator ti+1 to label xi+1 Query the label of xi+1 from ti+1 Remove xi+1 from unlabeled set Update f , wti+1 and gti+1

it is also queried with the most reliable annotator identified with Eq. (10).

Building the reliability model for an annotator may be a class-imbalanced problem since the positive/negative data collected for a highly unskilled/skilled annotator will be rare. Quite a few existing techniques [Batuwita and Palade, 2010] [He and Garcia, 2009] can be adopted to address this problem. For the sake of simplicity, training instances are assigned with weights proportional to the sizes of class in the whole training data, i.e.:

where wp,t and wn,t are the weights assigned to positive data (labeled data) and negative data (unsure data) when training gt(x). Np,t and Nn,t are the sizes of positive and negative data, respectively, collected for annotator t.

Algorithm 1 outlines the steps of ALCU-SVM, where wt denotes [wp,t,wn,t]. In line 10 of Algorithm 1, xi+1 ̸= x′ indicates that the current reliability models cannot suggest a sufficiently reliable annotator to label the most informative instance x′ . However, there may be some annotators who can label it correctly while the current reliability models are not accurate enough in this instance. As the classifier can greatly benefit from obtaining the correct label of x′ , it is necessary to obtain this label by all means. This is what lines 12-16 do.

5 Experiments

Empirical studies on three UCI data sets (including Pima, Heart and Ionosphere) and a real crowdsourcing data set have been conducted. Overall, through these experiments, the following questions will be investigated:

• (a). The benefit of providing the annotators an unsure option.
• (b). The advantages of ALCU-SVM over other ALC methods for ALCU problems.
• (c). The influence of reliability model selection.

Section 5.1 investigates question (a) on UCI data sets. Question (b) is investigated in Section 5.1 and 5.2 on UCI and real-world data sets, respectively. Question (c) is studied in Section 5.3. In the experiments, three state-of-the-art ALC algorithms, namely PMActive [Wu et al., 2013], IEThresh [Donmez et al., 2009] and ALC [Yan et al., 2011], were evaluated as compared methods. In every experiment, each algorithmwas repeated 20 times. If not specified explicitly, the linear kernel was employed in the classifier (K(x, y) = x·y) and the RBF kernel was in reliability models (Kt(x, y) = exp(-||x - y||2 )).

5.1 Experiments on Simulated Data

To answer question (a), the three existing algorithms were applied in two scenarios, ALC scenario and ALCU scenario. In this experiment, each annotator is assigned with an area of expertise. For the instances belonging to its expertise, annotator t will give the correct labels with probability Pt and wrong labels with probability 1-Pt in both the ALC and ALCU scenarios. For the other instances, annotator t will give correct labels with probability pt and wrong labels with 1-pt in the ALC scenario while give unsure feedbacks in the ALCU scenario. The three compared methods mentioned above were developed for the ALC scenario. At the same time, they can be directly applied to the ALCU scenario by treating the unsure feedbacks as missing values (i.e., no responses). Although exactly the same algorithms were used in the two scenarios, we denote the algorithms used in the latter as PMActive+R, IETresh+R and ALC+R to differentiate the two scenarios. It is noteworthy that none of the three methods was modified to exploit the information contained in an unsure response, i.e., they just discarded the unsure responses. Hence, comparing the results of the three methods in the ALCU scenario against their results in the ALC scenario would allow us to assess whether it would be beneficial to provide annotators the unsure option.

The ALCU-SVM was also applied in the ALCU scenario and was compared against PMActive+R, IETresh+R and ALC+R. As ALCU-SVM explicitly makes use of the unsure responses to model the reliability of annotators, such a comparison would provide some evidence on whether it is worth developing a specially tailored approach, e.g., ALCUSVM, for ALCU rather than utilizing some existing ALC directly.

When simulating multiple annotators with different expertise, we followed the settings in [Yan et al., 2011] and [Wu et al., 2013]: Each data set was first clustered into five subsets using k-means [Jain et al., 1999]. This procedure was repeated twice and ten clusters were obtained. Then, 10 annotators were assumed such that annotator t (t = 1, 2, . . . , 10) was capable of giving the correct labels for instances in cluster t with probability Pt, i.e., s/he would give the wrong label with probability 1 - Pt. For the instances not belonging to cluster t, annotator t did not have enough knowledge. It was assumed to reply with unsure feedbacks in the ALCU scenario. In the ALC scenario, it would give the correct labels with probability pt and make a mistake with 1 - pt. In our experiment, Pt ∼ U(0.9, 1.0) and pt ∼ U(0.5, 0.6). Besides, each data set was randomly divided into three parts: initial set, active learning set and testing set. To be specific, the three data sets were divided as: Pima (20,548,200); Heart (20,150,100) and Ionosphere (20,180,151), where the three elements in the parenthesis are the numbers of instances in initial set, active learning set, and testing set respectively. As the same conclusion can be drawn for all the three data sets, only the results obtained on Pima data set are presented and analyzed below. The results on the other two data sets are available online 1 .

It is deemed that wrong labels are harmful to active learning. The average numbers of wrong labels received by the 3 existing algorithms in ALC and ALCU scenarios are depicted in Fig. 1(a). It can be seen that all the methods in the ALCU scenario indeed have far fewer wrong labels, which demonstrates the benefit to provide annotators the unsure option.

1 http://staff.ustc.edu.cn/ ketang/codes/IJCAI15ALCU.html

Fig. 1(b) plots the average accuracies of all the competing methods. It can be observed that ALCU-SVM outperformed the other methods in terms of the accuracy of the obtained classifier. This implies that the active learning procedure can be enhanced if the unsure feedback is exploited properly. In addition, querying labels of instances usually induces some sort of cost. Thus, an unsure feedback is in general unfavorable. In Fig. 1(c), the average cumulative numbers of unsure feedbacks received by ALCU-SVM and the other 3 methods in ALCU scenario are plotted. It can be observed that, by properly exploiting the unsure feedbacks, ALCU-SVM also managed to induce much fewer unsure feedbacks than the compared algorithms.

Suppose ALCU-SVM is run m iterations and there are N unlabeled instances in the beginning. In i-th iteration, the simplest way to optimize Eq. (9) is to calculate the value for all N - i + 1 unlabeled instances at first and then choose the instance which minimizes Eq. (9). Moreover, getting the value of Ω(x) involves T logical operations (see Eq. (3)). Hence, the complexity of ALCU-SVM is ∑mi=1 (N-i+1)T, i.e. O(mNT). Fig. 2 plots the average running time of all the seven competing methods on the three data sets. It can be seen that ALCU-SVM is one of the least time-consuming methods. Comparing all the methods in ALC scenario with the corresponding methods in the ALCU scenario, the methods in the latter situation are in general less costly. For example, ALC+R needs much less time than ALC. One possible reason may be that the number of noise labels which slow down the convergence of algorithm is largely decreased by the unsure option.

5.2 Experiments on Real Data

In addition to preliminary empirical studies on UCI data, experiments have also been carried out in a real-world ALCU scenario. In this experiment, the UDI-TwitterCrawlAug2012-Tweets 2 [Li et al., 2012], which include 50 million tweets posted mainly between 2008 and 2011, were employed. Concretely, the hashtags of tweets were used as their "labels". The tweets with such hashtags as job, music, royal wedding (Prince William and Kate Middleton) or Osama Bin Laden being killed were used in our experiment. In total 1000 tweets belonging to these 4 topics were randomly chosen as the training data, and another 1000 tweets were chosen as the testing data. The text body of each tweet was pre-processed and transferred into a TF-IDF vector by the natural language toolkit (NLTK 3 ), and it ended uabelson-et-al:schemeabelsonet-al:schemep with a numerical feature matrix with 295 features. As binary-class problems are considered in this work, the tweets belonging to the "job" topic were treated as positive class, and the tweets under the other 3 topics were treated as negative class.

2 https://wiki.cites.illinois.edu/wiki/display/forward/Dataset-

UDI-TwitterCrawl-Aug2012

Given the above-described training and testing data, 5 real annotators (i.e., human) from our university were invited to assist in our experiment. Specifically, all of them were first asked to label 200 training tweets for initial training. Then, labels of the other 800 instances were queried from the annotators during the active learning procedure. For each tweet, an annotator could either label it as one of the 4 topics or reply "I'm unsure" to the query.

The experiment was conducted in a real situation with an unsure option, i.e., PMActive+R, IETresh+R, ALC+R and ALCU-SVM were compared. The average accuracies achieved by the competing methods are plotted in Fig. 3(a). It can be seen that ALCU-SVM dominates all of the other methods. Considering that all the competing methods ran in the same situation with the unsure option, it verifies that it is worth investigating a specially tailored approach for ALCU rather than applying some existing ALC directly. The average numbers of unsure feedbacks are plotted in Fig. 3(b), which also shows the advantage of ALCU-SVM in this aspect. The advantages of ALCU-SVM observed in Fig. 3(b) is not as significant as that observed in Fig. 1(b). One possible reason is that the ratio of unsure feedback in this experiment is much smaller than that in the experiments on UCI datasets. For example, it can be seen later in Table 1, annotators 2, 3 and 5 replied with unsure feedbacks in about 200 out of 1000 instances, while about 4/5 of replies were unsure feedbacks in the experiments on UCI datasets.

To further assess the necessity of ALCU in real-world scenarios, the 5 annotators were also requested to provide labels for all the 1000 training instances. The numbers of instances that each annotator provided correct/wrong labels and unsure feedbacks are summarized in Table 1, which shows that all annotators are unsure about the labels of a substantial number of instances, indicating that without an unsure option, a large number of poor quality labels could be introduced. Moreover, Table 2 presents the pair-wise similarities between annotators' labeling behaviors. Each element in the table represents the ratio of instances in which the two corresponding annotators provided the same labels. The observed small similarity values indicate that the 5 human annotators involved in the experiment behaved rather differently. This observation justified that for a real-world problem, it would be important to model the reliability of each annotator since each may show diverse labeling behaviors.

3 http://www.nltk.org

5.3 Influence of ReliabilityModel

A few hyper-parameters, i.e., the kernel function and its parameters, need to be predefined for ALCU-SVM to learn the reliability models. In previous experiments, only the RBF kernel was employed. To assess the influence of this issue on ALCU-SVM, further experiments have been conducted on the real-world data set using 8 different settings of kernel functions and hyper-parameters:

Fig. 3(c) plots the results of all these 8 kernels. It can be observed that both the kernel type and hyper-parameters affect the accuracy of ALCU-SVM. However, the kernel type appears to have much more significant influence than the hyper-parameters. Specifically, the polynomial kernel led to significantly lower performance than the other two kernels, while the RBF and linear kernel led to comparable accuracy. Therefore, a rule-of-thumb in practice would be to first employ both the linear and RBF kernels for a few iterations and then test the obtained reliability model against newly obtained responses from annotators. After that, the kernel that better fit the distribution of the annotators' expertise can be chosen.

6 Conclusion and Discussion

In this paper, a variant of active learning from crowds, namely active learning from crowds with unsure option, is put forward and investigated. An algorithm called ALCU-SVM is proposed for this new problem. Empirical studies on both simulated data and real-world crowdsourcing data imply that providing annotators the unsure option would benefit ALC significantly. Further, although some existing ALC methods are directly applicable to ALCU, they were clearly outperformed by the proposed ALCU-SVM in the empirical studies. This suggests that exploiting the unsure feedbacks to model the expertise (e.g., in forms of reliability) of annotators, as ALCU-SVM does, is crucial for tackling ALCU. Hence, it is worth investigating specially tailored approaches to this new learning problem.

There are a few directions for further improving ALCUSVM. First, ALCU-SVM solely relies on the feedbacks of annotators to decide whether an annotator will be trusted in a given instance. This setting may suffer in case annotators are falsely confident. A possible solution would be to employ two models to represent annotators' expertise. That is, the reliability model used in ALCU-SVM, which reflects the confidence of annotators, and a probabilistic model that represents the probability that an annotator can correctly label an instance. The latter can be used for filtering possibly wrong labels provided by a falsely confident annotator. On the other hand, making ALCU-SVM more robust to wrong labels would be another direction to resolve this problem. Second, ALCU-SVM takes a binary view of the annotators' reliability, e.g., Ω is defined as the disjunction over all annotators. Other forms of functions can be employed for Ω so as to avoid the instance selection being biased to instances in which at least one annotator is deemed to be sufficiently reliable. Potential approaches could be using a soft-max function for Ω or to seek more advanced techniques, e.g., [Auer et al., 2002] [Liu et al., 2009], to guarantee that a reliable annotator will be found if any exists. Third, theoretical properties of ALCU-SVM are also worthy of further investigations to fully understand the advantages and disadvantages of ALCUSVM.

In additional to improving ALCU-SVM, it would also be interesting (and maybe even more important) to explore alternative frameworks to tackle ALCU. A thread for thoughts is to view the problem from the perspective of optimal annotator selection, and the family of Dynamic Classifier Selection (DCS) methods [Ho et al., 1994] [Woods et al., 1996], could be used. Annotator selection may also be explicitly formulated as a bandit problem, where the reward of choosing an annotator is high/low if the annotator gives a label/says "unsure". In this sense, some bandit algorithms [Gittins et al., 2011] might be applicable to ALCU after appropriate modifications. Last but not least, if it is possible to recruit a large number of human annotators, it will be very interesting to study the scalability of the ALCU-SVM (and any other new algorithm proposed for ALCU) with respect to number of annotators on a real crowdsourcing platform.

7 Acknowledgement

This work was supported in part by the 973 Program of China under Grants 2011CB707006 and 2014CB340501, the National Natural Science Foundation of China under Grants 61175065, 61329302, 61333014 and 61321491, the Program for New Century Excellent Talents in University under Grant NCET-12-0512, and the European Union Seventh Framework Programme under Grant 247619.