Computational learning theory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computational learning theory: survey and selected bibliography

Full text

Pdf (2.11 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 351 - 369

Year of Publication: 1992

ISBN:0-89791-511-9

Author

Dana Angluin

Department of Computer Science, Yale University, P. O. Box 2158, New Haven, CT

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 239, Citation Count: 16

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/129712.129746 What is a DOI?

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	Naoki Abe, Polynomial learnability of semilinear sets, Proceedings of the second annual workshop on Computational learning theory, p.25-40, December 1989, Santa Cruz, California, United States
	2	Naoki Abe , Manfred K. Warmuth , Jun-ichi Takeuchi, Polynomial learnability of probabilistic concepts with respect to the Kullback-Leibler divergence, Proceedings of the fourth annual workshop on Computational learning theory, p.277-289, August 05-07, 1991, Santa Cruz, California, United States
	3	Naoki Abe , Manfred K. Warmuth, On the computational complexity of approximating distributions by probabilistic automata, Proceedings of the third annual workshop on Computational learning theory, p.52-66, August 06-08, 1990, Rochester, New York, United States
	4	Howard Aizenstein , Leonard Pitt, Exact learning of read-twice DNF formulas (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.170-179, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185366]
	5	D. Aldous and U. Vazirani. A Markovian extension of Valiant's learning model, in Proceedings of the $1st Annual Symposium on Foundations of Computer Science, pages 392-396. IEEE Computer Society Press, 1990.
	6	D. Angluin. Finding patterns common to a set of strings, j. Gomp. Sys. Sci., 21:46-62, 1980.
	7	D. Angluin. Learning k-term D NF formulas using queries and counterexamples. Technical report, Yale University, YALE/DCS/RR-559, 1987.
	8	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]
	9	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	10	Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
	11	D. Angluin, M. Frazier, and L. Pitt. Learning conjunctions of Horn clauses. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 186-192. IEEE Computer Society Press, 1990.
	12	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning Read-Once Formulas with Queries, University of California at Berkeley, Berkeley, CA, 1989
	13	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
	14	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	15	Dana Angluin , Donna K. Slonim, Learning monotone DNF with an incomplete membership oracle, Proceedings of the fourth annual workshop on Computational learning theory, p.139-146, August 05-07, 1991, Santa Cruz, California, United States
	16	Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983 [doi>10.1145/356914.356918]
	17	Martin Anthony , Norman Biggs , John Shawe-Taylor, The learnability of formal concepts, Proceedings of the third annual workshop on Computational learning theory, p.246-257, August 06-08, 1990, Rochester, New York, United States
	18	S. Arikawa, S. Goto, S. Ohsuga, and T. Yokomori, editors. Proceedings of the First International Workshop on Algorithmic Learning Theory. Japanese Society for Artificial Intelligence, Tokyo, October 8-10, 1990.
	19	S. Arikawa, A. Maruoka, and T. Sato, editors. Proceedings of the Second International Workshop on Algorithmic Learning Theory. Japanese Society for Artificial Intelligence, Tokyo, October 23- 25, 1991.
	20	J. M. Barzdin and R. V. Freivalds. On the prediction of general reeursive functions. Soy. Math. Dokl., 13:1224-1228, 1972.
	21	E. B. Baum, On learning a union of half spaces, Journal of Complexity, v.6 n.1, p.67-101, Mar. 1990 [doi>10.1016/0885-064X(90)90012-3]
	22	Eric B. Baum, Polynomial time algorithms for learning neural nets, Proceedings of the third annual workshop on Computational learning theory, p.258-272, August 06-08, 1990, Rochester, New York, United States
	23	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
	24	Shai Ben-David , Alon Itai , Eyal Kushilevtiz, Learning by distances, Proceedings of the third annual workshop on Computational learning theory, p.232-245, August 06-08, 1990, Rochester, New York, United States
	25	Gyora M. Benedek , Alon Itai, Learnability by fixed distributions, Proceedings of the first annual workshop on Computational learning theory, p.80-90, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	26	A. Blum. Separating distribution-free and mistake-bound learning models over the boolean domain. In Proc. 31st Annual Symposium on Foundations of Computer Science, pages 211-218. IEEE Computer Society Press, 1990.
	27	Avrim Blum , Lisa Hellerstein , Nick Littlestone, Learning in the presence of finitely or infinitely many irrelevant attributes, Proceedings of the fourth annual workshop on Computational learning theory, p.157-166, August 05-07, 1991, Santa Cruz, California, United States
	28	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]
	29	Avrim Blum , Mona Singh, Learning functions of k terms, Proceedings of the third annual workshop on Computational learning theory, p.144-153, August 06-08, 1990, Rochester, New York, United States
	30	A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12158]
	31	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]
	32	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]
	33	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning arithmetic read-once formulas, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.370-381, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129747]
	34	William J. Bultman , Wolfgang Maass, Fast identification of geometric objects with membership queries, Proceedings of the fourth annual workshop on Computational learning theory, p.337-353, August 05-07, 1991, Santa Cruz, California, United States
	35	J. Case and C. Smith. Comparison of identification criteria for machine inductive inference. Theor. Comp. Sci., 25:193-220, 1983.
	36	A. Ehrenfeucht , David Haussler, Learning decision trees from random examples, Proceedings of the first annual workshop on Computational learning theory, p.182-194, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	37	Paul Fisher , Stefan Pölt , Hans Ulrich Simon, Probably almost Bayes decisions, Proceedings of the fourth annual workshop on Computational learning theory, p.88-96, August 05-07, 1991, Santa Cruz, California, United States
	38	Paul Fischer , Hans Ulrich Simon, On learning ring-sum-expansions, SIAM Journal on Computing, v.21 n.1, p.181-192, Feb. 1992 [doi>10.1137/0221014]
	39	Sally Jean Floyd, On space-bounded learning and the vapnik-chervonenkis dimension, 1989
	40	Sally Floyd, Space-bounded learning and the Vapnik-Chervonenkis dimension, Proceedings of the second annual workshop on Computational learning theory, p.349-364, December 1989, Santa Cruz, California, United States
	41	Yoav Freund, Boosting a weak learning algorithm by majority, Proceedings of the third annual workshop on Computational learning theory, p.202-216, August 06-08, 1990, Rochester, New York, United States
	42	Proceedings of the third annual workshop on Computational learning theory, July 1990
	43	Merrick L. Furst , Jeffrey C. Jackson , Sean W. Smith, Improved learning of AC0 functions, Proceedings of the fourth annual workshop on Computational learning theory, p.317-325, August 05-07, 1991, Santa Cruz, California, United States
	44	W. Gasarch and C. Smith. Learning via queries. In Proc. 29th Annual Symposium on Foundations of Computer Science, pages 130-137. IEEE Computer Society Press, 1988.
	45	Sally Ann Goldman , Ronald L. Rivest, Learning binary relations, total orders, and read-once formulas, 1990
	46	Sally A. Goldman , Michael J. Kearns, On the complexity of teaching, Proceedings of the fourth annual workshop on Computational learning theory, p.303-314, August 05-07, 1991, Santa Cruz, California, United States
	47	Sally A. Goldman , Michael J. Kearns , Robert E. Schapire, On the sample complexity of weak learning, Proceedings of the third annual workshop on Computational learning theory, p.217-231, August 06-08, 1990, Rochester, New York, United States
	48	S. Goldman, R. Rivest, and R. Schapire. Learning binary relations and total orders. In Proceedings of the Thirtieth Annual Symposium on Foundations of Computer Science, pages 46-51. IEEE Computer Society Press, 1989.
	49	S. A. Goldman, M. J. Kearns, and R. E. Schapire. Exact identification of circuits using fixed points of amplification functions. In Proc. 31st Annual Symposium on Foundations of Computer Science, pages 193-202. IEEE Computer Society Press, 1990.
	50	O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions, in Proc. 25th Annual Symposium on Foundations of Computer Science, pages 464-479. IEEE, 1984.
	51	T. Hancock. Identifying #u-formula decision trees with queries. Technical report, Harvard University Center for Research in Computing Technology, TR- 16-90, 1990.
	52	Thomas R. Hancock, Identifying μ-formula decision trees with queries, Proceedings of the third annual workshop on Computational learning theory, p.23-37, August 06-08, 1990, Rochester, New York, United States
	53	Thomas R. Hancock, Learning 2u DNF formulas and ku decision trees, Proceedings of the fourth annual workshop on Computational learning theory, p.199-212, August 05-07, 1991, Santa Cruz, California, United States
	54	T. Hancock, M. Golea, and M. Marchand. Learning nonoverlapping perceptron networks from examples and membership queries. Technical report, Harvard University Center for Research in Computing Technology, TR-26-91, 1991.
	55	Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
	56	Thomas Hancock , Yishay Mansour, Learning monotone ku DNF formulas on product distributions, Proceedings of the fourth annual workshop on Computational learning theory, p.179-183, August 05-07, 1991, Santa Cruz, California, United States
	57	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]
	58	D. Haussler. Generalizing the PAC model: sample size bounds from metric dimension-based uniform convergence results. In Proceedings of the Thirtieth Annual Symposium on Foundations of Computer Science, pages 40-45. IEEE Computer Society Press, 1989.
	59	David Haussler, Learning Conjunctive Concepts in Structural Domains, Machine Learning, v.4 n.1, p.7-40, October 1989 [doi>10.1023/A:1022601210986]
	60	David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	61	D. Haussler, M. Kearns, N. Littlestone, and M. Warmuth. Equivalence of models for polynomial learnability. Technical report, University of California, Santa Cruz, UCSC-CRL-88-06, 1988.
	62	D. Haussler, N. Littlestone, and M. Warmuth. Predicting {0,1}-functions on randomly drawn points. In Proc. 29th Symposium on Foundations of Computer Science, pages 100-109. IEEE Computer Society Press, 1988.
	63	Proceedings of the first annual workshop on Computational learning theory, December 1988
	64	Lisa Hellerstein , Richard M. Karp, On characterizing and learning some classes of read-once functions, 1989
	65	L. ttellerstein and M. Karpinski. Computational complexity of learning read-once formulas over different bases. Technical report, International Computer Science Institute, Berkeley, CA, TR- 91-014, 1991.
	66	David P. Helmbold , Philip M. Long, Tracking drifting concepts using random examples, Proceedings of the fourth annual workshop on Computational learning theory, p.13-23, August 05-07, 1991, Santa Cruz, California, United States
	67	David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, Proceedings of the third annual workshop on Computational learning theory, p.288-302, August 06-08, 1990, Rochester, New York, United States
	68	David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning Nested Differences of Intersection-Closed Concept Classes, Machine Learning, v.5 n.2, p.165-196, Jun. 1990 [doi>10.1023/A:1022696716689]
	69	Oscar H. Ibarra , Tao Jiang, Learning regular languages from counterexamples, Proceedings of the first annual workshop on Computational learning theory, p.371-385, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	70	Hiroki Ishizaka, Learning simple deterministic languages, Proceedings of the second annual workshop on Computational learning theory, p.162-174, December 1989, Santa Cruz, California, United States
	71	M. Jerrum. Simple translation-invariant concepts are hard to learn. Technical report, University of Edinburgh, Department of Computer Science, CSR-12-91, 1991.
	72	Tao Jiang , Ming Li, On the complexity of learning strings and sequences, Proceedings of the fourth annual workshop on Computational learning theory, p.367-371, August 05-07, 1991, Santa Cruz, California, United States
	73	M. J. Kearns, The computational complexity of machine learning, Harvard University, Cambridge, MA, 1990
	74	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]
	75	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]
	76	Michael Kearns , Leonard Pitt, A polynomial-time algorithm for learning k-variable pattern languages from examples, Proceedings of the second annual workshop on Computational learning theory, p.57-71, December 1989, Santa Cruz, California, United States
	77	M. Kearns and R. Schapire. Efficient distributionfree learning of probabilistic concepts. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 382-391. IEEE Computer Society Press, 1990.
	78	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]
	79	Jyrki Kivinen, Reliable and useful learning, Proceedings of the second annual workshop on Computational learning theory, p.365-380, December 1989, Santa Cruz, California, United States
	80	R. Klette and R. Wiehagen. Research in the theory of inductive inference by GDR mathematicians-a survey. Information Sciences, 22:149- 169, 1980.
	81	Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.455-464, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103466]
	82	Philip D. Laird, Learning from good and bad data, Kluwer Academic Publishers, Norwell, MA, 1988
	83	P. Laird. A survey of computational learning theory. In R. Banerji, editor, Formal Techniques in Artificial Intelligence: A Sourcebook, pages 173- 215. Elsevier Science Publishers, 1990.
	84	M. Li. Towards a DNA sequencing theory: learning a string. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 125-134. IEEE Computer Society Press, 1990.
	85	M. Li and P. Vitanyi. A theory of learning simple concept8 under .simple distributions and average case complexity for the universal distribution. In Proceedings of the 30th Annual Symposium on Foundations of Compuler Science, pages 34-39. IEEE Computer Society Press, 1989.
	86	N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. In Proceedings of the Thzrtieth Annual Symposium on Foundations of Computer Science, pages 574- 579. IEEE Computer Society Press, 1989.
	87	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]
	88	Nicholas Littlestone, Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow, Proceedings of the fourth annual workshop on Computational learning theory, p.147-156, August 05-07, 1991, Santa Cruz, California, United States
	89	Nicholas Littlestone , Philip M. Long , Manfred K. Warmuth, On-line learning of linear functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.465-475, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103467]
	90	N. Littlestone and M. Warmuth. The weighted majority algorithm. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 256-261. IEEE Computer Society Press, 1989.
	91	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
	92	Wolfgang Maass, On-line learning with an oblivious environment and the power of randomization, Proceedings of the fourth annual workshop on Computational learning theory, p.167-178, August 05-07, 1991, Santa Cruz, California, United States
	93	W. Maass and G. Turan. On the complexity of learning from counterexamples. In Proceedings of the 30#h Annual Symposium on Foundations of Computer Science, pages 262-267. IEEE Computer Society Press, 1989.
	94	W. Maass and G. Turan. On the complexity of learning from counterexamples and membership queries. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 203-210. IEEE Computer Society Press, 1990.
	95	Oded Maler , Amir Pnueli, On the learnability of infinitary regular sets, Proceedings of the fourth annual workshop on Computational learning theory, p.128-138, August 05-07, 1991, Santa Cruz, California, United States
	96	S. Miyano, A. Shinohara, and T. Shinohara. Which classes of elementary formal systems are polynomial-time learnable? In Proceedings of the Second Workshop on Algorithmic Learning Theory, pages 139-150. Japanese Society for Artificial Intelligence, 1991.
	97	M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
	98	B. K. Natarajan, On learning from exercises, Proceedings of the second annual workshop on Computational learning theory, p.72-87, December 1989, Santa Cruz, California, United States
	99	B. K. Natarajan, On Learning Sets and Functions, Machine Learning, v.4 n.1, p.67-97, October 1989 [doi>10.1023/A:1022605311895]
	100	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]
	101	Balas Kausik Natarajan, Machine learning: a theoretical approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	102	D. Osherson, M. Stob, and S. Weinstein. Systems That Learn. MIT Press, Cambridge, MA, 1986.
	103	G. Pagallo and D. ttaussler. A greedy method for learning #-DNF functions under the uniforn distribution. Technical report, University of California at Santa Cruz, UCSC-CRL-89-12, 1989.
	104	R. Board , L. Pitt, On the necessity of Occam algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.54-63, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100223]
	105	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]
	106	L. Pitt , M. K. Warmuth, The minimum consistent DFA problem cannot be approximated within and polynomial, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.421-432, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73048]
	107	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	108	Sara Porat , Jerome A. Feldman, Learning automata from ordered examples, Proceedings of the first annual workshop on Computational learning theory, p.386-396, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	109	Vijay Raghavan , Stephen R. Schach, Learning switch configurations, Proceedings of the third annual workshop on Computational learning theory, p.38-51, August 06-08, 1990, Rochester, New York, United States
	110	Proceedings of the second annual workshop on Computational learning theory, December 1989
	111	R. Rivest and R. Schapire. Diversity-based inference of finite automata. In Proc. 28th IEEE Symposium on Foundations of Computer Science, pages 78-87. IEEE Computer Society Press, 1987.
	112	R. Rivest and R. Schapire. A new approach to unsupervised learning in deterministic environments, in Proc. of the 4th International Workshop on Machine Learning, pages 364-375. Morgan Kaufmann Publishers, Inc., San Mateo, CA, 1987.
	113	R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]
	114	Ronald L. Rivest , Robert Sloan, Learning complicated concepts reliably and usefully, Proceedings of the first annual workshop on Computational learning theory, p.69-79, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	115	Ronald L. Rivest , Robert H. Sloan, A New Model for Inductive Inference, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.13-28, March 01, 1988
	116	Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
	117	Yasubumi Sakakibara, On learning from queries and counterexamples in the presence of noise, Information Processing Letters, v.37 n.5, p.279-284, March 14, 1991 [doi>10.1016/0020-0190(91)90220-C]
	118	Yasubumi Sakakibara, Learning context-free grammars from structural data in polynomial time, Theoretical Computer Science, v.76 n.2-3, p.223-242, Nov. 21, 1990 [doi>10.1016/0304-3975(90)90017-C]
	119	Robert E. Schapire, Pattern languages are not learnable, Proceedings of the third annual workshop on Computational learning theory, p.122-129, August 06-08, 1990, Rochester, New York, United States
	120	Robert E. Schapire, Learning probabilistic read-once formulas on product distributions, Proceedings of the fourth annual workshop on Computational learning theory, p.184-198, August 05-07, 1991, Santa Cruz, California, United States
	121	R. E. Schapire. The strength of weak learnability. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 28-33. IEEE Computer Society Press, 1989.
	122	Robert Elias Schapire, The design and analysis of efficient learning algorithms, Massachusetts Institute of Technology, Cambridge, MA, 1992
	123	George Shackelford , Dennis Volper, Learning k-DNF with noise in the attributes, Proceedings of the first annual workshop on Computational learning theory, p.97-103, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	124	Ayumi Shinohara , Satoru Miyano, Teachability in computational learning, New Generation Computing, v.8 n.4, p.337-347, 1991 [doi>10.1007/BF03037091]
	125	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
	126	R. H. Sloan. Computational Learning Theory: New Models and Algorithms. PhD thesis, MIT, 1989. Issued as MIT/LCS/TR-448.
	127	L. Valiant. Deductive learning. Phil. Trans. Roy. Soc. Lond. A, 312:441-446, 1984.
	128	L. Valiant. Learning disjunctions of conjunctions. In Proc. 9th 1jCAL pages 560-566. IJCAI, 1985.
	129	L. Valiant. A view of computational learning theory. In C. W. Gear, editor, Computation # Cognition: Proceedings of the First NEC Research Symposium, pages 32-51. SIAM, 1991.
	130	Proceedings of the fourth annual workshop on Computational learning theory, August 1991
	131	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]
	132	L. G. Valiant, Functionality in neural nets, Proceedings of the first annual workshop on Computational learning theory, p.28-39, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	133	Karsten Verbeurgt, Learning DNF under the uniform distribution in quasi-polynomial time, Proceedings of the third annual workshop on Computational learning theory, p.314-326, August 06-08, 1990, Rochester, New York, United States
	134	Jeffrey Scott Vitter , Jyh-Han Lin, Learning in parallel, Information and Computation, v.96 n.2, p.179-202, Feb. 1992 [doi>10.1016/0890-5401(92)90047-J]
	135	Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
	136	Kenji Yamanishi, A learning criterion for stochastic rules, Proceedings of the third annual workshop on Computational learning theory, p.67-81, August 06-08, 1990, Rochester, New York, United States
	137	Takashi Yokomori, Polynomial-time learning of very simple grammars from positive data, Proceedings of the fourth annual workshop on Computational learning theory, p.213-227, August 05-07, 1991, Santa Cruz, California, United States

