Modification of the WaldBoost algorithm to improve the efficiency of solving pattern recognition problems in real-time
https://doi.org/10.32362/2500-316X-2019-7-5-20-29
Abstract
The implementation of the WaldBoost algorithm is considered, and its modification is proposed, which allows to significantly reduce the number of weak classifiers to achieve a given classification accuracy. The efficiency of the proposed algorithm is shown by specific examples. The paper studies modifications of compositions (ensembles) of algorithms for solving real-time pattern recognition problems. The aim of the study is to improve the known machine learning algorithms for pattern recognition using a minimum amount of time (the minimum number of used classifiers) and with a given accuracy of the results. We consider the implementation of the WaldBoost algorithm, which combines two algorithms: adaptive boosting of weak classifiers – AdaBoost (adaptive boosting), which has a high generalizing ability, and the sequential probability ratio test – SPRT (Wald test), which is the optimal rule of decision-making when distinguishing two hypotheses. It is noted that when using the WaldBoost, the values of the actual probability of classification errors, as a rule, are less than given because of the approximate boundaries of the SPRT, so that the classification process uses an excessive series of weak classifiers. In this regard, we propose a modification of the WaldBoost based on iterative refinement of the decision boundaries, which can significantly reduce the number of used weak classifiers required for pattern recognition with a given accuracy. The efficiency of the proposed algorithm is shown by specific examples. The results are confirmed by statistical modeling on several data sets. It is noted that the results can be applied in the refinement of other cascade classification algorithms.
About the Authors
A. N. Chesalin
MIREA – Russian Technological University
Russian Federation
Russian Federation
Cand. of Sci. (Engineering), Associate Professor of the Chair of Computer and Information Security, Institute of Cybernetics,
78, Vernadskogo pr., Moscow 119454
S. Ya. Grodzenskiy
MIREA – Russian Technological University
Russian Federation
Russian Federation
Dr. of Sci., Professor of the Chair of Metrology and Standardization, Institute of Physics and Technology,
78, Vernadskogo pr., Moscow 119454
M. Yu. Nilov
MIREA – Russian Technological University
Russian Federation
Russian Federation
Postgraduate Student, the Chair of Metrology and Standardization, Institute of Physics and Technology,
78, Vernadskogo pr., Moscow 119454
A. N. Agafonov
MIREA – Russian Technological University
Russian Federation
Russian Federation
Master, the Chair of Computer and Information Security, Institute of Cybernetics,
78, Vernadskogo pr., Moscow 119454
References
1. Freund Y., Schapire R. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comp. & System Sci. 1997;55(1):119-139. https://doi.org/10.1006/jcss.1997.1504
2. Friedman J. Greedy function approximation: A gradient boosting machine. The Annals of Statistics. 2001;29(5):1189-1232. https://doi.org/10.1109/SMRLO.2016.83.
3. Wald A. Sequential Analysis. NY: John Wiley and Sons, 1947. 212 р.
4. Tartakovsky A., Nikiforov I., Basseville M. Sequential analysis: Hypothesis testing and changepoint detection. Boca Raton: CRC press/Taylor & Francis, 2015. 579 р.
5. Сhesalin A., Grodzenskiy S., Grodzenskiy Ya. About the effectiveness of the statistical sequential analysis in the reliability trials. In: 2016 Second Int. Symp. on Stochastic Models in Reliability Engineering, Life Science and Operations Management (SMRLO). Beer Sheva, Israel, February 15–18, 2016. P. 475-480. https://doi.org/10.1109/SMRLO.2016.83
6. Yanjing O., Nan C., Michael B. An efficient multivariate control charting mechanism based on SPRT. Int. J. Production Res. 2015;53(7):1937-1949. https://doi.org/10.1080/00207543.2014.925601
7. Sochman J., Matas J. WaldBoost – Learning for time constrained sequential detection. In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). June 20–25, 2005. P. 150-156. https://doi.org/10.1109/CVPR.2005.373
8. Chesalin A., Grodzenskiy S. The algorithm of calculating the refined boundaries of sequential criteria based on the likelyhood ratio. In: Proceed. of the Int. Seminar on Electron Devices Design and Production (SED). April 23–24, 2019. Prague, Czech Republic, 2019. 4 p. IEEE Catalog Number: CFP19P59-CDR. https://doi.org/10.1109/SED.2019.8798445
9. Zhu J., Rosset S., Zou H., Hastie T. Multi-class AdaBoost. Statistics and its Interface. 2006;2(1): 21 p. https://doi.org/10.4310/SII.2009.v2.n3.a8
Supplementary files
|
|
1. Fig. 1. Simulated datasets (training sample): "○“corresponds to the class y = +1, ” × " – to the class y = 1. | |
| Subject | ||
| Type | Исследовательские инструменты | |
View
(806KB)
|
Indexing metadata ▾ | |
Review
For citations:
Chesalin A.N., Grodzenskiy S.Ya., Nilov M.Yu., Agafonov A.N. Modification of the WaldBoost algorithm to improve the efficiency of solving pattern recognition problems in real-time. Russian Technological Journal. 2019;7(5):20-29. (In Russ.) https://doi.org/10.32362/2500-316X-2019-7-5-20-29
Views:
837
Email this article 