Markovovo náhodné pole - Markov random field

Příklad Markovova náhodného pole.
Příklad Markovova náhodného pole. Každá hrana představuje závislost. V tomto případě: A závisí na B a D. B závisí na A a D. D závisí na A, B a E. E závisí na D a C. C závisí na E.

V oblasti fyziky a pravděpodobnosti je Markovovo náhodné pole ( MRF ), Markovova síť nebo neorientovaný grafický model sada náhodných proměnných, které mají Markovovu vlastnost popsanou neorientovaným grafem . Jinými slovy, náhodné pole je označováno jako Markovovo náhodné pole, pokud splňuje Markovovy vlastnosti.

Síť Markov nebo MRF je ve své reprezentaci závislostí podobná Bayesovské síti ; rozdíly jsou v tom, že Bayesovské sítě jsou směrované a acyklické , zatímco Markovovy sítě nejsou směrované a mohou být cyklické. Síť Markov tedy může představovat určité závislosti, které bayesovská síť nemůže (například cyklické závislosti); na druhé straně nemůže představovat určité závislosti, které může bajesovská síť (například indukované závislosti). Podkladový graf Markovova náhodného pole může být konečný nebo nekonečný.

Když je společná hustota pravděpodobnosti náhodných proměnných striktně kladná, je také označována jako Gibbsovo náhodné pole , protože podle Hammersley -Cliffordovy věty ji pak lze reprezentovat Gibbsovým měřítkem pro příslušnou (lokálně definovanou) energetická funkce. Prototypové Markovovo náhodné pole je Isingův model ; skutečně bylo jako obecné nastavení pro Isingův model zavedeno Markovovo náhodné pole. V oblasti umělé inteligence se Markovovo náhodné pole používá k modelování různých úkolů nízké až střední úrovně ve zpracování obrazu a počítačového vidění .

Definice

Vzhledem k neorientovanému grafu sada náhodných proměnných indexovaných podle   Markovova náhodného pole s ohledem na to,   zda splňují místní Markovovy vlastnosti:

Párová Markovova vlastnost: Libovolné dvě nesousedící proměnné jsou podmíněně nezávislé vzhledem ke všem ostatním proměnným:
Místní vlastnost Markov: Proměnná je podmíněně nezávislá na všech ostatních proměnných vzhledem k jejím sousedům:
kde je množina sousedů , a je uzavřený sousedství of .
Globální vlastnost Markov: Jakékoli dvě podmnožiny proměnných jsou podmíněně nezávislé vzhledem k oddělovací podmnožině:
kde prochází každá cesta z uzlu do uzlu v .

Vlastnost Global Markov je silnější než vlastnost Local Markov, která je zase silnější než vlastnost Pairwise. Výše uvedené tři Markovovy vlastnosti jsou však ekvivalentní pro kladné distribuce (ty, které přiřazují přidruženým proměnným pouze nenulové pravděpodobnosti).

Faktorizace kliky

Protože Markovovu vlastnost libovolného rozdělení pravděpodobnosti lze obtížně stanovit, běžně používanou třídou Markovových náhodných polí jsou ta, která lze faktorizovat podle kliků grafu.

Vzhledem k množině náhodných proměnných nechť je pravděpodobnost konkrétní konfigurace pole v  . To je pravděpodobnost zjištění, že náhodné proměnné nabývají konkrétní hodnoty . Protože jde o množinu, měla by být chápána pravděpodobnost, že bude brána v úvahu společné rozdělení souboru .

Pokud lze tuto hustotu spoje rozložit na kliky :

pak vytvoří Markovovo náhodné pole vzhledem k . Zde je sada klik . Definice je ekvivalentní, pokud jsou použity pouze maximální kliky. Funkce jsou někdy označovány jako potenciály faktorů nebo potenciály kliky . Všimněte si však, že se používá konfliktní terminologie: slovo potenciál je často aplikováno na logaritmus . To je proto, že v statistické mechanice , má přímý výklad jako potenciální energie části konfigurace .  

Některé MRF nefaktorizují: jednoduchý příklad lze sestrojit na cyklu 4 uzlů s některými nekonečnými energiemi, tj. Konfigurace nulových pravděpodobností, i když jedna, vhodněji, umožňuje nekonečným energiím působit na celý graf .

Faktorizace MRF je splněna, pokud je splněna alespoň jedna z následujících podmínek:

Pokud taková faktorizace existuje, je možné sestrojit graf faktorů pro síť.

Exponenciální rodina

Jakékoli pozitivní Markovovo náhodné pole lze zapsat jako exponenciální rodinu v kanonické formě s funkcemi funkcí tak, že distribuci s plným spojem lze zapsat jako

kde notace

je jednoduše bodový produkt přes konfigurace pole a Z je funkce oddílu :

