Algoritmo di Clark, Manning

La proposta di Clark,Manning [14] `e a nostra conoscenza la prima imple- mentazione di un solver per la coreference basato su reti neurali deep. Uno degli principali obiettivi di tale proposta `e quello di dimostrare come non sia necessario l’utilizzo di feature numerose e complesse per costruire un sistema con prestazioni allo stato dell’arte. Tale sistema utilizza tre componenti:

• Mention-Pair Encoder: si tratta di uno strumento che fornisce una rappresentazione per ciascuna coppia di menzioni, passando informa- zioni rilevanti ad una rete feed-forward ;

• Cluster-Pair Encoder: produce rappresentazioni di cluster di men- zioni effettuando un’operazione di pooling su coppie di menzioni rispet- tivamente appartenenti ai due cluster;

• Mention-Ranking Model: fornisce un punteggio per ciascuna coppia di menzioni utilizzando queste ultime come input di una rete neurale. I parametri cos`ı ottenuti vengono utilizzati per inizializzare il cluster- pair encoding e per effettuare pruning su quali cluster considerare per un merge.

Il sistema fornisce al mention-pair encoder una serie di feature, nelle quali si utilizza la media fra word embedding per fornire la rappresentazione di una sequenza di parole, oltre ad vettori one-hot binned che codificano le distanze fra parole. Le feature utilizzate sono:

• Embedding Features: i word embedding della prima e dell’ultima parola della menzione, del nodo padre in un albero di parsing a dipen- denze, della head word, due parole precedenti e due parole successive;

• Additional Mention Features: Il tipo della menzione (pronome, no- minale, nome proprio o lista), la posizione della menzione (indice della menzione diviso il numero di menzioni nel documento), se la menzione `e contenuta in un’altra menzione, il numero di parole della menzione; • Document genre: il genere del documento considerato;

• Distance Features: la distanza fra le due menzioni in termini di frasi; • Speaker Features: se le due menzioni hanno lo stesso speaker e se una delle due menzioni `e lo speaker dell’altra frase secondo le regole di string matching proposte da Raghunathan et al [51];

• String Matching Features: head match, string match esatto e string match parziale.

Tali feature vengono poi concatenati in un vettore h0, che costituisce l’input

per il mention pair encoder. Tale rete utilizza poi tre hidden layer di unit`a ReLU completamente connesse al livello precedente:

hi(a, m) = max(0, Wihi−1(a, m) + bi) (2.38)

Dove Wi `e la matrice dei pesi del livello i-esimo della rete, mentre bi `e

il vettore di bias. L’output dell’ultimo livello nascosto che rappresenta la coppia di menzioni (a, m): rm(a, m) = h3(a, m).

La seconda componente del sistema, il cluster-pair encoder, effettua ope- razioni di pooling su due cluster di menzioni ci = mi1, mi2, . . . , mi|ci| e cj =

mj₁, mj₂, . . . , mj_|c

j|. Si utilizza dunque l’insieme di rappresentazioni di tutte le

coppie di menzioni dei due cluster ottenute tramite mention-pair encoder : Rm(ci, cj) = [rm(mi1, m j 1), rm(mi1, m j 2), . . . , rm(mi|ci|, m j |cj|)] (2.39)

Per ottenere la rappresentazione dei due cluster rc(ci, cj) A tali coppie di

2.2 Coreference resolution tramite Reti Neurali Deep 81 concatenando poi i due risultati:

rc(ci, cj)k =    max(Rm(ci, cj)k) per 0 ≤ k < d avg(Rm(ci, cj)k−d) per d ≤ k < 2d (2.40) Viene infine utilizzato un classificatore lineare sulle rappresentazioni del mention- pair encoder per effettuare il mention-ranking:

sm(a, m) = Wmrm(a, m) + bm (2.41)

Dove Wm `e la matrice dei pesi della rete e bm `e il vettore di bias.

Il mention-ranking model utilizza una funzione di loss proposta da Wi- seman et al [64] e detta slack rescaled max margin training objective. Sup- ponendo che il training set sia composto dalle menzioni m1, m2, . . . , mn, si

denota con A(mi) l’insieme di candidati ad essere antecedenti della menzione

mi. Con tm si indica l’insieme dei candidati che sono antecedenti di mi, op-

pure {N A} se mi non ha antecedenti. L’antecedente con il miglior punteggio

stimato dalla rete viene indicato con ˆti ed `e definito come:

ˆ

ti = arg max t∈T (mi)

sm(t, mi) (2.42)

La loss `e dunque data da: L = N X i=1 max a∈A(mi) ∆(a, mi)(1 + sm(a, mi) − sm(ˆt, mi)) (2.43)

una taratura dei pesi pi`u granulare: ∆(a, mi) =                αF N se a = N A ∧ T (mi) 6= N A αF A se a 6= N A ∧ T (mi) = N A αW L se a 6= N A ∧ a /∈ T (mi) 0 se a ∈ T (mi) (2.44) dove i tre pesi non nulli corrispondono rispettivamente ai casi di false new, false anaphoric, wrong link.

Oltre ai modelli precedenti, che operano su coppie di menzioni, `e utile utilizzare un cluster-ranking model sc, che fornisca uno score a due cluster in

modo da comprendere quali siano valutati pi`u compatibili dalla rete. Esso `e strutturato in maniera del tutto analoga a quanto visto per il mention-ranking model.

sc(ci, cj) = Wcrc(ci, cj) + bc (2.45)

Viene infine utilizzata un’ulteriore rete per fornire una misura della pro- babilit`a che una menzione abbia un antecedente, sN A, definita nel modo

seguente:

sN A(m) = WN Arm(N A, m) + bN A (2.46)

Utilizzando il ranking dei cluster ed il ranking delle menzioni con antece- denti, l’algoritmo seleziona per ciascuna menzione l’azione da compiere (non unirla ad alcun cluster oppure cercare un cluster a cui unirla fra i candidati). Per selezionare il cluster fra i candidati viene utilizzato un algoritmo easy- first, nel quale si utilizza il mention-ranking model per valutare sempre le scelte pi`u semplici per prime. Vengono inoltre ignorati i candidati con score troppo bassi, riducendo la complessit`a dell’algoritmo.

Nella fase di training viene infine utilizzato un algoritmo del tipo learning- to-search, in quanto lo stato del sistema viene variato con ciascuna iterazione dell’algoritmo.

2.2 Coreference resolution tramite Reti Neurali Deep 83 neurali deep, che `e in grado di ottenere risultati stato dell’arte utilizzando poche e semplici feature. Tramite questo algoritmo vengono dimostrate le potenzialit`a delle reti neurali deep per il task della coreference.