Constructive evaluation of the complete cross-validation for threshold classification

I. S. Guz

Matematičeskaâ biologiâ i bioinformatika, Tome 6 (2011) no. 2, pp. 173-189.

Résumé

Significant part of classification problems, in particular problems in medical diagnostics and bioinformatics, can be naturally reduced to the problem of selection of the optimal thresholds for features that take real values, which is studied in this article. Combinatorial upper and lower bounds of the complete cross-validation (CCV) for one-dimensional binary classification problem are introduced. Solution for this problem is sought in the family of monotone threshold classifiers. Iterative procedure for CCV bounds evaluation is introduced that has polynomial complexity of the number of objects in the problem. This procedure is also used for the detection of anomalous objects that can be filtered out to reduce upper CCV bound.

Bibliographie

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

[2] Vorontsov K.V., “Optimizatsionnye metody lineinoi i monotonnoi korrektsii v algebraicheskom podkhode k probleme raspoznavaniya”, ZhVM i MF, 40:1 (2000), 166–176 | MR | Zbl

[3] Guz I.S., “Nelineinye monotonnye kompozitsii klassifikatorov”, Matematicheskie metody raspoznavaniya obrazov–13, MAKS Press, M., 2007, 111–114

[4] Rudakov K.V., Vorontsov K.V., “O metodakh optimizatsii i monotonnoi korrektsii v algebraicheskom podkhode k probleme raspoznavaniya”, Doklady RAN, 367:3 (1999), 314–317 | MR | Zbl

[5] Vorontsov K.V., “Kombinatornyi podkhod k otsenke kachestva obuchaemykh algoritmov”, Matematicheskie voprosy kibernetiki, 13, Fizmatlit, M., 2004, 5–36

[6] Vorontsov K.V., “Kombinatornye obosnovaniya obuchaemykh algoritmov”, ZhVM i MF, 44:11 (2004), 2099–2112 | MR | Zbl

[7] Vorontsov K.V., “Kombinatornye otsenki kachestva obucheniya po pretsedentam”, Doklady RAN, 394:2 (2004), 175–178 | MR | Zbl

[8] Vorontsov K.V., “Combinatorial probability and the tightness of generalization bounds”, Pattern Recognition and Image Analysis, 18:2 (2008), 243–259 | DOI

[9] Vorontsov K.V., “Splitting and similarity phenomena in the sets of classifiers and their effect on the probability of overfitting”, Pattern Recognition and Image Analysis, 19:3 (2009), 412–420 | DOI | MR

[10] Vorontsov K.V., “Tochnye otsenki veroyatnosti pereobucheniya”, Doklady RAN, 429:1 (2009), 15–18 | Zbl

[11] Vapnik V.N., Vosstanovlenie zavisimostei po empiricheskim dannym, Nauka, M., 1979

[12] Zhuravlev Yu.I., “Ob algebraicheskom podkhode k resheniyu zadach raspoznavaniya ili klassifikatsii”, Problemy kibernetiki, 33 (1978), 5–68 | Zbl

[13] Rudakov K.V., Algebraicheskaya teoriya universalnykh i lokalnykh ogranichenii dlya algoritmov raspoznavaniya, Dissertatsiya na soiskanie uchenoi stepeni d.f.-m.n., VTs RAN, M., 1992

[14] Hastie T., Tibshirani R., Friedman J., The elements of statistical learning, Springer-Verlag, 2001 | MR | Zbl

[15] Vapnik V., The nature of statistical learning theory, 2, Springer-Verlag, New York, 2000 | MR | Zbl

[16] Rudakov K.V., “Monotonnye i unimodalnye korrektiruyuschie operatsii dlya algoritmov raspoznavaniya”, Matematicheskie metody raspoznavaniya obrazov–VII, Tez. dokl., M., 1995

[17] Kohavi R., “A study of cross-validation and bootstrap for accuracy estimation and model selection”, 14th International Joint Conference on Artificial Intelligence (Palais de Congres Montreal, Quebec, Canada), 1995, 1137–1145; URL: http://citeseer.ist.psu.edu/kohavi95study.html

[18] Mullin M., Sukthankar R., Complete cross-validation for nearest neighbor classifiers, Proceedings of International Conference on Machine Learning, 2000 URL: http://citeseer.ist.psu.edu/309025.html