On decompositions of decision function quality measure

V. M. Nedel'ko

The Bulletin of Irkutsk State University. Series Mathematics, Tome 33 (2020), pp. 64-79

Résumé

A comparative analysis of two approaches to the decomposition of quality criterion of decision functions is carried out. The first approach is the bias-variance decomposition. This is the most well-known decomposition that is used in analyzing the quality of decision function construction methods, in particular for justifying some ensemble methods. This usually assumes a monotonous dependence of the bias and variance on the complexity. Recent studies show that this is not always true. The second approach (G.S. Lbov, N.G. Startseva, 1989) is a decomposition into a measure of adequacy and a measure of statistical stability (robustness). The idea of the approach is to decompose the prediction error into approximation error and statistical error. In this paper we propose a method of statistical estimation of the components of both decompositions on real data. We compare the dependencies of these components on the complexity of the decision function. Non-normalized margin is used as a general measure of complexity. The results of the study and the experiments on UCI data show significant qualitative similarities in behavior of the bias and the adequacy measure and between the variance and the statistical stability measure. At the same time, there is a fundamental difference between the considered decompositions, in particular, with increasing complexity, the measure of adequacy cannot increase, while the bias first decreases, but at high enough values of complexity usually starts to grow.

Détail

Keywords: machine learning, decision function complexity.
Mots-clés : bias-variance decomposition

Bibliographie

[1] Baliuk A. S., “Complexity Lower Bound for Boolean Functions in the Class of Extended Operator Forms”, The Bulletin of Irkutsk State University. Series Mathematics, 30 (2019), 125–140 | DOI | Zbl

[2] Berikov V., “Semi-Supervised Classification Using Multiple Clustering And Low-Rank Matrix Operations”, Lecture Notes in Computer Science, 11548, 2019, 529–540 | DOI | Zbl

[3] Domingos P., “A Unified Bias-Variance Decomposition and its Applications”, Proceedings of the Seventeenth International Conference on Machine Learning, Morgan Kaufmann, Stanford, CA, 2000, 231–238

[4] Dyakonov A. G., Bias and variance, 2016 (In Russian)

[5] Heskes T., “Bias/Variance Decompositions for Likelihood-Based Estimators”, Neural Computation, 10:6 (1998), 1425–1433 | DOI

[6] Kanevskiy D., Vorontsov K., “Cooperative Coevolutionary Ensemble Learning”, Multiple Classifier Systems, 7th International Workshop, MCS 2007, Proceedings (Prague, Czech Republic, May 23–25, 2007), 469–478 | DOI

[7] Khachay M., Khachay D., “Attainable accuracy guarantee for the k-medians clustering in [0, 1]”, Optimization Letters, 13:8 (2019), 1837–1853 | DOI | MR | Zbl

[8] Kotsiantis S., “Bagging and boosting variants for handling classifications problems: A survey”, The Knowledge Engineering Review, 29:1 (2014), 78–100 | DOI

[9] Kuncheva L. I., Skurichina M., Duin R. P. W., “An experimental study on diversity for bagging and boosting with linear classifiers”, Information Fusion, 2002, no. 3, 245–258 | DOI | MR

[10] Kuncheva L., Vetrov D., “Evaluation of stability of k-means cluster ensembles with respect to random initialization”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28:11 (2006), 1798–1808 | DOI

[11] Lbov G. S., Startseva N. G., “On Some a Concept of Complexity of a Strategy of Nature in Pattern Recognition”, Computational systems, Data Analysis in Expert Systems, 117, Novosibirsk, 1986, 91–102 (In Russian) | MR

[12] Lbov G. S., Startseva N. G., “Complexity of Distributions in the Classification Problem”, Doklady RAS, 338:5 (1994), 592–594 (In Russian) | Zbl

[13] Lbov G. S., Startseva N. G., Logical Decision Functions and the Problem of Statistical Robustness of Solutions, Institute of Mathematics Publ., Novosibirsk, 211 pp. (In Russian) | MR

[14] Nedel'ko V.M., “Some aspects of estimating a quality of decision functions construction methods”, Tomsk State University Journal of Control and Computer Science, 2013, no. 3 (24), 123–132 (In Russian)

[15] Nedel'ko V.M., “On performance of boosting in classification problem”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 15:2 (2015), 72–89 (In Russian) | Zbl

[16] Nedel'ko V.M., “Tight risk bounds for histogram classifier”, Proceedings of IFOST-2016 11th International Forum on Strategic Technology, 2016, 267–271 | DOI

[17] Nedel'ko V.M., “On the Maximization of Quadratic Weighted Kappa”, The Bulletin of Irkutsk State University. Series Mathematics, 23 (2018), 36–45 (in Russian) | DOI | MR | Zbl

[18] Nedel'ko V.M., “Statistical Fitting Criterion on the Basis of Cross-Validation Estimation”, Pattern Recognition and Image Analysis, 28:3 (2018), 510–515 | DOI

[19] Rudakov K. V., “Mathematical Foundations for Processing High Data Volume, Machine Learning, and Artificial Intelligence”, Pattern Recognit. Image Anal., 29 (2019), 339–343 | DOI

[20] Stuart G., Bienenstock E., Doursat R., “Neural networks and the bias/variance dilemma”, Neural Computation, 4 (1992) | DOI

[21] Zhuravlev Y. I., Ryazanov V. V., Aslanyan L. H. et al., “On a Classification Method for a Large Number of Classes”, Pattern Recognit. Image Anal., 29 (2019), 366–376 | DOI