La struttura complessa degli spazi semantici: un approccio guidato dalla network science

(1)

Dipartimento di Filologia, Letteratura e Linguistica Corso di Laurea in Informatica Umanistica

La struttura complessa degli spazi semantici

Un approccio guidato dalla Network Science

Relatore:

Prof. Giulio Rossetti

Candidato:

Salvatore Citraro

Sessione primaverile

Anno Accademico 2017/2018

(2)

Indice

1 Verso una struttura del significato 4

1.1 Sistemi complessi e il lessico mentale . . . 4

1.2 Nozioni preliminari sui grafi . . . 8

1.3 Modelli di reti complesse . . . 11

1.3.1 Modello di Erdös-Rényi . . . 11 1.3.2 Modello di Watts-Strogatz . . . 13 1.3.3 Modello di Barabási-Albert . . . 15 1.4 Community discovery . . . 17 1.4.1 Definizioni di comunità . . . 17 1.4.2 Valutare i partizionamenti . . . 20

1.5 Lo studio del significato se l’unit`a minima di analisi `e… . . . 21

1.5.1 …la frase . . . 22

1.5.2 …la parola . . . 22

1.5.3 …il contesto . . . 24

1.6 Verso una classificazione delle reti semantiche complesse . . . 26

1.7 Modelli di reti semantiche complesse . . . 28

(3)

1.7.2 Modello di ST-Utsumi . . . 30

2 Data collection: estrazione di reti da uno spazio semantico 33 2.1 Corpora e loro preprocessing . . . 33

2.2 Modello del linguaggio . . . 35

2.3 Estrazione delle reti . . . 38

3 Network analysis 42 3.1 Invarianza di scala, propriet`a small-world, assortativit`a . . . 42

3.2 Interpretazioni . . . 46

3.2.1 Cosa rappresentano i gradi . . . 46

3.2.2 Le variabili epistemologiche: corpus, modello del linguaggio, me-todo di estrazione . . . 50

4 Community discovery: campi contestuali 52 4.1 Un primo approccio: Infomap, Louvain, Leiden . . . 55

4.1.1 Infomap . . . 55

4.1.2 Louvain . . . 57

4.1.3 Leiden . . . 59

4.1.4 Interpretazioni: topic lessicalmente ricchi . . . 60

4.2 Un secondo approccio: Demon . . . 64

4.2.1 Interpretazioni: pi`u contesti per uno stesso dominio . . . 65

4.3 Un terzo approccio: seed-set expansion . . . 69

4.3.1 Quale ground truth? . . . 71

(4)

(5)

Sommario

It is proposed a complex network approach to the self - organization of word meaning in semantic spaces, NLP techniques capable to model theories of distributional seman-tics: words link each others if they can be substituted in the same linguistic context, shaping clusters representing semantic fields. This perspective can be used to model a mental lexicon of word similarities, supporting psycholinguistics or emerging area of research in Cognitive Science. Extracted networks are analyzed in terms of global properties and meso-scale structure: they have small-world properties and they are as-sortative by degree; probability of degree distributions follows a truncated power law. Through three community discovery methods, clusters have been identified (1) as strict semantic fields (2) as different linguistic contexts in which the same word can appear (3) as semantic fields conveyed by a single word, highlighting polysemy.

(6)

Introduzione

L’obiettivo di questo lavoro è un’analisi del comportamento emergente del significato attraverso la struttura complessa degli spazi semantici. Gli spazi semantici sono modelli del Natural Language Processing capaci di catturare una determinata proprietà del si-gnificato a partire dal contesto linguistico in cui le parole compaiono insieme nei testi. Vengono assunte, perciò, le teorie del significato proprie della semantica distribuziona-le - applicate ai metodi e al paradigma di ricerca della Network Science - per studia-re l’organizzazione di coppie di parole connesse tra loro da forti studia-relazioni di similarità semantica.

Uno spazio semantico offre la possibilità di studiare l’organizzazione del significa-to a partire da una grande quantità di dati. Le strutture emergenti saranno analizzate in termini di proprietà globali di rete e di meso-struttura. Ricordando che in uno spa-zio semantico le parole sono in realtà vettori, è necessario fare i conti con le seguenti assunzioni, riassunte poi in Figura 1:

• se un vettore `e capace di riprodurre una parola, un vettore pu`o essere rappresentato come un nodo, in modo tale da rappresentare una parola come un nodo;

• più nello specifico, se una misura di similarità geometrica tra vettori riproduce una similarità semantica tra parole, è possibile rappresentare tali similarità di

(7)

si-Figura 1: (1) Uno spazio semantico riproduce le parole come vettori. (2) Un approccio agli spazi semantici con i metodi della Network Science rappresenta i vettori come no-di. (3) Possiamo rappresentare una struttura del significato tramite lo studio degli spazi semantici?

gnificato mediante connessioni tra vettori: il risultato di questa operazione `e una rete semantica complessa, che modella una struttura del significato tra coppie di parole.

In sintesi, se gli spazi semantici rendono concreta la metafora SIGNIFICATO = SPA-ZIO DI PAROLE[1]1_{, questo lavoro intende rendere concreta la metafora SIGNIFICATO}

