Advancing Curvature-Based Methods in Machine Learning

Abstract

Das Taylorpolynom zweiter Ordnung liefert eine lokale, „schüsselförmige“ Näherung einer gegebenen Funktion. Diese Approximation ist Ausgangspunkt für krümmungsbasierte Methoden. Dazu zählen insbesondere (i) Optimierungsverfahren, die auf dem Newton-Schritt - dem Schritt ins Minimum der lokalen Approximation - aufbauen, sowie (ii) die Laplace-Approximation. Diese erlaubt es, beliebige Wahrscheinlichkeitsverteilungen durch einfachere Gauß-Verteilungen anzunähern.

Derartige krümmungsbasierte Ansätze eröffnen Möglichkeiten zur Verbesserung bestehender Methoden des maschinellen Lernens. Das Trainieren moderner Modelle auf großen Datensätzen ist oft mit erheblichem Rechenaufwand verbunden. Newton-Schritt basierte Ansätze könnten hier einen wertvollen Beitrag zur Effizienzsteigerung leisten. Auch im Bereich der approximativen Inferenz sind krümmungsbasierte Ansätze hilfreich: Die Laplace-Approximation wird etwa zur Inferenz in nicht-konjugierten Gaußschen Prozessen sowie zur Quantifizierung von Unsicherheit in den Vorhersagen neuronaler Netze eingesetzt.

Trotz ihres Potenzials finden krümmungsbasierte Verfahren im maschinellen Lernen bislang nur begrenzt Anwendung. Das liegt primär daran, dass diese Algorithmen zweite Ableitungen berechnen, was mit erheblichen Rechenanforderungen verbunden ist. Des Weiteren ist das Taylorpolynom teilweise nicht exakt berechenbar, sondern nur in Form einer stochastischen Näherung zugänglich. Das übergeordnete Ziel dieser Arbeit ist es, derartige Hindernisse zu adressieren, um so die Vorzüge krümmungsbasierter Methoden im maschinellen Lernen weiter zu erschließen. Konkret werden in dieser Dissertation drei Beiträge vorgestellt.

Zunächst stellen wir das iterative Inferenzverfahren IterNCGP für nicht-konjugierte Gaußsche Prozesse vor, das auf der Laplace-Approximation basiert. Unser Ansatz verwendet „unvollständige“ Berechnungen - dies ermöglicht Inferenz auf großen Datensätzen - erfasst aber den entstehenden Approximationsfehler als zusätzliche Unsicherheit. So ermöglicht es unsere Methode, reduzierten Rechenaufwand gegen Unsicherheitszuwachs abzuwägen. Durch die Wiederverwendung rechenintensiver Zwischenergebnisse wird der Inferenzprozess erheblich beschleunigt.

Zweitens präsentieren wir die Open-Source-Bibliothek ViViT, die effizienten Zugang zu Krümmungsinformation im Kontext neuronaler Netze bietet. Unser Ansatz nutzt die Niedrigrangstruktur der generalisierten Gauß-Newton Matrix aus und ermöglicht so eine effiziente Berechnung von Eigenwerten und Eigenvektoren sowie Steigungen und Krümmungen entlang dieser Richtungen. Im Gegensatz zu bestehenden Verfahren macht unser Ansatz die Streuung in den Steigungs- und Krümmungsschätzern explizit sichtbar und implementiert fundierte Approximationen, die einen Kompromiss zwischen Rechenaufwand und Genauigkeit ermöglichen.

Im Kontext von neuronalen Netzen ist es zu aufwendig, das Taylorpolynom exakt zu berechnen. Stattdessen wird es typischerweise auf einem kleinen Teildatensatz der Trainingsdaten approximiert. In unserem dritten Beitrag zeigen wir, dass dies zu einer systematischen Verzerrung der Taylor-Approximation führt. Wir liefern eine theoretische Erklärung für dieses Phänomen und erklären dessen nachteilige Auswirkungen auf krümmungsbasierte Methoden. Schließlich entwickeln wir effektive Strategien zur Behebung der Verzerrungen. Diese erzeugen vernachlässigbaren Rechenmehraufwand, verbessern die Approximationsgüte aber erheblich.

In dieser Arbeit werden krümmungsbasierte Methoden für das maschinelle Lernen weiterentwickelt: Methodische Innovationen steigern ihre Effizienz, Softwareimplementierungen machen sie breiter zugänglich, und die Anerkennung und Behebung inhärenter Approximationsfehler steigern ihre Effektivität und Zuverlässigkeit. Unsere Beiträge fördern die breitere Anwendung krümmungsbasierter Methoden in der Forschung und Praxis des maschinellen Lernens.

The second-order Taylor polynomial provides a local, “bowl-shaped” approximation of a given function. This approximation serves as the foundation for curvature-based methods. These include in particular (i) optimization techniques based on the Newton step - the step into the minimum of the local approximation - as well as (ii) the Laplace approximation. The latter allows arbitrary probability distributions to be approximated by simpler Gaussian distributions.

Such curvature-based approaches offer opportunities to improve existing machine learning methods. Training modern models on large data sets is often computationally expensive. Newton-based approaches could make a valuable contribution to improving training efficiency. Curvature-based approaches are also useful in the context of approximate inference: The Laplace approximation, for instance, is used for inference in non-conjugate Gaussian processes and for quantifying uncertainty in neural network predictions.

Despite their potential, curvature-based methods are still only used to a limited extent in machine learning. This is primarily due to the fact that these algorithms require second-order derivatives, whose evaluation incurs high computational costs. In addition, the Taylor polynomial is in some cases not computable accurately, but only accessible in the form of a stochastic estimate. The overarching goal of this work is to address these limitations in order to further unlock the benefits of curvature-based methods in machine learning. Specifically, the thesis presents three contributions.

We first introduce the iterative inference method IterNCGP for non-conjugate Gaussian processes, which is based on the Laplace approximation. Our method uses “incomplete” computations - enabling inference on large data sets - but captures the resulting approximation error as an additional source of uncertainty. This allows our approach to trade off reduced computational costs for increased uncertainty. Furthermore, by reusing computationally expensive intermediate results, the inference process is accelerated significantly.

Second, we present the open-source library ViViT, which provides efficient access to curvature information in the context of neural networks. Our approach exploits the low-rank structure of the generalized Gauss-Newton matrix. This enables efficient computation of eigenvalues and eigenvectors, as well as slopes and curvatures along those directions. Unlike existing methods, our approach explicitly exposes the noise in the slope and curvature estimates and implements principled approximations that allow for a trade-off between computational cost and accuracy.

Computing the exact Taylor polynomial is prohibitively expensive for neural networks. It is therefore typically approximated on a small subset of the training data. In our third contribution, we show that this leads to systematic biases in the Taylor approximation. We provide a theoretical explanation for this phenomenon and explain its negative effects on curvature-based methods. Finally, we develop effective strategies for correcting these biases. These strategies incur negligible computational overhead, but improve the quality of the approximation significantly.

This thesis advances curvature-based methods for machine learning: Methodological innovations improve their efficiency, software implementations make them more accessible, and acknowledging and correcting inherent approximation errors increases their reliability and effectiveness. Our contributions support the broader application of curvature-based methods in machine learning research and practice.