Classificazione di frasi in linguaggio naturale per il riconoscimento di interazioni tra geni e...

UNIVERSITA DEGLI STUDI DI TRIESTEDipartimento di Ingegneria e Architettura

Corso di Laurea Magistrale in Ingegneria Informatica

Tesi di Laurea in Reti di Calcolatori II

Classificazione di frasi inlinguaggio naturale per il riconoscimento diinterazioni tra geni e proteine con tecniche di

Machine Learning

LAUREANDO RELATORE

Marco Virgolin prof. Alberto Bartoli

CORRELATORI

prof. Eric Medvetdott. Andrea De Lorenzo

dott. Fabiano Tarlao

Anno Accademico 2013/2014

Indice

1 Introduzione 1

2 Scenario 3

2.1 Scopo del lavoro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Aspetti utili di NLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3 Fondamentali di GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.4 Richiami su DFA ed espressioni regolari . . . . . . . . . . . . . . . . . . . 6

3 Classificatore GP 9

3.1 Rappresentazione delle frasi . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2 Generazione di una espressione regolare . . . . . . . . . . . . . . . . . . . 11

3.3 Generazione del classificatore . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.4 Modifiche effettuate a Regex Turtle . . . . . . . . . . . . . . . . . . . . . . 19

4 Dataset 21

4.1 Dataset utilizzato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.2 Dataset BC e GI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.3 Dettagli sulla generazione di φ-stringhe . . . . . . . . . . . . . . . . . . . 25

4.4 Costruzione del dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.5 Dettagli implementativi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5 Valutazione sperimentale 29

5.1 Algoritmo evolutivo per la generazione di DFA . . . . . . . . . . . . . . . 29

5.2 Metodi di riferimento basati sul problema . . . . . . . . . . . . . . . . . . 30

5.3 Metodi di classificazione tradizionali . . . . . . . . . . . . . . . . . . . . . 31

5.4 Risultati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6 Ulteriori esperimenti 37

6.1 Ulteriori esperimenti con φ-SSLEA . . . . . . . . . . . . . . . . . . . . . . 37

6.2 Ulteriori esperimenti con GP . . . . . . . . . . . . . . . . . . . . . . . . . 37

i

INDICE ii

7 Conclusioni 41

Bibliografia 43

Ringraziamenti 47

Elenco delle figure

2.1 Tokenization e POS tagging applicate ad una frase. . . . . . . . . . . . . . 52.2 Funzionamento tipico della programmazione genetica. . . . . . . . . . . . 62.3 Esempio di DFA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 Esempio di espressione regolare. . . . . . . . . . . . . . . . . . . . . . . . . 8

3.1 Trasformazione di una frase in φ-stringa. . . . . . . . . . . . . . . . . . . . 103.2 Albero rappresentante una espressione regolare. . . . . . . . . . . . . . . . 15

5.1 Esempio di classificatore generato con GP. . . . . . . . . . . . . . . . . . . 35

6.1 Prestazioni di φ-SSLEA con n = 7 e nit variabile. . . . . . . . . . . . . . . 386.2 Prestazioni di φ-SSLEA con n variabile e nit = 5000. . . . . . . . . . . . . 386.3 Prestazioni di tre diversi classificatori GP. . . . . . . . . . . . . . . . . . . 40

iii

Elenco delle tabelle

3.1 Porzioni dei due dizionari di geni/proteine e interatori. . . . . . . . . . . . 123.2 Lista parziale delle annotazioni utilizzate. . . . . . . . . . . . . . . . . . . 13

4.1 Alcune frasi del corpus utilizzato negli esperimenti. . . . . . . . . . . . . . 22

5.1 Risultati del metodo proposto nel presente lavoro e dei metodi di riferimento. 34

v

Capitolo 1Introduzione

Lo studio di tecniche per l’estrazione automatica di informazioni da testi scritti e unargomento di enorme interesse, sia nella comunita scientifica, sia dal punto di vistadelle applicazioni tecnologiche. L’estrazione automatica di conoscenza inerente la ricercabiomedica, in particolare, e uno degli ambiti in cui queste tecniche devono affrontaremolte sfide importanti [24, 17, 25, 5, 26, 22, 12]. Uno dei problemi maggiormente rilevantiin questo scenario consiste nella costruzione automatica di descrizioni sistematiche estrutturate di osservazioni di interesse biomedico riportate nella letteratura scientifica [13,11, 20].

Il presente lavoro di tesi riguarda l’identificazione automatica di frasi contenentiinterazioni tra geni e proteine in articoli scientifici, utilizzando tecniche di MachineLearning quali l’elaborazione del linguaggio naturale e la programmazione genetica. Idati a disposizione sono un dizinario di geni, proteine e interatori1 e un piccolo insieme difrasi d’esempio [5, 26, 22]. La difficolta del problema e determinata dal fatto che la meraoccorrenza di parole del dizionario in una frase non implica che quest’ultima contengauna interazione (si veda la Tabella 4.1).

L’approccio descritto in questo documento prevede l’utilizzo della programmazionegenetica per generare un modello dei pattern sintattici corrispondenti alle sole frasi checontengono interazioni tra geni/proteine. I pattern sono implementati tramite espressioniregolari su annotazioni part-of-speech (POS ) rappresentanti l’analisi grammaticale dellerelative parole. In particolare, la costruzione di espressioni regolari viene realizzatatraendo spunto da recenti proposte [2], mentre l’impiego delle annotazioni permette diaffrontare il problema ad un piu alto livello di astrazione e comporta vantaggi praticinotevoli: (i) e possibile basare il lavoro su annotatori gia esistenti, considerati allo statodell’arte nel campo dell’elaborazione del linguaggio naturale, ed (ii) e sufficiente cambiareannotatore per affrontare testo espresso in una lingua diversa o per includere gli ultimiprogressi sviluppati nella tecnologia, senza dover apportare alcuna modifica al framework.

1Con “interatore” si intende una parola che descrive il tipo di interazione che avviene tra duegeni/proteine.

1

1. Introduzione 2

Le prestazioni della classificazione operata dal metodo sono state valutate su undataset di frasi estratte da articoli scientifici biomedici e sono state confrontate con quelledi alcuni importanti metodi di riferimento. I risultati ottenuti consentono di affermareche il classificatore generato per mezzo della programmazione genetica e di fatto in gradodi apprendere pattern sintattici in uno scenario di elaborazione del linguaggio naturaledi interesse pratico.

Il lavoro e stato condotto presso il Machine Learning Lab dell’Universita degli Studi diTrieste, perseguendo i seguenti obiettivi tattici:

1. studio delle basi della programmazione genetica, di alcuni aspetti dell’elaborazionedel linguaggio naturale e di articoli rilevanti a riguardo;

2. studio delle tecnologie e degli strumenti a disposizione;

3. progettazione e sviluppo di modifiche da effettuare al motore evolutivo fornito dallaboratorio per poter generare un classificatore;

4. generazione del dataset per gli esperimenti;

5. valutazione sperimentale e confronto con risultati ottenuti utilizzando metodi diclassificazione di riferimento.

In particolare, l’algoritmo evolutivo per la generazione del classificatore e stato imple-mentato in linguaggio Java, modificando il preesistente motore Regex Turtle, capace digenerare espressioni regolari a partire da esempi.

Per quanto concerne i capitoli successivi, il capitolo Scenario introduce lo scopo dellavoro e richiama elementi dell’informatica discussi in seguito; il capitolo ClassificatoreGP esplica il processo di programmazione genetica utilizzato per generare il classificatore;il capitolo Dataset descrive la costruzione del dataset utilizzato per gli esperimenti; ilcapitolo Valutazione sperimentale tratta i metodi di riferimento utilizzati e i risultatiottenuti; il capitolo Ulteriori esperimenti discute ulteriori esperimenti effettuati modi-ficando alcuni aspetti di due metodi trattati; infine, il capitolo Conclusioni riporta unsunto di quanto discusso e alcune considerazioni finali.

Capitolo 2Scenario

In questo capitolo e descritto lo scopo del presente lavoro e sono riportati richiami diconcetti trattati, utili a facilitare la lettura dei capitoli successivi. Nello specifico, vengonodescritti alcuni aspetti di interesse dell’elaborazione del linguaggio naturale (NLP1), siintroducono i concetti fondamentali della programmazione genetica (GP2) e si richiamanogli automi deterministici a stati finiti e le espressioni regolari.

2.1 Scopo del lavoro

Lo scopo del presente lavoro consta nella generazione di un classificatore C che, data unafrase s espressa in linguaggio naturale, effettui una classificazione binaria rappresentativadel fatto che s contenga o meno almeno una interazione tra un gene e una proteina, otra un gene e un gene, o tra una proteina e una proteina (per brevita, con la locuzione“interazione tra gene e proteina” si intendono i tre casi). Si vuole realizzare il classificatorea partire da due insiemi di apprendimento, detti learning set, S+

L , S−L : le frasi contenute

in S+L contengono (almeno) una iterazione gene-proteina, mentre quelle contenute in S−

L

no. Sono disponibili anche due dizionari di geni/proteine e interatori, come solitamenteavviene in questo tipo di scenari [13, 11, 12].

Al fine di poter apprezzare la natura e la difficolta del problema, e opportunosottolineare che gli insiemi S+

L , S−L non sono etichettati automaticamente utilizzando

un pattern predefinito tenuto nascosto al processo di generazione del classificatore.Piuttosto, l’etichettatura e stata operata da esperti del settore che leggono e analizzano ilsignificato di ciascuna frase nella sua interezza. Ancora, gli esperti non scelgono la classedi appartenenza di una frase utilizzando un pattern sintattico predefinito—non si puoescludere la possibilita che un pattern adatto ad effettuare la classificazione desideratapotrebbe non esistere nemmeno.

1Dall’inglese Natural Language Processing.2Dall’inglese Genetic Programming.

3

2. Scenario 4

Nothing

↓NCS

is

↓VP3S

certain

↓AGG

but

↓CG

death

↓NCS

and

↓CG

taxes

↓NCP

Figura 2.1: Esempio di tokenization e POS tagging applicate ad una frase. La scissione in tokenoperata dalla tokenization e rappresentata dalle sottolineature sotto ciascuna parola, mentrel’analisi grammaticale assegnata dal POS tagging e rappresentata dalle sigle sotto alle frecce. Inparticolare, i significati delle sigle sono: NCS-nome comune singolare, VP3S-verbo presente interza persona singolare, AGG-aggettivo, CG-congiunzione, NCP-nome comune plurale.

2.2 Aspetti utili di NLP

Il Natural Language Processing (NLP) e un campo dell’informatica che riguarda l’insiemedegli studi e delle tecniche per il trattamento automatico di informazioni espresse inlinguaggio naturale. Il problema principale e rappresentato dalla comprensione automaticadel linguaggio naturale, ovvero l’estrazione automatica del significato di un discorso odi un testo. Le applicazioni sono molteplici e spaziano da scenari di ricerca di altolivello, come lo studio dell’intelligenza artificiale e della linguistica, a contesti piu pratici,come il rilevamento del plagio [14] e l’individuazione di relazioni tra entita di interessebiomedico [13, 12].

