Analysis of the generalization ability of a full decision tree

I. E. Genrikhov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 54 (2014) no. 6, pp. 1033-1047

Résumé

Classification algorithms based on full decision trees are investigated. Due to the decision tree construction under consideration, all the features satisfying a branching criterion are taken into account at each special vertex. The generalization ability of a full decision tree is estimated by applying margin theory. It is shown on real-life problems that the construction of a full decision tree leads to an increase in the margins of the learning objects; moreover, the number of objects with a positive margin increases as well. It is shown that the empirical Rademacher complexity of a full decision tree is lower than that of a classical decision tree.

Bibliographie

[1] Zhuravlev Yu. I., “Ob algebraicheskom podkhode k resheniyu zadach raspoznavaniya ili klassifikatsii”, Problemy kibernetiki, 1978, no. 33, 5–68

[2] Zhuravlev Yu. I., Ryazanov V. V., Senko O. V., “Raspoznavanie”. Matematicheskie metody. Programmnaya sistema. Prakticheskie primeneniya, FAZIS, M., 2006

[3] Djukova E. V., Peskov N. V., “Selection of typical objects in classes for recognition problems”, J. Pattern Recognition and Image Analys., 17:3 (2007), 363–367 | DOI

[4] Donskoi V. I., Bashta A. I., Diskretnye modeli prinyatiya reshenii pri nepolnoi informatsii, Tavriya, Simferopol, 1992

[5] Genrikhov I. E., Postroenie polnogo reshayuschego dereva na baze algoritma S4.5, Soobschenie po prikl. matem., VTs RAN, M., 2009

[6] Quinlan J. R., C4.5: Programs for machine learning, Morgan Kaufmann, San Mateo, 1993

[7] Genrikhov I. E., “Synthesis and analysis of recognizing procedures on the basis of full decision trees”, J. Pattern Recognition and Image Analysis, 21:1 (2011), 45–51 | DOI

[8] Genrikhov I. E., Dyukova E. V., “Klassifikatsiya na osnove polnykh reshayuschikh derevev”, Zh. vychisl. matem. i matem. fiz., 52:4 (2012), 750–761 | Zbl

[9] Genrikhov I. E., “Issledovanie pereobuchennosti raspoznayuschikh protsedur na osnove polnykh reshayuschikh derevev”, Programmnye produkty i sistemy, 96:4 (2011), 141–147

[10] Breiman L., “Random forests”, Machine Learning, 45:1 (2001), 5–32 | DOI | Zbl

[11] Holmes G., Pfahringer B., Kirkby R., Frank E., Hall M., “Multiclass alternating decision trees”, Europ. Conf. Machine Learning, Springer, Berlin, 2002, 105–122 | MR

[12] Vapnik V. N., Chervonenkis A. Ya., Teoriya raspoznavaniya obrazov, Nauka, M., 1974

[13] Vorontsov K. V., Kombinatornaya teoriya nadezhnosti obucheniya po pretsedentam, Dis. ... dok. fiz.-matem. nauk, 05-13-17, VTs RAN, M., 2010

[14] Kuncheva L. I., Combining pattern classifiers methods and algorithms, Wiley, New York, 2004 | MR | Zbl

[15] Schapire R. E., Freund Y., Lee W. S., Bartlett P. L., “Boosting the margin: a new explanation for the effectiveness of voting methods”, Annals of Statistics, 26:5 (1998), 1651–1686 | DOI | MR | Zbl

[16] Mason L., Margins and combined classifiers, A thesis submitted for the degree of doctor of philosophy of the australian national university, 1999, 118 pp.

[17] Burges C. J. C., “A tutorial on support vector machines for pattern recognition”, Data Mining and Knowledge Discovery, 2:2 (1998), 121–167 | DOI

[18] Bartlett P. L., “For valid generalization the size of the weights is more important than the size of the network”, Advances in Neural Informat. Proc. Systems, 9 (1997), 134–140

[19] Golea M., Bartlett P. L., Lee W. S., Mason L., Generalization in decision trees and DNF: Does size matter?, Advances in Neural Informat. Proc. Systems, 10 (1998), 259–265

[20] Mason L., Bartlett P. L., Golea M., “Generalization error of combined classifiers”, Comp. System Sci., 65:2 (2002), 415–438 | DOI | MR | Zbl

[21] Sauer N., “On the density of families of sets”, Combinatorial Theory Ser. A, 1972, no. 13, 145–147 | DOI | MR | Zbl

[22] Asuncion A., Newman D., UCI Machine learning repository, , University of California, School of Information and Computer Science, Irvine, 2007 http://www.ics.uci.edu/m̃learn/MLRepository.html

[23] Koltchinskii V., “Rademacher penalties and structural risk minimization”, IEEE Transactions on Information Theory, 47:5 (2001), 1902–1914 | DOI | MR | Zbl

[24] Koltchinskii V., Panchenko D., “Empirical margin distributions and bounding the generalization error of combined classifiers”, The Annals of Statistics, 30:1 (2002), 1–50 | MR | Zbl

[25] Lozano F., “Model selection using Rademacher penalization”, Proc. of the 2nd ICSC Symp. on Neural Computat., NC2000, ICSC Academic Press, Berlin, 2000

[26] Bartlett P. L., Mendelson S., “Rademacher and Gaussian complexities: Risk bounds and structural results”, J. Machine Learning Research, 3 (2002), 463–482 | MR

[27] McDiarmid C., “On the method of bounded differences”, Surveys in Combinatorics, London Mathematical Soc. Lecture Notes, 141, ed. J. Siemons, Cambridge Univ. Press, 1989, 148–188 | MR