Markov hálózat

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. február 2-án felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A Markov - hálózat , Markov véletlenmező vagy irányítatlan gráfmodell olyan gráfmodell , amelyben a valószínűségi változók halmaza rendelkezik az irányítatlan gráf által leírt Markov - tulajdonsággal . A Markov-hálózat a valószínűségi változók közötti függőségek ábrázolásában különbözik egy másik gráfmodelltől, a Bayes-hálózattól . Kifejezhet néhány függőséget, amelyet a Bayes-hálózat nem tud kifejezni (például ciklikus függőségek); másrészt nem tud másokat kifejezni. A Markov-hálózat prototípusa az anyagmágnesezés Ising-modellje volt a statisztikai fizikában : A Markov-hálózatot ennek a modellnek az általánosításaként mutatták be . [egy]

Definíció

Adott egy irányítatlan G = ( V , E ) gráf, akkor a V -vel indexelt ( X v ) v ∈ V valószínűségi változók halmaza Markov véletlenszerű mezőt alkot G -hez képest, ha kielégítik a következő ekvivalens Markov-tulajdonságokat:

Pár tulajdonság : Bármely két nem szomszédos változó feltételesen független, figyelembe véve az összes többi változót:

X_{u}\perp \!\!\!\perp X_{v}|X_{V\setminus \{u,v\}}\quad {\text{if }}\{u,v\ }\notin E

Lokális tulajdonság : a változó feltételesen független minden más értéktől, a szomszédai alapján:

{\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operátornév {cl} (v)}|X_{\operátornév {ne} (v)))

ahol ne( v ) V szomszédainak halmaza , és cl( v ) = { v } ∪ ne( v ) v zárt környezete . Globális tulajdonság : A változók bármely két részhalmaza feltételesen független, tekintettel az elválasztó részhalmazra:

{\displaystyle X_{A}\perp \!\!\!\perp X_{B}|X_{S))

ahol az A -beli csomóponttól a B -beli csomópontig minden út S - en halad át .

Más szavakkal, egy G gráfról azt mondjuk, hogy egy Markov-féle véletlenszerű mező a P ( X = x ) közös eloszlású valószínűségek tekintetében X valószínűségi változók halmazán, akkor és csak akkor, ha a G gráf felosztása feltételes függetlenséget jelent: Ha két csomópont és G -ben felosztva, miután eltávolítottuk a Z csomópontok G halmazából , akkor P ( x = x ) ezt kell, hogy állítsa, és feltételesen függetlenek a Z -nek megfelelő valószínűségi változók alapján . Ha ez a feltétel teljesül, akkor G -t a valószínűségi eloszlás független leképezésének (vagy I-térképének) nevezzük . $X_{i}$ $X_{j}$

Sok definíció azt is megköveteli, hogy G legyen egy minimális I-térkép, azaz olyan I-térkép, amelyből az egyik élt eltávolítjuk, és megszűnik I-térkép lenni. (Ez egy ésszerű követelmény, mivel ez a lehető legkevesebb függőséget tartalmazó legkompaktabb ábrázoláshoz vezet; vegye figyelembe, hogy a teljes gráf egy triviális I-térkép.) Abban az esetben, ha G nem csak egy I-térkép (azaz az, nem képvisel olyan függetlenségeket, amelyeket nem ad meg P ( X = x )), de nem reprezentálja azokat a függőségeket sem, amelyek nem szerepelnek P -ben ( X = x ), G -t tökéletes térképnek (tökéletes térképnek) nevezzük P ( X = x ). A P -vel meghatározott függetlenségek halmazát reprezentálja ( X = x ).

A klikkek faktorizálása

Mivel egy tetszőleges valószínűségi eloszlás Markov-tulajdonságait nehéz megállapítani, van egy széles körben használt Markov-féle véletlenmező, amely a gráf klikkjei szerint faktorizálható. Az X = ( X v ) v ∈ V valószínűségi változók halmaza, amelyekre az illesztési sűrűség faktorizálható a G klikkeken :

p(x)=\prod _{C\in \operatorname {cl} (G)}\phi _{C}(x_{C})

Markov véletlenszerű mezőt képez G -hez képest , ahol cl( G ) a G klikkjeinek halmaza (a definíció ekvivalens, ha csak maximális klikkeket használunk). A φ C függvényeket gyakran faktorpotenciáloknak vagy klikkpotenciáloknak nevezik. Bár vannak olyan MRF-ek, amelyek nem bomlanak le (egy egyszerű példa 4 csomópontos hurokra építhető [2] ), bizonyos esetekben bizonyíthatóan egyenértékű állapotúak:

ha a sűrűség pozitív
ha a gráf harmonikus

Ha létezik ilyen dekompozíció, létrehozhatunk egy faktorgráfot a hálózathoz.

Példa

Logisztikai modell

A függvényt a teljes együttes eloszlás függvényében használó Markov véletlenmező logisztikai modellje így írható fel $f_{k}$

P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k) \)))\right)={\frac {1}{Z}}\exp \left(\sum _{k}\sum _{i=1}^{N_{k}}w_{k,i} \cdot f_{k,i}(x_{\{k\)))\jobbra)

elosztási funkcióval

Z=\sum _{x\in {\mathcal {X))}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k \)))\jobb)

ahol az összes hálózat valószínűségi változói értékeinek lehetséges eloszlásának halmaza. ${\mathcal {X}}$

Gauss Markov véletlenszerű mező

Egy Markov véletlenmező többváltozós normális eloszlásának formái egy G = ( V , E ) gráfra, ha a hiányzó élek a precíziós mátrixban (inverz kovarianciamátrix ) nulláknak felelnek meg :

X=(X_{v})_{v\in V}\sim {\mathcal {N))({\boldsymbol {\mu )),\Sigma )\qquad {\text{olyan, hogy)) \qquad (\Sigma ^{-1})_{uv}=0\quad {\text{if))\quad \{u,v\}\notin E.

[3]

Jegyzetek

↑ Kindermann, Ross; Snell, J. Laurie. Markov véletlenszerű mezői és alkalmazásaik . - American Mathematical Society, 1980. - ISBN 0-8218-5001-6 .
↑ Moussouris, John. Gibbs és Markov véletlenszerű rendszerek megszorításokkal // Journal of Statistical Physics : folyóirat. - 1974. - 1. évf. 10 , sz. 1 . - P. 11-33 . - doi : 10.1007/BF01011714 .
↑ Rue, Havard; Tartott, Leonhard. Gauss-Markov véletlenszerű mezők : elmélet és alkalmazások . - CRC Press , 2005. - ISBN 1584884320 .

Grafikon valószínűségi modellek
Bayesi hálózat Oksági Bayes-hálózat Markov hálózat Rejtett Markov-modell

Gépi tanulás és adatbányászat
Feladatok	Osztályozási feladat Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellegyüttesek Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-háló Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG