{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T20:31:39Z","timestamp":1779222699787,"version":"3.51.4"},"reference-count":34,"publisher":"Elsevier","isbn-type":[{"value":"9781558603776","type":"print"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1016\/b978-1-55860-377-6.50012-8","type":"book-chapter","created":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T03:00:24Z","timestamp":1404183624000},"page":"21-29","source":"Crossref","is-referenced-by-count":37,"title":["Theory and Applications of Agnostic PAC-Learning with Small Decision Trees"],"prefix":"10.1016","author":[{"given":"Peter","family":"Auer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert C.","family":"Holte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Maass","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib1","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF00116829","article-title":"Learning from noisy examples","volume":"2","author":"Angluin","year":"1988","journal-title":"Machine Learning"},{"issue":"no. 3","key":"10.1016\/B978-1-55860-377-6.50012-8_bib2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF00993345","article-title":"Trading Accuracy for Simplicity in Decision Trees","volume":"15","author":"Bohanec","year":"1994","journal-title":"Machine Learning"},{"issue":"4","key":"10.1016\/B978-1-55860-377-6.50012-8_bib3","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","article-title":"Learnability and the Vapnik-Chervonenkis dimension","volume":"36","author":"Blumer","year":"1989","journal-title":"JACM"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib4","series-title":"Classification and Regression Trees","author":"Breiman","year":"1984"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib5","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF00994006","article-title":"A further comparison of splitting rules for decision-tree induction","volume":"8","author":"Buntine","year":"1992","journal-title":"Machine Learning"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib6","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1162\/neco.1992.4.2.249","article-title":"How tight are the Vapnik-Chervonenkis hounds","volume":"4","author":"Cohn","year":"1992","journal-title":"Neural Computation"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib7","doi-asserted-by":"crossref","unstructured":"S. E. Decatur, Statistical queries and faulty PAC oracles, Proc. of the 6th ACM Conference on Computational Learning Theory, 1993, 262\u2013268.","DOI":"10.1145\/168304.168346"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib8","unstructured":"D. P. Dobkin, D. Gunopulos, W. Maass, Computing the maximum bichromatic discrepancy; with applications in computer graphics and machine learning, invited paper for a special issue of the Journal of Computer and System Sciences."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib9","unstructured":"L. Devroye, G. Lugosi, Lower bounds in pattern recognition and learning, appears in Pattern recognition."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib10","doi-asserted-by":"crossref","unstructured":"A. Danyluk, F. Provost, Small Disjuncts in Action: Learning to Diagnose Errors in the Local Loop of the Telephone Network, Proc. 10th International Conf. Machine Learning (ML'93), Morgan Kaufmann, 1993, 81\u201388.","DOI":"10.1016\/B978-1-55860-307-3.50017-4"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib11","first-page":"42","article-title":"Improving performance in neural networks using a boosting algorithm","volume":"5","author":"Druker","year":"1993"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib12","unstructured":"T. Elomaa, J. Kivinen, Learning decision trees from noisy examples, Report A-1991\u20133, Dept, of Computer Science, University of Helsinki (1991)."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib13","unstructured":"T. Elomaa, A hybrid approach to decision tree learning, Report C-1992\u201361, Dept, of Computer Science, University of Helsinki (1992)."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib14","doi-asserted-by":"crossref","unstructured":"T. Elomaa, In defense of C4.5: Notes on learning one-level decision trees, Proc. of the 11th Int. Conf. on Machine Learning, Morgan Kaufmann, 1994, 62\u201369.","DOI":"10.1016\/B978-1-55860-335-6.50016-7"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib15","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","article-title":"Decision theoretic generalizations of the PAC-modelfor neural nets and other learning applications","volume":"100","author":"Haussler","year":"1992","journal-title":"Inf. and Comp."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib16","doi-asserted-by":"crossref","unstructured":"D. Haussler, M. Kearns, H. S. Seung, N. Tishby, Rigorous learning curve boundsfrom statistical mechanics, Proc. of the 7th Annual ACM Conference on Computational Learning Theory 1994, ACM-Press (1994), 76\u201387.","DOI":"10.1145\/180139.181018"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib17","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1023\/A:1022631118932","article-title":"Very simple classification rules perform well on most commonly used datasets","volume":"11","author":"Holte","year":"1993","journal-title":"Machine Learning"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib18","doi-asserted-by":"crossref","unstructured":"K. U. Hoeffgen, H. U. Simon, K. S. Van Horn, Robust trainability of single neurons, preprint (1993)","DOI":"10.1145\/130385.130431"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib19","doi-asserted-by":"crossref","unstructured":"M. Kearns, Efficient noise-tolerant learning from statistical queries, Proc. of the 25th ACM Symp. on the Theory of Computing, 1993, 392\u2013401.","DOI":"10.1145\/167088.167200"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib20","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1137\/0222052","article-title":"Learning in the presence of malicious errors","volume":"22","author":"Kearns","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib21","doi-asserted-by":"crossref","unstructured":"M. J. Kearns, R. E. Schapire, L. M. Sellie, Toward efficient agnostic learning, Proc. of the 5th ACM Workshop on Computational Learning Theory, 1992, 341\u2013352.","DOI":"10.1145\/130385.130424"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib22","unstructured":"D. J. Lubinsky, Bivariate Splits and Consistent Split Criteria in Dichotomous Classification Trees, HD- Dissertation in Computer Science, Rutgers University (1994)."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib23","first-page":"311","article-title":"Agnostic PAC-learning of functions on analog neural nets","volume":"6","author":"Maass","year":"1994"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib24","doi-asserted-by":"crossref","unstructured":"W. Maass, Efficient Agnostic PAC-Learning with Simple Hypotheses, Proc. of the 7th Annual ACM Conference on Computational Learning Theory, 1994, 67\u201375.","DOI":"10.1145\/180139.181016"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib25","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1023\/A:1022604100933","article-title":"An empirical comparison of pruning methods for decision tree induction","volume":"4","author":"Mingers","year":"1989","journal-title":"Machine Learning"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib26","series-title":"C4.5: Programs for Machine Learning","author":"Quinlan","year":"1992"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib27","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1162\/neco.1990.2.3.374","article-title":"Exhaustive Learning","volume":"2","author":"Schwartz","year":"1990","journal-title":"Neural Computation"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib28","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1214\/aop\/1176988847","article-title":"Sharper bounds for Gaussian and empirical processes","volume":"22","author":"Talagrand","year":"1994","journal-title":"Annals of Probability"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib29","doi-asserted-by":"crossref","unstructured":"N. Tishby, E. Lavin, S. A. Solla, Consistent inference of probabilities in layered networks: Predictions and generalizations, Proc. of IJCNN 1989, Vol. II, 403\u2013409.","DOI":"10.1109\/IJCNN.1989.118274"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib30","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Comm, of the ACM"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib31","series-title":"Estimations of Dependencies Based on Empirical Data","author":"Vapnik","year":"1982"},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib32","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0004-3702(90)90037-Z","article-title":"Maximizing the predictive value of production rules","volume":"45","author":"Weiss","year":"1990","journal-title":"Art. Int."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib33","unstructured":"S. M. Weiss, I. Kapouleas, An empirical comparison of pattern recognition, neural nets, and machine learning classification methods, Proc. of the 11th Int. Joint Conf. on Art. Int. 1990, Morgan Kaufmann, 781\u2013787."},{"key":"10.1016\/B978-1-55860-377-6.50012-8_bib34","series-title":"Computer Systems that Learn","author":"Weiss","year":"1991"}],"container-title":["Machine Learning Proceedings 1995"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B9781558603776500128?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B9781558603776500128?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T05:46:22Z","timestamp":1565588782000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/B9781558603776500128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9781558603776"],"references-count":34,"URL":"https:\/\/doi.org\/10.1016\/b978-1-55860-377-6.50012-8","relation":{},"subject":[],"published":{"date-parts":[[1995]]}}}