Gdzie jest teoria grafów w modelach graficznych?

29

Wprowadzenie do modeli graficznych opisuje je jako „... połączenie teorii grafów z teorią prawdopodobieństwa”.

Rozumiem część teorii prawdopodobieństwa, ale mam problem ze zrozumieniem, gdzie dokładnie pasuje teoria grafów. Jakie spostrzeżenia z teorii grafów pomogły nam pogłębić nasze rozumienie rozkładów prawdopodobieństwa i podejmowania decyzji w warunkach niepewności?

Szukam konkretnych przykładów poza oczywistym zastosowaniem terminologii teoretycznej grafów w PGM, takich jak klasyfikowanie PGM jako „drzewa” lub „dwustronnego” lub „nieukierowanego” itp.

graphical-model graph-theory distributions Vimal
źródło

Odpowiedzi:

33

Bardzo mało jest prawdziwej teorii grafów matematycznych w probabilistycznych modelach graficznych, gdzie przez prawdziwą teorię wykresów matematycznych rozumiem dowody dotyczące klików, rzędów wierzchołków, twierdzeń o maksymalnym przepływie min-cut i tak dalej. Nie stosuje się nawet czegoś tak podstawowego, jak twierdzenie Eulera i lemat handhakingowy, ale przypuszczam, że można je przywołać, aby sprawdzić niektóre właściwości kodu komputerowego używanego do aktualizacji szacunków probabilistycznych. Co więcej, modele graficzne probabilisty rzadko używają więcej niż podzbioru klas grafów, takich jak wykresy wieloskładnikowe. Twierdzenia o przepływach na wykresach nie są wykorzystywane w probabilistycznych modelach graficznych.

Gdyby uczeń A był ekspertem w zakresie prawdopodobieństwa, ale nie wiedział nic o teorii grafów, a uczeń B był ekspertem w teorii grafów, ale nie wiedział nic o prawdopodobieństwie, wówczas A z pewnością nauczyłby się i zrozumiał probabilistyczne modele graficzne szybciej niż B.

David G. Stork
źródło
8

W ścisłym znaczeniu teoria grafów wydaje się luźno związana z PGM. Przydają się jednak algorytmy graficzne . PGM rozpoczęły się od wnioskowania o przekazywaniu wiadomości, które jest podzbiorem ogólnej klasy algorytmów przekazywania wiadomości na wykresach (być może dlatego jest w nich słowo „graficzne”). Algorytmy wycinania wykresów są szeroko stosowane do wnioskowania losowego pola Markowa w wizji komputerowej; opierają się na wynikach podobnych do twierdzenia Forda-Fulkersona (maksymalny przepływ równa się min. cięcie); najpopularniejsze algorytmy to prawdopodobnie Bojkow-Kołmogorow i IBFS.

Referencje [Murphy, 2012 , §22.6.3] obejmuje wykorzystanie cięć graficznych do wnioskowania MAP. Zobacz także [Kolmogorom i Zabih, 2004 ; Boykov i in., PAMI 2001] , które obejmują raczej optymalizację niż modelowanie.

Roman Shapovalov
źródło
Warto zauważyć, że algorytmy wycinania wykresów są używane w MRF. Czy możesz wskazać odniesienie? Na podstawie powyższej odpowiedzi Davida Stork'a wydaje się, że algorytmy te powstają z powodu faktu, że teoria grafów była użytecznym narzędziem do modelowania, a nie jakiegoś fundamentalnego związku między teorią grafów a PGM.
Vimal
Dodałem referencje, jak prosiłeś. Od ostatniego stwierdzenia, w jaki sposób możemy oddzielić przyczyny, tj. Stwierdzić, czy ma ono zasadnicze znaczenie, czy nie?
Roman Shapovalov,
@overrider czy możesz podać pełne referencje, aby dokumenty można było łatwo przeszukiwać ..? Googling może prowadzić ludzi do referencji, ale może też prowadzić do marnowania czasu na nieistotne wyniki. Warto więc dodać tytuły, wydawców, nazwy czasopism, linki itp.
Tim
2
Algorytmy wycinania wykresów są przydatne w wizji komputerowej, ale nie w probabilistycznych modelach graficznych. Jednym problemem w obrazie stereo jest problem z korespondencją: znalezienie, które punkty na obrazie A odpowiadają punktom na obrazie B. Można ustawić wykres, w którym wierzchołki odpowiadają punktom charakterystycznym na dwóch obrazach, a wykres przedstawia wszystkie możliwe zależności. Następnie problem znalezienia „właściwych” korespondencji można odrzucić jako problem wycięty na wykresie. Nie ma takiego zastosowania w ogólnych modelach graficznych, chociaż przypuszczam, że można spróbować zmapować ten problem z widzeniem komputerowym na modele graficzne.
David G. Stork,
2
@ DavidG.Stork Istnieją inne problemy z widzeniem komputerowym, które stosują cięcia wykresów w podobny sposób: segmentacja obrazu, tworzenie kolaży itp., Więc podejście jest dość ogólne. Problemy te można naturalnie wyrazić w kategoriach niekierowanych modeli graficznych (choć nie zawsze tak robią dokumenty). Umożliwia to stosowanie różnych algorytmów wnioskowania MRF, a także dopasowanie modelu. Z drugiej strony, cięcia wykresów mogą zoptymalizować dość duży podzbiór MRF, a zatem mogą być stosowane poza wzrokiem, np. Do analizy sieci społecznościowych (chociaż nie pamiętam teraz konkretnych prac).
Roman Shapovalov,
4