Al fine di facilitare la comprensione dei prossimi capitoli, si riportano ora alcunedefinizioni3 di concetti NLP utilizzati in seguito. Sia s una frase, considerata come unasequenza ordinata di parole w. Si dice annotatore a una funzione che assegna un valoreva, tipicamente detto annotazione o tag, a una parola w, ovvero a : Q → Va, dove Q el’insieme di tutte le possibili parole e Va e l’insieme di tutti i possibili valori che possonoessere assegnati da a. Si dice token t una tupla < va1 , ..., van > di annotazioni assegnatedagli annotatori a1, ..., an ad una parola w. Tipicamente, un token contiene sempre unelemento che e il valore testuale della parola di partenza stessa.

Nel presente lavoro vengono effettuate due operazioni NLP sulle frasi: l’operazionetokenization e l’operazione Part-Of-Speech tagging. La prima scinde una frase in input sin una sequenza ordinata di token, assegnando a ciascuno di essi il valore testuale dellaparola di partenza. La seconda effettua la annotazione Part-of-Speech (POS ), ovveroassegna a ciascun token un valore che rappresenta l’analisi grammaticale della relativaparola originale.

La Figura 2.1 esplica gli effetti delle operazioni tokenization e POS tagging, eseguitesu una frase in lingua inglese d’esempio.

2.3 Fondamentali di GP

La programmazione genetica e una metodologia di programmazione ispirata all’evoluzionebiologica per generare automaticamente uno o piu programmi che risolvano un problema.

3Le definizioni riportate sono da intendersi relative al presente lavoro, poiche strumenti NLP diversida quelli utilizzati potrebbero non essere conformi ad esse.

5 Richiami su DFA ed espressioni regolari

Inizialmente si considera un insieme di programmi (popolazione), dove ciascun pro-gramma (individuo) e tipicamente generato in modo casuale o secondo euristiche chedipendono dal particolare problema. Ogni individuo rappresenta una soluzione candidataal problema e la bonta della soluzione viene misurata da una specifica funzione (fitness).Gli individui che costituiscono una popolazione sono tradizionalmente rappresentati daalberi, costituiti da nodi funzione (non-foglie), nodi terminali (foglie) e archi che colleganogerarchicamente i nodi. L’albero e considerato il genotipo dell’individuo, perche lo descri-ve con componenti elementari (nodi e archi), ovvero al piu basso livello di astrazione. Ilfenotipo di un individuo e il programma ottenuto dall’interpretazione dell’albero, mentreil comportamento di un individuo e la soluzione che il programma da al problema4. Dueindividui con differente genotipo possono avere il medesimo fenotipo, cosı come individuicon differente fenotipo possono avere il medesimo comportamento.

Su una selezione di individui sono tipicamente impiegate due operazioni genetiche,ispirate anch’esse all’evoluzione biologica: l’operazione crossover e l’operazione mutazione.La prima emula la riproduzione sessuata tra organismi viventi e consiste nella generazionedi nuovi individui ottenuti scambiando due sottoalberi, scelti casualmente, di due individuidi partenza; la seconda riproduce la mutazione di entita biologiche generando un individuoche e ottenuto modificando casualmente un sottoalbero o un nodo di un individuo originale.

Successivamente, si crea una nuova popolazione di individui rimpiazzando le soluzioniche risultano inadatte a risolvere il problema con quelle che hanno prestazioni migliori(secondo la fitness). E inoltre tipico promuovere una piccola parte della popolazioneprecedente alla popolazione successiva (elitismo).

Il ripetersi di tali operazioni permette di generare individui sempre migliori deiprecedenti, finche si converge ad una soluzione ottima o si raggiunge un numero prefissatodi iterazioni (generazioni). Uno schema della procedura complessiva e riportato inFigura 2.2.

2.4 Richiami su DFA ed espressioni regolari

Un automa a stati finiti deterministico (DFA5) e una quintupla A =< Σ, S, δ, s0, F >,dove:

• Σ = {α0, α1, . . . , αn} e l’insieme finito dei simboli (alfabeto);

• S = {s0, s1, . . . , sm} e l’insieme finito degli stati;

• δ : S × σ → S e la funzione (o matrice) di transizione;

• s0 ∈ S e lo stato iniziale;

• F ⊆ S e l’insieme degli stati di accettazione.

4Le definizioni date sono relative al presente lavoro. In altri scenari fenotipo e comportamento possonocoincidere ed essere associati alla fitness dell’individuo.

5Dall’inglese Deterministic Finite Automaton

2. Scenario 6

Figura 2.2: Funzionamento tipico della programmazione genetica.

s0start s1

1

0

1

0

Figura 2.3: Esempio di DFA con alfabeto Σ = {0, 1} e insieme degli stati S = {s0, s1}. Larappresentazione indica che s0 e lo stato iniziale e che s1 e stato di accettazione. L’automa accettatutte le stringhe che hanno un numero dispari di zeri.

Il principio di funzionamento e il seguente. Sia σ una stringa in input di simbolinell’alfabeto Σ, che inizia con simbolo αi. Inizialmente, l’automa A e nello stato iniziales0 e applica la funzione di transizione δ sulla coppia (s0, αi), passando cosı al nuovo statosk = δ(s0, αi). Sia ora αj il successivo simbolo di σ. Nuovamente, A applica δ su (sk, αj)e commuta il proprio stato nel risultante sl. Quando tutta σ e stata consumata, si diceche A accetta σ se lo stato in cui si trova l’automa sf e di accettazione, ovvero sf ∈ F ,

altrimenti si dice che A rifiuta σ se sf e di rifiuto, ovvero sf ∈ S \F . E possibile operareuna classificazione binaria di una stringa valutando l’accettazione o il rifiuto della stessada parte di un automa.

La Figura 2.3 mostra un esempio di semplice DFA con due stati e alfabeto binario.

Una espressione regolare e una descrizione concisa e compatta di insiemi di stringhe. Ladescrizione consiste di una sequenza di costanti ed operatori espressa in un formalismoapposito. Le costanti rappresentano i caratteri dell’alfabeto con cui sono espresse lestringhe in esame, classi di tali caratteri (ad esempio ., \w, \d) e altri elementi sintattici

7 Richiami su DFA ed espressioni regolari

r = href="[ˆ"]+"

s = <a href="www.units.it">sito web UniTs</a>

Figura 2.4: L’espressione regolare r permette di individuare la porzione sottolineata dellastringa s. Infatti, r accetta le (sotto)stringhe che cominciano con la sequenza di caratteri href=",seguita da una sequenza non vuota di caratteri diversi da ", seguita dal carattere ".

(ad esempio l’inizio e la fine della stringa), mentre gli operatori sono costrutti sintatticiche si applicano sulle costanti per ampliare l’espressivita dell’espressione regolare (adesempio i quantificatori, i gruppi catturanti, i lookaround).

Analogamente a quanto avviene utilizzando DFA, una espressione regolare puoaccettare o meno una stringa in input. In particolare, e sempre possibile individuare unaespressione regolare a partire da un automa deterministico a stati finiti [15]. Il viceversanon e sempre vero: esistono costrutti delle espressioni regolari che trascendono le capacitadiscriminative degli automi, come i quantificatori possessivi e la backreference. Ancora,mentre DFA puo solo accettare o rifiutare interamente una stringa s, una espressioneregolare consente di determinare esattamente quali sottostringhe di s sono accettate. Diconseguenza, le espressioni regolari possono essere impiegate per affrontare problemi diestrazione di informazioni.

Per una completa e approfondita analisi delle espressioni regolari, si rimanda a [10].La Figura 2.4 mostra un esempio di espressione regolare applicata ad una stringa.

Capitolo 3Classificatore GP

Il presente capitolo descrive la costruzione e le caratteristiche del classificatore C, costruitocon tecniche di programmazione genetica (GP) e capace di individuare pattern sintatticidelle frasi che devono essere estratte, al di la della mera co-occorrenza di parole rilevanti.Esso viene istruito per mezzo di esempi, utilizzando due insiemi di apprendimento(learning set) S+

L , S−L : le frasi contenute in S+

L contegono almeno una interazione tra genie proteine, mentre quelle in S−

L non ne contegono alcuna.

Il classificatore non opera direttamente sulle frasi espresse in linguaggio naturale,bensı su sequenze di caratteri Unicode, qui denominate φ-stringhe, da esse derivate. Inbreve, ogni frase e stata prima trasformata in una sequenza di annotazioni Part-of-Speech1

(POS) e di altra natura, dopodiche ogni annotazione e stata sostituita da un simboloUnicode ad essa univocamente associato. Tutti i dettagli su questa procedura sonoriportati nella Sezione 3.1 e un esempio e disponibile in Figura 3.1.

Il classificatore desiderato C consiste di un insieme di espressioni regolari {r�1, r�2, . . . }tali che l’output di C per una φ-stringa x in input sara positivo (cioe C asserisce che lafrase corrispondente a x contiene almeno una interazione tra geni e proteine) se almenouna r�i accetta x o una sottostringa non vuota di x.

La costruzione di r�i e stata affrontata per mezzo di una procedura GP ispirata darecenti studi riguardo l’apprendimento di espressioni regolari da esempi [1, 2]. Dal puntodi vista implementativo, e stato modificato e utilizzato il motore Java Regex Turtle,sviluppato dal Machine Learning Lab dell’Universita degli Studi di Trieste, affinche fossepossibile effettuare classificazione su annotazioni anziche estrazione di caratteri. A talriguardo si consideri, ad esempio, il fatto che le espressioni regolari includono costruttiche permettono la generalizzazione e la compattezza quando applicati su testo, come \we \d, che non sono ragionevolmente applicabili su sequenze di annotazioni POS. Inoltre,mentre solitamente gli esempi sono costituiti esattamente da sezioni di testo da estrarre,di cui e possibile individuare dei pattern ben definiti, in questo scenario si voglionoidentificare frasi intere, in cui l’informazione e diluita e non e nemmeno detto che esista

1Data una parola, la annotazione POS ne esprime l’analisi grammaticale.

9

3. Classificatore GP 10

The

↓DT↓DT↓f

physiological

↓JJ↓JJ↓6

role

↓NN↓NN↓9

of

↓IN↓IN↓i

sigmaB-dependent

↓JJ↓

GENEPTN↓G

katX

↓NN↓

GENEPTN↓G

expression

↓NN↓

INOUN↓J

remains

↓VBZ↓

VBZ↓5

obscure

↓JJ↓JJ↓6

.

↓.↓.↓x

Figura 3.1: La frase originale s (in cima) viene trasformata in una φ-stringa x (in fondo) permezzo di due trasformazioni a cascata: la prima produce una sequenza di annotazioni POS e laseconda sostituisce alcune di esse con altre annotazioni specifiche (Sezione 3.1).

un pattern specifico. Le principali modifiche effettuate al motore sono riportate nellaSezione 3.4.

