• Startseite
• Recherche
• Veröffentlichen
• Hilfe

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-23769
URL: http://www.freidok.uni-freiburg.de/volltexte/2376/

Haasdonk, Bernard

Transformation knowledge in pattern analysis with kernel methods - distance and integration kernels

Transformationswissen in Musteranalyse mit Kernmethoden - Distanz- und Integrationskerne

Kurzfassung in Englisch

Modern techniques for data analysis and machine learning are so called kernel methods. The most famous and successful one is represented by the support vector machine (SVM) for classification or regression tasks. Further examples are kernel principal component analysis for feature extraction or other linear classifiers like the kernel perceptron. The fundamental ingredient in these methods is the choice of a kernel function, which computes a similarity measure between two input objects. For good generalization abilities of a learning algorithm it is indispensable to incorporate problem-specific a-priori knowledge into the learning process. The kernel function is an important element for this.

This thesis focusses on a certain kind of a-priori knowledge namely transformation knowledge. This comprises explicit knowledge of pattern variations that do not or only slightly change the pattern's inherent meaning e.g. rigid movements of 2D/3D objects or transformations like slight stretching, shifting, rotation of characters in optical character recognition etc. Several methods for incorporating such knowledge in kernel functions are presented and investigated:

(1) Invariant distance substitution kernels (IDS-kernels): In many practical questions the transformations are implicitly captured by sophisticated distance measures between objects. Examples are nonlinear deformation models between images. Here an explicit parameterization would require an arbitrary number of parameters. Such distances can be incorporated in distance- and inner-product-based kernels.

(2) Tangent distance kernels (TD-kernels): Specific instances of IDS-kernels are investigated in more detail as these can be efficiently computed. We assume differentiable transformations of the patterns. Given such knowledge, one can construct linear approximations of the transformation manifolds and use these efficiently for kernel construction by suitable distance functions.

(3) Transformation integration kernels (TI-kernels): The technique of integration over transformation groups for feature extraction can be extended to kernel functions and more general group, non-group, discrete or continuous transformations in a suitable way.

Theoretically, these approaches differ in the way the transformations are represented and in the adjustability of the transformation extent. More fundamentally, kernels from category 3 turn out to be positive definite, kernels of types 1 and 2 are not positive definite, which is generally required for being usable in kernel methods. This is the motivation to investigate the theoretical meaning of such indefinite kernels. The finding is that on given data these kernels correspond to inner products in pseudo-Euclidean spaces. Here certain kernel methods, in particular SVMs, have a reasonable geometrical and theoretical interpretation.

Practical applicability of the kernels is demonstrated in addition to the theoretical properties. For these experiments, support vector classification on various types of data has been performed. The datasets comprise standard benchmark datasets for optical character recognition like USPS and MNIST or real-world biological data resulting from micro-Raman-spectroscopy with the goal of bacteria identification.

In addition to the demonstration that transformation knowledge can be involved in kernel functions in different ways and that these can be practically applied, there are more fundamental findings and perspectives. We demonstrate and theoretically argue that indefinite kernels can be used or tolerated by kernel methods, as exemplified for the SVM. There exist statements about the training-algorithm, the resulting solutions and a reasonable geometric interpretation. This opens up mainly two directions. Firstly, these insights facilitate the process of kernel design, which hitherto is mainly restricted to positive definite functions. In particular, this enables SVMs to be used widely in other fields like distance-based learning, i.e. in all analysis problems, where dissimilarities between objects are available. Secondly, the investigation of suitability or robustness of other kernel methods than SVMs with respect to indefinite kernels seems very promising.

Kurzfassung in Deutsch

Moderne Techniken der Datenanalyse und des maschinellen Lernens stellen so genannte Kernmethoden dar. Die bekannteste und erfolgreichste Vertreterin dieser Klasse von Verfahren ist die Supportvektor-Maschine (SVM) für Klassifikations- oder Regressionsaufgaben. Weitere Beispiele sind die Kern-Hauptachsen-Transformation zur Merkmalsextraktion oder andere lineare Klassifikatoren wie das Kern-Perzeptron. Der grundlegende Baustein in diesen Methoden ist die Wahl einer Kernfunktion, die ein Ähnlichkeitsmaß zwischen Paaren von Eingabe-Objekten berechnet. Für gute Generalisierungsfähigkeit eines Lernalgorithmus ist es unabdingbar, dass vorhandenes problemspezifisches Vorwissen in den Lernprozess eingebracht wird. Die Kernfunktion ist hierfür eines der entscheidendsten Glieder.

