Deep Dive: dependency parsing (MALT, MST, biaffine)

Companion di notes.md (§5). Fonte: lezione-04-Syntax03-TLN-INFO-2526.pdf.

1. Il problema

Dato w_1..n, trovare testa h(i) ed etichetta l(i) per ogni parola (piu’ radice ROOT).
Vincoli: albero singolo (connesso, aciclico), di solito proiettivo.

2. I 5 algoritmi (mappa)

#AlgoritmoIdeaProiettivo?Costo
1Eisner chartDP su span come CKYsi’O(n^3)
2MST McDonaldmax spanning tree su grafo completonoO(n^2)-O(n^3)
3MALT/Nivre transition-basedshift-reduce + classificatoresi’ (varianti no)O(n)
4Beam/stack-LSTMtransizioni con memoria e beamsi’O(n·beam)
5Biaffine Dozat-ManningBiLSTM + scorer biaffine + MSTnoO(n^2)

3. MALT passo passo

Stato: stack S, buffer B, archi E. Esempio I Jedi possono avere figli (semplificato):
SHIFT spinge I, Jedi; LEFT-ARC crea Jedi -det-> I; SHIFT fino ad avere; RIGHT-ARC crea
avere -nsubj-> Jedi… Il classificatore guarda in cima a stack/buffer (parole, tag, archi
parziali) e sceglie l’azione. Training: oracle che deriva la sequenza gold; learning: SVM/MLP.
Errore tipico: propagazione (una azione sbagliata avvelena il resto) -> beam search.

4. MST e biaffine

MST: ogni arco (h->d) ha peso s(h,d) (e con etichetta s(h,d,l)); Chu-Liu-Edmonds trova
l’arborescenza massima. Biaffine: s(h,d) = h_h^T W h_d + ... con rappresentazioni BiLSTM
di testa/dipendente: preciso e parallelo, domina pre-LLM.

5. UAS/LAS ed errori

UAS ignora le etichette (struttura), LAS le include (ruoli). Errori tipici: PP attachment,
coordinazioni, verbi modali/ausiliari, punteggiatura. Nel progetto 3.A bastano pattern
ad alta precisione (nsubj/obj/det) estratti con spaCy/Stanza/Tint.


Related: notes.md, flashcards.md. Libri: JM cap. dependency parsing.