On-line learning of rectangles

ABSTRACT

This paper solves the following open problem: Is there an algorithm for on-line learning of rectangles i=1

d

ai, ai+1,…,bi} over a discrete domain {1,…,n}d whose error bound is polylogarithmic in the size nd of the domain (i.e. polynomial in d and log n )? We give a positive solution by introducing a new design technique that appears to be of some interest on its own. The new learning algorithm for rectangles consists of 2d separate search strategies that search for the parameters a1,b1,…,ad,bd of the target rectangle. A learning algorithm with this type of modular design ends to fail because of the well known “credit assignment problem”: Which of the 2d local search strategies should be “blamed” when the global algorithm makes an error? We overcome this difficulty by employing local search strategies (“error tolerant binary search”) that are able to tolerate certain types of wrong credit assignments. Section 4 contains another application of this design technique: an algorithm for learning the union of two rectangles in the plane.

REFERENCES

• A: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• H: D. Haussler, personal communication, 1989.
• KMRSW: D.J. Kleitman, A.R. Meyer, R.L. Rivest, J. Spencer, K. Winklman, "Coping with errors in binary search procedures", J. Comp. Syst. Sci., 1980, 396 - 404.
• L: 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]
• MTa: W. Maass, G. Turin, "On the complexity of learning from counterexamples (extended abstract)", Proc of the 30th Annual LE.E.E. Symposium on Foundations of Computer Science, 1989, 262 - 267.
• MTb: W. Maass, G. Turin, "Algorithms and Lower Bounds for On-line Learning of Geometrical Concepts", Report 316 (Oct. 1991), IIG-Report Series, Technische Universitaet Graz;, to appear in Machine Learning.
• MTc: 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]
• P: A. Pelc, Searching with known error probability, Theoretical Computer Science, v.63 n.2, p.185-202, Feb. 1989 [doi>10.1016/0304-3975(89)90077-7]
• PV: 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]
• SW: J. Spencer, P. Winkler, "Three thresholds for a liar", DIMACS Tech. Report 91 - 72 (Oct. 1991).
• V: 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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification