Vai al contenuto

Campo casuale di Markov

Da Wikipedia, l'enciclopedia libera.
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.

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].

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].

Dato un grafo non orientato , un insieme di variabili casuali indicizzato da costituisce un Markov random field rispetto a 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
Proprietà locale: una variabile è condizionatamente indipendente da tutte le altre variabili dati i suoi vicini
dove è l'insieme dei vicini di e è il vicinato chiuso di , ossia comprende .
Proprietà globale: due sottoinsiemi di variabili sono condizionatamente indipendenti dato un sottoinsieme di separazione
dove ogni percorso da un nodo in a un nodo in passa attraverso .

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 non uguali o adiacenti, ;
  • prop. locale: per ogni e non contenente o adiacente a , ;
  • prop. globale: per ogni coppia non intersecanti o adiacenti, .

Fattorizzazione in cricche

[modifica | modifica wikitesto]

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 , sia la probabilità di una particolare configurazione del campo , cioè la probabilità che le variabili casuali in assumano lo specifico valore in . Essendo un insieme, la probabilità di deve essere intesa come riferita alla distribuzione congiunta delle varie .

Se tale congiunta può essere fattorizzata sulle cricche di , ossia

allora forma un MRF rispetto a . Nella formula, denota l'insieme delle cricche di . La definizione può essere scritta in modo equivalente considerando solo le cricche massimali. Le funzioni 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:

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

Famiglia esponenziale

[modifica | modifica wikitesto]

Qualsiasi MRF positivo può essere scritto come famiglia esponenziale in forma canonica, con funzioni caratteristiche , in modo tale che la distribuzione congiunta completa possa essere scritta come

dove la notazione

è semplicemente un prodotto scalare sulle configurazioni del campo e è la funzione di partizione:

Qui, indica l'insieme di tutte le possibili assegnazioni di valori a tutte le variabili casuali della rete. Di solito, le funzioni sono definite in modo tale da rappresentare indicatori della configurazione della cricca, ossia se corrisponde all'-esima configurazione possibile della -esima cricca ed è nulla altrimenti. Questo modello è equivalente al modello di fattorizzazione in cricche sopra indicato, se è la cardinalità della cricca e il peso di una corrisponde al logaritmo del fattore di cricca corrispondente, cioè , dove denota l'-esima configurazione possibile della -esima cricca, cioè l'-esimo valore nel dominio della cricca .

La probabilità 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 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 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 del grafo, si può aggiungere un termine guida alla funzione di partizione ottenendo così:

Formalmente, differenziando rispetto a si ottiene il valore atteso della variabile casuale associata al vertice :

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

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).

Caso gaussiano

[modifica | modifica wikitesto]

Una distribuzione normale multivariata forma un MRF rispetto a un grafo se gli archi mancanti corrispondono a zeri nella matrice di precisione:

tale che

[7]

Come per una rete bayesiana, si può calcolare la distribuzione condizionale di un insieme di nodi dati i valori assegnati a un altro insieme di nodi nel MRF sommando su tutte le possibili assegnazioni a ; 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].

Esplicative
  1. ^ Questa terminologia può risultare un po' problematica in quanto il termine potenziale è spesso associato al logaritmo di e, in meccanica statistica, ha un'interpretazione diretta come energia potenziale di una configurazione .
  2. ^ Un semplice esempio può essere quello di un grafo con un ciclo di 4 nodi con alcune delle energie infinite, ossia configurazioni con probabilità nulla.
Documentali
  1. ^ (EN) Sherrington, David; Kirkpatrick, Scott, Solvable Model of a Spin-Glass, in Physical Review Letters, vol. 35, n. 35, 1975, pp. 1792-1796, Bibcode:1975PhRvL..35.1792S, DOI:10.1103/PhysRevLett.35.1792.
  2. ^ (EN) Ross Kindermann e J. Laurie Snell, Markov Random Fields and Their Applications (PDF), American Mathematical Society, 1980, ISBN 978-0-8218-5001-5. URL consultato il 17 agosto 2024 (archiviato dall'url originale il 10 agosto 2017).
  3. ^ (EN) S. Z. Li, Markov Random Field Modeling in Image Analysis, Springer, 2009, ISBN 9781848002791.
  4. ^ (EN) Steffen Lauritzen, Graphical models, Clarendon Press, 1996, p. 33, ISBN 978-0198522195.
  5. ^ (EN) Daphne Koller e Nir Friedman, Probabilistic Graphical Models, MIT Press, 2009, p. 114-122, ISBN 9780262013192.
  6. ^ (EN) John Moussouris, Gibbs and Markov random systems with constraints, in Journal of Statistical Physics, vol. 10, n. 1, 1974, pp. 11–33, Bibcode:1974JSP....10...11M, DOI:10.1007/BF01011714, MR 0432132.
  7. ^ (EN) Håvard Rue e Leonhard Held, Gaussian Markov random fields: theory and applications, CRC Press, 2005, ISBN 978-1-58488-432-3.
  8. ^ (EN) Benjamin Taskar, Vassil Chatalbashev e Daphne Koller, Learning associative Markov networks, Proceedings of the Twenty-First International Conference on Machine Learning (ICML 2004), Banff, Alberta, Canada, July 4-8, 2004, ACM International Conference Proceeding Series, vol. 69, Brodley, C.E., 2004, p. 102, DOI:10.1145/1015330.1015444, ISBN 978-1581138283..
  9. ^ (EN) Duchi, John C.; Tarlow, Daniel, Elidan, Gal; Koller, Daphne, Using Combinatorial Optimization within Max-Product Belief Propagation, a cura di Schölkopf, B.; et al., Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, Advances in Neural Information Processing Systems, vol. 19, MIT Press, 2006, pp. 369–376..
  10. ^ (EN) Petitjean, F.; Webb, G.I.; Nicholson, A.E., Scaling log-linear analysis to high-dimensional data (PDF), International Conference on Data Mining. Dallas, TX, USA, 2013.

Voci correlate

[modifica | modifica wikitesto]