Il numero di espressioni regolari che costituiscono C non e determinato a priori ma inmodo dinamico e automatico durante la procedura. Inizialmente viene generata una primaespressione regolare utilizzando tutta l’informazione disponibile. Quando viene trovataun’espressione regolare con performance adeguate su un subset di esempi, la ricercaevolutiva viene reinizializzata sugli esempi che non sono stati identificati adeguatamente,portando cosı alla generazione di una nuova espressione regolare. Tale metodo prendeil nome di separate-and-conquer ed e ispirato da un recente articolo per l’estrazionedi frammenti di testo [3]: a differenza dell’articolo citato, in questo scenario si vuoleeffettuare classificazione anziche estrazione e si permette la generazione di espressioniregolari che, in fase di addestramento, non hanno precisione perfetta.

3.1 Rappresentazione delle frasi

La rappresentazione delle frasi tramite φ-stringhe prevede l’utilizzo di due dizionari,Dgenes e Dinteractors, il primo contenente parole che rappresentano geni e proteine, ilsecondo parole che rappresentano interatori. Una porzione dei dizionari e mostrata nellaTabella 3.1. La trasformazione di ciascuna frase s in una φ-stringa x avviene come segue.

1. s viene scissa in una sequenza {t1, . . . , tn} di token secondo lo standard Penn-Treebank2;

2. Tramite un annotatore Part-of-Speech (POS) eseguito su {t1, . . . , tn} viene ottenutauna sequenza {a1, . . . , an} di annotazioni, con ai ∈ A. L’insieme A di possibiliannotazioni dipende dallo specifico annotatore POS utilizzato; Si assume cheesistono tre sottoinsiemi di A disgiunti Averb, Aadj, Anoun che corrispondono averbi, aggettivi e nomi rispettivamente—A potrebbe includere altri elementi noncontenuti in Averb∪Aadj∪Anoun. L’annotatore utilizzato nel presente lavoro e quellosviluppato dal gruppo di ricerca Stanford Natural Language Processing Group3, cheutilizza le annotazioni dello standard Penn Treebank. La Tabella 3.2 mostra unalista parziale degli elementi di A usati da tale annotatore POS.

2http://www.cis.upenn.edu/∼treebank3http://nlp.stanford.edu/software/tagger.shtml

11 Generazione di una espressione regolare

3. La sequenza di annotazioni {a1, . . . , an} viene modificata come segue. Sia t ∈∗ D set e uguale a o inizia con un elemento di D—ad esempio, se D = {sigmaB,katX},allora sigmaB-dependent ∈∗ D and katX ∈∗ D. Per ogni i,

• se ti ∈∗ Dgenes, si pone ai := GENEPTN;

• se ti ∈ Dinteractors e ai ∈ Averbi, si pone ai := IVERB;

• se ti ∈ Dinteractors e ai ∈ Aadj, si pone ai := IADJ;

• infine, se ti ∈ Dinteratori e ai ∈ Anoun, si pone ai := INOUN.

L’insieme di tutte le possibili annotazioni viene definito come A′ = A∪ {GENEPTN,IVERB,IADJ,INOUN}.

4. Sia U l’insieme di caratteri che includono cifre, lettere minuscole e maiuscole esia φ : A′ → U una funzione iniettiva che mappa le annotazioni in caratteri (siveda l’ultima colonna a destra della Tabella 3.2). La φ-stringa x corrispondentea {a1, . . . , an} viene ricavata tramite concatenazione dei caratteri ottenuti dallaapplicazione di φ ad ogni elemento della sequenza di annotazioni, in altre parolex = φ(a1) . . . φ(an).

La Figura 3.1 mostra i risultati intermedi e finale della procedura applicata ad unafrase d’esempio.

3.2 Generazione di una espressione regolare

In questa sezione viene descritta la procedura basata su GP per ottenere una espressioneregolare r� da due insiemi di addestramento (training set) X+, X− di φ-stringhe. Loscopo di questa procedura e di generare una espressione regolare r� tale che:

(i) per ogni φ-stringa x in X+, x, o una sottostringa non-vuota di x, e accettata da r�;

(ii) per ogni φ-stringa x in X−, x e tutte le sottostringhe di x non sono accettate da r�.

La relazione tra i training set e i learning set utilizzati per sintetizzare il classificatore eesplicata in seguito.

Rappresentazione della soluzione

Una soluzione candidata, ovvero un individuo, e una espressione regolare che vienerappresentata con un albero, come segue. L’insieme di nodi terminali e composto dalcarattere wildcard . e da ogni carattere nel codominio di φ, cioe ogni caratteri in U checorrisponde ad una annotazione in A′. L’insieme di nodi funzione e composto da:

• il concatenatore ◊◊;

• la classe di caratteri [◊] e la classe di caratteri negata [ˆ◊];


Dgenes

abrBalpha-amylase

amyPbkdbmrURcheVClpXComKCtsRdegRDksAdltBDnaKEsig29EsigAEsigBEsigGfabLFlgMgbsAGerEkatXkdgRKinCmrpAPhoP PprosigKRpoSsigmaKsigmaHsigmaWSpoIIABspoIVCBYtxHyfhRaltri

Dinteractors

abrogationacetylationactivationbinding

conversiondestabilizationdownregulation

expressioninductioninhibitionmodulation

phosphorylationrepression

stabilizationsuppressionsynthesisacetylateactivateaffectbindblock

comprisingconjugatedestabilizedimerizeencodingenhanceexhibit

potentiateregulaterepressed

severstabilizesuppressyieldaltri

Tabella 3.1: Porzioni dei due dizionari di geni/proteine e interatori.


a Significato Sottoinsieme φ(a)

VB verb, base form

Averb

0VBD verb, past tense 1VBG verb, pres. part. or gerund 2VBN verb, past participle 3VBP verb, pres. tense, ¬3rd p. s. 4VBZ verb, pres. tense, 3rd p. s. 5JJ adjective or numeral, ordinal

Aadj

6JJR adjective, comparative 7JJS adjective, superlative 8NN noun, common, sing. or mass

Anoun

9NNP noun, proper, singular aNNPS noun, proper, plural bNNS noun, common, plural cCC conjunction, coordinating dCD numeral, cardinal eDT determiner fEX existential there gFW foreign word hIN prep. or conj., subordinating iLS list item marker jPDT pre-determiner kPOS genitive marker lPRP pronoun, personal mPRP$ pronoun, possessive nRB adverb oRP particle pSYM symbol qTO “to” as preposition or infinitive marker rUH interjection sWDT WH-determiner tWP WH-pronoun uWP WH-adverb v, comma w. sentence terminator x: colon or ellipsis y( opening parenthesis z) closing parenthesis A

altre annotazioni

GENEPTN gene or protein

A′ \AG

IVERB verb interactor RIADJ adjective interactor PINOUN noun interactor J

Tabella 3.2: Lista parziale degli elementi di A′. Per la lista completa degli elementi di A (PennTreebank Tag-set) si visiti http://www.comp.leeds.ac.uk/amalgam/tagsets/upenn.html.


◊◊

◊?+ [ˆ◊]

G ◊◊

◊◊

3 ◊++

.

c

Figura 3.2: Albero rappresentante l’espressione regolare G?+[ˆ3c++.].

• i quantificatori possessivi4 ◊*+, ◊++, ◊?+ e ◊{◊,◊}+;• il gruppo non-catturante (?:◊).

Un albero rappresenta una espressione regolare come una ricerca in profondita (depth-first search) in cui ciascun simbolo ◊ in un nodo non-terminale viene rimpiazzato dallarappresentazione del nodo figlio corrispondente. Un esempio e rappresentato in Figura 3.2.

Definizione della fitness

La fitness di un individuo r quantifica la prestazioni dello stesso sui training set. Lafitness scelta e multi-obiettivo ed e stata definita con la tupla

f(r) := (FPR(r,X−) + FNR(r,X+),FPR(r,X−), �(r)) ,

dove �(r) e la lunghezza dell’espressione regolare rappresentata da r e FPR(r,X−) eFNR(r,X+) sono il tasso di falsi positivi (False Positive Rate) e il tasso di falsi negativi(False Negative Rate), rispettivamente, di r sui training set. In dettaglio, FPR(r,X−)

4Sono stati preferiti i quantificatori possessive a quelli greedy e lazy perche questi ultimi portanoil motore Java ad effettuare il backtracking per valutare le espressioni regolari in cui sono presenti. Ilbacktracking rappresenta un collo di bottiglia per i tempi di calcolo.


e la percentuale di φ-stringhe x ∈ X− tali che x o almeno una sottostringa non-vuotadi x e accettata da r; FNR(r,X+) e la percentuale di φ-stringhe x ∈ X+ tali che x etutte le sottostringhe di x non sono accettate da r. Tutti i componenti della fitness sivogliono minimizzare. Intuitivamente, date due soluzioni candidate r1 e r2, se valgonocontemporaneamente

(i) FPR(r1, X−) + FNR(r1, X

+) < FPR(r2, X−) + FNR(r2, X

+),

(ii) FPR(r1, X−) < FPR(r2, X

−) e

(iii) �(r1) < �(r2),

allora r1 e migliore di r2. Si noti che il primo obiettivo di f(r), cioe FPR(r,X−) +FNR(r,X+), fa le veci della accuratezza della classificazione di r sugli esempi in X−, X+.

Gli individui vengono classificati in base alle loro fitness secondo il principio didominanza di Pareto e l’ordine lessicografico, come segue. In principio, gli individuivengono ordinati secondo la loro frontiera di Pareto: un individuo appartiene i-esimafrontiera se e solo se e dominato secondo Pareto solo da individui, se esistono, cheappartengono alla j-esima frontiera, con j < i—un individuo domina secondo Paretoun altro individuo se e migliore su almeno un elemento della fitness e non e peggioresugli altri. Successivamente, viene stabilito un ordinamento totale sugli individui cheappartengono alla stessa frontiera di Pareto: vengono preferiti gli individui con piu bassaFPR + FNR; in caso di uguale FPR + FNR vengono preferiti quelli con piu bassa FPR;in caso di uguale FPR vengono preferiti quelli con piu bassa �.

Come si puo notare, si e deciso di non inserire aspetti specifici del problema inesame nella definizione della fitness. Ad esempio, annotazioni POS rappresentative digeni/proteine o interatori non hanno alcuna influenza particolare su di essa. L’approcciomulti-obiettivo utilizzato ha lo scopo di massimizzare l’accuratezza e, nel contempo,promuovere soluzioni compatte prevenendo cosı il fenomeno del bloat [9]. Infine, poicheil classificatore non consiste di una singola espressione regolare ma di un insieme diespressioni generate progressivamente da training set sempre piu piccoli (Sezione 3.3),l’obiettivo FPR impone una pressione evolutiva sulle singole soluzioni atta a migliorare iltasso di falsi positivi dell’aggregazione delle stesse.

Procedura di ricerca

