Conditional random field: differenze tra le versioni

Versione delle 18:40, 17 ago 2024

Versione attuale delle 17:08, 16 nov 2024

(8 versioni intermedie di 3 utenti non mostrate)

Riga 2:

'''I Conditional Random Field'''<ref name="Laf:McC:Per01">{{Cita conferenza|titolo=Conditional random fields: Probabilistic models for segmenting and labeling sequence data|conferenza=ICML 2001: 18th International Conf. on Machine Learning|autore=Lafferty, J. McCallum, A., Pereira, F.|data=2001|pagine=282–289|url=http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162&context=cis_papers|editore=Morgan Kaufmann}}

</ref> ( '''CRF''' ) sono una classe di metodi di [[Modello statistico|modellazione statistica]] spesso utilizzati nel [[riconoscimento di pattern]] e nell'[[apprendimento automatico]] anche per predizioni strutturate. Mentre un generico [[Classificazione statistica|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 previsionipredizioni vengonosono basate su un [[modello grafico]], che rappresenta la presenza di dipendenze tra le variabili in giocoaleatorie. 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 previsionipredizioni simili.

Altri esempi di applicazione dei CRF sono: l'etichettatura o [[Parsing|analisi]] di dati sequenziali per l'[[elaborazione del linguaggio naturale]] o di [[Bioinformatica|sequenze biologiche]], il [[Analisi grammaticale|POS tagging]], l'analisi superficiale<ref>{{Cita conferenza|autore=Sha, F.; Pereira, F.|titolo=Shallow parsing with conditional random fields.|url=http://portal.acm.org/ft_gateway.cfm?id=1073473&type=pdf&CFID=4684435&CFTOKEN=39459323}}</ref>, il [[Risoluzione all'identità|riconoscimento di entità]]<ref>{{Cita conferenza|titolo=Biomedical named entity recognition using conditional random fields and rich feature sets|conferenza=Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications|autore=Settles, B.|pagine=104–107|url=http://www.aclweb.org/anthology/W04-1221.pdf}}</ref>, la ricerca di geni, la ricerca di regioni funzionali critiche dei peptidi<ref>{{Cita pubblicazione|autore=Chang KY; Lin T-p; Shih L-Y; Wang C-K|anno=2015|titolo=Analysis and Prediction of the Critical Regions of Antimicrobial Peptides Based on Conditional Random Fields|rivista=PLOS ONE|volume=10|numero=3|doi=10.1371/journal.pone.0119490|bibcode=2015PLoSO..1019490C|PMID=25803302}}</ref>, il [[Object recognition|riconoscimento di oggetti]] <ref name="Rui:Gal:Gon15">{{Cita conferenza|titolo=UPGMpp: a Software Library for Contextual Object Recognition|conferenza=3rd Workshop on Recognition and Action for Scene Understanding (REACTS)|autore=J.R. Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez|data=2015|DOI=10.13140/RG.2.2.25749.12006|url=https://www.researchgate.net/publication/281620302}}</ref> e la [[Segmentazionesegmentazione di immagini|segmentazione delle immagini]] nella [[visione artificiale]].

== Descrizione ==

IFormalmente, i CRF sono un tipo di [[modello grafico]] probabilistico discriminativo non orientato.

Lafferty, McCallum e Pereira <ref name="Laf:McC:Per01"></ref> definiscono un CRF sulle osservazioni <math>\boldsymbol{X}</math> e le [[Variabile casuale|variabili casuali]] <math>\boldsymbol{Y}</math> (di output) come segue:<blockquote>Sia <math>G = (V, E)</math> un grafo tale che <math>\boldsymbol{Y} = (\boldsymbol{Y}_v)_{v\in V}</math>, in modo che <math>\boldsymbol{Y}</math> sia indicizzato dai vertici (nodi) di <math>G</math> .

<math>(\boldsymbol{X}, \boldsymbol{Y})</math> è un ''conditional random field'' se ogni variabile casuale <math>\boldsymbol{Y}_v</math>, condizionata su <math>\boldsymbol{X}</math>, gode della [[proprietà di Markov]] rispetto al grafo ossia se la sua probabilità dipende solo dai suoi vicini in <math>G</math>:

<math>P(\boldsymbol{Y}_v |\boldsymbol{X}, \{\boldsymbol{Y}_w: w \neq v\}) = P(\boldsymbol{Y}_v |\boldsymbol{X}, \{\boldsymbol{Y}_w: w \sim v\})</math>

dove <math>\mathit{w} \sim v</math> significadenota il fatto che <math>w</math> e <math>v</math> sono vicini in <math>G</math> .</blockquote>Ciò significavuol dire che un CRF è un [[Modello grafico|modello grafico non orientato]] i cui nodi possono essere divisiseparati esattamente in due insiemi disgiunti <math>\boldsymbol{X}</math> e <math>\boldsymbol{Y}</math>, comprendenti, rispettivamente, le variabili osservate e quelle di output; ne discende un modello <math>p(\boldsymbol{Y}|\boldsymbol{X})</math> della distribuzione condizionalecondizionata.

==== Inferenza ====

Per i grafi arbitrari, il problema dell{{'}}''inferenza esatta'' nei CRF èrisulta intrattabile. Il problema di inferenza perusando un CRF è fondamentalmente è lo stesso che risulta dall'uso di un [[Markov random field|MRF]] evalendo per valgonoentrambi glile stessistesse argomentiargomentazioni. Tuttavia, esistono casi speciali per i quali è possibile l'inferenza esatta:

* Se il grafo è una catena o un albero, gli algoritmi dia ''passaggio di messaggi'' (message passing) forniscono soluzioni esatte. Gli algoritmi utilizzati in questi casi sono analoghi all'algoritmo [[Algoritmo forward-backward|forward-backward]] e all'[[algoritmo di Viterbi]] per il caso degli [[Modello di Markov nascosto|HMM]].

* Se il CRF contiene solo potenziali a coppie e l'energia è submodularesub-modulare, gli algoritmi combinatori ''min cut/max flow'' fornisconosono in grado di calcolare soluzioni esatte.

Se l'inferenza esatta non è impossibilepossibile/trattabile, si possono utilizzare diversi algoritmi per ottenere soluzioni ''approssimate.'', Questifra includonocui:

* [[Loopy beliefBelief propagation]]

* [[Espansione Alpha]]

* [[Mean field inference]]

* Rilassamenti della [[programmazione lineare]]

==== Apprendimento dei parametri ====

L'apprendimento dei parametri <math>\theta</math> di solito viene svolto tramite stima [[Metodo della massima verosimiglianza|di massima verosimiglianza]] di <math>p(Y_i|X_i; \theta)</math>. Se tutti i nodi, ossia le relative variabili, hanno distribuzioni della famiglia esponenziale e tuttitutte isono nodiosservate sonoin osservatifase durantedi l'addestramento (supervisionato), sil'apprendimento tratta dicostituisce un problema di [[Ottimizzazione (matematica)|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 va risolto anche per questetali variabili. Nei grafi di struttura arbitraria l'inferenza esatta èrisulta impossibile, quindi è necessariobisogna ricorrere ad approssimazioni.

==== Esempi ====

Nella modellazione sequenzialedi dati sequenziali, il grafo di interesse è solitamente un grafo a catena. Una sequenza di input di variabili osservate <math>X</math> rappresenta una sequenza di osservazioni e <math>Y</math> rappresenta una [[variabile di stato]] nascosta (o sconosciuta) che deve essere dedotta in base alle osservazioni. Gli <math>Y_{i}</math> sono strutturati in modo da formare una catena, con un arco tra ciascuna coppia <math>Y_{i-1}</math> e <math>Y_{i}</math>. Oltre a una semplice interpretazione dei <math>Y_{i}</math> come "etichette" per ogni elemento nella sequenza di input, questo layout ammette algoritmi efficienti per:

Oltre a una semplice interpretazione dei <math>Y_{i}</math> 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 <math>Y_{i}</math> e funzioni caratteristiche da un corpus di dati di addestramento.

* la ''decodifica'', determinazione della probabilità di una certa sequenza di etichette <math>Y</math> dato <math>X</math> .

* l'''inferenza'', determinazione della sequenza di etichette ''più probabile'' <math>Y</math> dato <math>X</math> .

* l{{'}}''addestramento'' del modello, apprendimento delle distribuzioni condizionali tra le <math>Y_{i}</math> e funzioni caratteristiche da un corpus di dati di addestramento.

La dipendenza condizionale di ciascun <math>Y_{i}</math> da <math>X</math> è definita attraverso un insieme fisso di ''funzioni caratteristiche'' della forma <math>f(i, Y_{i-1}, Y_{i}, X)</math>, che possono essere viste come misurazioni sulla sequenza di input che determinano parzialmente la [[Funzione di verosimiglianza|probabilità]] di ogni possibile valore per <math>Y_{i}</math>. Il modello assegna a ciascuna caratteristica un peso numerico e li combina per determinare la probabilità di un certo valore per <math>Y_{i}</math>.

* la ''decodifica'', determinazionecalcolo della probabilità di una certa sequenza di etichette <math>Y</math> dato <math>X</math> .

* l{{'}}''inferenza'', determinazionecalcolo della sequenza di etichette ''più probabile'' <math>Y</math> dato <math>X</math> .

La dipendenza condizionalecondizionata di ciascun <math>Y_{i}</math> da <math>X</math> è definita attraverso un insieme fisso di ''funzioni caratteristiche'' della forma <math>f(i, Y_{i-1}, Y_{i}, X)</math>, che possono essere viste come misurazioni sullache in base alla sequenza di input che determinano parzialmente la [[Funzione di verosimiglianza|probabilità]] di ogni possibile valore per <math>Y_{i}</math>. Il modello assegna a ciascuna caratteristicafeature un peso numerico e li combina per determinare la probabilità di un certo valore per <math>Y_{i}</math>.

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.

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 <math>X</math> in qualsiasi momento durante l'inferenza e il loro codominio non deve necessariamente avere un'interpretazione probabilistica.

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 <math>X</math> in qualsiasi momento durante l'inferenza e il loro codominio non deve necessariamente avere un'interpretazione probabilistica.

== Argomenti collegati ==

== Note ==

* Teorema di Hammersley-Clifford

<references />

* Modello di Markov a massima entropia (MEMM)

== RiferimentiVoci correlate ==

* [[Modello di Markov a massima entropia]] (MEMM)

{{References|30em}}

* [[Campo casuale di Markov]]

[[Categoria:Apprendimento automatico]]

[[Categoria:Modelli grafici]]

[[Categoria:Pagine con traduzioni non revisionate]]

[[Categoria:ModelliVariabili graficicasuali]]