Entity linking

il compito di assegnare un'identità univoca a entità menzionate in un testo

Nell'ambito dell'elaborazione del linguaggio naturale, l'entity linking, noto anche come named entity linking (NEL),[1] named entity disambiguation (NED), named entity recognition e disambiguation (NERD) o named entity normalization (NEN)[2] è 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).

Nell'entity linking, ciascuna named entity è collegata ad un identificatore univoco. Spesso, questo identificatore è nua pagina di Wikipedia.

IntroduzioneModifica

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).[2][3] 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.[4]

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 corrisponenze univoche tra gli URI delle singole knowledge base, in modo tale che siano interscambiabili.[5]

Nella maggior parte dei casi, le knowledge base sono costruite manualmente[6], 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.[7]

ApplicazioniModifica

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.[8][9]

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..[10]

Inoltre, l'entity linking è stato utilizzato per migliorare le prestazioni dei sistemi di recupero delle informazioni[2] e per migliorare le prestazioni di ricerca nelle biblioteche digitali.[11] L'entity linking è anche un input chiave per la ricerca semantica.[12]

Difficoltà nell'entity linkingModifica

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,[13] 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.[13]
  • Scalabilità e velocità: è auspicabile che un algoritmo di entity linking fornisca risultati in tempi ragionevoli e spesso in tempo reale.[14] 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 corrisponente 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à.[15]
  • 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.[16]

Differenze da altre tecnicheModifica

L'entity linking è anche noto come named entity disambiguation (NED) ed è profondamente collegato a wikificazione e a record linkage.[17] Le definizioni sono spesso sottili e variano leggermente tra i diversi autori: Alhelbawy et al.[18] 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.[19][20]

  • 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à.[11] Il record linkage è un componente chiave per digitalizzare gli archivi e per unire più knowledge base.[11]
  • 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 linkingModifica

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.[21]

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...).[22][13]
  • Approcci basati sull'analisi di grafi, che sfruttano la struttura dei knowledge graph per rappresentare il contesto e la relazioni tra entità.[11][23]

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.[19][20]

 
La maggior parte degli algoritmi di entity linking sono costituiti da una fase di named entity recognition, seguita da una fase in cui ciascuna named entity è collegata ad un corrisponendente identificatore univoco (qui, una pagina di Wikipedia). Quest'ultima operazione viene spesso eseguita creando un piccolo insieme di entità candidate per ciascuna named entity e selezionando il candidato più promettente rispetto a una data metrica.

Approcci basati sull'analisi di testoModifica

Il fondamentale lavoro di Cucerzan nel 2007 propone uno delle prime tecniche di entity linking che sono comparse in letteratura.[22] Nel suo lavoro, Cucerzan si è occpuato 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.[24]

Il lavoro di Rao et al. è altamente consciuto nell'ambito dell'entity linking.[13] 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.,[17] 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.[25] Altri approcci hanno raccolto dati di addestramento basati su sinonimi non ambigui.[26] Kulkarni et al. hanno sfruttato il fatto che i documenti con simile argomento si riferiscono a entità appartenenti a classi fortemente correlate.[24]

Approcci basati sull'analisi di grafiModifica

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).[11] 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.[23]

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.[27]

