Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

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


Reisert, Marco

Group integration techniques in pattern analysis : a kernel view

Gruppen Integration Techniken in der Muster Analyse : eine Kern-Sicht

Dokument1.pdf (4.553 KB) (md5sum: 096567feed78367fa78d31b37dc5502b)

Kurzfassung in Deutsch

Diese Dissertation beschäftigt sich mit einer bestimmten
Art von a-priori Wissen: wir nehmen an, dass die Daten ihre Bedeutung unter
bestimmten Transformationen nicht ändern, dass heißt, der Mustererkennungsprozeß ist
'invariant' unter diesen Transformationen. In der statistischen Mustererkennung
sind die Daten typischerweise in vektorieller Form gegeben. In dieser Arbeit nehmen
wir an, dass diese vektoriellen Daten von linearen, invertierbaren Transformationen verändert werden.
Als Beispiel ist die Verschiebung oder Rotation des betrachteten Objektes zu nennen.

Typischerweise kann der Erkennungsprozeß als eine Klassifikations- oder Regressionsfunktion
ausgedrückt werden, dabei basiert das Argument dieser Funktion auf den zuvor erwähnten
vektoriellen Daten. Kernbasierte Modelle dieser Funktionen kamen Mitte der 90er
Jahren auf. Dieser neue Ansatz ermöglichte es Forschern, nichtlineare Beziehungen mit einer Effektivität zu analysieren,
die bis dahin lediglich linearen Algorithmen vorbehalten war.
Sowohl vom Gesichtspunkt der Berechenbarkeit als auch von einem konzeptuell, mathematischen
Punkt aus, sind die kernbasierten Algorithmen sowohl effizient als auch wohlfundiert,
wobei sie nicht unter den typischen Problemen nichtlinearer Algorithmen leiden, wie zum Beispiel
das Steckenbleiben in lokalen Minimas oder dem sogenannten 'overfitting'.
In dieser Arbeit werden wir die konzeptuelle Einfachheit der kernbasierten Modelle
nutzen, um ein theoretisch wohlfundiertes Rahmenwerk des Invarianzbegriffs in der Musteranalyse aufzustellen.
Die lineare Natur wird uns helfen, auf überraschend einfache Weise Optimalitätsaussagen
zu treffen. Diese sind eng verwandt sind mit dem Prinzip der Gruppenintegration, welche seine
Ursprünge in der klassischen Invariantentheorie hat. In Zusammenhang mit der Mustererkennung hat die
Gruppenintegration von Anfang an eine zentrale Rolle gespielt, wenn sie auch in vielen Fällen
eher implizit genutzt wurde.

Diese Arbeit lässt sich in einen theoretischen und praktischen Teil gliedern. In der Theorie
stellen wir das zuvor erwähnte Rahmenwerk auf, welches die Invariantentheorie mit den
kernbasierten Methoden verknüpft. Die Betrachtungen schließen eine präzise Formulierung
des Invarianzbegriffs und seine Erscheinungsform in kernbasierten Räumen mit ein.
Als ein Hauptresultat ist das 'Representer Theorem' zu sehen, welches zeigt, dass
jede Lösung eines bestimmen invarianten Lernproblems
sich mit Gruppenintegration lösen lässt. Desweiteren stellen wir die Charakterisierung und
Interpretation der auftretenden Kerne vor und zeigen Verbindungen zu verwandten Theorien
auf, wie zum Beispiel der Volterra Theorie. Der praktische Teil beschäftigt sich auf der
einen Seite mit der Merkmalsextraktion und auf der anderen Seite mit den Kernmaschinen
selbst. Wir stellen Merkmale vor, welche auf Gruppenintegration basieren und wenden
diese auf zwei Klassifikationsaufgaben an, der Klassifikation von Oberflächenmodellen und
der Klassifikation von Proteinstrukturen. Auf der anderen Seite präsentieren wir ein Konzept
zur Objektdetektion, welches auf der Idee der verallgemeinerten Hough Transformation
basiert. Hierbei modellieren wir das Funktional, welches ein lokales Bildstück auf eine
örtliche Wahrscheinlichkeitsverteilung abbildet, mittels einer Kernmaschine.


Kurzfassung in Englisch

Pattern analysis deals with the problem of characterizing and analyzing relations in data
in an automated way. A quite important issue during the design process of
such algorithms is the incorporation of prior knownledge; knowledge that
is related to all information about the problem available in addition to the training data.
This thesis is about a certain kind of prior knowledge: we assume to know that
the data does not change its meaning under certain transformations, that is, the
pattern recognition process has to be 'invariant' under these transformations.
In statistical pattern recognition the data is typically given in vectorial
form. In this work we assume that the transformations affect this vectorial data just by a linear group-like
transformation. This comprises, for example, translations or rotations of the object under consideration.

Typically, the recognition process can be expressed as classification or regression
functions based on the before mentioned vectorial data. Kernel-based models of these functions
arose in the mid-1990s. This new approach enabled researchers to analyze non-linear relations with the
effectiveness that have been previously reserved for linear algorithms. From a computational and a conceptual,
mathematical point of view the kernel-based pattern analysis algorithms are as efficient and as well
founded as linear ones, whereas problems like local minima and overfitting that were typical
of previous non-linear methods have been overcome. In this work we will use the conceptual ease
of kernel-based models to build a theoretical well-founded framework of invariance in pattern analysis.
The linear nature will help us to provide, in a surprisingly simple way, optimality statements
that are closely related with the principle of group integration having its origin in classical invariant theory.
In the context of pattern recognition group integration has been playing a major role from the beginning while in most cases
the use is rather implicit.

This work is divided into a theoretical and a practical part. In the theoretical part we establish the
beforementioned framework that connects invariance theory with kernel-based methods. The considerations
include a precise formulation of the notion of invariance and its manifestation in kernel spaces.
As a main result a representer theorem is proven, showing that any solution of a learning
problem with certain invariance constraints makes use of the principle of group integration.
Furthermore, we provide characterizations and interpretations of the occurring kernels, we mention kernels with
different concepts of invariance and show connections to related work like Volterra theory.
The practical part concerns on the one hand the feature extraction process and on the other hand
the kernel framework itself. We propose features that are based on group integration and
evaluate them with two classification tasks, classification of surface models and protein structures.
Secondly, we propose a rotation-invariant object detection concept based on the generalized Hough transform.
Thereby, we model the mapping from the local appearance patches onto the spatial probability density by
a kernel machine.



SWD-Schlagwörter: Mustererkennung , Bildverarbeitung , Dreidimensionale Bildverarbeitung , Maschinelles Lernen
Freie Schlagwörter (englisch): group integration , svm, matrix valued kernel , protein classification , object detection
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Burkhardt, Hans (Prof.)
Sprache: Englisch
Tag der mündlichen Prüfung: 28.07.2008
Erstellungsjahr: 2008
Publikationsdatum: 24.10.2008
Indexliste