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

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

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

Dissertationzur Erlangung des Doktorgradesder Fakulta¨t fu¨r Angewandte Wissenschaftenan der Albert-Ludwigs-Universitat Freiburg im Breisgau¨Transformation Knowledge inPattern Analysis with KernelMethods–Distance and Integration KernelsvonDipl.-Math. Bernard Haasdonk24. Mai 2005iiDekan: Prof. Dr. Jan G. KorvinkPrufungskommission: 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 2005AcknowledgementFirstly, IwanttothankmysupervisorProf.Dr.-Ing.HansBurkhardtforgivingmethepossibilityandwidesupportfortheresearchwhichhasledtothisthesis. Inparticular,the excellent technical environment, the availability of various interesting applicationfields 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 manyimportant and fruitful contacts. Similarly, I am deeply grateful to Prof. Dr. BernhardSch¨olkopf who was a constant source of motivation through his own related work andvarious guiding hints, many of which find themselves realized in the present thesis. Iam very glad that he agreed to act as the second referee. In particular, I am verythankful for being given the opportunity to visit his group for a talk, several weeksof research and the machine learning summer school MLSS 2003.

Subjects

Informations

Published by
Published 01 January 2006
Reads 21
Language English
Document size 10 MB

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 ar-
bitrary 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 transfor-
mation 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,theseapproachesdifferinthewaythetransformationsarerepresented
andintheadjustabilityofthetransformationextent. Morefundamentally,kernelsfrom
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
viiviii
motivationtoinvestigatethetheoreticalmeaningofsuchindefinitekernels. Thefinding
is that on given data these kernels correspond to inner products in pseudo-Euclidean
spaces. Herecertainkernelmethods,inparticularSVMs,haveareasonablegeometrical
and theoretical interpretation.
Practical applicability of the kernels is demonstrated in addition to the theoretical
properties. Fortheseexperiments,supportvectorclassificationonvarioustypesofdata
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 demonstrateand theoreticallyar-
gue 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 solu-
tions 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.Contents
1 Introduction 1
1.1 Pattern Analysis and Kernel Methods . . . . . . . . . . . . . . . . . . . 1
1.2 Prior Knowledge by Transformations . . . . . . . . . . . . . . . . . . . 3
1.3 Main Motivating Questions . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background 7
2.1 Transformation Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Distances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Goals for Invariance in Kernel Methods . . . . . . . . . . . . . . . . . . 14
2.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Invariant Distance Substitution Kernels 19
3.1 Distance Substitution Kernels . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Definiteness of DS-Kernels . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Examples of Hilbertian Metrics . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Symmetrization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Choice of Origin O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.6 Transformation Knowledge in DS-Kernels. . . . . . . . . . . . . . . . . 28
3.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Tangent Distance Kernels 35
4.1 Regularized Tangent Distance Measures . . . . . . . . . . . . . . . . . 35
4.2 Definiteness of TD-Kernels . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Invariance of TD-Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Separability Improvement . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.5 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5 Transformation Integration Kernels 49
5.1 Partial Haar-Integration Features . . . . . . . . . . . . . . . . . . . . . 49
5.2 Transformation Integration Kernels . . . . . . . . . . . . . . . . . . . . 50
5.3 Invariance of TI-Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.4 Separability Improvement . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.5 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 55
ixx CONTENTS
5.6 Kernel Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.7 Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.8 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6 Learning with Indefinite Kernels 61
6.1 Feature Space Representation . . . . . . . . . . . . . . . . . . . . . . . 61
6.2 VC-bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.3 Convex Hull Separation in pE Spaces . . . . . . . . . . . . . . . . . . . 66
6.4 SVM in pE Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.5 Uniqueness of Solutions. . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.6 Practical Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7 Experiments - Support Vector Classification 79
7.1 General Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . 79
7.1.1 SVM Implementation . . . . . . . . . . . . . . . . . . . . . . . . 79
7.1.2 Multiclass Architectures . . . . . . . . . . . . . . . . . . . . . . 80
7.1.3 Model Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.2 Invariant Distance Substitution Kernels . . . . . . . . . . . . . . . . . . 82
7.2.1 Application of SVM Suitability Indicators . . . . . . . . . . . . 83
7.2.2 Comparison to k-NN Classification . . . . . . . . . . . . . . . . 85
7.2.3 Indefinite versus Positive Definite Kernel Matrix . . . . . . . . . 87
7.2.4 Large Scale Experiments . . . . . . . . . . . . . . . . . . . . . . 89
7.2.5 Summary of DS-Kernel Experiments . . . . . . . . . . . . . . . 90
7.3 Tangent Distance Kernels . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.3.1 USPS Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.3.2 Micro-Raman Spectra . . . . . . . . . . . . . . . . . . . . . . . 96
7.3.3 Summary of TD-Kernel Experiments . . . . . . . . . . . . . . . 101
7.4 Transformation Integration Kernels . . . . . . . . . . . . . . . . . . . . 102
7.4.1 Toy Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.4.2 USPS Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.4.3 Summary of TI-Kernel Experiments . . . . . . . . . . . . . . . . 105
8 Summary and Conclusions 107
8.1 IDS and TD-Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.2 TI-Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.3 Indefinite Kernels in SVMs . . . . . . . . . . . . . . . . . . . . . . . . . 110
8.4 Invariant Kernels versus Invariant Representations . . . . . . . . . . . . 111
8.5 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
A Datasets 117
A.1 USPS Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
A.2 MNIST Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
A.3 Micro-Raman Spectra . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
A.4 Kimia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
A.5 Unipen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
A.6 Proteins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
A.7 Cat-Cortex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124