In welcher Kombination von Datenstrukturen werden diskrete Bayes'sche Netzwerke effizient gespeichert?

Ich verstehe die Theorie hinter den Bayes'schen Netzwerken und frage mich, was es braucht, um ein solches Netzwerk in der Praxis aufzubauen. Nehmen wir für dieses Beispiel an, ich habe ein Bayes'sches (gerichtetes) Netzwerk von 100 diskreten Zufallsvariablen; Jede Variable kann einen von bis zu 10 Werten annehmen.

Speichere ich alle Knoten in einer DAG und für jeden Knoten seine CPT (Conditional Probability Table)? Gibt es andere Datenstrukturen, die ich verwenden sollte, um eine effiziente Berechnung von Werten zu gewährleisten, wenn sich einige CPTs ändern (abgesehen von denen, die von einer DAG verwendet werden)?

Die "beste" Datenstruktur hängt wahrscheinlich davon ab, welches bestimmte Problem Sie damit lösen möchten. Hier ist ein Ansatz, den ich gesehen habe (und den ich selbst verwendet habe), der einfach alle Informationen speichert und dem Algorithmus überlässt, was damit zu tun ist.

1. Zuerst indizieren Sie die Knoten nach eindeutigen Ganzzahlen von 0 bis n-1. Dann speichern Sie einfach für jeden Knoten die Liste seiner Eltern als ein Array von ganzen Zahlen - in C ++ könnten Sie zum Beispiel haben std::vector<std::vector<int> >: einen ersten Vektor über Knoten, einen zweiten Vektor listet die jeweiligen Eltern auf). Das erfasst die gesamte DAG-Struktur.

2. Da jedem Knoten genau eine bedingte Wahrscheinlichkeitstabelle zugeordnet ist, können Sie außerdem diejenigen mit denselben ganzzahligen IDs indizieren. Für jede Wahrscheinlichkeitstabelle müssen Sie ihren Gültigkeitsbereich speichern, dh die Menge der Zufallsvariablen, über die sie definiert ist. Zweitens hätten Sie wahrscheinlich eine große Liste von Gleitkommazahlen, die die tatsächlichen bedingten Wahrscheinlichkeiten enthalten (und Sie möchten sicherstellen, dass Sie die richtige Indizierung haben). Um noch einmal ein C ++ - Beispiel zu geben, könnte so etwas tun:

   struct CondProbTable {
       std::vector<int> scope;    // list of random variables the CPT is defined over
       std::vector<double> table; // appropriately sized and indexed table of
                                  // conditional probabilities
   };
   

   Mit a können Sie std::vector<CondProbTable>alle Ihre CPTs speichern.

Auch hier wird im Grunde nur das Bayes-Netz gespeichert, es wird jedoch nicht davon ausgegangen, was Sie damit tun möchten. Das Einbeziehen des CPT-Bereichs in CondProbTable ist etwas redundant, da dies aus der Liste der unter Punkt 1 beschriebenen übergeordneten Knoten abgeleitet werden kann.

Grundsätzlich sind diskrete CPT Hypermatrizen, und Sie sollten sie auf diese Weise betrachten.

Eine übliche Art, eine Hypermatrix darzustellen, ist die Verwendung einer Hash-Tabelle unter Verwendung eines String-Index. zB in 2 Dimensionen wäre t [1] [2] t.get ("1_2")

Eine speichereffizientere Lösung ist möglich: Wenn die Hypermatrix spärlich ist, können Sie eine spezielle spärliche Darstellung verwenden (z. B. Fuchs 72), wenn sie strukturiert ist, können Sie ADD (algrebraisches Entscheidungsdiagramm) oder logikbasierte Regeln verwenden.

Ihre letzte Frage ist nicht sehr klar. Wenn Sie jedoch eine häufige Änderung Ihres CPT erwartet haben, ist es wahrscheinlich besser, wenn Sie eine flache Darstellung des CPT mit einer Tabelle oder einer Hash-Tabelle haben.