Document Type

Technical Report

Publication Date

1993

Filename

WUCS-93-46.pdf

DOI:

10.7936/K72B8WC1

Technical Report Number

WUCS-93-46

Abstract

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 each coordinate can have n discrete values. The first algorithm receives at most s*d counterexamples and uses time and membership queries polynomial in s and logn for d any constant. Further, all equivalence queries made can be formulated as the union of O(s*d*log(s)) 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, [sigma], 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 [sigma] and log(n). The hypothesis class used here is the decision trees of height at most 2*s*d. 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.

Comments

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

Download

Share

COinS