<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Active Search using Meta-Bandits</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>10/01/2020</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10184358</idno>
					<idno type="doi">10.1145/3340531.3417409</idno>
					<title level='j'>The 29th ACM International Conference on Information and Knowledge Management (CIKM'2020)</title>
<idno></idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>Shengli Zhu</author><author>Jakob Coles</author><author>Sihong Xie</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[There are many applications where positive instances are rare but important to identify. For example, in NLP, positive sentences for a given relation are rare in a large corpus. Positive data are more informative for learning in these applications, but before one labels a certain amount of data, it is unknown where to find the rare positives. Since random sampling can lead to significant waste in labeling effort, previous ”active search” methods use a single bandit model to learn about the data distribution (exploration) while sampling from the regions potentially containing more positives (exploitation). Many bandit models are possible and a sub-optimal model reduces labeling efficiency, but the optimal model is unknown before any data are labeled. We propose Meta-AS (Meta Active Search) that uses a meta-bandit to evaluate a set of base bandits and aims to label positive examples efficiently, comparing to the optimal base bandit with hindsight. The meta-bandit estimates the mean and variance of the performance of the base bandits, and selects a base bandit to propose what data to label next for exploration or exploitation. The feedback in the labels updates both the base bandits and the meta-bandit for the next round. Meta-AS can accommodate a diverse set of base bandits to explore assumptions about the dataset, without over-committing to a single model before labeling starts. Experiments on five datasets for relation extraction demonstrate that Meta-AS labels positives more efficiently than the base bandits and other bandit selection strategies.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">INTRODUCTION</head><p>In many applications of classification, a large unlabeled dataset can be collected without much cost (e.g. via Internet crawling), while identifying the rare positive data instances can be labor-intensive. In NLP, relation extraction classifies a pair of words/phrases in a sentence into one of the multiple relations. For example, a model can extract the relation hasSpouse between the occurrences of the two concepts (Barack_Obama, Michelle_Obama) from the text snippets ". . . Barack Obama and his wife Michelle Obama . . . ". Such an occurrence of the pair in a sentence is called a mention or an instance, which needs to be classified as having a specific relation (positive) or not (negative). The current best relation extractors are based on machine learning and need to be trained on a large number of labeled data. And yet humans have to label the data, which is costly. In particular, positive mentions are informative for model training and yet are much more rare and difficult to find. The more prevalent negative mentions can be obtained less expensively by randomly sampling pairs of arbitrary words/phrases from any sentences.</p><p>To learn a relation extractor on a new corpus, one starts with an unlabeled dataset. Weak supervision for relation extraction <ref type="bibr">[20]</ref> can be helpful in data augmentation but can only complement human-labeled data whenever an annotation budget is available. Data annotation will face the exploration vs. exploitation dilemma: an annotator needs to find positive samples without knowing where they are ahead of time, but also has to explore the data distribution by labeling certain samples that are negatives. On the one hand, more exploratory labeling leads to better knowledge of the data distribution but leaves less budget to exploit the regions that have more positives. On the other hand, less exploration may trap the annotator in a narrow part of the dataset, missing the areas potentially with more positives.</p><p>To address the dilemma, active search (AS) algorithms are designed to carefully balance the exploration and exploitation in order to obtain the most positive samples. Active search differs from active learning (AL): an AL algorithm labels data for a specific model and is evaluated by the model's performance trained on the data, while an AS algorithm is model-agnostic and aims to find as many positives as possible that potentially can be used to train a model, construct a knowledge base, or for other downstream tasks. Greedy active search algorithms with limited steps of look-ahead and without exploration have been proposed in <ref type="bibr">[6,</ref><ref type="bibr">8,</ref><ref type="bibr">23]</ref>, but their search scales poorly with the number of unlabeled data due to the look-ahead. Bandit algorithms can manage the trade-off between exploration and exploitation in active search <ref type="bibr">[2-4, 11, 12, 17, 18]</ref>. However, prior bandit based active search <ref type="bibr">[13,</ref><ref type="bibr">16]</ref> committed to a single bandit model by making an implicit assumption about the data distribution, which is unknown before the bandit is selected. As a result, the selected bandit can be sub-optimal with respect to the true data distribution. Indeed, we empirically show that different bandit algorithms lead to a rather diverse annotation efficiency. One possible explanations is that, a bandit may assume that the positives are from multiple clusters under a specific distance metric, while another bandit uses a different distance metric, so that the positives form a single cluster and less exploration is needed.</p><p>To avoid over-committing to a presupposition of data distribution of a particular dataset, in an online fashion, the "usefulness" of different bandit algorithms should be actively evaluated (exploration of the algorithms), and then be selected to propose unlabeled data for annotation (exploration in the data space). For the purpose, we propose Meta-AS (Meta Active Search) that has the following benefit over the prior work. First, Meta-AS has a set of more diverse bandit models, including linear <ref type="bibr">[3,</ref><ref type="bibr">11,</ref><ref type="bibr">17]</ref>, kernel-based <ref type="bibr">[18]</ref>, and graphbased bandits <ref type="bibr">[1,</ref><ref type="bibr">21]</ref> to fit the unknown data distribution. The EXP4 algorithm <ref type="bibr">[2]</ref> uses a bandit to manage a set of linear bandits, while Meta-AS adopts more diverse bandits to allow more exploration in the algorithm space. Second, specific to the annotations for relation extraction, a bag of multiple mentions regarding the same pair of words/phrases appearing in one or multiple sentences, can be annotated all at once to save human mental effort. We design Meta-AS to propose bags of mentions, rather than individual mentions.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">PROBLEM DEFINITION</head><p>Let {x 1 , . . . , x n } denote the feature vectors of n mentions, which are initially in the set of unlabeled data U = {x i } n i=1 . B j = {x j i , i = 1, . . . , m j } &#8834; {x 1 , . . . , x n } denote the j-th bag of mentions (instances). The label of x i is y i &#8712; {0, 1}. A bag is positive if and only if at least one of the mentions it contains is positive. The subset P &#8834; U is the designated set of positive instances to be discovered using a budget of M units of human annotation. The generic active search algorithm works iteratively, as shown in Algorithm 1. At iteration t, the algorithm chooses a bag B j(t ) from the unlabeled set U and asks the human annotator to label the mentions in B j(t ) . Since we are interested in collecting positive data, an instance labeled as positive leads to reward 1 and a negative instance leads to reward 0. The model is updated according to the label of instances in B j(t ) , which are then removed from U as their labels are now revealed. The labels of the data points that are not selected remain unknown. The goal is to design a query strategy, parametrized by &#952; , that can select B j(t ) over t = 1, . . . until the budget is used up, so that the number of positive instances labeled is maximized.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Algorithm 1 Generic Active Search</head><p>Input: unlabeled dataset U; labeling budget M. Output: labeled dataset L Initialize the parameters &#952; of the selection strategy.</p><p>Out of budget and return L (t ) . end if ( * ) Use &#952; to select a bag B j(t ) of unlabeled instances. Label the instances in B j(t ) . Remove B j(t ) from U and let L (t +1) = L (t ) &#8746; B j(t ) . Update parameters &#952; using the labeled data in B j(t ) . end for</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">METHODOLOGIES</head><p>The above generic framework can be implemented using a single bandit algorithm, such as UCB <ref type="bibr">[3]</ref> or Thompson sampling <ref type="bibr">[4,</ref><ref type="bibr">11]</ref>, or a meta-bandit with multiple base bandit algorithms. We describe each of these bandit algorithms.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1">Base bandits</head><p>3.1.1 UCB. The UCB <ref type="bibr">[3]</ref> for the multi-armed bandit problem aims to attain maximal cumulative rewards by pulling K arms {1, . . . , K } over time to explore the arm reward distributions and collect the rewards. At iteration t, it pulls the arm a(t) &#8712; {1, . . . , K } with the highest upper bound of the mean rewards:</p><p>where &#956;j (t) is the empirical average reward collected by arm j up to time t, and t j is the number of times the arm j has been pulled up to time t. The parameter &#952; in Algorithm 1 for UCB is &#956;j (t) and t j for j = 1, . . . , K. When the reward of the pulled arm a(t) is revealed, &#956;j (t) and t j will be updated accordingly for the next iteration. UCB will be used in two ways. As a base bandit, the data will be clustered into K clusters, so that each resulting cluster is an arm. See Section 3.1.4 for more details. UCB will be used as a meta-bandit to select base bandits as arms (see Section 3.2).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1.2">Thompson sampling. Thompson sampling (TS for short) is a</head><p>Bayesian treatment of the bandit problem. Here we adopt Thompson sampling in the contextual bandit setting <ref type="bibr">[4]</ref> to take feature vectors x i into account. As the rewards are binary, logistic regression is used to model the likelihood of a positive label/reward p(y i = 1|x i ; &#952; ), given a context x i and a linear model &#952; :</p><p>(</p><p>For exploration, TS draws a sample of w from the posterior p(w|L (t ) ), where L (t ) is the set of instances labeled up to time t. Using Laplace approximation, the posterior p(w|L (t ) ) can be parametrized by the mean vector m and a diagonal covariance matrix q. When a new batch of data is labeled, the mean and the covariance are updated in an online fashion. See <ref type="bibr">[4]</ref> for more details.</p><p>3.1.3 UCB using Gaussian Process. TS assumes a linear relationship between y i and x i . The GP-UCB algorithm <ref type="bibr">[18]</ref> uses Gaussian Process and kernel functions to model a nonlinear relationship between the data and the labels. Let f (x) be a function that predicts the reward when x is selected for labeling. GP-UCB assumes the function f is sampled from a Gaussian Process GP(f ), which controls the smoothness of f via a kernel function k(x, x &#8242; ) &#8712; R for any two instances x and x &#8242; . Given &#8467; labeled points {(x 1 , y 1 ), . . . , (x &#8467; , y &#8467; )}, the reward of any unlabeled point x can be estimated using the posterior Gaussian distribution with the following mean and variance:</p><p>where k &#8467; (x) = [k(x, x 1 ), . . . , k(x, x t )] &#8868; is the function k(x, &#8226;) evaluated on the &#8467; labeled instances, K &#8467; is the kernel matrix with K &#8467; (i, j) = k(x i , x j ), and y &#8467; = [y 1 , . . . , y &#8467; ] &#8868; . GP-UCB <ref type="bibr">[18]</ref> selects</p><p>where &#946; balances exploitation and exploration.</p><p>3.1.4 UCB using graph information. If there are some relationships among the instances beyond the data vectors, a graph can describe the relationships to benefit active search. In the graph, an instance is a node and two related nodes are connected by an edge. For example, the "homophily relationship" assumes that connected instances are more likely to have similar labels. In particular, graph bandits (Graph-UCB for short) assume that the rewards of a node can be inferred from those of its neighbors <ref type="bibr">[1,</ref><ref type="bibr">21]</ref>. We construct a graph of mentions so that two mentions are connected if they shared at least one word.</p><p>The is that if a mention is positive, then other mentions including the shared word(s) are likely to be positive. We first run DeepWalk <ref type="bibr">[15]</ref> on the constructed graph to obtain embeddings of the nodes, and then run the k-means algorithm to cluster the nodes into clusters. Each cluster will contain instances that are likely to have similar labels. A UCB bandit uses the clusters as arms and all instances from a cluster will receive the same UCB score (Eq. ( <ref type="formula">1</ref>)).</p><p>3.1.5 Proposing Bags of Instances. Each base bandit (TS, GP-UCB, Graph-UCB) returns a score for each instance while we need to propose multiple instances in a bag to reduce annotator mental effort. For each bag and each base bandit, we can take the minimum, average, or maximum of the scores of instances in the bag to estimate the value of the bag. Note that different instances from a bag can belong to multiple clusters in Graph-UCB.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2">Meta-bandit for Active Search</head><p>We don't know which of the above bandits (called "base" bandits) is the best for active search on an unlabeled dataset. We propose Meta-AS, a "meta-bandit" that uses UCB to learn to select base bandit to propose data for labeling to collect as many positives as possible. The faster Meta-AS can find the optimal base bandit, the more remaining budget can be used to exploit the positive part of the dataset. The meta-bandit maintains performance statistics of a set A of base bandit algorithms. To diversify the base bandit portfolio, we set different values to the hyper-parameters of each base bandit (kernel function, exploration rate, etc.). At iteration t of Algorithm 1, step ( * ), Meta-AS first samples a base bandit according to</p><p>where p a (t) is the number of positives collected using the a-th base bandit, p(t) = a p a (t) is the number of all positive instances collected so far, and r a (t) is the proportion of iterations that arm a was selected by the meta-bandit among the first t iterations. The exploration is controlled by the hyper-parameter C and how frequent the base bandit a has been used to sample data (n a (t)). The selected base bandit (indexed by a(t) &#8712; A) then selects an unlabeled bag B j(t ) for labeling, and the labeled instances are used to update the parameters of the selected base bandit (e.g. Graph-UCB) and the parameters p a (t), p(t), r a (t) and n a (t) of the meta-bandit (Eq. ( <ref type="formula">4</ref>)). </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">EXPERIMENTS</head><p>Datasets. We adopt a review corpus used in <ref type="bibr">[7]</ref> and four larger product review corpora (Pet, Auto, Instruments, and Videos) from <ref type="bibr">[14]</ref>.</p><p>Our goal is to discover mentions of an adjective and a noun that appear in the same sentence, where the adjective modifies the noun (considering "modification" as a relationship). For example, in the sentence "This large screen is what I have been looking for for long time. ", the adjective "large" modifies "screen" and they are a positive mention of the pair ("large", "screen"), while the pair ("long", "screen") is a negative one. The statistics of the bags and instances in the corpora are listed in Table <ref type="table">1</ref>.</p><p>Bandits settings and baselines. There are hyper-parameters for the base bandits: the covariance matrix q in Thompson sampling (set to the identity matrix multipled by a scalar in {0, 0.01, 0.1, 1.0, 10.0}), the bandwidth of the radial basis function kernel in GP-UCB (set to the inverse of the number of features in x), the &#946; in Eq. ( <ref type="formula">3</ref>) (set to values from {1, 10, 100, 1000, 10000}). We vary the length of walks in {3, 4, 7, 10} with a fixed walk length 80 for DeepWalk and the number of clusters in Graph-UCB is fixed at 20 for all datasets. When running UCB on the resulting clusters, the hyper-parameter C = &#8730; 2 in Eq. (1). To show that Meta-AS can learn from a set of base bandits with diverse performances, on each unlabeled dataset, we evaluate each base bandit with different combinations of hyper-parameter values and aggregation functions (min, mean, and max) for bag proposal, and identify the worst, median, and best settings. We then have three instances of TS, denoted as TS-0, TS-1, and TS-2, with increasing performances, and similarly for GP-UCB (GP-0, GP-1, and GP-2) and Graph-UCB (GU-0, GU-1, and GU-2). Note that GP-UCB is not scale only tested on the small dataset.</p><p>We use two sets of baselines. The first contains any single base bandit with a particular hyper-parameter setting. By comparing the performances of Meta-AS and a single base bandit, we can see how much Meta-AS can approach or even exceed the best base bandit, and by comparing different base bandits with different hyper-parameters, we can see the diverse performance of the base bandits and confirming the need of bandit selection during data annotation.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1">Results</head><p>Overall performance. We run Meta-AS with the selected set of base bandits on the five datasets. In Figure <ref type="figure">1</ref>, we show the performance of each bandit, measured in recall (the percentage of all positive instances that are selected and annotated by the bandit). On the smaller 5-product dataset, Meta-AS is the runner-up among all nine base-bandits, indicating that Meta-AS learned to identify the best base bandit and aimed to approximate the best performance. Even more interesting is the performance of Meta-AS on the four larger corpora: Meta-AS learned to find the best base bandit and started to exceed the best after between 200 to 300 rounds of human feedback. We believe that the better performance comes from less exploration   in the meta-bandit, which safely enter the exploitation mode early. Note the diversity of the performances in the base bandits indicate the necessity of Meta-AS to learn to avoid the low-performing bandits.</p><p>Although not shown here, we observed that more base bandits leads to better Meta-AS performance, confirming the capability of Meta-AS to learn to focus on the optimal base bandit. Sensitivity studies. In Figure <ref type="figure">2</ref>, we study how sensitive Meta-AS is to its hyper-parameter C in Eq. ( <ref type="formula">4</ref>) that controls the amount of exploration in the space of base bandits. We can see that on all five datasets, the hyper-parameter C (set to values in {3, 4, 5, 6}) does not affect the performance of Meta-AS much.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">RELATED WORK AND CONCLUSION</head><p>The selection of base bandit algorithms is an instance of "algorithm selection" <ref type="bibr">[5]</ref> and more broadly an instance of "meta learning" <ref type="bibr">[22]</ref>. In <ref type="bibr">[5]</ref>, they proposed to use a bandit to select SAT solvers to find solutions to different SAT problem instances in an online learning setting. In meta learning <ref type="bibr">[22]</ref>, features describing different problem instances (in our case, different datasets to be actively searched) are designed to guide the selection the best from a portfolio of algorithms to solve each problem. In <ref type="bibr">[9]</ref>, the performance of a trained classifier is actively evaluated. An ensemble of base bandits has been applied to recommendation systems <ref type="bibr">[24]</ref>. However, the experts or base models themselves are not learning as more data are annotated and therefore can't reflect the latest exploration results.</p><p>We conclude that Meta-AS is needed when multiple search algorithms exist but have unknown and diverse performance. We plan to include more base bandit algorithms in Meta-AS, and demonstrate its usefulness beyond text data.</p></div></body>
		</text>
</TEI>
