💻 computer science

noDice: Inference for Discrete Probabilistic Programs with Nondeterminism and Conditioning

Das Paper stellt noDice vor, eine Erweiterung des diskreten probabilistischen Inferenz-Engine Dice, die durch die Konstruktion von Markov-Entscheidungsprozessen und den Einsatz von Entscheidungsdiagrammen die Inferenz für loop-freie Programme mit Nondeterminismus und Bedingung ermöglicht.

Ursprüngliche Autoren: Tobias Gürtler, Benjamin Lucien Kaminski

Veröffentlicht 2026-02-24

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Tobias Gürtler, Benjamin Lucien Kaminski

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

🎲 Die Geschichte von noDice: Wenn das Schicksal nicht nur würfelt, sondern auch entscheidet

Stell dir vor, du bist ein Detektiv, der versucht, das Wetter von morgen vorherzusagen. Normalerweise würfelst du einfach: „Es gibt eine 70 % Chance auf Regen." Das ist einfach. Aber was, wenn das Wetter nicht nur vom Zufall abhängt, sondern auch von Entscheidungen, die wir nicht kennen?

Vielleicht entscheidet ein unsichtbarer „Wetter-Gott" (das ist das Nichtdeterminismus-Element), ob eine Wolke bleibt oder geht. Und dazu kommt noch, dass wir nur sehr ungenaue Messungen haben (das ist das Conditioning oder „Bedingen"): Wir sehen nur einen Regentropfen und müssen daraus schließen, ob es stundenlang regnen wird.

Bisherige Werkzeuge (wie das Programm Dice) waren super im Berechnen von reinem Zufall (Würfel, Münzwürfe). Aber sobald dieser „Wetter-Gott" ins Spiel kam, der Entscheidungen trifft, die wir nicht genau kennen, kamen sie an ihre Grenzen. Sie mussten entweder raten oder die Rechnung so komplex machen, dass der Computer explodierte.

Hier kommt noDice ins Spiel.

🛠️ Wie funktioniert noDice? (Die drei Schritte)

noDice ist wie ein genialer Übersetzer, der ein chaotisches Programm in eine übersichtliche Landkarte verwandelt. Es macht das in drei Schritten:

1. Der Übersetzer (Kompilierung)

Stell dir vor, du hast einen langen, verworrenen Text über das Wetter. noDice nimmt diesen Text und schreibt ihn in eine ganz einfache Sprache um: Nur noch „Wahr" oder „Falsch" (Boolesche Formeln).

Die Analogie: Es ist, als würde man ein komplexes Kochrezept in eine einfache Checkliste verwandeln: „Ist der Ofen an? Ja/Nein. Ist der Teig fertig? Ja/Nein."
Dabei merkt sich noDice genau, welche Schritte vom Zufall (Münzwurf) und welche von der unsicheren Entscheidung (der Wetter-Gott) abhängen.

2. Der Kompressor (Entscheidungsdiagramme)

Jetzt hat noDice diese Checkliste. Aber eine normale Liste wäre riesig und unübersichtlich. noDice nutzt einen Trick namens Entscheidungsdiagramm (ADD).

Die Analogie: Stell dir vor, du hast einen riesigen Baum mit Millionen von Ästen. noDice schneidet alle Äste ab, die doppelt sind oder die zum selben Ergebnis führen. Es verwandelt den riesigen Wald in einen kleinen, effizienten Tunnel.
Warum ist das wichtig? Wenn du versuchst, alle möglichen Wege durch den Wald zu zählen, brauchst du Jahre. noDice zählt nur die einzigartigen Wege in Sekunden.

3. Die Landkarte (Markov-Entscheidungsprozess)

Schließlich baut noDice aus diesem kleinen Tunnel eine Landkarte, die man leicht ablaufen kann. Diese Landkarte zeigt alle möglichen Szenarien auf einmal.

Die Analogie: Es ist wie eine Schatzkarte. Auf der Karte sind alle Pfade markiert.
- Die Zufalls-Pfade sind wie Flüsse, die zufällig links oder rechts abbiegen.
- Die Entscheidungs-Pfade sind wie Gabelungen, bei denen ein unsichtbarer Fahrer entscheidet, wohin es geht.
noDice fragt dann: „Wenn wir alle falschen Pfade (wo unsere Messungen nicht gepasst haben) ignorieren, wie groß ist die Wahrscheinlichkeit, dass wir am Ende am falschen Ort (z. B. der Flugzeug landet auf der falschen Landebahn) ankommen?"

🚀 Warum ist das so cool?

Das Besondere an noDice ist, dass es nicht versucht, jeden einzelnen Weg einzeln durchzugehen (was bei komplexen Problemen unmöglich wäre). Stattdessen nutzt es die Struktur des Programms, um riesige Teile des Problems zu ignorieren, die ohnehin gleich sind.

