Chinese Journal of Computers   Full Text
Title	Fast Adaboost Training Algorithm by Dynamic Weight Trimming
Authors	JIA Hui-Xing1),2) ZHANG Yu-Jin1),2)
Address	1)(National Laboratory for Information Science and Technology, Tsinghua University, Beijing 100084) 2)(Department of Electronic Engineering, Tsinghua University, Beijing 100084)
Year	2009
Issue	No.2(336—341)
Abstract &   Background	Abstract This paper presents a novel fast Adaboost training algorithm by dynamic weight trimming, which increases the training speed greatly when dealing with large datasets. At each iteration, the algorithm discards most of the samples with small weight and keeps only the samples with large weight to train the weak classifier. Then it checks the performance of the weak classifier on all the samples, if the weighted error is above 0.5, it will increase the number of training samples and retrain the weak classifier. During training, only a small portion of the samples are used to train the weak classifier, so the speed is increased greatly. Keywords Adaboost; dynamic weight trimming; machine learning Background Adaboost algorithm has demonstrates its success in face detection. Since the diversity of face pose, a lot of samples are needed to train a detector. Traditional training algorithm of Adaboost is very slow, costing about two weeks to train one detector. In order to train many detectors to evaluate the performance of different parameters, a faster training algorithm is needed. There are two strategies to increase the training speed: feature selection and sample selection. The method in this paper belongs to the latter. Since the weight of each sample changes at each round of Adaboost, all weak classifiers are needed to retrain. The training time is determined by the number of sample, so it can be reduced by discarding some small weight samples. Based on the observation, Friedman proposed static weight trimming Adaboost (SWTAdaboost), which increase the training speed greatly. However, the parameter choose for SWTAdaboost is hard for different data sets. This paper presents dynamic weight trimming Adaboost (DWTAdaboost). At each iteration, dynamic weight trimming discards most of the samples with small weight and keeps only the samples with large weight to train the weak classifier. Then it checks the performance of the weak classifier on all the samples, if the weighted error is too high, it will increase the number of training samples and retrain the weak classifier. DWTAdaboost increases the training speed greatly compared to original Adaboost algorithm while keeps the classification power of the original Adaboost compared to SWTAdaboost.