lp-Norm Multiple Kernel Learning
Creators: name: Kloft, Marius
Publisher: name: Technische Universität Berlin
Year: 2011
Subjects: subject: 004 Datenverarbeitung; Informatik
subject: Kern
subject: maschinelles Lernen
subject: MKL
subject: Multiple Kernel Learning
subject: Kernel
subject: machine learning
subject: multiple kernel learning

description: Ziel des Maschinellen Lernens ist das Erlernen unbekannter Konzepte aus Daten. In vielen aktuellen Anwendungsbereichen des Maschinellen Lernens, wie zum Beispiel der Bioinformatik oder der Computer Vision, sind die Daten auf vielfältige Art und Weise in Merkmalsgruppierungen repräsentiert. Im Voraus ist allerdings die optimale Kombination jener Merkmalsgruppen oftmals unbekannt. Die Methodologie des Lernens mit mehreren Kernen bietet einen attraktiven und mathematisch fundierten Ansatz zu diesem Problem. Existierende Modelle konzentrieren sich auf dünn besetzte Merkmals- bzw. Kernkombinationen, um deren Interpretierbarkeit zu erleichtern. Allerdings erweisen sich solche klassischen Ansätze zum Lernen mit mehreren Kernen in der Praxis als wenig effektiv. In der vorliegenden Dissertation betrachte ich das Problem des Lernens mit mehreren Kernen aus einer neuartigen, generelleren Perspektive. In dieser Sichtweise sind klassische Ansätze nur Spezialfälle eines wesentlich generelleren Systems des Lernens mit mehreren Kernen. Um effektivere Kernmischungen zu erhalten, entwickle ich die lp-norm multiple kernel learning Methodologie, die sich effizienter und effektiver als vorherige Lösungsansätze erweist. Insbesondere leite ich Algorithmen zur Optimierung des Problems her, die wesentlich schneller sind als existierende und es erlauben, gleichzeitig Zehntausende von Trainingsbeispielen und Tausende von Kernen zu verarbeiten. Ich analysiere die Effektivität unserer Methodologie in einer Vielzahl von schwierigen und hochzentralen Problemen aus den Bereichen Bioinformatik und Computer Vision und zeige, dass lp-norm multiple kernel learning Vorhersagegenauigkeiten erreicht, die den neuesten Stand der Forschung übertreffen. Die entwickelten Techniken sind tief untermauert in der Theorie des Maschinellen Lernens: Ich beweise untere und obere Schranken auf die Komplexität der zugehörigen Hypothesenklasse, was die Herleitung von Generalisierungsschranken erlaubt, die eine schnellere Konvergenzgeschwindigkeit haben als vorherige Schranken. Des Weiteren stelle ich den minimalen Wert der Schranken mit den geometrischen Eigenschaften der Bayes-Hypothese in Verbindung. Darauf basierend beweise ich, dass für eine grosse Anzahl von Szenarien lp-norm multiple kernel learning deutlich stärkere Generalisierungsgarantien aufweist als vorherige Anätze zum Lernen mit mehreren Kernen. Mit Hilfe einer von mir vorgeschlagenen Methodik, basierend auf den theoretischen Schranken und sogenannten kernel alignments, untersuche ich, warum sich lp-norm multiple kernel learning als hocheffektiv in praktischen Anwendungsgebieten erweist.
description: The goal of machine learning is to learn unknown concepts from data. In real-world applications such as bioinformatics and computer vision, data frequently arises from multiple heterogeneous sources or is represented by various complementary views, the right choice - or even combination - of which being unknown. To this end, the multiple kernel learning (MKL) framework provides a mathematically sound solution. Previous approaches to learning with multiple kernels promote sparse kernel combinations to support interpretability and scalability. Unfortunately, classical approaches to learning with multiple kernels are rarely observed to outperform trivial baselines in practical applications. In this thesis, I approach learning with multiple kernels from a unifying view which shows previous works to be only particular instances of a much more general family of multi-kernel methods. To allow for more effective kernel mixtures, I have developed the lp-norm multiple kernel learning methodology, which, to sum it up, is both more efficient and more accurate than previous approaches to multiple kernel learning, as demonstrated on several data sets. In particular, I derive optimization algorithms that are much faster than the commonly used ones, allowing to deal with up to ten thousands of data points and thousands of kernels at the same time. Empirical applications of lp-norm MKL to diverse, challenging problems from the domains of bioinformatics and computer vision show that lp-norm MKL achieves accuracies that surpass the state-of-the-art. The proposed techniques are underpinned by deep foundations in the theory of learning: I prove tight lower and upper bounds on the local and global Rademacher complexities of the hypothesis class associated with lp-norm MKL, which yields excess risk bounds with fast convergence rates, thus being tighter than existing bounds for MKL, which only achieve slow convergence rates. I also connect the minimal values of the bounds with the soft sparsity of the underlying Bayes hypothesis, proving that for a large range of learning scenarios lp-norm MKL attains substantial stronger generalization guarantees than classical approaches to learning with multiple kernels. Using a methodology based on the theoretical bounds, and exemplified by means of a controlled toy experiment, I investigate why MKL is effective in real applications.