Publications Details

Learning unions of boxes with membership and equivalence queries

Goldberg, P.W.; Goldman, S.A.; Mathias, H.D.

We present two algorithms that use membership and equivalence queries to exactly identify the concepts given by the union of s discretized axis-parallel boxes in d-dimensional discretized Euclidean space where there are n discrete values that each coordinate can have. The first algorithm receives at most sd counterexamples and uses time and membership queries polynomial in s and log n for d any constant. Further, all equivalence queries made can be formulated as the union of O(sd logs) axis-parallel boxes. Next, we introduce a new complexity measure that better captures the complexity of a union of boxes than simply the number of boxes and dimensions. Our new measure, u, is the number of segments in the target polyhedron where a segment is a maximum portion of one of the sides of the polyhedron that lies entirely inside or entirely outside each of the other halfspaces defining the polyhedron. We then present an improvement of our first algorithm that uses time and queries polynomial in u and log n. The hypothesis class used here is decision trees of height at most 2sd, Further we can show that the time and queries used by this algorithm are polynomial in d and log n for s any constant thus generalizing the exact learnability of DNF formulas with a constant number of terms. In fact, this single algorithm is efficient for either s or d constant.