Efficient boosted ensemble-based machine learning in the context of cascaded frameworks : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Auckland, New Zealand
The ability to both efficiently train robust classifiers and to design them for fast detection
is an important goal of machine learning. With an ever increasing amount of available data
being generated, the task of expeditiously producing real-time capable classifiers is becoming more
challenging. In the context of the increasing complexity of the task, ensemble-based learning
methods have proven themselves to be effective approaches for satisfying these requirements.
Ensemble methods produce a number of weak models that are strategically combined into a
single classifier. They have been particularly effective when combined with boosting algorithms
and strategies that structure the ensembles into cascades. The strength of cascaded-ensembles
lies in the separate-and-conquer approach they employ during the training of each layer. Class
decision-boundaries for trivial cases are learned in the early rounds, while more difficult decision
boundaries are refined with each succeeding layer. In a two-class problem domain, non-target
instances learned in initial layers are removed and replaced by more complex samples, frequently
referred to as bootstrapping. With this procedure, efficient coarse-to-fine learning is accomplished.
The contribution of this thesis lies in three main areas that centre around the concept of
improving the efficiency in the training and execution process. The first explored ways in which
the conventional ensemble-cascades could be combined with an even more aggressive separateand-
conquer strategy that further partitions the ensemble inside each layer. The focus was on
the two-class learning problem and used face detection as the medium to observe the trade-offs
involved concerning both the accuracy and the efficiency of the resulting classifiers. The algorithm
was further developed in a way that enabled the bootstrapping of positive samples within a cascade,
alongside the conventional approach that bootstraps only the negative samples. Secondly,
the negative effect of dynamic environments on static classifiers on binary class problems was considered.
A method was developed which enabled the cascaded classifiers to efficiently adapt to
the changing environment on domains with high volume streaming data. This environment was
simulated using face detection as well. Lastly, the open problem of creating integrated multiclass
cascades was researched and an algorithm was devised.
Overall, the findings have shown that invariably a trade-off is incurred between reduced training
runtimes resulting from aggressive separate-and-conquer strategies and the accuracy of the
final classifiers. Using the CMU MIT test dataset, the experiments showed that though the proposed
positive sample bootstrapping component succeeded in significantly reducing the training
runtimes without compromising the accuracy, the general decomposition strategy did lower the
accuracy when compared to the benchmark Viola-Jones classifiers. The proposed adaptive cascade
learning algorithm for drifting concepts was also evaluated on a face detection problem set. The
results demonstrated its ability to effectively adapt to dynamic environments in high speed data
streams without requiring explicit re-training of the individual classifiers. The multiclass cascaded
algorithm was compared to three existing algorithms on 18 UCI datasets. It was found to be, on
average, several times faster to train and to execute, while generating comparable accuracy rates.
The algorithm exhibited scalability to large datasets but was found to be susceptible to producing
overly complex classifiers on datasets with a large number of class labels.