Conditional random field: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Argomenti collegati: non standard |
Funzionalità collegamenti suggeriti: 2 collegamenti inseriti. |
||
| (4 versioni intermedie di 3 utenti non mostrate) | |||
Riga 17:
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 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 [[Markov random field|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 [[Algoritmo forward-backward|forward-backward]] e all'[[algoritmo di Viterbi]] per il caso degli [[Modello di Markov nascosto|HMM]].
Riga 25:
Se l'inferenza esatta non è possibile/trattabile, si possono utilizzare diversi algoritmi per ottenere soluzioni ''approssimate'', fra cui:
* [[
* [[
* [[
* Rilassamenti della [[programmazione lineare]]
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 tutte sono osservate in fase di addestramento (supervisionato), l'apprendimento costituisce 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 per tali variabili. Nei grafi di struttura arbitraria l'inferenza esatta risulta impossibile, quindi bisogna ricorrere ad approssimazioni.
Nella modellazione di 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 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'', calcolo della probabilità di una certa sequenza di etichette <math>Y</math> dato <math>X</math>.
* l{{'}}''inferenza'', calcolo della sequenza di etichette ''più probabile'' <math>Y</math> dato <math>X</math> .
La dipendenza condizionata 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 che in base alla sequenza di input determinano parzialmente la [[Funzione di verosimiglianza|probabilità]] di ogni possibile valore per <math>Y_{i}</math>. Il modello assegna a ciascuna feature 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.
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 <math>X</math> in qualsiasi momento durante l'inferenza e il loro codominio non deve necessariamente avere un'interpretazione probabilistica.
Riga 50:
== Note ==
<references />
== Voci correlate ==
* [[Modello di Markov a massima entropia]] (MEMM)
* [[Campo casuale di Markov]]
[[Categoria:Apprendimento automatico]]
[[Categoria:Pagine con traduzioni non revisionate]]
[[Categoria:Variabili casuali]]
| |||