Losowe pole Markowa - Markov random field

Przykład pola losowego Markowa. Każda krawędź reprezentuje zależność. W tym przykładzie: A zależy od B i D. B zależy od A i D. D zależy od A, B i E. E zależy od D i C. C zależy od E.

W dziedzinie fizyki i prawdopodobieństwa , losowe pole Markowa ( MRF ), sieć Markowa lub nieskierowany model graficzny jest zbiorem zmiennych losowych posiadających właściwość Markowa opisaną przez graf nieskierowany . Innymi słowy, pole losowe mówi się Markow losowe pole jeżeli spełnia własności Markowa.

Sieć Markowa lub MRF jest podobna do sieci bayesowskiej pod względem reprezentacji zależności; różnice polegają na tym, że sieci bayesowskie są ukierunkowane i acykliczne , podczas gdy sieci Markowa są nieskierowane i mogą być cykliczne. Zatem sieć Markowa może reprezentować pewne zależności, których sieć bayesowska nie może (takie jak zależności cykliczne); z drugiej strony nie może reprezentować pewnych zależności, które może sieć bayesowska (takich jak indukowane zależności). Podstawowy wykres pola losowego Markowa może być skończony lub nieskończony.

Gdy łączna gęstość prawdopodobieństwa zmiennych losowych jest ściśle dodatnia, jest również określana jako pole losowe Gibbsa , ponieważ zgodnie z twierdzeniem Hammersleya-Clifforda może być następnie reprezentowana przez miarę Gibbsa dla odpowiedniego (zdefiniowanego lokalnie) funkcja energii. Prototypowym polem losowym Markowa jest model Isinga ; w rzeczywistości pole losowe Markowa zostało wprowadzone jako ogólne ustawienie dla modelu Isinga. W dziedzinie sztucznej inteligencji pole losowe Markowa jest wykorzystywane do modelowania różnych zadań niskiego i średniego poziomu w przetwarzaniu obrazu i wizji komputerowej .

Definicja

Biorąc pod uwagę graf nieskierowany , zbiór zmiennych losowych indeksowanych przez   pole losowe Markowa w odniesieniu do tego,   czy spełniają lokalne właściwości Markowa: ${\ Displaystyle G = (V, E)}$${\ Displaystyle X = (X_ {v}) _ {v \ w V}}$${\ Displaystyle V}$${\ Displaystyle G}$

Własność Markowa w parach: Dowolne dwie niesąsiadujące zmienne są warunkowo niezależne, biorąc pod uwagę wszystkie inne zmienne:

${\ Displaystyle X_ {u} \ sprawca \! \! \! \ sprawca X_ {v} \ mid X_ {V \ setminus \ {u, v \}}}$

Lokalna właściwość Markowa: Zmienna jest warunkowo niezależna od wszystkich innych zmiennych, biorąc pod uwagę jej sąsiadów:

${\ Displaystyle X_ {v} \ sprawca \! \! \! \ sprawca X_ {V \ setminus \ operatorname {N} [v]} \ mid X_ {\ operatorname {N} (v)}}$

gdzie jest zbiorem sąsiadów , i jest zamkniętym osiedlu z .${\textstyle \operatorname {N} (v)}$${\displaystyle v}$${\ Displaystyle \ operatorname {N} [v] = v \ filiżanka \ operatorname {N} (v)}$${\displaystyle v}$

Globalna właściwość Markowa: dowolne dwa podzbiory zmiennych są warunkowo niezależne, biorąc pod uwagę podzbiór oddzielający:

${\ Displaystyle X_ {A} \ sprawca \! \! \! \ sprawca X_ {B} \ mid X_ {S}}$

gdzie każda ścieżka od węzła do węzła w przechodzi przez .${\ Displaystyle A}$${\ Displaystyle B}$${\displaystyle S}$

Globalna własność Markowa jest silniejsza niż lokalna własność Markowa, która z kolei jest silniejsza niż własność Pairwise. Jednak powyższe trzy własności Markowa są równoważne dla rozkładów dodatnich (tych, które przypisują skojarzonym zmiennym tylko niezerowe prawdopodobieństwa).

