eprintid: 10999
rev_number: 6
eprint_status: archive
userid: 1
dir: disk0/00/01/09/99
datestamp: 2010-11-02 12:49:45
lastmod: 2014-04-03 22:12:28
status_changed: 2012-08-15 08:55:52
type: doctoralThesis
metadata_visibility: show
creators_name: Hörnlein, Thomas
title: Boosted Feature Generation for Classification Problems Involving High Numbers of Inputs and Classes
title_de: Merkmalsgenerierung mithilfe von Boosting zur Lösung von Klassifikationsproblemen die eine große Anzahl von Merkmalen und Klassen aufweisen
ispublished: pub
subjects: ddc-004
divisions: i-708000
adv_faculty: af-11
keywords: feature generation , classification , boosting
cterms_swd: Feature
cterms_swd: Maschinelles Lernen
cterms_swd: Boosting
abstract: 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. 
abstract_translated_text: Klassifikationsprobleme, welche hohe Anzahlen von Eingangsmerkmalen und Klassen aufweisen spielen eine wichtige Rolle auf dem Gebiet des Maschinenlernens.  Besonders Bildverarbeitung stellt ein sehr aktives Forschungsfeld mit unzähligen Anwendungen dar.   Häufig sind im Verhältnis zur Anzahl der Eingangsmerkmale nur wenig Trainingsbeispiele verfügbar.  Deswegen müssen Techniken gefunden werden, die sich nicht zu stark an die Trainingsdaten anpassen.  Aufgrund von Echtzeit-Anforderungen vieler Anwendungen, ist effiziente Implementierbarkeit ebenso von großer Bedeutung. Boosting ist ein Lernverfahren, das insbesondere im Gebiet der Bildverarbeitung erfolgreich eingesetzt wird.  Boosting konstruiert lineare Ensembles von Basis-Klassifikatoren in einer rundenbasierten Vorgehensweise.  Modulares Design und hohe Flexibilität ermöglichen einfache Anpassung an neue Problemstellungen.  Durch entsprechende Techniken kann der Rechenaufwand von Boosting-Klassifikatoren optimiert werden.  Mit den Trainingsbeispielen assoziierte Gewichte weisen auf schwer zu klassifizierende Beispiele hin, was ein Anpassung an ein gegebenes Problem während des Trainings ermöglicht. Die vorliegende Arbeit befasst sich mit dem Entwurf von Techniken welche Boosting besser an Klassifikationsprobleme mit vielen Eingangsmerkmalen und Klassen anpassen.  Im ersten Teil wird die Anwendung von Boosting für Multiklassenprobleme analysiert.  Nach einem Überblick über existierende Verfahren wird eine neue Formulierung für Basis-Klassifikatoren vorgestellt,  welche auf einer Zerlegung des Multiklassenproblems in binäre Teilprobleme basieren.  Experimente zeigen die gute Klassifikationsleistung und Recheneffizienz im Vergleich zum Stand der Technik. Im zweiten Teil der Arbeit werden Techniken, welche Boosting zum Lernen von Merkmalskombinationen verwenden, vorgestellt.  Dabei werden die Gewichte der Trainingsbeispiele herangezogen um an das aktuelle Trainingsproblem angepasste Merkmale zu lernen.  Durch die Verwendung geglätteter Splines als Basisklassifikatoren, können Gradienten-Abstiegsverfahren verwendet werden um gute Merkmale zu finden.  Experimente zeigen, dass Boosting mit linearen projektiven Merkmalen signifikant bessere Klassifikationsleistung als andere populäre Verfahren wie beispielsweise SVM und Random Forests erreichen. Das vorgestellte Verfahren wird für die Anwendung auf Bilddaten erweitert, indem verschiebungsinvariante Merkmale trainiert werden.  Diese sind inspiriert von Merkmalen welche in Convolutional Neural Networks eingesetzt werden und eine Kombination aus Faltung und Unterabtastung durchführen.  Experimente an den Beispielen Klassifikation von Ziffern und von Seitenansichten von PKWs zeigen, dass das vorgestellte System Klassifikationsleistung vergleichbar zu den besten veröffentlichen Ergebnissen erreicht.  Vorteile liegen in der einfachen Struktur und geringen Anzahl einstellbarer Trainingsparameter.
abstract_translated_lang: ger
class_scheme: msc
class_labels: 62H30, 62H35
date: 2010
date_type: published
id_scheme: DOI
id_number: 10.11588/heidok.00010999
ppn_swb: 63943794X
own_urn: urn:nbn:de:bsz:16-opus-109991
date_accepted: 2010-07-21
advisor: HASH(0x55fc36ad5d30)
language: eng
bibsort: HORNLEINTHBOOSTEDFEA2010
full_text_status: public
citation:   Hörnlein, Thomas  (2010) Boosted Feature Generation for Classification Problems Involving High Numbers of Inputs and Classes.  [Dissertation]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/10999/1/dissertation_thomas_hoernlein_2010_08_16.pdf