Exakte relaxationsbasierte Inferenz in Graphischen Modellen (ERBI)

• Antragsteller: Dr. Bogdan Savchynskyy
• Fachliche Zuordnung: Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung von 2016 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 323301551

Graphische Modelle sind ein wichtiges Modellierungswerkzeug in Computer Vision, Bioinformatik, Kommunikationstheorie, statistischer Physik, Signalverarbeitung, Informationsrückgewinnung und Maschinellem Lernen. Die Verbreitung Graphischer Modelle ist durch ihre Fähigkeit komplexe Objekte zu modellieren, die aus einer Menge der zusammenhängenden Komponenten bestehen, bestimmt. Wir befassen uns mit dem wichtigen Maximum a posteriori Inferenzproblem für Graphische Modelle. Das Problem besteht aus der Suche nach der wahrscheinlichsten Konfiguration der Komponenten des Objektes. Dieses Problem ist NP-schwer. Es existieren jedoch effiziente, approximative Lösungsverfahren, diegute Ergebnisse in einer Reihe von Anwendungen liefern. Gleichzeitig sind exakte Lösungsverfahren für dieses Problem meist langsam und speicherintensiv. Dies verhindert ihren Einsatz bei größeren Probleminstanzen. In Bereichen, wo die Genauigkeit der Lösung eine entscheidende Rolle spielt, wie z.B. in der Bioinformatik, sind diese langsamen Verfahren trotzdem weit verbreitet. Das Ziel dieses Projektes ist einen exakten und gleichzeitig skalierbaren und parallelisierbaren Ansatz zum Inferenzproblem für graphische Modelle zu entwickeln. Wir bauen dabei auf unserer vorherige Arbeit auf, die einen ersten Ansatz für solche Lösungsverfahren bereitstellt. Die Methode nutzt den Fakt aus, dassapproximative, relaxationsbasierte Verfahren oft Lösungen liefern, bei der nur wenige Variablen von der exakten Lösung abweichen. Das wurde benutzt, um das Problem zu verkleinern und eineeffiziente Lösung mittels der üblichen, langsamen aber exakten Verfahren zu ermöglichen. Obwohl der vorgeschlagene Ansatz in einer jüngsten Benchmark-Studie vielversprechende Ergebnisse liefert, ist seine praktische Anwendung auf dünnbesetzte, paarweise Modelle mit einer kleinen Anzahl von Variablenzustände begrenzt. In diesem Projekt erweitern wir den exakten Inferenzansatz auf für die Praxis relevante Graphische Modelle, die oft eine dichte graphische Struktur, sowie viele Variablenzustände haben, und zusätzlich noch externen linearen Bedienungen genügen müssen.

• DFG-Verfahren: Sachbeihilfen