Conditional random field

I Conditional Random Field (CRF, campi aleatori condizionati) sono una classe di metodi di modellazione statistica spesso utilizzati nel riconoscimento di pattern e nell'apprendimento automatico anche per predizioni strutturate. Mentre un generico classificatore predice un'etichetta associata a ciascun campione senza considerare i campioni "vicini", un CRF può tenere conto anche del contesto nel quale si trova. A tale scopo, le predizioni sono basate su un modello grafico che rappresenta la presenza di dipendenze tra le variabili aleatorie che rappresentano le etichette di ciascuno di essi. Il tipo di modello utilizzato dipende dall'applicazione. Ad esempio, nell'elaborazione del linguaggio naturale sono diffusi i CRF "a catena lineare", nei quali ogni variabile dipende solo dai suoi vicini immediati. Nell'elaborazione delle immagini, il modello grafico in genere collega le posizioni a posizioni vicine (e/o simili) per garantire che ricevano predizioni simili.

Vi sono molteplici altri esempi di applicazione dei CRF, quali: l'etichettatura o analisi di dati sequenziali per l'elaborazione del linguaggio naturale o di sequenze biologiche, il POS tagging, l'analisi sintattica superficiale, il riconoscimento di entità, la ricerca di regioni funzionali critiche dei peptidi in genetica, il riconoscimento di oggetti e la segmentazione di immagini nella visione artificiale.

Descrizione

Formalmente, i CRF rappresentano un tipo di modello grafico probabilistico discriminativo non orientato.

Lafferty, McCallum e Pereira definiscono un CRF sulle osservazioni ${\boldsymbol {X}}$ e le variabili casuali ${\boldsymbol {Y}}$ (di output) come segue:

Sia $G=(V,E)$ un grafo tale che ${\boldsymbol {Y}}=({\boldsymbol {Y}}_{v})_{v\in V}$, in modo che ${\boldsymbol {Y}}$ sia indicizzato dai vertici (nodi) di $G$.

$({\boldsymbol {X}},{\boldsymbol {Y}})$ è un conditional random field se ogni variabile ${\boldsymbol {Y}}_{v}$, condizionata su ${\boldsymbol {X}}$, gode della proprietà di Markov rispetto al grafo, ossia se la sua probabilità dipende solo dai suoi vicini in $G$:

$P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\neq v\})=P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\sim v\})$

dove ${\mathit {w}}\sim v$ denota il fatto che $w$ e $v$ sono vicini in $G$.

Quindi un CRF è un modello grafico non orientato i cui nodi possono essere separati esattamente in due insiemi disgiunti ${\boldsymbol {X}}$ e ${\boldsymbol {Y}}$, comprendenti, rispettivamente, le variabili osservate e quelle di output; ne discende un modello $p({\boldsymbol {Y}}|{\boldsymbol {X}})$ della distribuzione condizionata.

Inferenza

Per grafi arbitrari, il problema dell'inferenza esatta nei CRF risulta intrattabile. Difatti, il problema di inferenza su CRF è fondamentalmente è lo stesso che risulta dall'uso di un campo casuale di Markov valendo per entrambi le stesse argomentazioni. Tuttavia, esistono casi speciali per i quali è possibile l'inferenza esatta:

• se il grafo è una catena o un albero, gli algoritmi a passaggio di messaggi (message passing) forniscono soluzioni esatte. Gli algoritmi utilizzati in questi casi sono analoghi all'algoritmo forward-backward e all'algoritmo di Viterbi per il caso degli HMM;
• se il CRF contiene solo funzioni-potenziali a coppie e l'energia è sub-modulare, si possono calcolare soluzioni esatte mediante algoritmi combinatori min cut/max flow.

Se l'inferenza esatta non è possibile o non è trattabile, si possono utilizzare diversi algoritmi per ottenere soluzioni approssimate, fra i quali:

• Belief propagation
• Espansione Alpha
• Mean field inference
• Metodi ad hoc di programmazione lineare

Apprendimento dei parametri

L'apprendimento dei parametri $\theta$ di solito viene operato tramite stima di massima verosimiglianza della distribuzione $p(Y_{i}|X_{i};\theta )$. Se tutti i nodi, ossia le relative variabili, hanno distribuzioni della famiglia esponenziale e sono tutte osservate in fase di addestramento (supervisionato), l'apprendimento si traduce in un problema di ottimizzazione convessa. Tale problema può essere risolto, ad esempio, utilizzando algoritmi di discesa del gradiente o metodi Quasi-Newton come l'algoritmo L-BFGS. D'altro canto, se alcune delle variabili non sono osservate, va risolto anche il problema di inferenza per tali variabili. In generale, nei grafi di struttura arbitraria l'inferenza esatta risulta impossibile, quindi bisogna ricorrere ad approssimazioni.

Esempi

Nella modellazione di dati sequenziali, il grafo di interesse è solitamente un grafo a catena. Una sequenza di input di variabili osservate $X$ costituisce una sequenza di osservazioni e $Y$ rappresenta una variabile di stato latente (ossia sconosciuta) che deve essere dedotta in base alle osservazioni. In nodo relativi alle $Y_{i}$ formano una catena, con un arco tra ciascuna coppia $Y_{i-1}$ e $Y_{i}$.

Oltre a una semplice interpretazione dei valori di $Y_{i}$ come "etichette" per ogni elemento nella sequenza di input, questo tipo di layout ammette algoritmi efficienti per:

• l'addestramento del modello, apprendimento delle distribuzioni condizionate tra le $Y_{i}$ e funzioni caratteristiche da un corpus di dati di addestramento;
• la decodifica, calcolo della probabilità di una certa sequenza di etichette $Y$ dato $X$;
• l'inferenza, calcolo della sequenza di etichette più probabile $Y$ dato $X$.

La dipendenza condizionata di ciascun $Y_{i}$ da $X$ è definita attraverso un insieme fisso di funzioni caratteristiche della forma $f(i,Y_{i-1},Y_{i},X)$, che possono essere viste come misurazioni che in base alla sequenza di input determinano parzialmente la probabilità di ogni possibile valore per $Y_{i}$. Il modello assegna a ciascuna feature un peso numerico e le combina per determinare la probabilità di un certo valore per $Y_{i}$.

I CRF a catena lineare hanno molte applicazioni in comune con gli HMM i quali sono concettualmente più semplici, ma rilassano alcune ipotesi sulle distribuzioni delle sequenze di input e output. Un HMM può essere inteso in senso lato come un CRF con funzioni caratteristiche molto specifiche che utilizzano probabilità costanti per modellare le transizioni di stato e gli output. Al contrario, un CRF può essere inteso in senso lato come una generalizzazione di un HMM che trasforma le probabilità di transizione costanti in funzioni arbitrarie che variano attraverso le posizioni nella sequenza di stati nascosti, a seconda della sequenza di input.

In particolare, a differenza degli HMM, i CRF possono contenere un numero qualsiasi di funzioni caratteristiche, tali funzioni possono ispezionare l'intera sequenza di input $X$ in qualsiasi momento durante l'inferenza e il loro codominio non deve necessariamente avere un'interpretazione probabilistica.

Voci correlate

• Modello di Markov a massima entropia (MEMM)
• Campo casuale di Markov