Learnability and the Vapnik-Chervonenkis dimension

ABSTRACT

Valiant's learnability model is extended to learning classes of concepts defined by regions in Euclidean space En. The methods in this paper lead to a unified treatment of some of Valiant's results, along with previous results on distribution-free convergence of certain pattern recognition algorithms. It is shown that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned. Using this parameter, the complexity and closure properties of learnable classes are analyzed, and the necessary and sufficient conditions are provided for feasible learnability.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	3	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	4	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	5	ANGLUIN, D., AND VALIANT, L. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. Syst. Sci. 19 (1979), 155-193.
	6	ASSOUAD, P. Densit6 et Dimension. Ann. Inst. Fourier, Grenoble 33, 3 (1983), 233-282.
	7	Eric B. Baum , David Haussler, What size net gives valid generalization?, Neural Computation, v.1 n.1, p.151-160, Spring 1990 [doi>10.1162/neco.1989.1.1.151]
	7a	Shai Ben-David , Gyora M. Benedek , Yishay Mansour, A parametrization scheme for classifying models of learnability, Proceedings of the second annual workshop on Computational learning theory, p.285-302, December 1989, Santa Cruz, California, United States
	8	Gyora M. Benedek , Alon Itai, Nonuniform Learnability, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.82-92, July 11-15, 1988
	9	Avrim Blum , Ronald L. Rivest, Training a 3-node neural network is NP-complete, Proceedings of the first annual workshop on Computational learning theory, p.9-18, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	10	Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
	11	BOLLOB/~S, B. Combinatorics. Cambridge Univ. Press, Cambridge, Mass., 1986.
	12	Stéphane Boucheron , Jean Sallantin, Some remarks about space-complexity of learning, and circuit complexity of recognizing, Proceedings of the first annual workshop on Computational learning theory, p.125-138, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	13	COVER, T. Geometrical and statistical properties of systems of linear inequalities with applications to pattern recognition. IEEE Trans. Elect. Comp. 14 (1965), 326-334.
	14	Luc Devroye, Automatic Pattern Recognition: A Study of the Probability of Error, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.4, p.530-543, July 1988 [doi>10.1109/34.3915]
	15	DEVROYE, L. P., AND WAGNER, T.J. A distribution-free performance bound in error estimation. IEEE Trans. inf. Theorem 22 (1976), 586-587.
	16	DUDA, R., AND HART, P. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
	17	DUDLEY, R.M. A course on empirical processes. In Lecture Notes in Mathematics, vol. 1097. Springer-Verlag, New York, 1984.
	18	DUDLEY, R. M. Universal Donsker classes and metric entropy. Ann. Prob. 15, 4 (1987), 1306-1326.
	19	H. Edelsbrunner , F. P. Preparata, Minimum polygonal separation, Information and Computation, v.77 n.3, p.218-232, May 1988 [doi>10.1016/0890-5401(88)90049-1]
	20	Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
	21	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	22	GII~L, J. Probabilistic Turing machines. SlAM J. Comput. 6, 4 (1977), 675-695.
	23	Gm~, E., AND ZINN, J. Lectures on the central limit theorem for empirical processes. In Lecture Notes in Mathematics, vol. 122 I. Springer-Verlag, New York, 1986.
	24	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	25	S E Hampson , D J Volper, Linear function neurons: Structure and training, Biological Cybernetics, v.53 n.4, p.203-218, Feb. 1986 [doi>10.1007/BF00336991]
	26	David Haussler, Learning Conjunctive Concepts in Structural Domains, Machine Learning, v.4 n.1, p.7-40, October 1989 [doi>10.1023/A:1022601210986]
	27	HA USSLER, D. Applying Valiant's learning framework to AI concept learning problems. In Proceedings of the 4th International Workshop on Machine Learning. Morgan Kaufinann, San Mateo, Calif., 1987, pp. 324-336.
	28	D. Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, Artificial Intelligence, v.36 n.2, p.177-221, September 1988 [doi>10.1016/0004-3702(88)90002-1]
	28a	HA USSLER, D. Generalizing the PAC model: Sample size bounds from metric dimension-based uniform convergence results. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (Research Triangle Park, N.C., Oct. 30-Nov. 1). IEEE, New York:, 1989, to appear.
	29	HA USSLER, D., AND WELZL, E. Epsilon-nets and simplex range queries. Disc. Comput. Geometry 2 (1987), 127-151.
	30	HAUSSLER, D., KEARNS, M., LITTLESTONE, N., AND WARMUTH, M.K. Equivalence of models for polynomial learnability. Tech. Rep. UCSC-CRL-88-06. Univ. California at Santa Cruz, Santa Cruz, Calif., 1988.
	31	HAUSSLER, D., LITTLESTONE, N., AND WARMUTH, M.K. Predicting {0, 1}-functions on~ randomly drawn points. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (White Plains, N.Y., Oct.). IEEE, New York, 1988, pp. 100-109.
	32	JOHNSON, D.S. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9 (1974), 256-278.
	33	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	34	Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
	35	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	36	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	37	KEARNS, M., LI, M., PITT, L., AND VALIANT, L. Recent results on Boolean concept learning. In Proceedings of the 4th International Workshop on Machine Learning. Morgan-Kaufinann, San Mateo, Calif., 1987, pp. 337-352.
	38	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	39	LAIRD, P.D. Learning from good data and bad. Tech. Rep. YALEU/DCS/TR-551. Yale Univ., New Haven, Conn., 1987.
	40	LEE, D. T., AND PREPARATA, F.P. Computational geometry--A survey. IEEE Trans. Comput. 33, 12 (1984), 1072-1101.
	41	LINIAL, N., MANSOUR, Y., AND RWEST, R. Results on learnability and the Vapnik-Chervonenkis dimension. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (White Plains, N.Y., Oct.). IEEE, New York, 1988, pp. 120-129.
	42	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]
	43	MASEK, W.J. Some NP-complete set cover problems. MIT Laboratory for Computer Science, unpublished manuscript.
	44	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	45	MEGIDDO, N. On the complexity of polyhedral separability. Discrete Comput. Geometry 3 (1988), 325-337.
	46	MUROGA, S. Threshold Logic and Its Applications. Wiley, New York, 1971.
	47	B. K. Natarajan, On learning Boolean functions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.296-304, January 1987, New York, New York, United States [doi>10.1145/28395.28427]
	48	NATARAJAN, B.K. Learning functions from examples. Tech. Rep. CMU-RI-TR-87-19. Carnegie Mellon Univ., Pittsburgh, Pa., Aug. 1987.
	49	NIGMATULLIN, R. G. The fastest descent method for coveting problems (in Russian). In Proceedings of a Symposium on Questions of Precision and Efficiency of Computer Algorithms, Book 5. Kiev, 1969, pp. 116-126.
	50	PEARL, J. On the connection between the complexity and credibility of inferred models. Int. J. Gen. Syst. 4 (1978), 255-264.
	51	PEARL, J. Capacity and error estimates for Boolean classifiers with limited capacity. IEEE Trans. Pattern Analysis Mach. Intell. 1, 4 (1979), 350-355.
	52	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]
	53	PITT, L., AND WARMUTH, M. Reductions among prediction problems, on the difficulty of predicting automata. In Proceedings of the 3rd IEEE Structure in Complexity Theory Conference (Washington, D.C.). IEEE, New York, 1988, pp. 62-69.
	54	POLLARD, D. Convergence of Stochastic Processes. Springer-Verlag, New York, 1984.
	55	J. R. Quinlan , R. L. Rivest, Inferring decision trees using the minimum description length principle, Information and Computation, v.80 n.3, p.227-248, Mar. 1989 [doi>10.1016/0890-5401(89)90010-2]
	56	Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
	57	ROYDEN, H.L. RealAnalysis, 2nd ed. MacMillan, New York, 1968.
	58	Robert Sloan, Types of noise in data for concept learning, Proceedings of the first annual workshop on Computational learning theory, p.91-96, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	59	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]
	60	VALIANT, L.G. Learning disjunctions of conjunctions. In Proceedings of the 9th International Conference on Artificial Intelligence (Los Angeles, Calif., Aug.), vol. 1. Morgan Kaufmann, San MateD, Calif., 1985, pp. 560-566.
	61	Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
	62	VAPNIK, V. N., AND CHERVONENKIS, A. YA. On the uniform convergence of relative frequencies of events to their probabilities. Theoret. Probi. and its Appl. 16, 2 ( 1971), 264-280.
	63	VAPNIK, V. N., AND CHERVONENKIS, A. YA. Theory of Pattern Recognition (in Russian). Nauka, Moscow, 1974.
	64	Jeffrey Scott Vitter , Jyh-Han Lin, Learning in parallel, Proceedings of the first annual workshop on Computational learning theory, p.106-124, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	65	WATANABE, S. Pattern recognition as information compression. In Frontiers of Pattern Recognition, S. Watanabe, Ed. Academic Press, Orlando, Fla., 1972.
	66	WENOCUR, R. S., AND DUDLEY, R.M. Some special Vapnik-Chervonenkis classes. Discrete Math. 33 (1981), 313-318.
	67	WINSTON, P. Learning structural descriptions from examples. In The Psychology of Computer Vision. McGraw-Hill, New York, 1975.