Conditional random field: differenze tra le versioni

Versione delle 20:15, 16 ago 2024

Versione attuale delle 17:08, 16 nov 2024

(17 versioni intermedie di 3 utenti non mostrate)

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'''<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}}

'''I Conditional Random Field'''</ref> ( '''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 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 graficografo 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.

</ref>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 deldei peptidepeptidi<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]]<ref>{{Cita news|linkautore=Xuming He}}</ref>.

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]]<ref name="Laf:McC:Per01">{{Cita conferenza|autore=Lafferty, J.|url=http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162&context=cis_papers}}

</ref>, 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 del peptide<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 ==

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> .

Lafferty, McCallum e Pereira <ref name="Laf:McC:Per01">{{Cita conferenza|autore=Lafferty, J.|url=http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162&context=cis_papers}}<cite class="citation conference cs1" data-ve-ignore="true" id="CITEREFLafferty,_J.McCallum,_A.Pereira,_F.2001">Lafferty, J.; McCallum, A.; Pereira, F. (2001). [http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162&context=cis_papers "Conditional random fields: Probabilistic models for segmenting and labeling sequence data"]. ''Proc. 18th International Conf. on Machine Learning''. Morgan Kaufmann. pp.&nbsp;282–289.</cite>

</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 se la sua probabilità dipende solo dai suoi vicini in <math>G</math>:

Si può scrivere:<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 grafico 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.

dove <math>\mathit{w} \sim v</math> denota il fatto che <math>w</math> e <math>v</math> sono vicini in <math>G</math>.</blockquote>Ciò vuol dire che un CRF è un [[Modello grafico|modello grafico non orientato]] i cui nodi possono essere separati 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 condizionata.

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:

=== Inferenza ===

* 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 [[Algoritmo forward-backward|forward-backward]] e [[Algoritmo di Viterbi|all'algoritmo di Viterbi]] per il caso degli HMM.

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

* Se il CRF contiene solo potenziali a coppie e l'energia è submodulare, gli algoritmi combinatori min cut/max flow forniscono soluzioni esatte.

* Se il graficografo è una catena o un albero, gli algoritmi dia ''passaggio deidi messaggi'' (message passing) 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 l'inferenza esatta è impossibile, si possono utilizzare diversi algoritmi per ottenere soluzioni approssimative. Questi includono:

* 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 approssimative.''approssimate'', Questifra includonocui:

* Propagazione di credenze strampalate

* Espansione Alpha

* Inferenza del campo medio

* Rilassamenti della programmazione lineare

* [[Belief propagation]]

Apprendimento dei parametri <math>\theta</math> di solito viene fatto tramite apprendimento [[Metodo della massima verosimiglianza|di massima verosimiglianza]] per <math>p(Y_i|X_i; \theta)</math> . Se tutti i nodi hanno distribuzioni familiari esponenziali e tutti i nodi vengono osservati durante l'addestramento, questa [[Ottimizzazione (matematica)|ottimizzazione]] è convessa. Può essere risolto ad esempio utilizzando algoritmi [[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 deve essere risolto per queste variabili. Nei grafici generali l'inferenza esatta è impossibile, quindi è necessario ricorrere alle approssimazioni.

* [[Espansione Alpha]]

* [[Mean field inference]]

* Rilassamenti della [[programmazione lineare]]

=== Apprendimento dei parametri ===

Nella modellazione sequenziale, il grafico di interesse è solitamente un grafico 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. IL <math>Y_{i}</math> sono strutturati in modo da formare una catena, con un bordo tra ciascuna <math>Y_{i-1}</math> E <math>Y_{i}</math> . Oltre ad avere una semplice interpretazione del <math>Y_{i}</math> come "etichette" per ogni elemento nella sequenza di input, questo layout ammette algoritmi efficienti per:

ApprendimentoL'apprendimento dei parametri <math>\theta</math> di solito viene fattosvolto tramite apprendimentostima [[Metodo della massima verosimiglianza|di massima verosimiglianza]] perdi <math>p(Y_i|X_i; \theta)</math> . Se tutti i nodi, ossia le relative variabili, hanno distribuzioni familiaridella famiglia esponenzialiesponenziale e tuttitutte isono nodiosservate vengonoin osservatifase durantedi l'addestramento (supervisionato), questal'apprendimento costituisce 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, va risolto anche il problema di inferenza deve essere risolto per questetali variabili. Nei graficigrafi generalidi struttura arbitraria l'inferenza esatta èrisulta impossibile, quindi è necessariobisogna ricorrere allead approssimazioni.

=== Esempi ===

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

Nella modellazione sequenzialedi dati sequenziali, il graficografo di interesse è solitamente un graficografo 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 ad avere una semplice interpretazione del <math>Y_{i}</math> come "etichette" per ogni elemento nella sequenza di input, questo layout ammette algoritmi efficienti per:

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

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

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:

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

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

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.

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

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'intervallo delle funzioni caratteristiche non deve necessariamente avere un'interpretazione probabilistica.

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.

== Vedi anche ==

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.

* Teorema di Hammersley-Clifford

* Modello di Markov a massima entropia (MEMM)

== RiferimentiNote ==

<references />

{{References|30em}}

== Voci correlate ==

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

* [[Campo casuale di Markov]]

== Ulteriori letture ==

* McCallum, A.: [[arxiv:1212.2504|Induzione efficiente di caratteristiche di campi casuali condizionali]] . In: ''Proc.'' ''19a Conferenza sull'incertezza nell'intelligenza artificiale'' . (2003)

* Wallach, HM : [http://www.cs.umass.edu/~wallach/technical_reports/wallach04conditional.pdf Campi casuali condizionali: un'introduzione] . Rapporto tecnico MS-CIS-04-21, Università della Pennsylvania (2004)

* Sutton, C., McCallum, A.: Introduzione ai campi casuali condizionali per l'apprendimento relazionale. In "Introduzione all'apprendimento relazionale statistico". A cura di Lise Getoor e Ben Taskar. Casa editrice del MIT. (2006) [http://www.cs.umass.edu/~mccallum/papers/crf-tutorial.pdf PDF in linea]

* Klinger, R., Tomanek, K.: Modelli probabilistici classici e campi casuali condizionali. Rapporto di ingegneria algoritmica TR07-2-013, Dipartimento di informatica, Università di tecnologia di Dortmund, dicembre 2007. ISSN 1864-4503. [http://ls11-www.cs.uni-dortmund.de/_media/techreports/tr07-13.pdf PDF in linea]

[[Categoria:Apprendimento automatico]]

[[Categoria:Modelli grafici]]

[[Categoria:Pagine con traduzioni non revisionate]]

[[Categoria:ModelliVariabili graficicasuali]]