La procedura di ricerca GP viene eseguita con una popolazione iniziale di npop individui.La popolazione iniziale e composta di una porzione di individui generati casualmente euna porzione di individui costruiti in modo tale da accettare almeno una φ-stringa inX+. Nel dettaglio, vengono costruiti tre individui da ogni x ∈ X+:

1. un individuo r rappresentante una espressione regolare che e uguale alla φ-stringax;


2. un individuo r′ ottenuto rimpiazzando in r ogni nodo foglia non incluso in {φ(IVERB),φ(GENEPTN), φ(IADJ), φ(INOUN)} con un sottoalbero che corrisponde all’espres-sione regolare

[ˆφ(GENEPTN)φ(IVERB)φ(IADJ)φ(INOUN)] ,

ovvero con la classe di caratteri che esclude quelli che corrispondono a geni/proteinee interatori;

3. un individuo r′′ ottenuto rimpiazzando in r′ ripetizioni consecutive di caratteri chenon rappresentano geni/proteine o interatori con [ˆφ(GENEPTN)φ(IVERB)φ(IADJ)φ(INOUN)]++, ovvero con il sottoalbero che corrisponde a una o piu ripetizionidella classe di caratteri.

Se il numero di individui generati con questa procedura e maggiore di npop, vengonorimossi individui scelti a caso (con le configurazioni utilizzate nel presente lavoro questoevento non si verifica); invece, qualora il numero di individui sia strettamente minore dinpop, ne vengono generati altri in modo casuale con metodo ramped half-and-half [16]finche non viene raggiunto il limite di popolazione imposto.

La popolazione iniziale viene evoluta secondo la seguente procedura. Ad ogni iterazione(o generazione), vengono generati npop individui, di cui:

• l’80% tramite crossover tra individui della popolazione corrente;

• il 10% tramite mutazione di individui della popolazione corrente;

• il rimanente 10% a caso con metodo ramped half-and-half.

Dei 2npop individui complessivi a disposizione ne viene scartata la meta con fitnesspeggiore e i rimanenti npop diventano la nuova popolazione corrente. Sia per il crossoverche per la mutazione, la scelta di un individuo candidato viene effettuata con selezionea torneo (tournament selection): si considerano 7 individui casuali della popolazionecorrente e si sceglie quello con fitness migliore. Ogniqualvolta viene generato un individuoche rappresenta una espressione regolare non valida, esso viene scartato e ne vienegenerato un altro.

Viene inoltre effettuata l’imposizione della diversita fenotipica come segue. Se vienegenerato un individuo r1 che rappresenta la stessa espressione regolare di un altro individuor2 appartenente alla popolazione corrente, allora r1 viene scartato e si genera un altroindividuo—un meccanismo simile e utilizzato in [19] per prevenire la creazione di soluzioniduplicate. Si e osservato sperimentalmente che questo semplice meccanismo porta asoluzioni notevolmente migliori in questo scenario, con una penalizzazione trascurabiledel tempo di completamento della ricerca. E presumibile che tale miglioramento siainfluenzato dall’utilizzo di una popolazione iniziale non completamente composta daindividui generati a caso e dall’impiego di una ricerca GP multi-obiettivo. Riguardoquest’ultimo punto, si sono osservati benefici apportati dai meccanismi espliciti per lapromozione di forme di diversita tra gli individui, siano esse implementate a livello

17 Generazione del classificatore

genetipico o comportamentale delle soluzioni, oppure implementate nello spazio dellafitness [9, 6].

La ricerca GP termina quando si verifica uno dei seguenti eventi: (i) un numeroprefissato di ngen iterazioni sono state effettuate; o (ii) la tupla fitness del miglior individuoe rimasta inalterata per nstop iterazioni consecutive. L’esito della ricerca e l’espressioneregolare rappresentata dal miglior individuo della popolazione finale.

3.3 Generazione del classificatore

Inizialmente, i learning set S+L e S−

L vengono trasformati negli insiemi di φ-stringheX+

L , X−L , rispettivamente, applicando la procedura descritta nella Sezione 3.1. Succes-

sivamente, X+L , X−

L vengono campionati a caso per costruire i training set X+, X−,

rispettivamente, garantendo che |X+||X−| =

|X+L |

|X−L | .

Il classificatore e inizializzato come un insieme vuoto di espressioni regolari (C = ∅) eviene via via arricchito di elementi per mezzo della seguente procedura iterativa (doveτFPR e una soglia prefissata):

1. si effettua una ricerca GP su X+, X− e si ottiene r�;

2. se FPR(r�, X−) ≤ 1 − τFPR o la ricerca e terminata dopo aver eseguito ngen

generazioni, allora si pone C := C ∪ {r�}, altrimenti si termina;

3. si rimuove da X+ ogni φ-stringa x tale che x, o una sottostringa di x, e accettatada r�;

4. se X+ e vuoto, si termina, altrimenti si torna al passo 1.

L’esito della procedura e il classificatore C.Vengono eseguite njob esecuzioni indipendenti della procedura, tutte a partire dagli

stessi training set X+, X−, ma con differenti semi per la generazione di numeri casuali.Percio, vengono ottenuti (fino a) njob classificatori diversi5 e tra essi viene scelto quellocon minore tasso d’errore su i learning set X+

L , X−L . In altre parole, gli njob classificatori

vengono validati su dati parzialmente non disponibili durante l’addestramento, al fine diprevenire/mitigare il fenomeno dell’overfitting.

Negli esperimenti effettuati sono state utilizzate le seguenti configurazioni: τFPR = 0.7,ngen = 1000, nstop = 200, npop = 1000, njob = 8 e profondita massima degli alberi pari a15. I valori sono stati scelti dopo sperimentazioni preliminari (in particolare per ngen,npop, e njob) e considerando le proposte presenti in letteratura.

3.4 Modifiche effettuate a Regex Turtle

La versione originale del motore Regex Turtle consente di generare espressioni regolari cheaccettano stringhe composte di caratteri in codifica UTF-166, con lo scopo di individuare

5I classificatori generati negli esperimenti relativi al presente lavoro sono risultati sempre tutti diversi.6http://tools.ietf.org/html/rfc2781.


specifiche porzioni di testo. In altre parole, Regex Turtle e progettato per risolvere ilproblema della estrazione di informazione a livello di piccole porzioni di testo. L’obiettivodel presente lavoro e invece la classificazione di intere frasi.

Nella versione originale del motore, gli esempi utili ad addestrare e a validare unaespressione r (i) non rappresentano necessariamente frasi, (ii) specificano quali porzionidi testo devono essere accettate e quali non devono essere accettate da r.

Le modifiche apportate al motore permettono di generare il classificatore descritto inquesto capitolo. Anziche rimpiazzare componenti, si e scelto di scrivere nuove classi cheeriditano/implementano opportune classi/interfacce preesistenti. Cosı facendo vengonomantenute le vecchie funzionalita e la modularita del sistema: il nuovo Regex Turtle puoessere utilizzato sia per il compito di estrazione di porzioni di testo che per quello diclassificazione di frasi, scegliendo opportunamente i moduli coinvolti tramite un file diconfigurazione. Nello specifico:

• e stata scritta una nuova classe descrittiva della struttura della ricerca GP al finedi implementare la procedura separate-and-conquer con uno scenario di naturaclassificativa;

• sono state ampliate le funzionalita della classe che gestisce il dataset in modo dapoter operare la scissione del problema nella porzione risolta e non risolta, durantela procedura separate-and-conquer con scenario classificativo;

• e stata scritta una nuova classe per generare la popolazione iniziale della proceduradi ricerca GP, affinche fosse possibile generare parte degli individui a partire dalleφ-stringhe (Sezione 3.2);

• e stata scritta una nuova classe per implementare la valutazione degli individui,ovvero il calcolo di alcune prestazioni utili (come FPR e FNR) e la fitness.

Sono inoltre stati introdotti ulteriori elementi non strettamente legati al processo evolutivo,come ad esempio un modulo per l’output dei risultati su un foglio di calcolo su cloud.

Capitolo 4Dataset

In questo capitolo viene discussa nel dettaglio la costruzione del dataset utilizzato per gliesperimenti, a partire da due corpus di frasi contenute in articoli scientifici biomedici:BioCreAtIvE corpus1 (BC ) e Genic Interaction Basic Training Dataset2 (GI ).

4.1 Dataset utilizzato

Gli esperimenti sono stati condotti utilizzando un corpus di 456 frasi in lingua inglese,costruito a partire da due dataset (comprensivi di ground-truth fornita da un esperto delsettore), entrambi derivanti da competizioni di interesse biomedico riguardo l’estrazionedi interazioni tra geni e proteine. Le frasi costituenti tali dataset sono estrapolate daarticoli scientifici presenti nel database bibliografico di letteratura scientifia biomedicaPubMed. La Tabella 4.1 mostra alcuni esempi, dai quali si evince che la mera presenzadelle parole nei dizionari Dgenes e Dinteractors non e sufficiente per qualificare una frasecome contenente una interazione tra geni e proteine.

4.2 Dataset BC e GI

Il corpus BioCreAtIvE e composto da 1000 frasi codificate in formato XML. In 173 frasisono riportate interazioni tra geni e proteine, mentre le rimanenti 827 non contengonoalcuna interazione. La ground truth relativa alle frasi e descritta con una codifica nonstandard in un file di testo esterno, il quale specifica quali sono i componenti delleinterazioni delle 173 frasi. Gli elementi XML del corpus sono i seguenti:

• sentences: e l’elemento root, contiene elementi sentence;

• sentence: rappresenta la particolare frase, ha attributo id che identifica la frasestessa e contiene gli elementi gene, interactor, token ed elementi puramente testuali;

1https://www2.informatik.hu-berlin.de/∼hakenber/corpora/#bc2http://genome.jouy.inra.fr/texte/LLLchallenge/#task1

19

4. Dataset 20

Frasi in cui e presente almeno unainterazione tra geni e/o proteine

In this mutant, expressionof the spoIIG gene, whosetranscription depends onboth sigma(A) and thephosphorylated Spo0A protein,Spo0A-P, a major transcriptionfactor during early stagesof sporulation, was greatlyreduced at 43 degrees C.

These results suggestthat YfhP may act as anegative regulator for thetranscription of yfhQ, yfhR,sspE and yfhP.These results demonstrate thatsigmaK-dependent transcriptionof gerE initiates a negativefeedback loop in which GerEacts as a repressor to limitproduction of sigmaK.In this study, we usedfootprinting and gel mobilityretardation assays to revealthat bacterially sinthetizedZta fusion proteins bounddirectly to six TGTGCAA-likemotifs within DSL.

Frasi in cui non e presente alcunainterazione tra geni e/o proteine

From day 10, a significantincrease in platelet countwas observed in eight of theten patients treated withheparin (p < 0.05), withreturn to the initial valueafter heparin cessation in sixof the responders.

Two phosphopeptides,identified asRS-[32P]SGASGLLTSEHHSR andS-[32P]SGASGLLTSEHHSR, wereobtained after stoichiometricphosphorylation andtrypsinization of the peptide.

