Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-962
Main Title: Statistical Learning with Similarity and Dissimilarity Functions
Author(s): von Luxburg, Ulrike
Advisor(s): Schölkopf, Bernhard
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: In dieser Dissertation werden statistische Eigenschaften von Lernalgorithmen untersucht. Die Arbeit ist in drei Hauptteile gegliedert. Der erste Teil untersucht die Konvergenz von Spektral-Clustering-Algorithmen auf zufälligen Daten. Wir unterscheiden zwischen zwei Varianten des Algorithmus, die entweder die normalisierte oder die unnormalisierte Graph-Laplace-Matrix benutzen. Wir zeigen, dass die von normalisiertem Spektralclustering erzeugten Partitionen unter Standardvoraussetzungen immer konvergieren, was für die unnormalisierte Version nicht gilt. Für Konvergenz im letzteren Fall werden starke Zusatzvoraussetzungen benötigt, die nicht immer erfüllt sind. Im zweiten Teil der Arbeit werden ''large margin'' Klassifikatoren auf metrischen Räumen konstruiert. Diese Klassifikatoren haben ähnlich schöne Eigenschaften wie Support-Vektor-Maschinen, benutzen aber Distanzfunktionen statt positiv definiten Kernfunktionen. Im letzten Teil wird untersucht, wie man Parameter von Support-Vektor-Maschinen mit Hilfe von Datenkompressionsargumenten bestimmen kann. Für eine gegebene Hyperebene wird ein Code konstruiert, mit dessen Hilfe die Trainingsdaten übermittelt werden können. Dieser Code beruht auf geometrischen Eigenschaften wie der Größe des Klassenabstandes, der Anzahl der Support-Vektoren oder der Lage der Trainingsdaten im Merkmalsraum. Man wählt dann diejenigen Parameter, für die der entsprechende Code am kürzesten ist. Dieses Verfahren kann mit anderen Standardverfahren zur Parameterbestimmung konkurrieren.
This thesis investigates statistical properties of machine learning algorithms and contains three main topics. The first part deals with the question of the convergence of spectral clustering on randomly drawn sample points for growing sample size. We show that spectral clustering always converges if the normalized graph Laplacian is used. For the unnormalized graph Laplacian, convergence only holds under strong assumptions which are not always satisfied in practice. The second part presents a theoretical framework for large margin classification in metric spaces where we work with distance functions instead of kernel functions. We show that many of the nice features of support vector machines such as the representer theorem and generalization bounds can be carried over to this setting. The last part deals with model selection for support vector machines by compression arguments. We first construct a code which can describe the training data with the help of the separating hyperplane constructed by the support vector machine. This code explicitly uses geometric properties such as the margin, the number of support vectors, or the shape of the data in the feature space. Then we choose the parameters of the support vector machine such that the length of the corresponding code is minimized. This procedure can compete with many other model selection criteria.
URI: urn:nbn:de:kobv:83-opus-8624
http://depositonce.tu-berlin.de/handle/11303/1259
http://dx.doi.org/10.14279/depositonce-962
Exam Date: 24-Nov-2004
Issue Date: 13-Dec-2004
Date Available: 13-Dec-2004
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Konvergenz
Metrischer Raum
Spektral-Clustering
Statistische Lerntheorie
Support-Vektor-Maschine
Convergence
Metric space
Spectral clustering
Statistical learning theory
Support vector machine
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_19.pdf1,78 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.