The Geometry of Generalized Binary Search

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 stra...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2011-12, Vol.57 (12), p.7893-7906
Main Author: Nowak, R. D.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial intelligence
Binary search
channel coding with feedback
Coding, codes
Coherence
Collection
Complexity
Complexity theory
Exact sciences and technology
Hypotheses
Image processing
Incoherence
Information theory
Information, signal and communications theory
Learning
learning theory
Noise measurement
Optimization
Prediction algorithms
Queries
query learning
Search problems
Searching
Shannon-Fano coding
Signal and communications theory
Signal processing
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2011.2169298