Levels of TSG-14 protein(also termed PTX-3) becomeelevated in the serumof mice and humans afterinjection with bacteriallipopolysaccharide, but incontrast to conventional acutephase proteins, the bulk ofTSG-14 synthesis in the intactorganism occurs outside theliver.

No mutations were found infollicular adenomas.

Tabella 4.1: Otto frasi del corpus utilizzato negli esperimenti, 4 che includono (sinistra) e 4che non includono (destra) interazioni tra geni e proteine. Per facilitare la comprensione, leparole appartenenti al dizionario Dgenes sono in grassetto e le parole appartenenti al dizionarioDinteractors sono in corsivo (si veda la Sezione 3.1).

21 Dataset BC e GI

• gene: contiene del testo che rappresenta un gene o una proteina, non ha attributi;

• interactor : contiene del testo che rappresenta un interatore, ha attributo pos il cuivalore rappresenta l’analisi grammaticale del testo contenuto;

• token: contiene del testo che non rappresenta un gene, una proteina o un interatore,ha attributo pos il cui valore rappresenta l’analigi grammaticale del testo contenuto,secondo lo standard Penn Treebank;

• elemento puramente testuale: utilizzato sempre per rappresentare lo spazio, vieneinterposto tra elementi gene, interactor e token.

Un esempio di frase e riportato di seguito (le righe vuote rappresentano il caratterespazio).

<sentence id="@@0006"><token pos="DT">These</token>

<token pos="NNS">observations</token>

<token pos="VB">establish</token>

<token pos="IN">that</token>

<gene>RsmC</gene>

<token pos="RB">negatively</token>

<interactor pos="VBZ">regulates</interactor>

<gene>rsmB</gene>

<token pos="NN">transcription</token>

<token pos="CC">but</token>

<token pos="RB">positively</token>

<interactor pos="VBZ">affects</interactor>

<gene>RsmA</gene>

<token pos="NN">production</token><token pos=".">.</token>

</sentence>

Il dataset Genic Interaction Basic Training Dataset e costituito da 55 esempi di interazionitra geni e proteine codificati in un formato non standard. Ogni esempio e costituito daiseguenti campi:

4. Dataset 22

• ID : l’identificativo dell’esempio;

• sentence: la frase espressa come testo semplice;

• words: suddivisione della frase in parole, dove ogni elemento e una quadrupla(indice parola, parola, indice carattere d’inizio, indice carattere di fine).

• agents: specifica gli indici delle parole che sono geni o proteine agenti, ovverocomponenti attivi dell’interazione che influenzano altri geni o proteine;

• targets: specifica gli indici delle parole che sono geni o proteine subenti, ovverocomponenti passivi dell’interazione che sono influenzati da geni o proteine agenti;

• genic interactions : coppie di indici delle parole costituenti una interazione: uno deidue indici rappresenta un componente agente, l’altro un componente subente.

Un esempio e riportato di seguito.

ID 11069677-3sentence In vivo studies of the activity of four of the kinases,

KinA, KinC, KinD (ykvD) and KinE (ykrQ), using abrB transcriptionas an indicator of Spo0A˜P level, revealed that KinC and KinD wereresponsible for Spo0A˜P production during the exponential phase

of growth in the absence of KinA and KinB.words word(0,’In’,0,1) word(1,’vivo’,3,6) word(2,’studies’,8,14)

word(3,’of’,16,17) word(4,’the’,19,21) word(5,’activity’,23,30)word(6,’of’,32,33) word(7,’four’,35,38) word(8,’of’,40,41) word(9,’the’,43,45) word(10,’kinases’,47,53) word(11,’KinA’,56,59)word(12,’KinC’,62,65) word(13,’KinD’,68,71) word(14,’ykvD’,74,77)word(15,’and’,80,82) word(16,’KinE’,84,87) word(17,’ykrQ’,90,93)word(18,’using’,97,101) word(19,’abrB’,103,106) word(20,’transcription’,108,120) word(21,’as’,122,123) word(22,’an’,125,126) word(23,’indicator’,128,136) word(24,’of’,138,139) word(25,’Spo0A˜P’,141,147) word(26,’level’,149,153) word(27,’revealed’,156,163) word(28,’that’,165,168) word(29,’KinC’,170,173)word(30,’and’,175,177) word(31,’KinD’,179,182) word(32,’were’

,184,187) word(33,’responsible’,189,199) word(34,’for’,201,203)word(35,’Spo0A˜P’,205,211) word(36,’production’,213,222) word(37,’during’,224,229) word(38,’the’,231,233) word(39,’exponential’,235,245) word(40,’phase’,247,251) word(41,’of’,253,254) word(42,’growth’,256,261) word(43,’in’,263,264) word(44,’the’,266,268)

word(45,’absence’,270,276) word(46,’of’,278,279) word(47,’KinA’,281,284) word(48,’and’,286,288) word(49,’KinB’,290,293)

agents agent(29) agent(31)targets target(35)genic_interactions genic_interaction(29,35) genic_interaction

(31,35)

23 Dettagli sulla generazione di φ-stringhe

4.3 Dettagli sulla generazione di φ-stringhe

Riguardo il dataset Genic Interaction Basic Training Dataset, la generazione delle φ-stringhe avviene esattamente come descritto nella Sezione 3.1, utilizzando i dizionari pergeni, proteine e interatori3. Per le frasi estrapolate dal corpus BioCreAtIvE, invece, estata utilizzata una procedura leggermente diversa per ottenere le φ-stringhe. Infatti,non e necessario utilizzare dizionari per identificare parole rappresentanti geni, proteine einteratori, essendo esse incapsulate in specifici elementi XML. E altresı stato possibilesfruttare le annotazioni POS gia fornite nel corpus, compatibili con lo standard PennTreebank.

La procedura di generazione di una φ-stringa x a partire da una frase s (espressain XML) del corpus BioCreAtIvE e la seguente. Per ogni elemento XML e di s, coneventuale attributo pos a, si determina la annotazione a′ ricorrendo alle casistiche:

• se e e un elemento token, si pone a′ := a;

• se e e un elemento interactor, si considerano i sottoinsiemi disgiunti Averb, Aadj eAnoun (definiti nella Sezione 3.1) e:

– se a ∈ Aadj, si pone a′ := IADJ;

– se a ∈ Anoun, si pone a′ := INOUN;

– se a ∈ Averb, si pone a′ := IVERB;

• se e e un elemento gene, si pone a′ := GENEPTN.

• infine, se e e un elemento puramente testuale, lo si ignora4;

Nota la sequenza di annotazioni {a′1, . . . , a′n}, si costruisce la corrispondente φ-stringax = φ(a′1), . . . , φ(a′n).

Si riportano due ultimi dettagli tecnici. Nel corpus BC, la frase con id @@0634presenta un interatore con annotazione POS “FW” (foreign word), quando e evidenteche si tratta di un verbo presente in terza persona singolare (“VBZ”). Infine, e statonecessario uniformare le annotazioni POS nel corpus BC relative alle parentesi aperte echiuse, rispettivamente “(” e “)”, con quelle effettuate dall’annotatore POS sviluppato dalgruppo Stanford Natural Language Processing Group, rispettivamente “LRB” e “RRB”.

4.4 Costruzione del dataset

Il dataset utilizzato nel presente lavoro e stato ottenuto per aggregazione delle 173 frasidi BC contenenti interazioni tra geni e proteine con le 55 frasi di GI, per costituire gliesempi positivi, e prelevando le prime 228 frasi di BC che non contengono interazioni,

3I dizionari sono disponibili all’indirizzo http://www2.informatik.hu-berlin.de/∼hakenber/publ/suppl/lll05/.

4Gli elementi puramente testuali del corpus BioCreAtIvE sono tutti il carattere spazio.

4. Dataset 24

per costituire gli esempi negativi. Il risultato e un corpus di 456 esempi, meta positivi emeta negativi.

La rappresentazione del dataset e stata declinata coerentemente alle specifiche delclassificatore impiegato, ovvero rispetto al classificatore ottenuto con GP e ai metodidi riferimento (discussi nel Capitolo 5). In particolare, per il classificatore ottenutocon GP, il dataset e espresso come uno specifio oggetto descritto in formato JSON ecompatibile con il motore Regex Turtle modificato per la classificazione. La separazionedel dataset in insiemi per l’addestramento, la validazione e il test avviene attraverso unfile di configurazione esterno. Per i metodi di riferimento, il dataset presenta ciascunesempio come una linea di testo ed e costituito da quattro file: addestramento positivo,addestramento negativo, test positivo e test negativo.

4.5 Dettagli implementativi

Dal punto di vista implementativo, le procedure per la generazione delle φ-stringhee per la costruzione del dataset sono state operate in modo automatico per mezzo disoftware Java e script per shell Bash appositamente preparati. Gli strumenti sviluppatihanno permesso di analizzare i dataset BC e GI, estrarre le informazioni utili, ottenere leannotazioni POS, effettuare la conversione in φ-stringhe e generare il dataset finale neiformati precedentemente descritti (Sezione 4.4), il tutto in modo automatico.

In particolare, sono state utilizzate librerie del progetto Stanford CoreNLP5 (v3.4.1)—per le operazioni tokenization e POS tagging sul dataset GI—e i package della libreriadataSetManager6—per costruire il dataset nel formato adatto al motore Regex Turtle.

5http://nlp.stanford.edu/software/corenlp.shtml.6Sviluppata dal Machine Learning Lab dell’Universita degli Studi di Trieste.

Capitolo 5Valutazione sperimentale

Al fine di valutare i risultati ottenuti con la metodologia descritta nel Capitolo 3, sono stateimplementate e utilizzate diverse tecniche alternative di classificazione come riferimenti:(i) un approccio evolutivo allo stato dell’arte per desumere pattern da esempi, (ii) dueapprocci che racchiudono una grande quantita di conoscenza specifica del problema e(iii) due metodi tradizionali per la classificazione di testo. Specificamente, nel presentelavoro si e modificata una versione sviluppata di i, implementati ex novo strumenti pereseguire ii e applicati strumenti gia pronti di iii1. Tutti gli approcci sono stati utilizzatisullo stesso dataset.

5.1 Algoritmo evolutivo per la generazione di DFA

E stato modificato e utilizzato un classificatore basato sull’algoritmo Smart State LabelingEvolutionary Algorithm (SSLEA) descritto in [21]. Il lavoro citato propone un algoritmoallo stato dell’arte per apprendere un automa deterministico a stati finiti a partire daesempi del comportamento di classificazione desiderato. SSLEA e stato sviluppato alcunianni dopo una competizione di grande influenza nella comunita del grammar learninge ha dimostrato prestazioni migliori degli strumenti vincitori della gara (e di versioniperfezionate degli stessi), sulla stessa classe di problemi [18, 8] e persino in presenza didati rumorosi.

SSLEA rappresenta una soluzione candidata come una coppia composta da un vettoredi output di dimensione n e una matrice di transizione di dimensione n× |α|, dove n e ilnumero di stati dell’automa desiderato e |α| e il numero di simboli presenti nell’alfabetoin input: il primo ha un elemento per ogni stato dell’automa e ciascun elemento contienel’etichetta (accettazione o rifiuto) dello stato corrispondente; la seconda contiene, per ognistato e transizione, l’indice del corrispondente stato di destinazione. SSLEA implementauna forma di hill-climbing in cui la fitness di una soluzione e il tasso di esempi classificati

