Transformation knowledge in pattern analysis with kernel methods [Elektronische Ressource] : distance and integration kernels / von Bernard Haasdonk

Bernard Haasdonk, [e-mail]

Sujets

• Informatik

Informations

• Publié par: albert-ludwigs-universitat_freiburg
• Publié le: 01 janvier 2006
• Nombre de lectures: 21
• Langue: English
• Poids de l'ouvrage: 10 Mo

Extrait

Dissertation
zur Erlangung des Doktorgrades
der Fakulta¨t fu¨r Angewandte Wissenschaften
an der Albert-Ludwigs-Universitat Freiburg im Breisgau¨
Transformation Knowledge in
Pattern Analysis with Kernel
Methods
–
Distance and Integration Kernels
von
Dipl.-Math. Bernard Haasdonk
24. Mai 2005ii
Dekan: Prof. Dr. Jan G. Korvink
Prufungskommission: Prof. Dr. Wolfram Burgard (Vorsitz)¨
Prof. Dr. Luc De Raedt (Beisitz)
Prof. Dr. Hans Burkhardt (Gutachter)
Prof. Dr. Bernhard Scholkopf (Gutachter)¨
Datum der Disputation: 18. November 2005Acknowledgement
Firstly, IwanttothankmysupervisorProf.Dr.-Ing.HansBurkhardtforgivingmethe
possibilityandwidesupportfortheresearchwhichhasledtothisthesis. Inparticular,
the excellent technical environment, the availability of various interesting application
fields and the scientific freedom have combined to be an excellent basis for indepen-
dent research. The generous support of research travel enabled me to establish many
important and fruitful contacts. Similarly, I am deeply grateful to Prof. Dr. Bernhard
Sch¨olkopf who was a constant source of motivation through his own related work and
various guiding hints, many of which find themselves realized in the present thesis. I
am very glad that he agreed to act as the second referee. In particular, I am very
thankful for being given the opportunity to visit his group for a talk, several weeks
of research and the machine learning summer school MLSS 2003. During these occa-
sions, many fruitful discussions were possible, especially with Dr. Ulrike von Luxburg,
Matthias Hein and Dr. Olivier Bousquet. Large parts of the experiments were based
on third party data which were kindly provided by Dr. Elzbieta Pekalska, Dr. Thore
Graepel, DanielKeysersandRainerTypke. Ialsowanttomentionmyformerandcur-
rent colleagues at the pattern recognition group who contributed through discussions,
providingdataand, lastbutnotleast,encouragementwhenrequired. Thewholegroup
and also the members of the associated group of Prof. Dr. Thomas Vetter provided a
wonderful, friendly and personal atmosphere, which played a very important role for
me. Therefore, I want to mention outstandingly Nikos Canterakis, Olaf Ronneberger,
Dr.-Ing. Lothar Bergen, Dimitrios Katsoulas, Claus Bahlmann, Stefan Rahmann, Dr.
Volker Blanz and Klaus Peschke. A big“thank you”also goes to three of my former
students, Nicolai Mallig, Harald Stepputtis and Anselm Vossen, who all contributed
through discussions, ideas, implementations and scientific results to the development
of the subjects in three main chapters.
Last but not least, I dedicate the thesis to other important persons. On the one
hand,tomyparents,whosupportedtheunhindereddevelopmentofmyworkinvarious
ways. On the other hand, to my girlfriend Heide, who also had to live with all the ups
and downs of my work during the last several years, but always managed to remind
me of other important things in life.
Kunheim, April 2005 Bernard Haasdonk
iiiivZusammenfassung
ModerneTechnikenderDatenanalyseunddesmaschinellenLernensstellensogenannte
Kernmethoden dar. Die bekannteste und erfolgreichste Vertreterin dieser Klasse von
VerfahrenistdieSupportvektor-Maschine(SVM)fu¨rKlassifikations-oderRegressions-
aufgaben. WeitereBeispielesinddieKern-Hauptachsen-TransformationzurMerkmals-
extraktion oder andere lineare Klassifikatoren wie das Kern-Perzeptron. Der grundle-
¨gende Baustein in diesen Methoden ist die Wahl einer Kernfunktion, die ein Ahn-
lichkeitsmaß zwischen Paaren von Eingabe-Objekten berechnet. Fur gute Generali-¨
sierungsf¨ahigkeit eines Lernalgorithmus ist es unabdingbar, dass vorhandenes pro-
blemspezifisches Vorwissen in den Lernprozess eingebracht wird. Die Kernfunktion
ist hierfu¨r eines der entscheidendsten Glieder.
DieseDissertationkonzentriertsichaufeinebestimmteArtvonVorwissen, n¨amlich
Vorwissen uber Transformationen. Dies bedeutet, dass explizite Kenntnis von Muster-¨
variationen vorhanden ist, welche die inh¨arente Bedeutung der Objekte nicht oder nur
unwesentlich verandern. Beispiele sind rigide Bewegungen von 2D- und 3D-Objekten¨
oder Transformationen wie geringe Streckung, Verschiebung oder Rotation von Buch-
staben in der optischen Zeichenerkennung. Es werden mehrere generische Methoden
pra¨sentiert und untersucht, welche solches Vorwissen in Kernfunktionen beru¨cksichti-
gen.
1. Invariante Distanzsubstitutions-Kerne (IDS-Kerne):
In vielen praktischen Fragestellungen sind die Transformationen implizit in aus-
gefeiltenDistanzmaßenzwischenObjektenerfasst. BeispielesindnichtlineareDe-
formationsmodelle zwischen Bildern. Hier wu¨rde eine explizite Parametrisierung
der Transformationen beliebig viele Parameter beno¨tigen. Solche Maße ko¨nnen
in distanz- und skalarprodukt-basierte Kerne eingebracht werden.
2. Tangentendistanz-Kerne (TD-Kerne):
Spezielle Beispiele der IDS-Kerne werden detaillierter untersucht, weil diese ef-
fizient berechnet und weit angewandt werden konnen. Wir setzen differenzier-¨
bare Transformationen der Muster voraus. Bei solchem gegebenen Vorwissen
kann man lineare Approximationender Transformations-Mannigfaltigkeitenkon-
struierenundmittelsgeeigneterDistanzfunktioneneffizientzurKonstruktionvon
Kernfunktionen verwenden.
3. Transformations-Integrations-Kerne (TI-Kerne):
DieTechnikderGruppen-Integrationu¨berTransformationenzurMerkmalsextrak-
tion kann in geeigneter Weise erweitert werden auf Kernfunktionen und allge-
meinere Transformationen, die nicht notwendigerweise eine Gruppe bilden.
vvi
Theoretisch unterscheiden sich diese Verfahren darin, wie sie die Transformationen
repra¨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 Kern-
methoden angesehen wird. Dies war die Motivation dafur zu untersuchen, was die the-¨
oretische Bedeutung von solchen indefiniten Kernen ist. Das Ergebnis zeigt, dass diese
KerneaufgegebenenDatenSkalarprodukteinpseudo-euklidischenR¨aumendarstellen.
In diesen haben bestimmte Kernmethoden, insbesondere die SVM, eine sinnvolle geo-
metrische und theoretische Interpretation.
Zusatzlich zu theoretischen Eigenschaften wird die praktische Anwendbarkeit der¨
Kerne demonstriert. Fu¨r diese Experimente wurde Supportvektor-Klassifikation auf
einer Vielzahl von Datensatzen durchgefuhrt. Diese Datensatze umfassen Standard-¨ ¨ ¨
Benchmark-Datens¨atze der optischen Zeichenerkennung, wie USPS und MNIST, und
biologische Anwendungsdaten, die aus der Raman-Mikrospektroskopie stammen und
zur Identifikation von Bakterien dienen.
Zus¨atzlich 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 erla¨utern am
Beispiel der SVM, dass indefinite Kerne in Kernmethoden verwendet oder toleriert
werdenko¨nnen. EsexistierenAussagenu¨berdenTrainings-AlgorithmusunddieEigen-
schaften der Losungen und eine sinnvolle geometrische Interpretation. Dies eroffnet im¨ ¨
Wesentlichen zwei Richtungen. Erstens vereinfachen diese Einsichten den Prozess des
Kerndesigns, welcher bislang hauptsachlich auf positiv definite Kerne beschrankt war.¨ ¨
Insbesondere ero¨ffnet dies die Mo¨glichkeit der weiten Anwendbarkeit von SVM in an-
deren Gebieten wie distanzbasiertem Lernen, d.h. fur Analyse-Probleme, bei denen¨
Unterschiedsmaße zwischen Objekten verfugbar sind. Zweitens erscheint die Unter-¨
suchung der Anwendbarkeit von indefiniten Kernen in weiteren Kernmethoden sehr
vielversprechend.Abstract
Modern techniques for data analysis and machine learning are so called kernel meth-
ods. 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 per-
ceptron. Thefundamentalingredientinthesemethodsisthechoiceofakernelfunction,
which computes a similarity measure between two input objects. For good generaliza-
tion 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 ele-
ment 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 ob-
jects 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):
Inmanypracticalquestionsthetransformationsareimplicitlycapturedbysophis-
ticated distance measures between objects. Examples are nonlinear deformation
models between images. Here an explicit parameterization would require an