Faktoryzacja klików

Ponieważ właściwość Markowa arbitralnego rozkładu prawdopodobieństwa może być trudna do ustalenia, powszechnie używaną klasą pól losowych Markowa są te, które można podzielić na czynniki zgodnie z klikami grafu.

Mając zestaw zmiennych losowych , niech będzie prawdopodobieństwo określonej konfiguracji pola w  . Oznacza to, że jest prawdopodobieństwo znalezienia, że ​​zmienne losowe przyjmą określoną wartość . Ponieważ jest ustawiona, to prawdopodobieństwo, należy rozumieć, jakie należy podjąć w odniesieniu do łącznego rozkładu z . ${\ Displaystyle X = (X_ {v}) _ {v \ w V}}$${\ Displaystyle P (X = x)}$${\displaystyle x}$${\ Displaystyle X}$${\ Displaystyle P (X = x)}$${\ Displaystyle X}$${\displaystyle x}$${\ Displaystyle X}$${\displaystyle x}$${\ Displaystyle X_ {v}}$

Jeśli tę gęstość połączeń można rozłożyć na czynniki przez kliki : ${\ Displaystyle G}$

${\ Displaystyle P (X = x) = \ prod _ {C \ w \ operatorname {cl} (G)} \ phi _ {C} (x_ {C})}$

następnie tworzy losowe pole Markowa względem . Oto zbiór klik . Definicja jest równoważna, jeśli używa się tylko maksymalnych klik. Funkcje są czasami określane jako potencjały czynnikowe lub potencjały klikowe . Należy jednak zauważyć, że w użyciu jest sprzeczna terminologia: słowo potencjał jest często stosowane do logarytmu . To dlatego, że w mechanice statystycznej , ma bezpośredni interpretację jako energii potencjalnej z konfiguracją . ${\ Displaystyle X}$${\ Displaystyle G}$${\ Displaystyle \ operatorname {cl} (G)}$${\ Displaystyle G}$${\ Displaystyle \ phi _ {C}}$${\ Displaystyle \ phi _ {C}}$${\ Displaystyle \ log (\ phi _ {C})}$ ${\displaystyle x_{C}}$

Niektóre MRF nie uwzględniają faktoryzacji: prosty przykład można skonstruować na cyklu 4 węzłów z pewnymi nieskończonymi energiami, tj. konfiguracjami zerowych prawdopodobieństw, nawet jeśli jedna, bardziej odpowiednio, pozwala nieskończonym energiom oddziaływać na cały wykres na . ${\ Displaystyle V}$

Faktoryzacja MRF, jeśli spełniony jest co najmniej jeden z następujących warunków:

• gęstość jest dodatnia (według twierdzenia Hammersleya-Clifforda )
• wykres jest akordowy (przez równoważność z siecią bayesowską )

Gdy taka faktoryzacja istnieje, możliwe jest skonstruowanie grafu czynnikowego dla sieci.

Rodzina wykładnicza

Każde dodatnie pole losowe Markowa można zapisać jako rodzinę wykładniczą w postaci kanonicznej z funkcjami cech takimi, że pełny rozkład można zapisać jako ${\displaystyle f_{k}}$

${\ Displaystyle P (X = x) = {\ Frac {1} {Z}} \ exp \ lewo (\ suma _ {k} w_ {k} ^ {\ top} f_ {k} (x_ {\ {k \}})\Prawidłowy)}$

gdzie notacja

${\ Displaystyle w_ {k} ^ {\ top} f_ {k} (x_ {\ {k \}}) = \ suma _ {i = 1} ^ {N_ {k}} w_ {k, i} \ cdot f_{k,i}(x_{\{k\}})}$

jest po prostu iloczynem skalarnym przez konfiguracje pól, a Z jest funkcją podziału :

${\ Displaystyle Z = \ suma _ {x \ w {\ mathcal {X}}} \ exp \ lewo (\ suma _ {k} w_ {k} ^ {\ top} f_ {k} (x_ {\ {k \}})\Prawidłowy).}$

Tutaj oznacza zbiór wszystkich możliwych przypisań wartości do wszystkich zmiennych losowych sieci. Zwykle funkcje cech są definiowane w taki sposób, że są wskaźnikami konfiguracji kliki, tj. jeśli odpowiada i- tej możliwej konfiguracji k- tej kliki, a 0 w przeciwnym razie. Model ten jest równoważny z modelem faktoryzacji kliki podanym powyżej, jeśli jest licznością kliki, a waga cechy odpowiada logarytmowi odpowiedniego czynnika kliki, tj. , gdzie jest i -tą możliwą konfiguracją k - th klika, tj i wartość -tego w domenie kliki . ${\displaystyle {\mathcal {X}}}$${\displaystyle f_{k,i}}$ ${\ Displaystyle f_ {k, i} (x_ {\ {k \}}) = 1}$${\displaystyle x_{\{k\}}}$${\ Displaystyle N_ {k} = | \ operatorname {dom} (C_ {k}) |}$${\displaystyle f_{k,i}}$ ${\ Displaystyle w_ {k, i} = \ log \ phi (c_ {k, i})}$${\displaystyle c_{k,i}}$${\ Displaystyle C_ {k}}$

Prawdopodobieństwo P jest często nazywane miarą Gibbsa. Wyrażenie pola Markowa logistycznym modelu jest to możliwe tylko wtedy, gdy wszystkie czynniki Clique są niezerowe, to jest gdy żaden z tych elementów są przypisane prawdopodobieństwo 0. To umożliwia technik, Algebra macierzy do zastosowania, na przykład , że im ślad macierzy to log wyznacznika , z macierzową reprezentacją grafu wynikającą z macierzy padania grafu . ${\displaystyle {\mathcal {X}}}$

Znaczenie funkcji podziału Z polega na tym, że wiele pojęć z mechaniki statystycznej , takich jak entropia , bezpośrednio uogólnia się na przypadek sieci Markowa i dzięki temu można uzyskać intuicyjne zrozumienie. Ponadto funkcja podziału umożliwia zastosowanie metod wariacyjnych do rozwiązania problemu: można przypisać siłę napędową do jednej lub więcej zmiennych losowych i zbadać reakcję sieci w odpowiedzi na to zaburzenie . Tak więc, na przykład, można dodać człon sterujący J _v , dla każdego wierzchołka v grafu, do funkcji podziału, aby uzyskać:

${\ Displaystyle Z [J] = \ suma _ {x \ w {\ mathcal {X}}} \ exp \ lewo (\ suma _ {k} w_ {k} ^ {\ top} f_ {k} (x_ { \{k\}})+\sum _{v}J_{v}x_{v}\right)}$

Formalne różnicowanie względem J _v daje wartość oczekiwaną zmiennej losowej X _v związanej z wierzchołkiem v :

${\ Displaystyle E [X_ {v}] = {\ Frac {1} {Z}} \ lewo. {\ Frac {\ częściowy Z [J]} {\ częściowy J_ {v}}} \ prawej | _ {J_ {v}=0}.}$

Podobnie obliczane są funkcje korelacji ; dwupunktowa korelacja to:

${\ Displaystyle C [X_ {u} X_ {v}] = {\ Frac {1} {Z}} \ lewo. {\ Frac {\ częściowy ^ {2} Z [J]} {\ częściowy J_ {u }\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}.}$

Niestety, chociaż prawdopodobieństwo logistycznej sieci Markowa jest wypukłe, ocena prawdopodobieństwa lub gradientu prawdopodobieństwa modelu wymaga wnioskowania w modelu, co jest ogólnie niewykonalne obliczeniowo (patrz „Wnioskowanie” poniżej).

Przykłady

Gaussa

Wielowymiarowy rozkład normalny tworzy losową pola Markowa w odniesieniu do wykresu jeśli brakuje krawędzie odpowiadają zer na matrycy precyzyjnej (odwrotność macierzy kowariancji ) ${\ Displaystyle G = (V, E)}$

${\ Displaystyle X = (X_ {v}) _ {v \ w V} \ sim {\ mathcal {N}} ({\ pogrubienie {\ mu}}, \ Sigma)}$

takie, że

${\ Displaystyle (\ Sigma ^ {-1}) _ {uv} = 0 \ quad {\ tekst {iff}} \ quad \ {u, v \} \ notin E.}$

Wnioskowanie

Podobnie jak w sieci bayesowskiej, można obliczyć rozkład warunkowy zbioru węzłów o danych wartościach na inny zbiór węzłów w polu losowym Markowa przez zsumowanie wszystkich możliwych przypisań do ; nazywa się to wnioskowaniem dokładnym . Jednak wnioskowanie dokładne jest problemem #P-zupełnym , a zatem obliczeniowo niewykonalne w ogólnym przypadku. Techniki aproksymacyjne, takie jak łańcuch Markowa Monte Carlo i pętlowa propagacja przekonań są często bardziej wykonalne w praktyce. Niektóre szczególne podklasy MRF, takie jak drzewa (patrz drzewo Chow-Liu ), mają algorytmy wnioskowania wielomianowego w czasie; odkrywanie takich podklas jest aktywnym tematem badawczym. Istnieją również podklasy MRF, które umożliwiają wydajne wnioskowanie MAP lub najprawdopodobniej przypisanie; przykłady obejmują sieci asocjacyjne. Inną interesującą podklasą jest podklasa modeli dekompozycyjnych (gdy graf jest akordowy ): mając formę zamkniętą dla MLE , można odkryć spójną strukturę dla setek zmiennych. ${\ Displaystyle V '= \ {v_ {1} \ ldots, v_ {i} \}}$${\ Displaystyle W' = \ {w_ {1}, \ ldots, w_ {j} \}}$${\displaystyle u\notin V',W'}$

Warunkowe pola losowe

Jednym z godnych uwagi wariantów pola losowego Markowa jest warunkowe pole losowe , w którym każda zmienna losowa może być również uwarunkowana zbiorem obserwacji globalnych . W tym modelu każda funkcja jest odwzorowaniem wszystkich przypisań zarówno do kliki k, jak i obserwacji do nieujemnych liczb rzeczywistych. Ta forma sieci Markowa może być bardziej odpowiednia do tworzenia klasyfikatorów dyskryminacyjnych , które nie modelują rozkładu na obserwacjach. CRF zostały zaproponowane przez Johna D. Lafferty'ego , Andrew McCalluma i Fernando CN Pereira w 2001 roku. ${\displaystyle o}$${\ Displaystyle \ phi _ {k}}$ ${\displaystyle o}$

Zróżnicowane aplikacje

Losowe pola Markowa znajdują zastosowanie w różnych dziedzinach, od grafiki komputerowej po wizję komputerową, uczenie maszynowe czy biologię obliczeniową . MRF są wykorzystywane w przetwarzaniu obrazu do generowania tekstur, ponieważ mogą być wykorzystywane do generowania elastycznych i stochastycznych modeli obrazu. W modelowaniu obrazu zadaniem jest znalezienie odpowiedniego rozkładu natężenia danego obrazu, gdzie przydatność zależy od rodzaju zadania, a MRF są wystarczająco elastyczne, aby można je było wykorzystać do syntezy obrazu i tekstury, kompresji i przywracania obrazu, segmentacji obrazu , obrazu 3D wnioskowanie z obrazów 2D, rejestracja obrazu , synteza tekstur , superrozdzielczość , dopasowanie stereo i wyszukiwanie informacji . Mogą być używane do rozwiązywania różnych problemów widzenia komputerowego, które mogą być przedstawiane jako problemy minimalizacji energii lub problemy, w których różne regiony muszą być rozróżniane za pomocą zestawu cech rozróżniających, w ramach losowego pola Markowa, w celu przewidzenia kategorii regionu. Pola losowe Markowa były uogólnieniem modelu Isinga i od tego czasu były szeroko stosowane w optymalizacjach kombinatorycznych i sieciach.

Zobacz też

Bibliografia