1L’approccio evolutivo e i metodi tradizionali di classificazione sono stati forniti dal Machine LearningLab dell’Universita degli Studi di Trieste.

25

5. Valutazione sperimentale 26

correttamente. La ricerca termina qualora l’automa evoluto raggiunga la fitness perfettaoppure dopo che siano state effettuate un numero predefinito nit di iterazioni.

Le operazioni fondamentali che occorrono nell’evoluzione dell’automa sono lo SmartState Labeling e la mutazione. La prima implementa un algoritmo che si basa sullamatrice di transizione e sugli esempi di addestramento, il cui impiego consente di ridurrenotevolmente lo spazio di ricerca: per ogni stato, si contano il numero p di esempi chesi vogliono siano accettati e il numero q di esempi che si vogliono siano rifiutati cheterminano nello stato stesso, dopodiche se p > q allora lo stato viene etichettato comed’accettazione, altrimenti viene etichettato come di rifiuto. La mutazione consiste nellamodifica casuale dell’indice di uno stato di destinazione, scelto anch’esso a caso, nellamatrice di transizione.

Nel presente lavoro e stata modificata una versione gia implementata di SSLEA inlinguaggio C++ per adattarla al problema ed e stata applicata alle φ-stringhe. Il metodoe stato denominato φ-SSLEA. Dopo alcune sperimentazioni esplorative, i migliori risultatisono stati ottenuti con α = range(φ), n = 7 e nit = 5000 e tale configurazione e statautilizzata nella presente valutazione. In particolare, si e verificato sperimentalmenteche aumentare il numero nit di iterazioni disponibili, anche di molto, non porta a unamigliore accuratezza sui dati di test.

5.2 Metodi di riferimento basati sul problema

Sono stati implementati due classificatori che racchiudono una considerevole quantita diconoscenza legata allo specifico problema in esame.

Il classificatore denominato Annotations-Co-occurrence classifica positivamente unafrase s se e solo se s contiene almeno due geni/proteine e un interatore—chiaramente, epesantemente confezionato per questo particolare problema.

Il classificatore denominato Annotations-LLL05-patterns e costruito a partire dairisultati dell’articolo [13], nel quale e proposto un metodo per identificare patternsintattici ad allineamento che descrivono interazioni tra geni e proteine in testi scientifici.Un pattern ad allineamento e descritto in termini di (i) sequenze di annotazioni POSrilevanti che devono presentarsi in una frase, senza specifiche limitazioni sul tipo e sullaquantita di ulteriori annotazioni che potrebbero essere presenti tra le annotazioni salienti;(ii) dipendenze tra i componenti estratti, ovvero informazioni su quale gene/proteina ecomponente attivo (agente) e quale e componente passivo (subente) nell’interazione. Sinoti che il punto ii non e rilevante in termini di classificazione delle frasi—ma di estrazionedelle componenti di una interazione—e pertanto e stato ignorato. Il metodo sfrutta unaconsiderevole quantita di conoscenza specifica del dominio nella calibrazione di decine dicoefficienti utilizzati per pesare gli errori commessi dai pattern, errori che sono associatia specifiche annotazioni POS e annotazioni che rappresentano geni e interatori. Il lavorocitato fornisce una lista dei 10 pattern ad allineamento piu frequenti imparati su tuttoil corpus usato nell’articolo, che e piu grande di quello usato nel presente lavoro (essoconsiste di ≈ 1000 frasi). Annotations-LLL05-patterns classifica positivamente una frases se e solo se s e accettata da almeno uno dei 10 pattern ad allineamento nella suddetta

27 Metodi di classificazione tradizionali

lista. Il corpus di questo lavoro e composto, per ≈ 90%, di frasi derivate dal corpus usatonell’articolo citato.

Entrambi i classificatori sono stati realizzati per mezzo di opportune espressioniregolari Perl eseguite su shell Bash con il comando grep -P su φ-stringhe. Nello specifico,Annotations-Co-occurrence e implementato come applicazione dell’espressione regolare

G.*[JRP].*G|[JRP].*G.*G|G.*G.*[JRP] ,

la cui prima parte—ovvero cio che antecede l’operatore or “|”—e espressa in annotazioniPOS (con spazi tra gli elementi per facilitare la lettura) come

GENEPTN .* [ INOUN IVERB IADJ ] .* GENEPTN .

La classificazione operata dall’unione dei 10 pattern ad allineamento, alla base diAnnotations-LLL05-patterns, e stata implementata con l’espressione regolare

G.*R.*G|G.*J.*G|J.*G.*G ,

che accetta le φ-stringhe in cui compaiono, ordinatamente e non necessariamente inmodo consecutivo, (i) un gene/proteina, un interatore verbo e un gene/proteina, o (ii) ungene/proteina, un interatore nome e un gene/proteina, o (iii) un interatore nome e duegeni/proteine.

5.3 Metodi di classificazione tradizionali

Sono stati utilizzati due metodi di machine learning tipicamente impiegati per la clas-sificazione del testo [23], uno basato su Naive Bayes e l’altro su Macchine a Vettori diSupporto (SVM 2).

I classificatori Naive Bayes sono degli strumenti addestrati in modo supervisionato chebasano il discernimento sul teorema di Bayes. Essi assumono che le feature caratterizzantil’istanza del problema in esame, rappresentate come punti nello spazio, seguano unacerta distribuzione di probabilita (ad esempio gaussiana) e siano indipendenti tra loro(ipotesi naive). I classificatori SVM sono dei modelli di classificazione lineare, anch’essiad addestramento supervisionato e rappresentanti gli esempi come punti nello spazio. Laclassificazione avviene definendo un iperpiano che separa le categorie in modo tale damassimizzare il margine geometrico. Per rendere possibile la separazione lineare delleclassi, tali metodi ricorrono alla tecnica kernel trick, che consiste nel proiettare le istanzedel problema in un nuovo spazio di dimensioni maggiori in cui tipicamente esiste uniperpiano lineare separatore.

Come anticipato, quanto segue e stato realizzato dal Machine Learning Lab dell’Uni-versita degli Studi di Trieste.

Innanzitutto e stato effettuato il seguente pre-processamento di ogni frase s: (i) sirimpiazza ogni occorrenza di una stringa contenuta in Dinteractors con interactor;

2Dall’inglese Support Vector Machines


(ii) si rimpiazza ogni occorrenza di una stringa contenuta in Dgenes con geneptn; (iii) siconvertono tutti i caratteri di s in minuscolo; (iv) si sostituiscono tutti i caratteri nonalfabetici (precisamente quelli che sono accettati dall’espressione regolare [ˆa-zA-Z ])con uno spazio; (v) si esegue uno stemming su ciascuna parola, ad eccezione di geneptne interactor. I passi i e ii sono eseguiti al fine di sfruttare la conoscenza contenutanei dizionari, la quale non sarebbe altrimenti disponibile al classificatore.

Per costruire il classificatore:

1. Si costruisce un insieme ordinato W di parole composto di tutte le parole cheappaiono almeno una volta nei learning set S+

L , S−L ;

2. Si trasforma ciascuna frase s in un vettore �f ′ in cui l’i-esimo elemento corrispondeal numero di occorrenze in s della parola wi ∈ W ;

3. Si esegue una procedura di feature selection per identificare i k elementi di �f ′ chemeglio discriminano tra le frasi appartenenti a S+

L o S−L (si veda sotto). Sia �f il

vettore ottenuto considerando solo i k elementi scelti di �f ′—ovvero, �f contienesolo il conteggio delle occorrenze della parole selezionate nella procedura di featureselection;

4. Infine, si addestra un classificatore binario usando i vettori �f1, �f2, ..., �fn corrispon-denti alle frasi s1, s2, ..., sn nei learning set S+

L , S−L (|S+

L ∪ S−L | = n).

Una volta costruito il classificatore, al fine di classificare una nuova frase s: (i) si pre-processa s come descritto sopra; (ii) si ottiene il corrispondente vettore di feature �f ; e,infine, (iii) si fornisce �f al classificatore addestrato.

La procedura di feature selection e basata sui vettori �f ′ = [ρ1, ..., ρm], dove ρi e lai-esima feature del vettore. Tale metodo necessita di due parametri k, k′, con k′ k, elavora in due passi, come segue. Si consideri la matrice ottenuta prendendo come righe ivettori �f ′

1,�f ′2, ...,

�f ′n, ogni colonna della matrice corrisponde a una feature. Al primo passo

si calcola, per ogni i-esima ρi feature, la differenza relativa δi tra il suo valore medio sullefrasi dei due insiemi:

δi =

∣∣∣ 1|S+

L |∑

S+Lρi − 1

|S−L |

∑S−Lρi

∣∣∣

maxS+L∪S−

Lρi

Successivamente si selezionano le k′ feature con maggior δi—tra quelle per le qualimaxS+

L∪S−Lρi > 0. Al secondo passo si calcola, per ogni i-esima feature tra le k′ scelte al

passo precedente, la mutua informazione Ii con una etichetta—l’etichetta e un valorebinario che e positivo per gli elementi in S+

L e negativa per gli elementi in S−L . Si scelgono

poi le k feature con la maggiore Ii.

Nel presente lavoro sono stati utilizzati due classificatori binari precedentementerealizzati in linguaggio R secondo il metodo riportato: Words-NaiveBayes e Words-SVM.

Riguardo i parametri di feature selection k′ e k, si e posto k′ = 1000 per entrambi iclassificatori mentre il valore di k e stato scelto in modo da massimizzare l’accuratezza

29 Risultati

Classificatore Accuratezza FPR FNR

Annotations-Co-occurrence 77.8 40.0 4.5Annotations-LLL05-patterns 82.3 25.0 10.5

Words-NaiveBayes 51.3 25.0 95.0Words-SVM 73.8 29.0 23.5

φ-SSLEA 61.3 44.0 33.5C 77.0 23.5 22.5

Tabella 5.1: Risultati percentuali del metodo proposto nel presente lavoro e dei 5 metodi diriferimento, mediati sui 5 fold.

sui learning set, ovvero, k = 25 per Words-NaiveBayes e k = 50 per Words-SVM. Words-NaiveBayes assume che le feature seguano una distribuzione gaussiana. Infine, riguardoSVM, e stato utilizzato un kernel radiale Gaussiano con parametro di costo posto a 1.

5.4 Risultati

E stata eseguita una validazione incrociata a 5 fold, ovvero, sono state generate casual-mente 5 diverse istanze del problema dal corpus. Per ciascuna istanza, ≈ 80% dei datisono stati utilizzati per l’apprendimento e ≈ 20% per il test. Nello specifico, sono statiutilizzati i learning set S+

L , S−L (con |S+

L | = |S−L | = 188) per addestrare il classificatore

