Efficient agnostic PAC-learning with simple hypothesis

ABSTRACT

We exhibit efficient algorithms for agnostic PAC-learning with rectangles, unions of two rectangles, and unions of k intervals as hypotheses. These hypothesis classes are of some interest from the point of view of applied machine learning, because empirical studies show that hypotheses of this simple type (in just one or two of the attributes) provide good prediction rules for various real-world classification problems. In addition, optimal hypotheses of this type may provide valuable heuristic insight into the structure of a real world classification problem. The algorithms that are introduced in this paper make it feasible to compute optimal hypotheses of this type for a training set of several hundred examples. We also exhibit an approximation algorithm that can compute nearly optimal hypotheses for much larger datasets.

REFERENCES

• AL: Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
• BN: Wray Buntine , Tim Niblett, A Further Comparison of Splitting Rules for Decision-Tree Induction, Machine Learning, v.8 n.1, p.75-85, Jan. 1992 [doi>10.1023/A:1022686419106]
• D: Scott Evan Decatur, Statistical queries and faulty PAC oracles, Proceedings of the sixth annual conference on Computational learning theory, p.262-268, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168346]
• DG a: D.P. Dobkin, D. Gunopulos, Computing the rectangle discrepancy (video), 3rd Annual Video Review of Computational Geometry
• DG b: D.P. Dobkin, D. Gunopulos, Computing the rectangle discrepancy, Tech Report 443-94, Princeton University
• H: David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
• HSV: K.U. Hoeffgen, H. U. Simon, K. S. Van Horn, Robust trainability of single neurons, preprint (1993)
• Ho: Robert C. Holte, Very Simple Classification Rules Perform Well on Most Commonly Used Datasets, Machine Learning, v.11 n.1, p.63-90, April 1993 [doi>10.1023/A:1022631118932]
• K: Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
• KL: Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
• KS: M.J. Kearns, R. E. Schapire, Efficient distribution-free learning of probabilisiic concepts, Proc. of the 31st Annual IEEE Symp. on Foundations of Computer Science, 1990, 382 - 391
• KSS: Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130424]
• M: John Mingers, An Empirical Comparison of Pruning Methods for Decision Tree Induction, Machine Learning, v.4 n.2, p.227-243, November 1989 [doi>10.1023/A:1022604100933]
• Me: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Q: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• T: M. Talagrand, Sharper bounds for empirical processes, to appear in Annals of Probability and its Applications
• V 84: 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]
• V 85: L.G. Valiant, Learning disjunctions of conjunctions, Proc. of the 9th Intern. Joint Conf. on Art. Int., 1985, 560 - 566
• WGT: S. M. Weiss , R. S. Galen , P. V. Tadepalli, Maximizing the predictive value of production rules, Artificial Intelligence, v.45 n.1-2, p.47-71, Sep. 1990 [doi>10.1016/0004-3702(90)90037-Z]
• WK 90: S.M. Weiss, I. Kapouleas, An empirical comparison of paltern recognition, neural nets, and machine learning classification methods, Proc. of the 11th Int. Joint Conf. on Art. Int. 1990, Morgan Kaufmann, 781 - 787
• WK 91: S.M. Weiss, C. A. Kulikowski, Computer Systems thai Learn, 1991, Morgan Kaufmann

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory