Predizione strutturata

La predizione strutturata o l'apprendimento con output strutturato è un termine generale che ricomprende tecniche di apprendimento automatico supervisionato che finalizzate alla predizione di oggetti strutturati, piuttosto che valori discreti o reali.^[1]

Analogamente alle tecniche di apprendimento supervisionato comunemente utilizzate, i modelli di predizione strutturata vengono in genere addestrati mediante dati osservati, in cui il valore previsto viene confrontato con i risultati attesi, e questo viene utilizzato per regolare i parametri del modello. A causa della complessità del modello e delle interrelazioni tra le variabili predette, i processi di addestramento e inferenza del modello sono spesso computazionalmente intrattabili, pertanto vengono utilizzati metodi approssimati di inferenza e apprendimento.

Applicazioni

Un esempio di applicazione è il problema di tradurre una frase in linguaggio naturale in una rappresentazione sintattica come un albero di parsing. Questo può essere visto come un problema di predizione strutturata ^[2] in cui il dominio di output strutturato è l'insieme di tutti i possibili alberi di analisi. La predizione strutturata è utilizzata in un'ampia varietà di domini, tra cui la bioinformatica, l'elaborazione del linguaggio naturale (NLP), il riconoscimento vocale e la visione artificiale.

Esempio: tagging di sequenze

Il tagging di sequenze è una classe di problemi prevalenti in NLP in cui i dati di input sono spesso sequenziali, ad esempio frasi di testo. Il problema del tagging di sequenze si presenta in diverse forme, come il tagging delle parti del discorso (POS tagging) e il riconoscimento di entità denominate. Nel POS tagging, ad esempio, a ogni parola in una sequenza deve essere assegnata un'etichetta di classe che ne rappresenti il tipo:

Questa	DT
è	VBZ
una	DT
frase	NN
etichettata.	JJ

La sfida principale in questo problema è dirimere l'ambiguità, allorché le stesse parole possono avere etichette diverse.

Tecniche

I modelli grafici probabilistici costituiscono un'ampia classe di modelli di previsione strutturati. In particolare, le reti bayesiane e i campi casuali sono molto diffusi. Altri algoritmi e modelli per la previsione strutturata includono la programmazione logica induttiva, il ragionamento basato sui casi, le SVM strutturate, le reti logiche di Markov, la logica probabilistica flessibile e i modelli condizionati vincolati. Le tecniche principali sono:

• Campi casuali condizionali
• Macchine a vettori di supporto strutturate
• K-NN strutturato
• Reti neurali ricorrenti, in particolare le reti di Elman
• Trasformatori

Percettrone strutturato

Uno dei modi più semplici per comprendere gli algoritmi per la previsione strutturata generale è il percettrone strutturato di Collins. ^[3] Questo algoritmo combina l'algoritmo del percettrone per l'apprendimento di classificatori lineari con un algoritmo di inferenza (classicamente l'algoritmo di Viterbi quando si utilizza su dati sequenziali) e può essere descritto in astratto come segue:

1. Per prima cosa si definisce una funzione ${\displaystyle \phi (x,y)}$  che mappa un esempio di training ${\displaystyle x}$  e una predizione candidata ${\displaystyle y}$  su un vettore di lunghezza ${\displaystyle n}$  ( ${\displaystyle x}$  e ${\displaystyle y}$  possono avere qualsiasi struttura; ${\displaystyle n}$  dipende dal problema, ma deve essere fissato per ogni modello). Sia ${\displaystyle GEN}$  una funzione che genera predizioni candidate.
2. Quindi:
   • Sia ${\displaystyle w}$  un vettore-peso di lunghezza ${\displaystyle n}$ 
   • Per un numero predeterminato di iterazioni:
     • Per ogni esempio ${\displaystyle x}$  nel training set con output atteso ${\displaystyle t}$ :
       • Fare una predizione ${\displaystyle {\hat {y}}}$  : ${\displaystyle {\hat {y}}={\operatorname {arg\,max} }\,\{y\in GEN(x)\}\,(w^{T},\phi (x,y))}$ 
       • Aggiornare ${\displaystyle w}$  (da ${\displaystyle {\hat {y}}}$  in direzione ${\displaystyle t}$ ): ${\displaystyle w=w+c(-\phi (x,{\hat {y}})+\phi (x,t))}$ , dove ${\displaystyle c}$  è il tasso di apprendimento .

In pratica, per trovare l'argmax su ${\displaystyle {GEN}({x})}$  si utilizza un algoritmo come quello di Viterbi o uno max-sum, piuttosto che una ricerca esaustiva su tutto l'insieme di insieme di candidati di dimensioni esponenziali.

L'idea di apprendimento è simile a quella dei percettrone multiclasse.

Note

1. ^ (EN) Gökhan BakIr, Thomas Hofmann, Bernhard Schölkopf, Alexander J. Smola, Ben Taskar & S.V.N Vishwanathan (eds.), Predicting Structured Data, collana Neural Information Processing series, MIT Press, 27 luglio 2007, ISBN 978-0-262-52804-7.
2. ^ John D. Lafferty, Andrew McCallum e Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, in Proceedings of the Eighteenth International Conference on Machine Learning, Morgan Kaufmann Publishers Inc., 28 giugno 2001, pp. 282–289, DOI:10.5555/645530.655813.
3. ^ Michael Collins, Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms, in Proceedings of the ACL-02 conference on Empirical methods in natural language processing - Volume 10, Association for Computational Linguistics, 6 luglio 2002, pp. 1–8, DOI:10.3115/1118693.1118694.

Riferimenti Bibliografici

• Noah Smith, Linguistic Structure Prediction, 2011.
• Michael Collins, Discriminative Training Methods for Hidden Markov Models 2002.

Link esterni

• Implementazione del percettrone strutturato di Collins