While many active learning papers assume that the learner can simply ask for a label and receive it, real annotation often presents a mismatch between the form of a label (say, one among many classes), and the form of an annotation (typically yes/no binary feedback). To annotate examples corpora for multiclass classification, we might need to ask multiple yes/no questions, exploiting a label hierarchy if one is available. To address this more realistic setting, we propose active learning with partial feedback (ALPF), where the learner must actively choose both which example to label and which binary question to ask. At each step, the learner selects an example, asking if it belongs to a chosen (possibly composite) class. Each answer eliminates some classes, leaving the learner with a partial label. The learner may then either ask more questions about the same example (until an exact label is uncovered) or move on immediately, leaving the first example partially labeled. Active learning with partial labels requires (i) a sampling strategy to choose (example, class) pairs, and (ii) learning from partial labels between rounds. Experiments on Tiny ImageNet demonstrate that our most effective method improves 26% (relative) in top-1 classification accuracy compared to i.i.d. baselines and standard active learners given 30% of the annotation budget that would be required (naively) to annotate the dataset. Moreover, ALPF-learners fully annotate TinyImageNet at 42% lower cost. Surprisingly, we observe that accounting for per-example annotation costs can alter the conventional wisdom that active learners should solicit labels for hard examples. Given a large set of unlabeled images, and a budget to collect annotations, how can we learn an accurate image classifier most economically? Active Learning (AL) seeks to increase data efficiency by strategically choosing which examples to annotate. Typically, AL treats the labeling process as atomic: every annotation costs the same and produces a correct label. However, large-scale multi-class annotation is seldom atomic; we can't simply ask a crowd-worker to select one among 1000 classes if they aren't familiar with our ontology. Instead, annotation pipelines typically solicit feedback through simpler mechanisms such as yes/no questions. For example, to construct the 1000-class ImageNet dataset, researchers first filtered candidates for each class via Google Image Search, then asking crowd-workers questions like "Is there a Burmese cat in this image?" BID5 . For tasks where the Google trick won't work, we might exploit class hierarchies to drill down to the exact label. Costs scale with the number of questions asked. Thus, real-world annotation costs can vary per example BID24 .We propose Active Learning with Partial Feedback (ALPF), asking, can we cut costs by actively choosing both which examples to annotate, and which questions to ask? Say that for a new image, our current classifier places 99% of the predicted probability mass on various dog breeds. Why start at the top of the tree -"is this an artificial object?" -when we can cut costs by jumping straight to dog breeds ( FIG0 )? ALPF proceeds as follows: In addition to the class labels, the learner possesses a pre-defined collection of composite classes, e.g. dog ⊃ bulldog, mastiff, .... At each round, the learner selects an (example, class) pair. The annotator responds with binary feedback, leaving the learner with a partial label. If only the atomic class label remains, the learner has obtained an exact label. For simplicity, we focus on hierarchically-organized collections-trees with atomic classes as leaves and composite classes as internal nodes. For this to work, we need a hierarchy of concepts familiar to the annotator. Imagine asking an annotator "is this a foo?" where foo represents a category comprised of 500 random ImageNet classes. Determining class membership would be onerous for the same reason that providing an exact label is: It requires the annotator be familiar with an enormous list of seemingly-unrelated options before answering. On the other hand , answering "is this an animal?" is easy despite animal being an extremely coarse-grained category -because most people already know what an animal is.We use active questions in a few ways. To start, in the simplest setup, we can select samples at random but then once each sample is selected, choose questions actively until finding the label:ML: "Is it a dog?" Human: Yes! ML: "Is it a poodle ?" Human: No! ML: "Is it a hound ?" Human: Yes! ML: " Is it a Rhodesian ?" Human: No! ML: "Is it a Dachsund ?" Human: Yes!In ALPF, we go one step further. Since our goal is to produce accurate classifiers on tight budget, should we necessarily label each example to completion? After each question, ALPF learners have the option of choosing a different example for the next binary query. Efficient learning under ALPF requires (i) good strategies for choosing (example , class) pairs, and (ii) techniques for learning from the partially-labeled data that results when labeling examples to completion isn't required.We first demonstrate an effective scheme for learning from partial labels. The predictive distribution is parameterized by a softmax over all classes. On a per-example basis, we convert the multiclass problem to a binary classification problem, where the two classes correspond to the subsets of potential and eliminated classes. We determine the total probability assigned to potential classes by summing over their softmax probabilities. For active learning with partial feedback, we introduce several acquisition functions for soliciting partial labels, selecting questions among all (example, class) pairs. One natural method, expected information gain (EIG) generalizes the classic maximum entropy heuristic to the ALPF setting. Our two other heuristics, EDC and ERC, select based on the number of labels that we expect to see eliminated from and remaining in a given partial label, respectively.We evaluate ALPF learners on CIFAR10, CIFAR100, and Tiny ImageNet datasets. In all cases, we use WordNet to impose a hierarchy on our labels. Each of our experiments simulates rounds of active learning, starting with a small amount of i. 2 ACTIVE LEARNING WITH PARTIAL FEEDBACK By x ∈ R d and y ∈ Y for Y = {{1}, ..., {k}}, we denote feature vectors and labels. Here d is the feature dimension and k is the number of atomic classes . By atomic class, we mean that they are indivisible. As in conventional AL, the agent starts off with an unlabeled training set D = {x 1 , ..., x n }.Composite classes We also consider a pre-specified collection of composite classes C = {c 1 , ..., c m }, where each composite class c i ⊂ {1, ..., k} is a subset of labels such that |c i | ≥ 1. Note that C includes both the atomic and composite classes. In this paper's empirical section, we generate composite classes by imposing an existing lexical hierarchy on the class labels BID19 . Our experiments validate the active learning with partial feedback framework on large-scale classification benchmarks. The best among our proposed ALPF learners fully labels the data with 42% fewer binary questions as compared to traditional active learners. Our diagnostic analysis suggests that in ALPF, it's sometimes more efficient to start with "easier" examples that can be cheaply annotated rather than with "harder" data as often suggested by traditional active learning.A WARM-STARTING PLOT ALPF -ERC -0% ALPF -ERC -5% ALPF -ERC -10% FIG4 : This plot compares our models under various amounts of warm-starting with pre-labeled i.i.d. data. We find that on the investigated datasets, ERC does benefit from warm-starting. However, absent warm-starting, EIG performs significantly worse and EDC suffers even more. We find that 5% warmstarting helps these two models and that for both, increasing warm-starting from 5% up to 10% does not lead to further improvements.
We provide a new perspective on training a machine learning model from scratch in hierarchical label setting, i.e. thinking of it as two-way communication between human and algorithms, and study how we can both measure and improve the efficiency.  Introduces a new Active Learning setting where the oracle offers a partial or weak label instead of querying for a particular example's label, leading to a simpler retrieval of information. This paper proposes a method of active learning with partial feedback that outperforms existing baselines under a limited budget. The paper considers a multiclass classification problem in which labels are grouped in a given number M of subsets, which contain all individual labels as singletons.