Sintesi automatica di una metrica di similarità tra stringhe tramite tecniche di computazione evolutiva

Università degli Studi di Trieste
Dipartimento di Ingegneria e Architettura
Corso di Laurea Magistrale in
Ingegneria Informatica
Tesi di Laurea Magistrale
Sintesi automatica di una metrica di
similarità tra stringhe tramite tecniche di
computazione evolutiva
Laureando:
Michele Furlanetto
Matricola IN1400049
Relatore:
Prof. Eric Medvet
Correlatore:
Prof. Alberto Bartoli
ANNO ACCADEMICO 2014 – 2015

Ai miei genitori,
ai miei fratelli
e alla mia ﬁdanzata Laura

Indice
Introduzione 1
1 Stato dell’arte 2
2 Metodo proposto 4
2.1 Algoritmi Genetici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Processo evolutivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Evoluzione Grammaticale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Grammatica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Macchina Virtuale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Parametri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Procedura sperimentale 9
3.1 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Distanza di Levenshtein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2 Distanza di Jaccard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Validazione incrociata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3.1 Indici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 Linguaggi e tecnologie usate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Risultati sperimentali 13
4.1 Popolazione di 50 individui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Popolazione di 100 individui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Analisi dei dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3.1 Confronto con algoritmi noti . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Conclusione 20
Appendici 21
A Grammatica usata 22
B Istruzioni della Macchina virtuale 24
C Listato di Wagner-Fisher 26
D Listato di Jaccard 28
iii

Introduzione
Il tema di estrarre informazioni rilevanti per un utente, da testi non strutturati ed estesi, ha
suscitato nel corso degli anni un notevole interesse da parte di vari gruppi di ricerca in tutto il
mondo. Il problema affrontato è quello di fornire all’utente un sistema per estrarre da un documento
tutti i dati di suo interesse, individuandoli mediante esempi forniti dall’utente stesso. In pratica,
l’utente potrebbe essere intenzionato a estrarre tutte le date presenti in un romanzo; potrebbe
quindi selezionarne alcune e poi lasciare che questo strumento selezioni tutte le altre.
La soluzione proposta è quella di fare uso di un estrattore basato sulla similarità tra stringhe,
ovvero di un particolare strumento che possa selezionare dal testo in input tutte quelle stringhe che
siano simili agli esempi forniti. Pertanto, il problema di estrazione è stato ridotto all’applicazione
di una opportuna metrica di similarità. Tuttavia, data la dualità dei concetti di distanza e di
similarità, per praticità è stato trattato il problema dal punto di vista della distanza. L’estrattore,
dunque, si occuperà di estrarre tutte quelle stringhe la cui distanza media dagli esempi non supera
una certa soglia.
Il nucleo di questo progetto è definire una nuova metrica adatta all’estrazione di informazioni; in
particolare, la metrica viene sintetizzata mediante tecniche di calcolo evolutivo, che ben si adattano
al problema.
La trattazione approfondita degli argomenti sopra citati è stata suddivisa nei seguenti capitoli:
• Nel Capitolo 1 vengono elencati e brevemente descritti i lavori già condotti sull’uso di metriche
di similarità o dissimilarità tra stringhe;
• Nel Capitolo 2 viene descritto il metodo proposto, ovvero le tecniche utilizzate per ottenere
il risultato voluto. Verranno quindi trattate brevemente le tecniche di GA e di GE, viene
illustrata la grammatica scelta e verranno elencati i parametri utilizzati;
• Nel Capitolo 3 viene approfondita la procedura sperimentale effettuata per elaborare i dati a
disposizione. Verranno illustrate le distanze di Levenshtein e di Jaccard e la loro prestazione
nella nostra casistica. Inoltre viene spiegato come i risultati ottenuti sono stati analizzati;
• Nel Capitolo 4 vengono mostrati e analizzati i risultati ottenuti;
• Nel Capitolo 5 vi è la conclusione.
1

Capitolo 1
Stato dell’arte
Al fine di inquadrare al meglio questo progetto di tesi, in questa sezione viene discussa la letteratura
esistente riguardo l’uso di metriche di similarità o dissimilarità tra stringhe.
Le seguenti proposte descrivono pertanto lo stato dell’arte per il problema dell’estrazione di
entità da flussi di testo non strutturati, per l’uso di metriche di similarità (o dissimilarità) tra
stringhe per nome dell’entità corrispondente e attività di rilevamento dei duplicati e precedenti
tentativi di evolvere metriche di (dis)similarità tra stringhe specifiche per un dato problema.
In [1], gli autori affrontano il problema di string matching su nomi e record e confrontano
metodi che impiegano varie metriche di distanza tra stringhe.
Il lavoro in [2] propone una nuova metrica di similarità tra stringhe specificamente pensata per
i problemi di allineamento di ontologie e significativamente più efficace delle metriche di similarità
tradizionali.
Metriche di similarità tra stringhe vengono impiegate anche per il rilevamento di duplicati (ad
esempio all’interno di registrazioni nei database); l’opera in [3] mostra come alcune metriche di
similarità tra stringhe appositamente addestrate per il rilevamento dei duplicati, possano essere
migliori in termini di precisione di rilevamento rispetto alle tradizionali metriche di similarità.
Metodi basati sulla (dis)similarità tra stringhe possono essere adottate anche per la ricerca di
nomi all’interno di un dizionario: il lavoro in [4] addestra una metrica di similarità tra stringhe
per nomi di geni/proteine utilizzando la regressione logistica.
I testi sopra citati evidenziano che i metodi, implementati con metriche di similarità tra stringhe
(o di dissimilarità), migliorano la loro efficacia quando sono abbinati a metriche sviluppate per uno
specifico dominio del problema.
Questo tema ha suscitato notevole interesse in diversi gruppi di ricerca nel corso del tempo,
spingendoli a studiare e proporre sempre nuove soluzioni. Il lavoro in [5] sintetizza un estrattore,
nella forma di espressione regolare, da esempi del comportamento desiderato. Il metodo proposto
per prima cosa seleziona un sottoinsieme di caratteri e simboli con un approccio statistico e poi
sintetizza l’automa che alla fine viene convertito in un’espressione regolare.
Sono da segnalare, poi, le proposte [6], [7], [8] e [9] che considerano il problema di sintetizzare
un estrattore, in forma di espressione regolare, in modo automatico partendo da esempi del com-
portamento di estrazione previsto. A tal fine, le opere citate adottano tecniche di programmazione
genetica (GP).
Infine, una recente proposta di estrazione di informazioni da esempi [10] descrive un sofisticato
framework per estrarre automaticamente molteplici campi nei documenti semi-strutturati.
2

1 – Stato dell’arte
Considerando quanto detto, il metodo proposto è una sorta di rielaborazione degli studi già
eﬀettuati; viene impiegato, infatti, un metodo di evoluzione grammaticale che impara automa-
ticamente una nuova metrica di distanza tra stringhe, speciﬁcamente pensata per l’estrazione di
stringhe aventi caratteristiche strutturali comuni.
3

Capitolo 2
Metodo proposto
Il metodo proposto prevede la sintesi di una nuova metrica utilizzando tecniche di calcolo evo-
luzionistico. Nello specifico viene utilizzata la tecnica di evoluzione grammaticale, ovvero una
particolare applicazione degli algoritmi genetici. Nel corso del capitolo verrà fatta, quindi, una
breve introduzione di questi concetti e verranno illustrati i parametri utilizzati.
2.1 Algoritmi Genetici
Gli algoritmi genetici (GA) sono una particolare tecnica di ottimizzazione che pone le proprie basi
nella teoria della selezione naturale di Darwin. Ogni algoritmo genetico opera su una popolazione
di individui, ciascuno dei quali è caratterizzato dal proprio cromosoma. Ogni cromosoma è una
sequenza di geni, cioè di numeri binari.
Ogni individuo rappresenta una soluzione al problema in esame e ha una fitness, ossia un valore
numerico che indica la qualità della soluzione [11].
Un algoritmo genetico inizia la propria esecuzione con una popolazione di cromosomi generati
casualmente; successivamente applica un processo di selezione basato sulla fitness e uno di ricombi-
nazione, per produrre una nuova popolazione per la nuova generazione. Iterando questa procedura,
una sequenza di generazioni successive evolve e la fitness media dei cromosomi tende a migliorare
fino a che viene raggiunta una condizione, decisa in base al problema o alla precisione che si vuole
ottenere, per cui fermare l’iterazione.
Vi sono diverse strategie per quanto riguarda la selezione dei cromosomi destinati a sopravvivere
e a ricombinarsi.
Il metodo più utilizzato è la Roulette Wheel Selection, in cui ad ogni cromosoma viene assegnata
una probabilità di selezione proporzionale al suo valore di fitness relativo, ovvero comparato al resto
della popolazione [12].
Altri metodi di selezione sono: Random Stochastic Selection, Tournament Selection e Trun-
cation Selection. La Random Stochastic Selection individua esplicitamente ogni cromosoma un
numero di volte pari alla sua aspettativa di essere selezionato con il metodo Roulette Wheel Se-
lection. Tournament Selection preseleziona per prima cosa n cromosomi estraendoli casualmente
(con probabilità uniforme) dalla popolazione, per poi far selezionare quello con un valore di fit-
ness migliore. Infine, Truncation Selection seleziona alcuni cromosomi dalla popolazione dopo aver
eliminato quelli con i valori di fitness peggiori [11].
I principali meccanismi di ricombinazione genetica sono mutazione e crossover. La mutazione
prevede l’alterazione di alcuni dei geni del cromosoma a cui è applicata; il crossover, invece, scambia
parte del materiale genetico tra due individui [13]. Esistono due tipi di crossover: crossover a 1
4

2 – Metodo proposto
punto e crossover a 2 punti. Nel primo caso, un singolo punto di crossover viene selezionato su
entrambi i cromosomi e tutti i geni oltre a quel punto vengono scambiati. Nel secondo caso, invece,
i punti di crossover sono due e i geni scambiati sono quelli compresi tra i due punti.
In questo lavoro, GA è stata utilizzata per sintetizzare una nuova metrica di distanza tra
stringhe, generando l’algoritmo che la calcola. La funzione di fitness da minimizzare viene definita
nella sottosezione 2.1.2. Inoltre, GA viene affiancata dalla tecnica di evoluzione grammaticale
(sezione 2.2) per assicurare la generazione di algoritmi sintatticamente corretti.
2.1.1 Processo evolutivo
Il processo di evoluzione effettuato da GA è diviso in più fasi, dette generazioni: all’inizio di ogni
generazione vi è una popolazione iniziale P di n individui e al termine viene creato un insieme P
che diventerà la popolazione iniziale della generazione successiva.
Per generare P si eseguono queste operazioni:
1. viene costruito un insieme C di coppie (i, fi), dove i ∈ P e fi è il valore di fitness di i.
Normalmente, la funzione di fitness viene valutata su un insieme Es di esempi;
2. viene costruito un insieme Of di individui, applicando no volte a P un selettore So, che può
utilizzare C per la selezione;
3. viene costruito un insieme S di individui, applicando ns = n − no volte a P un selettore Ss,
che può anch’esso utilizzare C per la selezione;
4. viene costruito un insieme Of di individui applicando le operazioni genetiche di
• mutazione. Ogni gene di ogni individuo i di I ha una probabilità pm di essere alterato;
se ciò avviene, i viene inserito in Of ;
• crossover a due punti. Viene creato un insieme M di individui, selezionati casualmente
da I con probabilità pc. Successivamente, vengono formate (no − Of )/2 coppie di
individui di M. Infine, da ogni coppia vengono creati, tramite crossover, due nuovi
individui m1 e m2 che vengono inseriti in Of .
5. viene costruito l’insieme P = Of ∪ S.
Si ha così una nuova popolazione avente lo stesso numero di individui della precedente.
Il numero di generazioni g può essere deciso arbitrariamente a priori; tuttavia possono essere
fissati dei criteri di stop più complessi che tengano in considerazione altri parametri, come ad
esempio il tempo di esecuzione totale o il non miglioramento della fitness per diverse generazioni.
2.1.2 Fitness
La funzione di fitness f è stata definita in questo modo:
sia M l’insieme degli esempi di stringhe da estrarre, N l’insieme di esempi di stringhe da non
estrarre e d la distanza tra stringhe da applicare; definiamo ora
Om = {y : ∀a, b ∈ M, y = d(a, b)};
Et = {y : ∀a ∈ M, ∀b ∈ N, y = d(a, b)};
f1 = {o ∈ Om : o ≥ mine∈Et
e} + {e ∈ Et : e ≤ maxo∈Om
o}
f2 = {o ∈ Om : o ≥ 10%Et} + {e ∈ Et : e ≤ 90%Om}
f =
f1 + f2
2 · ( Et + Om )
Dove 10%E e 90%O indicano rispettivamente il primo e il decimo decile dell’insieme in argo-
mento. La funzione di fitness proposta è la media aritmetica di due componenti che misurano
entrambe il grado di separazione tra due collezioni di numeri:
5

• il multiinsieme delle distanze ottenute confrontando due stringhe da estrarre;
• il multiinsieme delle distanze ottenute confrontando una stringa da estrarre con una da non
estrarre.
Più precisamente, f1 considera le due collezioni nella loro totalità, mentre f2 penalizza i valori
outlier escludendo il primo e il decimo decile di entrambi i multiinsiemi. La somma f1 + f2 viene
poi normalizzato nell’intervallo [0, 1], in modo da semplificare il confronto tra le fitness di metriche
apprese su dataset diversi. In questo modo con f = 1 si ha la perfetta sovrapposizione dei due
insiemi Om ed Et, oppure la loro netta separazione ma con Et < O; con f = 0, invece, si ha la
perfetta separazione dei due insiemi, ossia ∀o ∈ Om, e ∈ Et; o < e.
Da ciò si deduce che più l’individuo è idoneo a risolvere il problema, minore è il valore della
sua fitness.
2.2 Evoluzione Grammaticale
Come già accennato nella sezione 2.1, per assicurare la generazione di algoritmi validi si è fatto
ricorso all’evoluzione grammaticale (GE) [14].
Tale approccio effettua il processo evolutivo su cromosomi di lunghezza o fissa o variabile, in cui
ogni gene è rappresentato da un bit. In particolare, viene utilizzato un procedimento di mappatura
per generare un programma in un qualunque linguaggio, utilizzando i valori dei geni per selezionare
le regole di produzione di una grammatica generativa espressa nella forma di Backus-Naur.
In generale, si definisce grammatica la tupla (T, NT, R, s), in cui T è l’insieme dei simboli
terminali, NT l’insieme dei simboli non terminali, R l’insieme delle regole di produzione e s l’ele-
mento di NT da cui inizia la produzione. Ogni regola di produzione descrive precisamente come
trasformare i simboli non-terminali in terminali all’interno di una stringa. In particolare, la forma
di Backus-Naur definisce la simbologia per una descrizione rigorosa delle regole di R. Il risultato
è la costruzione di un programma sintatticamente corretto che può essere valutato da un funzione
di fitness.
Il processo di mappatura avviene come segue. Per prima cosa il cromosoma viene spezzato in
gruppi di 8 bit, e ogni gruppo viene tradotto in un numero intero detto codone e appartenente
all’intervallo [0, 255]. Poi, quando una qualunque regola di produzione della grammatica ha la
possibilità di scegliere tra n alternative, viene letto dal cromosoma un codone c e viene utilizzata
l’alternativa numero i = c mod n. Infine, quando capita una nuova possibilità di scelta, viene
letto il codone successivo. Questo procedimento continua fino a che viene attraversato tutto il
cromosoma; a quel punto si riutilizza il primo codone e tutti i successivi [14].
Il vantaggio di utilizzare una grammatica sta nel superare il problema della closure, ossia della
generazione possibile generazione di programmi non validi (sintatticamente scorretti). Inoltre, dati
due individui validi, GE assicura che le operazioni di GA producano un nuovo individuo valido.
2.2.1 Grammatica
La grammatica di supporto, riportata in appendice A, è stata scelta in modo da essere piuttosto
compatta, ma che permetta al contempo di esprimere gli algoritmi di Levenshtein e di Jaccard in
un formalismo ragionevole (pseudocodice).
2.2.2 Macchina Virtuale
Per aver modo di valutare gli algoritmi espressi mediante la grammatica scelta, è stata implemen-
tata una macchina virtuale capace di eseguirli.
6

