EXACT LEARNING OF DISCRETIZED GEOMETRIC CONCEPTS

We first present an algorithm that uses membership and equivalence que ries to exactly identify a discretized geometric concept defined by th e union of m axis-parallel boxes in d-dimensional discretized Euclidea n space where each coordinate can have n discrete values. This algorit hm receives at most md counterexamples and uses time and membership qu eries polynomial in m and log n for any constant d. Furthermore, all e quivalence queries can be formulated as the union of O(md log m) axis- parallel boxes. Next, we show how to extend our algorithm to efficient ly learn, from only equivalence queries, any discretized geometric con cept generated from any number of halfspaces with any number of known (to the learner) slopes in a constant dimensional space. In particular , our algorithm exactly learns (from equivalence queries only) unions of discretized axis-parallel boxes in constant dimensional space in po lynomial time. Furthermore, this equivalence query only algorithm can be modified to handle a polynomial number of lies in the counterexampl es provided by the environment. Finally, we introduce a new complexity measure that better captures the complexity of the union of m boxes t han simply the number of boxes and the dimension. Our new measure, sig ma, is the number of segments in the target, where a segment is a maxi mum portion of one of the sides of the target that lies entirely insid e or entirely outside each of the other halfspaces defining the target . We present a modification of our first algorithm that uses time and queries polynomial in sigma and log n. In fact, the time and queries ( both membership and equivalence) used by this single algorithm are pol ynomial for either m or d constant.