Active Learning with Oracle Epiphany
We present a theoretical analysis of active learning with more realistic interactions with human oracles. Previous empirical studies have shown oracles abstaining on difficult queries until accumulating enough information to make label decisions. We formalize this phenomenon with an "oracle epiphany model" and analyze active learning query complexity under such oracles for both the realizable and the agnostic cases. Our analysis shows that active learning is possible with oracle epiphany, but incurs an additional cost depending on when the epiphany happens. Our results suggest new, principled active learning approaches with realistic oracles.
This work studies the problem of active learning in a setting where the oracle might not be sure how to answer queries in certain (unknown) regions of the space until asked a few times for samples from those regions.  The problem is well-motivated by behavioral studies of human labelers, and by intuitive descriptions of cases that might be seemingly ambiguous at first (e.g., when asked whether a webpage is about sports, the labeler might initially not make up her mind about how to label webpages about sports memorabilia).  The paper models this phenomenon by supposing there are K unknown regions of the space, and each time a query is made in one of these regions for which an "epiphany" has not yet occurred, there is a beta probability the epiphany occurs then, in which case the oracle returns a label as usual (and will henceforth return a label whenever points in that region are queried), and otherwise the oracle abstains from labeling. They propose simple modifications of known active learning algorithms (CAL in the realizable case, OracularCAL in the agnostic case), and analyze the query complexity in each case, paying particular attention to the increase in query complexity induced by these abstentions, which is generally a function of K and beta.
Overall I enjoyed reading this paper.  It is very well written, and the algorithms and analysis seem to be natural modifications of these existing approaches to active learning.  The theoretical issues that arise in handling these abstentions and quantifying their effect on the query complexity are at times nontrivial, and are handled in elegant and appropriate ways.  I suspect that not many people are aware of this problem, but it is quite well motivated in the paper, and seems to be a good problem to study.  The specific theoretical model proposed for this phenomenon is, however, a bit toy-like.  From the motivation, it seems these epiphanies might have more to do with the labeler needing enough data to get a feel for what the distribution of samples will be, to see where to draw the line, rather than there being some random internal event that could happen at any time upon being queried for a data point of that type.  But I suppose this simplistic model could at least be a reasonable starting place, which can hopefully be made more realistic or general in future work.  I have a few technical comments for the authors:  The halting criterion for EPICAL is that \mu_X(D) \le \epsilon. However, it seems far preferable to halt upon  \sup_{h,h' \in V} \mu_X(h(x)\neq h'(x)) \le \epsilon.   Not only is this more closely related to the error rate, but it  would guarantee that the algorithm actually halts (with query  complexity at most roughly the passive sample complexity);  in contrast, the halting criterion as currently stated might never  actually be satisfied (e.g., interval classifiers with target as  empty interval), so that the algorithm never halts.  In Theorem 1, it seems clear that the terms M_CAL and 1/beta are unavoidable (as argued on page 4).  It would be nice to also have some example(s) illustrating the kinds of scenarios where the \bar{M} term is also unavoidable and nonredundant.  If the region U has large probability, then we'll very quickly get 1/beta abstentions, so \bar{M} seems unnecessary.  But if U has small probability (eg, \epsilon/2), then we don't care about the abstentions anyway.  So it seems the medium-sized U case is where \bar{M} might be needed in the bound.  Is there a good example to illustrate its necessity in bounding the query complexity of EPICAL?  In Corollary 7, in the query complexity bound, the first appearance of \tilde{d} in this expression is redundant (the second term already includes a value greater then \tilde{d}(e*/\epsilon) toward the right-most side of the expression).  In the paragraph after Corollary 7, it is claimed that the leading term in the  agnostic setting is of order \theta (e*/\epsilon)(\tilde{d}+\tilde{K}/\beta). However, the bound also includes a term of order \theta (e*/\epsilon)^2 \tilde{d}. So the correct expression here would be \theta ( (e*/\epsilon)^2 \tilde{d} + (e*/\epsilon)\tilde{K}/\beta ).