warum in der Grid-Grafik unmöglich

Question

Die Frage die genaue Folgerung des MRF ist wie im Titel geschrieben

Es ist ein 3x3-Gitter Graph auf dem obigen Bild. Wir können es in einen Verzweigungsbaum umwandeln. Dann ist es möglich, Nachrichtenübergabe (Produktsummenalgorithmus) für die Inferenz zu verwenden (Schätzung der Wahrscheinlichkeit/posterior usw.). Also frage ich mich, warum die genaue Schlussfolgerung in der Grid-Grafik so schwer ist?

Ist es unmöglich, einen solchen Verzweigungsbaum zu finden, wenn das Gitter größer wird?

Answer 1

Die kurze Antwort: Für ein nxn-Gitter ist die Komplexität mindestens exponentiell n.

Aus dem induzierten Graphen der MRF wird ein Verzweigungsbaum erstellt, der von der Eliminationsreihenfolge abhängt (welche Variablen Sie zuerst eliminieren, um eine Marginale zu berechnen). Die Eliminationskosten sind exponentiell in der Größe der größten Clique im induzierten Graphen. Weitere Informationen finden Sie unter this Papier.

Also, obwohl wir eine genaue Inferenz auf den Junction-Baum verwenden können, wäre die Komplexität exponentiell in der Größe der größten Clique im induzierten Graph der Eliminationsordnung, die verwendet wurde.

Die bestmögliche Eliminierungsreihenfolge ergibt eine größte Cliquengröße, die der Baumbreite entspricht, also n für ein nxn-Gitter. Aber es gibt keine effizienten Algorithmen, um es zu finden.