In this work, we describe a framework that unifies many different interactive learning tasks. We present a generalization of the query-by-committee active learning algorithm for this setting, and we study its consistency and rate of convergence, both theoretically and empirically, with and without noise.
The analysis we present in this paper is closely related to that of the original query-by-committee algorithm @cite_7 ; in particular, it uses a very similar notion of uncertainty. Our results are also very close in spirit to those obtained for generalized binary search @cite_27 . In fact, the latter work is able to characterize the query complexity of binary active learning using certain geometric quantities, and it is an interesting open problem whether something similar can be done in our structural setting.
@cite_27 @cite_7
2543543809 2080021732 2135496842 1965313644
This paper studies a generalization of the classic binary search problem of locating a desired value within a sorted list. The classic problem can be viewed as determining the correct one-dimensional, binary-valued threshold function from a finite class of such functions based on queries taking the form of point samples of the function. The classic problem is also equivalent to a simple binary encoding of the threshold location. This paper extends binary search to learning more general binary-valued functions. Specifically, if the set of target functions and queries satisfy certain geometrical relationships, then an algorithm, based on selecting a query that is maximally discriminating at each step, will determine the correct function in a number of steps that is logarithmic in the number of functions under consideration. Examples of classes satisfying the geometrical relationships include linear separators in multiple dimensions. Extensions to handle noise are also discussed. Possible applications include machine learning, channel coding, and sequential experimental design. We propose an algorithm called query by commitee , in which a committee of students is trained on the same data set. The next query is chosen according to the principle of maximal disagreement . The algorithm is studied for two toy models: the high-low game and perceptron learning of another perceptron. As the number of queries goes to infinity, the committee algorithm yields asymptotically finite information gain. This leads to generalization error that decreases exponentially with the number of examples. This in marked contrast to learning from randomly chosen inputs, for which the information gain approaches zero and the generalization error decreases with a relatively slow inverse power law. We suggest that asymptotically finite information gain may be an important characteristic of good query algorithms. This paper addresses the problem of noisy Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued hypothesis through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search. GBS is used in many applications, including fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and active learning. In most of these cases, the responses to queries can be noisy. Past work has provided a partial characterization of GBS, but existing noise-tolerant versions of GBS are suboptimal in terms of query complexity. This paper presents an optimal algorithm for noisy GBS and demonstrates its application to learning multidimensional threshold functions. This paper investigates the problem of determining a binary-valued function through a sequence of strategically selected queries. The focus is an algorithm called Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued function through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search. This paper develops novel incoherence and geometric conditions under which GBS achieves the information-theoretically optimal query complexity; i.e., given a collection of N hypotheses, GBS terminates with the correct function after no more than a constant times logN queries. Furthermore, a noise-tolerant version of GBS is developed that also achieves the optimal query complexity. These results are applied to learning halfspaces, a problem arising routinely in image processing and machine learning.