Markovin verkko

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2. helmikuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Markovin verkko , Markovin satunnaiskenttä tai suuntaamaton graafimalli on graafimalli, jossa satunnaismuuttujien joukolla on suuntaamattoman graafin kuvaama Markov -ominaisuus . Markovin verkko eroaa toisesta graafimallista, Bayesin verkosta , siinä, että se esittää satunnaismuuttujien välisiä riippuvuuksia. Se voi ilmaista joitain riippuvuuksia, joita Bayesin verkko ei voi ilmaista (esimerkiksi sykliset riippuvuudet); toisaalta hän ei voi ilmaista joitain muita. Markovin verkon prototyyppi oli Isingin malli materiaalin magnetisoinnista tilastollinen fysiikka : Markovin verkko on esitetty tämän mallin yleistyksenä . [yksi]

Määritelmä

Kun suuntaamaton graafi G = ( V , E ), niin V :llä indeksoitu satunnaismuuttujien joukko ( X v ) v ∈ V muodostaa Markovin satunnaiskentän G :n suhteen, jos ne täyttävät seuraavat vastaavat Markovin ominaisuudet:

Parin ominaisuus : Mikä tahansa kaksi ei-viereistä muuttujaa ovat ehdollisesti riippumattomia, kun otetaan huomioon kaikki muut muuttujat:

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

Paikallinen ominaisuus : muuttuja on ehdollisesti riippumaton kaikista muista arvoista, kun otetaan huomioon sen naapurit:

{\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operaattorinimi {cl} (v)}|X_{\operaattorin nimi {ne} (v)))

missä ne( v ) on V :n naapureiden joukko ja cl( v ) = { v } ∪ ne( v ) on v: n suljettu naapuri . Yleinen ominaisuus : Mikä tahansa kaksi muuttujien osajoukkoa ovat ehdollisesti riippumattomia erottavan osajoukon perusteella:

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

jossa jokainen polku A :n solmusta B :n solmuun kulkee S :n kautta .

Toisin sanoen graafin G sanotaan olevan Markovin satunnaiskenttä suhteessa yhteishajautuneisiin todennäköisyyksiin P ( X = x ) satunnaismuuttujien joukossa X silloin ja vain, jos graafin G jakaminen edellyttää ehdollista riippumattomuutta: Jos kaksi solmua ja ovat jaettu G :ssä sen jälkeen, kun se on poistettu G :stä solmujen Z joukosta , niin P ( x = x ) on vakuutettava, että ja ovat ehdollisesti riippumattomia Z : tä vastaavien satunnaismuuttujien perusteella . Jos tämä ehto täyttyy, G :n sanotaan olevan riippumaton kartta (tai I-kartta) todennäköisyysjakaumasta . $X_{i}$ $X_{j}$

Monet määritelmät edellyttävät myös, että G on minimaalinen I-kartta, eli I-kartta, josta yksi reuna poistetaan, se lakkaa olemasta I-kartta. (Tämä on kohtuullinen vaatimus, koska se johtaa kompakteimpaan esitykseen, joka sisältää mahdollisimman vähän riippuvuuksia. Huomaa, että täydellinen graafi on triviaali I-kartta.) Siinä tapauksessa, että G ei ole vain I-kartta (että on, ei edusta riippumattomuuksia, joita ei ole määritelty P :ssä ( X = x )), mutta ei myöskään edusta riippuvuuksia, joita ei ole määritelty P :ssä ( X = x ), G : tä kutsutaan täydelliseksi kartaksi (täydellinen kartta) P ( X = x ). Se edustaa P :n määrittelemää riippumattomuuksien joukkoa ( X = x ).

Klikkien faktorointi

Koska mielivaltaisen todennäköisyysjakauman Markovin ominaisuuksia on vaikea määrittää, on olemassa laajalti käytetty Markovin satunnaiskenttien luokka, joka voidaan jakaa graafin klikkausten mukaan. Satunnaismuuttujien joukko X = ( X v ) v ∈ V , joiden liitostiheys voidaan kertoa klikeillä G :

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

muodostaa Markovin satunnaiskentän G :n suhteen , missä cl( G ) on G :n klikkien joukko (määritelmä on ekvivalentti, jos käytetään vain maksimaalisia klikkeja). Funktioita φ C kutsutaan usein tekijäpotentiaaliksi tai klikkipotentiaaliksi. Vaikka on MRF:itä, jotka eivät hajoa (yksinkertainen esimerkki voidaan rakentaa 4 solmun silmukalle [2] ), joissakin tapauksissa niiden voidaan osoittaa olevan vastaavissa tiloissa:

jos tiheys on positiivinen
jos kuvaaja on harmoninen

Kun tällainen hajautus on olemassa, verkolle voidaan rakentaa tekijägraafi.

Esimerkki

Logistinen malli

Markovin satunnaiskentän logistinen malli, joka käyttää funktiota täydellisen yhteisjakauman funktiona, voidaan kirjoittaa muodossa $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\)))\oikea)

jakelutoiminnolla

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

missä on joukko kaikkien verkkojen satunnaismuuttujien arvojen mahdollisia jakaumia. ${\mathcal {X}}$

Gaussin Markovin satunnaiskenttä

Markovin satunnaiskentän monimuuttujaisen normaalijakauman muodot graafin G = ( V , E ) suhteen, jos puuttuvat reunat vastaavat nollia tarkkuusmatriisissa (käänteinen kovarianssimatriisi ):

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

[3]

Muistiinpanot

↑ Kindermann, Ross; Snell, J. Laurie. Markovin satunnaiset kentät ja niiden sovellukset . - American Mathematical Society, 1980. - ISBN 0-8218-5001-6 .
↑ Moussouris, John. Gibbsin ja Markovin satunnaisjärjestelmät rajoituksilla // Journal of Statistical Physics : päiväkirja. - 1974. - Voi. 10 , ei. 1 . - s. 11-33 . - doi : 10.1007/BF01011714 .
↑ Rue, Havard; Pidetty, Leonhard. Gaussin Markovin satunnaiskentät : teoria ja sovellukset . - CRC Press , 2005. - ISBN 1584884320 .

Piirrä todennäköisyysmallit
Bayesin verkko Causal Bayesian Network Markovin verkko Piilotettu Markovin malli

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokittelu ongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-verkko Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG