@PhDThesis{Sochman-TR-2009-24, IS = { zkontrolovano 15 Jan 2013 }, UPDATE = { 2011-08-01 }, author = {{\v S}ochman, Jan}, supervisor = {Matas, Ji{\v r}{\'\i} }, title = {Learning for Sequential Classification}, school = {Center for Machine Perception, K13133 FEE Czech Technical University}, address = {Prague, Czech Republic}, year = {2009}, month = {December}, day = {2}, type = {{PhD Thesis CTU--CMP--2009--24}}, issn = {1213-2365}, pages = {85}, figures = {31}, authorship = {100}, psurl = {[Sochman-TR-2009-24.pdf]}, project = {CTU 0307313, FP6-IST-027113, Dur IG2003-2 062}, annote = {In many computer vision classification problems, both the error rates and the evaluation time characterises the quality of a decision. Yet most of the learning algorithms do not optimise the evaluation time explicitly. We show that such learning problems can be formalised in the framework of sequential decision-making. The proposed formalisation has been already studied (without learning) by Wald in the 1940's, who proved that the optimal sequential strategy in terms of the shortest average time to decision (number of measurements used) is the sequential probability ratio test (SPRT). We built on the SPRT test and enlarge its capabilities to problems with dependent measurements. We show, how the limitations of SPRT to a priori ordered measurements and known joint probability density functions can be overcome. We propose a learning algorithm, called WaldBoost, which handles the evaluation time vs. error rate trade-off during the learning, which integrates the AdaBoost learning algorithm for measurement selection and ordering and the joint probability density estimation, with the optimal SPRT decision strategy. The WaldBoost algorithm is tested on the face detection problem. The reached detection results are superior to the state of the art methods in the average evaluation time and comparable in the detection rates. Next, we show how existing (slow) binary decision algorithms can be approximated by a (fast) trained WaldBoost classifier. The WaldBoost learning is used to minimise the decision time of the emulated algorithm while guaranteeing predefined approximation precision. Moreover, we show that the WaldBoost algorithm together with bootstrapping is able to efficiently handle an effectively unlimited number of training examples provided by the implementation of the approximated algorithm. Two interest point detectors, the Hessian-Laplace and the Kadir-Brady saliency detectors, are emulated to demonstrate the approach. Experiments show that while the repeatability and matching scores are similar for the original and emulated algorithms, a 9-fold speed-up for the Hessian-Laplace detector and a 142-fold speed-up for the Kadir-Brady detector is achieved. For the Hessian-Laplace detector, the achieved speed is similar to SURF, a popular and very fast handcrafted modification of Hessian-Laplace; the WaldBoost emulator approximates the output of the Hessian-Laplace detector more precisely. Finally, an on-line learning version of the WaldBoost algorithm is proposed. On-line boosting allows to adapt a trained classifier to changing environmental conditions or to use sequentially available training data. Yet, two important problems in the on-line boosting training remain unsolved: (i) classifier evaluation speed optimisation and, (ii) automatic classifier complexity estimation. We show how the on-line boosting can be combined with Wald's sequential decision theory to solve both of the problems. The properties of the proposed on-line WaldBoost algorithm are demonstrated on a visual tracking problem. The complexity of the classifier is changing dynamically depending on the difficulty of the problem. On average, a speedup of a factor of 5-10 is achieved compared to the non-sequential on-line boosting.}, keywords = {sequential decision making, AdaBoost, sequential probability ratio test, Wald-Boost, machine learning, face detection, interest point detection, tracking}, }