Lernen mit Strukturierten Daten: Anwendungen in der Computer Vision

Die vorliegende Arbeit beschäftigt sich mit strukturierten Lernproblemen im Bereich des maschinellen Lernens. Hierbei bezieht sich “strukturiert” auf Prädiktionsfunktionen, deren Definitions- oder Zielmenge nicht wie sonst üblich in Vektorform dargestellt werden kann. Stattdessen kann die Eingabeinstanz oder der prädizierte Wert in Teile zerlegt werden, die gewissen Abhängigkeiten, Relationen und Nebenbedingungen genügen. Im Forschungsfeld der Computer Vision gibt es eine Vielzahl von strukturierten Lernproblemen, von denen wir einige im Rahmen dieser Dissertation diskutieren werden. Im ersten Teil der Arbeit behandeln wir strukturierte Definitionsmengen. Basierend auf dem Konzept der Unterstrukturen entwickeln wir ein flexibel anwendbares Schema zur Konstruktion von Klassifikationsfunktionen und zeigen, wie zwei wichtige Probleme im Bereich der Computer Vision, das Objekterkennen auf Klassenebene und das Erkennen von Aktivitäten in Videodaten, darauf abgebildet werden können. Beim Objekterkennen modellieren wir Bilder als Graphen, deren Knoten lokale Bildmerkmale repräsentieren. Kanten in diesem Graphen kodieren Informationen über die paarweise Geometrie der adjazenten Bildmerkmale. Die Aufgabe der Objekterkennung lässt sich in diesem Schema auf das Auffinden diskriminativer Untergraphen reduzieren. Diesem Prinzip folgend können auch Videos als Sequenz zeitlich und räumlich lokaler Bewegungsinformationen modelliert werden. Das Erkennen von Aktivitäten in Videos kann somit analog zu den Graphen auf das Auffinden von passenden Untersequenzen reduziert werden. In beiden Anwendungen ermöglicht unser Schema die Identifikation einer geeigneten Menge von diskriminativen Unterstrukturen anhand eines gegebenen Trainingsdatensatzes. In diesem ersten Teil besteht der Forschungsbeitrag aus unserem Schema und passenden abstrakten Algorithmen, die es ermöglichen, leistungsfähige Klassifikatoren für strukturierte Eingabemengen zu konstruieren. Im zweiten Teil der Arbeit diskutieren wir Lernprobleme mit strukturierten Zielmengen. Im Speziellen behandeln wir Bildsegmentierungsprobleme, bei denen die prädizierte Segmentierung globalen Nebenbedingungen, zum Beispiel Verbundenheit klassengleicher Pixel, genügen muss. Wir entwickeln eine allgemeine Methode, diese Klasse von globalen Interaktionen in Markov Random Field (MRF) Modelle der Computer Vision mit Hilfe von linearer Programmierung und Relaxationen zu integrieren. Um diese Relaxationen besser zu verstehen sowie Aussagen über die prädizierten Lösungen machen zu können, entwickeln wir ein neuartiges Konzept der Lösungsstabilität unter Störungen der Eingabedaten. Der Hauptbeitrag zum Forschungsfeld dieses zweiten Teils liegt in der Modellierung, den Lösungsalgorithmen und der Analyse der Lösungen komplexer strukturierter Lernprobleme im Feld der Computer Vision. Im Speziellen zeigen wir die Approximierbarkeit von Modellen, die sowohl globale Nebenbedingungen als auch lokale Evidenz berücksichtigen. Zudem zeigen wir erstmals, wie die Lösungen dieser Modelle mit Hilfe ihrer Stabilitätseigenschaften verstanden werden können.In this thesis we address structured machine learning problems. Here “structured” refers to situations in which the input or output domain of a prediction function is non-vectorial. Instead, the input instance or the predicted value can be decomposed into parts that follow certain dependencies, relations and constraints. Throughout the thesis we will use hard computer vision tasks as a rich source of structured machine learning problems. In the first part of the thesis we consider structure in the input domain. We develop a general framework based on the notion of substructures. The framework is broadly applicable and we show how to cast two computer vision problems — class-level object recognition and human action recognition — in terms of classifying structured input data. For the class-level object recognition problem we model images as labeled graphs that encode local appearance statistics at vertices and pairwise geometric relations at edges. Recognizing an object can then be posed within our substructure framework as finding discriminative matching subgraphs. For the recognition of human actions we apply a similar principle in that we model a video as a sequence of local motion information. Recognizing an action then becomes recognizing a matching subsequence within the larger video sequence. For both applications, our framework enables us to finding the discriminative substructures from training data. This first part contains as a main contribution a set of abstract algorithms for our framework to enable the construction of powerful classifiers for a large family of structured input domains. The second part of the thesis addresses structure in the output domain of a prediction function. Specifically we consider image segmentation problems in which the produced segmentation must satisfy global properties such as connectivity. We develop a principled method to incorporate global interactions into computer vision random field models by means of linear programming relaxations. To further understand solutions produced by general linear programming relaxations we develop a tractable and novel concept of solution stability, where stability is quantified with respect to perturbations of the input data. This second part of the thesis makes progress in modeling, solving and understanding solution properties of hard structured prediction problems arising in computer vision. In particular, we show how previously intractable models integrating global constraints with local evidence can be well approximated. We further show how these solutions can be understood in light of their stability properties