Jaka kombinacja struktur danych skutecznie przechowuje dyskretne sieci bayesowskie?

22

Rozumiem teorię leżącą u podstaw sieci bayesowskich i zastanawiam się, co trzeba zbudować w praktyce. Powiedzmy na przykład, że mam sieć bayesowską (ukierunkowaną) 100 dyskretnych zmiennych losowych; każda zmienna może przyjąć jedną z maksymalnie 10 wartości.

Czy przechowuję wszystkie węzły w DAG i dla każdego węzła przechowuję tabelę prawdopodobieństwa warunkowego (CPT)? Czy istnieją inne struktury danych, z których powinienem skorzystać, aby zapewnić wydajne obliczanie wartości w przypadku zmiany niektórych CPT (oprócz tych używanych przez DAG)?

data-structures machine-learning popiół
źródło
Korzystam z bazy danych sqlite pamięci do przechowywania tabel CP, ponieważ oczekuje się, że DB będą miały wydajne algorytmy i struktury danych do obsługi tabel. Działa w porządku! :)
Pratik Deoghare
Proszę zdefiniować, co rozumiesz przez „efektywność” (pamięć, wydajność itp.) I uwzględnij swoje ograniczenia. Bez nich może to z łatwością zakończyć konkurs na najbardziej wydajny, który zdegraduje do szyfrowania kodu, z którym nigdy nie chciałbym mieć do czynienia w codziennej pracy.
Justin Bozonier
1
@JustinBozonier wymaga mniej pamięci i jest szybki?
Pratik Deoghare

Odpowiedzi:

12

„Najlepsza” struktura danych prawdopodobnie zależy od konkretnego problemu, który próbujesz rozwiązać. Oto jedno podejście, które widziałem (i wykorzystałem sam), które po prostu przechowuje wszystkie informacje i pozostawia je algorytmowi, co z tym zrobić.

  1. Najpierw indeksujesz węzły według unikalnych liczb całkowitych, od 0 do n-1. Następnie po prostu przechowujesz, dla każdego węzła, listę jego rodziców jako tablicę liczb całkowitych --- na przykład w C ++, na przykład, możesz mieć std::vector<std::vector<int> >: pierwszy wektor nad węzłami, drugi wektor wyświetla odpowiednich rodziców). To rejestruje całą strukturę DAG.

  2. Ponadto, ponieważ każdy węzeł ma dokładnie jedną tabelę prawdopodobieństwa warunkowego, można indeksować te z tymi samymi liczbami całkowitymi. Dla każdej tabeli prawdopodobieństwa należy przechowywać jej zakres, tj. Zestaw zmiennych losowych, nad którymi jest zdefiniowany. Po drugie, prawdopodobnie miałbyś jedną dużą listę liczb zmiennoprzecinkowych, która zawiera rzeczywiste prawdopodobieństwa warunkowe (i musisz upewnić się, że indeksowanie jest prawidłowe). Aby ponownie podać przykład w C ++, można zrobić coś takiego:

    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
};

    Dzięki temu możesz użyć a std::vector<CondProbTable>do przechowywania wszystkich swoich CPT.

Ponownie, to w zasadzie tylko przechowuje sieć Bayesa, nie zakłada niczego o tym, co chcesz z tym zrobić. Włączenie zakresu CPT do CondProbTable jest nieco zbędne, ponieważ można je wywnioskować z listy węzłów nadrzędnych opisanej w punkcie 1.

los
źródło
0

Zasadniczo dyskretne CPT to hipermacierze i należy na nie spojrzeć w ten sposób.

Dość powszechnym sposobem przedstawiania hipermacierzy jest użycie tablicy mieszającej za pomocą indeksu ciągów. np. w 2 wymiarach t [1] [2] byłoby t.get („1_2”)

Możliwe są rozwiązania bardziej wydajne pod względem pamięci: jeśli hypermatrix jest rzadki, możesz użyć specjalnej rzadkiej reprezentacji (np. Fuchs 72), jeśli ma strukturę, możesz użyć ADD (schemat decyzyjny algrebraic) lub reguł opartych na logice.

Twoje ostatnie pytanie nie jest bardzo jasne, jednak jeśli spodziewałeś się, że CPT często się zmienia, prawdopodobnie lepiej Ci będzie z płaską reprezentacją CPT ze stołem lub tabelą skrótów.

Nicolas
źródło