generato con la programmazione genetica C, φ-SSLEA, Words-NaiveBayes e Words-SVM;mentre e stata valutata l’accuratezza di tutti i metodi di classificazione su due insiemidi test (testing set) S+

T , S−T (con |S+

T | = |S−T | = 40), distinti dai precedenti. Sono stati

utilizzati gli stessi learning set e testing set per tutti i metodi considerati.

La Tabella 5.1 mostra i risultati ottenuti dai 6 metodi. I risultati sono espressi inaccuratezza, FPR e FNR, mediati sui 5 fold.

Si puo osservare che il classificatore C e quello che ottiene la maggiore accuratezza(77%) tra i 4 metodi che addestrano un classificatore solo a partire dagli esempi e daidizionari—ovvero, senza alcun indizio relativo allo specifico problema. In altre parole sie dimostrato che la programmazione genetica e di fatto in grado di dedurre pattern daesempi, anche in scenari di elaborazione del linguaggio naturale di interesse pratico.

Le accuratezze dei metodi di riferimento basati sullo specifico problema sono del 82.3%e 77.8% per Annotations-LLL05-patterns e Annotations-Co-occurrence, rispettivamente.I buoni risultati ottenuti da questi classificatori non sono sorprendenti se si considerache tali metodi sono basati su una considerevole quantita di conoscenza relativa alproblema, come spiegato precedentemente nella Sezione 5.2. Inoltre, l’accuratezza diAnnotations-Co-occurrence e solo di poco migliore di quella di C.

E interessante notare che la accuratezza ottenuta da φ-SSLEA e di molto peggiore ri-spetto a quella ottenuta dal classificatore generato con GP, nonostante i due approcci sianobasati su strumenti simili—apprendimento evoluzionistico di DFA contro apprendimentoevoluzionistico di insiemi di espressioni regolari. Sebbene questo risultato possa apparirepiuttosto insolito—come detto, φ-SSLEA e derivato da una metodologia considerata allo


r1 = G[ˆo][ˆc3G]++G[ˆzfcB][ˆzc]

r2 = .JiG.[ˆf9]

r1 = GENEPTN [ ˆ RB ] [ ˆ NNS VBN GENEPTN ] ++

