Kategorische Glaubenspropagation: Neue Sheaf-Theoretische Inferenzmethodik

In einer kürzlich veröffentlichten Arbeit auf arXiv wird ein neues, kategorisches Fundament für die Glaubenspropagation (BP) auf Faktorgraphen vorgestellt. Der Ansatz baut die freie Hypergraphenkategorie Syn_Σ auf einer typisierten Signatur auf und beweist deren universelle Eigenschaft. Dadurch entsteht eine kompositionsfähige Semantik, die über einen eindeutigen Funktor in die Matrixkategorie Mat_R überführt wird.

Die Nachrichtenübermittlung wird mithilfe einer Grothendieck-Fibration ∫Msg → FG_Σ über polarisierten Faktorgraphen modelliert. Durch schrittweise definierte Endomorphismen, die nach einem Zeitplan indiziert sind, werden die BP-Updates formalisiert. Der Kern des Ansatzes liegt in der Charakterisierung exakter Inferenz als effektive Descent: Lokale Glaubenswerte bilden ein Descent-Datum, wenn die Kompatibilitätsbedingungen auf Überlappungen erfüllt sind.

Dieses Rahmenwerk vereint die klassischen Resultate zur Baumexaktheit, die Algorithmen des Junction Trees und die Fehlfunktionen von loopy BP unter einem sheaf-theoretischen Gesichtspunkt. Ein neuer Algorithmus namens HATCC (Holonomy-Aware Tree Compilation) erkennt Descent-Behinderungen, berechnet Holonomie auf dem Faktor-Nerv, kompiliert nicht-triviale Holonomie in Modvariablen und reduziert das Problem anschließend auf Baum-BP in einem erweiterten Graphen.

Die Komplexität von HATCC beträgt O(n² d_max + c · k_max · δ_max³ + n · δ_max²), wobei n die Anzahl der Faktoren, c die fundamentalen Zyklen und δ_max die maximale Knotengradzahl beschreibt. Experimentelle Ergebnisse zeigen, dass die Methode exakte Inferenz ermöglicht und dabei die Laufzeit gegenüber traditionellen Junction-Tree-Algorithmen auf Gitter-MRFs und zufälligen Graphen deutlich reduziert. Zusätzlich kann HATCC Unentscheidbarkeit in SAT-Instanzen erkennen.