Przeprowadzono pewne prace nad związkiem między łatwością dekodowania kodów kontroli parzystości o niskiej gęstości (która osiąga doskonałe wyniki, gdy uważa się, że jest to wykres probablistyczny i stosuje propagację Loopy Belief Propagation), a obwodem wykresu utworzonym przez macierz kontroli parzystości . Ten link do obwodu pochodzi z czasów, gdy wynaleziono LDPC [1], ale w ostatnim dziesięcioleciu były dalsze prace [2] [3] po tym, jak Mackay i wsp. [4] odkryli je osobno, a ich właściwości zostały zauważone .

Często widzę komentarz Pearl'a na temat czasu konwergencji propagacji przekonań w zależności od cytowanej średnicy wykresu. Ale nie znam żadnej pracy dotyczącej średnic grafów w grafach innych niż drzewne i jaki to ma efekt.

  1. RG Gallager. Kody kontroli parzystości o niskiej gęstości. MIT Press, 1963
  2. IE Bocharova, F. Hug, R. Johannesson, BD Kudryashov i RV Satyukov. Nowe kody kontroli parzystości o niskiej gęstości z dużym obwodem oparte na hipergraphach. W Information Theory Proceedings (ISIT), 2010 Międzynarodowe sympozjum IEEE na, strony 819–823, 2010.
  3. SC Tatikonda. Konwergencja algorytmu sumy iloczynu. W warsztacie teorii informacji, 2003. Postępowanie. 2003 IEEE, strony 222 - 225, 2003
  4. David JC MacKay i RM Neal. Blisko Shannon ogranicza wydajność kodów kontroli parzystości o niskiej gęstości. Electronics Letters, 33 (6): 457–458, 1997.
Poklepać
źródło
3

Jednym z udanych zastosowań algorytmów grafowych w probabilistycznych modelach graficznych jest algorytm Chow-Liu . Rozwiązuje problem znalezienia optymalnej (graficznej) struktury grafu i opiera się na algorytmie maksymalnych drzew opinających (MST).

Wspólne prawdopodobieństwo dla drzewiastego modelu graficznego można zapisać jako: Możemy zapisać znormalizowane prawdopodobieństwo dziennika w następujący sposób: gdzie to wzajemna informacja między i biorąc pod uwagę empiryczne maksymalne prawdopodobieństwo (ML) rozkład, który zlicza ile razy węzeł był w stanie . Ponieważ pierwszy termin jest niezależny od topologii

p(x|T)=∏t∈Vp(xt)∏(s,t)∈Ep(xs,xt)p(xs)p(xt)
1Nlog⁡P(D|θ,T)=∑t∈V∑kpML(xt=k)log⁡pML(xt=k)+∑(s,t)∈EI(xs;xt|θst)
I(xs;xt|θst)xsxtxkT, możemy to zignorować i skupić się na maksymalizacji drugiego terminu.

Prawdopodobieństwo dziennika jest zmaksymalizowane poprzez obliczenie maksymalnego drzewa rozpinającego wagę, gdzie wagi krawędzi są parami wzajemnych informacji . Maksymalna waga obejmujące drzewo można znaleźć za pomocą Algorytm Prima i Algorytm Kruskala .I(xs;xt|θst)

Vadim Smolyakov
źródło
Cześć Vadim. Dzięki za twoją odpowiedź. Ma to sens jako sformułowanie w kategoriach teoretycznych grafów. Ale można to również postrzegać jako problem optymalizacji. Istotą pytania było zapytanie o bardziej fundamentalny związek. Na przykład można sformułować problem sortowania jako sortowanie topologiczne na wykresie, gdzie węzłami są liczby, a strzałki oznaczają relację <=. Ale to nie stanowi fundamentalnego związku między algorytmami sortowania i algorytmów graficznych, prawda?
Vimal