Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries

Authors: Valery N. Shevchenko, and Nikolai Yu. Zolotykh

Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 61 - 71.

Abstract. Exact learning of half-spaces over finite subsets of Realsn from membership queries is considered. We describe the minimum set of labelled examples separating the target concept from all the other ones of the concept class under consideration. For a domain consisting of all integer points of some polytope we give non-trivial lower bounds on the complexity of exact identification of half-spaces. These bounds are near to known upper bounds.

©Copyright 1998 Springer