La macchina virtuale permette la creazione, l’accesso e la modifica di variabili di tipo float e
di vettori di float. Per tale motivo, le stringhe in input vengono trattate come vettori di numeri,
in cui ogni numero rappresenta il codice UTF-8 del carattere corrispondente.
Ogni variabile è visibile nello scope in cui è dichiarata e in tutti gli scope in esso contenuti. Le
variabili sono riferite per mezzo di indici: ogni volta che si vuole riferire ad una variabile, viene
costruita dinamicamente la lista delle variabili visibili. Non sono visibili, invece, le variabili definite
negli scope contenuti nello scope di riferimento. Ad esempio, sia S0 uno scope in cui viene definita
una variabile v0 e sia S1 uno scope contenuto in S0, ma definito dopo v0; siano v1 e v2 due variabili
definite all’interno di S1. In questo caso, all’interno di S1 si potranno riferire le variabili v0, v1 e
v2 rispettivamente con gli indici 0, 1 e 2. All’interno di S0, però, non sono accessibili le variabili
v1 e v2 e dunque, la lista delle variabili visibili sarà formata unicamente da v0.
Lo stesso meccanismo vale anche per i vettori.
La macchina virtuale non pone limitazioni al numero di variabili o di vettori allocabili, anche
se limita la dimensione massima dei vettori in modo proporzionale alla lunghezza delle stringhe
da valutare. Questo limite è stato imposto per evitare la saturazione della memoria nella reale
macchina di calcolo.
All’interno della macchina virtuale non è presente un meccanismo di garbage collection espli-
cito, sebbene sia presente in modo indiretto dal linguaggio di programmazione utilizzato per lo
sviluppo della macchina virtuale.
In appendice B vengono spiegate brevemente le operazioni compiute dalla macchina virtuale
per ogni simbolo sintattico della grammatica.
2.3 Parametri
Ci sono molte variabili che possono influire nel sistema proposto. Primi tra tutti vi sono i parametri
relativi a GE e a GA:
• dimensioni del cromosoma. Si è scelto di utilizzare un cromosoma a dimensione fissa
pari a 350 geni, valore scelto in modo tale da essere almeno sufficiente a generare l’equiva-
lente dell’algoritmo di calcolo della distanza di Levenshtein (sottosezione 3.2.1) e di Jaccard
(sottosezione 3.2.2);
• numero di offspring (no), pari al 60% della popolazione;
• selettori per GA. I selettori utilizzati sono Tournament Selection a 3 individui per scegliere
gli offspring e una combinazione di Truncation e Tournament Selection, rispettivamente a 1
e a 4 individui per i rimanenti;
• operazioni genetiche. Le operazioni genetiche applicate sono mutazione (pm 0.02%) e
crossover a due punti (pc 10%).
• numero di generazioni. In base alle sperimentazioni preliminari, è stato ritenuto sufficiente
utilizzare g pari a 200 generazioni;
• individui per generazione. Sono state effettuate più esecuzioni con questo parametro pari
a 50 e 100 individui;
7

• numero di esempi. Per ridurre il tempo impiegato dalla valutazione della fitness, sono
state effettuate più esecuzioni variando il numero di esempi np tra i valori 10, 25 e 50.
In secondo luogo abbiamo parametri relativi alla particolare implementazione del sistema:
• limite sulla complessità statica delle soluzioni. Per motivi tecnici di implementazione
della grammatica1
è stato introdotto un parametro detto ricorsione massima che agisce da
limite non vincolante sul numero massimo di funzioni annidate. Superata la soglia di 40
chiamate ricorsive, le regole descritte nel listato 2.1 sostituiscono le corrispettive presenti
nella grammatica;
• limite sulla complessità delle strutture dati. Durante la computazione di una distanza
vi è un limite alla dimensione massima di ogni vettore allocato ed è pari a 10 · l1 · l2, dove l1
è la lunghezza della prima stringa in input e l2 è la lunghezza della seconda;
• limite sul tempo di esecuzione. Per ridurre il tempo dedicato all’apprendimento della
distanza, è stato aggiunto un limite di 40000 istruzioni eseguibili durante una sola esecuzione.
<InstructionExpression > ::= <CreateVariable>
<ValueReturningFunction> ::= <Constant>
<RowOfBlockCode> ::= <InstructionExpression >
Listato 2.1. Grammatica ridotta
1Il metodo Java che effettua la mappatura del cromosoma in un algoritmo effettua numerose chiamate ricorsive,
causando la rapida saturazione dello heap riservato dalla Java Virtual Machine.
8

Capitolo 3
Procedura sperimentale
3.1 Dataset
Il dataset a disposizione è composto da dati provenienti da 8 task di estrazione già noti in lettera-
tura1
e rappresentano ciascuno uno scenario di utilizzo diverso. Ogni task è formato da un testo t e
da un insieme X di sottostringhe di t, che sono le estrazioni che si vuole fare da t. I testi utilizzati
sono:
• Bills-Date, un insieme di leggi del congresso statunitense e da cui vanno estratte le date [8];
• Email-Phone, un insieme di email da cui vanno estratti i numeri telefonici [9], [8], [15], [16];
• HTML-href, un insieme di pagine web da cui vanno estratti i valori degli attributi href[17];
• Log-IP, un insieme di linee di log create da un firewall e da cui vanno estratti indirizzi IP
[9], [8];
• Log-MAC+IP, un insieme di linee di log create da un firewall e da cui vanno estratti
indirizzi IP e indirizzi MAC;
• Twitter-URL, un insieme di messaggi provenienti da Twitter da cui vanno estratti gli URL
[9], [8];
• Web-URL, un insieme di pagine web (in HTML) da cui vanno estratti gli URL [9], [8], [16];
• Wiki-CapitalizedSequences, un insieme di pagine di Wikipedia da cui vanno estratte le
sequenze di due o più parole che inizino con la maiuscola.
Per comprendere quanto segue è necessario introdurre il processo di tokenizzazione. Partendo
da una stringa s e da un insieme Xt di sottostringhe di s, la tokenizzazione individua quell’insieme
S di separatori che, applicati alla stringa s, riescono a massimizzare il numero di sottostringhe che
corrispondono esattamente agli esempi forniti. Per far ciò, costruisce l’insieme S0 inserendo tutti
quei caratteri che sono immediatamente precedenti o immediatamente successivi ad ogni esempio,
li ordina per occorrenza e infine itera i seguenti passi iniziando da i = 1:
1. viene costruito l’insieme Si dei primi i caratteri di S0;
1Si citano, a titolo di esempio, solo alcuni dei paper che utilizzano i task descritti.
9

