DEIM Forum 2019 A5-2

Find Target Data Fast! A Method and Its Behavior of Target Data
Collection using Online Machine Learning
Ruide LI† , Yoko YAMAKATA†† , and Keishi TAJIMA†† Kyoto University36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501 Japan†† The University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656 Japan
E-mail: †li.ruide@dl.soc.i.kyoto-u.ac.jp, ††yamakata@hal.t.u-tokyo.ac.jp, †††tajima@i.kyoto-u.ac.jp
Abstract In this paper, we discuss a problem of collecting data of a target class from a fixed pool of unlabeleddataset as fast as possible. Our method consists of two phases. In the first phase, we repeatedly choose a candidate
data and query human annotators for the label. During that, we use the obtained labeled data also for training aclassifier, and use it to choose the next candidate. When the classifier has been trained enough, we switch to thesecond phase. We apply the obtained classifier to the remaining data to collect target data. In the first phase, wewant to choose candidates which are most likely to be target data in order to collect them fast. For the second phase,
however, we want to query a label for a data which is likely to improve the classifier. We have a dilemma between
these two. Another issue is diﬃculty of the estimation of the accuracy of the obtained classifier. The labeled data
set obtained in the first phase is biased towards the target class, and by using that we need to estimate the accuracyof the current classifier for the remaining data which is biased in the opposite way. In this paper, we explain thediﬃculty of this new problem by using our experimental results, and also show the behavior of our simple methodof ballancing the dilemma explained above.
Key words active learning, annotation, crowdsourcing, learn-to-enumerate

1 Introduction

problem in several ways. First, our goal is to collect target
data as fast as possible (i.e., with as few queries for non-In the pool-based active learning problem [3], we usuallytarget data). In the first phase, therefore, we want to choose

have a pool of unlabeled data, and the learner pick up aa candidate which is most likely to be of the target classsample from the pool for human annotation, referring to afrom the remaining unlabelled data. The performance of thefunction which gives the priority of every sample. In thisobtained classifier is not important as long as we can collectpaper, we discuss a slightly diﬀerent problem: a problem oftarget data fast. Moreover, the classification boundary of thecollecting data of a target class from a fixed pool of unla-classifier is not important in our problem as long as the single

beled dataset as fast as possible by using machine learning

best candidate chosen by the classifier in each step is always a

but without any prelabeled training data. We propose atarget data. On the other hand, in the ordinary active learn-

method which consists of two phases. In the first phase, weing, we want to achieve high accuracy of the classifier whilechoose a candidate data one by one, and repeatedly query

minimizing the total number of both target and non-target

human annotators for the label. If it is labeled as the target

queries. In the ordinary active learning, therefore, uncer-

class, we store it as a target data. During the first phase,tainty sampling [4], in which samples with lower confidence

we use the obtained labeled data also for train a classifier,will be annotated earlier, is a well-known approach. Existing

and use the classifier to choose the next candidate. When

research has shown that the opposite approach, which gives

we determine that the classifier has been trained enough, we

higher priority to samples with higher confidence, is a better

switch to the second phase: we switch from human annota-

strategy [1] if we simply want to collect target data as fasttion to prediction by the classifier. We apply the obtained

as possible.

classifier to the remaining unlabelled data and collect data
predicted as the target class.
This problem is diﬀerent from the ordinary active learning

For the second phase, however, we also want to achieve
high accuracy of the classifier.

As a result, we have adilemma between querying a label for a data which is likely

to be a target data and querying for a data which is likely

what we can conclude from the experiments and further is-

to improve the classifier. Another issue in this problem issues to the mentioned problems.

diﬃculty of the estimation of the accuracy of the obtainedclassifier on the remaining data. Because we choose data

2 Related Work

likely to be a target data in the first phase, our labeled data

Two most important problems related to our problem isset obtained in the first phase is biased towards the target

active learning and learning-to-enumerate. In this section,

class. On the contrary, the remaining data is biased towards

we breifly explain existing research on these two problems.

the non-target classes. In order to know on what point we

2 1 Active Learning [?]can trust the classifier and switch from human annotation to

As the boosting development of supervised machine learn-

the obtained classifier, we need to estimate the accuracy ofing, models are becoming more and more hungry for labeled

the current classifier on the remaining biased data only bytraining data. As we all know, human annotation may costusing the currently available labeled data, which is biased ina huge amount of money and time. To handle this problem,the opposite way.

many active learning algorithms have been developed. In

We call this problem target-extraction-learning problem.

the survey paper by Settles [?], the author summarized three

An example scenario of a potential application is as follows.

typical categories of active learning algorithm: pool-based

Suppose we have a natural disaster, and we want to collect(the learner picks up a sample from the pool of unlabeled

tweets on Twitter asking for rescue as fast as possible. Be-

data by means of a querying function), stream-based (thecause we cannot examine all the tweets, we want to train alearner tells whether to do annotation in a stream of unla-classifier, but the characteristics of tweets asking rescue isbeled data) and membership queries (the learner generates

diﬀerent from disaster to disaster, and we do not have any

data from the feature space of unlabeled data).

labeled data sets or pretrained classifiers. We need to label

The problem in this research is close to the pool-based

the data first, but it is waste of time to randomly sample

active learning, especially in the aspect of a fixed pool oftweets from Twitter and ask the annotators to label them.

unlabeled data which do not change during the annotation

We should first examine tweets that are the most likely tophase. On the other hand, typical active learning only focus

be relevant, and if it is asking for rescue, we should send theon the performance of the model, while in our research, we

rescue as soon as possible. We repeat it, and after obtain-

try to ballance the performance of the model which is useding enough labeled data, we should switch to the predictionin the second phase, and quick collection of target data inby the classifier because human judgement takes longer time

the first phse.

than the classifier for a huge number of tweets. Another

Another diﬀerence between the ordinary problem setting

example scinario is to find high risk patients among a big

in active learning and our problem setting is the assumption

group of people without existing labeled data to train a pre-on the properties of the remaining data. In the ordinary

dictive model, and under the constraint of a limited number

active learning, while we assume a closed data set when weof checkups we can perform [2].

select samples to label, we assume an open data set whenIn this paper, we introduce this new problem, and explain

we measure the performance of the obtained model. We as-

the diﬃculty of the problem by using our experimental re-sume that the selection of samples to label do not aﬀect thesults. We simulate the scinario with SVM implementation

properties of the remaining data. On the other hand, in ouron document classification tasks and analyze the behavior

problem, we assume that the selection of samples in prefer-of the classifier obtained at each step. We also discuss how

ence to the target data results in the remaining data biased

to control the dilemma mentioned before, suggest a simple

towards the non-target data.

method of ballancing the dilemma explained above, and show

2 2 Learning to Enumerate [1]its behavior in our simulation.

Sometimes we want to find data satisfying some partic-

The rmainder of the paper is organized as follows. In theular conditions and our goal is to find such data from thefollowing section, we first discuss several related literatures

whole dataset as fast as possible. One scenario might be toabout active learning and also about learning-to-enumerate

find tweets asking for rescue after some natural disaster, ex

problem, which is a problem similar to our target-extraction-

explained before.

learning problem. We then define the details of our problem

In such a case, if we have an extensive labeled dataset toin Section 3, and propose an approach trying to provide pos-train our model in advance, the best strategy would be tosible solution to the problem in Section 4. In the experimenttrain a model with it and to solely rely on the predictions

section, we simulate our framework on both balanced andby the model to identify all data of the target class. How-

unbalanced data, and report the results. Finally, we discuss

ever, when we do not have any labeled data in adnvance, oneapproach is to construct a training set while examining datathat are most likely to be the target data one by one, and use
the current trained model to choose the next candidate. In
other words, we can continue the first phase of our method
until we find all the target data. In this setting, we have adilemma between querying a label for a data which is likely
to be a target data and querying for a data which is likely to
improve the classifier, as explained before. Jörger et al. [1]call this problem the learning-to-enumerate problem.
This is a typical exploitation vs.

exploration dilemmathat has been studied extensively in reinforcement learn-

Figure 1: Flow Chart of Simulation Process

ing. Jörger et al. [1] proposed a simple ϵ-greedy like strategy, and tested it with diﬀerent base learners and heuristic

to querying function in active learning).

functions, on 19 small and medium-sized public datasets accessible through the UCI Machine Learning Repository. The•

We usually use all labeled data to train the model, but

results of their experiments shows that the best result wasin this framework, we split a small part of labeled poolachieved by an exploitation only (ϵ = 0) strategy. Here theas “current test set”, to evaluate the model at each step.

exploitation means the model picks up a data that is theMetrics, such as precision and recall, measured on thismost likely to be of the target class, i.e., the data for whichcurrent test set are available in real application.

the model has the highest confidence.

•

However, there is a diﬀerence in our research from their

In comparison, we provide a test set with label to evaluate the model without bias, which we call it “oracle test

learning-to-enumerate problem. Their purpose is to find allset”. Various metrics mesured on the oracle test set are

target data by human labeling, while in our research, weonly available in this simulation for research purpose,want to switch to the prediction by the model at certain

and cannot be known in real application.

point, when we can be sure that the model is well trained.

3 Problem Definition
In target-extraction-learning problem, as the literal meaning, we want to extract target data faster, and also try tolearn a model. We presume that there is a fixed pool of unlabeled data, and the final purpose is to find target samples using as few non-target annotation as possible. To achieve thisgoal, we consider two-phase method. At the early phase, thesystem choose data that are likely to be target data, queryfor human annotation, and train a model with labeled data.
At the later phase, we switch from human annotation to the•

Use the labeled data pool to train a machine learningmodel, and use the model to update the querying function if needed.
3 1 Evaluation
In order to see every detail in the annotation simulation,

we evaluate several metrics. Note that there are metrics that
we can obtain in real application, and metrics that we cannot
obtain in real application. In the list below, for the metrics
that can be known in real application, the corresponding
checkbox is checked. The others are used only for the evaluation in this simulation.

prediction by the model, and provide a ranking of data basedon the likelihood of being a target data.
At the early phase, it is reasonable just to make use of
the learning-to-enumerate algorithm, but the point is that,the labeled data, which is used to train a machine learningmodel, is biased towards target samples, so we can not estimate how the model will perform on the unlabeled data. In
order to know the details, we build a framework to simulate
this annotation process.
A flow chart of the simulation process is shown in Figure 1.
The framework works as follows:•

