Approximate discriminative training of graphical models

Abstract

Im vergangenen Jahrzehnt haben sich grafische Modelle als wichtiges Werkzeug zur statistischen Analyse von Daten aus unterschiedlichsten wissenschaftlichen Disziplinen - wie etwa maschinellem Sehen, Sprachverarbeitung, Nachrichtentechnik und Biologie - herauskristallisiert. Diesen Disziplinen ist gemein, dass die Aufgabenstellungen typischerweise Objekte mit komplexer interner Struktur behandeln. Grafische Modelle sind dabei behilflich, diese Struktur explizit zu machen, und sie zum Zwecke der statistischen Inferenz auszunützen.<br />Neuerdings hat die erhöhte Verfügbarkeit von Daten aller Art zu verstärktem Interesse an Ansätzen geführt, die aus vorhandenen Beispielen lernen, Eigenschaften bisher ungesehener Objekte vorherzusagen. Grafische Modelle bieten zu diesem Zweck ein wohldefiniertes theoretisches Rüstzeug. Der diskriminative Lernansatz zielt darauf ab, die Parameter eines grafischen Modells so zu schätzen, dass die Vorhersagen des Modells mit den beobachteten Daten konsistent sind. Die vorherrschenden Ansätze sind elegant und konzeptuell einfach, leiden jedoch unter dem Problem, dass sie - sofern das grafische Modell Zyklen aufweist - aus rechnerischer Sicht für praktische Zwecke zu langsam sind. In den letzten Jahren hat sich das Verständnis von approximativer Inferenz in grafischen Modellen dramatisch verbessert.<br />Dennoch wird dem ausufernden rechnerischen Aufwand in Lernanwendungen häufig mit "ad-hoc"-Ansätzen oder Heuristiken begegnet. Ziel dieser Dissertation ist es, Teile der neuen theoretischen Erkenntnisse auf die Anwendung in Lernverfahren zu übertragen.<br />Der erste in dieser Dissertation präsentierte Ansatz basiert primär auf Werkzeugen aus der konvexen Optimierung. Basierend auf einer variationalen Charakterisierung von Inferenz in grafischen Modellen werden mehrere äquivalente Formulierungen des diskriminativen Lernproblems vorgestellt, von denen jede ihre eigenen Stärken aufweist.<br />Die Idee, die diesem Ansatz zugrunde liegt, ist die Inferenz - als Unterproblem des Lernens - zu relaxieren, worunter eine Aufweichung der Beschränkungen des ursprünglichen Optimierungsproblems verstanden wird.<br />Es werden neue Inferenzalgorithmen vorgestellt, die solche relaxierten Probleme effizienter lösen können, als dies bisher möglich war.<br />Alternativ dazu wird demonstriert, wie das Problem des diskriminativen Lernens als ein einziges unbeschränktes konvexes Programm dargestellt, und somit handelsübliche Optimierungssoftware zum Einsatz gelangen kann.<br />Der zweite verfolgte Ansatz basiert auf einem Gauss'schen Modell und erlaubt es, sowohl kontinuierliche als auch diskrete Lernanwendungen zu behandeln. Die Festlegung auf eine Gauss'sche Dichtefunktion mag auf den ersten Blick als starke Einschränkung empfunden werden; die Mächtigkeit des Modells kann jedoch durch nicht-parametrische Konditionierung auf die beobachteten Daten massiv erhöht werden.<br />Die in der Dissertation betrachteten Anwendungen aus den Bereichen des maschinellen Sehens und der Sprachverarbeitung untermauern die vielseitige Einsetzbarkeit der vorgestellten Algorithmen, sowie die Notwendigkeit prinzipienbasierter Approximationen. Als besonders erwähnenswert soll unter den in der Dissertation präsentierten Ergebnissen hervorgehoben werden, dass durch die vorgestellten Verfahren die besten bisher publizierten Ergebnisse im Entrauschen natürlicher Bilder und in damit verwandten Bildrestaurierungsproblemen gewonnen werden konnten.<br />

Over the past decade, graphical models have emerged as a workhorse for statistical processing of data in disciplines as diverse as computer vision, natural language processing, digital communications and computational biology. Problems from all of these disciplines have in common that the objects of interest possess rich internal structure.<br />Graphical models help us make this structure explicit and exploit it during statistical inference.<br />The proliferation of freely available data has lead to reinforced interest in approaches that learn from existing examples how to infer the properties of previously unseen instances. Graphical models provide a sound formal framework towards this end - the discriminative learning approach seeks to estimate the parameters of a graphical model such that its predictions are consistent with the observed data. While conceptually simple, the prevalent approaches suffer from computational intractability if the underlying graphical model contains cycles.<br />Unfortunately, this is the case in many applications of practical interest. During recent years, the understanding of approximate inference in graphical models has improved dramatically. Yet, in a learning scenario, intractability is still often dealt with in an ad-hoc or heuristic manner. This thesis aims to aid the goal of bridging this gap.<br />The first approach we present draws heavily on tools from convex optimization. Based on a variational characterization of the inference problems in graphical models, we present a whole catalogue of equivalent formulations of discriminative learning, each exposing different merits.<br />The idea underlying this approach is to relax the inference subproblems, that is, to optimize over a simpler constraint set. We introduce new algorithms that can be used to solve these relaxed problems more efficiently than previously possible. Alternatively, we demonstrate how the variational viewpoint allows to formulate discriminative learning as a single unconstrained convex optimization problem that can be solved using off-the-shelf solvers.<br />Our second approach is based on a Gaussian model and allows for treatment of both discrete and continuous learning tasks. Discrete variables can be handled either via a high-dimensional encoding, or by optimizing a specific loss function. While the use of a Gaussian predictive density may seem overly restrictive at first, we demonstrate how the expressiveness of the model can be increased significantly via non-parametric conditioning.<br />We present applications from computer vision and natural language processing that demonstrate the wide applicability of our algorithms and the importance of employing principled approximations. A highlight among our results is that we obtain the best published numbers for natural image denoising and related image restoration problems.<br />