Conditional random field

I Conditional Random Field^[1] ( CRF ) 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 prevede un'etichetta per un singolo campione senza considerare i campioni "vicini", un CRF può tenere conto anche del contesto. A tale scopo, le predizioni sono basate su un modello grafico che rappresenta la presenza di dipendenze tra le variabili aleatorie. Il tipo di grafo utilizzato dipende dall'applicazione. Ad esempio, nell'elaborazione del linguaggio naturale sono diffuse le CRF "a catena lineare", nelle quali ogni variabile dipende solo dai suoi vicini immediati. Nell'elaborazione delle immagini, il grafo in genere collega le posizioni a posizioni vicine e/o simili per garantire che ricevano predizioni simili.

Altri esempi di applicazione dei CRF sono: l'etichettatura o analisi di dati sequenziali per l'elaborazione del linguaggio naturale o di sequenze biologiche, il POS tagging, l'analisi superficiale^[2], il riconoscimento di entità^[3], la ricerca di geni, la ricerca di regioni funzionali critiche dei peptidi^[4], il riconoscimento di oggetti ^[5] e la segmentazione di immagini nella visione artificiale.

Descrizione

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

Lafferty, McCallum e Pereira^[1] 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 casuale ${\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$ .

Ciò vuol dire che 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. Il problema di inferenza usando un CRF fondamentalmente è lo stesso che risulta dall'uso di un MRF 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 potenziali a coppie e l'energia è sub-modulare, gli algoritmi combinatori min cut/max flow sono in grado di calcolare soluzioni esatte.

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

Belief propagation
Espansione Alpha
Mean field inference
Rilassamenti della programmazione lineare

Apprendimento dei parametri

L'apprendimento dei parametri $\theta$ di solito viene svolto tramite stima di massima verosimiglianza di $p(Y_{i}|X_{i};\theta )$ . Se tutti i nodi, ossia le relative variabili, hanno distribuzioni della famiglia esponenziale e tutte sono osservate in fase di addestramento (supervisionato), l'apprendimento costituisce un problema di ottimizzazione convessa. Esso 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 variabili non sono osservate, va risolto anche il problema di inferenza per tali variabili. 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$ rappresenta una sequenza di osservazioni e $Y$ rappresenta una variabile di stato nascosta (o sconosciuta) che deve essere dedotta in base alle osservazioni. Gli $Y_{i}$ sono strutturati in modo da formare una catena, con un arco tra ciascuna coppia $Y_{i-1}$ e $Y_{i}$ .

Oltre a una semplice interpretazione dei $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 condizionali 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 li combina per determinare la probabilità di un certo valore per $Y_{i}$ .

I CRF a catena lineare hanno molte applicazioni in comune con i modelli di Markov nascosti (HMM) 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.