# Entity linking

Nell'ambito dell'elaborazione del linguaggio naturale, l'entity linking, noto anche come named entity linking (NEL), named entity disambiguation (NED), named entity recognition e disambiguation (NERD) o named entity normalization (NEN) è il compito di assegnare un'identità univoca a entità (come personaggi famosi, luoghi o aziende) menzionate in un testo. Ad esempio, data la frase "Washington è la capitale degli Stati Uniti", l'idea è di determinare che "Washington" si riferisce alla città di Washington e non a George Washington o qualsiasi altra entità che potrebbe essere indicata come "Washington". L'entity linking è diverso dal named entity recognition (NER) in quanto il NER identifica l'occorrenza di un'entità denominata nel testo, ma non identifica l'entità specifica (vedere Differenze da altre tecniche).

## Introduzione

Nell'entity linking, le parole di interesse (nomi di persone, ubicazioni e aziende) sono collegate da un testo di input a entità univoche contenute in una knowledge base di destinazione. Le parole di interesse sono chiamate named entity (NE), menzioni o forme di superficie. La knowledge base di destinazione dipende dall'applicazione prevista, ma per gli algoritmi di entity linking pensati per funzionare su testo di contenuto generico è comune utilizzare knowledge base derivate da Wikipedia (come Wikidata o DBpedia). In questo caso, ogni singola pagina di Wikipedia è considerata un'entità separata. Le tecniche di entity linking che associano le named entity ad entità di Wikipedia prendono anche il nome di wikificazione.
Considerando nuovamente la frase "Washington è la capitale degli Stati Uniti", l'output atteso di un algoritmo di entity linking sarà Washington e Stati Uniti d'America. Questi URL (Uniform Resource Locators) possono essere utilizzati come URI (Uniform Resource Identifier) univoci per le entità nella knowledge base. L'utilizzo di una diversa knowledge base restituirà diversi URI, ma per gran parte delle knowledge base costruite a partire da Wikipedia esistono corrispondenze univoche tra gli URI delle singole knowledge base, in modo tale che siano interscambiabili.
Nella maggior parte dei casi, le knowledge base sono costruite manualmente, ma in applicazioni in cui sono disponibili corpus di testo di grandi dimensioni, la knowledge base può essere dedotta automaticamente a partire dal testo disponibile.

### Applicazioni

L'entity linking è fondamentale in molti ambiti, come l'analisi del testo, i sistemi di raccomandazione, la ricerca semantica e i chatbot. Tutti questi campi beneficiano di rappresentazioni di alto livello del testo, in cui i concetti rilevanti per l'applicazione sono separati dal testo grezzo e da altri dati non significativi.
Ad esempio, un'attività comune eseguita dai motori di ricerca consiste nel trovare documenti simili a uno dato come input o per trovare ulteriori informazioni sulle persone menzionate in esso. Si consideri una frase contenente l'espressione "la capitale della Francia": senza entity linking, il motore di ricerca che esamina il contenuto dei documenti non sarebbe in grado di recuperare direttamente i documenti contenenti la parola "Parigi", portando a cosiddetti falsi negativi (FN). Ancor peggio, il motore di ricerca potrebbe produrre corrispondenze spurie (o falsi positivi (FP)), come il recupero di documenti che si riferiscono a "Francia" nel senso di nazione.
Esistono molti approcci ortogonali all'entity linking per recuperare documenti simili a un documento di input. Ad esempio, l'utilizzo di latent semantic analysis (LSA) o il confronto di embedding di documenti ottenuti mediante doc2vec. Tuttavia, queste tecniche non consentono lo stesso controllo granulare che viene fornito da tecniche di entity linking, in quanto vengono restituiti altri documenti invece di creare rappresentazioni di alto livello del testo originale. Ad esempio, ottenere informazioni schematiche su "Parigi", come presentato dagli Infobox di Wikipedia, risulta meno semplice, o persino infattibile, a seconda della complessità della query..
Inoltre, l'entity linking è stato utilizzato per migliorare le prestazioni dei sistemi di recupero delle informazioni e per migliorare le prestazioni di ricerca nelle biblioteche digitali. L'entity linking è anche un input chiave per la ricerca semantica.

### Difficoltà nell'entity linking

