Conditioned Generalized Belief Propagation

Motivation

Probabilistische graphische Modelle bilden ein Framework zur Repräsentation multivariater Wahrscheinlichkeitsverteilungen. Anwendungen umfassen Spracherkennung, Bilderkennung, Dekodieren von Error-Correcting-Codes, Modellierung von Genregulationsnetzwerken und Proteinstrukturen, Diagnose von Krankheiten, und vieles andere.

Conditioned Belief Propagation (CBP, [1]) ist ein Divide-and-Conquer Algorithmus zur genäherten probabilistischen Inferenz in graphischen Modellen. CBP verfeinert eine Approximation, indem er rekursiv eine Variable auswählt und eine Fallunterscheidung nach allen möglichen Belegungen dieser Variable durchführt. Hierdurch entsteht ein Baum, dessen Kanten Variablenbelegungen repräsentieren und dessen Knoten vereinfachte Probleme darstellen. – der Wurzelknoten stellt hierbei das ursprüngliche Problem dar. Eine Endergebnis erhält man durch Näherungen der Blatt-Probleme mittels des Belief Propagation Algorithmus. Je mehr Variablen belegt werden (und je größer der Baum wird), desto exakter ist die letztendliche Näherung.

Inhalt der Arbeit

Der CBP Algorithmus arbeitet, mit Ausnahme einiger Heuristiken, unabhängig von der Wahl des letztendlichen Approximationsalgorithmus (BP). Es ist daher naheliegend BP durch andere Approximationen zu ersetzen. Kandidaten hierfür sind zum Beispiel Verallgemeinerungen von BP, wie Generalized Belief Propagation in den Ausführungen Cluster-Variational-Method und Cluster-Graph-Propagation.
Inhalt dieser Arbeit ist die Implementierung und empirische Evaluation mindestens einer Variante von CBP. Die Implementierung kann entweder auf einer bestehenden -Implementierung von CBP, oder auf der C++-Bibliothek libdai erfolgen, die bereits einige GBP Implementationen enthält.

Was gehört dazu?

• Theoretische Grundlagen
  • probabilistische Inferenz und Markov Netze
  • grundlegende Eigenschaften der BP Näherung und des GBP Ansatzes
  • der CBP-Algorithmus
• Technische Fertigkeiten
  • funktionale Programmierung in (ähnlich Haskell, OCaml), oder Programmierung in C++
  • empirische Evaluation von Algorithmen
  • statistische Auswertung der empirischen Evaluation mit

Referenzen

1. Geier, T.; Richter, F. & Biundo, S. Conditioned Belief Propagation Revisited: Extended Version; Ulm University, 2014