3 – Procedura sperimentale
2. viene costruito l’insieme Ti dei token, ovvero delle sottostringhe ottenute separando s con i
separatori contenuti in Si.
L’ultima fase del procedimento di tokenizzazione consiste nell’assegnare S := Si∗ , dove i∗
=
argmaxi ||Ti ∩ X||.
Come già accennato, il dataset utilizzato è composto da dati provenienti dai task sopra elencati.
Nello specifico, da ogni task si ottiene una coppia c = (P, N) di insiemi di sottostringhe di t. P
rappresenta l’insieme di stringhe da estrarre ed è ottenuto scegliendo a caso (senza ripetizioni) nP
elementi di X tra quelli che appaiono nella prima metà di t. N rappresenta, invece, l’insieme di
stringhe da non estrarre ed è ottenuto così:
1. si genera S mediante il processo di tokenizzazione, utilizzando t e X;
2. si suddivide la prima metà di t con S ottenendo un insieme di sottostringhe T;
3. N è formato scegliendo a caso (senza ripetizioni) nP elementi di T tra quelli che non si
sovrappongono agli elementi in X.
Ogni coppia c = (P, N) forma il dataset di apprendimento relativo al task. Queste coppie verranno
usate per calcolare la fitness durante il processo di evoluzione.
Infine, per ogni task viene ottenuta una seconda coppia c = (P , N ), utilizzando lo stesso
procedimento, ma applicato alla seconda metà di t. L’insieme delle coppie c è definito dataset di
validazione e il suo uso viene spiegato in sezione 3.3.
3.2 Baseline
Per poter avere un metro di paragone, sono stati descritti, utilizzando il linguaggio definito dal-
la grammatica scelta, gli algoritmi che calcolano le distanze di Levenshtein e di Jaccard. Suc-
cessivamente, sono stati individuati dei cromosomi che possano essere mappati da GE nei due
algoritmi.
3.2.1 Distanza di Levenshtein
La distanza di Levenshtein è il numero minimo di operazioni di inserzione, cancellazione e sostitu-
zione di caratteri che trasforma la stringa a nella stringa b e viene calcolata mediante l’algoritmo di
Wagner-Fisher [18]. Il cromosoma di tale algoritmo consta di 166 geni ed è riportato nel listato 3.1.
Affinché venga mappato come previsto è necessario impostare un valore di ricorsione massima di
almeno 35 chiamate: in tal caso il listato risultate è visibile in appendice C.
1 , 1 , 2 , 7 , 0 , 0 , 0 , 1 , 1 , 3 , 7 , 0 , 2 , 0 , 6 , 0 , 2 , 1 , 0 , 0 , 1 ,
0 , 0 , 1 , 1 , 2 , 7 , 0 , 0 , 0 , 1 , 1 , 3 , 7 , 0 , 1 , 1 , 3 , 7 , 0 , 2 ,
0 , 4 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 6 , 0 , 3 , 0 , 0 , 2 , 1 , 0 , 0 , 0 , 1 ,
0 , 4 , 0 , 6 , 0 , 0 , 3 , 1 , 0 , 1 , 0 , 1 , 6 , 0 , 1 , 1 , 0 , 0 , 0 , 6 ,
0 , 3 , 1 , 0 , 1 , 6 , 0 , 2 , 3 , 1 , 0 , 1 , 0 , 1 , 0 , 6 , 0 , 3 , 1 , 0 ,
1 , 5 , 2 , 6 , 0 , 2 , 1 , 0 , 1 , 0 , 1 , 5 , 2 , 6 , 0 , 3 , 3 , 1 , 0 , 1 ,
0 , 1 , 0 , 1 , 2 , 6 , 0 , 2 , 3 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 3 , 7 , 0 ,
3 , 0 , 6 , 0 , 2 , 1 , 0 , 1 , 6 , 0 , 3 , 1 , 0 , 1 , 0 , 5 , 6 , 0 , 3 , 3 ,
7 , 0 , 3 , 0 , 1
Listato 3.1. cromosoma dell’algoritmo di Levensthein
10

3.2.2 Distanza di Jaccard
La distanza di Jaccard (dJ (A, B)) misura la dissimilarità tra due insiemi e viene calcolata come
segue [19]:
dJ (A, B) = 1 − J(A, B) = 1 −
A ∩ B
A ∪ B
Dove J(A, B) è detto indice di Jaccard ed è definito come il rapporto tra la cardinalità dell’insieme
intersezione tra A e B e la cardinalità dell’insieme unione.
Poiché in questo caso specifico si cerca una distanza tra stringhe e non tra insiemi, l’algoritmo di
computazione deve ignorare tutti i caratteri presenti più volte all’interno di ogni singola stringa di
input; in questo modo le stringhe vengo considerate come se fossero insiemi.
Il cromosoma dell’algoritmo di calcolo consta di 299 geni ed è riportato nel listato 3.2. Affinché
venga mappato come previsto è necessario impostare un valore di ricorsione massima di almeno 36
chiamate: in tal caso il listato risultate è visibile in appendice D.
1 , 1 , 2 , 7 , 0 , 0 , 7 , 0 , 1 , 1 , 2 , 1 , 2 , 1 , 3 , 7 , 0 , 0 , 1 , 3 , 1 ,
0 , 0 , 0 , 4 , 0 , 6 , 0 , 0 , 1 , 0 , 2 , 6 , 0 , 2 , 1 , 0 , 3 , 0 , 0 , 0 ,
1 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 4 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 6 ,
0 , 2 , 1 , 0 , 0 , 6 , 0 , 0 , 1 , 0 , 2 , 0 , 0 , 0 , 0 , 2 , 0 , 1 , 1 , 0 ,
0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 3 , 7 , 0 , 1 , 1 , 3 , 1 , 0 , 0 , 0 , 4 , 0 ,
6 , 0 , 1 , 1 , 0 , 2 , 6 , 0 , 2 , 1 , 0 , 3 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 ,
0 , 1 , 1 , 0 , 1 , 0 , 4 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 6 , 0 , 2 , 1 , 0 , 0 ,
6 , 0 , 1 , 1 , 0 , 2 , 0 , 0 , 0 , 0 , 2 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 ,
0 , 0 , 1 , 2 , 1 , 0 , 0 , 2 , 7 , 0 , 2 , 1 , 1 , 2 , 7 , 0 , 0 , 7 , 0 , 1 ,
1 , 2 , 1 , 2 , 1 , 3 , 7 , 0 , 0 , 0 , 3 , 7 , 0 , 1 , 0 , 4 , 0 , 6 , 0 , 0 ,
1 , 0 , 5 , 6 , 0 , 1 , 1 , 0 , 6 , 1 , 3 , 1 , 0 , 3 , 0 , 4 , 0 , 6 , 0 , 0 ,
1 , 0 , 5 , 6 , 0 , 3 , 1 , 0 , 7 , 0 , 0 , 0 , 4 , 0 , 1 , 0 , 0 , 0 , 1 , 1 ,
0 , 1 , 0 , 4 , 0 , 1 , 0 , 4 , 0 , 0 , 1 , 6 , 0 , 3 , 1 , 0 , 3 , 6 , 0 , 0 ,
1 , 0 , 5 , 0 , 0 , 0 , 3 , 2 , 0 , 1 , 1 , 0 , 3 , 0 , 0 , 0 , 4 , 0 , 0 , 0 ,
0 , 0 , 4 , 1 , 0 , 4 , 0 , 5 , 3 , 0 , 1 , 8 , 1 , 0 , 3 , 1 , 0 , 0
Listato 3.2. cromosoma dell’algoritmo di Jaccard
3.3 Validazione incrociata
Quando si utilizzano algoritmi genetici è buona norma separare l’insieme destinato all’appren-
dimento da quello utilizzato per valutare l’efficacia della soluzione trovata: infatti, misurare le
prestazioni della soluzione sui dati di training potrebbe portare a valori artificialmente buoni nel
caso di overfitting. Una stima più fedele dell’efficacia della soluzione la si ottiene valutandola su
dati dati non usati durante l’apprendimento.
Per valutare l’efficacia reale della soluzione si è effettuata una cross-validazione: si è scelto di
evolvere l’algoritmo solo su esempi di 7 task e di utilizzare per la validazione il task non usato nel
training. Questo esperimento è stato ripetuto 8 volte, utilizzando ogni volta task diversi per la
validazione.
Siccome il fine ultimo di questo lavoro di tesi è provare a costruire una metrica che permetta
un’estrazione efficace, è opportuno valutare la metrica anche ipotizzando di basare su di essa un
semplice estrattore e misurando le prestazioni dell’estrattore.
In generale, un estrattore E è un algoritmo parametrico che riceve in input una stringa t e dà
in output un insieme Y di sottostringhe di t (che sono le cose che estrae). L’estrattore deve essere
tarato. La procedura di taratura riceve in input una stringa t e un insieme X di sottostringhe di t
11