CITED BY 16

	Aaron Feigelson , Lisa Hellerstein, Learning conjunctions of two unate DNF formulas (extended abstract): computational and informational results, Proceedings of the ninth annual conference on Computational learning theory, p.255-265, June 28-July 01, 1996, Desenzano del Garda, Italy
	Rodney G. Downey , Patricia A. Evans , Michael R. Fellows, Parameterized learning complexity, Proceedings of the sixth annual conference on Computational learning theory, p.51-57, July 26-28, 1993, Santa Cruz, California, United States
	Michael Frazier , Leonard Pitt, CLASSIC learning, Proceedings of the seventh annual conference on Computational learning theory, p.23-34, July 12-15, 1994, New Brunswick, New Jersey, United States
	Leslie G. Valiant, Rationality, Proceedings of the eighth annual conference on Computational learning theory, p.3-14, July 05-08, 1995, Santa Cruz, California, United States
	Roni Khardon , Dan Roth, Learning to reason, Journal of the ACM (JACM), v.44 n.5, p.697-725, Sept. 1997
	Eyal Kushilevitz , Dan Roth, On learning visual concepts and DNF formulae, Proceedings of the sixth annual conference on Computational learning theory, p.317-326, July 26-28, 1993, Santa Cruz, California, United States
	Dan Roth , Ming-Hsuan Yang , Narendra Ahuja, Learning to recognize three-dimensional objects, Neural Computation, v.14 n.5, p.1071-1103, May 2002
	Mark Burgin , Allen Klinger, Experience, generations, and limits in machine learning, Theoretical Computer Science, v.317 n.1-3, p.71-91, June 4, 2004
	Russell Greiner , Adam J. Grove , Dan Roth, Learning cost-sensitive active classifiers, Artificial Intelligence, v.139 n.2, p.137-174, August 2002
	György Turán, Lower bounds for PAC learning with queries, Proceedings of the sixth annual conference on Computational learning theory, p.384-391, July 26-28, 1993, Santa Cruz, California, United States
	Hema Raghavan , James Allan, An interactive algorithm for asking and incorporating feature feedback into support vector machines, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands
	Hema Raghavan , Omid Madani , Rosie Jones, Active Learning with Feedback on Features and Instances, The Journal of Machine Learning Research, 7, p.1655-1686, 12/1/2006
	Brian J. Ross, Probabilistic Pattern Matching and the Evolution of Stochastic Regular Expressions, Applied Intelligence, v.13 n.3, p.285-300, November-December 2000
	György Turán, Remarks on computational learning theory, Annals of Mathematics and Artificial Intelligence, v.28 n.1-4, p.43-45, 2000
	Atsuyuki Morishima , Seiichi Koizumi , Hiroyuki Kitagawa , Satoshi Takano, Enabling End-users to Construct Data-intensive Web-sites from XML Repositories: An Example-based Approach, Proceedings of the 27th International Conference on Very Large Data Bases, p.703-704, September 11-14, 2001
	Hema Raghavan , Omid Madani , Rosie Jones, InterActive feature selection, Proceedings of the 19th international joint conference on Artificial intelligence, p.841-846, July 30-August 05, 2005, Edinburgh, Scotland

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
A. General Literature

F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES

I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE
I.2.6 Learning
Subjects: Induction; Concept learning

General Terms:
Algorithms, Theory

REVIEW

"Sally Goldman : Reviewer"

This comprehensive survey of the published results in computational learning theory describes the basic probably approximately correct (PAC) model and some commonly studied variations. Also, a large number of positive and negative results draw more...

Collaborative Colleagues:

Dana Angluin: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player