Algorytm drzewa skrzyżowań

Przykład drzewa skrzyżowań

Algorytm drzewa połączeń (znany również jako „drzewo kliki”) to metoda stosowana w uczeniu maszynowym do wydobywania marginalizacji z ogólnych grafów . Zasadniczo polega to na przeprowadzeniu propagacji przekonań na zmodyfikowanym grafie zwanym drzewem połączeń . Wykres nazywany jest drzewem, ponieważ rozgałęzia się na różne sekcje danych; węzłami zmiennych są gałęzie. Podstawowym założeniem jest eliminacja cykli poprzez łączenie ich w pojedyncze węzły. Wiele rozbudowanych klas zapytań może być kompilowanych w tym samym czasie w większe struktury danych. Istnieją różne algorytmy spełniające określone potrzeby i określające, co należy obliczyć. Algorytmy wnioskowania zbierają nowe zmiany w danych i obliczają je na podstawie dostarczonych nowych informacji.

Algorytm drzewa skrzyżowań

Algorytm Hugina

• Jeśli wykres jest skierowany, moralizuj go, aby stał się niekierowany.
• Przedstaw dowody.
• Wykonaj triangulację wykresu, aby był akordowy.
• Skonstruuj drzewo połączeń z grafu triangulowanego (wierzchołki drzewa połączeń będziemy nazywać „ superwęzłami ”).
• Propaguj prawdopodobieństwa wzdłuż drzewa połączeń (poprzez propagację przekonań )

Zauważ, że ten ostatni krok jest nieefektywny dla grafów o dużej szerokości drzewa . Obliczanie komunikatów, które mają być przekazywane między superwęzłami, wymaga dokładnej marginalizacji zmiennych w obu superwęzłach. Wykonanie tego algorytmu dla wykresu o szerokości drzewa k będzie zatem wymagało co najmniej jednego obliczenia, które zajmie czas wykładniczy w k. Jest to przekazywania wiadomości . Algorytm Hugina wymaga mniej obliczeń , aby znaleźć rozwiązanie w porównaniu z algorytmem Shafera-Shenoya.

Algorytm Shafera-Shenoya

• Obliczane rekurencyjnie
• Wielokrotne rekursje algorytmu Shafera-Shenoya skutkują algorytmem Hugina
• Znalezione przez równanie przekazywania wiadomości
• separatora nie są zapisywane

Algorytm Shafera-Shenoya jest iloczynem sumy drzewa połączeń. Jest używany, ponieważ uruchamia programy i zapytania wydajniej niż algorytm Hugina. Algorytm umożliwia obliczenia warunków warunkowych dla funkcji przekonań . Aby wykonać lokalne obliczenia, potrzebne są wspólne dystrybucje .

Podstawowa teoria

Przykład dynamicznej sieci bayesowskiej

Pierwszy krok dotyczy tylko sieci bayesowskich i jest procedurą zamiany grafu skierowanego na nieskierowany . Robimy to, ponieważ pozwala to na uniwersalną stosowalność algorytmu, niezależnie od kierunku.

Drugim krokiem jest ustawienie zmiennych na ich obserwowaną wartość. Jest to zwykle potrzebne, gdy chcemy obliczyć prawdopodobieństwa warunkowe, więc ustalamy wartość zmiennych losowych, od których uzależniamy. Mówi się również, że zmienne te są ograniczone do ich określonej wartości.

Przykład wykresu akordowego

Trzecim krokiem jest upewnienie się, że wykresy są akordowe , jeśli jeszcze nie są akordowe. Jest to pierwszy istotny krok algorytmu. Korzysta z następującego twierdzenia:

Twierdzenie: Dla grafu nieskierowanego G następujące właściwości są równoważne:

• Wykres G jest triangulowany.
• Wykres kliki G ma drzewo skrzyżowań.
• Istnieje porządek eliminacji dla G, który nie prowadzi do żadnych dodanych krawędzi.

