Geodesic
Constructive evaluation of the complete cross-validation for threshold classification
Matematičeskaâ biologiâ i bioinformatika, Tome 6 (2011), pp. 173-189.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{MBB_2011_6_a9,
     author = {I. S. Guz},
     title = {Constructive evaluation of the complete cross-validation for threshold classification},
     journal = {Matemati\v{c}eska\^a biologi\^a i bioinformatika},
     pages = {173--189},
     publisher = {mathdoc},
     volume = {6},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MBB_2011_6_a9/}
}
TY  - JOUR
AU  - I. S. Guz
TI  - Constructive evaluation of the complete cross-validation for threshold classification
JO  - Matematičeskaâ biologiâ i bioinformatika
PY  - 2011
SP  - 173
EP  - 189
VL  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MBB_2011_6_a9/
LA  - ru
ID  - MBB_2011_6_a9
ER  - 
%0 Journal Article
%A I. S. Guz
%T Constructive evaluation of the complete cross-validation for threshold classification
%J Matematičeskaâ biologiâ i bioinformatika
%D 2011
%P 173-189
%V 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MBB_2011_6_a9/
%G ru
%F MBB_2011_6_a9
I. S. Guz. Constructive evaluation of the complete cross-validation for threshold classification. Matematičeskaâ biologiâ i bioinformatika, Tome 6 (2011), pp. 173-189. http://geodesic.mathdoc.fr/item/MBB_2011_6_a9/

[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 <ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=1757695'>1757695</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:0988.68156'>0988.68156</ext-link>

[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 <ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=1724217'>1724217</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:0963.68172'>0963.68172</ext-link>

[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 <ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=2129861'>2129861</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1075.93049'>1075.93049</ext-link>

[7] Vorontsov K.V., “Kombinatornye otsenki kachestva obucheniya po pretsedentam”, Doklady RAN, 394:2 (2004), 175–178 <ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=2089748'>2089748</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1219.94059'>1219.94059</ext-link>

[8] Vorontsov K.V., “Combinatorial probability and the tightness of generalization bounds”, Pattern Recognition and Image Analysis, 18:2 (2008), 243–259 <ext-link ext-link-type='doi' href='https://doi.org/10.1134/S1054661808020090'>10.1134/S1054661808020090</ext-link>

[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 <ext-link ext-link-type='doi' href='https://doi.org/10.1134/S1054661809030055'>10.1134/S1054661809030055</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=2606198'>2606198</ext-link>

[10] Vorontsov K.V., “Tochnye otsenki veroyatnosti pereobucheniya”, Doklady RAN, 429:1 (2009), 15–18 <ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1185.68613'>1185.68613</ext-link>

[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 <ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:0426.68092'>0426.68092</ext-link>

[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 <ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=1851606'>1851606</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:0973.62007'>0973.62007</ext-link>

[15] Vapnik V., The nature of statistical learning theory, 2, Springer-Verlag, New York, 2000 <ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=1719582'>1719582</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:0934.62009'>0934.62009</ext-link>

[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: <ext-link ext-link-type='uri' href='http://citeseer.ist.psu.edu/kohavi95study.html'>http://citeseer.ist.psu.edu/kohavi95study.html</ext-link>

[18] Mullin M., Sukthankar R., Complete cross-validation for nearest neighbor classifiers, Proceedings of International Conference on Machine Learning, 2000 URL: <ext-link ext-link-type='uri' href='http://citeseer.ist.psu.edu/309025.html'>http://citeseer.ist.psu.edu/309025.html</ext-link>