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
[modifica | modifica wikitesto]Formalmente, i CRF sono un tipo di modello grafico probabilistico discriminativo non orientato.
Lafferty, McCallum e Pereira[1] definiscono un CRF sulle osservazioni e le variabili casuali (di output) come segue:
Sia un grafo tale che , in modo che sia indicizzato dai vertici (nodi) di .
è un conditional random field se ogni variabile casuale , condizionata su , gode della proprietà di Markov rispetto al grafo ossia se la sua probabilità dipende solo dai suoi vicini in :
dove denota il fatto che e sono vicini in .
Ciò vuol dire che un CRF è un modello grafico non orientato i cui nodi possono essere separati esattamente in due insiemi disgiunti e , comprendenti, rispettivamente, le variabili osservate e quelle di output; ne discende un modello della distribuzione condizionata.
Inferenza
[modifica | modifica wikitesto]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:
- 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, 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
[modifica | modifica wikitesto]Nella modellazione di dati sequenziali, 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 tipo di 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, calcolo della probabilità di una certa sequenza di etichette dato .
- l'inferenza, calcolo della sequenza di etichette più probabile dato .
La dipendenza condizionata di ciascun da è definita attraverso un insieme fisso di funzioni caratteristiche della forma , che possono essere viste come misurazioni che in base alla sequenza di input determinano parzialmente la probabilità di ogni possibile valore per . Il modello assegna a ciascuna feature 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 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]- Algoritmi message-passing: Belief propagation
- 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.