Boosted Feature Generation for Classification Problems Involving High Numbers of Inputs and Classes

Classification problems involving high numbers of inputs and classes play an important role in the field of machine learning. Image classification, in particular, is a very active field of research with numerous applications. In addition to their high number, inputs of image classification problems often show significant correlation. Also, in proportion to the number of inputs, the number of available training samples is usually low. Therefore techniques combining low susceptibility to overfitting with good classification performance have to be found. Since for many tasks data has to be processed in real time, computational efficiency is crucial as well. Boosting is a machine learning technique, which is used successfully in a number of application areas, in particular in the field of machine vision. Due to it's modular design and flexibility, Boosting can be adapted to new problems easily. In addition, techniques for optimizing classifiers produced by Boosting with respect to computational efficiency exist. Boosting builds linear ensembles of base classifiers in a stage-wise fashion. Sample-weights reflect whether training samples are hard-to-classify or not. Therefore Boosting is able to adapt to the given classification problem over the course of training. The present work deals with the design of techniques for adapting Boosting to problems involving high numbers of inputs and classes. In the first part, application of Boosting to multi-class problems is analyzed. After giving an overview of existing approaches, a new formulation for base-classifiers solving multi-class problems by splitting them into pair-wise binary subproblems is presented. Experimental evaluation shows the good performance and computational efficiency of the proposed technique compared to state-of-the-art techniques. In the second part of the work, techniques that use Boosting for feature generation are presented. These techniques use the distribution of sample weights, produced by Boosting, to learn features that are adapted to the problems solved in each Boosting stage. By using smoothing-spline base classifiers, gradient descent schemes can be incorporated to find features that minimize the cost function of the current base classifier. Experimental evaluation shows, that Boosting with linear projective features significantly outperforms state-of-the-art approaches like e.g. SVM and Random Forests. In order to be applicable to image classification problems, the presented feature generation scheme is extended to produce shift-invariant features. The utilized features are inspired by the features used in Convolutional Neural Networks and perform a combination of convolution and subsampling. Experimental evaluation for classification of handwritten digits and car side-views shows that the proposed system is competitive to the best published results. The presented scheme has the advantages of being very simple and involving a low number of design parameters only.