Campo casuale di Markov

Un campo casuale (o aleatorio) di Markov (in inglese Markov random field, MRF), detto anche rete di Markov, è un insieme di variabili casuali che verificano la proprietà di Markov rispetto a un grafo non orientato che rappresenta le dipendenze fra tali variabili. In altre parole, un campo aleatorio si dice markoviano se verifica la proprietà di Markov (in una delle sue forme). L'idea trae origine dalla fisica e in particolare dal modello Sherrington-Kirkpatrick^[1].

Un esempio di MRF. Ogni arco rappresenta una dipendenza. In questo esempio: A dipende da B e D. B dipende da A e D. D dipende da A, B ed E. E dipende da D e C. C dipende da E.

Una rete di Markov è simile a una rete bayesiana in quanto modelli grafici per rappresentare le dipendenze fra variabili; la differenza sta nel fatto che le reti bayesiane sono grafi orientati e aciclici, mentre le reti di Markov non sono orientate e possono essere cicliche. Pertanto, una rete di Markov può rappresentare dipendenze che una rete bayesiana non può rappresentare; d'altra parte, una rete di Markov non può rappresentare certe dipendenze che una rete bayesiana può rappresentare (come, ad esempio, le dipendenze indotte). Inoltre, il grafo relativo a una rete di Markov può essere finito o infinito.

Il prototipo di rete di Markov è il modello di Ising: difatti il concetto di MRF è stato introdotto proprio come generalizzazione di tale modello^[2]. Nel campo dell'intelligenza artificiale, un MRF viene utilizzato come modello di riferimento per diversi problemi di medio-basso livello nell'elaborazione delle immagini e nella visione artificiale^[3].

Definizione

Dato un grafo non orientato ${\displaystyle G=(V,E)}$, un insieme di variabili casuali ${\displaystyle X=(X_{v})_{v\in V}}$ indicizzato da ${\displaystyle V}$ costituisce un Markov random field rispetto a ${\displaystyle G}$ se esse soddisfano una delle seguenti proprietà di Markov locali:

Proprietà di coppia: due variabili non adiacenti sono condizionatamente indipendenti date tutte le altre variabili

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\setminus \{u,v\}}}$

Proprietà locale: una variabile è condizionatamente indipendente da tutte le altre variabili dati i suoi vicini

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {N} [v]}\mid X_{\operatorname {N} (v)}}$

dove ${\textstyle \operatorname {N} (v)}$ è l'insieme dei vicini di ${\displaystyle v}$ e ${\displaystyle \operatorname {N} [v]=v\cup \operatorname {N} (v)}$ è il vicinato chiuso di ${\displaystyle v}$, ossia comprende ${\displaystyle v}$.

Proprietà globale: due sottoinsiemi di variabili sono condizionatamente indipendenti dato un sottoinsieme di separazione

${\displaystyle X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}}$

dove ogni percorso da un nodo in ${\displaystyle A}$ a un nodo in ${\displaystyle B}$ passa attraverso ${\displaystyle S}$.

La proprietà globale è più forte della proprietà locale che, a sua volta, è più forte di quella di coppia^[4]. Ad ogni buon conto, le tre proprietà di Markov sopra menzionate risultano equivalenti nel caso di distribuzioni positive^[5] (quelle che assegnano alle variabili solo probabilità non nulle).

La relazione fra le tre proprietà di Markov è più chiara nella formulazione seguente:

• prop. di coppia: per ogni coppia ${\displaystyle i,j\in V}$ non uguali o adiacenti, ${\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}}$;
• prop. locale: per ogni ${\displaystyle i\in V}$ e ${\displaystyle J\subset V}$ non contenente o adiacente a ${\displaystyle i}$, ${\displaystyle X_{i}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (\{i\}\cup J)}}$;
• prop. globale: per ogni coppia ${\displaystyle I,J\subset V}$ non intersecanti o adiacenti, ${\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}}$.

Fattorizzazione in cricche

