Markov netværk

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 2. februar 2018; checks kræver 8 redigeringer .

Et Markov-netværk , Markov-tilfældigt felt eller urettet grafmodel er en grafmodel, hvor sættet af tilfældige variabler har Markov-egenskaben beskrevet af en urettet graf . Et Markov-netværk adskiller sig fra en anden grafmodel, Bayesian-netværket , i sin repræsentation af afhængigheder mellem tilfældige variable. Det kan udtrykke nogle afhængigheder, som det Bayesianske netværk ikke kan udtrykke (for eksempel cykliske afhængigheder); på den anden side kan hun ikke udtrykke nogle andre. Prototypen på Markov-netværket var Ising-modellen for materialemagnetisering istatistisk fysik : Markov-netværket er blevet præsenteret som en generalisering af denne model. [en]

Definition

Givet en urettet graf G = ( V , E ), danner sættet af stokastiske variable ( X v ) v ∈ V indekseret med V et Markov tilfældigt felt med hensyn til G , hvis de opfylder følgende ækvivalente Markov-egenskaber:

Paregenskab : Alle to ikke-tilstødende variable er betinget uafhængige, givet alle andre variabler:

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

Lokal egenskab : variablen er betinget uafhængig af alle andre værdier, givet dens naboer:

{\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatørnavn {cl} (v)}|X_{\operatørnavn {ne} (v)))

hvor ne( v ) er mængden af naboer til V , og cl( v ) = { v } ∪ ne( v ) er et lukket kvarter til v . Global egenskab : Enhver to delmængder af variable er betinget uafhængige givet den adskillende delmængde:

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

hvor hver vej fra en knude i A til en knude i B går gennem S .

Med andre ord siges en graf G at være et Markov tilfældigt felt med hensyn til fælles distribuerede sandsynligheder P ( X = x ) på et sæt af stokastiske variable X , hvis og kun hvis opdeling af graf G indebærer betinget uafhængighed: Hvis to noder og er opdelt i G efter at være blevet fjernet fra G sæt af noder Z , så skal P ( x = x ) hævde det og er betinget uafhængig givet de stokastiske variabler svarende til Z. Hvis denne betingelse er opfyldt, så siges G at være et uafhængigt kort (eller I-kort) af sandsynlighedsfordelingen . $X_{i}$ $X_{j}$

Mange definitioner kræver også, at G er et minimalt I-kort, det vil sige et I-kort, hvorfra den ene kant er fjernet, det ophører med at være et I-kort. (Dette er et rimeligt krav, da det fører til den mest kompakte repræsentation, der inkluderer så få afhængigheder som muligt; bemærk, at hele grafen er et trivielt I-kort.) I det tilfælde, hvor G ikke kun er et I-kort (det er, repræsenterer ikke uafhængigheder, der ikke er angivet i P ( X = x )), men repræsenterer heller ikke afhængigheder, der ikke er specificeret i P ( X = x ), G kaldes et perfekt kort (perfekt kort) P ( X = x ). Det repræsenterer mængden af uafhængigheder specificeret af P ( X = x ).

Faktorisering af kliker

Da Markov-egenskaberne for en vilkårlig sandsynlighedsfordeling er svære at fastslå, er der en meget brugt klasse af Markov-tilfældige felter, der kan faktoriseres i henhold til grafens kliker. Sættet af stokastiske variable X = ( X v ) v ∈ V , for hvilke ledtætheden kan faktoriseres på kliker G :

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

danner et Markov tilfældigt felt med hensyn til G , hvor cl( G ) er mængden af kliker af G (definitionen er ækvivalent, hvis der kun bruges maksimale kliker). Funktionerne φ C kaldes ofte faktorpotentialer eller klikpotentialer. Selvom der er MRF'er, der ikke nedbrydes (et simpelt eksempel kan bygges på en 4 node loop [2] ), kan de i nogle tilfælde bevises at være i ækvivalente tilstande:

hvis tætheden er positiv
hvis grafen er harmonisk

Når en sådan nedbrydning eksisterer, kan man konstruere en faktorgraf for netværket.

Eksempel

Logistisk model

Den logistiske model af et Markov tilfældigt felt, der bruger funktionen som en funktion af den komplette fælles fordeling, kan skrives som $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\)))\right)

med fordelingsfunktion

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

hvor er sættet af mulige distributioner af værdier af tilfældige variabler for alle netværk. ${\mathcal {X}}$

Gaussisk Markov tilfældigt felt

Former af den multivariate normalfordeling af et Markov tilfældigt felt i forhold til en graf G = ( V , E ), hvis de manglende kanter svarer til nuller i præcisionsmatricen (invers kovariansmatrix ):

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

[3]

Noter

↑ Kindermann, Ross; Snell, J. Laurie. Markov tilfældige felter og deres applikationer . - American Mathematical Society, 1980. - ISBN 0-8218-5001-6 .
↑ Moussouris, John. Gibbs og Markov tilfældige systemer med begrænsninger // Journal of Statistical Physics : journal. - 1974. - Bd. 10 , nej. 1 . - S. 11-33 . - doi : 10.1007/BF01011714 .
↑ Rue, Havard; Holdt, Leonhard. Gaussiske Markov tilfældige felter : teori og anvendelser . - CRC Press , 2005. - ISBN 1584884320 .

Grafer sandsynlighedsmodeller
Bayesiansk netværk Kausalt Bayesian Network Markov netværk Skjult Markov-model

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG