Given a classi er trained on relatively few training examples, active learning (AL) consists in ranking a set of unlabeled examples in terms of how informative they would be, if manually labeled, for retraining a (hopefully) better classi er. An important text learning task in which AL is potentially useful is information extraction (IE), namely, the task of identifying within a text the expressions that instantiate a given concept. We contend that, unlike in other text learning tasks, IE is unique in that it does not make sense to rank individual items (i.e., word occurrences) for annotation, and that the minimal unit of text that is presented to the annotator should be an entire sentence. In this paper we propose a range of active learning strategies for IE that are based on ranking individual sentences, and experimentally compare them on a standard dataset for named entity extraction.
In many applicative contexts involving supervised learning, labeled data may be scarce or expensive to obtain, while unlabeled data, even sampled from the same distribution, may abound. In such situations it may be useful to employ an algorithm that ranks the unlabeled examples and asks a human annotator to label a few of them, starting from the top-ranked ones, so as to provide additional highly informative training data. The task of this algorithm is thus to rank the unlabeled examples in terms of how informative they would be, once labeled, for the supervised learning task. The discipline that studies these algorithms is called (pool-based) active learning (aka selective sampling ). This paper focuses on the application of active learning to information extraction (IE), the task of annotating sequences of one or more words (aka tokens) in a text by means of tags representing concepts of interest. The hypothetically perfect IE system is thus the one for which, for each tag in the Corresponding author tagset of interest, the predicted sequences of tokens coincide with the true sequences.
In text classi cation and other text learning tasks di erent from IE, the units of ranking and the units of annotation are the same; e.g., in text classi cation, it is the texts themselves that are ranked, and it is the texts themselves that are then annotated in their entirety by the human annotator. IE is peculiar from this standpoint since, while the units of annotation are the tokens, it does not make sense to rank individual tokens: if this were to happen, an annotator would be presented with \tokens in context" (i.e., a token in the xed-size window of text in which the token occurs) and asked to annotate the token, with the consequence that she might be asked to read the same context several times, for annotating neighbouring tokens.
In this paper we take the view that the optimal unit of
ranking is the sentence. This means that all the sentences
of the automatically annotated texts are going to be ranked
and presented to the annotator, who will then annotate all
the tokens of a few sentences, starting from the top-ranked
ones. This is di erent from several other works in the eld
[
We deem the sentence to be the optimal unit of ranking for additional reasons:
An entire sentence o ers more context for actually
interpreting the tokens and the sequences within it than
the xed-size window often used in the literature. This
is especially important in complex IE tasks such as
opinion extraction (see e.g., [
Di erent sentences never overlap, while di erent xedlength windows may do. The sentence-based approach results in smaller annotation e ort, since the same token is never examined twice by the annotator.
From a semantic point of view, sentences are fairly self-contained units. This means that using portions of text larger than sentences (e.g., paragraphs) as ranking units is unnecessary, also given that it is hardly the case that an annotation crosses the boundary between two consecutive sentences. Conversely, with a xedsize window centered around a predicted sequence, another true sequence may cross the boundary between the window and its neighbouring text.
In the past, typical strategies adopted in AL for generic
learning tasks have relied on ranking objects based either
on the classi cation score attributed by the classi er to the
object (relevance sampling ), or on the con dence score with
which the classi er has classi ed it (uncertainty sampling )
[
The main contribution of this paper consists in proposing several alternative strategies for combining the token- and tag-speci c scores into a sentence-speci c score, and comparing these strategies experimentally.
We remark that this paper does not deal with active
learning algorithms for speci c supervised learning devices (such
as e.g., [
The rest of the paper is organized as follows. Our strategies for performing AL in IE are described in Section 2. In Section 3 we move to describing our experiments and the experimental protocol we have followed. We conclude in Section 4 by pointing out avenues for future work.
This paper focuses on the application of active learning to (single-tag) information extraction (STIE, or simply IE). Let a text T consist of a sequence T = ft1 s1 : : : sn 1 tng of tokens (i.e., word occurrences) and separators (i.e., sequences of blanks and punctuation symbols), where \ " means \precedes in the text". Let C = fc1; : : : ; cmg be a prede ned set of tags (aka labels, or classes), and let c; 62 C be a special tag (to be read as \no tag"). We de ne (single-tag) information extraction as the task of estimating an unknown target function : T ! C [ fc;g that speci es the true tag in C [fc;g attached to each token ti 2 T and to each separator si 2 T . The result ^ : T ! C [ fc;g of this estimation is called the tagger (or wrapper, or classi er )1. A further property of both and ^ is that they can attribute a tag cj to a separator si only if they also attribute the same tag to both ti 1 and ti.
In most IE tasks it is actually the case that, rather than isolated tokens and separators, sequences of consecutive tokens and separators are annotated with a given tag; e.g., the sequence \George W. Bush", containing three tokens and 1Consistently with most mathematical literature we use the caret symbol (^) to indicate estimation. two separators, might be annotated with the PER (\person name") tag. Such sequences of tokens will here be referred to as annotated sequences (ASs); the expressions true AS and predicted AS will refer to ASs according to and ^ , respectively. Note that the reason for considering separators to be the object of tagging too is that the IE system should correctly identify sequence boundaries. For instance, given the expression \Barack Obama, Hillary Clinton and Joe Biden" the perfect IE system will attribute the PER tag, among others, to the tokens \Barack", \Obama", \Hillary", \Clinton", and to the separators (in this case: blank spaces) between \Barack" and \Obama" and between \Hillary" and \Clinton", but not to the separator \, " between \Obama" and \Hillary". If the IE system does so, this means that it has correctly identi ed the boundaries of the sequences \Barack Obama" and \Hillary Clinton".
Note that \single-tag" IE means that each token (resp.,
separator) has exactly one tag. This is di erent from
multitag IE, in which it is assumed that a given token (resp.,
separator) may have more than one tag (opinion extraction
{ see e.g., [
Our experimental work is focused on comparing a range of active learning strategies for IE that are based on ranking individual sentences. This section describes the strategies and the intuitions supporting them.
In this work we test two alternative learning devices,
support vector machines (SVMs) (see e.g., [
CRFs are a discriminative probabilistic learning method
based on an undirected graph model, and is frequently used
for labeling sequential data, e.g., a sequence of words
composing a text. Given a token t, a CRFs classi er estimates
the likelihood ^ c(t) = P (cjt) for each c 2 C [fc;g and,
similarly to SVMs, the assigned label is the one scoring the
highest ^ c(t) value. CRFs are nowadays considered the
stateof-the-art learning device for information extraction [
The strategies we propose are based on two concepts, label score and tag score. The label score of a token is equal to ls(t) = maxc2C[fc;g ^ c(t), i.e., the maximum condence score that determines the decision taken by the classi er ^ (t). The tag score is instead de ned as ts(t) = maxfc2Cg ^ c(t), i.e., the maximum con dence that the classi er as on considering a token as belonging to a tag, regardless of the con dence with respect to c;. 2.2.1
The following strategies are based on combining the label scores assigned to the tokens in the sentence, following the intuition that the elements on which the classi er has low con dence could be more useful to the learner, so as to gather knowledge on \di cult" cases.
The Min Min Con dence (MMC) strategy assigns to the sentence a value equal to the minimum tag score value among the tokens composing it, i.e.,
M M C(s) = mint2s(ts(t)) Sentence ranking is performed in increasing order of M M C(s) value.
Min Average Con dence (MAC) is a version of MMC that tries instead to be robust to single \extreme" evaluations, averaging the tag scores of all the tokens composing the sentence, i.e.,
M AC(s) = avgt2s(ts(t)) 2.2.2
Symmetrically to the tag-score-based strategies, the labelscore-based strategies follow the somehow di erent intuition that the elements on which the classi er has high con dence could be useful, so that the strong beliefs of the learner are con rmed when correct or corrected when a blatant error is found.
The Max Max Score (MMS) strategy assigns to each sentence a value equal to the highest label score among the tokens composing it, i.e.,
M M S(s) = maxt2s(ls(t)) Sentence ranking is performed in decreasing order of M AS(s).
Similarly to MAC, Max Average Score (MAS) instead averages the label scores of all the tokens composing the sentence, i.e., (1) (2) (3) (4) (5) (7)
The Round Robin Max Score (RRMS) strategy assigns, for each c 2 C, a relevance score to the sentence equal to the maximum score obtained by the tokens contained in it, i.e.,
RRM Sc(s) = maxt2s( ^ c(t)) Then a round robin selection process is performed on the jCj rankings produced.
Similarly to MAS, Round Robin Average Score (RRAS) uses averaging instead of maximization, i.e.,
RRASc(s) = avgt2s( ^ c(t)) (8) (9) The Round Robin Max Tag Ratio (RRMTR) strategy applies instead the MTR strategy considering the various tags separately from each other, so as to avoid favouring the most frequent tags over the most infrequent. 3. 3.1
The dataset we have used for evaluating our strategies is the
CoNLL2003 named entity extraction dataset. The dataset
consists of 1,393 Reuters newswire articles, for a total of
301,418 tokens. The tagset consists of 4 tags (LOC, PER,
ORG, MISC, standing for \location", \person",
\organization", and \miscellaneous", respectively) plus the special tag
O, which tags any token / separator not tagged by any tag
in fLOC, PER, ORG, MISCg. The tokens inside the
corpus are tagged as follows: 10,645 tokens are tagged as LOC,
9,323 as ORG, 10,059 as PER, 5,062 as MISC, while the
remaining 266,329 are tagged as O. We used a version of
the CoNLL corpus already preprocessed with Pianta and
Zanoli's Tagpro system [
For this latter, we have tested two alternative, o -the-shelf packages, i.e., YamCha2 and CRF++3, respectively based on support vector machines and conditional random elds.
We evaluate the results of our experiments using the F1
measure on a token & separator evaluation model [
In this work we adopt the following iterative experimental protocol. The protocol has three integer parameters , , and . Let be a set of natural language sentences partitioned into a training set T r and a test set T e, and let be an active learning strategy:
1. Set an iteration counter t = 0; 2http://www.chasen.org/~taku/software/YamCha/ 3http://crfpp.sourceforge.net/ 2.2.3
The following strategies are instead based on counting the number of tokens that are given a tag di erent from c; by the classi er.
The Max Tag Count (MTC) strategy counts the number of tokens in the sentence that are given a tag di erent from c;, i.e.,
M T C(s) = jft 2 sj ^ (t) 2 Cgj Sentence ranking is performed in decreasing order of M T C(s) value.
Since MTC naturally favours long sentences, we have also tested a strategy (Max Tag Ratio { MTR) that normalizes the values by sentence length, i.e.,
M T R(s) = jft 2 sj ^ (t) 2 Cgj (6) jsj The Medium Tag Ratio (MedTR) strategy instead top-ranks the sentences with a tag ratio closer to the average tag ratio measured on the training set, i.e.,
M edT R(s) =
M T R(s) avgs02T rM T R(s0)
M AS(s) = avgt2s(ls(t)) 2.2.4
While the previous strategies always combine the con dence values returned on the various tag types, the following strategies are based on computing values separately for each tag, then selecting the most informative sentences using a \round robin" selection process across all the tags.
2. Set the current training set T rt to the set of the rst sentences of T r; set the current \unlabeled set" Ut T r=T rt; 3. For t = 1; : : : ; repeat the following steps: (a) Generate a classi er ^ t from the current training set T rt; (b) Evaluate the e ectiveness of ^ t on T e; (c) Classify Ut by means of ^ t; (d) Rank Ut according to strategy , thus generating the ranking (Ut); (e) Let r(Ut; ) be the smallest pre x of (Ut) (i.e., the smallest number of top-ranked elements of (Ut)) that contains at least tokens; set T rt+1
T rt [ r(Ut; ); set Ut+1 Ut=r(Ut; ).
It is important to remark that Step 3b has only the purpose of collecting the results for experimental purposes (i.e., for producing the tables of Section 3.3); since it uses the test set T e, its results should obviously not be (and are not) accessible to the algorithm.
The above protocol simulates the activity of a human annotator who, at the beginning of the process, has available a training set T r0 consisting of manually tagged sentences, and an \unlabeled set" U0 consisting of jT rj untagged sentences. The annotator generates a classi er ^ 0 from T r0, uses it to tag the sentences in U0, asks the active learning agent to rank them, manually labels the top-ranked ones for a total of roughly tokens, generates a new classi er ^ 1 from an augmented training set that comprises T r0 and the newly tagged sentences, and repeats this process times.
In our experiments we have set = 110 (in the CoNLL 2003 dataset this means approximately 2000 tokens), = 20, and = 200; this means that each strategy will be evaluated by testing the accuracy of the classi ers generated from training sets consisting of approximately 2000, 2200, . . . , 5800, 6000 training tokens, for a total 20 experiments per strategy. We think these parameters are realistic, since they simulate a situation in which there are only about 100 manually tagged sentences at the beginning; (this is reasonable, since in many applications in which signi cantly more training data are available, human annotators might not nd it worthwhile to annotate any further); every time the human annotator manually labels 200 unlabeled tokens, he/she wants to retrain the system; (this is reasonable, since he/she wants the operate on a ranking of the unlabeled documents that incorporates as much as possible the feedback he/she has already given to the system;) the human annotator does not want to do any further manual labeling once about 6,000 training tokens are available; (this seems reasonable, since at this point the cost-e ectiveness of the manual e ort has probably decreased signi cantly.) As the baseline strategy for the evaluation of our results we adopt the one that consists in adding further labeled sentences to the training set by picking them at random. This simulates the behaviour of a human annotator that picks unlabeled sentences and labels them in no particular order. 3.3
The main results of our experiments are summarized in Table 1. This table reports, for each individual strategy, the values of F1 and F1M obtained after 20 training sessions resulting from the protocol of Section 3.2, with = 110, = 20, and = 200, using the two di erent learners, SVMs and CRFs.
Quite surprisingly, the only genuine strategy that
outperforms the random baseline is the MAC strategy. The
relative improvement of MAC over RAND ranges from 3.9%
up to 6.3%. This improvement matches our expectations,
given the close relation between the MAC strategy with the
uncertainty sampling [
Surprisingly, all the other strategies perform worse or no better than the random baseline. In order to understand the possible motivations behind these results we have inspected the sentences selected by the various strategies at the various iterations. This inspection allowed us to draw some speci c conclusions on some of the strategies, and a general observation for the entire pool of strategies.
The MTR and RRMTR strategies tend to select very short sentences (two/three words) composed just by named entities. This allows gathering a lot of di erent instances of named entities, but without a context of use, which is important in order to learn how to perform extraction from longer, more articulated sentences.
The MTC strategy selects sentences of variable length, but tends to exceed in selecting sentences full of named entities, thus with a very limited amount of O-tagged tokens.
A common aspect of all the strategies is that, the more similar two sentences are, the more similar are the scores that the various strategies assign them. If the dataset contains a lot of similar sentences, and such sentences obtain high scores, the contribution of relevant information to the training set is limited, because of the redundancy contained in the set of sentences selected.
A comparison between the strategies based on round robin (RRAS, RRMS, RRMTR) against the respective \singlerank" versions (MAS, MMS, MTR) shows that the RRstrategies produce an improvement in the F1M measure, as should be expected when using a class-balancing method as RR.
The comparison of the averaging-based strategies (MAC, MAS, RRAS) against the respective versions based on maximization / minimization (MMC, MMS, RRMS) shows that averaging always perform better than maximization / minimization. This indicates that the smoothing introduced by the averaging helps the strategies to lter out the single \false-relevant" tokens that may appear in otherwise nonrelevant sentences. 4.
We have argued that, in active learning for information extraction, the sentence should be the unit of ranking. We have thus studied several strategies for scoring a given sentence for ranking, based on the classi cation score and the con dence score obtained by each token in the sentence. On the positive side, the experimental results that we have obtained by testing these strategies on a named entity extraction task show one such strategy (Min Average Con dence) to outperfom the others, irrespectively of learning device F1M used (support vector machines or conditional random elds) and evaluation measure (microaveraged or macroaveraged F1) used. On the negative side, the same results show that all the other strategies, that seem based on solid intuitions, tend to be roughly equivalent to a random strategy. In the future we plan to test these strategies further, possibly on IE tasks more di cult than named entity extraction such as opinion extraction.
We thank Emanuele Pianta and Roberto Zanoli for kindly
providing us a version of the CoNLL corpus already
preprocessed with their Tagpro system [