Probabilistische Inferenz

Probabilistische Inferenz ist die Berechnung der Wahrscheinlichkeit von Abfragevariablen bei gegebener beobachteter Evidenz in einem probabilistischen Modell, die zentrale Schlussfolgerungsaufgabe über Bayes'sche und Markov-Netzwerke.

Definition

Probabilistische Inferenz berechnet eine posteriore Verteilung, wie die Wahrscheinlichkeit einer oder mehrerer Abfragevariablen, konditioniert auf beobachtete Evidenz, aus einem spezifizierten probabilistischen Modell, entweder exakt oder durch Approximation.

Scope

Dieses Thema behandelt die Algorithmen, die probabilistische Abfragen in grafischen Modellen beantworten: exakte Methoden wie Variabelnelimination, Belief Propagation in Bäumen und der Junction-Tree- (Clique-Tree-) Algorithmus; sowie approximative Methoden wie Loopy Belief Propagation und Monte-Carlo-Sampling (Rejection Sampling, Likelihood Weighting und Markov Chain Monte Carlo). Es befasst sich mit der rechnerischen Schwierigkeit der Inferenz und den Kompromissen zwischen Exaktheit und Skalierbarkeit. Die Struktur der Modelle selbst wird unter Bayes'schen Netzwerken behandelt.

Core questions

• Wie wird eine bedingte oder marginale Wahrscheinlichkeit aus einem gemeinsamen Modell berechnet, ohne die vollständige Verteilung aufzulisten?
• Wie nutzt die Variabelnelimination die Faktorisierung, um exakte Antworten effizient zu berechnen?
• Wann ist exakte Inferenz unlösbar, und welche approximativen Methoden werden stattdessen verwendet?
• Wie schätzen samplingbasierte Methoden posteriore Wahrscheinlichkeiten?

Key concepts

• marginale und bedingte Abfragen
• Variabelnelimination
• Belief Propagation (Nachrichtenübertragung)
• Junction Tree und Baumweite
• Loopy Belief Propagation
• Rejection Sampling und Likelihood Weighting
• Markov Chain Monte Carlo
• exakte vs. approximative Inferenz

Key theories

Belief Propagation

In baumstrukturierten Netzwerken können exakte Posteriori-Verteilungen durch den Austausch lokaler Nachrichten zwischen benachbarten Knoten berechnet werden; Pearls Belief Propagation führt diese verteilte Berechnung durch und liefert, angewendet auf schleifenbehaftete Graphen, eine weit verbreitete approximative Inferenzmethode.

Junction-Tree- (Clique-Tree-) Inferenz

Exakte Inferenz in allgemeinen Netzwerken kann durch das Clustern von Variablen in einen Baum von Cliquen und die Propagation von Nachrichten darüber organisiert werden, was korrekte Antworten in einer Zeit liefert, die nur in der größten Clique (der Baumweite) exponentiell ist.

Approximative Inferenz durch Sampling

Wenn exakte Inferenz undurchführbar ist, ziehen Monte-Carlo-Methoden wie Likelihood Weighting und Markov Chain Monte Carlo Stichproben, die mit der Evidenz übereinstimmen, um posteriore Wahrscheinlichkeiten zu schätzen, wobei garantierte Exaktheit gegen Skalierbarkeit getauscht wird.

Clinical relevance

Inferenzalgorithmen machen probabilistische Modelle nutzbar: Sie treiben Diagnose- und Entscheidungsunterstützungssysteme, Fehlerkorrekturcodes (mittels Belief Propagation), Computer Vision, Spracherkennung und Bioinformatik an, indem sie die Wahrscheinlichkeiten versteckter Variablen bei gegebenen Beobachtungsdaten berechnen.

History

Pearls Belief Propagation (1980er Jahre) lieferte exakte Inferenz für Baumnetzwerke, und die Junction-Tree-Methode von Lauritzen und Spiegelhalter aus dem Jahr 1988 erweiterte die exakte Inferenz auf allgemeine Netzwerke mittels lokaler Berechnungen an Cliquen. Die Erkenntnis, dass exakte Inferenz im Allgemeinen NP-schwer ist, führte zu umfangreichen Arbeiten an Sampling- und Variationsapproximationen.

Key figures

• Judea Pearl
• Steffen L. Lauritzen
• David J. Spiegelhalter
• Daphne Koller

Seminal works

• pearl1986
• lauritzen1988

Frequently asked questions

Ist probabilistische Inferenz immer handhabbar?

Nein. Exakte Inferenz in allgemeinen Bayes'schen Netzwerken ist NP-schwer, und ihre Kosten steigen mit der Baumweite des Netzwerks. Für Netzwerke, die Bäume sind oder eine geringe Baumweite aufweisen, ist exakte Inferenz effizient; andernfalls werden approximative Methoden wie Sampling oder Loopy Belief Propagation verwendet.

Was ist der Unterschied zwischen exakter und approximativer Inferenz?

Exakte Inferenz, wie die Variabelnelimination oder der Junction-Tree-Algorithmus, berechnet die wahren posterioren Wahrscheinlichkeiten. Approximative Inferenz, wie Monte-Carlo-Sampling oder Loopy Belief Propagation, schätzt diese, was notwendig ist, wenn die exakte Berechnung für ein großes oder dicht verbundenes Modell zu aufwendig ist.