GENEPTN [ ˆ \( DT NNS RRB ] [ ˆ \( NNS ]

r2 = . INOUN IN GENEPTN . [ ˆ DT NN ]

Figura 5.1: Un esempio di classificatore generato con GP composto da due espressioni regolari,mostrate sia nella loro forma originale con i simboli in U (sopra), sia usando le annotazioni (sotto).Nelle epressioni con annotazioni sono stati inseriti degli spazi fra gli elementi per facilitare lalettura.

stato dell’arte nell’addestramento di DFA—e presumibile che cio sia dovuto al fatto che iproblemi di benchmark tipici del DFA learning considerano brevi sequenze di simbolibinari, con dati di addestramento presi uniformemente dallo spazio di input. Scenari diquesto genere non calzano le problematiche di applicazioni NLP di interesse pratico, in cuisi devono affrontare sequenze di simboli molto piu lunghe, alfabeti di dimensioni maggiori,dati non presi uniformemente dallo spazio di tutte le possibili sequenze. Questa possibileinterpretazione e avvalorata dalle recenti affermazioni di diversi autori: i problemi dibenchmark per DFA learning non sono ispirati da applicazioni di interesse pratico [8] el’applicabilita dei corrispondenti algoritmi di addestramento ad altri domini applicativi eancora un argomento largamente inesplorato [4].

La Figura 5.1 mostra uno dei classificatori ottenuti con GP negli esperimenti effettuati,composto di due espressioni regolari. Al fine di facilitare la comprensione, sono riportateanche le epressioni utilizzando le annotazioni (A′) oltre che i simboli di U . Si puo osservareche le espressioni includono annotazioni salienti (GENEPTN e INOUN) nonostante ad essenon sia stato attribuito un peso speciale nel meccanismo evolutivo. I due pattern nonrisultano di facile lettura, il che non e sorprendente poiche non e stato implementato alcunmeccanismo per l’agevolazione di individui rappresentanti espressioni regolari leggibili(tale aspetto rappresenta un possibile obiettivo da perseguire per lavori futuri).

Capitolo 6Ulteriori esperimenti

Nel presente capitolo sono descritti ulteriori esperimenti eseguiti con variazioni dell’algo-ritmo φ-SSLEA e con variazioni del metodo GP. I risultati sono sempre riferiti ad unamedia su 5 fold, analogamente a quanto descritto nella Sezione 5.4.

6.1 Ulteriori esperimenti con φ-SSLEA

Il classificatore ottenuto con l’algoritmo evolutivo φ-SSLEA raggiunge il 61.3% di accura-tezza sui dati di test, con parametri n = 7 (stati dell’automa) e nit = 5000 (iterazioni).Come riportato nella Sezione 5.1, si e verificato che aumentare il numero di iterazioninon porta ad un aumento dell’accuratezza.

La Figura 6.1 mostra le prestazioni degli automi ottenuti fissando n = 7 e variando ilnumero di iterazioni effettuate dall’algoritmo evolutivo. In particolare, con 1000 e 10000iterazioni si ottiene, in entrambi i casi, un’accuratezza pari al 60.8%.

La Figura 6.2 mostra invece i risultati per automi generati con nit = 5000 e variandoil numero stati. Sono rilevanti i risultati ottenuti con 5 e 8 stati, per i quali l’accuratezzae rispettivamente del 61.0% e 59.5%.

6.2 Ulteriori esperimenti con GP

Analogamente a quanto effettuato per il metodo φ-SSLEA, sono stati condotti diversiesperimenti con i classificatori ottenuti per GP al variare dei parametri evolutivi. Si eosservato, ad esempio, il diverso comportamento di classificazione influendo sul numerodi individui nella popolazione iniziale npop, sul numero di generazioni ngen e sul numerodi esecuzioni indipendenti njob.

Sono discussi di seguito due esperimenti particolarmente rilevanti, relativi ad unadifferente metodologia evolutiva, piuttosto che alla mera messa a punto di alcun parametri.Essi sono (i) l’esperimento w/o separate-and-conquer e (ii) l’esperimento full precision. Ilprimo conduce una procedura priva del metodo separate-and-conquer, ovvero la ricerca

31

6. Ulteriori esperimenti 32

0

10

20

30

40

50

60

70

500 1000 5000 10 000 25 000

Prestazioni%

Iterazioni

AccuratezzaFPRFNR

Figura 6.1: Prestazioni di φ-SSLEA con n = 7 e nit variabile.

0

10

20

30

40

50

60

70

3 4 5 6 7 8 9 10

Prestazioni%

Stati

AccuratezzaFPRFNR

Figura 6.2: Prestazioni di φ-SSLEA con n variabile e nit = 5000.

33 Ulteriori esperimenti con GP

GP viene eseguita una sola volta e da essa si ottiene un’unica espressione regolare,addestrata su tutti i dati dei training set X+ e X−. Dal punto di vista implementativo,e sufficiente porre nstop ≥ ngen per ottenere tale comportamento. Il secondo esperimentomira a produrre un classificatore ad alta precisione ed e stato implementato utilizzandola fitness

f(r) := (FPR(r,X−),FNR(r,X+), �(r))

e imponendo τFPR = 1. La fitness f e l’ordinamento applicato—sulla dominanza diPareto prima, lessicografico poi—promuovono individui che rappresentano espressioniregolari tali da accettare pochi esempi negativi, mentre la soglia τFPR = 1 impone cheil metodo separate-and-conquer venga effettuato solo se il miglior individuo r, rimastoimmutato per nstop generazioni, e tale che FPR(r,X−) = 0.

La Figura 6.3 riporta i risultati in termini di accuratezza, FPR e FNR, relativi agliesperimenti i e ii, confrontati con l’esito del metodo “standard” esplicato nel Capitolo 3.Osservando gli istogrammi si possono trarre le seguenti conclusioni:

(i) e presumibile che le prestazioni di w/o separate-and-conquer siano inferiori rispettoa quelle di standard perche il primo affronta l’intero problema con un solo pattern,mentre il problema stesso e intrinsecamente multi-pattern;

(ii) sebbene full precision sia migliore di standard in termini di FPR, l’eccessiva pressioneevolutiva sulla precisione porta il metodo ad ottenere un pessimo tasso FNR.

6. Ulteriori esperimenti 34

0

10

20

30

40

50

60

70

80

standard w/o s&c full precision

Prestazioni%

Metodi

AccuratezzaFPRFNR

Figura 6.3: Prestazioni dei classificatori GP ottenuti con metodo standard, w/o separate-and-conquer e full precision.

Capitolo 7Conclusioni

Nel presente lavoro di tesi e stato presentato un metodo evolutivo per generare patternsintattici a partire da esempi testuali espressi in linguaggio naturale. Il metodo e statoapplicato ad un problema tanto interessante quanto arduo: la classificazione di frasipresenti in articoli scientifici del dominio biomedico. In particolare, la classificazioneeffettuata e binaria e discerne tra frasi che contegono almeno una interazione tra geni eproteine e frasi che non ne contengono alcuna.

Il metodo proposto si basa sulla programmazione genetica e trae spunto da recenti studiriguardo la generazione automatica di espressioni regolari da esempi del comportamentodesiderato. E stata inoltre studiata e applicata una tecnica per rappresentare le frasi comestringhe di simboli, le quali possono essere manipolate da comuni espressioni regolari.I simboli corrispondono ad annotazioni POS estese utilizzando dizionari relativi allospecifico problema. Lavorare al livello d’astrazione di annotazioni comporta diversivantaggi pratici, tra i quali la modularita e la possibilita di sfruttare strumenti diannotazione considerati allo stato dell’arte, costantemente aggiornati. Il numero dipattern da generare a partire da un insieme di frasi d’esempio non e noto priori, bensıviene determinato automaticamente attraverso la procedura separate-and-conquer, chescompone il problema in sottoproblemi piu semplici.

Il metodo e stato valutato su un corpus di 456 frasi etichettate a mano e confrontatocon 5 metodi di riferimento significativi. Le prestazioni di classificazione sono risultate lemigliori tra quelle dei metodi ad apprendimento. I buoni risultati ottenuti indicano chela programmazione genetica e effettivamente in grado di imparare pattern sintattici apartire da esempi, anche in scenari dell’elaborazione del linguaggio naturale di interessepratico.

E presumibile che il metodo sviluppato e i risultati conseguiti possano essere miglio-rati con l’impiego di ulteriori fonti di informazione applicate al corpus di frasi e unamodellizzazione piu espressiva del problema. Infatti, impiegare strumenti capaci di estrar-re particolari informazioni semantiche da una frase, come ad esempio l’identificazionedi entita e l’albero di dipendenze logiche tra le parole, potrebbe aiutare la capacitadiscernitiva del classificatore. Sarebbe inoltre opportuno valutare l’impiego di modelli piu

35

7. Conclusioni 36

espressivi delle espressioni regolari [7], da rappresentare opportunamente come individuidel processo di programmazione genetica.

Bibliografia

[1] A. Bartoli, G. Davanzo, A. De Lorenzo, M. Mauri, E. Medvet, E. Sorio. Automaticgeneration of regular expressions from examples with genetic programming. InProceedings of the fourteenth international conference on Genetic and evolutionarycomputation conference companion, pagine 1477–1478. ACM, 2012. [citato a p. 9]

[2] A. Bartoli, G. Davanzo, A. De Lorenzo, E. Medvet, E. Sorio. Automatic synthesisof regular expressions from examples. Computer, 47:72–80, 2014. [citato a p. 1, 9]

[3] A. Bartoli, A. De Lorenzo, E. Medvet, F. Tarlao. Learning text patterns usingseparate-and-conquer genetic programming. In 18-th European Conference onGenetic Programming (EuroGP), 2015. [citato a p. 10]

[4] J. Bongard H. Lipson. Active coevolutionary learning of deterministic finite automata.The Journal of Machine Learning Research, 6:1651–1678, 2005. [citato a p. 35]

[5] M. Bundschus, M. Dejori, M. Stetter, V. Tresp, H.-P. Kriegel. Extraction of semanticbiomedical relations from text using conditional random fields. BMC Bioinformatics,9(1):207, 2008. [citato a p. 1]

[6] E. K. Burke, S. Gustafson, G. Kendall. Diversity in genetic programming: Ananalysis of measures and correlation with fitness. Evolutionary Computation, IEEETransactions on, 8(1):47–62, 2004. [citato a p. 18]

[7] A. X. Chang C. D. Manning. Tokensregex: Defining cascaded regular expressionsover tokens. Technical report, Technical Report CSTR 2014-02, Department ofComputer Science, Stanford University, 2014. [citato a p. 42]

[8] O. Cicchello S. C. Kremer. Inducing grammars from sparse data sets: a survey ofalgorithms and results. The Journal of Machine Learning Research, 4:603–632, 2003.[citato a p. 29, 34]

[9] E. D. De Jong J. B. Pollack. Multi-objective methods for tree size control. GeneticProgramming and Evolvable Machines, 4(3):211–233, 2003. [citato a p. 16, 18]

37

BIBLIOGRAFIA 38

[10] J. Friedl. Mastering regular expressions. O’Reilly Media, Inc., 2006. [citato a p. 7]

[11] K. Fundel, R. Kuffner, R. Zimmer. Relex—relation extraction using dependencyparse trees. Bioinformatics, 23(3):365–371, 2007. [citato a p. 1, 3]

[12] S. Gupta, D. L. MacLean, J. Heer, C. D. Manning. Induced lexico-syntactic patternsimprove information extraction from online medical forums. Journal of the AmericanMedical Informatics Association, 21(5):902–909, 2014. [citato a p. 1, 3, 4]

[13] J. Hakenberg, C. Plake, U. Leser, H. Kirsch, D. Rebholz-Schuhmann. LLL’05challenge: Genic interaction extraction-identification of language patterns based onalignment and finite state automata. In Proceedings of the 4th Learning Languagein Logic workshop (LLL05), pagine 38–45, 2005. [citato a p. 1, 3, 4, 30]

[14] J. Kasprzak, M. Brandejs, et al. Improving the reliability of the plagiarism detectionsystem. Notebook Papers of CLEF, 2010. [citato a p. 4]

[15] S. Kleene. Representation of events in neuron networks and finite automata.Automata studies, Princeton, 1956. [citato a p. 7]

[16] J. R. Koza. Genetic Programming: On the Programming of Computers by Meansof Natural Selection. pagine 93–94, 1992. [citato a p. 17]

[17] S. Kulick, A. Bies, M. Liberman, M. Mandel, R. McDonald, M. Palmer, A. Schein,L. Ungar, S. Winters, P. White. Integrated annotation for biomedical informationextraction. In Proc. of HLT/NAACL, pagine 61–68, 2004. [citato a p. 1]

[18] K. J. Lang, B. A. Pearlmutter, R. A. Price. Results of the abbadingo one DFA learningcompetition and a new evidence-driven state merging algorithm. In GrammaticalInference, pagine 1–12. Springer, 1998. [citato a p. 29]

[19] W. Langdon M. Harman. Optimizing existing software with genetic program-ming. Evolutionary Computation, IEEE Transactions on, 19(1):118–135, Feb 2015.[citato a p. 18]

[20] J. Li, Z. Zhang, X. Li, H. Chen. Kernel-based learning for biomedical relationextraction. Journal of the American Society for Information Science and Technology,59(5):756–769, 2008. [citato a p. 1]

[21] S. M. Lucas T. J. Reynolds. Learning deterministic finite automata with a smartstate labeling evolutionary algorithm. IEEE Transactions on Pattern Analysis andMachine Intelligence, 27(7):1063–1074, 2005. [citato a p. 29]

[22] H. Poon, C. Quirk, C. DeZiel, D. Heckerman. Literome: Pubmed-scale genomicknowledge base in the cloud. Bioinformatics, 2014. [citato a p. 1]

[23] F. Sebastiani. Machine learning in automated text categorization. ACM computingsurveys (CSUR), 34(1):1–47, 2002. [citato a p. 31]

39 BIBLIOGRAFIA

[24] M. Volk, B. Ripplinger, S. Vintar, P. Buitelaar, D. Raileanu, B. Sacaleanu. Se-mantic annotation for concept-based cross-language medical information retrieval.International Journal of Medical Informatics, 67(1):97–112, 2002. [citato a p. 1]

[25] A. Yakushiji, Y. Miyao, T. Ohta, Y. Tateisi, J. Tsujii. Automatic constructionof predicate-argument structure patterns for biomedical information extraction.In Proceedings of the 2006 Conference on Empirical Methods in Natural Langua-ge Processing, pagine 284–292. Association for Computational Linguistics, 2006.[citato a p. 1]

[26] L. Yao, C.-J. Sun, X.-L. Wang, X. Wang. Relationship extraction from biomedicalliterature using maximum entropy based on rich features. In Machine Learningand Cybernetics (ICMLC), 2010 International Conference on, volume 6, pagine3358–3361, July 2010. [citato a p. 1]

Ringraziamenti

Apriamo le danze.

Ringrazio in primis il buon Dio della religione pseudocristiana in cui credo. Senza diLui tutto non sarebbe stato possibile. Proprio tutto.

Ringrazio i miei genitori, che hanno foraggiato i miei studi e il mio stomaco: unaspesa notevole. Solo il tempo potra rivelarci se tale scelta sia stata oculata o meno. Duebrave e oneste persone, non tutti sono fortunati quanto me. Un grazie soprattutto perl’educazione e l’affetto datomi. Spero che questo mio traguardo possa in parte ripagarelo sforzo che hanno sostenuto.

Ringrazio tutti gli altri familiari che hanno concorso a darmi affetto e incoraggiarmidurante questo percorso. Non dimentico Ottavia, la cui luce si e purtroppo spenta duranteil percoso universitario, perche so che mi e stata e mi stara sempre accanto.

Ringrazio inoltre tutte le persone che, per qualche motivo, mi vogliono bene e misono state vicine.

Ringrazio i miei amici, sia i belli quasi-quanto-me, sia i brutti e i molto brutti, pertutte le attivita extra-universitarie che hanno concorso a mantenere integra la mia sanitamentale. Ringrazio anche Daniele, compagno di intense sessioni di programmazioneper sviluppare app di successo al limite della legalita, che non rientra nelle categoriesopracitate in quanto palesemente piu bello (e piu intelligente) di me.

Ringrazio i volontari del Burlo, di cui sono diventato membro negli ultimi mesi, perchecercano di portare un sorriso ai bimbi malati e un conforto alle famiglie di queste piccoleanime. Un nobile intento. L’opportunita di partecipare a questo volontariato e una dellecose che considero piu importanti. Keep up the good work.

Ringrazio Rossella per l’aiuto a scrivere il seguente paragrafo in friulano.

O ringracii il professor Alberto Bartoli che al a permetut di puarta indenant chestetesi. Cun di plui che al e stat un otim insegnant e relator, o pensi che al sedi ancjeune grande persone. In ogni cas, cemut che si use dı, “Chi di schiena e chi di petto,tutti abbiam qualche difetto”: al e un ver pecjat che nol sedi bon di presea le gloriosemarilenghe furlane. Piu seriamente: una grande, grande persona, di cui ho tanta, tantastima. Non ha senso fare complimenti sul campo professionale, sarebbero ridondanti

41

Ringraziamenti 42

dopo che e stata riconosciuta la sua supremazia come miglior docente... xe proprio cosıcio dei.

Ringrazio Eric. Nonostante la giovine eta, un capacissimo docente. Ottimi sugge-rimenti dovuti ad una grande creativita, risposta e battuta sempre pronta1. Inoltre, esempre il migliore in qualsivoglia disciplina—a patto di restringere opportunamente ilsubset.

Ringrazio Andrea. Un postdoc di cui francamente invidio le capacita e le conoscenze.Grazie a lui mi sento un po’ meno capra. Tuttavia, ci tengo a precisare che non loringrazio affatto per i metodi di approccio fallimentari che mi ha suggerito con le ragazze:il “lui non verra” e stato uno dei miei flop peggiori. E non lo ringrazio nemmeno peraver sabotato il “posto della merenda di Marco”.

Ringrazio Fabiano. Oh sapiente dottorando, a lui, antico saggio, dedico i mieiringratiamenti in modo sı aulico, poiche da altre e lontane epoche ello giunge a noi etergo merita le miliori vocationi! Con la sua snervante pazienza e irritante riflessivita miha aiutato piu volte a trovare il bandolo della matassa, mentre io modificavo casualmenterighe di codice2, in preda allo sclero piu totale. Come per Andrea, non lo posso ringraziareper i consigli con le donne.

Possa il MaLe Lab continuare a produrre conoscenza scientifica e spadroneggiare neglialti piani del C3.

Un pensiero va poi a chi, putroppo, ci ha lasciato proprio durante questa esperienza.In effetti nessuno si aspettava che potesse durare molto e cosı e tristemente stato. Certoi segni della malattia c’erano, ha avuto spesso problemi. Ci siamo conosciuti appena, maso che restera nel mio cuore.Caro Odyssey, R.I.P. (Riposa In Pezzi).

1Purtroppo la quantita di battute e spesso compensata dalla qualita delle stesse.2In realta mi ispiravo a GP: generare tante soluzioni casuali e poi scegliere la migliore, con fitness

f = “forse cosı funziona”. Anziche crossover, facevo cross-fingers.

43 Ringraziamenti

Ultimo ma non ultimo, ringrazio me stesso. Sono soddisfatto dell’impegno profuso edi come io sia cresciuto professionalmente e umanamente in questi anni. Bravo Marco,sono fiero di me.

Classificazione di frasi in linguaggio naturale per il riconoscimento di interazioni tra geni e...

Data & Analytics

Transcript of Classificazione di frasi in linguaggio naturale per il riconoscimento di interazioni tra geni e...