ACTIVE LEARNING WITH PARTIAL FEEDBACK
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.
The paper considers a multiclass classification problem in which labels are grouped in a given number M of subsets c_j, which contain all individual labels as singletons. Training takes place through an active learning setting in which all training examples x_i are initially provided without their ground truth labels y_i. The learner issues queries of the form (x_i,c_j) where c_j is one of the given subsets of labels. The annotator only replies yes/no according to whether the true label y_i of x_i belongs to c_j or not. Hence, for each training example the learner maintains a "version space" containing all labels that are consistent with the answers received so far for that example. The active learning process consists of the following steps: (1) use the current learning model to score queries (x_i,c_j); (2) query the best (x_i,c_j); (3) update the model.
In their experiments, the authors use a mini-batched version, where queries are issued and re-ranked several times before updating the model. Assuming the learner generates predictive models which map examples to probability distributions over the class labels, several uncertainty measures can be used to score queries: expected info gain, expected remaining classes, expected decrease in remaining classes. Experiments are run using the Res-18 neural network architecture over CIFAR10, CIFAR100, and Tiny ImageNet, with training sets of 50k, 50k, and 100k examples. The subsets c_j are computed using the Wordnet hierarchy on the label names resulting in 27, 261, and 304 subsets for the three datasets. The experiments show the advantage of performing adaptive queries as opposed to several baselines: random example selection with binary search over labels, active learning over the examples with binary search over the labels, and others. 
This paper develops a natural learning strategy combining two known approaches: active learning and learning with partial labels. The main idea is to exploit adaptation in both choosing examples and queries. The experimental approach is sound and the results are informative. In general, a good experimental paper with a somewhat incremental conceptual contribution.
In (2) there is t+1 on the left-hand side and t on the right-hand side, as if it were an update. Is it a typo?
In 3.1, how is the standard multiclass classifier making use of the partially labeled examples during training?
How are the number of questions required to exactly label all training examples computed? Why does this number vary across the different methods?
What specific partial feedback strategies are used by AQ for labeling examples?
EDC seems to consistently outperform ERC for small annotation budgets. Any intuition why this happens?