che sono le sottostringhe che si vogliono estrarre da t; la conseguenza della taratura è che vengono
settati i valori dei parametri dell’estrattore.
Nel caso in esame si è costruito un semplice estrattore basato su una distanza d. I parametri
di tale estrattore sono due set di stringhe P e N e un set di separatori S, ottenuti a partire da t e
X utilizzando la tokenizzazione. L’estrazione segue questa procedura:
1. si tochenizza t con S ottenendo un multiinsieme T di stringhe s;
2. ogni s viene considerata da estrarre (cioè si inserisce in Y ) se è solo se vale la condizione
seguente: 1
|P | p∈P d(s, p) ≤ 1
|N| n∈N d(s, n), cioè se la sua distanza media dagli elementi
di P è minore della sua distanza media dagli elementi di N.
3. vengono calcolati gli indici descritti nella sottosezione seguente.
Siccome il processo di evoluzione è stocastico, la procedura di generazione-validazione viene
ripetuta per 5 volte utilizzando seed diversi. In questo modo è possibile raccogliere dati che non
siano dovuti ad una esecuzione particolarmente fortunata o sfortunata.
3.3.1 Indici
Al fine di ottenere risultati oggettivi, viene fatta un’analisi utilizzando i seguenti indici riferiti al
miglior individuo ottenuto dell’evoluzione:
• Best Fitness (BF), punteggio di fitness calcolato sui dataset di addestramento;
• Validation Fitness (VF), punteggio di fitness calcolato su tutto il dataset di validazione;
• #Instruction (#I), numero di istruzioni che compongono l’algoritmo generato;
• #Steps (#S), numero medio di istruzioni eseguite per task durante la validazione;
• Precision (P), rapporto tra il numero di stringhe valutate come da estrarre e la somma tra
il numero di stringhe da estrarre e il numero di stringhe estratte per errore;
• Recall (R), rapporto tra il numero di stringhe valutate come da estrarre e la somma tra il
numero di stringhe da estrarre e il numero di stringhe non estratte;
• F-Measure (F1), media armonica di Precision e Recall.
Si precisa che P, R e F1 sono riferiti all’estrattore costruito sulla metrica in esame e vengono
valutati su tutto il dataset di validazione.
3.4 Linguaggi e tecnologie usate
Il software impiegato in questo progetto è stato scritto in linguaggio Java, nella versione Java 8. Il
modulo relativo a GA utilizza la libreria opensource Jenetics.io2
.
2http://jenetics.io/
12

Capitolo 4
Risultati sperimentali
Di seguito vengono riportati tutti i dati raccolti relativi agli esperimenti eseguiti con due diversi
valori di popolazione (50 e 100 individui). Come già accennato in sezione 3.3 essi sono il risultato
delle medie aritmetiche di 5 esecuzioni indipendenti. Nelle tabelle che seguono sono quindi ripor-
tati gli indici di valutazione dell’algoritmo ottenuto mediante evoluzione su dataset di training di
dimensioni diverse:
• Tabella 4.1 e Tabella 4.4, indici ottenuti con 10 esempi;
• Tabella 4.2 e Tabella 4.5, indici ottenuti con 25 esempi;
• Tabella 4.3 e Tabella 4.6, indici ottenuti con 50 esempi.
4.1 Popolazione di 50 individui
Task BF VF #I #S [×106
] P R F1
HTML-href 0.366 0.491 236.6 0.134 0.068 1.000 0.127
Log-MAC+IP 0.369 0.113 65.6 0.045 0.785 1.000 0.879
Log-IP 0.320 0.867 1271.0 0.063 0.256 1.000 0.407
Email-Phone 0.358 0.648 1565.4 0.704 0.064 0.591 0.116
Bills-Date 0.306 0.749 813.8 0.564 0.064 1.000 0.121
Web-URL 0.420 0.417 130.6 1.034 0.029 1.000 0.057
Twitter-URL 0.387 0.306 497.2 1.082 0.063 1.000 0.119
Wiki-CapitalizedSequences 0.388 0.516 155.8 1.207 0.071 1.000 0.133
Medie 0.364 0.513 592.0 0.604 0.175 0.949 0.245
Tabella 4.1. Indici di valutazione ottenuti con 10 esempi
13

4 – Risultati sperimentali
] P R F1
HTML-href 0.491 0.537 226.6 0.163 0.068 1.000 0.127
Log-MAC+IP 0.456 0.100 768.8 0.139 0.785 1.000 0.879
Log-IP 0.443 0.892 1135.2 1.817 0.390 0.620 0.478
Email-Phone 0.469 0.665 2661.6 0.482 0.057 0.600 0.104
Bills-Date 0.309 0.767 360.6 0.885 0.064 1.000 0.121
Web-URL 0.408 0.288 2665.8 0.968 0.030 1.000 0.058
Twitter-URL 0.429 0.292 11 769.8 0.711 0.063 1.000 0.119
Medie 0.426 0.513 2551.5 0.764 0.191 0.902 0.252
] P R F1
HTML-href 0.454 0.418 1877.4 0.223 0.067 1.000 0.126
Log-MAC+IP 0.443 0.078 179.2 0.061 0.785 1.000 0.879
Log-IP 0.343 0.890 90.4 0.117 0.197 1.000 0.330
Email-Phone 0.430 0.644 352.2 0.413 0.051 0.600 0.095
Bills-Date 0.487 0.845 1115.8 1.563 0.064 1.000 0.121
Web-URL 0.402 0.297 150.8 0.715 0.030 1.000 0.058
Twitter-URL 0.478 0.297 147.2 0.836 0.063 1.000 0.119
Wiki-CapitalizedSequences 0.464 0.645 20 429.0 3.159 0.057 0.800 0.106
Medie 0.438 0.514 3042.7 0.886 0.164 0.924 0.229
A integrazione dei dati sopra esposti, nel grafico Figura 4.1 si riporta l’andamento della fitness
durante l’evoluzione dell’individuo che, alla fine dell’addestramento, ha ottenuto la fitness migliore.
In particolare, il grafico si riferisce all’addestramento compiuto senza il dataset Log-IP e compara
gli individui ottenuti con np pari a 10, 25 e 50 esempi.
14

