Loading…
Statistical Learning with Similarity and Dissimilarity Functions
Luxburg, Ulrike von
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.
