On the necessity of Occam algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the necessity of Occam algorithms

Full text

Pdf (872 KB)

Source

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

Baltimore, Maryland, United States

Pages: 54 - 63

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

R. Board	Department of Computer Science, University of Illinois, Urbana, Illinois
L. Pitt	Department of Computer Science, University of Illinois, Urbana, Illinois

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 27, Citation Count: 9

Additional Information:

references cited by index terms 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/100216.100223 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	D. Angluin. Negative results for equivalence queries. Technical Report YALEU/DCS/RR-648, Department of Computer Science, Yale University, September 1988. To appear, Machine Learning. A preliminary version appears in the Proceedings of the 1989 Workshop on Computational Learning Theory.
	2	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]
	3	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]
	4	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]
	5	David Haussler, Learning Conjunctive Concepts in Structural Domains, Machine Learning, v.4 n.1, p.7-40, October 1989 [doi>10.1023/A:1022601210986]
	6	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
	7	Proceedings of the first annual workshop on Computational learning theory, December 1988
	8	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]
	9	William of Occam. Quodlibeta Septem (in translation). Circa 1320.
	10	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]
	11	Leonard Pitt , Manfred K. Warmuth, The minimum consistent DFA problem cannot be approximated within any polynomial, Journal of the ACM (JACM), v.40 n.1, p.95-142, Jan. 1993 [doi>10.1145/138027.138042]
	12	Proceedings of the second annual workshop on Computational learning theory, December 1989
	13	R. Schapire. The strength of weak learnability. Technical Report MIT/LCS/TM-415, MIT Laboratory for Computer Science, October 1989. To appear, Machine Learning. A preliminary version appears in the Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, October, 1989.
	14	R. Sloan. Computational learning theory: New models and algorithms. Technical Report MIT/LCS/TR-448, Ph.D. Thesis, MIT, 1989.
	15	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]
	16	Manfred K. Warmuth, Towards Representation Independence in PAC Learning, Proceedings of the International Workshop on Analogical and Inductive Inference, p.78-103, October 01-06, 1989

CITED BY 9

	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada
	Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996
	William Evans , Sridhar Rajagopalan , Umesh Vazirani, Choosing a reliable hypothesis, Proceedings of the sixth annual conference on Computational learning theory, p.269-276, July 26-28, 1993, Santa Cruz, California, United States
	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
	Fei Yu , Victor Leung, Mobility-based predictive call admission control and bandwidth reservation in wireless cellular networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.5, p.577-589, 5 April 2002
	Eiji Takimoto , Akira Maruoka, Conservativeness and monotonicity for learning algorithms, Proceedings of the sixth annual conference on Computational learning theory, p.377-383, July 26-28, 1993, Santa Cruz, California, United States
	Ming Li , John Tromp , Paul Vitányi, Sharpening Occam's razor, Information Processing Letters, v.85 n.5, p.267-274, 16 March 2003
	Brendan Juba, Estimating relatedness via data compression, Proceedings of the 23rd international conference on Machine learning, p.441-448, June 25-29, 2006, Pittsburgh, Pennsylvania
	Misha Alekhnovich , Mark Braverman , Vitaly Feldman , Adam R. Klivans , Toniann Pitassi, The complexity of properly learning simple concept classes, Journal of Computer and System Sciences, v.74 n.1, p.16-34, February, 2008