0 50 100 150 200
0
0.2
0.4
0.6
0.8
1
Generazione
Fitness 10 esempi
25 esempi
50 esempi
Figura 4.1. Andamento della ﬁtness per Log-IP con popolazione di 50 individui
4.2 Popolazione di 100 individui
] P R F1
HTML-href 0.371 0.508 68.8 0.190 0.069 1.000 0.129
Log-MAC+IP 0.391 0.421 200.8 0.043 0.791 1.000 0.884
Log-IP 0.223 0.890 1787.2 0.217 0.000 0.000 0.000
Email-Phone 0.282 0.630 717.4 0.350 0.106 0.597 0.180
Bills-Date 0.314 0.728 595.0 0.842 0.064 1.000 0.121
Web-URL 0.324 0.342 160.4 10.440 0.030 1.000 0.058
Twitter-URL 0.361 0.368 5086.8 4.690 0.068 1.000 0.127
Medie 0.323 0.557 1092.9 1.046 0.150 0.950 0.204
15

] P R F1
HTML-href 0.371 0.413 1038.0 0.184 0.068 1.000 0.127
Log-MAC+IP 0.426 0.106 1570.0 0.047 0.785 1.000 0.879
Log-IP 0.300 0.885 313.4 0.106 0.197 0.400 0.264
Email-Phone 0.346 0.656 344.8 0.389 0.017 0.200 0.032
Bills-Date 0.320 0.778 3402.2 1.803 0.064 1.000 0.121
Web-URL 0.499 0.533 933.8 2.581 0.024 0.800 0.046
Twitter-URL 0.435 0.390 54.6 0.660 0.063 1.000 0.119
Medie 0.389 0.553 1093.2 0.871 0.161 0.800 0.215
] P R F1
HTML-href 0.406 0.318 74.0 0.211 0.068 1.000 0.127
Log-MAC+IP 0.383 0.750 78.0 0.047 0.785 1.000 0.879
Log-IP 0.313 0.885 194.0 0.076 0.197 0.400 0.264
Email-Phone 0.336 0.538 746.5 0.655 0.034 0.400 0.063
Bills-Date 0.324 0.754 46.5 0.478 0.064 1.000 0.121
Web-URL 0.404 0.295 791.8 0.549 0.030 1.000 0.058
Twitter-URL 0.430 0.289 922.6 0.710 0.063 1.000 0.119
Medie 0.372 0.475 373.6 0.412 0.164 0.850 0.221
Analogamente a quanto è stato fatto per la popolazione di 50 individui, si riporta di seguito il gra-
fico Figura 4.2 che compara le evoluzioni della fitness durante le generazioni. Anche in questo caso
è stato scelto di mostrare gli andamenti della fitness (su 10, 25 e 50 esempi) durante un apprendi-
mento che non comprende il dataset Log-IP e che si avvicinano maggiormente all’andamento ideale.
16

0 50 100 150 200
0
0.2
0.4
0.6
0.8
1
Generazione
Fitness
10 esempi
25 esempi
50 esempi
Figura 4.2. Andamento della fitness per Log-IP con popolazione di 100 individui
4.3 Analisi dei dati
Dalle tabelle esposte in questo capitolo è possibile vedere come il valore di F-Measure (F1) non
presenti alterazioni significative variando il numero di esempi o di individui per popolazione. Ad
esempio, si può notare che tale parametro varia da un valore medio minimo di 0.204, per una
popolazione di 100 individui e un addestramento su 10 esempi, ad un valore medio massimo di
0.252, per 50 individui e 25 esempi.
Osservando le tabelle si può notare anche che il valore di F1 riferito al dataset Log-MAC+IP è
sempre molto al di sopra del valore medio, ma ciò è dovuto al rapporto estrazioni desiderate/token1
.
Inoltre, è possibile notare come i valori di fitness ottenuti al termine dell’evoluzione non siano
correlati al valore di fitness dello stesso individuo calcolato su un dataset in cui non è stato adde-
strato. Ad esempio, il valore di BF riferito a Log-IP è generalmente maggiore del corrispondente
valore di VF, mentre per Email-Phone accade esattamente l’opposto. Questo indica che il miglior
individuo generato dal processo evolutivo spesso non è applicabile ad un contesto più generale.
Analizzando i grafici Figura 4.1 e Figura 4.2 relativi all’andamento del valore di BF durante
l’evoluzione, si può notare che, in generale, entro le prime generazioni si ha un rapido decremento
dei valori. Nelle generazioni successive, tale decremento tende a rallentare e il valore tende a
1481 stringhe da estrarre su 613 token. Se il classificatore restituisse sempre POS, P = 0.78 e R = 1.0
17

stabilizzarsi. Inoltre, maggiore è il numero di individui nella popolazione, maggiormente ripido è
il decremento. Si può notare, anche, che il valore di BF al termine delle 200 risulta aumentare con
il numero di esempi: tale comportamento è confermato anche dalle tabelle. Prendendo sempre in
considerazione il dataset Log-IP, si ha che l’indice in esame, per la popolazione di 100 individui,
varia da un minimo di 0.223 (con 10 esempi) ad un massimo di 0.313 (con 50 esempi).
4.3.1 Confronto con algoritmi noti
Per valutare le prestazioni del metodo proposto, si confrontano ora gli indici medi relativi alla
metrica ottenuta con i medesimi indici relativi alle distanze di Levenshtein (Tabella 4.7 e di Jaccard
(Tabella 4.3.1).
Task VF #I #S [×107
] P R F1
HTML - href 0.910 103.0 2.253 1.000 0.726 0.841
Log-MAC+IP 0.907 103.0 0.752 0.000 0.000 0.000
Log-IP 0.901 103.0 1.050 0.915 0.765 0.833
Email-Phone 0.897 103.0 3.638 0.720 0.837 0.774
Bills-Date 0.899 103.0 5.186 0.671 0.703 0.687
Web-URL 0.915 103.0 10.000 0.794 0.984 0.879
Twitter-URL 0.900 103.0 8.100 0.967 1.000 0.983
Wiki-CapitalizedSequences 0.908 103.0 9.697 0.000 0.000 0.000
Medie 0.905 103.0 5.084 0.6334 0.627 0.625
Tabella 4.7. Indici di valutazione dell’algoritmo di Levenshtein
Task VF #I #S [×107
] P R F1
HTML-href 0.637 174.0 3.485 0.150 1.000 0.262
Log-MAC+IP 0.818 174.0 0.415 0.981 0.904 0.941
Log-IP 0.505 174.0 0.857 0.939 1.000 0.969
Email-Phone 0.555 174.0 4.622 0.299 1.000 0.461
Bills-Date 0.586 174.0 2.711 0.274 1.000 0.431
Web-URL 0.427 174.0 23.860 0.064 1.000 0.121
Twitter-URL 0.293 174.0 6.279 0.153 1.000 0.266
Wiki-CapitalizedSequences 0.799 174.0 7.552 0.227 1.000 0.370
Medie 0.578 174.0 6.223 0.386 0.988 0.478
Tabella 4.8. Indici di valutazione dell’algoritmo di Jaccard
L’indice più significativo è F1: nel caso di Levenshtein e di Jaccard esso risulta essere nettamente
maggiore del miglior indice ottenuto dalle evoluzioni. Ciò denota come i relativi classificatori
riescono a compiere meno errori.
Il valore medio di VF della soluzione proposta (compreso tra 0.475 e 0.557) è paragonabile
a Jaccard (0.578), mentre Levenshtein ottiene il punteggio di 0.905, che in termini qualitativi
rappresenta la quasi totale sovrapposizione di E e O. Nonostante ciò Levenshtein ottiene comunque
buoni risultati di F1 e questo potrebbe indicare che la funzione di fitness presa in considerazione
non è adeguata.
18

Infine, è possibile notare come Jaccard e Levenshtein richiedano l’esecuzione di un numero di
istruzioni circa 10 volte maggiore.
Analizzando il grafico di Figura 4.3 è possibile capire qualitativamente come le grandezze VF
e F1 si rapportano tra loro, in base alle 3 metriche considerate e i relativi classificatori.
0 0.2 0.4 0.6 0.8 1
0
0.2
0.4
0.6
0.8
1
VF
F1
Levenshtein
Jaccard
Evoluta
Figura 4.3. Relazione tra i valori di F1 e VF per le distanze esaminate
Innanzi tutto, si può notare che i risultati relativi alla distanza di Levenshtein siano prevalen-
temente concentrati in alto a destra, dimostrando una buona capacità di classificazione, ma una
scarsa capacità di separazione. La distanza di Jaccard, invece, è piuttosto sparsa, impedendo di
fare alcuna osservazione. Infine, la metrica proposta in questa tesi produce risultati che si concen-
trano principalmente in basso al grafico, in quanto il classificatore associato dimostra una scarsa
capacità di decisione.
19

