Learning unions of boxes with membership and equivalence queries

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 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 logn for any d constant. Further, all equivalence queries made can be formulated as the union of O(sdlogs) 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, &sgr;, 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 &sgr; and logn. 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 logn for s any constant thus generating 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.

REFERENCES

• 1: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 2: Peter Auer, On-line learning of rectangles in noisy environments, Proceedings of the sixth annual conference on Computational learning theory, p.253-261, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168345]
• 3: Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129748]
• 4: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 5: Zhixiang Chen, Learning unions of two rectangles in the plane with equivalence queries, Proceedings of the sixth annual conference on Computational learning theory, p.243-252, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168342]
• 6: Zhixiang Chen , Wolfgang Maass, On-line learning of rectangles, Proceedings of the fifth annual workshop on Computational learning theory, p.16-28, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130387]
• 7: V. Chvatal. A greedy heuristic for the set covering problem. Mathematics of Operations Research, 4(3):233-235, 1979.
• 8: Michael Frazier , Sally Goldman , Nina Mishra , Leonard Pitt, Learning from a consistently ignorant teacher, Proceedings of the seventh annual conference on Computational learning theory, p.328-339, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181170]
• 9: Steven Homer and Zhixiang Chen. Fast learning unions of rectangles with queries. Unpublished manuscript, July 1993.
• 10: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 11: Philip M. Long , Manfred K. Warmuth, Composite geometric concepts and polynomial predictability, Proceedings of the third annual workshop on Computational learning theory, p.273-287, August 06-08, 1990, Rochester, New York, United States
• 12: Wolfgang Maass and GySrgy Turan. On the complexity of learning from counterexamples. In 30th Annual Symposium on Foundations of Computer Science, pages 262-267, October 1989.
• 13: Wolfgang Maass and GySrgy Turan. On the complexity of learning from counterexamples and membership queries. In 31st Annual Symposium on Foundations of Computer Science, pages 203-210, October 1990.
• 14: Wolfgang Maass and GySrgy Turin. Algorithms and lower bounds for on-line learning of geometrical concepts. Technical Report IIG-Report 316, Technische Universit~it Graz, TU Graz, Austria, October 1991.
• 15: Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]
• 16: Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
• 17: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms, Theory, Verification