Graph-based Clustering Algorithms for Word Sense Induction

This dissertation is about Word Sense Induction (WSI), a branch of Natural Language Processing concerned with the automated, unsupervised detection and listing of the possible senses that a word can assume relative to the different contexts in which it appears. To this end, no external resources like dictionaries or ontologies are used. Among the many existing approaches to WSI, we focus specifically on modelling the context of a word through a graph and on running a clustering algorithm on it: the resulting clusters are interpreted as implicitly describing the possible senses of the word. Fundamental notions of WSI, basic concepts and some WSI approaches selected from literature are presented and examined in the first part of this work. In the second part, we introduce our threefold contribution. Firstly, we define and explore a weighted (together with an unweighted) Jaccard distance, i.e. a distance on the nodes of a positively weighted undirected graph which we use to obtain second-order relations from the first-order ones modelled by the graph (e.g. co-occurrences). Moreover, we define the related notion of gangplank edge, a separator edge with weight greater than the mean weights of the edges incident to either of its two ends, and finally a new synthetic interpretation of the curvature on a graph, seen as the difference between weighted and unweighted Jaccard distances between node couples. Our Jaccard distance is at the basis of the second contribution: three novel graph-based clustering algorithms expressly created for the task of WSI, respectively the gangplank clustering algorithm, an aggregative clustering algorithm and a curvature-based clustering algorithm. The third contribution is a novel evaluation framework for graph-based clustering algorithms for WSI, consisting of two word graph data sets (one for co-occurrences and one for semantic similarities) and a new ad hoc evaluation measure built around pseudowords. A pseudoword is the artificial conflation of two existing words, used as an ambiguous word whose (pseudo)senses are perfectly known. This enables to evaluate WSI algorithms on an easily creatable and expandable data set. We carry out a pseudoword-based evaluation for a number of graph-based clustering algorithms, including our three proposed systems. The investigation of how the parameters of a pseudoword affect an algorithm's outcomes, the comparison of the scores obtained by different evaluation metrics together with the detection of their biases, the size of the clusterings and the trends put in evidence by the hyperclustering step, the influence of the type of a word graph (based on semantic similarities or co-occurrences) on the output of an algorithm - all these factors, preceded by the comprehensive description of the task and the definition of novel concepts and instruments to tackle it, concur to give a deeper insight into the functioning and pitfalls of graph-based Word Sense Induction. We highlight and isolate the elements that determine how the results of an algorithm look like, discuss their properties and behaviours in relation to the word graph features and establish the pro and contra of each algorithm. Our analysis provides an experimental compass that helps pinpoint the right characteristics required by a clustering algorithm for the task of Word Sense Induction, and that helps orient the construction of a word graph. In particular, we have put in evidence the different syntagmatic versus paradigmatic contrast inherent to word graphs based on co-occurrences and semantic similarities.

La presente tesi si occupa dell’induzione dei significati delle parole (ISP o word sense induction - WSI), una branca dell’elaborazione dei linguaggi naturali il cui scopo è individuare ed elencare automaticamente e in modo non supervisionato i possibili significati o sensi che un termine può assumere relativamente ai differenti contesti in cui esso viene impiegato, senza ricorrere a risorse esterne quali dizionari od ontologie. Fra i vari approcci alla ISP esistenti, ci siamo concentrati in particolare su quelli che modellano il contesto di una parola tramite un grafo, su cui viene fatto operare un algoritmo per partizionarlo: la partizione che ne risulta ha come interpretazione l’implicita descrizione dei possibili sensi di quella parola. Le nozioni fondamentali dell’ISP, alcuni concetti base e approcci alla ISP scelti fra la letteratura del campo vengono presentati e analizzati nella prima parte del lavoro. Nella seconda parte introduciamo il nostro triplice contributo. Per prima cosa definiamo ed esploriamo la distanza di Jaccard pesata (assieme a una sua versione non pesata), cioè una distanza sui nodi di un grafo non orientato con pesi positivi, che usiamo per ottenere relazioni di secondo ordine dalle relazioni di primo ordine eventualmente modellate dal grafo (p.e. cooccorrenze). Inoltre, definiamo la nozione correlata di “arco passerella”, un arco “separatore” il cui peso è superiore alla media dei pesi sugli archi uscenti da una delle sue due estremità, e definiamo anche una nuova interpretazione sintetica delle curvatura di un grafo, vista come la differenza delle distanze di Jaccard pesata e non pesata sugli archi. La distanza di Jaccard da noi definita è alla base del nostro secondo contributo: tre nuovi algoritmi di clustering su grafo espressamente creati per l’ISP, rispettivamente l’algoritmo di clustering per passerelle, un algoritmo di clustering aggregativo e uno basato sulla curvatura. Il terzo contributo di questa tesi è un nuovo sistema di valutazione per algoritmi di clustering su grafo per l’ISP, il quale consiste di due collezioni di grafi (una per le cooccorrenze e una per le similarità semantiche) e di una nuova misura di valutazione ad hoc, entrambi sviluppati attorno all’idea di pseudoparola. Una pseudoparola è la fusione artificiale di due parole esistenti, usata come una nuova parola ambigua i cui (pseudo)significati sono perfettamente conosciuti. Tale sistema permette di valutare algoritmi per l’ISP su dati facilmente creabili ed espandibili. Svolgiamo inoltre una valutazione basata sulle pseudoparole per vari algoritmi di clustering su grafo, inclusi i tre da noi proposti. L'indagine di come i parametri di una pseudoparola influiscono sul risultato di un algoritmo, il confronto dei punteggi ottenuti da diverse metriche di valutazione, assieme all'individuazione dei loro bias, la grandezza dei clustering e le tendenze evidenziate dall'iperclustering, l'influenza del tipo di un grafo di parole (basato su similarità sintattiche o cooccorrenze) sul prodotto di un algoritmo – tutti questi fattori, preceduti da un'esauriente descrizione degli obiettivi e dalla definizione di nuovi concetti e strumenti per affrontarli, concorrono a dare una migliore comprensione del funzionamento e delle insidie dell'ISP su grafo. Sottolineiamo e isoliamo gli elementi che determinano l'aspetto dei risultati di un algoritmo, ne discutiamo le proprietà e i comportamenti in relazione alle caratteristiche del grafo di parole e stabiliamo i pro e i contro di ogni algoritmo. La nostra analisi fornisce una bussola sperimentale che aiuta a individuare con precisione le caratteristiche richieste da un algoritmo nell'ambito dell'ISP e a orientare la costruzione di un grafo di parole. In particolare, abbiamo evidenziato il contrasto fra paradigma e sintagma inerente ai grafi di parole basati su similarità semantiche e cooccorrenze.