Dato che può risultare difficile stabilire se le proprietà di Markov siano verificate da un'arbitraria distribuzione di probabilità, una classe di MRF comunemente utilizzata è quella delle reti che possono essere fattorizzate in base alle cricche del grafo.

Dato un insieme di variabili casuali ${\displaystyle X=(X_{v})_{v\in V}}$, sia ${\displaystyle P(X=x)}$ la probabilità di una particolare configurazione ${\displaystyle x}$ del campo ${\displaystyle X}$, cioè la probabilità che le variabili casuali in ${\displaystyle X}$ assumano lo specifico valore in ${\displaystyle x}$. Essendo ${\displaystyle X}$ un insieme, la probabilità di ${\displaystyle x}$ deve essere intesa come riferita alla distribuzione congiunta delle varie ${\displaystyle X_{v}}$.

Se tale congiunta può essere fattorizzata sulle cricche di ${\displaystyle G}$, ossia

${\displaystyle P(X=x)=\prod _{C\in \operatorname {cl} (G)}\varphi _{C}(x_{C})}$

allora ${\displaystyle X}$ forma un MRF rispetto a ${\displaystyle G}$. Nella formula, ${\displaystyle \operatorname {cl} (G)}$ denota l'insieme delle cricche di ${\displaystyle G}$. La definizione può essere scritta in modo equivalente considerando solo le cricche massimali. Le funzioni ${\displaystyle \varphi _{C}}$ sono talvolta chiamate potenziali di fattori o potenziali di cricca^{[note 1]}.

Alcuni MRF non sono fattorizzabili ^{[6][note 2]}. Un MRF può essere fattorizzato se è soddisfatta almeno una delle seguenti condizioni:

• la densità è positiva (per il teorema di Hammersley-Clifford)
• il grafo associato è cordale (per l'equivalenza con una rete bayesiana)

Quando esiste una tale fattorizzazione, è possibile costruire il cosiddetto grafo con fattori per la rete.

Famiglia esponenziale

Qualsiasi MRF positivo può essere scritto come famiglia esponenziale in forma canonica, con funzioni caratteristiche ${\displaystyle f_{k}}$, in modo tale che la distribuzione congiunta completa possa essere scritta come

${\displaystyle P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)}$

dove la notazione

${\displaystyle w_{k}^{\top }f_{k}(x_{\{k\}})=\sum _{i=1}^{N_{k}}w_{k,i}\cdot f_{k,i}(x_{\{k\}})}$

è semplicemente un prodotto scalare sulle configurazioni del campo e ${\displaystyle Z}$ è la funzione di partizione:

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

Qui, ${\displaystyle {\mathcal {X}}}$ indica l'insieme di tutte le possibili assegnazioni di valori a tutte le variabili casuali della rete. Di solito, le funzioni ${\displaystyle f_{k,i}}$ sono definite in modo tale da rappresentare indicatori della configurazione della cricca, ossia ${\displaystyle f_{k,i}(x_{\{k\}})=1}$ se ${\displaystyle x_{\{k\}}}$ corrisponde all'${\displaystyle i}$-esima configurazione possibile della ${\displaystyle k}$-esima cricca ed è nulla altrimenti. Questo modello è equivalente al modello di fattorizzazione in cricche sopra indicato, se ${\displaystyle N_{k}=|\operatorname {dom} (C_{k})|}$ è la cardinalità della cricca e il peso di una ${\displaystyle f_{k,i}}$ corrisponde al logaritmo del fattore di cricca corrispondente, cioè ${\displaystyle w_{k,i}=\log \varphi (c_{k,i})}$, dove ${\displaystyle c_{k,i}}$ denota l'${\displaystyle i}$-esima configurazione possibile della ${\displaystyle k}$-esima cricca, cioè l'${\displaystyle i}$-esimo valore nel dominio della cricca ${\displaystyle C_{k}}$.