Zde označuje množinu všech možných přiřazení hodnot všem náhodným proměnným sítě. Obvykle jsou funkce funkcí definovány tak, že jsou indikátory konfigurace kliky, tj. Pokud odpovídá i -té možné konfiguraci k -té kliky a 0 jinak. Tento model je ekvivalentní výše uvedenému modelu faktorizace kliky, pokud je mohutnost kliky, a váha prvku odpovídá logaritmu odpovídajícího faktoru kliky, tj . Kde je i -ta možná konfigurace k - th klika, tj i tého hodnota v oblasti kliky .

Pravděpodobnost P se často nazývá Gibbsova míra. Tento výraz pole Markov jako logistický model je možné pouze tehdy, když jsou všechny klika faktory jsou nenulové, tj , jestliže žádný z prvků je přiřazena pravděpodobnost 0. To umožňuje techniky z maticové algebře, které mají být použity, například , že čím stopa matice je log determinantu , přičemž maticová reprezentace grafu vychází z matice dopadu grafu .

Význam funkce rozdělení Z je v tom, že mnoho konceptů ze statistické mechaniky , jako je entropie , přímo zobecňuje na případ Markovových sítí, a lze tak dosáhnout intuitivního porozumění. Funkce rozdělení navíc umožňuje použít na řešení problému variační metody : k jedné nebo více náhodným proměnným lze připojit hnací sílu a prozkoumat reakci sítě v reakci na tuto poruchu . Například lze do funkce rozdělení přidat řídící výraz J v pro každý vrchol v grafu, abychom získali:

Formální diferenciace s ohledem na J v dává očekávanou hodnotu náhodné proměnné X v související s vrcholem v :

Korelační funkce se počítají podobně; dvoubodová korelace je:

Bohužel, i když je pravděpodobnost logistické sítě Markov konvexní, hodnocení pravděpodobnosti nebo gradientu pravděpodobnosti modelu vyžaduje odvození v modelu, který je obecně výpočetně neproveditelný (viz 'Inference' níže).

Příklady

Gaussian

Vícerozměrného normálního rozdělení tvoří nepravidelnou pole Markov vzhledem ke grafu v případě, že chybějící okraje odpovídají nul na přesné matice (inverzní kovarianční matice ):

takové to

Odvození

Stejně jako v Bayesovské síti lze vypočítat podmíněné rozdělení sady daných hodnot uzlů do jiné sady uzlů v náhodném poli Markov součtem všech možných přiřazení k ; tomu se říká přesný závěr . Přesný závěr je však problémem #P-kompletní , a tedy v obecném případě výpočetně neřešitelný. Aproximační techniky, jako je Markovský řetězec Monte Carlo a šíření víry v propagaci, jsou v praxi často proveditelnější. Některé konkrétní podtřídy MRF, jako jsou stromy (viz strom Chow – Liu ), mají algoritmy odvození polynomiálního času; objevování takových podtříd je aktivním výzkumným tématem. Existují také podtřídy MRF, které umožňují efektivní odvození MAP nebo nejpravděpodobnější přiřazení; jejich příklady zahrnují asociativní sítě. Další zajímavou podtřídou je rozložitelné modely (když je graf akordický ): s uzavřenou formou pro MLE je možné objevit konzistentní strukturu pro stovky proměnných.

Podmíněná náhodná pole

Jedna pozoruhodná varianta Markovova náhodného pole je podmíněné náhodné pole , ve kterém každá náhodná proměnná může být také podmíněna sadou globálních pozorování . V tomto modelu je každá funkce mapováním všech přiřazení k klice k a pozorování nezáporných reálných čísel. Tato forma Markovovy sítě může být vhodnější pro produkci diskriminačních klasifikátorů , které nemodelují distribuci na základě pozorování. CRF navrhli John D. Lafferty , Andrew McCallum a Fernando CN Pereira v roce 2001.

Různé aplikace

Markovská náhodná pole nacházejí uplatnění v různých oblastech, od počítačové grafiky po počítačové vidění, strojové učení nebo výpočetní biologii . MRF se používají při zpracování obrázků ke generování textur, protože je lze použít ke generování flexibilních a stochastických obrazových modelů. V modelování obrazu je úkolem najít vhodné rozložení intenzity daného obrazu, kde vhodnost závisí na druhu úkolu a MRF jsou dostatečně flexibilní, aby mohly být použity pro syntézu obrazu a textury, kompresi a obnovu obrazu, segmentaci obrazu , 3D obraz odvození z 2D obrázků, registrace obrazu , syntéza textur , super rozlišení , stereo shoda a získávání informací . Mohou být použity k řešení různých problémů s počítačovým viděním, které mohou představovat problémy s minimalizací energie nebo problémy, kde je třeba rozlišovat různé oblasti pomocí sady diskriminačních funkcí v rámci Markovova náhodného pole k předpovědi kategorie regionu. Markovská náhodná pole byla zobecněním Isingova modelu a od té doby byla široce používána v kombinatorických optimalizacích a sítích.

Viz také

Reference