Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts

摘要

The complexity of on-line learning is investigated for the basic classes of geometrical objects over a discrete (“digitized”) domain. In particular, upper and lower bounds are derived for the complexity of learning algorithms for axis-parallel rectangles, rectangles in general position, balls, half-spaces, intersections of half-spaces, and semi-algebraic sets. The learning model considered is the standard model for on-line learning from counterexamples.