Tak więc, triangulując wykres, upewniamy się, że istnieje odpowiednie drzewo połączeń. Zwykłym sposobem na to jest ustalenie kolejności eliminacji dla jego węzłów, a następnie uruchomienie eliminacji zmiennych . Algorytm eliminacji zmiennych stwierdza, że ​​algorytm musi być uruchamiany za każdym razem, gdy pojawia się inne zapytanie. Spowoduje to dodanie większej liczby krawędzi do początkowego wykresu, w taki sposób, że wynik będzie wykresem akordowym . Wszystkie grafy akordowe mają drzewo połączeń. Następnym krokiem jest zbudowanie drzewa połączeń . W tym celu używamy wykresu z poprzedniego kroku i tworzymy odpowiadający mu wykres kliki . Teraz następne twierdzenie daje nam sposób na znalezienie drzewa skrzyżowań:

Twierdzenie: Biorąc pod uwagę graf triangulowany, zważ krawędzie grafu kliki przez ich liczność, |A∩B|, przecięcia sąsiednich klik A i B. Wtedy dowolne drzewo rozpinające grafu kliki o maksymalnej wadze jest drzewem połączeń .

Tak więc, aby skonstruować drzewo połączeń, musimy po prostu wyodrębnić drzewo rozpinające o maksymalnej wadze z wykresu kliki. Można to skutecznie zrobić, na przykład modyfikując algorytm Kruskala . Ostatnim krokiem jest zastosowanie propagacji przekonań do otrzymanego drzewa połączeń.

Użycie: Wykres drzewa połączeń służy do wizualizacji prawdopodobieństwa wystąpienia problemu. Drzewo może stać się drzewem binarnym, tworząc rzeczywisty budynek drzewa. Szczególne zastosowanie można znaleźć w autoenkoderach , które automatycznie łączą graf i przechodzącą sieć na dużą skalę.

Algorytmy wnioskowania

Kondycjonowanie zestawu cięć

Propagacja błędnego przekonania: inna metoda interpretacji złożonych wykresów. Propagacja błędnego przekonania jest stosowana, gdy potrzebne jest rozwiązanie przybliżone zamiast rozwiązania dokładnego . Jest to przybliżony wniosek .

Kondycjonowanie zestawu fragmentów: używane z mniejszymi zestawami zmiennych. Kondycjonowanie zbioru cięć umożliwia tworzenie prostszych wykresów, które są łatwiejsze do odczytania, ale nie są dokładne .

•    Lauritzen, Steffen L.; Spiegelhalter, David J. (1988). „Lokalne obliczenia z prawdopodobieństwami na strukturach graficznych i ich zastosowanie w systemach eksperckich”. Dziennik Królewskiego Towarzystwa Statystycznego . Seria B (metodologiczna) . 50 (2): 157–224. doi : 10.1111/j.2517-6161.1988.tb01721.x . JSTOR 2345762 . MR 0964177 .
•   Dawid, AP (1992). „Zastosowania ogólnego algorytmu propagacji dla probabilistycznych systemów ekspertowych”. Statystyka i informatyka . 2 (1): 25–26. doi : 10.1007/BF01890546 . S2CID 61247712 .
•   Huang, Cecil; Darwiche, Adnan (1996). „Wnioskowanie w sieciach przekonań: przewodnik proceduralny” . International Journal of Approximate Reasoning . 15 (3): 225–263. CiteSeerX 10.1.1.47.3279 . doi : 10.1016/S0888-613X(96)00069-2 .
• Paskin, Mark A. „Krótki kurs modeli graficznych: 3. Algorytmy drzewa skrzyżowań” (PDF) . Zarchiwizowane od oryginału w dniu 19 marca 2015 r. {{ cite journal }} : Cite journal wymaga |journal= ( pomoc ) CS1 maint: nieodpowiedni adres URL ( link )
• Lepar, V., Shenoy, P. (1998). „Porównanie architektur Lauritzena-Spiegelhaltera, Hugina i Shenoya-Shafera do obliczania marginesów rozkładów prawdopodobieństwa”. https://arxiv.org/ftp/arxiv/papers/1301/1301.7394.pdf