The Geometry of Generalized Binary Search
Author:
- 5 December 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 57 (12) , 7893-7906
Abstract
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.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Minimax Bounds for Active LearningIEEE Transactions on Information Theory, 2008
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationIEEE Transactions on Information Theory, 2006
- Active Learning in the Non-realizable Case2006
- Rates of convergence for the sup-norm risk in image models under sequential designsStatistics & Probability Letters, 2000
- On minimax rates of convergence in image models under sequential designStatistics & Probability Letters, 1999
- Promising directions in active visionInternational Journal of Computer Vision, 1993
- Ulam's searching game with a fixed number of liesTheoretical Computer Science, 1992
- Searching in the presence of linearly bounded errors1991
- Coping with errors in binary search proceduresJournal of Computer and System Sciences, 1980