Rețeaua Markov

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 februarie 2018; verificările necesită 8 modificări .

O rețea Markov , un câmp aleator Markov sau un model de grafic nedirecționat este un model de grafic în care setul de variabile aleatoare are proprietatea Markov descrisă de un grafic nedirecționat . O rețea Markov diferă de un alt model grafic, rețeaua Bayesiană , prin reprezentarea dependențelor dintre variabilele aleatoare. Poate exprima unele dependențe pe care rețeaua bayesiană nu le poate exprima (de exemplu, dependențe ciclice); pe de altă parte, ea nu poate exprima unele altele. Prototipul rețelei Markov a fost modelul Ising al magnetizării materialelor în fizica statistică : Rețeaua Markov a fost prezentată ca o generalizare a acestui model. [unu]

Definiție

Având în vedere un grafic nedirecționat G = ( V , E ), atunci mulțimea de variabile aleatoare ( X v ) v ∈ V indexate de V formează un câmp aleator Markov în raport cu G dacă satisfac următoarele proprietăți Markov echivalente:

Proprietatea perechii : oricare două variabile neadiacente sunt independente condiționat, având în vedere toate celelalte variabile:

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

Proprietate locală : variabila este independentă condiționat de toate celelalte valori, având în vedere vecinii săi:

X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {cl} (v)}|X_{\operatorname {ne} (v))

unde ne( v ) este mulțimea vecinilor lui V , iar cl( v ) = { v } ∪ ne( v ) este o vecinătate închisă a lui v . Proprietate globală : oricare două subseturi de variabile sunt independente condiționat, având în vedere submulțimea de separare:

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

unde fiecare cale de la un nod din A la un nod din B trece prin S .

Cu alte cuvinte, se spune că un grafic G este un câmp aleator Markov în raport cu probabilitățile distribuite comune P ( X = x ) pe un set de variabile aleatoare X dacă și numai dacă împărțirea graficului G implică independență condiționată: Dacă două noduri și sunt împărțit în G după ce a fost îndepărtat din G set de noduri Z , atunci P ( x = x ) trebuie să afirme că și sunt independenți condiționat având în vedere variabilele aleatoare corespunzătoare lui Z. Dacă această condiție este îndeplinită, atunci se spune că G este o hartă independentă (sau I-hartă) a distribuției de probabilitate . $X_{i}$ $X_{j}$

Multe definiții necesită, de asemenea, ca G să fie o hartă I minimă, adică o hartă I din care o margine este îndepărtată, încetează să mai fie o hartă I. (Aceasta este o cerință rezonabilă, deoarece duce la cea mai compactă reprezentare care include cât mai puține dependențe posibil; rețineți că graficul complet este o hartă I trivială.) În cazul în care G nu este doar o hartă I (aceasta este, nu reprezintă independențe care nu sunt specificate în P ( X = x )), dar nici nu reprezintă dependențe care nu sunt specificate în P ( X = x ), G se numește o hartă perfectă (hartă perfectă) P ( X = x ). Reprezintă mulțimea de independențe specificate de P ( X = x ).

Factorizarea clicurilor

Deoarece proprietățile Markov ale unei distribuții de probabilitate arbitrare sunt dificil de stabilit, există o clasă larg utilizată de câmpuri aleatoare Markov care pot fi factorizate în funcție de clicurile graficului. Mulțimea variabilelor aleatoare X = ( X v ) v ∈ V pentru care densitatea îmbinării poate fi factorizată pe clicurile G :

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

formează un câmp aleator Markov în raport cu G , unde cl( G ) este mulțimea de clicuri ale lui G (definiția este echivalentă dacă sunt utilizate numai clicuri maxime). Funcțiile φ C sunt adesea numite potențiale factoriale sau potențiale de clică. Deși există MRF-uri care nu se descompun (un exemplu simplu poate fi construit pe o buclă cu 4 noduri [2] ), în unele cazuri se poate dovedi a fi în stări echivalente:

dacă densitatea este pozitivă
dacă graficul este armonic

Când există o astfel de descompunere, se poate construi un grafic al factorilor pentru rețea.

Exemplu

Model logistic

Modelul logistic al unui câmp aleator Markov folosind funcția ca o funcție a distribuției comune complete poate fi scris ca $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)

cu functie de distributie

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

unde este setul de distribuții posibile de valori ale variabilelor aleatoare ale tuturor rețelelor. ${\mathcal {X}}$

Câmp aleatoriu lui Gaussian Markov

Forme ale distribuției normale multivariate a unui câmp aleator Markov în raport cu un grafic G = ( V , E ) dacă muchiile lipsă corespund cu zerouri în matricea de precizie (matricea de covarianță inversă ):

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

[3]

Note

↑ Kindermann, Ross; Snell, J. Laurie. Câmpurile aleatoare Markov și aplicațiile lor . - Societatea Americană de Matematică, 1980. - ISBN 0-8218-5001-6 .
↑ Moussouris, John. Sisteme aleatoare Gibbs și Markov cu constrângeri // Journal of Statistical Physics : jurnal. - 1974. - Vol. 10 , nr. 1 . - P. 11-33 . - doi : 10.1007/BF01011714 .
↑ Rue, Havard; Amânat, Leonhard. Câmpuri aleatoare ale lui Gaussian Markov : teorie și aplicații . - CRC Press , 2005. - ISBN 1584884320 .

Modele grafice probabilistice
Rețeaua bayesiană Rețeaua Bayesiană cauzală Rețeaua Markov Modelul Markov ascuns

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbare medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG