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 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[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 delle immagini nella visione artificiale.
Descrizione
[modifica | modifica wikitesto]I CRF sono un tipo di modello grafico probabilistico discriminativo non orientato.
Lafferty, McCallum e Pereira [1] definiscono un CRF sulle osservazioni e variabili casuali come segue:
Sia un grafo tale che , in modo che sia indicizzato dai vertici di .
è un conditional random field se ogni variabile casuale , condizionata su , gode della proprietà di Markov rispetto al grafo ossia la sua probabilità dipende solo dai suoi vicini in :
dove significa che e sono vicini in .
Ciò significa che un CRF è un modello grafico non orientato i cui nodi possono essere divisi esattamente in due insiemi disgiunti e , comprendenti, rispettivamente, le variabili osservate e quelle di output; ne discende un modello della distribuzione condizionale.
Inferenza
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]L'apprendimento dei parametri di solito viene svolto tramite stima di massima verosimiglianza di . 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
[modifica | modifica wikitesto]Nella modellazione sequenziale, il grafo di interesse è solitamente un grafo a catena. Una sequenza di input di variabili osservate rappresenta una sequenza di osservazioni e rappresenta una variabile di stato nascosta (o sconosciuta) che deve essere dedotta in base alle osservazioni. Gli sono strutturati in modo da formare una catena, con un arco tra ciascuna coppia e . Oltre a una semplice interpretazione dei 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 e funzioni caratteristiche da un corpus di dati di addestramento.
- la decodifica, determinazione della probabilità di una certa sequenza di etichette dato .
- l'inferenza, determinazione della sequenza di etichette più probabile dato .
La dipendenza condizionale di ciascun da è definita attraverso un insieme fisso di funzioni caratteristiche della forma , che possono essere viste come misurazioni sulla sequenza di input che determinano parzialmente la probabilità di ogni possibile valore per . Il modello assegna a ciascuna caratteristica un peso numerico e li combina per determinare la probabilità di un certo valore per .
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 in qualsiasi momento durante l'inferenza e il loro codominio non deve necessariamente avere un'interpretazione probabilistica.
Argomenti collegati
[modifica | modifica wikitesto]- Teorema di Hammersley-Clifford
- Modello di Markov a massima entropia (MEMM)
Riferimenti
[modifica | modifica wikitesto]- ^ a b 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.
- ^ Sha, F.; Pereira, F., Shallow parsing with conditional random fields..
- ^ Settles, B., Biomedical named entity recognition using conditional random fields and rich feature sets (PDF), Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications, pp. 104–107.
- ^ Chang KY; Lin T-p; Shih L-Y; Wang C-K, Analysis and Prediction of the Critical Regions of Antimicrobial Peptides Based on Conditional Random Fields, in PLOS ONE, vol. 10, n. 3, 2015, Bibcode:2015PLoSO..1019490C, DOI:10.1371/journal.pone.0119490, PMID 25803302.
- ^ J.R. Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez, UPGMpp: a Software Library for Contextual Object Recognition, 3rd Workshop on Recognition and Action for Scene Understanding (REACTS), 2015, DOI:10.13140/RG.2.2.25749.12006.