Diese Dissertation konzentriert sich auf eine bestimmte Art von Vorwissen, nämlich Vorwissen über Transformationen. Dies bedeutet, dass explizite Kenntnis von Mustervariationen vorhanden ist, welche die inhärente Bedeutung der Objekte nicht oder nur unwesentlich verändern. Beispiele sind rigide Bewegungen von 2D- und 3D-Objekten oder Transformationen wie geringe Streckung, Verschiebung oder Rotation von Buchstaben in der optischen Zeichenerkennung. Es werden mehrere generische Methoden präsentiert und untersucht, welche solches Vorwissen in Kernfunktionen berücksichtigen:

(1) Invariante Distanzsubstitutions-Kerne (IDS-Kerne): In vielen praktischen Fragestellungen sind die Transformationen implizit in ausgefeilten Distanzmaßen zwischen Objekten erfasst. Beispiele sind nichtlineare Deformationsmodelle zwischen Bildern. Hier würde eine explizite Parametrisierung der Transformationen beliebig viele Parameter benötigen. Solche Maße können in distanz- und skalarprodukt-basierte Kerne eingebracht werden.

(2) Tangentendistanz-Kerne (TD-Kerne): Spezielle Beispiele der IDS-Kerne werden detaillierter untersucht, weil diese effizient berechnet und weit angewandt werden können. Wir setzen differenzierbare Transformationen der Muster voraus. Bei solchem gegebenen Vorwissen kann man lineare Approximationen der Transformations-Mannigfaltigkeiten konstruieren und mittels geeigneter Distanzfunktionen effizient zur Konstruktion von Kernfunktionen verwenden.

(3) Transformations-Integrations-Kerne (TI-Kerne): Die Technik der Gruppen-Integration über Transformationen zur Merkmalsextraktion kann in geeigneter Weise erweitert werden auf Kernfunktionen und allgemeinere Transformationen, die nicht notwendigerweise eine Gruppe bilden.

Theoretisch unterscheiden sich diese Verfahren darin, wie sie die Transformationen repräsentieren und die Transformations-Weiten regelbar sind. Grundlegender erweisen sich Kerne aus Kategorie 3 als positiv definit, Kerne der Gattung 1 und 2 sind nicht positiv definit, was generell als notwendige Voraussetzung zur Verwendung in Kernmethoden angesehen wird. Dies war die Motivation dafür zu untersuchen, was die theoretische Bedeutung von solchen indefiniten Kernen ist. Das Ergebnis zeigt, dass diese Kerne auf gegebenen Daten Skalarprodukte in pseudo-euklidischen Räumen darstellen. In diesen haben bestimmte Kernmethoden, insbesondere die SVM, eine sinnvolle geometrische und theoretische Interpretation.

Zusätzlich zu theoretischen Eigenschaften wird die praktische Anwendbarkeit der Kerne demonstriert. Für diese Experimente wurde Supportvektor-Klassifikation auf einer Vielzahl von Datensätzen durchgeführt. Diese Datensätze umfassen Standard-Benchmark-Datensätze der optischen Zeichenerkennung, wie USPS und MNIST, und biologische Anwendungsdaten, die aus der Raman-Mikrospektroskopie stammen und zur Identifikation von Bakterien dienen.

Zusätzlich zur Erkenntnis, dass Transformations-Wissen auf verschiedene Weise in Kernfunktionen eingebracht werden kann und diese praktisch anwendbar sind, gibt es grundlegendere Einsichten und Ausblicke. Wir demonstrieren und erläutern am Beispiel der SVM, dass indefinite Kerne in Kernmethoden verwendet oder toleriert werden können. Es existieren Aussagen über den Trainings-Algorithmus und die Eigenschaften der Lösungen und eine sinnvolle geometrische Interpretation. Dies eröffnet im Wesentlichen zwei Richtungen. Erstens vereinfachen diese Einsichten den Prozess des Kerndesigns, welcher bislang hauptsächlich auf positiv definite Kerne beschränkt war. Insbesondere eröffnet dies die Möglichkeit der weiten Anwendbarkeit von SVM in anderen Gebieten wie distanzbasiertem Lernen, d.h. für Analyse-Probleme, bei denen Unterschiedsmaße zwischen Objekten verfügbar sind. Zweitens erscheint die Untersuchung der Anwendbarkeit von indefiniten Kernen in weiteren Kernmethoden sehr vielversprechend.