Loading…
Thumbnail Image

Kernel Fisher Discriminants

Mika, Sebastian

Diese Doktorarbeit beschäftigt sich mit statistischer Lerntheorie und statistischen Lernmaschinen. Eine statistische Lernmaschine versucht aus gegebenen Beispielen eine Regel zu inferieren mit der man in der Lage ist auf ungesehenen Beispielen korrekte Vorhersagen zu machen. Diese Vorhersagen sind reellwertig (Regression) oder diskret (Klassifikation). Wir betrachten insbesondere so genannte kernbasierte Lernverfahren. Die Hauptbeiträge dieser Arbeit lassen sich wie folgt zusammenfassen: Aufbauend auf der Theorie der reproduzierenden Kerne schlagen wir neue Lernmaschinen vor, die auf der Maximierung eines Rayleigh Koeffizienten in einem Kernmerkmalsraum basieren. Wir machen dies beispielhaft für orientierte (Kern) Hauptkomponentenanalyse und insbesondere für Fishers Diskriminanten, was in Kern Fisher Diskriminanten (KFD) resultiert. Dann wird gezeigt, daß KFD eng mit quadratischer und linearer Optimierung verbunden ist. Darauf aufbauend werden verschiedene Möglichkeiten diskutiert mit den Optimierungsproblemen umzugehen die bei kernbasierten Methoden und insbesondere KFD entstehen. Die Formulierung als mathematisches Optimierungsproblem ist der Ausgangspunkt um verschiedene wichtige und interessante Varianten von KFD herzuleiten: Robuste KFD, sparse KFD und lineare KFD. Die mathematische Optimierung ermöglicht es darüber hinaus KFD mit anderen Techniken wie Support Vektor Maschinen, der Relevanzvektormethode und Boosting in Verbindung zu setzen. Durch einen strukturellen Vergleich der zugrundeliegenden Optimierungsprobleme wird illustriert, daß viele moderne Lernmethoden, auch KFD, sich sehr ähneln. Außerdem präsentieren wir erste Ergebnisse über Lerngarantien für Eigenwerte und Eigenvektoren die aus Kovarianzmatrizen geschätzt werden. Wir zeigen, daß unter schwachen Annahmen, die empirischen Eigenwerte mit hoher Wahrscheinlichkeit nahe an den zu erwartenden Eigenwerten liegen. Für Eigenvektoren zeigen wir, daß mit hoher Wahrscheinlichkeit ein empirischer Eigenvektor nahe zu einem Eigenvektor der zugrundeliegenden Verteilung sein wird. In einer großen Sammlung von Experimenten wird demonstriert, daß KFD und seine Varianten sehr gut in der Lage sind mit dem technischen Standard zu konkurrieren. Wir vergleichen KFD mit Boosting und Support Vektor Maschinen und diskutieren sorgfältig die Vor- und Nachteile der vorgeschlagenen Methoden.
In this thesis we consider statistical learning problems and machines. A statistical learning machine tries to infer rules from a given set of examples such that it is able to make correct predictions on unseen examples. These predictions can for example be a classification or a regression. We consider the class of kernel based learning techniques. The main contributions of this work can be summarized as follows. Building upon the theory of reproducing kernels we propose a number of new learning algorithms based on the maximization of a Rayleigh coefficient in a kernel feature space. We exemplify this for oriented (kernel) PCA, and especially for Fisher's discriminant, yielding kernel Fisher discriminants (KFD). Furthermore, we show that KFD is intimately related to quadratic and linear optimization. Building upon this connection we propose several ways to deal with the optimization problems arising in kernel based methods and especially for KFD. This mathematical programming formulation is the starting point to derive several important and interesting variants of KFD, namely robust KFD, sparse KFD and linear KFD. Several algorithms to solve the resulting optimization problems are discussed. As a last consequence of the mathematical programming formulation we are able to relate KFD to other techniques like support vector machines, relevance vector machines and Arc-GV. Through a structural comparison of the underlying optimization problems we illustrate that many modern learning techniques, including KFD, are highly similar. In a separate chapter we present first results dealing with learning guarantees for eigenvalues and eigenvectors estimated from covariance matrices. We show that under some mild assumptions empirical eigenvalues are with high probability close to the expected eigenvalues when training on a specific, finite sample size. For eigenvectors we show that also with high probability an empirical eigenvector will be close to an eigenvector of the underlying distribution. In a large collection of experiments we demonstrate that KFD and its variants proposed here are capable of producing state of the art results. We compare KFD to techniques like AdaBoost and support vector machines, carefully discussing its advantages and also its difficulties.