Predicting nearly as well as the best pruning of a decision tree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Predicting nearly as well as the best pruning of a decision tree

Full text

Pdf (765 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the eighth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 61 - 68

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

David P. Helmbold	Computer and Information Sciences, University of California, Santa Cruz, CA
Robert E. Schapire	AT&T Bell Laboratories, 600 Mountain Avenue, Room 2A-424, Murray Hill, NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 10, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/225298.225305 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	Wray Buntine. Learning classification trees. Statistics and Computing, 2:63-73, 1992.
	2	Wray Lindsay Buntine. A Theory of Learning Classification Rules. PhD thesis, University of Technology, Sydney, 1990.
	3	Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
	4	Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
	5	Trevor Hastie and Daryl Pregibon. Shrinking trees. Technical report, AT~T Bell Laboratories, 1990.
	6	Jyrki Kivinen , Manfred K. Warmuth, Using experts for predicting continuous outcomes, Proceedings of the first European conference on Computational learning theory, p.109-120, October 1994, Royal Holloway, Univ. of London, United Kingdom
	7	Suk Wah Kwok , Chris Carter, Multiple decision trees, Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence, p.327-338, January 1990
	8	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]
	9	Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
	10	Jonathan J. Oliver , David Hand, Averaging over decision stumps, Proceedings of the European conference on machine learning on Machine Learning, p.231-241, May 1994, Catania, Italy
	11	J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	12	Jorma Rissanen. A universal data compression system. IEEE Transactions on Information Theory, IT-29(5):656-664, September 1983.
	13	Dana Ron , Yoram Singer , Naftali Tishby, Learning probabilistic automata with variable memory length, Proceedings of the seventh annual conference on Computational learning theory, p.35-46, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181006]
	14	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
	15	M. J. Weinberger, A. Lempel, and J. Ziv. Universal coding of finite-memory sources. IEEE Transactions on Information Theory, IT-38(3):1002-1014, May 1992.
	16	Marcelo J. Weinberger, Neff Merhav, and Meir Feder. Optimal sequential probability assignment for individual sequences. IEEE Transactions on Information Theory, IT-40(2):384-396~ March 1994.
	17	Marcelo J. Weinberger, Jorma J. Rissanen, and Meir Feder. A universal finite memory source. To appeal IEEE Transactions on Information Theory.
	18	F. M. J. Willems, Y. M. Shtarkov, and Tj. J. Tjalkens. Context tree weighting: a sequential uni~ versal source coding procedure for FSMX sources. In Proceedings 1993 IEEE International Symposium on Information Theory, page 59, 1993.
	19	Frans M. J. Willerns, Yuri M. Shtarkov, and Tjalling J. Tjalkens. The context tree weighting method: basic properties. Unpublished manuscript.

CITED BY 4

	Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States
	Fernando Pereira , Yoram Singer, An efficient extension to mixture techniques for prediction and decision trees, Proceedings of the tenth annual conference on Computational learning theory, p.114-121, July 06-09, 1997, Nashville, Tennessee, United States
	Rani Yaroshinsky , Ran El-Yaniv , Steven S. Seiden, How to Better Use Expert Advice, Machine Learning, v.55 n.3, p.271-309, June 2004
	Yoram Singer, Adaptive Mixtures of Probabilistic Transducers, Neural Computation, v.9 n.8, p.1711-1733, November 15, 1997