Conditional random field

I Conditional Random Field ( 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 del contesto. A tale scopo, le previsioni vengono basate su un modello grafico, che rappresenta la presenza di dipendenze tra le variabili in gioco. 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 previsioni 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, il riconoscimento di entità, la ricerca di geni, la ricerca di regioni funzionali critiche dei peptidi, il riconoscimento di oggetti e la segmentazione delle immagini nella visione artificiale.

Descrizione

I CRF sono un tipo di modello grafico probabilistico discriminativo non orientato.

Lafferty, McCallum e Pereira definiscono un CRF sulle osservazioni ${\boldsymbol {X}}$ e variabili casuali ${\boldsymbol {Y}}$ 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 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 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$ significa che $w$ e $v$ sono vicini in $G$ .

Ciò significa che un CRF è un modello grafico non orientato i cui nodi possono essere divisi 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 condizionale.

Inferenza

Per i grafi arbitrari, il problema dell'inferenza esatta nei CRF è intrattabile. Il problema di inferenza per un CRF è fondamentalmente lo stesso di un MRF e valgono gli stessi argomenti. Tuttavia, esistono casi speciali per i quali è possibile l'inferenza esatta:

• Se il grafo è una catena o un albero, gli algoritmi di passaggio di messaggi 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 è submodulare, gli algoritmi combinatori min cut/max flow forniscono soluzioni esatte.

Se l'inferenza esatta è impossibile, si possono utilizzare diversi algoritmi per ottenere soluzioni approssimate. Questi includono:

• Loopy 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 hanno distribuzioni della famiglia esponenziale e tutti i nodi sono osservati durante l'addestramento, si tratta di 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, il problema di inferenza va risolto anche per queste variabili. Nei grafi di struttura arbitraria l'inferenza esatta è impossibile, quindi è necessario ricorrere ad approssimazioni.

Esempi

Nella modellazione sequenziale, 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 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, determinazione della probabilità di una certa sequenza di etichette $Y$ dato $X$ .
• l'inferenza, determinazione della sequenza di etichette più probabile $Y$ dato $X$ .

La dipendenza condizionale 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 sulla sequenza di input che determinano parzialmente la probabilità di ogni possibile valore per $Y_{i}$. Il modello assegna a ciascuna caratteristica 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 di 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.

Argomenti collegati

• Teorema di Hammersley-Clifford
• Modello di Markov a massima entropia (MEMM)