La probabilità ${\displaystyle P}$ viene spesso chiamata misura di Gibbs. La formulazione di un MRF come modello logistico è possibile solo se tutti i fattori di cricca sono non nulli, cioè se a nessuno degli elementi di ${\displaystyle {\mathcal {X}}}$ viene assegnata una probabilità nulla. Ciò consente l'uso di operatori dell'algebra matriciale, ad esempio la traccia per ottenere il logaritmo del determinante di una matrice, data una rappresentazione matriciale del grafo, ad esempio la sua matrice di incidenza.

L'importanza della funzione di partizione ${\displaystyle Z}$ risiede nel fatto che molte nozioni di meccanica statistica, come l'entropia, possono essere generalizzate direttamente al caso delle reti di Markov, favorendone così la loro comprensione a livello intuitivo. Inoltre, la funzione di partizione consente di applicare metodi variazionali nella soluzione del problema di inferenza: è possibile associare una forza motrice a una o più variabili casuali ed esplorare la reazione della rete in risposta a questa perturbazione. Quindi, ad esempio, per ogni nodo ${\displaystyle v}$ del grafo, si può aggiungere un termine guida ${\displaystyle J_{v}}$ alla funzione di partizione ottenendo così:

${\displaystyle Z[J]=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})+\sum _{v}J_{v}x_{v}\right)}$

Formalmente, differenziando rispetto a ${\displaystyle J_{v}}$ si ottiene il valore atteso della variabile casuale ${\displaystyle x_{v}}$ associata al vertice ${\displaystyle v}$:

${\displaystyle E[X_{v}]={\frac {1}{Z}}\left.{\frac {\partial Z[J]}{\partial J_{v}}}\right|_{J_{v}=0}.}$

Le funzioni di correlazione vengono calcolate allo stesso modo; la correlazione di due punti è:

${\displaystyle C[X_{u},X_{v}]={\frac {1}{Z}}\left.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\,\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}.}$

Sfortunatamente, sebbene la verosimiglianza di una rete logistica di Markov sia convessa, la sua valutazione, o quella del suo gradiente, richiede di fare inferenza sul modello, il che risulta generalmente computazionalmente intrattabile (si veda la sezione "Inferenza" nel seguito).

Esempi

Caso gaussiano

Una distribuzione normale multivariata forma un MRF rispetto a un grafo ${\displaystyle G=(V,E)}$ se gli archi mancanti corrispondono a zeri nella matrice di precisione:

${\displaystyle X=(X_{v})_{v\in V}\sim {\mathcal {N}}({\boldsymbol {\mu }},\Sigma )}$

tale che

${\displaystyle (\Sigma ^{-1})_{uv}=0\quad {\text{iff}}\quad \{u,v\}\notin E.}$ ^[7]

Inferenza

Come per una rete bayesiana, si può calcolare la distribuzione condizionale di un insieme di nodi ${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$ dati i valori assegnati a un altro insieme di nodi ${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$ nel MRF sommando su tutte le possibili assegnazioni a ${\displaystyle u\notin V',W'}$; questo procedimento è una forma di inferenza esatta. Tuttavia, l'inferenza esatta è un problema #P-completo e quindi computazionalmente intrattabile in generale. Nella pratica, tecniche di approssimazione come il MCMC e la belief propagation ciclica risultano spesso più trattabili.

Per alcune sottoclassi particolari di MRF, come quelle associate ad alberi, esistono algoritmi di inferenza polinomiali (in tempo); la scoperta di tali sottoclassi è un attivo settore di ricerca. Esistono anche sottoclassi di MRF per le quali esistono metodi efficienti d'inferenza MAP o dell'assegnazione più probabile; esempi di questo tipo di modelli comprendono le reti associative^[8][9]. Un'altra sottoclasse interessante è quella dei modelli decomponibili (quando il grafo è cordale): dato che ammettono soluzioni in forma chiusa per la stima di massima verosimiglianza, è possibile scoprire una struttura coerente anche per modelli con centinaia di variabili^[10].