Performance characterization of boosting in computer vision
Terry E. Boult, Weiliang Li · 2005
Boosting algorithms have successfully been applied in machine learning systems. However, the training error and the generalization error of these algorithms can only be empirically estimated. The upper error bounds given in the literature are only loose bounds that are meaningful for a very large training set. In applications, there are no effective tools to evaluate the impact of the training sample size on the performance of boosted classifiers. The training data are blindly increased by random sampling to make the classifiers perform better. In this thesis, the fundamental questions related to the classification performance of boosting techniques, such as sample size and boosting rounds, are addressed. We present an analytical error modeling theory to characterize classification performance of boosted classifiers and demonstrate that the error statistics can be represented as a function of the collection of weak classifiers, the true distributions of the classes, and the sample size of training data. The relationship between the classification error statistics and the distribution parameters as well as the sample size can therefore be established. This offers a new approach to determine the number of samples necessary for a certain level of classification performance. Moreover, this approach provides more accurate estimates of generalization error than the existing error bounds. The analytical error modeling depends on knowledge of estimated distributions. Since it takes a weak classifier learning algorithm, using distribution parameters and sample sizes as input, to produce a collection of weak classifiers, the distribution parameter estimates lead the uncertainty to the weak classifiers. Therefore, in applications, we need to determine the necessary number of samples to estimate the distributions to be precise enough for the error modeling. To address this issue, we investigate the perturbations of weak classifiers and explore the small sample effect on the classification performance. The analytical error modeling is based on random sampling, but it can be applied to stratified sampling. While training samples are collected under different experimental context, designers need an efficient method to evaluate the number of clustered samples versus the within-cluster and the overall classification performance. In the last part, we propose an effective approach for analyzing the classification errors in stratified sampling design.