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 n 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