= RETE DI PAROLE. Solo dopo aver reso esplicite queste assunzioni, ha senso parlare -dal punto di vista della Network Science - di strutture complesse degli spazi semantici, discriminandole da altre strutture del significato che partono dall’assunzione di differenti propriet`a semantiche (i.e., connessioni) tra parole.

Perci`o, avendo a che fare con gli spazi semantici, le analisi che concluderanno ogni sezione cercheranno di valutare il peso e l’influenza delle variabili epistemologiche in gioco nell’interpretazione dei dati. Esse sono il corpus di partenza, il modello del lin-guaggio utilizzato e il metodo di estrazione della rete adottato. In generale, ci interessa valutare se le analisi ottenute saranno conformi alla sola realt`a oggettiva della rappresen-tazione vettoriale o se attraverso questa sia possibile conformarsi a una reale struttura

(8)

del significato, che dal punto di vista della Network Science si traduce in una struttu-ra a invarianza di scala con propriet`a small-world (cos`ı come emerge dalle reti eststruttu-ratte da database lessicali o da norme associative annotate da linguisti o acquisite tramite esperimenti).

Venendo al dunque, il lavoro si snoda come segue. Il Capitolo 1 è teso a focalizzare il carattere interdisciplinare della materia, dando nozioni preliminari sui grafi, sui modelli di reti complesse reali, sulle tecniche di community discovery, sulle diverse rappresen-tazioni del significato e sullo stato dell’arte delle reti semantiche complesse. Il Capitolo 2 spiega in che modo sono stati propriamente costruiti gli spazi semantici in questo lavoro e in che modo sono state estratte le reti. Il Capitolo 3 si focalizza sulle proprietà globali emergenti dalle reti, in termini di invarianza di scala, proprietà small-world e assortati-vità rispetto al grado. Il Capitolo 4 si focalizza sulla meso-struttura delle reti, analizzando i partizionamenti ottenuti a partire da differenti definizioni di comunità rappresentanti campi semantici o con l’intenzione di catturare la molteplicità di significato veicolabile da una parola. Infine, un capitolo conclusivo farà il punto della situazione, insistendo sui possibili lavori futuri emergenti da questo paradigma di ricerca e da questo approccio al significato.

(9)

Capitolo 1

Verso una struttura del significato

1.1 Sistemi complessi e il lessico mentale

Un sistema complesso è un’unità collettiva costituita da un insieme di elementi intera-genti fra loro; il suo comportamento globale è differente da quello delle singole parti che lo compongono. Un sistema complesso concretizza il principio epistemologico secondo cui il tutto non è la somma delle sue parti. Si tratta di sistemi che manifestano strutture e dinamiche non casuali; il loro comportamento è legato a specifici pattern di connessione emergenti al loro interno (che ne caratterizzano la struttura) e al modo specifico in cui avvengono gli scambi relazionali tra le parti (che ne descrivono le dinamiche).

Applicato al dominio che intendiamo studiare, cominciamo col dire che l’approccio al linguaggio come sistema complesso `e giovane e non offre ancora solidit`a metodologiche[2]1_.

1_{First of all, it must be stressed that complex networks are far from being a mature linguistic methodology}

[…]. Particular results obtained with linguistic networks might be an artifact of the network models rather than faithful indicators of the phenomenon in question. Problems of this type may arise with any research method, especially complex networks considering their only recent application to linguistic research(2014, 647).

(10)

Tuttavia, le possibilit`a che il paradigma dei sistemi complessi apre alla ricerca linguistica sono molte, aprendo al dialogo con le scienze cognitive[3][4] e con i modelli di Natural Language Processing che intendono simulare processi cognitivi[5][6][7].

Un sistema semantico descrive il comportamento emergente del significato. È l’obiet-tivo di questo lavoro intendere il significato del linguaggio naturale come una realtà per cui non basta analizzare le proprietà semantiche delle singole parole per rendere conto della loro complessità e del perché interagiscono con le altre parole. L’idea di fondo che muove questo lavoro è relativa alla simulazione di un’organizzazione lessicale che possa rendere conto delle realtà cognitive di un sistema semantico. Non è la prima volta, in letteratura, che si cerca di descrivere la struttura organizzativa di una rappresentazione di conoscenza semantica né che tale struttura venga utilizzata come simulazione di una possibile navigazione mentale tra le parole. La prima metafora del significato come rete di parole risale ai modelli di recupero dell’informazione della memoria semantica propo-sti in [8] e in [9], ma solo recentemente si può parlare di reti semantiche complesse e di come queste possano offrire modelli del lessico mentale guidati dal paradigma di ricerca della Network Science.

Il lessico mentale costituisce la base dell’organizzazione cognitiva del linguaggio. Si ipotizza che esso non sia semplicemente l’equivalente di un dizionario ordinato in modo alfabetico(2008, 95)[10], ma presenta un’organizzazione più complessa e efficiente. La Network Science può offrire nuovi modi di modellare il lessico mentale come un sistema complesso, concretizzandolo in un grafo. Un grafo G è una struttura dati costituita da un primo insieme di nodi N e da un secondo insieme di archi o relazioni L, tali che nella coppia G = (N, L) gli elementi di L siano composti da coppie di elementi di N; dati u e v, due nodi connessi da un arco o relazione e ∈ L, quest’ultimo è identificato come

(11)

segue: e = (u, v), u, v ∈ N.

Perché il lessico mentale possa essere modellato come rete complessa, serve identifi-care un insieme di unità linguistiche di cui è possibile studiare l’organizzazione globale. L’approccio delle reti complesse si applica indistintamente a sistemi e fenomeni fisici, biologici, metabolici, artificiali e sociali. Tutto può essere trasformato in una rete com-plessa, purché il tutto si presti a essere scomposto in un insieme di nodi e in un insieme di archi di un grafo. Solo in questo senso, quindi, le reti complesse possono rivelarsi utili anche allo studio di un fenomeno linguistico[2]2_.

In generale, il lessico mentale è da intendere come un sistema di conoscenza umano relativo a una rappresentazione astratta di un aspetto della conoscenza semantica espres-sa in termini di relazioni tra coppie di parole. Più formalmente, è un grafo G = (N, L) in cui l’insieme N è composto da un vocabolario di parole e l’insieme L è costituito da un qualche tipo di relazione semantica tra queste. Perciò, in primis, in questo lavoro dovrà essere spiegato in che modo intendiamo offrire un modello di parola come nodo (lo abbiamo già anticipato nell’Introduzione) e su quale tipologia di proprietà seman-tica intendiamo insistere e focalizzarsi perché i nodi si connettano facendo emergere una realtà complessa. Attenzione, perché in questo studio l’attenzione sarà rivolta uni-camente alle proprietà semantiche e non verranno prese in considerazione - nel’ottica di simulare un lessico mentale - le relazioni fonologiche, cioè la vicinanza di suono tra parole (e.g., le coppie minime come cane-pane), che tuttavia costituiscono un aspetto importante nell’ottica di una totalità conoscitiva del lessico mentale.

Per quanto riguarda N, poich´e si ipotizza che le informazioni riguardanti le parole

2_{Appropriate modeling of language depends on the research question to be addressed. Complex networks}

are appropriate when language is to be characterized globally in terms of linguistic units and their relations (2014, 646).

(12)

[la parola mangia] siano immagazzinate nel lessico mentale sotto forma di entrate les-sicali in cui sono immagazzinate informazioni relative […] alla sua pronuncia fonetica, alla sua trascrizione ortografica, alla sua categoria grammaticale (verbo), al suo signifi-cato concettuale (atto di ingerire cibo) e grammaticale (presente, indicativo, diatesi attiva, terza persona, singolare) e alle sue valenze morfosintattiche (il concetto MANGIARE richie-de che venga specificato chi compie l’azione di mangiare e ci`o che viene mangiato)(2008, 96)[10], possiamo dire che ogni nodo della rete mentale del lessico equivalga a un con-tenitore astratto comprendente un insieme di informazioni relative a pi`u livelli di analisi linguistica.

Per quanto riguarda L, le similarità semantiche tra le parole si organizzano in una struttura del significato discriminata a partire dal tipo di similarità che avvicina o allon-tana (crea distanza tra) le parole. Una rete semantica complessa (che intende offrire un modello del lessico mentale) può essere classificata sulla base del tipo di relazione che intercorre tra le parole: esistono relazioni semantiche intrinseche (di gerarchia, di sino-nimia, di antosino-nimia, di meronimia) cos`ı come relazioni associative cos`ı come qualsiasi altro tipo di relazione di co-occorrenza tra parole (cfr. 1.6).

In generale, queste brevi informazioni iniziali costituiscono il punto di partenza teo-rico per le analisi che saranno svolte successivamente in questo lavoro. Ci serve capire in che modo interagiscono le singole parti che danno origine al nostro sistema comples-so prima di indagarne le proprietà globali. I pattern elementari da cui partiamo comples-sono le connessioni semantiche tra le singole parole e la proprietà semantica su cui intendiamo insistere è legata alla rappresentazione distribuzionale del significato, per noi la più in-dicata a far emergere la complessità del significato. L’ipotesi di fondo è la seguente: le parole che possono essere sostituite all’interno di un contesto semantico simile danno

(13)

origine a campi semantici; tradotto nel linguaggio della Network Science, i nodi si rag-gruppano in zone della rete particolarmente più dense di altre, che possono essere deli-mitate nell’ottica di un partizionamento algoritmico del grafo. Sono i campi semantici, in realtà, a essere i mattoni costitutivi che compongono il sistema semantico. Identifi-carli può aiutarci a capire qual è il loro peso e in che modo la complessità emerge da una rappresentazione distribuzione del significato.

1.2 Nozioni preliminari sui grafi

In Sezione 1.1 si è già data una definizione preliminare di grafo. Un grafo G = (N, L) è una struttura dati costituita da un insieme di nodi N e da un insieme di archi o relazioni L, composto da coppie di elementi del primo, tale che e = (u, v), u, v ∈ N.

Un grafo si dice orientato se le sue coppie di nodi sono ordinate, cioè se la relazione e = (u, v)non è identica alla relazione e = (v, u). Un grafo si dice non orientato se le relazioni non seguono una direzione da un nodo in entrata a un nodo in uscita, cioè se e = (u, v) è equivalente a e = (v, u). In un grafo orientato si dice che il nodo u è il predecessore di v e v è il successore di u; in un grafo non orientato si dice che i due nodi sono adiacenti.

Ogni nodo pu`o connettersi a uno o, naturalmente, a pi`u nodi. Il numero di relazioni di un nodo corrisponde al suo grado k. Il grado medio hki di una rete corrisponde alla somma delle relazioni di ogni nodo in rapporto al numero complessivo di questi, non altro che hki = L

N, in un grafo orientato, e hki = 2L

N, in un grafo non orientato. Tra

parentesi, il numero massimo di archi in un grafo di N nodi si indica con Lmax ed `e

uguale a Lmax = N (N −1)₂ . La maggior parte delle reti complesse `e sparsa, cio`e quasi mai

(14)

L Lmaxe hki N − 1. Una rete con L = Lmax `e un grafo completo e il suo grado

medio è uguale a hki = N − 1. La densità di una rete è pari a density = 2L N (N −1)

Il numero di nodi con grado k si indica con Nke la probabilit`a che un nodo selezionato

casualmente abbia grado k `e uguale a p(k) = Nk

N . La successione di tutti i valori di p(k)

corrisponde alla distribuzione di probabilit`a dei gradi dei nodi del grafo. La funzione cumulativa (CDF) e la sua complementare (CCDF) corrispondono rispettivamente a la probabilit`a che un nodo abbia grado uguale o minore (o maggiore) a k:

CDF = _N1 P k0_≤k Nk0 CCDF = 1 N P k0_≥k Nk0

Insistendo ancora sulla nozione di grado, in questo lavoro si indagherà la cosiddetta assortatitivà di una rete rispetto al grado. In breve, una rete è assortativa se nodi con grado simile tendono a connettersi fra di loro; al contrario, è disassortativa se gli hub (i nodi con il grado più alto della rete) tendono a connettere zone meno connesse della rete. L’assortatività di una rete rispetto al grado viene misura dal coefficiente di assortatività rinteso come correlazione di Pearson tra coppie di vertici connesse da un arco:

r = 1 N P j>1 kikjaij−[_N1 P j>1 1 2(ki+kk)aij] 2 1 N P j>1 1 2(k2i+k2j)aij−[12(ki+kk)aij]2

Con r compreso tra -1 e 1, se r > 0, la rete `e assortativa, se r < 0, la rete `e disassortativa; se r = 0, non presenta nessuno dei due caratteri.

In questo lavoro si far`a anche uso di K-Nearest-Neighbor Knn (o grado medio dei

vicini). Come proposto in [11], riprendendo [12], per misurare l’assortatività di una rete si può verificare l’andamento di Knn(k) rilevato su Knn. Il procedimento è il seguente:

per ogni nodo n della rete viene calcolato il grado medio dei vicini knn = _k1_n kn

P

i=1

ki, con

knuguale al numero dei vicini del nodo, cio`e al suo grado, e kiuguale al grado dei vicini

(15)

knnper ogni classe di gradi k, vale a dire knn(k): una correlazione tra knn(k)e k `e indice

di assortativit`a della rete.

Dato un grafo G = (N, L), un cammino `e una sequenza di nodi n0, ..., nk tale che

(ni, ni+1) ∈ Lper ogni i = 0, ..., k − 1, cio`e una sequenza dove ogni nodo `e adiacente

al successivo, la lunghezza della quale `e il numero di archi osservati per arrivare da n0

a nk. Un cammino minimo d `e la lunghezza minima tra una coppia di nodi. Il diametro

dmax `e la lunghezza del pi`u lungo cammino minimo tra due nodi. Il cammino minimo

medio hdi equivale alla media dei cammini minimi per ogni coppia di nodi del grafo, in breve: hdi = 1 N (N −1) P i,j>i dij

Infine, il coefficiente di clustering evidenzia in che misura i vicini di un nodo tendono a essere connessi anche fra di loro. Pu`o essere calcolato localmente (sui singoli nodi) o globalmente (sull’intera rete). Indicando con Enil numero dei triangoli formati dal nodo

ne i suoi vicini, il coefficiente di clustering locale Ci `e due volte il numero dei triangoli

in rapporto alla totalit`a dei collegamenti possibili, in breve:

Ci = _k_n_(k2E_nn₋₁₎

Globalmente, il coefficiente di clustering C pu`o essere inteso come la media dei coefficienti di clustering locali, in breve:

C = 1 N n P i=1 Ci

I nodi possano essere valutati differentemente in merito alla loro rilevanza all’in-terno della rete, calcolando, ad esempio, la closenness centrality CCi e la betweenness

(16)

CCi`e intesa come il reciproco della somma della lunghezza dei cammini minimi tra il

determinato nodo selezionato e tutti gli altri nodi del grafo; in breve, misura la centralit`a di un nodo sulla base della sua vicinanza con il maggior numero di nodi possibile:

CCi = P1 jdij

BCi `e il numero di cammini minimi che attraversano un nodo; in breve, se σni,nj(n)

`e il numero dei cammini minimi tra ni e nj che passano da n e σni,nj `e il numero di

cammini minimi totali tra i nodi nie nj:

BCi =

P

n6=ni6=nj

σ_ni,nj(n) σ_ni,nj

Ci sono tutti gli elementi minimi necessari per proseguire. Questa breve introduzione `e necessaria per l’analisi successiva delle propriet`a globali della rete. In particolare, p(k), hdie C sono gli indici principali utilizzati per identificare una rete complessa.

1.3 Modelli di reti complesse

In questa sezione viene presentata una breve lista di tre modelli classici entrati a far parte della letteratura della materia. Ogni modello d`a il nome al paragrafo. In Figura 1.1 sono visualizzate le due principali tipologie di reti che i modelli intendono descrivere e generare.

1.3.1 Modello di Erd¨

os-R´enyi

Il modello di Erdös-Rényi o modello ER (dal nome dei suoi creatori Pál Erdös e Al-fréd Rényi, nonostante i contributi al modello provengano anche da E. N. Gilbert) è un modello che si propone di generare reti casuali.

(17)

Figura 1.1: Due tipologie di reti, a sinistra una rete casuale e a destra una rete scale-free, determinata dalla presenza di hub, pochi nodi con un numero di vicini fortemente maggiore rispetto agli altri.

Ne esistono due formulazioni, la variante G(N, L)[13] e la variante G(N, p)[14]. • G(N, L): si ottiene scegliendo casualmente un grafo tra quelli presenti nella lista

di tutti i possibili grafi aventi N nodi e L archi;

• G(N, p): si ottiene connettendo casualmente le coppie di nodi di N generando archi con probabilit`a p indipendente da quella di ogni altro arco.

In presenza di una probabilità, il numero delle connessioni della rete è variabile, e si indica con p(L) la probabilità di avere esattamente L archi (ovvero L = N (N −1)

2 archi)

in una rete di N nodi con probabilit`a p:

p(L) = (N2) L p

L_{(1 − p)}N (N −1)₂ −L

La distribuzione di probabilit`a dei gradi p(k) `e la seguente:

p(k) = N −1_k pk(1 − p)N −1−k Per un numero alto di N e piccolo di k:

(18)

p(k) = e−hki hki_k!k

con hki = p(N − 1). La distribuzione rivela che la maggior parte dei nodi della rete ha lo stesso numero dei vicini, che corrisponde pressoch´e al grado medio della rete.

Le reti complesse reali, in realtà, non sono caratterizzate dall’aleatorietà dei modelli ER, cioè non è la generazione casuale di archi con una determinata probabilità p a co-stituire un fattore determinante nella composizione della struttura delle reti complesse. Esse sono tali perché presentano una struttura irregolare, non casuale e dinamica, che si evolve nel tempo secondo determinati principi. Altri modelli sono, quindi, necessari a cogliere la struttura delle reti reali.

1.3.2 Modello di Watts-Strogatz

Il modello di Watts-Strogatz o modello WS (dal nome dei suoi creatori Duncan Watts e Steven Strogatz) `e un modello che genera reti casuali che presentano propriet`a small-world[15].

Dalle reti casuali, infatti, è possibile far emergere una tipologia di proprietà nota con il nome small-world. L’espressione pone l’accento su hdi e C: valori piccoli di hdi e relativamente alti di Cicaratterizzano le reti reali con proprietà small-world.

Perch´e il nome small-world? Se esiste un cammino minimo medio relativamente corto tra ogni coppia di nodi della rete, significa che anche nodi distanti possono essere raggiunti in pochi passi, cio`e con l’attraversamento di un numero relativamente breve di altri nodi. Il sociologo statunitense Milgram descrisse il fenomeno small-world nel co-siddetto esperimento dei sei gradi di separazione[16], teoria ispirata e formulata per la prima volta dallo scrittore ungherese Karinthy[17]. L’esperimento di Milgram consisteva nel selezionare casualmente un gruppo di cittadini statunitensi del Midwest, chiedendo

(19)

loro di spedire un pacchetto a un estraneo nel Massachussetts, conoscendo solo il nome, l’impiego e la zona di residenza, ma non l’indirizzo. Chiedendo loro di spedire il pac-chetto unicamente a una persona conosciuta (e.g. ad un vicino del nodo) che avrebbe potuto avere la maggiore probabilità di conoscere il destinatario finale, Milgram rilevò, contro l’ipotesi che sarebbero serviti almeno un centinaio di tentativi per far giungere il pacchetto a destinazione, che esisteva un cammino lungo solo 5 o 6 passi, cioè che il pacchetto arrivava a destinazione con una media relativamente corta di soli cinque o sei passaggi.

Questa proprietà (hdi molto breve) è presente anche nelle reti casuali, ed è evidenziata dal modello WS. Dato un insieme di N nodi N = n1, n2, ..., ni, un valore pari di k e

n k ln(n) 1, il modello presenta i seguenti passaggi:

• si dispongono i nodi in una struttura ad anello e si connette ciascuno di essi ai k nodi pi`u vicini (i.e. k/2 a destra e k/2 a sinistra);

• si ridistribuiscono gli archi ottenuti con una determinata probabilità p, escludendo self-loops e archi duplicati (i.e. si sostituisce e = (u, v) con e = (u, w), w 6= u, w 6= v), in modo tale da osservare il cambiamento della rete da p = 0 (nessun cambiamento, quindi resta una struttura regolare) a p = 1 (il massimo di casualità, quindi è una rete casuale).

Al variare di p, è possibile monitorare la trasformazione di una struttura regolare in una casuale, come visibile in Figura 1.2. Per quali valori della probabilità di sostituzione è possibile osservare una rete small-world? Per bassi valori di p, C tende a rimanere relativamente alto, per via della topologia ancora regolare della rete, ma tende pian piano a decrescere e tendere a 0 all’aumentare della probabilità; per quanto riguarda hdi, esso

(20)

Figura 1.2: Da una struttura regolare a una casuale: le propriet`a small-world si osservano nella ridistribuzione degli archi al variare di p osservando i valori di C e di hdi.

decresce all’aumentare della probabilit`a, che stabilisce casualmente scorciatoie tra nodi; i valori di Cirimangono relativamente alti.

Con il modello WS, al variare di p `e possibile stabilire una famiglia di reti small-world, che catturano valori di hdi e Cicoerenti con le osservazioni dei sistemi fenomeni

complessi. Però, non è ancora possibile descrivere la distribuzione di probabilità dei gradi non casuale osservata nelle reti complesse reali.

1.3.3 Modello di Barab´asi-Albert

Nelle reti casuali abbiamo visto che p(k) segue una distribuzione poissoniana. Le reti reali complesse non presentano n´e una topologia regolare n´e una topologia totalmente casuale: per una prima visualizzazione, la Figura 1.3 mostra la distribuzione dei gradi in una rete casuale e in una a invarianza di scala.

Si chiamano reti a invarianza di scala (o scale-free) le reti che presentano una di-stribuzione di probabilità dei gradi l’andamento della quale segue una legge di potenza (power-law). La relazione tra il numero di nodi e il numero di archi della rete è di tipo esponenziale negativo e la struttura della rete è identificabile dall’esponente di scala, il

(21)

parametro α, per cui:

p(k) ' k−α

Figura 1.3: A sinistra la distribuzione di probabilit`a dei gradi di una rete casuale e scale-free, a destra la stessa distribuzione rappresentata su doppia scala logaritmica.

Il modello di Barabási-Albert o modello BA (dal nome dei suoi autori Albert-László Barabási e Réka Albert) [18][19] si propone di generare reti con una struttura scale-free, basandosi sui due concetti di crescita (growth) di una rete e di collegamento preferenziale (preferential attachment).

Partendo dal presupposto che le reti reali si evolvano nel tempo (i.e. non predispon-gono di un valore fisso di N), ha origine il concetto di crescita di una rete; partendo dal presupposto che esista un qualche criterio per cui i nodi si connettano tra di loro (e, quindi, non solo una probabilit`a p indipendente da altri fattori), ha origine il concetto di collegamento preferenziale, che stabilisce come un nuovo nodo si introduca nella rete preferendo connettersi ai nodi con un numero di connessioni (i.e. grado) pi`u alte degli altri.

(22)

• growth: si parte con una piccola rete di m0 nodi a cui, ad ogni step t, si aggiunge

un nuovo nodo con m(m ≤ m0)connessioni da stabilire con m nodi gi`a presenti;

• preferential attachment: le connessioni si stabiliscono sulla base del grado ki:

Pi(t) = n(t)ki(t) P j=1

kj(t)

L’invarianza di scala catturata dal modello BA indica come la crescita e il collega-mento preferenziale giochino un ruolo fondamentale nella strutturazione della rete.

1.4 Community discovery

1.4.1 Definizioni di comunit`a

L’analisi delle reti complesse non si focalizza unicamente sulle proprietà globali delle strutture complesse, ma anche sulle loro meso-strutture, cioè sull’esplorazione di pattern interni alla rete che presentano una topologia non banale. Tali strutture interne vengono identificate con il nome di comunità. Non è semplice definire cos’è una comunità in una rete complessa. In generale, si tratta di un insieme di nodi strettamente più connessi tra loro che non con nodi appartenenti ad altri insiemi. Tale definizione quasi tautologica ci permette quanto meno di osservare la presenza di gruppi di nodi più connessi tra loro.

Figura 1.4: La scala di analisi di complessit`a di una rete: ciascun livello ha i propri metodi e strumenti di analisi per indagare la struttura di una rete complessa.

(23)

L’obiettivo delle tecniche di community discovery consiste nel delimitare tali gruppi omogenei. In altre parole, si tratta di partizionare un grafo in un insieme di comunità. Un algoritmo di community discovery modella una comunità sulla base di specifiche proprietà che di essa vuole catturare. Perciò, è possibile classificare gli algoritmi sulla base di tali criteri discriminanti: cosa si vuole analizzare, quale approccio si vuol se-guire, che tipo di comunità viene prodotto[20]. Di seguito, viene presentata una breve classificazione a partire dal criterio di partenza discriminante:

• densità interna: una comunità è caratterizzata da un numero di archi significati-vamente maggiore rispetto a quello presente in un grafo casuale. Si tenta di mas-simizzare una funzione di modularità Q, che quantifica la densità di una comu-nità. Due degli algoritmi più interessanti che propongono questo approccio sono Louvain[21] e Leiden[22], evoluzione del primo;

• ponti: si ottiene una comunità eliminando i ponti (i.e., gli archi) che connetto-no le parti della rete più dense. Girvan-Newman[23], uconnetto-no degli algoritmi più famosi in letteratura, propone questo approccio basandosi sul calcolo dell’edge-betweenness;

• percolazione: una comunità è un insieme di nodi raggruppati in seguito alla pro-pagazione di una stessa proprietà o informazione all’interno del network. Due esempi caratteristici sono Label Propagation[24] e Demon[25][26]:

– Label Propagation: ogni nodo viene inizializzato con un proprio id; nella prima iterazione, ciascun nodo, con probabilit`a α, cambia il suo label con quello dei suoi vicini; a ogni successiva iterazione, ogni nodo adotta il label condiviso dalla maggior parte dei suoi vicini;

(24)

– Demon: Demon è un algoritmo che produce comunità con overlapping (i.e., i nodi possono appartenere a più d’una comunità), che pensa localmente nella misura in cui ogni nodo è capace di identificare le proprie comunità -e globalm-ent-e - n-ella misura in cui si t-enta di raggruppar-e l-e comunità locali in altre più grandi. Per ogni nodo della rete viene estratto il suo ego-network (i.e., un grafo composto dal nodo stesso più i suoi vicini e le connessioni tra questi, se presenti), viene rimosso il nodo dal grafo estratto e viene eseguito Label Propagation sulla rete restante. Il nodo iniziale viene inserito all’in-terno di ogni comunità estratta. Una soglia τ determina quali nodi vengono raggruppati all’interno di comunità più grandi: se il τ% della comunità più piccola non è inclusa in quella più grande, le comunità vengono unite;

• prossimità: una comunità è caratterizzata da un insieme di nodi che raggiungono i loro vicini attraversando un numero molto piccolo di archi, significativamente più basso del cammino minimo medio della rete;

• struttura: una comunità è un insieme di nodi con un preciso numero di archi distri-buiti in una topologia ben precisa. K-clique è l’algoritmo più popolare che sfrutta la definizione di comunità come struttura;

• relazioni: una comunità è un insieme di nodi che condividono un determinato numero di relazioni raggruppate insieme, vale a dire che a definire una comunità soo determinati pattern relazionali: è la relazione che appartiene alla comunità e i nodi appartengono alle comunità delle loro connessioni;

• per concludere, non c’`e una definizione a priori: ciascun dominio presenta raggrup-pamenti di nodi definiti da principi coerenti e interni al dominio stesso.

(25)

1.4.2 Valutare i partizionamenti

Per valutare la bontà di un partizionamento ci serviamo di due famiglie di approcci, uno che si focalizza su una valutazione interna alla rete e un altro che prevede una valutazione esterna. Nel primo caso il partizionamento viene valutato sulla base delle caratteristiche interne delle comunità (dimensioni, distribuzione dell’overlapping, etc.) e su funzioni qualitative del partizionamento (modularità, conduttanza, densità, etc.). Per quanto ri-guarda una valutazione interna, invece, facciamo uso del ground truth testing. Dato un grafo G = (N, L) e un insieme di comunità C estratte con un algoritmo di commu-nity discovery, un partizionamento ground truth P (G) è un insieme di comunità gold standard attraverso cui valutare la bontà di C. Per paragonare le due reti facciamo uso di funzioni che valutano la somiglianza tra i due partizionamenti, ad esempio F1[27] e NF1[28]. Per ogni comunità x ∈ C associamo la corrispettiva comunità y ∈ P (G) con il più alto numero di label presenti anche nella prima e calcoliamo Precision e Recall delle coppie (x, y), nella misura in cui Precision è la percentuale di nodi in x etichettati come ye Recall è la percentuale di nodi in y coperta da x:

precision = |x∩y|_|x| ∈ [0, 1] recall = |x∪y|_|y| ∈ [0, 1]

Infine, F1 `e la media armonica di Precision e Recall:

F 1 = 2·precision·recall_{precision+recall}

Per quanto riguarda NF1, aggiungiamo Redundancy e Coverage, intese come match multipli a una stessa comunit`a, la prima, e la percentuale di comunit`a catturate:

redundancy = _|P|C|

id(G)| ∈ [1, ∞] coverage =

|Pid(G)|

(26)

Pid(G)sono le comunit`a in P (G) catturate in C.

Infine, NF1:

N F 1 = F 1∗redundancy_coverage

Il ground truth testing è un problema di difficile formalizzazione allo stesso modo in cui lo si è affrontato per la definizione di una comunità. Non esiste un partizionamento P (G)ottimale per una determinata rete - nella misura in cui le ground truth communities identificate possono non costituire l’unico valido partizionamento topologico per la rete analizzata. In sintesi, definizione di comunità e valutazione dei partizionamenti - e, in generale, i compiti di community discovery - rientrano tra gli argomenti più delicati della Network Science.

1.5 Lo studio del significato se l’unit`a minima di

ana-lisi `e…

Le lingue sono le attuazioni socio-culturali[29] della facoltà del linguaggio[30]. Per la linguistica generale, una lingua è un sistema complesso che si scompone su più livelli di analisi secondo un ordine gerarchico in cui un livello inferiore costituisce la base di quello superiore, cioè dove ciascun livello assume come unità minima di analisi il punto di arrivo del livello precedente[31]. Cos`ı, il punto di arrivo della morfologia è la struttura della parola e il suo punto di partenza, cioè la sua unità minima di analisi, è il morfema, inteso come il più piccolo elemento di una parola dotato di significato (che veicola, cioè, una categoria grammaticale). I due livelli successivi alla morfologia sono la morfosintassi e la sintassi: entrambe prendono la parola come unità minima di analisi per studiare la struttura della frase, loro punto d’arrivo.

(27)

Venendo a noi, la semantica è lo studio del significato e, nella classificazione gerar-chica dello studio di una lingua, fa parte dei suoi livelli più alti. Alla domanda cos’è il significato? non si deve rispondere se prima non si ha la chiarezza che la definizione del significato cambia in base all’unità minima dell’analisi semantica scelta. Le unità minime di analisi del significato sono la frase, la parola o il contesto.

1.5.1 …la frase

Assumendo come unità minima la frase, la semantica studia la struttura argomentale del verbo. Intorno a un predicato si costituisce un insieme di argomenti, cioè chi o cosa partecipa all’evento denotato dal predicato stesso. Quest’ultimo stabilisce il numero e il tipo dei suoi argomenti: il verbo esistere, ad esempio, necessita di un solo argomento (formalizzando la sua struttura argomentale come esistere(x)), mentre il verbo mangiare implica due argomenti, chi mangia e cosa viene mangiato (mangiare(x, y)), e cos`ı via. Il tipo di relazione che un verbo instaura con i propri argomenti si chiama ruolo tematico (o ruolo semantico o ruolo θ). La lista di tali ruoli tematici è potenzialmente infinita: essi, infatti, si stabiliscono lungo un continuum stabilito da due poli, delimitati da due ruoli tematici principali e opposti, Agente e Paziente, per cui il primo descrive l’entità che compie volontariamente un’azione e il secondo l’entità che ne subisce passivamente una; tra i due poli si viene a formare una lista di ruoli tematici definita dalla granularità della classificazione che si vuole proporre.

1.5.2 …la parola

Assumendo come unit`a minima la frase, la semantica studia il significato delle parole. La semantica lessicale stabilisce diversi tipi di relazioni semantiche, tra cui quelle di

(28)

gerarchia (ipo-iperonimia), di sinonimia, antonimia, meronimia, olonimia. Per fare brevi esempi, una relazione tra i termini cane e animale identifica una relazione di gerarchia, dove il secondo, che comprende un significato più esteso e generale del primo, è il suo iperonimo, e cane è iponimo di animale. Una relazione tra caldo e freddo è un esempio di antinomia, mentre tra freddo e gelido è stabilito un rapporto di sinonimia, e tra zampa e cane si dice che esiste un rapporto di meronimia.

WordNet[32][33] `e un database lessicale che cattura molti dei tipi di relazione appena descritti. In particolare, in WordNet, i sostantivi si raggruppano in synset, insiemi di sinonimi, mentre tra gli aggettivi `e frequente la relazione di antonimia (black-white). In sintesi, le relazioni vedono coinvolte coppie di parole che appartengono alla stessa parte del discorso.

Da questi database non bisogna dimenticare che ogni tassonomia che intende cata-logare le relazioni semantiche è arbitraria e dettata dalla volontà dei linguisti che nel tempo hanno studiato il significato. Come nel caso dei ruoli tematici, le liste di relazioni semantiche dipendono dalla granularità che si vuole proporre. Tuttavia, al di là delle differenze tra le cosiddette relazioni semantiche intrinseche appena descritte, si può me-glio optare per una differenza tra queste e altri tipi di relazioni tra parole che catturano caratteristiche più connotative del significato, correlate alle esperienze soggettive di un individuo o ad accezioni legate a un contesto socio-culturale condiviso. La differenza con le precedenti consiste nel fatto che no si tratta di vere e proprie relazioni semantiche ma di associazioni.

(29)

1.5.3 …il contesto

Assumendo come unità minima il contesto, facciamo i conti con la teoria distribuzionale del significato e con i suoi modelli di semantica distribuzionale: gli spazi semantici[34]. Il contesto linguistico è la pietra miliare della semantica distribuzionale, l’approccio alla semantica che coglie le proprietà del significato a partire dalla distribuzione delle parole nei testi. Gli assiomi della semantica distribuzionale si riassumono nelle parole di J. R. Firth: conoscerai una parola dalla compagnia che frequenta (1957,11)[35], nel distribuzio-nalismo di Z. Harris[36], e nelle teorie del significato di L. Wittgenstein: il significato di una parola è il suo uso nel linguaggio(1953, §43)[37].

I modelli usati per catturare le propriet`a del significato teorizzate dalla semanti-ca distribuzionale sono gli spazi semantici. Nella loro formulazione pi`u generale, la costruzione di uno spazio semantico prevede, almeno, i seguenti passi:

• si parte da un corpus da cui si estrapolano un insieme di elementi target T (i.e., il vocabolario di un corpus) e un insieme di contesti B (gli elementi che compongono la finestra contestuale degli elementi di T ):

• si genera una matrice M di dimensione |T |X|B| le cui celle contengono i valori di una funzione di peso w con cui si confrontano gli elementi di T con quelli di B per stabilire ci`o che `e statisticamente importante e cosa no;

– le funzioni di peso w sono molteplici: pu`o essere semplicemente la frequenza f (ti, bi)con cui gli elementi dei due insiemi co-occorrono o funzioni via via

pi`u complesse come tf-idf o PPMI;

• si riduce la dimensione dei vettori sparsi utilizzando tecniche di riduzione della dimensionalit`a;

(30)

• si stabilisce una funzione di similarità vettoriale; una delle più utilizzate è la simi-larità del coseno sim(~v1, ~v2) = _kvv~1· ~v2

1kkv2k, corrispondente al coseno dell’angolo che

i due vettori formano nello spazio.

In sintesi, un corpus, una funzione di peso, una riduzione della dimensionalit`a e una funzione di similarit`a semantica sono gli ingredienti necessari per la costruzione di uno spazio semantico. Un primo esempio di spazio semantico fu il Vector Space Model[38] un documento d (i.e., una sequenza di parole) veniva identificato da un vettore v(d), de-scrivibile come combinazione lineare v(d) = P

i=1

wivi, dove wiera il valore della funzione

di peso utilizzata per rilevare cosa era statisticamente rilevante e cosa no. Ogni vettore v(di)era composto (se un termine compariva nella sequenza di di e quindi il suo valore

non era 0), dai valori della funzione di peso assegnata.

La definizione di contesto linguistico aveva a che fare con le parole che comparivano nello stesso documento in cui occorreva la parola target. Anche la definizione dell’insie-me B, perciò, dipende dal modo in cui il contesto linguistico viene modellato. In questo lavoro l’attenzione si focalizzerà sui word embedding, e il contesto linguistico sarà co-stituito dalle parole che compaiono all’interno di una finestra contestuale intorno alla parola target (cfr 2.2). Un’altra definizione di contesto linguistico, non utilizzata qui ma interessante per studi futuri, si concentra sulle parole con cui la parola target è legata da relazioni di dipendenza sintattica.

(31)

1.6 Verso una classificazione delle reti semantiche

com-plesse

In questa sezione propongo una classificazione delle reti semantiche a partire dal tipo di relazione che le parole instaurano tra loro. In altri termini, significa classificare le reti a partire dalle differenti definizioni del significato di cui ciascun tipo di relazione rappresenta le propriet`a catturate da esse. La discriminante, quindi, risulta dal tipo di definizione data al significato. Nell’elenco seguente riassumo brevemente lo stato dell’ar-te delle reti semantiche complesse, fornendone una semplice classificazione sulla base delle differenti unit`a minime di analisi del significato:

• frase: come già visto, il significato di una frase ruota intorno alla struttura argo-mentale del verbo. I dataset da cui estrarre le reti sono le treebank annotate con i ruoli semantici del verbo. Le strutture emergenti presentano una topologia scale-free, proprietà small-world, una struttura gerarchica e una lieve disassortatività rispetto al grado[11][39];

• la parola: si `e accennato al fatto che le relazioni tra parole nascono in seno a caratteristiche intrinseche o associative[10]:

– relazioni semantiche intrinseche: le relazioni di sinonimia, antonimia, ipo-iperonimia, meronimia, olonimia, etc sono gli archi che identificano le rela-zioni tra nodi. I dataset da cui estrarre le reti sono i database lessicali come WordNet o i tesauri. Le strutture emergenti sono scale-free e small-world[40]

3_[41];

(32)

– relazioni semantiche associative: le relazioni che non rientrano nelle categorie precedenti connettono le parole sulla base di esperienze individuali o contesti socio-culturali condivisi. I dataset da cui estrarre le strutture sono le norme di associazione come USF[42], per la lingua inglese. Le strutture sono scale-free e small-world[41];

• il contesto linguistico: si parte dagli assunti della semantica distribuzionale[5] e si rappresenta il significato come uno spazio di parole[1]. I dataset da cui estrarre le strutture sono gli spazi semantici, come word2vec[43][44]. Sono le strutture di cui è più controversa l’identificazione di una topologia scale-free e delle proprietà small-world[41][6][45].

In sintesi, nonostante esistano differenti definizioni del significato (e, di conseguen-za, differenti tipi di reti emergenti), una struttura complessa `e sempre individuabile4_.

Classificare le reti semantiche, però, non è un esercizio di stile fine a se stesso. Le si-milarità osservate nelle proprietà globali non devono sminuire l’importanza della tipo-logia di proprietà semantica che collea le parole: infatti, non è detto che l’analisi della meso-struttura delle reti sia simile.

Per un riepilogo conclusivo, incentrato sulla propriet`a semantica che intendiamo stu-diare in questo lavoro, uno spazio semantico esula dal definire il tipo di relazione lingui-stica che le parole instaurano tra loro, vale a dire che in uno spazio semantico una parola

from the WordNet dataset. Nodes in the network are English words, and links are relationships between them, such as synonymy, antonymy, meronymy, etc. All relationships present in the WordNet dataset are included. The resulting network is undirected. hdi = 5.36, C = 0.09, λ = 2.4, r = −0.06 (i.e., lievemente disassortativa.

4_{Although the processes that generated these data surely differ in important ways, we see that the resulting}

(33)

può essere connessa senza distinzione di classificazione ai suoi sinonimi, ai suoi iperoni-mi, ai suoi opposti, etc. Questo perché la discrimante su cui viene definito il significato è la proprietà del contesto linguistico. In letteratura, l’attenzione si sta focalizzando sulla struttura complessa degli spazi semantici e sulla ricerca di modelli del lessico mentale a partire da questi. Tre macro-variabili, però, devono essere prese in considerazione per valutarne la solidità metodologica: la dipendenza da un corpus, la scelta di un model-lo del linguaggio e di un metodo di estrazione. Discussioni più approfondite riguardo a queste che possono essere considerate come delle vere e proprie variabili epistemo-logiche (che infuenzano, cioè, la riproduzione del significato come attinente alla realtà conoscitiva del significato) emergeranno nel momento in cui dovranno essere date, nei capitoli successivi, interpretazioni sui dati oggettivi che ci troveremo ad analizzare.

1.7 Modelli di reti semantiche complesse

Come fatto in precedenza per i modelli di reti reali complesse, dopo aver osservato che anche le reti emergenti da strutture semantiche di vario tipo presentano topologie e proprietà globali non banali, passiamo brevemente in rassegna due specifici modelli ge-nerativi di reti semantiche complesse. I modelli gege-nerativi, al contrario degli approcci data-driven(e.g., le reti estratte dai dataset cui si è fatto riferimento nel paragrafo prece-dente o quelle che verranno estratte in questo lavoro), costituiscono tentativi di simulare l’evoluzione di un sistema semantico identificando innanzitutto i principi secondo cui i nodi stabiliscono i propri vicini, offrendo modelli di acquisizione del linguaggio che ren-dano conto di variabili psicolinguistiche come la frequenza con cui una parola viene utilizzata o l’età in cui viene acquisita.

(34)

signifi-cato a partire dalle connessioni tra coppie di parole sui cosiddetti due assi del linguaggio. Secondo la teoria strutturalista[29], il linguaggio si posiziona su due assi: un asse sin-tagmatico e uno paradigmatico. Il primo coincide con la disposizione necessariamente lineare della sequenza linguistica (vale a dire che il linguaggio si articola una parola dopo l’altra), il secondo coincide con le parole che possono essere sostituite nella catena lin-guistica (vale a dire le associazioni di parole che vengono alla mente durante la lettura dell’asse sintagmatico).

1.7.1 Modello di Steyvers-Tenenbaum

Il modello di Steyvers-Tenenbaum o modello ST (dal nome dei suoi autori Mark Steyvers e Joshua Tenenbaum)[41] `e un modello che intende generare reti semantiche scale-free e small-world, in virt`u di quanto emerso dalle loro analisi su WordNet, i tesauri e USF.

Riprendendo il modello BA, gli autori sostengono come quest’ultimo non renda conto dell’evoluzione di una rete semantica: i valori di C, infatti, tendono a rimanere bassi, contrariamente a quanto osservato nelle reti semantiche reali da loro analizzate. Cos`ı, ipotizzano che la crescita di una rete non dipenda solo da una probabilità proporzionale al grado del vicino scelto dal nodo che deve aggiungersi in rete (i.e., il parametro del collegamento preferenziale) ma estendono tale possibilità anche ai vicini dei nodi scelti. In più, introducono una funzione di utilità che ha l’obiettivo di scegliere tra i vicini del nodo selezionato.

Identificando con Γ(x) l’insieme dei vicini di un nodo x pi`u il nodo x, il modello ST si sviluppa nei seguenti termini:

• growth: si parte con una piccola rete di m0 nodi a cui, ad ogni step t, si aggiunge

(35)

Γ(m);

• le connessioni si stabiliscono sulla base di due funzioni:

– preferential attachment: come per il modello BA;

– semantic differentiation: `e la funzione di utilit`a che permette al nuovo nodo di connettersi ai nodi di Γ(m): Pij(t) = utj P l∈Γ(l) utl

dove ut è una funzione di utilità variabile che coglie l’utilità di una parola rispetto alle altre. Può essere identificata sulla base di vari criteri corrispon-denti a realtà cognitive differenti come la frequenza d’uso.

L’aggiunta del parametro di differenziazione semantica (semantic differentiation) `e giustificato sulla base dell’esistenza dell’asse sintagmatico del linguaggio.

1.7.2 Modello di ST-Utsumi

Una versione modificata del modello ST `e stata proposta in [6], in cui viene aggiunto un parametro che rende conto dell’esistenza dell’asse paradigmatico del linguaggio. Gli m nodi con cui un nuovo nodo deve stabilire connessioni sono etichettati rispettivamente come semantic differentiation (per identificare un rapporto sintagmatico) e come expe-riential correlation(per indicare un rapporto paradigmatico) e si distinguono come mp,

i primi, e mr = (m − mp), i secondi. Il nuovo nodo si connette ai nodi mp con una

probabilit`a pari a 1 − p, ai nodi mr con una probabilit`a p. In questa maniera, vengono

avvantaggiate le prime rispetto alle altre. Relativamente alle due singole classi, la pro-babilit`a di connessione tra i nodi mp `e identica a quanto espresso nel modello ST; per

(36)

quanto riguarda le connessioni tra il nuovo nodo e i nodi mr, esse sono scelte tra tutti i

nodi della rete.

Il senso di tale differenziazione `e di rendere atto di una struttura del significato emer-gente dalla combinazione della catena sintagmatica con l’asse paradigmatico. In un certo senso, anche gli spazi semantici analizzano la catena sintagmatica (i.e., il contesto) per catturare relazioni di tipo paradigmatico.

È a partire da quest’ottica che nel prossimo capitolo entreremo nel vivo di questo lavoro, costruendo gli spazi semantici da cui saranno estratte le reti da analizzare. Prima di iniziare, concludo con un’ultima considerazione relativa a quanto esposto in questa sezione e nella precedente. In [41] l’estrazione di una rete da uno spazio semantico veniva vista come un modello alternativo a uno generativo nel tentativo di simulare una reale struttura del significato. Cos`ı, gli autori sostenevano che uno spazio semantico non fosse in grado di simulare le reti estratte da WordNet o da norme di associazione (in particolare nella struttura scale-free della distribuzione di probabilità dei gradi) perché il modo di estrarre una rete da uno spazio semantico non rende conto della crescita (il parametro growth) di una rete.

Tuttavia, all’interno della nostra classificazione proposta nella Sezione 1.6, le reti complesse estratte dagli spazi semantici non sono metodi alternativi a modelli generati-vi: nonostante si tratti di reti estratte a partire da una rappresentazione computazionale del significato (cfr. Introduzione: i nodi sono vettori), esse vengono estratte a partire da un dataset e modellando una propriet`a semantica basata sul contesto, capace di cattura-re cattura-relazioni sia di tipo sintagmatico che di tipo paradigmatico. Qualunque sia il modo di intendere e classificare le reti complesse estratte da uno spazio semantico, si tratta, quindi, di reti reali e di un approccio data-driven al dominio.

(37)

I problemi teorici posti nell’Introduzione e risollevati in queste considerazioni finali concludono questo capitolo iniziato dando una giustificazione dell’approccio al significa-to dal punsignifica-to di vista della Network Science, nel tentativo di modellare il lessico mentale come un sistema complesso. Questo argomento verr`o ripreso nel capitolo conclusivo, dopo aver svolto le analisi che costituiscono il corpo di questo lavoro, che iniziano dal prossimo capitolo.

(38)

Capitolo 2

Data collection: estrazione di reti da

uno spazio semantico

2.1 Corpora e loro preprocessing

I corpora scelti per questo studio sono Wikipedia in lingua italiana (una sua versione light) e PAIS À[46], una collezione di testi italiani estrapolati dal web. La lunghezza di entrambi i corpora è di 250 milioni di token circa, annotati in formato CoNLL-U e lemma-tizzati. Per quanto riguarda la composizione di Paisà, in particolare, la distribuzione dei testi che lo compongono è sintetizzata nella Figura 2.1. Il fatto che i due corpora siano in parte simili (Paisà contiene pagine di Wikipedia) è coerente con i task che applicheremo in seguito.

A questa fase corrisponde il tentativo di modellare gli elementi di N. `E lecito do-mandarsi che tipo di atomi lessicali rappresentare come nodi. Tale questione si inserisce all’interno di un quadro di lavoro noto come pre-processing del testo, un insieme di tec-niche e metodi di pulizia del testo che si snoda in una sequenza di operazioni

(39)

compren-dente, almeno, la tokenizzazione, il PoS-tagging, lo stemming o la lemmatizzazione. La tokenizzazione è il processo tramite cui si individuano i token di un testo. Il PoS-tagging (PoS, da part of speech, parte del discorso o categoria grammaticale), è il riconoscimento della categoria grammaticale cui il token appartiene (nome, verbo, articolo, aggettivo, etc). Lo stemming consiste nel processo di riduzione di una forma flessa (e.g. un token) nel suo tema (e.g. ciò che resta di una parola tolta la desinenza). La lemmatizzazio-ne consiste, invece, lemmatizzazio-nella riduziolemmatizzazio-ne di una forma flessa lemmatizzazio-nel suo lemma, ovvero la forma canonica di una parola utilizzata nella ricerca in un vocabolario.

Abbiamo deciso - in vista del training nella fase successiva - di utilizzare i lemmi al posto dei lessemi, nonché di usare solo nomi, verbi, aggettivi e avverbi. Tale scelta è giustificata sulla base di argomentazioni di tipo sia teorico che pratico. Per quanto ri-guarda il primo tipo di argomento, quello di maggior interesse verte sulla possibilità di modellare un’unità lessicale che renda conto della maniera in cui l’informazione lessicale è immagazzinata in memoria (i.e., nel lessico mentale). L’unità cognitiva alla base del-l’organizzazione lessicale mentale contiene informazioni riguardanti più livelli di analisi linguistica (cfr. 1.1). Concretamente, in un testo troviamo un insieme di lessemi che si strutturano in frasi grammaticalmente corrette, mentre un lemma ha lo scopo di iden-tificare in una singola forma di citazione il contenuto semantico di una parola di cui i diversi lessemi catturano più tratti morfosintattici, come il genere e il numero nei nomi o il tempo e il modo dei verbi. È indubbio che anche un training effettuato su token rap-presentanti lessemi sia capace di estrapolare il loro significato (cfr. sezione successiva), ma venendo, quindi, al secondo tipo di argomentazione - quello pratico - la scelta dei lemmi risiede nel tentativo di eliminare relazioni inutili tra nodi che rappresentano il singolare e il plurale dei nomi o le differenti forme dei verbi (i.e., relazioni tra due forme

(40)

dello stesso concetto) o anche per distinguere il pi`u possibile il fenomeno dell’omonimia tra le differenti categorie grammaticali (e.g., la stessa forma ortografica per porta come sostantivo singolare e porta come terza persona dell’indicativo del verbo portare).

In sintesi, gli elementi di N devono rappresentare unità concettuali distinte, nella mi-sura in cui a connettersi fra loro sono solo contenuti semantici distinti e non differenti forme dello stesso significato denotativo di una parola che presenta più forme grammati-cali. Per far ciò, utilizziamo i lemmi e non lessemi. Il loro utilizzo non inficia sul modello del linguaggio, a cui interessa quali parole si trovano vicine l’una all’altra perché ne sia catturato il significato. Perciò, il secondo importante passo del pre-processing è elimina-re le stopwords (i.e., parole non semanticamente piene) per teneelimina-re solo lemmi di nomi, verbi, aggettivi e avverbi.

Figura 2.1: Composizione del corpus Pais`a

2.2 Modello del linguaggio

Word2vec `e un insieme di tecniche per creare word embedding. Uno spazio semanti-co `e uno spazio vettoriale V in R, che ha per base l’insieme dei termini t1, t2, ..., tn del

(41)

vocabolario T e dimensione |T |, la lunghezza del vocabolario. Le parole vengono ri-prodotte come vettori one-hot (dove 1 si trova alla posizione di ti in T ). In uno spazio

di embedding le features vengono forzate all’interno di uno spazio ridotto per risolve-re il problema della rapprisolve-resentazione sparsa dei vettori. Un vettorisolve-re v(ti)di dimensione

R|T | viene forzato all’interno di uno spazio di dimensione Rk_{, con k |T |. Usiamo la}

funzione di embedding Embed : R|T |_{−→ R}k_:

Embed(v(ti)) = e(t1)

I due modelli word2vec sono SkipGram e CBoW, che predicono un contesto da una parola (SkipGram) o una parola da un contesto (CBoW).

Per ogni parola target wtdobbiamo massimizzare la seguente funzione in SkipGram:

J =P

−n≥j≥n,6=0logp(wt+j|wt)

e la seguente in CBoW:

J = logp(wt|wt − n, ..., wt + 1, ...wt + n)

Per questo studio abbiamo scelto un modello standard in letteratura, Skip-Gram with Negative Sampling (SGNS)[47], nella sua implementazione in Python con Gensim[48]. La Figura 2.2 mostra un’architettura molto semplificata dei due modelli, tesa a mostra-re esclusivamente in che maniera il contesto influisce sulla pmostra-redizione dei valori della distribuzione. Per semplicit`a, prendiamo in esame solamente SkipGram. La sua architet-tura consiste nella generazione di un primo layer (embedding layer) che produce word embedding himoltiplicando il vettore one-hot per una matrice di embedding W0 di

di-mensione |T |xk. Questa rappresenta l’hidden layer della rete neurale. Generando una seconda matrice di embedding W1 di dimensione kx|T | e un’altra serie di embedding u,

(42)

viene applicata su questi ultimi una funzione softmax1_{che trasforma gli embedding u} i

in una distribuzione di probabilit`a:

yi = P exp(ui) j∈Texp(uj)

In sostanza, ogni hi rappresenta l’embedding di una parola, mentre ui

rappresen-ta l’embedding di una parola quando quesrappresen-ta appare in un contesto. In questo lavoro, i nodi equivarranno alla riproduzione del primo tipo di word embedding, ma sarebbe interessante approfondire l’argomento relativamente a reti complesse generate da altre rappresentazioni di embedding.

Per quanto riguarda l’implementazione di tale modello in Gensim[48], `e possibile modificare i seguenti parametri principali:

• size: definisce la dimensione k dello spazio di embedding;

• window: definisce la lunghezza della finestra contestuale, ovvero il numero delle nparole successive e precedenti alla parola target ti;

• min count: stabilisce |T |, eliminando dal training le parole che nel corpus non compaiono almeno le n volte stabilite dal valore del parametro;

• negative: solo con il metodo Negative Sampling, stabilisce quante m parole devono essere utilizzate per calcolare la distribuzione di probabilit`a nella funzione softmax yi = P exp(ui)

j∈Eexp(uj), dove E = m;

Abbiamo settato size = 200, window = 10, negative = 10 per entrambi i corpora, mincount = 10per Wikipedia e min count = 200 per PAIS `A. Il motivo di questa scelta

1_{Una funzione softmax permette di comprimere vettori di valori reali in vettori di valori compresi tra}

(43)

consiste nell’evitare una sovrapposizione eccessiva dei due vocabolari, dal momento che PAIS `A collezione anche pagina di Wikipedia. Riducendo il vocabolario abbiamo pensato di diverfisicare i corpora.

Figura 2.2: Le architetture SkipGram (a sinistra) e CBoW (a destra)

2.3 Estrazione delle reti

Un metodo di estrazione di rete stabilisce il criterio secondo cui ogni nodo stabilisce i propri vicini. Uno di questi `e l’-method[41], che permette di connettere i vettori tra loro se e solo il valore della loro similarit`a del coseno supera una certa soglia :

∃ e = (u, v) ∈ L sse sim(~u, ~v) ≥

Applicato a questo dominio, Lmax corrisponde alla totalit`a delle distanze tra

tut-te le coppie di vettori. Si ha bisogno, quindi, di un metodo che estragga un grafo con L Lmaxin cui L contenga forti relazioni di similarit`a semantica. Col metodo appena

(44)

introdotto, ordine e grandezza della rete sono vincolate dal valore posto come soglia. Ipotizzando di aver posto simτ pari a un valore che superi il pi`u alto valore di similarit`a

del coseno di un vettore v1con tutti gli altri vettori della rete, il vettore in questione sar`a

escluso dalla rete. Ne consegue che N 6= |T |. Servirebbe identificare un criterio per il valore di . Questo sar`a discusso nel capitolo successivo.

Per quanto riguarda i limiti epistemologici riguardo alla validit`a delle reti estratte da uno spazio semantico nel riprodurre una reale struttura del significato, la discussione `e aperta.

Alcuni autori sono critici nei confronti di un modello di rete a partire dagli spazi semantici perché la sua estrazione (e.g., l’-method), non tiene conto della sua crescita (i.e., growth nel modello BA)[41]. Altri autori, invece, sostengono come la distribuzione di probabilità dei gradi di una rete semantica complessa debba seguire una power-law troncata, in particolare perché i nodi non possono crescere all’infinito, ed evidenziano come gli spazi semantici riescano a simulare tale realtà[6].

Un secondo metodo di estrazione di rete è il cs-method[6], e consiste nello stabili-re i vicini di ogni nodo sulla base del valostabili-re più piccolo del rapporto cumulativo della similarità del coseno nel momento in cui oltrepassa una determinata soglia R:

P v∈V N_i sim(~u,~v) P v∈V sim(~u,~v) ≥ R dove |VN

i |`e il numero dei vicini del nodo u, in breve k = |ViN|.

In questo caso, N ' |T |. Siamo vincolati a un valore R ma non alla distribuzione di similarit`a stessa. Per un alto valore di R, aumentano le relazioni al numeratore che servono a oltrepassare la soglia, quindi i nodi avranno pi`u connessioni. In sintesi, in entrambi i metodi, si lavora con un numero di nodi non infinito da cui si cerca di far emergere una rete di grandezza variabile.

(45)

Venendo a questo lavoro, la metrica di similarità utilizzata è la similarità del coseno:

sim( ~v1, ~v2) = _kvv~₁1_kkv· ~v2₂_k

Sono state estratte quattro reti utilizzando -method, con due tagli = 0.5 e = 0.65. Come intuibile nella Figura 2.3, la parte più densa della distribuzione di similarità si con-centra nei valori compresi tra 0 e 0.4, escludendo i valori minori di 0. Ciò significa, innanzitutto, che non tutti i vettori possono essere simili con tutti, e questo può essere un punto di partenza verso una giustificazione del valore di . Il metodo del taglio prevede che una struttura complessa emerga escludendo un corposo numero di relazioni non se-manticamente simili tra loro, agevolando il comportamento emergente di una struttura del significato composta esclusivamente da associazoni tra coppie di parole semantica-mente simili. In questo lavoro abbiamo deciso di concentrarci maggiorsemantica-mente su finalità pratiche, vale a dire che una rete di grandezza maggiore è più difficile da analizzare per i task che ci proponiamo di affrontare - community discovery, in particolare. Perciò, le ragioni del taglio acquistano senso solo da questa prospettiva.

(46)

Figura 2.3: Distribuzione dei valori di sim(~u,~v) con SGNS sul corpus Paisa’. Il nu-mero di relazioni comprese nei seguenti intervalli è un indice di similarità del corpus: 0.0=70046466, 0.1=125049680, 0.2=52766555, 0.3=11577928, 0.4=2260289, 0.5=459875, 0.6=96871, 0.7=19293, 0.8=2707, 0.9=210. Significa, ad esempio, che poco meno di 300 relazioni possono essere usate indistintamente negli stessi contesti. Per essere chiari, questo non è necessariamente indice di sinonimia o di relazioni gerarchica: in un inter-vallo di similarità pari a 0.9 è presente una connessione come padre-madre. Questo è un indizio di ciò che ci aspettiamo di trovare estraendo una struttura di significato ta-gliandole relazioni comprese sotto un certo intervallo di similarità: parole che possono essere sostituite negli stessi contesti. Cosa emerge analizzando la struttura globale e le comunità delle reti?

(47)

Capitolo 3

Network analysis

In questa sezione saranno analizzate le proprietà globali delle reti estratte. Ci concen-treremo su un’analisi generale delle proprietà che determinano la complessità delle reti, sulla distribuzione di probabilità dei gradi e sul forte grado di assortatività rispetto al grado osservato in tutte le reti estratte.

3.1 Invarianza di scala, propriet`a small-world,

assor-tativit`a

In Figura 3.1 mostro la distribuzione di probabilità dei gradi delle differenti reti. Con-siderando la letteratura corrente, non è chiaro se le reti estratte dagli spazi semantici presentino l’invarianza di scala, ovvero se la distribuzione di probabilità dei gradi segua una legge di potenza.

In [41] viene fatto presente come ci`o non sia possibile e che le reti siano meglio descritte da una distribuzione esponenziale, mentre in [6] viene mostrato come le di-stribuzioni possano presentare l’invarianza di scala ma con un taglio esponenziale (la

(48)

distribuzione non `e una power law ma una truncated power law). Infine, in [45] viene ag-giunto che in alcuni casi le reti possano essere descritte da una distribuzione lognormale. In sintesi, non sono presenti dati certi a riguardo.

Ho deciso di replicare le analisi utilizzando la libreria powerlaw[49] in Python. Pri-ma di tutto, inferisco il parametro λ e a partire da quale classe di gradi l’invarianza di scala viene mostrata (cfr. Tabella 3.2. Nelle reti estratte da Wikipedia il parametro λ è minore di 2 nelle reti estratte da Wikipedia, ma il comportamento power law è visibile sulla quasi totalità della distribuzione, mentre l’invarianza di scala nelle reti estratte da Paisà è visibile solo nell’ultima parte della distribuzione, nel taglio minore, e da metà distribuzione, nel taglio maggiore. Tuttavia, l’obiettivo principale è quello di capire qua-le modello di distribuzione fitta meglio i dati. Per farlo, powerlaw si serve del test del rapporto di verosimiglianza (LR-test). È un test comparativo che valuta la probabilità di due distribuzioni di generare campioni dai dati empirici basandosi sulla funzione di ve-rosimiglianza massima di ciascuna distribuzione. Il valore di R è la log-likelihood ratio tra due distribuzioni: è positivo se la prima distribuzione descrive meglio i dati, negati-vo se è la seconda distribuione a farlo. Le distribuzioni e i risultati sono mostrati nella Figura 3.2 e nellaTabella 3.1. I confronti sono stati effettuati tra le distribuzioni power law, truncated power law, esponenziale e lognormale.

Dai dati emerge che la distribuzione power law non è la più indicata a fittare i dati empirici. In generale, le più indicate sembrano essere la truncated power law e la lognor-male. Nel dettaglio: per quanto riguarda Wikipedia con il taglio a 0.5, dal grafico emerge che la distribuzione che meglio descrive i dati sia la truncated power law, ma in realtà sia quest’ultima sia la distribuzione lognormale potrebbero essere indicate a rappresen-tarla (infatti, in TPL vs. logNorm KS=1.09 ma p=0.27); per quanto riguarda Wikipedia

(49)

Figura 3.1: Distribuzione di probabilità dei gradi, in senso orario dall’alto a sinistra, Wikipedia = 0.50, Wikipedia = 0.65, Paisà = 0.50, Paisà = 0.65

con il taglio a 0.65, la situazione è simile ma i risultati riguardanti la significatività del-la truncated power del-law rispetto aldel-la lognormale è più forte (TPL vs logNorm KS=1.99 e p=0.04); per le reti estratte dal corpus Paisà la situazione è identica: la distribuzione power law non è il modello adatto rispetto alla lognormale e alla truncated power law, per una propensione verso quest’ultima.

Nella Tabella 3.2 mostro un’analisi generale per quattro reti estratte con tagli dif-ferenti. È chiaro, sia nel corpus Wikipedia che in Paisà, come un taglio più alto non inficia sulla presenza di una componente gigante nonostante frammenti la rete in più componenti. Verifichiamo, inoltre, come già anticipato, che N si riduce con i tagli più alti, escludendo una serie di nodi di cui nella successiva analisi qualitativa cercheremo