Active Imitation Learning with Noisy Guidance (2020)

Abstract: Imitation learning algorithms provide state-of-the-art results on many structured prediction tasks by learning near-optimal search policies. Such algorithms assume training-time access to an expert that can provide the optimal action at any queried state; unfortunately, the number of such queries is often prohibitive, frequently rendering these approaches impractical. To combat this query complexity, we consider an active learning setting in which the learning algorithm has additional access to a much cheaper noisy heuristic that provides noisy guidance. Our algorithm, LEAQI, learns a difference classifier that predicts when the expert is likely to disagree with the heuristic, and queries the expert only when necessary. We apply LEAQI to three sequence labelling tasks, demonstrating significantly fewer queries to the expert and comparable (or better) accuracies over a passive approach.

## introduction structured prediction methods learn models to map inputs to complex outputs with internal dependencies, typically requiring a substantial amount of expert-labeled data. to minimize annotation cost, we focus on a setting in which an expert provides labels for pieces of the input, rather than the complete input (e.g., labeling at the level of words, not sentences). a natural starting point for this is imitation learning-based "learning to search" approaches to structured prediction @xcite @xcite . in imitation learning, training proceeds by incrementally producing structured outputs on piece at a time and, at every step, asking the expert "what would you do here?" and learning to mimic that choice. this interactive model comes at a substantial cost: the expert demonstrator must be continuously available and must be able to answer a potentially large number of queries. we reduce this annotation cost by only asking an expert for labels that are truly needed; our algorithm, learning to query for imitation (leaqi, /"li:,tsi:/) foot_0 achieves this by capitalizing on two factors. first, as is typical in active learning (see §2), leaqi only asks the expert for a label when it is uncertain. second, leaqi assumes access to a noisy heuristic labeling function (for instance, a rule-based model, dictionary, or inexpert annotator) that can provide low-quality labels. leaqi operates by always asking this heuristic for a label, and only querying the expert when it thinks the expert is likely to disagree with this label. it trains, simultaneously, a difference classifier @xcite that predicts disagreements between the expert and the heuristic (see figure 1 ). the challenge in learning the difference classifier is that it must learn based on one-sided feedback: if it predicts that the expert is likely to agree with the heuristic, the expert is not queried and the classifier cannot learn that it was wrong. we address this one-sided feedback problem using the apple tasting framework @xcite , in which errors (in predicting which apples are tasty) are only observed when a query is made (an apple is tasted). learning in this way particularly important in the general case where the heuristic is likely not just to have high variance with respect to the expert, but is also statistically biased. experimentally ( §4.5), we consider three structured prediction settings, each using a different type of heuristic feedback. we apply leaqi to: english named entity recognition where the heuristic is a rule-based recognizer using gazetteers @xcite ; english scientific keyphrase extraction, where the heuristic is an unsupervised method @xcite ; and greek part-ofspeech tagging, where the heuristic is a small dictio-after completing his ph.d. , ellis worked at bell labs from 1969 to 1972 on probability theory... x is the input sentence and y is the (unobserved) ground truth. the predictor π operates left-to-right and, in this example, is currently at state s 10 to tag the 10th word; the state s 10 (highlighted in purple) combines x with ŷ1:9 . the heuristic makes two errors at @xmath0. the heuristic label at @xmath1. under hamming loss, the cost at @xmath2, which is therefore the expert action (if it were queried). the label that would be provided for s 10 to the difference classifier is 0 because the two policies agree. ## background and related work we review first the use of imitation learning for structured prediction, then online active learning, and finally applications of active learning to structured prediction and imitation learning problems. ## our approach: leaqi our goal is to learn a structured prediction model with minimal human expert supervision, effectively by combining human annotation with a noisy heuristic. we present leaqi to achieve this. as a concrete example, return to figure 1 : at s 10 , π must predict the label of the tenth word. if π is confident in its own prediction, leaqi can avoid any query, similar to traditional active learning. if π is not confident, then leaqi considers the label suggested by a noisy heuristic (here: org). leaqi predicts whether the true expert label is likely to disagree with the noisy heuristic. here, it predicts no disagreement and avoids querying the expert. ## experiments the primary research questions we aim to answer experimentally are: q1 does uncertainty-based active learning achieve lower query complexity than passive learning in the learning to search settings? q2 does learning a difference classifier improve query efficiency over active learning alone? q3 does apple tasting successfully handle the problem of learning from one-sided feedback? q4 is the approach robust to cases where the noisy heuristic is uncorrelated with the expert? q5 is casting the heuristic as a policy more effective than using its output as features? to answer these questions, we conduct experiments on three tasks (see ## discussion and limitations in this paper, we considered the problem of reducing the number of queries to an expert labeler for structured prediction problems. we took an imitation learning approach and developed an algorithm, leaqi, which leverages a source that has low-quality labels: a heuristic policy that is suboptimal but free. to use this heuristic as a policy, we learn a difference classifier that effectively tells leaqi when it is safe to treat the heuristic's action as if it were optimal. we showed empiricallyacross named entity recognition, keyphrase extraction and part of speech tagging tasks-that the active learning approach improves significantly on passive learning, and that leveraging a difference classifier improves on that. 1. in some settings, learning a difference classifier may be as hard or harder than learning the structured predictor; for instance if the task is binary sequence labeling (e.g., word segmentation), minimizing its usefulness. despite these limitations, we hope that leaqi provides a useful (and relatively simple) bridge that can enable using rule-based systems, heuristics, and unsupervised models as building blocks for more complex supervised learning systems. this is particularly attractive in settings where we have very strong rule-based systems, ones which often outperform the best statistical systems, like coreference resolution @xcite , information extraction @xcite , and morphological segmentation and analysis @xcite .