Conditional random field: differenze tra le versioni

Versione delle 20:36, 16 ago 2024

Versione delle 02:01, 17 ago 2024

Riga 1:

{{C|Da controllare la correttezza della traduzione dalla versione inglese della voce. Alcune frasi non sono sintatticamente corrette in italiano.|Informatica|agosto 2024}}

'''I Conditional Random Field''' ( '''CRF''' ) sono una classe di metodi di [[Modello statistico|modellazione statistica]] spesso applicatiutilizzati nel [[riconoscimento di pattern]] e nell'[[Apprendimento automatico|nell'apprendimento automatico]] e utilizzatianche 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 del contesto. A tale scopo, le previsioni vengono basate su un [[modello grafico|modello grafo]], 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 [[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|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|autore=Settles, B.|url=http://www.aclweb.org/anthology/W04-1221.pdf}}</ref>, la ricerca di geni, la ricerca di regioni funzionali critiche deldei peptidepeptidi<ref>{{Cita pubblicazione|volume=10|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|url=https://www.researchgate.net/publication/281620302}}</ref> e la [[Segmentazione di immagini|segmentazione delle immagini]] nella [[visione artificiale]]<ref>{{Cita news|linkautore=Xuming He}}</ref>.

== Descrizione ==

I CRF sono un tipo di [[modello grafico|modello grafo]] probabilistico discriminativo non orientato .

Lafferty, McCallum e Pereira <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> definiscono un CRF sulle osservazioni <math>\boldsymbol{X}</math> e [[Variabile casuale|variabili casuali]] <math>\boldsymbol{Y}</math> 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 di <math>G</math> .

<math>(\boldsymbol{X}, \boldsymbol{Y})</math> è un campo''conditional casualerandom condizionalefield'' se ogni variabile casuale <math>\boldsymbol{Y}_v</math>, condizionata su <math>\boldsymbol{X}</math>, gode della [[proprietà di Markov]] rispetto al grafo ossia 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> significa che <math>w</math> e <math>v</math> sono vicini in <math>G</math> .</blockquote>Ciò significa che un CRF è un [[Modello grafico|modello grafografico non orientato]] i cui nodi possono essere divisi 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 condizionale.

==== Inferenza ====

Per i grafi generaliarbitrari, il problema dell'inferenza esatta nellenei 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 unl'inferenza esatta:

* Se il grafo è una catena o un albero, gli algoritmi di ''passaggio deidi messaggi'' forniscono soluzioni esatte. Gli algoritmi utilizzati in questi casi sono analoghi all'algoritmo [[Algoritmo forward-backward|forward-backward]] e [[Algoritmo di Viterbi|all'[[algoritmo di Viterbi]] per il caso degli [[Modello di Markov nascosto|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 approssimativeapprossimate. Questi includono:

* [[Loopy belief propagation]]

* [[Espansione Alpha]]

* [[Mean field inference]]

* Rilassamenti della [[programmazione lineare]]

==== Apprendimento dei parametri ====

L'apprendimento dei parametri <math>\theta</math> di solito viene operatosvolto tramite apprendimentostima [[Metodo della massima verosimiglianza|di massima verosimiglianza]] di <math>p(Y_i|X_i; \theta)</math> . Se tutti i nodi hanno distribuzioni familiaridella famiglia esponenzialiesponenziale e tutti i nodi vengonosono osservati durante l'addestramento, questasi tratta di un problema di [[Ottimizzazione (matematica)|ottimizzazione]] è convessa. PuòEsso può essere risolto ad esempio utilizzando algoritmi di [[Discesa del gradiente|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 deveva essererisolto risoltoanche per queste variabili. Nei grafi generalidi struttura arbitraria l'inferenza esatta è impossibile, quindi è necessario ricorrere allead approssimazioni.

==== Esempi ====

Nella modellazione sequenziale, 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. ILGli <math>Y_{i}</math> sono strutturati in modo da formare una catena, con un bordoarco tra ciascuna coppia <math>Y_{i-1}</math> Ee <math>Y_{i}</math> . Oltre adOltre averea una semplice interpretazione deldei <math>Y_{i}</math> come "etichette" per ogni elemento nella sequenza di input, questo layout ammette algoritmi efficienti per:

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

* la ''decodifica'', determinazione della probabilità di una datacerta 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> .

La dipendenza condizionale di ciascunociascun <math>Y_{i}</math> SUda <math>X</math> è definitodefinita attraverso un insieme fisso di ''funzioni caratteristiche'' della forma <math>f(i, Y_{i-1}, Y_{i}, X)</math>, che possono essere pensateviste 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> .

I CRF a catena lineare hanno molte delleapplicazioni stessein applicazionicomune con deii modelli di Markov nascosti (HMM) concettualmente più semplici, ma allentanorilassano 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 legli emissionioutput. 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 l'intervalloil delleloro funzioni caratteristichecodominio non deve necessariamente avere un'interpretazione probabilistica.

== VediArgomenti anchecollegati ==

* Teorema di Hammersley-Clifford