Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1994-01-01

Filename

WUCS-94-19.PDF

DOI:

10.7936/K7CR5RJD

Technical Report Number

WUCS-94-19

Abstract

We first present an algorithm that uses membership and equivalence queries to exactly identify a discretized geometric concept defined by the unioin of m axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. This algorithm receives at most md counterexamples and uses time and membership queries polynomial in m and log(n) for any constant d. Furthermore, all equivalence queries can be formulated as the union of O(mdlog(m)) axis-parallel boxes. Next, we show how to extend our algorithm to efficiently learn, from only equivalence queries, any discretized geometric concept 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 polynomial time. Further, this algorithm can be modified to handle a polynomial number of lies in the counterexamples provided by the environment. Finally, we introduce a new complexity measure that better captures the complexity of the union of m boxes than simply the number of boxes and the dimension. Our new measure, , is the number of segments in the target, where a segment is a maximum portion of one of the sides of the target that lies entirely inside 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 and log(n). In fact, the time and queries (both membership and equivalence) used by this single algorithm are polynomial for either m or d constant.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7CR5RJD

Download

Share

COinS