Conditional random field

I Conditional Random Field ( CRF ) sono una classe di metodi di modellazione statistica spesso applicati nel riconoscimento di pattern e nell'apprendimento automatico e utilizzati per predizioni strutturate. Mentre un 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 grafico 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^[1], il riconoscimento di entità, ^[2] la ricerca di geni, la ricerca di regioni funzionali critiche del peptide^[3], il riconoscimento di oggetti ^[4] e la segmentazione delle immagini nella visione artificiale^[5].

Descrizione

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

Lafferty, McCallum e Pereira ^[6] definiscono un CRF sulle osservazioni ${\displaystyle {\boldsymbol {X}}}$  e variabili casuali ${\displaystyle {\boldsymbol {Y}}}$  come segue:

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

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

${\displaystyle 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 ${\displaystyle {\mathit {w}}\sim v}$  significa che ${\displaystyle w}$  e ${\displaystyle v}$  sono vicini in ${\displaystyle G}$  .

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

Per i grafi generali, il problema dell'inferenza esatta nelle 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 un'inferenza esatta:

• Se il grafico è una catena o un albero, gli algoritmi di passaggio dei 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 approssimative. Questi includono:

• Propagazione di credenze strampalate
• Espansione Alpha
• Inferenza del campo medio
• Rilassamenti della programmazione lineare

Apprendimento dei parametri ${\displaystyle \theta }$  di solito viene fatto tramite apprendimento di massima verosimiglianza per ${\displaystyle p(Y_{i}|X_{i};\theta )}$  . Se tutti i nodi hanno distribuzioni familiari esponenziali e tutti i nodi vengono osservati durante l'addestramento, questa ottimizzazione è convessa. 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 deve essere risolto per queste variabili. Nei grafici generali l'inferenza esatta è impossibile, quindi è necessario ricorrere alle approssimazioni.

Nella modellazione sequenziale, il grafico di interesse è solitamente un grafico a catena. Una sequenza di input di variabili osservate ${\displaystyle X}$  rappresenta una sequenza di osservazioni e ${\displaystyle Y}$  rappresenta una variabile di stato nascosta (o sconosciuta) che deve essere dedotta in base alle osservazioni. IL ${\displaystyle Y_{i}}$  sono strutturati in modo da formare una catena, con un bordo tra ciascuna ${\displaystyle Y_{i-1}}$  E ${\displaystyle Y_{i}}$  . Oltre ad avere una semplice interpretazione del ${\displaystyle Y_{i}}$  come "etichette" per ogni elemento nella sequenza di input, questo layout ammette algoritmi efficienti per:

• addestramento del modello, apprendimento delle distribuzioni condizionali tra i ${\displaystyle Y_{i}}$  e funzioni caratteristiche da un corpus di dati di addestramento.
• decodifica, determinazione della probabilità di una data sequenza di etichette ${\displaystyle Y}$  dato ${\displaystyle X}$  .
• inferenza, determinazione della sequenza di etichette più probabile ${\displaystyle Y}$  dato ${\displaystyle X}$  .

La dipendenza condizionale di ciascuno ${\displaystyle Y_{i}}$  SU ${\displaystyle X}$  è definito attraverso un insieme fisso di funzioni caratteristiche della forma ${\displaystyle f(i,Y_{i-1},Y_{i},X)}$ , che possono essere pensate come misurazioni sulla sequenza di input che determinano parzialmente la probabilità di ogni possibile valore per ${\displaystyle Y_{i}}$  . Il modello assegna a ciascuna caratteristica un peso numerico e li combina per determinare la probabilità di un certo valore per ${\displaystyle Y_{i}}$  .

I CRF a catena lineare hanno molte delle stesse applicazioni dei modelli di Markov nascosti (HMM) concettualmente più semplici, ma allentano 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 le emissioni. 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 ${\displaystyle X}$  in qualsiasi momento durante l'inferenza e l'intervallo delle funzioni caratteristiche non deve necessariamente avere un'interpretazione probabilistica.

Vedi anche

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

Riferimenti

1. ^ http://portal.acm.org/ft_gateway.cfm?id=1073473&type=pdf&CFID=4684435&CFTOKEN=39459323. Parametro titolo vuoto o mancante (aiuto)
2. ^ Settles, B., http://www.aclweb.org/anthology/W04-1221.pdf. Parametro titolo vuoto o mancante (aiuto)
3. ^ vol. 10, Bibcode:2015PLoSO..1019490C, DOI:10.1371/journal.pone.0119490, PMID 25803302, https://oadoi.org/10.1371/journal.pone.0119490. Parametro titolo vuoto o mancante (aiuto)
4. ^ https://www.researchgate.net/publication/281620302. Parametro titolo vuoto o mancante (aiuto)
5. ^ Parametro titolo vuoto o mancante (aiuto)
6. ^ Lafferty, J. McCallum, A., Pereira, F., Conditional random fields: Probabilistic models for segmenting and labeling sequence data, ICML 2001: 18th International Conf. on Machine Learning, Morgan Kaufmann, 2001, pp. 282–289.