Kernel-based information theoretical measures: accelerations and limits

Kernelmethoden bilden die Grundlage für einige der leistungsstärksten und fundiertesten Algorithmen für maschinelles Lernen. Die Eigenschaften, welche Kernelmethoden omnipräsent machen, sind die Anzahl der Domänen, für die sie entwickelt wurden, die Hilbert-Struktur der mit Kerneln verbundenen Funktionsklasse, die ihre statistische Analyse erlaubt, und die Möglichkeit, Wahrscheinlichkeitsmaße als Elemente in einem reproduzierenden Kernel-Hilbert-Raum ohne Informationsverlust und unter sehr milden Annahmen abzubilden. All diese Eigenschaften haben zur Entwicklung zahlreicher kernelbasierter informationstheoretischer Maße geführt, wie zum Beispiel der Maximum Mean Discrepancy (MMD; in der Statistikliteratur auch als ``energy distance'' bezeichnet), die den Unterschied zwischen zwei Wahrscheinlichkeitsmaßen quantifiziert; dem Hilbert-Schmidt Independence Criterion (HSIC; in der Statistikliteratur auch als ``distance covariance'' bezeichnet), welches die (Un-)abhängigkeit einer Verteilung quantifiziert; oder der Kernel Stein Discrepancy (KSD), die den Unterschied einer Verteilung zu einem gegebenen Ziel quantifiziert. ... mehrDiese Maße haben zahlreiche Anwendungen gefunden, vor allem bei der Entwicklung von Zweistichproben-, Unabhängigkeits- und Anpassungsgütetests. Die existierenden U- und V-Statistik-basierten Schätzer sind zwar leistungsfähig, haben aber eine Laufzeitkomplexität, die quadratisch mit der Stichprobengröße $n$ wächst, was ihre Anwendung auf große Stichproben stark beeinträchtigt. Um dieser schwerwiegenden Einschränkung zu begegnen, leistet diese Dissertation die folgenden Beiträge.

Wir schlagen den ersten beschleunigten Nyström-basierten HSIC-Schätzer vor, der mehr als zwei Zufallsvariablen verarbeiten kann, beweisen seine $\sqrt n$-Konsistenz und evaluieren seine Leistung auf synthetischen Daten, Abhängigkeitstests von Medienannotationen und dem Finden von kausalen Zusammenhängen. Darüber hinaus zeigen wir, dass die minimax-optimale Rate der HSIC-Schätzung für kontinuierliche, beschränkte, translationsinvariante Kernel auf $\mathbb R^d$ für Borel-Maße, die die Normalverteilungen enthalten, $\mathcal O\!\left( n^{-1/2} \right)$ ist. Damit beantworten wir eine Frage, die seit der Einführung von HSIC vor mehr als $20$ Jahren unbeantwortet war. Unser Ergebnis impliziert auch die Minimax-Optimalität der von uns vorgeschlagenen HSIC-Beschleunigung. In Bezug auf KSD schlagen wir ebenfalls eine Nyström-basierte Beschleunigung vor, beweisen ihre $\sqrt n$-Konsistenz mit einer klassischen sub-Gaußschen Annahme und zeigen mit einer Reihe von Anpassungsgütetest-Benchmarks, dass diese den bisherigen Stand der Forschung übertrifft. Schließlich entwerfen wir eine effiziente Online-Approximation von MMD, die deren Berechnung auf Datenströmen ermöglicht und die Basis für einen leistungsstarken Change Detection Algorithmus bietet. Umfangreiche Experimente zeigen, dass der vorgeschlagene Algorithmus sowohl auf synthetischen als auch auf realen Daten eine herausragende Leistung erzielt.

Insgesamt leistet diese Dissertation einen wissenschaftlichen Beitrag, indem sie beschleunigte Schätzer für kernelbasierte informationstheoretische Maße vorstellt und Werkzeuge für deren Analyse einführt. Unsere theoretischen und experimentellen Ergebnisse zeigen die hervorragenden Eigenschaften dieser Schätzer. Sämtlicher Code für die Replikation der Experimente ist frei verfügbar.

Kernel methods have been at the forefront of data science for several decades and provide the basis of some of the most powerful and principled machine learning algorithms currently known. The key properties rendering kernel methods ubiquitous are the number of domains they have been designed for, the Hilbert structure of the function class associated with kernels facilitating their statistical analysis, and their ability to represent probability measures as elements in a reproducing kernel Hilbert space without loss of information under very mild assumptions. These properties have led to the invention of many kernel-based information theoretical measures such as the maximum mean discrepancy (MMD; also known as energy distance in the statistics literature), quantifying the difference of two distributions, the Hilbert-Schmidt independence criterion (HSIC; also known as distance covariance in the statistics literature), quantifying the dependence of a distribution, or kernel Stein discrepancies (KSD), quantifying the difference of a distribution to a given target. ... mehrThese measures have found numerous applications, most prominently in designing two-sample, independence, and goodness-of-fit tests. However, while powerful, their classical U- and V-statistic-based estimators have a runtime complexity that scales quadratically with the number of samples $n$, prohibiting their application to large-sample settings. To tackle this severe limitation, this dissertation makes the following contributions.

We propose the first accelerated Nyström-based HSIC estimator capable of handling more than two random variables, prove its $\sqrt n$-consistency, and evaluate its performance on synthetic data, dependency testing of media annotations, and causal discovery. Further, we establish the minimax optimal rate of HSIC estimation for continuous bounded translation-invariant kernels on $\mathbb R^d$ for Borel measures containing the Gaussians to be $\mathcal O\!\left( n^{-1/2} \right)$, settling a question that has been open since the introduction of HSIC $20$ years ago. In this setting, the result also implies the minimax optimality of our proposed HSIC acceleration. Regarding KSD, we propose a Nyström-based acceleration, prove its $\sqrt n$-consistency with a classical sub-Gaussian assumption, and show its state-of-the-art performance in goodness-of-fit testing on a suite of benchmarks. Last, we design an efficient online approximation of MMD that allows its computation on data streams and gives rise to a powerful change detection algorithm. Extensive experiments show that the proposed change detector achieves state-of-the-art performance on synthetic and real-world data.

Overall, this dissertation advances our understanding of estimating kernel-based information theoretical measures and establishes fundamental tools for analyzing their accelerations. All code replicating the experiments is made openly available.