Geodesic
On performance of boosting in classification problem
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 15 (2015) no. 2, pp. 72-89 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The work provide some new explanation of effectiveness of the boosting methods. The main reason why boosting makes good decision functions on real world tasks is that the boosting utilizes some pattern of feature independence. We also discuss margin based risk estimations with relation to boosting and show that margin depends on complexity of composition.
Keywords: boosting, pattern recognition, machine learning, margin, misclassification probability. 
@article{VNGU_2015_15_2_a5,
     author = {V. M. Nedelko},
     title = {On performance of boosting in classification problem},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {72--89},
     year = {2015},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2015_15_2_a5/}
}
TY  - JOUR
AU  - V. M. Nedelko
TI  - On performance of boosting in classification problem
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2015
SP  - 72
EP  - 89
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VNGU_2015_15_2_a5/
LA  - ru
ID  - VNGU_2015_15_2_a5
ER  - 
%0 Journal Article
%A V. M. Nedelko
%T On performance of boosting in classification problem
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2015
%P 72-89
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/VNGU_2015_15_2_a5/
%G ru
%F VNGU_2015_15_2_a5
V. M. Nedelko. On performance of boosting in classification problem. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 15 (2015) no. 2, pp. 72-89. http://geodesic.mathdoc.fr/item/VNGU_2015_15_2_a5/

[1] Yu. I. Zhuravlev, “On algebraic approach to solving of pattern recognition or classification tasks”, Probl. Kibern., 33, no. 4, 1978, 5–68 (in Russian) | Zbl

[2] A. A. Vikent'ev, R. A. Vikent'ev, “Distances and uncertainty measures on the propositional formulas of an $n$-valued logic”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 11:2 (2011), 51–64 (in Russian) | Zbl

[3] N. G. Zagoruiko, I. A. Borisova, O. A. Kutnenko, V. V. Dyubanov, “Constructing the compressed description of dataset by the function of rival similarity”, Sib. Zh. Ind. Mat., 16:1(53) (2013), 29–41 (in Russian) | Zbl

[4] N. G. Zagoruiko, V. V. Tatarnikov, “Detecting mistakes and filling gaps in data cubes”, Sib. Zh. Ind. Mat., 17:2(58) (2014), 50–58 (in Russian) | Zbl

[5] V. M. Nedel'ko, “Regression models in the classification problem”, Sib. Zh. Ind. Mat., 17:1(57) (2014), 86–98 (in Russian) | MR | Zbl

[6] V. M. Nedel'ko, “Investigation of accuracy of crossvalidation”, JMLDA, 1:5 (2013), 526–533 (in Russian)

[7] G. S. Lbov, N. G. Startseva, “A comparison of pattern recognition algorithms with the programm tool “Poligon””, Analysis of Data and Knowledges in Expert Systems, Computational Systems, 134, ed. N. G. Zagoruiko, IM SO AN USSR, Novosibirsk, 1990, 56–66 (in Russian)

[8] E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, “On 2-capacitated peripatetic salesman problem with different weight functions”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 14:3 (2014), 3–18 (in Russian)

[9] Yu. A. Kochetov, M. S. Sivykh, A. V. Khmelev, A. V. Yakovlev, “Methods of local search for a problem on the permutation of the columns of a binary matrix”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 12:1 (2012), 91–101 (in Russian) | MR | Zbl

[10] Kel'manov A. V., Khamidullin S. A., “An Approximating Polynomial Algorithm for a Sequence Partitioning Problem”, J. of Applied and Industrial Mathematics, 8:2 (2014), 236–244 | DOI | MR | Zbl

[11] A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339 | DOI | DOI | MR | MR | Zbl

[12] D. V. Lisitsin, K. V. Lisitsin, “Estimation of the parameters of a compactly-supported model stable under the violation of compact supportedness”, Sib. Zh. Ind. Mat., 16:2(54) (2013), 109–121 (in Russian) | MR

[13] B. Yu. Lemeshko, S. B. Lemeshko, S. N. Postovalov, “Comparative analysis of the power of goodness-of-fit tests for near competing hypotheses. II: Verification of complex hypotheses”, J. Appl. Ind. Math., 4:1 (2010), 79–93 | DOI | MR | Zbl

[14] V. M. Nedel'ko, “Some aspects of estimating a quality of decision functions construction methods”, Vestn. Tom. Gos. Univ., Upr. Vich. Tekh. Inform., 2013, no. 3(24), 123–132 (in Russian)

[15] G. S. Lbov, N. G. Startseva, Logical Decision Functions and Problems of Statistical Stability of Solutions, Izdatel'stvo Instituta Matematiki, Novosibirsk, 1999 (in Russian) | MR

[16] M. Yu. Khachai, “Computational complexity of the minimum committee problem and related problems”, Dokl. Math., 73:1 (2006), 138–141 | DOI | MR | MR | Zbl

[17] Freund Y., Schapire R. E., “Experiments with a New Boosting Algorithm”, Machine Learning, Proceedings of the Thirteenth International Conference (1996), 148–156 | Zbl

[18] Mease D., Wyner A., “Evidence Contrary to the Statistical View of Boosting”, J. Mach. Learn. Res., 9, June (2008), 131–156

[19] A. A. Borovkov, “On the problem of pattern recognition”, Theory Probab. Appl., 16 (1971), 141–144 | DOI | MR | Zbl

[20] Schapire R. E., Freund Y., Bartlett P., Lee W. S., “Boosting the Margin: a New Explanation for the Effectiveness ot Voting Methods”, The Annals of Statistics, 26:5 (1998), 1651–1686 | DOI | MR | Zbl

[21] V. N. Vapnik, A. Ya. Chervonenkis, Theory of pattern recognition. Statistical problems of learning, Nauka, M., 1974 (in Russian) | MR

[22] V. I. Donskoi, “Kolmogorov complexity of classes of general recursive functions with bounded dimension”, Tavricheskij Vestn. Inform. Mat., 16:1 (2005), 25–34 (in Russian)

[23] Vorontsov K. V., “Combinatorial Probability and the Tightness of Generalization Bounds”, Pattern Recognition and Image Analysis, 18:2 (2008), 243–259 | DOI