Capitolo 5
Conclusione
Alla luce di quanto emerso da questo studio, si può affermare che l’obiettivo di creare nuovi
algoritmi sintatticamente validi per la computazione della distanza tra due stringhe tramite GE
e GA è stato raggiunto con successo. Inoltre, si è costruita una macchina virtuale in grado di
eseguire tali algoritmi.
Le metriche ottenute in questo modo si dimostrano efficaci, in quanto riescono a ottenere un
buon grado di separazione tra l’insieme dei risultati ottenuti confrontando una stringa con gli
esempi da estrarre, e quelli ottenuti confrontando la stessa stringa con gli esempi da non estrarre.
Data una metrica, si è creato anche un estrattore di stringhe con il compito di stabilire se la stringa
in esame vada estratta o meno, valutando la sua distanza media dai due insieme sopra citati.
Infine, dai dati ottenuti si può affermare che l’estrattore costruito con una metrica generata ha
prestazioni, in termini di F-Measure, molto inferiori ad uno costruito utilizzando metriche già note
in letteratura; questo comportamento può essere dovuto all’utilizzo di una funzione di fitness non
adeguata.
Pertanto, la tecnica utilizzata in questo progetto, sebbene possa essere considerata valida,
necessita di ulteriori studi e approfondimenti.
20

Appendice A
Grammatica usata
<InstructionExpression > ::= <Assign> |
<CreateArray> |
<CreateVariable> |
<For> |
<If > |
<Return> |
<SetArrayItem>
<ValueReturningFunction> ::= <Constant> |
<GetVariableValue> |
<Add> |
<Decrement> |
<Maximum> |
<Minimum> |
<GetArrayItem> |
<GetArrayLength> |
<Division > |
<Multiplication >
<Assign> ::= var[<ValueReturningFunction >] :=
<ValueReturningFunction>
<CreateArray> ::= newArray[<ValueReturningFunction >]
<CreateVariable> ::= createVariable ()
<Division > ::= (<ValueReturningFunction> /
<ValueReturningFunction >)
<For> ::= fo r ( index0 = 0; index0 <
<ValueReturningFunction >; index0++) <BlockCode>
<If > ::= i f (<Condition >) <BlockCode> e l s e <BlockCode>
<Return> ::= return <ValueReturningFunction>
<SetArrayItem> ::= array [<ValueReturningFunction >]
[<ValueReturningFunction >] :=
<Add> ::= <ValueReturningFunction> +
<Subtract> ::= <ValueReturningFunction> −
22