NoteModifica

  1. ^ Ben Hachey, Will Radford, Joel Nothman, Matthew Honnibal e James R. Curran, Artificial Intelligence, Wikipedia and Semi-Structured ResourcesEvaluating Entity Linking with Wikipedia, in Artificial Intelligence, vol. 194, 1º gennaio 2013, pp. 130–150, DOI:10.1016/j.artint.2012.04.005.
  2. ^ a b c M. A. Khalid, V. Jijkoun and M. de Rijke (2008). The impact of named entity normalization on information retrieval for question answering. Proc. ECIR.
  3. ^ Xianpei Han, Le Sun and Jun Zhao (2011). Collective entity linking in web text: a graph-based method. Proc. SIGIR.
  4. ^ Rada Mihalcea and Andras Csomai (2007)Wikify! Linking Documents to Encyclopedic Knowledge. Proc. CIKM.
  5. ^ Wikipedia Links, su wiki.dbpedia.org.
  6. ^ Wikidata
  7. ^ Aaron M. Cohen (2005). Unsupervised gene/protein named entity normalization using automatically extracted dictionaries. Proc. ACL-ISMB Workshop on Linking Biological Literature, Ontologies and Databases: Mining Biological Semantics, pp. 17–24.
  8. ^ Bill Slawski, How Google Uses Named Entity Disambiguation for Entities with the Same Names, su seobythesea.com.
  9. ^ (EN) Ming Zhou, Weifeng Lv, Pengjie Ren, Furu Wei e Chuanqi Tan, Entity Linking for Queries by Searching Wikipedia Sentences, pp. 68–77, DOI:10.18653/v1/D17-1007.
  10. ^ Quoc Le e Tomas Mikolov, Distributed Representations of Sentences and Documents, in Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, JMLR.org, 2014, pp. II–1188–II–1196.
  11. ^ a b c d e Xianpei Han, Le Sun e Jun Zhao, Collective Entity Linking in Web Text: A Graph-based Method, in Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 2011, pp. 765–774, DOI:10.1145/2009916.2010019.
  12. ^ STICS
  13. ^ a b c d (EN) Delip Rao, Paul McNamee e Mark Dredze, Entity Linking: Finding Extracted Entities in a Knowledge Base, in Multi-source, Multilingual Information Extraction and Summarization, Springer Berlin Heidelberg, 2013, pp. 93–115, DOI:10.1007/978-3-642-28569-1_5.
  14. ^ Alberto Parravicini, Rhicheek Patra, Davide B. Bartolini e Marco D. Santambrogio, Fast and Accurate Entity Linking via Graph Embedding, in Proceedings of the 2Nd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), ACM, 2019, pp. 10:1–10:9, DOI:10.1145/3327964.3328499.
  15. ^ Johannes Hoffart, Yasemin Altun e Gerhard Weikum, Discovering Emerging Entities with Ambiguous Names, in Proceedings of the 23rd International Conference on World Wide Web, ACM, 2014, pp. 385–396, DOI:10.1145/2566486.2568003.
  16. ^ (EN) David S. Doermann, Douglas W. Oard, Dawn J. Lawrie, James Mayfield e Paul McNamee, Cross-Language Entity Linking, in undefined, 2011.
  17. ^ a b Chen-Tse Tsai e Dan Roth, Cross-lingual Wikification Using Multilingual Embeddings, Proceedings of NAACL-HLT 2016, 2016, pp. 589–598.
  18. ^ Ayman Alhelbawy e Robert Gaizauskas, Collective Named Entity Disambiguation using Graph Ranking and Clique Partitioning Approaches, Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, Dublin City University and Association for Computational Linguistics, pp. 1544–1555.
  19. ^ a b Stefan Zwicklbauer, Christin Seifert e Michael Granitzer, Robust and Collective Entity Disambiguation Through Semantic Embeddings, in Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 2016, pp. 425–434, DOI:10.1145/2911451.2911535.
  20. ^ a b Ben Hachey, Will Radford, Joel Nothman, Matthew Honnibal e James R. Curran, Evaluating Entity Linking with Wikipedia, in Artif. Intell., vol. 194, 2013, pp. 130–150, DOI:10.1016/j.artint.2012.04.005, ISSN 0004-3702 (WC · ACNP).
  21. ^ Heng Ji, Joel Nothman, Ben Hachey e Radu Florian, Overview of TAC-KBP2015 Tri-lingual Entity Discovery and Linking, in TAC, 2015.
  22. ^ a b (EN) Silviu Cucerzan, Large-Scale Named Entity Disambiguation Based on Wikipedia Data, Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pp. 708–716.
  23. ^ a b (EN) Gerhard Weikum, Stefan Thater, Bilyana Taneva, Marc Spaniol, Manfred Pinkal, Hagen Fürstenau, Ilaria Bordino, Mohamed Amir Yosef e Johannes Hoffart, Robust Disambiguation of Named Entities in Text, in Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, 2011, pp. 782–792.
  24. ^ a b Sayali Kulkarni, Amit Singh, Ganesh Ramakrishnan e Soumen Chakrabarti, Collective annotation of Wikipedia entities in web text, Proc. 15th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD), 2009, DOI:10.1145/1557019.1557073, ISBN 978-1-60558-495-9.
  25. ^ David Milne and Ian H. Witten (2008). Learning to link with Wikipedia. Proc. CIKM.
  26. ^ Wei Zhang, Jian Su e Chew Lim Tan, Entity Linking Leveraging Automatically Generated Annotation, in Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), 2010.
  27. ^ (EN) Robert Gaizauskas e Ayman Alhelbawy, Collective Named Entity Disambiguation using Graph Ranking and Clique Partitioning Approaches, in Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, 2014, pp. 1544–1555.

Voci correlateModifica