Spectral Properties of the Kernel Matrix and their Relation to Kernel Methods in Machine Learning

Abstract

Machine learning is an area of research concerned with the construction of algorithms which are able to learn from examples. Among such algorithms, so-called kernel methods form an important family of algorithms which have proven to be powerful and versatile for a large number of problem areas. Central to these approaches is the kernel matrix which summarizes the information contained in the training examples. The goal of this thesis is to analyze machine learning kernel methods based on properties of the kernel matrix. The algorithms considered are kernel principal component analysis and kernel ridge regression. This thesis is divided into two parts: a theoretical part devoted to studying the spectral properties of the kernel matrix, and an application part which analyzes the kernel principal component analysis method and kernel based regression based on these theoretical results.<br /> In the theoretical part, convergence properties of the eigenvalues and eigenvectors of the kernel matrix are studied. We derive accurate bounds on the approximation error which have the important property that the error bounds scale with the magnitude of the eigenvalue, predicting correctly that the approximation error of small eigenvalues is much smaller than that of large eigenvalues. In this respect, the results improve significantly on existing results. A similar result is proven for scalar products with eigenvectors of the kernel matrix. It is shown that the scalar products with eigenvectors corresponding to small eigenvalues are small a priori independently of the degree of approximation.<br /> In the application part, we discuss the following topics. For kernel principal component analysis, we show that the estimated eigenvalues approximate the true principal values with high precision. Next, we discuss the general setting of kernel based regression and show that the relevant information of the labels is contained in the first few coefficients of the label vector in the basis of eigenvectors of the kernel matrix, such that the information and the noise can be divided much more easily in this representation. Finally, we show that kernel ridge regression works by suppressing all but the leading coefficients, thereby extracting the relevant information of the label vectors. This interpretation suggests an estimate of the number of relevant coefficients in order to perform model selection. In an experimental evaluation, this approach proves to perform competitively to state-of-the-art methods.

<strong>Spektrale Eigenschaften der Kernmatrix und ihre Beziehung zu Kernmethoden im maschinellen Lernen</strong><br /> Maschinelles Lernen ist ein Forschungsgebiet welches sich mit der Konstruktion von Algorithmen beschäftigt, welche in der Lage sind, von Beispielen zu Lernen. Unter solchen Algorithmen sind die sogenannten Kernmethoden eine wichtige Familie von Methoden, die sich als mächtig und vielseitig einsetzbar erwiesen haben. Zentral für diese Ansätze ist die Kernmatrix, welche die Information, die in den Trainingsbeispielen enthalten sind, zusammenfasst. Das Ziel dieser Arbeit ist es, Kernmethoden des maschinellen Lernens mit Hilfe der Eigenschaften der Kernmatrix zu analysieren. Diese Arbeit besteht aus zwei Teilen: Einem theoretischen Teil, der sich mit den spektralen Eigenschaften der Kernmatrix beschäftigt, und einem Anwendungsteils, der die Kernhauptkomponentenzerlegung und kernbasiertes Regression mit Hilfe der theoretischen Resultate analysiert.<br /> Im theoretischen Teil werden Konvergenzeigenschaften der Eigenwerte und Eigenvektoren der Kernmatrix untersucht. Präzise Approximationsfehlerschranken werden hergeleitet, welche die wichtige Eigenschaft haben, dass die Fehlerschranke mit der Größe des Eigenwerts skaliert, wodurch korrekt vorhergesagt wird, dass der Approximationsfehler für kleine Eigenwerte viel kleiner ist als der von großen Eigenwerten. In dieser Hinsicht sind diese Ergebnisse wesentlich besser als existierende Ergebnisse. Ein ähnliches Ergebnis wird für Skalarprodukte mit Eigenvektoren der Kernmatrix bewiesen. Es wird gezeigt, dass das Skalarprodukt mit Eigenvektoren von kleinen Eigenwerten von vorneherein klein ist, unabhängig vom Grad der Approximation.<br /> Im Anwendungsteil werden folgende Themen erörtert. Für Kernhauptkomponentenanalyse wird gezeigt, dass die geschätzten Eigenwerte die echten Hauptwerte mit hoher Genauigkeit approximieren. Weiterhin wird das allgemeine Szenario kernbasierter Regression untersucht und gezeigt, dass die relevante Information in den Labeln in den ersten paar Koeffizienten des Labelvektors in der Basis der Eigenvektoren der Kernmatrix enthalten ist, so dass es in dieser Darstellung sehr viel einfacher ist, Information vom Rauschen zu trennen. Schließlich wird gezeigt, dass eine bestimmte Variante von Kernregression, genannt Kernel Ridge Regression, durch das Unterdrücken der Koeffizienten mit Ausnahme der führenden Koeffizienten funktioniert, wodurch die relevante Information des Labelvektors extrahiert wird. Dieser Erklärungsansatz legt nahe, Modellselektion mit einer Methode zur Schätzung der Anzahl der relevanten Koeffizienten durchzuführen. In Vergleichsexperimenten erweist sich dieser Ansatz als ebenbürtig zu existierenden State-of-the-Art Methoden.