Universeller Algorithmus für die global erweiterte MAP Inferenz für strukturelle Produktion

The ultimate goal of discriminative learning is to train a prediction system by optimizing a desired measure of performance. Unlike in the standard learning scenario with univariate real-valued outputs, in structured prediction we aim at predicting a structured label corresponding to complex objects such as sequences, alignments, sets, or graphs. Here, structural support vector machine (SSVM) enables us to build complex and accurate models and directly integrate the desired performance measure into the optimization process. However, it relies on the availability of efficient inference algorithms — the state-of-the-art training algorithms repeatedly perform inference either to compute a subgradient or to find the most violating configuration. In the literature, the corresponding computational task is generally referred to as loss augmented (or adjusted) inference and is the main computational bottleneck during the training procedure. When the loss function is decomposable we often can perform inference efficiently by using the same algorithm we use for evaluating the prediction function. However, the most popular loss functions are non decomposable (or high order) and require new inference algorithms to benefit from learning with task-dependent loss functions. The main goal of the thesis is to address the computational difficulties inherent in a family of discrete optimization problems which we here refer to as augmented MAP inference. In particular, our main focus is on the exact inference, which is known to be NP-hard in general. As the main result, I define a large class of tractable problem instances within the framework of graphical models and derive an exact message passing algorithm which always finds an optimal solution in polynomial time. The latter is universal in a sense that its applicability does not explicitly depend on the graph structure of a corresponding model but rather on the intrinsic properties like treewidth and number of states of the auxiliary variables. Moreover, it leaves the global interactions between the energy of the underlying model and the sufficient statistics of the global terms largely unspecified. Due to its generic form, the presented algorithm can also be used in other application scenarios than as a subroutine for loss augmented inference in a training algorithm including evaluation of PAC-Bayesian generalization bounds for structured prediction and globally constrained MAP inference. I demonstrate its practical usefulness by training an SSVM for various non decomposable loss functions on the example of a few different applications of increasing complexity. To cope with more complex dependencies I analyze an accurate approximation framework of Lagrangian relaxation and dual decomposition in the context of globally augmented MAP inference.Der ultimative Zweck des diskriminativen Lernens is das Trainieren eines Vorhersagesystems durch das Optimieren einer gewünschten Zielfunktion. Anders als in dem herkömmlichen Ansatz des überwachten Lernens mit eindimensionalen reellwertigen Funktionen, die Labels in einer strukturellen Prädiktion (structured prediction) repräsentieren komplexe Objekte wie Sequenzen, Ausrichtungen, Mengen oder allgemeinere Graphen. Die strukturellen Support Vector Maschinen (SSVM) ermöglichen das Konstruieren von akkuraten und robusten Modellen für das Lernen mit strukturierten Ausgaben und integrieren das gewünschte Optimierungskriterium direkt in den Lernprozess. Jedoch, eine wichtige Voraussetzung dafür ist das Vorhandensein von effizienten Inferenzalgorithmen. Nämlich, die state-of-the-art Trainingsalgorithmen nutzen wiederholt einen Inferenzalgorithmus zum Berechnen eines Subgradienten oder Bestimmen einer maximal verletzenden Konfiguration. In der Literatur, das entsprechende Problem is bekannt als Loss Augmented Inference (mit Verlust erweiterte Inferenz), die den Flaschenhals in der Berechnung darstellt. Im Falle einer zerlegbaren Verlustfunktion können wir den gleichen Algorithmus verwenden zur Inferenz wie für das Auswerten von der Vorhersagefunktion. Jedoch sind die meisten der populären Verlustfunktionen nicht zerlegbar, so dass neue Inferenzalgorithmen notwendig sind um von dem Lernen mit diesen Funktionen zu profitieren. In dieser Dissertation präsentiere ich eine generische Sicht auf das erweiterte Inferenzproblem aus der Perspektive einer exakten Berechnung, die im allgemeinen Fall NP-hart ist. Als ein Hauptergebnis definiere ich eine große Klasse von berechenbaren Probleminstanzen mithilfe der graphischen Modelle und präsentiere einen exakten Algorithmus mit einer polynomiellen Laufzeit. Wegen seiner generischen Form kann dieser Algorithmus auch zum Lösen weiterer Probleme eingesetzt werden wie zum Beispiel das Auswerten von Generalisierungsschranken für strukturelle Prädiktion und MAP Inferenz mit globalen Bedingungen. Ich demonstriere den praktischen Nutzen von diesem Algorithmus anhand des Trainierens von SSVMs für mehrere Beispielapplikationen mit unterschiedlichen nicht zerlegbaren Verlustfunktionen. Zusätzlich untersuche ich den Ansatz der Lagrangian Relaxiereung and der dualen Zerlegung zur Handhabung von komplexeren Beziehungen zwischen den Variablen eines Models