Das Problem: Wenn du versuchst, ein Problem mit 100 Entscheidungen und 100 Zufällen zu lösen, hast du theoretisch mehr Möglichkeiten als Atome im Universum.
Die Lösung von noDice: Es erkennt Muster. „Oh, egal ob der Wetter-Gott hier links oder rechts wählt, am Ende kommt das gleiche Ergebnis heraus." Also spart es sich die Rechnung.

🏆 Das Ergebnis

In Tests hat noDice gezeigt, dass es bei vielen Problemen viel schneller ist als die besten existierenden Werkzeuge (wie der „Storm"-Model Checker).

Bei einfachen Problemen ist es ähnlich schnell wie die alten Werkzeuge.
Bei komplexen Problemen mit vielen Unsicherheiten (Nichtdeterminismus) ist noDice ein Superheld, der Aufgaben löst, bei denen andere Computer nach Stunden noch nicht fertig sind.

📝 Zusammenfassung in einem Satz

noDice ist ein neues Werkzeug, das komplexe Unsicherheiten und Zufälle in Computerprogrammen so clever zusammenfasst, dass man sie schnell berechnen kann, indem es riesige, verworrene Probleme in kleine, übersichtliche Landkarten verwandelt.

Es ist wie der Unterschied zwischen dem Versuch, jeden einzelnen Sandkorn am Strand zu zählen, und dem einfachen Messen des Wasserstands, um zu wissen, wie viel Sand da ist.

1. Problemstellung

Probabilistische Programmiersprachen (PPLs) wie Dice ermöglichen die intuitive Modellierung komplexer Wahrscheinlichkeitsverteilungen, insbesondere im diskreten Bereich. Ein zentrales Problem in der aktuellen Forschung ist jedoch die Kombination von Nichtdeterminismus (z. B. in Markov-Entscheidungsprozessen, MDPs, wie sie im Reinforcement Learning vorkommen) und Bedingung (Conditioning/Observation).

Herausforderung: Die meisten modernen Inferenz-Engines unterstützen Nichtdeterminismus nicht. Wenn Nichtdeterminismus hinzugefügt wird, modelliert ein Programm keine einzelne Verteilung mehr, sondern eine Menge von Verteilungen.
Komplexität: Die Inferenz wird nicht-kompositionell. Das bedeutet, dass die maximale bedingte Wahrscheinlichkeit eines Programms nicht einfach aus den maximalen Wahrscheinlichkeiten seiner Teilprogramme abgeleitet werden kann.
Bestehende Ansätze: Derzeitige Lösungen erfordern oft die direkte Anwendung von probabilistischen Model-Checkern auf die operationale Semantik des Programms. Dies führt jedoch häufig zu einem exponentiellen Anstieg des Zustandsraums (State-Space Explosion), was die Berechnung für größere Programme unpraktisch macht.

2. Methodik: Das noDice-Framework

Die Autoren stellen noDice vor, eine Erweiterung des diskreten Inferenz-Engines Dice, die speziell für nichtdeterministische Programme mit Beobachtungen entwickelt wurde. Der Kernansatz besteht darin, die Inferenz auf die Berechnung von bedingten Erreichbarkeitswahrscheinlichkeiten in einem konstruierten Markov-Entscheidungsprozess (MDP) zurückzuführen.

Der Inferenzprozess läuft in drei Hauptschritten ab:

Boolesche Kompilierung (Boolean Compilation):
- Das noDice-Programm wird in ein Paar boolescher Formeln übersetzt:
  - $\phi$ : Modelliert das Verhalten des Programms (Ausgabe), ignoriert aber Beobachtungen.
  - $\gamma$ : Modelliert ausschließlich die Beobachtungen (Observations).
- Im Gegensatz zu Dice wird hier eine annotierte Spur (Trace) von Variablen erstellt, die den zeitlichen Ablauf der Zufalls- und Nichtdeterminismus-Entscheidungen (Flips) festhält. Nichtdeterministische Flips werden mit einem speziellen Marker ( $n$ ) versehen, probabilistische mit ihrer Wahrscheinlichkeit ( $p$ ).
Entscheidungsdiagramme (Decision Diagrams):
- Die Formeln $\phi$ und $\gamma$ werden intern als Binäre Entscheidungsdiagramme (BDDs) dargestellt.
- Diese werden zu einem einzigen Algebraischen Entscheidungsdiagramm (ADD) kombiniert. ADDs sind eine Verallgemeinerung von BDDs, die mehr als binäre Ausgänge zulassen.
- Dieser Schritt nutzt die Struktur des Programms (z. B. bedingte Unabhängigkeit), um Redundanzen zu eliminieren und den Zustandsraum drastisch zu komprimieren, bevor der MDP gebaut wird.
Lifting zu Markov-Entscheidungsprozessen (MDP):
- Das ADD dient als Gerüst für die Konstruktion eines MDPs.
- Jeder Knoten im ADD wird zu einem Zustand im MDP.
- Die Kanten im ADD werden zu Übergängen im MDP:
  - Knoten mit probabilistischen Flips erhalten probabilistische Übergänge.
  - Knoten mit nichtdeterministischen Flips erhalten nichtdeterministische Aktionen (der Scheduler wählt den Pfad).
- Inferenz-Ziel: Die maximale Wahrscheinlichkeit, dass das Programm einen bestimmten Wert ausgibt, entspricht der maximalen bedingten Erreichbarkeitswahrscheinlichkeit im MDP, unter der Bedingung, dass der Zustand „Akzeptiert" (alle Beobachtungen erfolgreich) erreicht wird und der Zustand „Abgelehnt" (Beobachtungen fehlgeschlagen) vermieden wird.
- Zur Berechnung wird ein effizienter Bisektions-Algorithmus (implementiert im Storm Model Checker) verwendet, der besonders gut auf azyklische MDPs funktioniert.

3. Wichtige Beiträge

Sprache noDice: Einführung einer nicht-rekursiven funktionalen Sprache mit diskreten probabilistischen und nichtdeterministischen Wahlmöglichkeiten sowie First-Class-Beobachtungen.
Theoretische Grundlage: Beweis der Korrektheit (Soundness) des Inferenzalgorithmus. Es wird gezeigt, dass die maximale bedingte Erreichbarkeitswahrscheinlichkeit im konstruierten MDP exakt der maximalen Wahrscheinlichkeit entspricht, die das Programm unter allen möglichen Auflösungen des Nichtdeterminismus und unter erfolgreicher Bedingung liefert.
Effiziente Zustandsraumreduktion: Durch die Nutzung von ADDs als Zwischenschritt werden redundante Zustände entfernt, bevor der MDP erstellt wird. Dies verhindert oft die exponentielle Explosion, die bei direkter Operational-Semantik-Übersetzung auftritt.
Implementierung und Evaluation: Ein Prototyp in OCaml wurde implementiert und gegen den State-of-the-Art Model Checker Storm sowie das reine Dice auf einer Vielzahl von Benchmarks getestet.

4. Ergebnisse und Evaluation

Die Evaluation umfasste verschiedene Benchmark-Klassen (Runway, Coupon Collector, Network Reachability, Rabin-Protokoll, Bayes-Netze, 3SAT).

Skalierbarkeit: noDice kann für Programme mit einer hohen Anzahl an Variablen (hohe Dimensionalität des Zustandsraums) signifikant effizienter sein als direkte MDP-Modellierung.
- Beispiel Runway & Coupon Collector: noDice übertrifft Storm deutlich, da Storm den Zustandsraum explodieren lässt, während noDice durch die ADD-Kompilierung kompakte MDPs erzeugt.
- Beispiel Network & Rabin: Bei Problemen mit wenigen Variablen, aber komplexen Übergängen, ist die direkte Modellierung durch Storm manchmal schneller, da der Overhead der noDice-Kompilierung den Gewinn durch die Kompression nicht aufwiegt.
MDP-Größe: noDice konstruiert durchweg deutlich kleinere MDPs als die direkte Kodierung. Bei einigen Benchmarks (z. B. Coupon Collector) reduziert sich die Anzahl der Zustände um Größenordnungen.
Einfluss des Nichtdeterminismus: Die Laufzeit von noDice wird durch den Anteil nichtdeterministischer Operationen kaum beeinflusst. Die Kompilierungszeit dominiert den Gesamtprozess, während die eigentliche Model-Checking-Phase (auf dem kleinen MDP) sehr schnell ist.
State Compression: Eine zusätzliche Kompression von probabilistischen Zuständen im MDP reduziert die Größe weiter, beschleunigt die Inferenz jedoch nicht signifikant, da die Kompilierung ohnehin der Flaschenhals ist.

5. Bedeutung und Ausblick

Das Paper zeigt, dass es möglich ist, effiziente Inferenz für diskrete probabilistische Programme mit Nichtdeterminismus und Bedingung durchzuführen, ohne auf die operationale Semantik zurückgreifen zu müssen, was zu unhandlichen Zustandsräumen führt.

Paradigmenwechsel: Statt den Nichtdeterminismus als Hindernis zu betrachten, wird er durch die Abbildung auf Scheduler in einem MDP systematisch gelöst.
Anwendbarkeit: Die Methode ist besonders geeignet für Probleme mit vielen Variablen und komplexen Abhängigkeiten, wo traditionelle Model-Checker an ihre Grenzen stoßen.
Zukünftige Arbeit: Die Autoren sehen Potenzial in der Erweiterung auf unendliche Schleifen (mittels neuer Techniken für unbeschränkte Iteration) und in der Synthese optimaler Programme (nicht nur der Berechnung der Wahrscheinlichkeit, sondern des Findens der optimalen Strategie).

Zusammenfassend stellt noDice einen wichtigen Schritt dar, um die Lücke zwischen expressiven probabilistischen Programmiersprachen und effizienten Inferenzverfahren für Szenarien zu schließen, die sowohl Unsicherheit (Wahrscheinlichkeit) als auch Unbekanntes (Nichtdeterminismus) beinhalten.