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.
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 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:
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:
Percettrone strutturato
Uno dei modi più semplici per comprendere gli algoritmi per la previsione strutturata generale è il percettrone strutturato di Collins. 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:
- Per prima cosa si definisce una funzione
che mappa un esempio di training 
e una predizione candidata 
su un vettore di lunghezza 
( e possono avere qualsiasi struttura; dipende dal problema, ma deve essere fissato per ogni modello). Sia 
una funzione che genera predizioni candidate.
- Quindi:
- Sia
un vettore-peso di lunghezza
- Per un numero predeterminato di iterazioni:
- Per ogni esempio nel training set con output atteso
:
- Fare una predizione
: 
- Aggiornare (da in direzione ):
, dove 
è il tasso di apprendimento .
In pratica, per trovare l'argmax su 
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.