A – Grammatica usata
<Maximum> ::= maximum(<ValueReturningFunction >,
<Minimum> ::= minimum(<ValueReturningFunction >,
<Multiplication > ::= <ValueReturningFunction> ∗
<GetArrayItem> ::= array [<ValueReturningFunction >]
[<ValueReturningFunction >]
<GetArrayLength> ::= array [<ValueReturningFunction >]. length
<Constant> ::= 0 | 1 | . . | 255
<GetVariableValue> ::= var[<ValueReturningFunction >]
<BlockCode> ::= <RowOfBlockCode>
<RowOfBlockCode> ::= <InstructionExpression > |
<InstructionExpression > n <RowOfBlockCode>
<Condition> ::= <EqualCondition> |
<NotEqualCondition> |
<MajorCondition> |
<MajorEqualsCodition>
<EqualCondition> ::= <ValueReturningFunction> ==
<NotEqualCondition> ::= <ValueReturningFunction> !=
<MajorCondition> ::= <ValueReturningFunction> >
<MajorEqualsCodition> ::= <ValueReturningFunction> >=
Listato A.1. Grammatica in forma normale di Backus–Naur
23

Appendice B
Istruzioni della Macchina virtuale
Le operazioni implementate dalla macchina virtuale sono
• Assign(p1,p2)
Eﬀettua l’accesso alla p1-esima variabile dello scope e le assegna il valore p2. Se nessuna
variabile è accessibile, crea una nuova variabile nel contesto attuale;
• CreateArray(p1)
Crea nello scope in cui è invocato un nuovo vettore di float di dimensione p1:
• CreateVariable()
Crea nello scope in cui è invocato una nuova variabile di tipo di float e le assegna il valore
0;
• Division(p1, p2)
Restituisce il valore della divisione tra p1 e p2. Può comportare il blocco dell’esecuzione in
caso di p2 == 0;
• For(p1, p2)
Crea un nuovo scope, in cui viene creata una nuova variabile; esegue poi il codice di p2 nel
nuovo scope per un numero di volte pari a p1. Il numero dell’iterazione corrente è disponibile
nella variabile, ma è modiﬁcabile solo dalla macchina virtuale;
• If(p1, p2, p3)
Crea un nuovo contesto C1. Se vale p1 > 0 allora esegue p2 nel contesto C1, altrimenti esegue
p3 nel contesto C1;
• Return(p1)
Termina la computazione e imposta il risultato di essa a p1.
• SetArrayItem(p1, p2, p3)
Imposta il valore della p2-esima componente del vettore p1 pari a p2. Se non vi sono array
accessibili, crea un nuovo array di dimensione 1;
• Add(p1, p2)
Restituisce il valore di p1+p2;
• Subtract(p1, p2)
Restituisce il valore di p1-p2;
24

B – Istruzioni della Macchina virtuale
• Maximum(p1, p2)
Restituisce il valore maggiore tra p1 e p2;
• Minimum(p1, p2)
Restituisce il valore minore tra p1 e p2;
• Multiplication(p1, p2)
Restituisce il valore della moltiplicazione tra p1 e p2;
• GetArrayItem(p1, p2)
Restituisce il valore della p2-esima componente del vettore p1. Se non vi sono array accessibili,
crea nel contesto attuale un nuovo array di dimensione 1;
• GetArrayLength(p1)
Restituisce la lunghezza del p1-esimo vettore;
• Constant()
Restituisce un valore non modiﬁcabile nell’intervallo [0, 255];
• GetVariableValue(p1)
Restituisce il valore della p1-esima variabile. Se nessuna variabile è accessibile, crea una
nuova variabile nel contesto attuale;
• EqualCondition(p1, p2)
Restituisce 1 se vale p1 == p2, 0 altrimenti;
• NotEqualCondition(p1, p2)
Restituisce 1 se vale p1! = p2, 0 altrimenti;
• MajorCondition(p1, p2)
Restituisce 1 se vale p1 > p2, 0 altrimenti;
• MajorEqualsCodition(p1, p2)
Restituisce 1 se vale p1 >= p2, 0 altrimenti.
25

Appendice C
Listato di Wagner-Fisher
newArray [ array [ 0 . 0 ] . length + 1 . 0 ] ;
f or ( int index = 0; index <= array [ 2 . 0 ] . length ; index++)
{
Array [ 2 . 0 ] [ getVariable ( 0 . 0 ) ] := getVariable ( 0 . 0 ) ;
}
newArray [ array [ 0 . 0 ] . length + 1 . 0 ] ;
{
{
i f ( getVariable ( 1 . 0 ) == 0.0)
{
Array [ 3 . 0 ] [ 0 . 0 ] := getVariable ( 0 . 0 ) + 1 . 0 ;
}
e l s e
{
i f ( array [ 0 . 0 ] [ getVariable ( 1 . 0 ) − 1 . 0 ] == array [ 1 . 0 ] [ getVariable
( 0 . 0 ) ] )
{
Array [ 3 . 0 ] [ getVariable ( 1 . 0 ) ] := array [ 2 . 0 ] [ getVariable ( 1 . 0 ) −
1 . 0 ] ;
}
e l s e
{
Array [ 3 . 0 ] [ getVariable ( 1 . 0 ) ] := minimum( array [ 2 . 0 ] [
getVariable ( 1 . 0 ) ] + 1.0 , minimum( array [ 3 . 0 ] [ getVariable
( 1 . 0 ) − 1 . 0 ] + 1.0 ,
array [ 2 . 0 ] [ getVariable ( 1 . 0 ) − 1 . 0 ] + 1.0) ) ;
}
}
}
{
Array [ 2 . 0 ] [ getVariable ( 1 . 0 ) ] := array [ 3 . 0 ] [ getVariable ( 1 . 0 ) ] ;
26

C – Listato di Wagner-Fisher
}
}
return ( array [ 3 . 0 ] [ array [ 3 . 0 ] . length − 1 . 0 ] ) ;
27

Appendice D
Listato di Jaccard
newArray [ array [ 0 . 0 ] . length + array [ 1 . 0 ] . length ] ;
createVariable () ;
createVariable () ;
{
f or ( int index = 0; index <= getVariable ( 0 . 0 ) ; index++)
{
i f ( array [ 0 . 0 ] [ getVariable ( 2 . 0 ) ] == array [ 2 . 0 ] [
getVariable ( 3 . 0 ) ] )
{
var [ 1 . 0 ] := 1 . 0 ;
}
e l s e
{
var [ 1 . 0 ] := getVariable ( 1 . 0 ) ;
}
}
i f ( getVariable ( 1 . 0 ) == 0.0)
{
Array [ 2 . 0 ] [ getVariable ( 0 . 0 ) ] := array [ 0 . 0 ] [ getVariable
( 2 . 0 ) ] ;
var [ 0 . 0 ] := 1.0 + getVariable ( 0 . 0 ) ;
}
e l s e
{
var [ 1 . 0 ] := 0 . 0 ;
}
}
{
f or ( int index = 0; index <= getVariable ( 0 . 0 ) ; index++)
{
28

D – Listato di Jaccard
{
var [ 1 . 0 ] := 1 . 0 ;
}
e l s e
{
var [ 1 . 0 ] := getVariable ( 1 . 0 ) ;
}
}
i f ( getVariable ( 1 . 0 ) == 0.0)
{
Array [ 2 . 0 ] [ getVariable ( 0 . 0 ) ] := array [ 1 . 0 ] [ getVariable
( 2 . 0 ) ] ;
var [ 0 . 0 ] := 1.0 + getVariable ( 0 . 0 ) ;
}
e l s e
{
var [ 1 . 0 ] := 0 . 0 ;
}
}
createVariable () ;
var [ 2 . 0 ] := array [ 2 . 0 ] . length ;
newArray [ array [ 0 . 0 ] . length + array [ 1 . 0 ] . length ] ;
createVariable () ;
createVariable () ;
{
{
{
f or ( int index = 0; index <= getVariable ( 3 . 0 ) ;
index++)
{
i f ( array [ 0 . 0 ] [ getVariable ( 5 . 0 ) ] ==
array [ 3 . 0 ] [ getVariable ( 7 . 0 ) ] )
{
var [ 4 . 0 ] := 1 . 0 ;
}
e l s e
{
var [ 1 . 0 ] := getVariable ( 1 . 0 ) ;
}
}
i f ( getVariable ( 4 . 0 ) == 0.0)
{
Array [ 3 . 0 ] [ getVariable ( 3 . 0 ) ] := array
[ 0 . 0 ] [ getVariable ( 5 . 0 ) ] ;
var [ 3 . 0 ] := 1.0 + getVariable ( 3 . 0 ) ;
}
29

D – Listato di Jaccard
e l s e
{
var [ 4 . 0 ] := 0 . 0 ;
}
}
e l s e
{
var [ 4 . 0 ] := getVariable ( 4 . 0 ) ;
}
}
}
return (1.0 − ( getVariable ( 3 . 0 ) / getVariable ( 0 . 0 ) ) ) ;
30

Bibliograﬁa
[1] Cohen, William, Pradeep Ravikumar, and Stephen Fienberg. "A comparison of string metrics
for matching names and records." Kdd workshop on data cleaning and object consolidation.
Vol. 3. 2003.
[2] Stoilos, Giorgos, Giorgos Stamou, and Stefanos Kollias. "A string metric for ontology
alignment." The Semantic Web–ISWC 2005. Springer Berlin Heidelberg, 2005. 624-637.
[3] Bilenko, Mikhail, and Raymond J. Mooney. "Adaptive duplicate detection using learnable
string similarity measures." Proceedings of the ninth ACM SIGKDD international conference
on Knowledge discovery and data mining. ACM, 2003.
[4] Tsuruoka, Yoshimasa, John McNaught, and Sophia Ananiadou. "Learning string similarity
measures for gene/protein name dictionary look-up using logistic regression." Bioinformatics
23.20 (2007): 2768-2774.
[5] Brauer, Falk, et al. "Enabling information extraction by inference of regular expressions from
sample entities." Proceedings of the 20th ACM international conference on Information and
knowledge management. ACM, 2011.
[6] Bartoli, Alberto, et al. "Learning text patterns using separate-and-conquer genetic
programming." Genetic Programming. Springer International Publishing, 2015. 16-27.
[7] Bartoli, Alberto, et al. "Automatic generation of regular expressions from examples with ge-
netic programming." Proceedings of the 14th annual conference companion on Genetic and
evolutionary computation. ACM, 2012.
[8] Bartoli, Alberto, et al. "Inference of Regular Expressions for Text Extraction from Examples."
[9] Bartoli, Alberto, et al. "Automatic synthesis of regular expressions from examples." (2013).
[10] Le, Vu, and Sumit Gulwani. "FlashExtract: A framework for data extraction by examples."
ACM SIGPLAN Notices. Vol. 49. No. 6. ACM, 2014.
[11] McCall, John. "Genetic algorithms for modelling and optimisation." Journal of Computational
and Applied Mathematics 184.1 (2005): 205-222.
[12] Goldberg, David E. Genetic algorithms in search optimization and machine learning. Vol. 412.
Reading Menlo Park: Addison-wesley, 1989.
[13] Mitchell, Melanie. An introduction to genetic algorithms. MIT press, 1998.
[14] O’Neill, Michael, and Conor Ryan. "Grammatical evolution." IEEE Transactions on
Evolutionary Computation 5.4 (2001): 349-358.
[15] Brauer, Falk, et al. "Enabling information extraction by inference of regular expressions from
sample entities." Proceedings of the 20th ACM international conference on Information and
knowledge management. ACM, 2011.
[16] Li, Yunyao, et al. "Regular expression learning for information extraction." Proceedings
of the Conference on Empirical Methods in Natural Language Processing. Association for
Computational Linguistics, 2008.
31

Bibliograﬁa
[17] Cetinkaya, Ahmet. "Regular expression generation through grammatical evolution." Procee-
dings of the 9th annual conference companion on Genetic and evolutionary computation. ACM,
2007.
[18] Levenshtein, Vladimir I. "Binary codes capable of correcting deletions, insertions, and
reversals." Soviet physics doklady. Vol. 10. No. 8. 1966.
[19] Jaccard, Paul. Etude comparative de la distribution ﬂorale dans une portion des Alpes et du
Jura. Impr. Corbaz, 1901.
32

Ringraziamenti
Giunto al termine di questo lavoro desidero ringraziare il Prof. Eric Medvet per la sua disponibilità
e per avermi seguito in modo scrupoloso e attento. Ringrazio anche il Dott. Fabiano Tarlao per
avermi saggiamente consigliato in momenti di diﬃcoltà, dedicandomi molto del suo tempo e il Prof.
Alberto Bartoli.
Inoltre, vorrei ringraziare la mia famiglia e tutti gli amici di Trieste, per non avermi mai fatto
mancare il sostegno e il supporto in questi lunghi anni di studio.
Ma soprattutto, il mio più grande ringraziamento va a Laura, che più di tutti mi ha supportato
e sopportato nei periodi peggiori.
33

Sintesi automatica di una metrica di similarità tra stringhe tramite tecniche di computazione evolutiva

Recommended

Recommended

More Related Content

Viewers also liked

Viewers also liked (15)

Similar to Sintesi automatica di una metrica di similarità tra stringhe tramite tecniche di computazione evolutiva

Similar to Sintesi automatica di una metrica di similarità tra stringhe tramite tecniche di computazione evolutiva (20)

Recently uploaded

Recently uploaded (11)

Sintesi automatica di una metrica di similarità tra stringhe tramite tecniche di computazione evolutiva