Iteratively pick up a sample from the unlabeled datapool at each step according to a certain policy (similar□ Accuracy, recall, precision and f1-score on oracle test set.

3 Accuracy, recall, precision and f1-score on current test□set.
□ Positive coverage: the ratio of retrieved target samples
to all target samples.

3 Recent labeled target proportion: the proportion of re□trieved target samples in recent K labeled samples.
□ R-precision on unlabeled data.
We need an explanation on the last one in the list above,i.e., R-precision. We want the model to be able to give atarget likelihood ranking of the remaining unlabeled data.

the accuracy of the obtained model on the remaining data

To measure that ability of the model, we use R-precision.

due to the bias in the training data set and the remaining

R-precision on the remaining data is defined as follows:data set. To estimate the performance of obtained model, we

R-precision =AR

observe the curves of metrics on oracle test set and current
test set, and have found a regular phenomena of “current

where R is the number of target data in the remaining data,

precision pit”, which is able to indicate the relation between

and A is the number of target data ranked within top-R

oracle and current test set. We will explain the details in theby the model. However, if we use the ordinary R-precisionnext section reporting our experimental results.

to measure the performance of the model on the remain-

5 Experiments

ing data, the comparison can be unfair. For example, if wehave been very successful in collecting target data and only

In experiments, we run simulations both on balanced dataa small number of diﬃcult-to-find samples are left in the re-and unbalanced data, and compared our methods with ran-maining data, it is diﬃcult to achieve high R-precision on

dom sampling. The data sets we used in our experiments arethat remaining data. On the contrary, if we have been un-

as follows:

successful and many target data is still left in the remaining
data, it is easier to achieve high R-precision on the remain-•

sages, 50% target data (spam).

ing data. To avoid this unfairness, we add the number ofalready-found target samples to both numerator and dominator of R-precision. That is, we use R-precision defined byDataset 1: Text message spam classification, 1500 mes-•

Dataset 2: Moive review sentiment classification, 4000
reviews, 20% target data (positive reviews).

the formula below:
R-precision =

A+F
R+F

where F is the number of already-found target data.

For machine learning model, we chose Support Vector Machine (SVM). We have also compared Long Short Term Memory (LSTM) and Random Forest (RF). The results showed

Metrics on oracle test set are used to give the “real” per-that the linear SVM and LSTM give the similar performance,

formance of obtained model in this simulation, and metrics

while SVM is far more eﬃcient to train. RF gives poor per-on current test set are used to estimate the performance offormance without hyper-parameter tuning, but we cannot

the model on the remaining data in real applications (sincetune hyper-parameters in real application, so we finally choseoracle test set is not available there). At the early phase,linear SVM with all default hyper-parameters in scikit-learn

we evaluate the performance of finding target data by posi-

library [5]. In addition, we use class weight in training, astive coverage. At the later phase, we use R-precision defined

the data could be unbalanced.

above to evaluate the target likelihood ranking of unlabeleddata predicted by the obtained model.

4 Proposed Approaches

On oracle test set, we use 5-fold cross-validation in orderto obtain stable results. On current test set, we do not use
cross-validation due to eﬃciency reason.
Figure 2 to 11 show the metrics observed in our simu-

In target-extraction-learning, we have a dilemma that it

lations. The horizontal axis represents the size of the la-is hard to let these two purposes (improving the model andbeled pool, also can be considered as “steps”. We use thefinding target data fast) be fulfilled at the same time. The

learning-to-enumerate algorithm [1] as pure target-extraction

reason is that if we find target data faster, the data used tobaseline, and also use the method that combine it with 10%

train the model becomes biased towards target data, and as

random sampling warm start. At each step, random sam-a result, the performance of the model will be deteriorated

pling picks up a sample randomly, while target-extraction

compared with the training with random sampling.

picks up a sample which has the largest distance to the deci-

To handle this dilemma, we propose a compromised ap-

sion boundary on the target side, in contrast to uncertainty

proach that uses a “warm” start with random sampling tosampling, which picks up a sample closest to the boundary.

balance the trade-oﬀ. We use random sampling only at the

5 1 Results on Dataset 1very beginning of the first phase (for example, 1/10 of the

In Figure 4 showing positive coverage, we can see thatwhole unlabeled pool), and switch to target-extraction aftertarget-extraction works expectedly. On the other hand, inthat. The point is that, we can make use of random sam-Figure 2, since both accuracy and f1-score on oracle test set

pling phase to estimate the distribution of target data in theshow good results at the final step, we can assert that the

unlabeled pool. We call this “Random Starter Method”.

model is well trained. However, random sampling gives a

Another issue in our problem is the diﬃculty of estimatingmuch better learning speed than target-extraction, since the

1.0

0.8

0.8

0.6

0.6

acc

recall

1.0

0.4
0.2

0

200

400

Random Sampling
Target Extraction
Random Starter

0.0
600

labeled size

800

1000

1200

0

1.0

1.0

0.8

0.8

0.6

0.6

200

400

600

800

1000

1200

600

800

1000

1200

labeled size

f1

precision

0.2

Random Sampling
Target Extraction
Random Starter

0.0

0.4

0.4

0.4

0.2

0.2

Random Sampling
Target Extraction
Random Starter

0.0
0

200

400

Random Sampling
Target Extraction
Random Starter

0.0
600

labeled size

800

1000

1200

0

200

400

labeled size

Figure 2: Metrics on Oracle Test Setlabeled data does not have any bias. On the other hand,sampling, which indicates that the model trained by target-

in target-extraction, the model does not learn well at theextraction algorithm also provides a better ranking. This

early phase, since the labeled data used to train is biased to-satisfies our second purpose of providing a good target likeli-

wards target samples. As the model has found most of target

hood ranking, so that we can switch from human annotation

samples (aroud the step 600), non-target samples begin to in-to the prediction by the model.

crease in the labeled data, and the model starts to learn the

The random starter method has shown a compromised

classification task properly. In the precision on the current

result. Althought it do not extract target data as fast as

test set (Figure 3), there is an obvious pit around the step

pure target-extraction method, it was able to provide a much

700. We call it “current precision pit”. The reason of thishigher R-precision.

pit is as follows. At the early phase, the training data set is

Figure 6, which shows the recent labeled target propor-

biased toward the target data, and the model does not welltion, indicates the proportion of target samples in the recent

trained. However, the current test set is also biased toward

ten labeled data. Random sampling shows a relatively sta-

the target data, so the model shows good performance on theble curve as expected, while target-extraction picks muchcurrent test set, and we cannot know that the model is not

more target samples at early steps, but the proportion goeswell-trained only from the current test set metrics. At the

down at later steps when less target samples remain in un-

later phase, as the current test set gradually becomes bal-labeled data. Since this is a metric which can be known in

anced, these metrics begin to go down, but when the model

real application, it provide a possibility to estimate the tar-begins to learn the classification task properly, the metrics

get proportion of unlabeled data. Also, in random startergo up again.

method, it provided a priori of the whole unlabeled pool as

In Figure 5 showing R-precision, we can see that the model

expected.

shows poor R-precision compared with random sampling in

5 2 Results on Dataset 2

early steps, when the model is not well trained. On the con-Figure 7 to 11 show the result for the second data set. In

trary, when the model starts to perform well around step

Figure 8, although the current precision pit came earlier and

700, R-precision of target-extraction surpass that of random

lasted for longer than in the previous experiment with the

1.0

0.8

0.8

current_recall

current_acc

1.0

0.6
0.4
0.2

200

400

labeled size

800

1000

1200

0

1.0

1.0

0.8

0.8

0.6

0.6

0.4
0.2

0

200

400

200

400

600

labeled sizelabeled size

800

1000

1200

1000

1200

Random Sampling
Target Extraction
Random Starter

0.0
600

800

0.4
0.2

Random Sampling
Target Extraction
Random Starter

0.0

Random Sampling
Target Extraction
Random Starter

0.0
600

current_f1

current_precision

0

0.4
0.2

Random Sampling
Target Extraction
Random Starter

0.0

0.6

0

200

400

600

labeled size

800

1000

1200

Figure 3: Metrics on Current Test Set

1.0
0.8

0.8

0.6

r_precision

pos_coverage

1.0

Random Sampling
Target Extraction
Random Starter

0.4
0.2

0.6
0.4
0.2

0.0

Random Sampling
Target Extraction
Random Starter

0.0
0

200

400

600

labeled size

800

1000

1200

0

200

400

600

labeled size

800

1000

1200

Figure 4: Positive Coverage

Figure 5: R-Precisionbalanced dataset, f1-scores on oracle test set and current test

random sampling. In this way, target-extraction method not

set still converged, which means we can use current perfor-

only fetched target data faster, but contributed to model

mance to estimate oracle performance after the pit appears.

performance as well for this data set where the target data

The f1-score on oracle test set of Dataset 1 (Figure 7)

is minority. Hence, we can expect that if the target datashows that the model with target-extraction method learned

is majority in the unlabeled pool, the model will learn on amuch slower than with random sampling, due to the bias to-even more unbalanced dataset, and the performance will gowards target data. However, in unbalanced dataset, model

worse than random sampling.

with target-extraction method learned much faster than ran-

Figure 10 shows that random sampling and target-

dom sampling. This is because the model tried to fetch target

extraction on this unbalanced Dataset 2 gave the results

data, which is minority in unlabeled data pool, so that the

opposite to those on balanced Dataset 1. It is easy to under-model was able to learn on a more balanced dataset thanstand because a well-learned model should provide a betterReferences
1.0

Random Sampling
Target Extraction
Random Starterrecent_prop

0.8
0.6
0.4
0.2
0.0
0

200

400

600

labeled size

800

1000

1200

Figure 6: Recent Target Proporttion

ranking of target likelihood. We can also conclude that the
random starter method gives a compromised performance of
R-precision on both balanced and unbalanced datasets.

6 Conclusion
We defined a new problem called target-extractionlearning. The purpose is to extract target data faster, andwe propose a two-phase approach. At the early phase, thesystem queries samples most likely to be a target data forannotation, and at the later phase, we switch from humanannotation to the prediction by the model. We also analyze the diﬃculty in the model performance estimation due
to the bias towards target data in the training data set. To
handle this diﬃculty, we use a phenomena we found in our
experiiments. We can observe a “current precision pit” inprecision curve on current test set, and we are able to estimate the model performance since the results on current test
set and oracle test set begin to converge after striding overthe pit. Finally, to handle the dilemma between model performance and target extraction, we proposed a compromised
approach with a warm start of random sampling, and it gives
compromised results, both on balanced and unbalanced data.
However, the “current precision pit” can only be observed
after the model is well-trained. If the model cannot be welltrained on a certain dataset, the pit will not appear. We stillneed a way to estimate the performance even in such cases.
In addition, estimation using the experimental phenomena
is still ambiguous, and it is better to give more statisticalevidence, such as the expectation and variance to the performance of current model.

7 Acknowledgment
This work was supported by JST CREST (JPMJCR16E3)，
and JSPS KAKENHI Grant Numbers 18H03245, 16K12430,
and 18K11425.

[1] Patrick Jörger, Yukino Baba, and Hisashi Kashima. Learning to enumerate. Artificial Neural Networks and Machine
Learning, 2016.
[2] Y. Baba et al. Predictive approaches for low-cost preventive
medicine program in developing countries. Proc. of KDD,
pages 1681–1690, 2015.
[3] Anita Krishnakumar. Active learning literature survey.
2007.
[4] David D. Lewis and William A. Gale. A sequential algorithm for training text classifiers. Proc. of SIGIR, 1994.
[5] F. Pedregosa et al. Scikit-learn: Machine learning in python.
Journal of Machine Learning Research, 12:2825–2830, 2011.

1.0

0.8

0.8

0.6

0.6

acc

recall

1.0

0.4
0.2

500

1000

0.0
1500

2000

labeled size

2500

3000

0

1.0

1.0

0.8

0.8

0.6

0.6

500

1000

1500

2000

labeled size

2500

3000

Random Sampling
Target Extration
Random Starter

f1

precision

0

0.4
0.2

Random Sampling
Target Extration
Random Starter

0.0

Random Sampling
Target Extration
Random Starter

0.4

0.4

0.2

0.2

Random Sampling
Target Extration
Random Starter

0.0
0

500

1000

1500

2000

labeled size

2500

0.0

3000

0

500

1000

1500

2000

labeled size

2500

3000

1.0

1.0

0.8

0.8

current_recall

current_acc

Figure 7: Metrics on Oracle Test Set

0.6
0.4
0.2

500

1000

0.4

0.0
1500

2000

labeled size

2500

3000

0

1.0

1.0

0.8

0.8

0.6

0.6

current_f1

current_precision

0

0.6

0.2

Random Sampling
Target Extration
Random Starter

0.0

0.4
0.2

Random Sampling
Target Extration
Random Starter

0.0
0

500

1000

Random Sampling
Target Extration
Random Starter

1500

2000

labeled size

2500

3000

500

1000

1500

2000

labeled size

2500

3000

Random Sampling
Target Extration
Random Starter

0.4
0.2
0.0
0

500

1000

1500

2000

labeled size

Figure 8: Metrics on Current Test Set

2500

3000

1.0

pos_coverage

0.8
0.6
0.4
0.2

Random Sampling
Target Extration
Random Starter

0.0
0

500

1000

1500

2000

labeled size

2500

3000

Figure 9: Positive Coverage

1.0

r_precision

0.8
0.6
0.4
0.2

Random Sampling
Target Extration
Random Starter

0.0
0

500

1000

1500

2000

labeled size

2500

3000

Figure 10: R-Precision

1.0

Random Sampling
Target Extration
Random Starterrecent_prop

0.8
0.6
0.4
0.2
0.0
0

500

1000

1500

2000

labeled size

2500

3000

Figure 11: Recent Target Proporttion