Options
1998
Doctoral Thesis
Titel
Learning with kernels
Abstract
Support Vektor (SV) Maschinen verbinden verschiedene Techniken der Statistik, des maschinellen Lernens und Neuronaler Netze. Eine Schlüsselposition fällt den Kernen zu, d.h. dem Konzept, lineare Algorithmen durch eine Abbildung in Merkmalsräume nichtlinear zu machen. Die Dissertation behandelt folgende Aspekte: (1) Erweiterungen des Support Vektor Algorithmus (2) Erweiterungen und Anwendungen kernbasierter Methoden auf andere Algorith- men wie das unüberwachte Lernen (3) Abschätzungen zur Generalisierungsfähigkeit, die besonders auf kernbasierte Methoden abgestimmt sind Nach einer kurzen Einführung in die SV Regression wird gezeigt, wie die epsilon-unempfindliche Kostenfunktion durch andere Funktionen ersetzt werden kann, während gleichzeitig die Vorteile des ursprünglichen Algorithmus erhalten bleiben, oder auch neue Eigenschaften wie automatische Parameteranpassung hinzugefügt werden. Weiterhin wird die Verbindung zwischen Kernen und Regularisierung aufgezeigt. Es folgt eine theoretische Analyse verschiedener häufig verwendeter Kerne, nebst Kriterien zur leichten Überprüfung von Mercers Bedingung. Weitere Veränderungen führen zu semiparametrischen Modellen sowie "geizigen" Näherungsverfahren. Abschließend werden drei Optimierungsalgorithmen vorgestellt, nämlich die Methode der inneren Punkte, Auswahlalgorithmen und sequentiell minimale Optimierung. Als analytisches Werkzeug fungiert hier das primär-duale Konzept der Optimierung. Auch Pseudocode wird in diesem Zusammenhang zur Verfügung gestellt. Unüberwachtes Lernen ist ein Anwendungsfall kernbasierter Methoden auf neue Probleme. Neben Kern PCA kann man das Regularisierungskonzept dazu verwenden, allgemeinere Mermalsextraktoren zu erhalten. Ein zweiter Ansatz führt zu einem stufenlosen Übergang zwischen der erzeugenden topographischen Abbildung (GTM) und Hauptkurven. Der zweite Teil der Dissertation beschäftigt sich mit Abschätzungen zur uniformen Konvergenz für die bisher vorgestellten Algorithmen und Konzepte. Dazu wird zuerst kurz ein Überblick über existierende Techniken zur Kapazitätskontrolle und Funktionalanalysis gegeben. Letztere spielen eine entscheidende Rolle, da die Klasse der Kernentwicklungen als Bild unter einem linearen Operator aufgefaßt werden kann, was Abschätzungen der Generalisierungsfähigkeit sogar in den Fällen ermöglicht, in denen klassische Ansätze wie die VC Dimension versagen bzw. zu konservative Abschätzungen geben. Insbesondere wird gezeigt, daß es möglich ist, die Überdeckungszahlen einer gegebenen Hypothesenklasse direkt zu berechnen, ohne den Umweg über die Berechnung der VC Dimension zu nehmen. Anwendungen finden die neuen Methoden bei Support Vektor Maschinen, Konvexkombinationen von Hypothesen (z.B. Boosting und spärliche Kodierung), "geizigen" Näherungsverfahren und Hauptkurven.
;
Support Vector (SV) Machines combine several techniques from statistics, machine learning and neural networks. One of the most important ingredients are kernels, i.e. the concept of transforming linear algorithms into nonlinear ones via a map into feature spaces. The present work focuses on the following issues: (1) Extensions of Support Vector Machines. (2) Extensions of kernel methods to other algorithms such as unsupervised learning. (3) Capacity bounds which are particularly well suited for kernel methods. After a brief introduction to SV regression it is shown how the classical epsilon-insensitive loss function can be replaced by other cost functions while keeping the original advantages or adding other features such as automatic parameter adaptation. Moreover the connection between kernels and regularization is pointed out. A theoretical analysis of several common kernels follows and criteria to check Mercer's condition more easily are presented. Further modifications lead to semiparametric models and greedy approximation schemes. Next three different types of optimization algorithms, namely interior point codes, subset selection algorithms, and sequential minimal optimization (including pseudocode) are presented. The primal-dual framework is used as an analytic tool in this context. Unsupervised learning is an extension of kernel methods to new problems. Besides Kernel PCA one can use the regularization to obtain more general feature extractors. A second approach leads to regularized quantization functionals which allow a smooth transition between the Generative Topographic Map and Principal Curves. The second part deals with uniform convergence bounds for the algorithms and concepts presented so far. It starts with a brief self contained overview and an introduction to functional analytic tools which play a crucial role in this problem. By viewing the class of kernel expansions as an image of a linear operator one may give bounds on the generalization ability of kernel expansions even when standard concepts like the VC dimension fail or give too conservative estimates. In particular it is shown that it is possible to compute the covering numbers of the given hypothesis classes directly instead of taking the detour via the VC dimension. Applications of the new tools to SV machines, convex combinations of hypotheses (i.e. boosting and sparse coding), greedy approximation schemes, and principal curves conclude the presentation.
ThesisNote
Zugl.: Berlin, TU, Diss., 1998
FIRST