Sintesi automatica di una metrica di similarità tra stringhe tramite tecniche di computazione...
-
Upload
mfurlanetto -
Category
Science
-
view
111 -
download
0
Transcript of Sintesi automatica di una metrica di similarità tra stringhe tramite tecniche di computazione...
UNIVERSITA' DEGLI STUDI DI TRIESTEDIPARTIMENTO DI INGEGNERIA E ARCHITETTURACorso di Laurea Magistrale in Ingegneria Informatica
SINTESI AUTOMATICA SINTESI AUTOMATICA DI UNA METRICA DI SIMILARITA' DI UNA METRICA DI SIMILARITA'
TRA STRINGHE TRAMITE TECNICHE DI TRA STRINGHE TRAMITE TECNICHE DI COMPUTAZIONE EVOLUTIVACOMPUTAZIONE EVOLUTIVA
Laureando: Relatore: Michele Furlanetto Prof. Eric Medvet Correlatore: Prof. Alberto Bartoli
Anno Accademico 2014 - 2015
Estrarre da un documento di testo qualsiasi entità basate su sintassi esplicitate mediante esempi.
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
PROBLEMA AFFRONTATO
COME?COME?Classificatore basato sulla similarità tra stringhe
Concetto di DISTANZA
Estrazione
Testo t
Stringhe estratte
ESTRATTORE
Scomposizione
Sottostringhe s
Classificatore
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Classificatore
stringa s
s va estratta
CLASSIFICATORE
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Esempi Pda estrarre Esempi N da non estrarre
Calcola la distanza media dP di s da P
Calcola la distanza media dN di s da N
dN > dP?
SISI
Tecniche di CALCOLO EVOLUTIVO
DEFINIZIONE DI UNA NUOVA METRICA
● ALGORITMI GENETICI (GA)● EVOLUZIONE GRAMMATICALE (GE)
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
GA
POPOLAZIONE
CROMOSOMI
GENI
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
1 - Popolazione P di n individui
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Processo evolutivo
2 - Calcolo della funzione di fitness per ogni individuo i di P 3 - Selezione degli individui PS che sopravviveranno in P'4 - Selezione degli n' individui PO sottoposti ad alterazione
geneticaa) Ogni gene di ogni individuo o di PO viene mutato con probabilità pm ed inserito in PO'b) Ogni individuo o di PO ha una probabilità pc di essere selezionato per l’operazione di crossover.
5 - P' = PO' U PS
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Fitness
E' un valore numerico indicativo della qualità della soluzione
y = d(a,b)
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
d(“14/03/2013”, “10/03/2016”) d(“17/06/2015”, “Laura”)
y = d(a,b)
O
O
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Fitness (II)
O={y :∀ a ,b∈ X , y=d (a ,b)};E={ y :∀ a∈X ,∀ b∈N , y=d (a ,b)};f 1=∥{o∈O : o≥mine∈E e }∥∥{e∈E : e≤maxo∈O o}∥;f 2=∥{o∈O : o≥10%E }∥∥{e∈E : e≤90%O }∥;
f = f 1 f 22⋅(∥E∥∥O∥)
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
y = d(a,b)
≤ 10 ≤
O
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
GE
4 99 13 ... 255 ... 0
newArray[array[0].length + 1.0] ;for (int index = 0; index <= array[2].length; index++){ Array[2][getVariable(0)]:= getVariable(0) ;}
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
1
GE (II)
Grammatica<Assign> ::= var[<ValueReturningFunction>] := <ValueReturningFunction><CreateArray> ::= newArray[<ValueReturningFunction>]<CreateVariable> ::= createVariable()<Division> ::= <ValueReturningFunction> / <ValueReturningFunction><For> ::= for(index0 = 0; index0 < <ValueReturningFunction>; index0++) <BlockCode><If> ::= if(<Condition>) <BlockCode> else <BlockCode><Return> ::= return <ValueReturningFunction><SetArrayItem> ::= array[<ValueReturningFunction>][<ValueReturningFunction>] := <ValueReturningFunction><Add> ::= <ValueReturningFunction> + <ValueReturningFunction><Maximum> ::= maximum(<ValueReturningFunction>, <ValueReturningFunction>)<Constant> ::= 0 | 1 | .. | 255<BlockCode> ::= <RowOfBlockCode><RowOfBlockCode> ::= <InstructionExpression> | <InstructionExpression> \n <RowOfBlockCode><Condition> ::= <EqualCondition> | <MajorCondition><EqualCondition> ::= <ValueReturningFunction> == <ValueReturningFunction><MajorCondition> ::= <ValueReturningFunction> > <ValueReturningFunction><InstructionExpression> ::= <Assign> | <CreateArray> | <CreateVariable> | <For> | ...<ValueReturningFunction> ::= <Constant> | <GetVariableValue> | <Add> | <Maximum> | ...
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Macchina Virtuale
Variabili di tipo Float Vettori di variabili di tipo Float Visibilità per scope (ereditari)
Input rappresentati come vettori. Ogni numero rappresenta il codice UTF-8del carattere corrispondente
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
PARAMETRI
Dimensioni del cromosoma: 350 geniNumero di offspring: 60% della popolazioneSelettori per GA: Tournament Selection, Truncation + Tournament SelectionOperazioni genetiche: mutazione (0,02%), crossover (10%) Numero di generazioni: 200Individui per generazione: 50 e 100 individui
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
PARAMETRI (II)
Numero di esempi: 10, 25, 50 esempiLimite sulla complessità statica delle soluzioni: massimo numero di funzioni annidate pari a 40Limite sulla complessità delle strutture dati: lunghezza massima dei vettori allocati pari a Limite sulla complessità dinamica delle soluzioni: 40000 istruzioni
10⋅l1⋅l2
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
DATASET
● Bills-Date● Email-Phone● HTML-href● Log-IP● Log-MAC-IP● Twitter-URL● Web-URL● Wiki-CapitalizedSequences
Ogni task è formato da un testo t e da un insieme X di sottostringhe di t.
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Esempio (Log-IP)
DATASET (II)
P vanno richiesti all'utente,ma come si ottiene ma come si ottiene NN dal testo? dal testo?
TOKENIZZAZIONETOKENIZZAZIONEIndividua quel separatore che, applicato al testo t, riesce a massimizzare il numero di sottostringhe corrispondenti agli esempi da estrarre.
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
VALIDAZIONE INCROCIATA
INDICI DI CONFRONTO
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
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 estratte correttamente e la somma tra il numero di stringhe estratte correttamente e il numero di stringhe estratte per errore;Recall (R): rapporto tra il numero di stringhe estratte correttamente e la somma tra il numero di stringhe estratte correttamente e il numero di stringhe non estratte, ma che andrebbero estratte;F-Measure (F1): media armonica di Precision e Recall.
Popolazione 50, esempi 10
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Task BF VF #I #S [x106] 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 0.400 0.312 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 0.904 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.861 0.233Levenshtein - 0.905 103.0 50.84 0.633 0.627 0.626Jaccard - 0.578 174.0 62.23 0.386 0.988 0.478
Andamento generale
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
10 25 500,3
0,350,4
0,450,5
0,550,6
P. 50P. 100
Esempi
Valori
med
i
10 25 500,1
0,120,140,160,180,2
0,220,240,26
P. 50P. 100
Esempi
Valori
med
i
10 25 500,3
0,350,4
0,450,5
0,550,6
P. 50P. 100
Esempi
Valori
med
i
VFBF F1
BF per Log-IP
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
Popolazione 50 Popolazione 100
Correlazione
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
RIASSUMENDO
● E’ stato creato un generatore automatico di algoritmi sintatticamente validi;● E’ stata creata una macchina virtuale capace di eseguirli;● Sono state sintetizzate alcune metriche capaci di separare gli insiemi considerati.
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
IN CONCLUSIONE
● Le prestazioni degli estrattori (F-Measure) costruiti su tali metriche sono peggiori degli estrattori basati su distanze già presenti in letteratura;● L’analisi dei dati relativi alla distanza di Levenshtein mette in evidenza come vi sia una scarsa correlazione tra i risultati della funzione di fitness scelta e la qualità dell’estrattore basato su tale distanza.
Michele Furlanetto – “Sintesi automatica di una metrica di similarità tra stringhe mediante tecniche di computazione evolutiva”
GRAZIE PER L'ATTENZIONEGRAZIE PER L'ATTENZIONE