Un sistema di entity linking deve poter gestire una serie di difficoltà per poter essere adeguato ad applicazioni reali. Alcune di queste problematiche sono intrinseche all'entity linking stesso, come l'ambiguità del testo, mentre altre, come la scalabilità e il tempo di esecuzione, diventano rilevanti quando si considera l'utilizzo di tali sistemi in applicazioni reali.
* Variazioni dei nomi: la stessa entità potrebbe venire espressa in molti modi diversi. Le variazioni dei nomi possono essere causate da abbreviazioni (New York, NY), alias (New York, Big Apple), o varianti di spelling ed errori (New yokr).
* Ambiguità: la stessa menzione può spesso riferirsi a molte entità diverse, a seconda del contesto, poiché molti nomi tendono ad essere polisemici (cioè hanno significati multipli). La parola Washington, tra le altre cose, potrebbe riferirsi alla capitale statunitense o a George Washington. In alcuni casi (come nell'espressione la capitale degli Stati Uniti), non vi è alcuna somiglianza testuale tra il testo di partenza e l'entità che si desidera individuare (Washington).
* Assenza delle entità: a volte, alcune named entity potrebbero non avere una corrispondente entità nella knowledge base di destinazione. Ciò potrebbe accadere quando si ha a che fare con entità molto specifiche o insolite o quando si elaborano documenti su eventi recenti, in cui potrebbero esserci menzioni di persone o eventi che non hanno ancora un'entità corrispondente nella knowledge base. Un'altra situazione comune in cui è comune avere entità mancanti è quando si utilizzano knowledge base facenti riferimento a un dominio specifico (ad esempio, una knowledge base di biologia o un database di film). In tutti questi casi, l'algoritmo di entity linking dovrebbe restituire un collegamento nullo, cioè NIL. Capire quando restituire una previsione NIL non è semplice e sono stati proposti molti approcci diversi; ad esempio, limitando un qualche valore di confidenza nell'algoritmo di entity linking, o aggiungendo un'entità NIL aggiuntiva alla knowledge base, che viene trattata allo stesso modo delle altre entità. Inoltre, in alcuni casi fornire una stima errata, ma correlata al valore esatto, potrebbe essere migliore di non fornire alcun risultato, dal punto di vista di un utente finale.
* Scalabilità e velocità: è auspicabile che un algoritmo di entity linking fornisca risultati in tempi ragionevoli e spesso in tempo reale. Questo requisito è fondamentale per motori di ricerca e chatbot. Garantire tempi di esecuzione ridotti può essere difficile quando si utilizzano knowledge base o documenti di grandi dimensioni. Ad esempio, Wikipedia contiene circa 9 milioni di entità e oltre 170 milioni di relazioni tra loro.
* Evoluzione dell'informazione: un algoritmo di entity linking dovrebbe anche occuparsi delle informazioni in evoluzione e integrare facilmente gli aggiornamenti che possono essere fatti nella corrispondente knowledge base. Il problema dell'evoluzione delle informazioni è a volte collegato al problema delle entità mancanti, ad esempio quando si elaborano articoli di notizie recenti in cui ci sono menzioni di eventi che non hanno una voce corrispondente nella knowledge base a causa della loro novità.
* Lingue multiple: un algoritmo di entity linking può supportare query eseguite in più lingue. Idealmente, l'accuratezza del sistema non dovrebbe essere influenzata dalla lingua di input e le entità nella knowledge base dovrebbero essere le stesse in ogni lingua supportata.

### Differenze da altre tecniche

L'entity linking è anche noto come named entity disambiguation (NED) ed è profondamente collegato a wikificazione e a record linkage. Le definizioni sono spesso sottili e variano leggermente tra i diversi autori: Alhelbawy et al. considerano l'entity linking come una versione più ampia del NED, in quanto il NED assume che l'entità che corrisponde a una named entity sia contenuta nella knowledge base. I sistemi di entity linking, invece, possono trattare casi in cui nessuna entità presente nella knowledge base di riferimento sia adatta a essere collegata con la named entity considerata. Altri autori non fanno tale distinzione e usano le due definizioni in modo equivalente.
* La wikificazione è il compito di collegare le menzioni testuali alle entità di Wikipedia (generalmente, limitando l'ambito alla Wikipedia in inglese in caso di wikificazione multilingue).
* Il record linkage (RL) è considerato un campo più ampio rispetto all'entity linking e consiste nel trovare i documenti, attraverso set di dati multipli e spesso eterogenei, che si riferiscono alla stessa entità. Il record linkage è un componente chiave per digitalizzare gli archivi e per unire più knowledge base.
* Il named entity recognition (NER) individua e classifica le named entity contenute in un testo non strutturato in categorie predefinite come nomi, organizzazioni, luoghi geografici e altro. Ad esempio, la seguente frase:
«Parigi è la capitale della Francia.»
    sarebbe elaborata da un sistema NER in modo tale da ottenere il seguente risultato:
«[Parigi]$_{Città}$ è la capitale della [Francia]$_{Paese}$.»
    Il named entity recognition è solitamente una fase di pre-elaborazione negli algoritmi di entity linking, in quanto può essere utile sapere in anticipo quali parole debbano essere collegate alle entità della knowledge base.
* La coreference resolution stabilisce se più parole in un testo si riferiscono alla stessa entità. Può essere utile, ad esempio, per capire la parola a cui si riferisce un pronome. Si consideri il seguente esempio:
«Parigi è la capitale della Francia. Questa città è anche la più grande della Francia.»
    In questo esempio, un algoritmo di coreference resolution identificherebbe che la parola città si riferisce a Parigi, e non alla Francia o ad un'altra entità. Una distinzione notevole rispetto a entity linking è che coreference resolution non assegna nessuna identità univoca alle parole del testo, ma semplicemente stabilisce se si riferiscono alla stessa entità o meno.

## Tecniche di entity linking

L'entity linking è stato oggetto di grandi studi sia nell'industria che nel mondo accademico per l'ultimo decennio. Tuttavia, ad oggi gran parte delle difficoltà esistenti sono ancora irrisolte, e sono stati proposti innumerevoli algoritmi di entity linking, con punti di forza e punti deboli molto diversi.
In generale, le moderne tecniche di entity linking possono essere suddivise in due categorie:
* Approcci basati sull'analisi di testo, che si avvalgono di funzionalità testuali estratte da corpora di testo di grandi dimensioni (ad esempio Term frequency - Inverse document frequency (Tf-Idf), probabilità di co-occorrenza delle parole, ecc...).
* Approcci basati sull'analisi di grafi, che sfruttano la struttura dei knowledge graph per rappresentare il contesto e la relazioni tra entità.
Spesso i sistemi di entity linking non possono essere categorizzati esattamente in una di queste categorie, in quanto fanno uso di knowledge graph che sono stati arricchiti con informazioni aggiuntive estratte da un testo, ad esempio, dai corpus testuali impiegati per costruire i knowledge graph stessi.

### Approcci basati sull'analisi di testo

Il fondamentale lavoro di Cucerzan nel 2007 propone uno delle prime tecniche di entity linking che sono comparse in letteratura. Nel suo lavoro, Cucerzan si è occupato di wikificazione, il collegamento di menzioni testuali a pagine di Wikipedia. Questo algoritmo categorizza le pagine di Wikipedia in entità, pagine di disambiguazione o elenco di altre pagine, e le utilizza per assegnare categorie a ciascuna entità. L'insieme di entità presenti in ogni pagina entità viene utilizzato per costruire il contesto di ciascuna entità. La fase finale di collegamento delle entità è una disambiguazione collettiva eseguita confrontando vettori binari ottenuti da caratteristiche estratte manualmente dai dati e dal contesto di ciascuna entità. Il sistema di entity linking di Cucerzan è ancora utilizzato come punti di partenza per molti lavori più recenti.
Il lavoro di Rao et al. è altamente conosciuto nell'ambito dell'entity linking. Gli autori propongono un algoritmo in due fasi per collegare named entities ad entità in una knowledge base di destinazione. Innanzitutto, viene scelto per ciascuna named entity un insieme di entità candidate utilizzando somiglianza testuale, acronimi e alias noti di ogni entità. In seguito, il miglior candidato viene scelto con una Support Vector Machine (SVM) che utilizza caratteristiche di tipo linguistico.
Algoritmi più recenti, come quello proposto da Tsai et al., impiegano embeddings testuali ottenuti con un modello skip-gram e possono essere applicati a qualsiasi lingua purché sia disponibile un corpus testuale di dimensioni sufficienti alla creazione embeddings di parole. Analogamente alla maggior parte delle tecniche di entity linking, questo algoritmo è diviso in due fasi, con una selezione iniziale delle entità candidate e un SVM con ranking lineare come secondo passo.
In letteratura sono stati tentati molteplici approcci per affrontare il problema dell'ambiguità dell'entità. Nel lavoro di Milne e Witten, viene impiegato l'apprendimento supervisionato utilizzando i testi di ancoraggio dei link interni a Wikipedia come dati di addestramento. Altri approcci hanno raccolto dati di addestramento basati su sinonimi non ambigui. Kulkarni et al. hanno sfruttato il fatto che i documenti con simile argomento si riferiscono a entità appartenenti a classi fortemente correlate.

### Approcci basati sull'analisi di grafi

Le moderne tecniche di entity linking non si limitano ad analizzare informazioni ottenute da documenti di input o corpora di testi, ma impiegano knowledge graph creati da basi di conoscenza come Wikipedia. Questi algoritmi estraggono complesse informazioni a partire dalla topologia del knowledge graph o sfruttano connessioni multi-step tra entità, che sarebbero invisibili da una semplice analisi del testo. Inoltre, realizzare algoritmi di entity linking multilingue basati su natural language processing (NLP) è intrinsecamente difficile, in quanto richiede sia corpus di testo di grandi dimensioni, spesso assenti per molte lingue, sia regole grammaticali generate manualmente, che possono variare enormemente tra una lingua e l'altra. Han et al. proporre la creazione di un grafo di disambiguazione (un sottografo della knowledge base che contiene solamente le entità candidate). Questo grafo viene utilizzato per una procedura di classificazione puramente collettiva che trova il miglior link per ciascuna menzione testuale.
Un altro famoso algoritmo di entity linking è AIDA, che utilizza una serie di complessi algoritmi basati grafi e un algoritmo greedy che identifica le citazioni coerenti su un sottografo denso ottenuto da entità candidate, considerando anche le somiglianze del contesto di ciascuna entità e informazioni aggiuntive associate a ciascun vertice del grafo per eseguire la disambiguazione collettiva.
Il termine graph ranking (o vertex ranking) indica algoritmi come PageRank e HITS, il cui obiettivo è assegnare a ciascun vertice di un grafo un punteggio che rappresenti la sua importanza all'interno del grafo. L'algoritmo di entity linking presentato in Alhelbawy et al. utilizza PageRank per eseguire il collegamento collettivo di entità su un grafo di disambiguazione, e capire quali entità hanno maggiore coerenza tra di loro e rappresentano un collegamento migliore.