Argento per il «Machine Learning Lab» dell’Università di Trieste agli «Human Competitive Awards»
Il «Machine Learning Lab» si occupa di applicazioni ingegneristiche delle tecniche di apprendimento automatico (machine learning), una disciplina di grande attualità e con numerose applicazioni nella vita quotidiana di tutti noi: filtri antispam, riconoscimento facciale, scrittura vocale, traduzione automatica, raccomandazione di testi e contenuti multimediali, previsioni dei mercati e molte altre.
Il team di ricercatori del «Machine Learning Lab» dell’Università di Trieste, diretto dal Professor Alberto Bartoli, si è aggiudicato la medaglia d’argento agli «Human Competitive Awards», prestigiosa competizione scientifica di caratura internazionale, giunta alla 13-esima edizione e tenutasi recentemente a Denver (Colorado). Il campo di gara era rappresentato dai sistemi di apprendimento automatico. E, in particolare, l’ideazione di sistemi realizzati con tecniche di programmazione evoluzionistica, ispirate ai meccanismi biologici di selezione naturale.
dott. Fabiano Tarlao, dott. Andrea De Lorenzo, prof. Eric Medvet, prof. Alberto Bartoli.
Composto dal prof. Alberto Bartoli, il prof. Eric Medvet, il dott. Andrea De Lorenzo (che ha presentato il lavoro) e il dott. Fabiano Tarlao, Il team triestino ha presentato un sistema per la costruzione automatica di espressioni regolari a partire solo da esempi del comportamento desiderato. Per espressioni regolari s’intendono quei programmi che consentono di identificare, in testi anche molto lunghi, delle porzioni che abbiano una struttura sintattica comune: date, nomi, numeri di telefono e così via.
Sono molto utilizzate per l’estrazione di testo e il rilevamento di pattern testuali, ma costruire un’espressione regolare comporta una notevole abilità, competenza e creatività.
Il «Machine Learning Lab» ha indagato la possibilità per una macchina di surrogare queste qualità e costruire automaticamente le espressioni regolari per compiti di realistica complessità. L’indagine si è svolta attraverso un esperimento su larga scala che ha coinvolto più di 1700 utenti su 10 compiti impegnativi di estrazione di testo, da attuare con la scrittura di una espressione regolare appropriata.
I 10 task proposti comprendono, ad esempio, l’estrazione automatica da documenti testuali di: indirizzi IP, indirizzi MAC, numeri di telefono, il nome di autori da note bibliografiche in formato bibtex, headings HTML.
L’esperimento con gli utenti umani si è svolto attraverso una sfida, proposta nella forma di un gioco online, ancora disponibile alla seguente URL http://play.inginf.units.it/.
Si sono confrontate le soluzioni costruite dagli utenti umani con quelle costruite in modo automatico dalla macchina, ovvero dall’algoritmo genetico proposto dal «Machine Learning Lab».
La qualità delle soluzioni costruite automaticamente è risultata simile alla qualità di quelle costruite dal gruppo di utenti più abile e il tempo di costruzione automatica delle soluzioni è risultato simile al tempo richiesto dagli utenti umani.
Il sistema del «Machine Learning Lab» è dunque il primo ad avere dimostrato accuratezza e velocità in linea con gli operatori umani esperti, su problemi di interesse pratico.
Negli algoritmi genetici ogni soluzione a un problema - la soluzione potrebbe essere una formula o un programma - viene convertita in una rappresentazione detta “genotipo” che ha lo stesso ruolo del DNA in un essere vivente. Il genotipo può essere ad esempio una stringa binaria o anche una sequenza di numeri o un albero sintattico.
play.inginf.units.it
Gli algoritmi genetici partono da un insieme iniziale di soluzioni - dette individui - approssimative o causali e per ognuna di esse misurano la fitness, ovvero la sua bontà al fine della soluzione di un problema. Successivamente creano un nuova generazione di soluzioni effettuando delle operazioni di mutazione (mutation) e incrocio (crossover) delle migliori soluzioni precedenti.
Nel dettaglio, l’operazione di mutation modifica casualmente una parte del genotipo di una soluzione precedente, mentre il crossover produce il genotipo di nuovi individui “mischiando” il genotipo di due soluzioni precedenti.
Il procedimento dato da (i)valutazione della fitness-bontà-degli individui della generazione corrente, (ii)mutation/crossover dei migliori individui della generazione corrente al fine di creare una nuova generazione di individui, viene iterato moltissime volte fino al raggiungimento di una soluzione soddisfacente. Il calcolo evoluzionistico include una varietà enorme di strategie e approcci. Nello specifico la soluzione proposta dal «Machine Learning Lab» ricade nel tree based Genetic Programming (GP), e adotta un approccio multiobiettivo - multiobjective optimization - per la ricerca delle soluzioni migliori. Con il metodo GP le espressioni regolari sono state rappresentate in un genotipo costituito da un albero sintattico, mentre la ricerca multiobiettivo tiene conto di molti indici diversi per valutare la bontà delle soluzioni ottenute e selezionarle per la mutation e crossover.
Riferimenti bibliografici
Bartoli, Alberto, et al. “Inference of regular expressions for text extraction from examples.” IEEE Transactions on Knowledge and Data Engineering 28.5 (2016): 1217-1230.
Bartoli, Alberto, et al. “Can A Machine Replace Humans In Building Regular Expressions? A Case Study.”
http://machinelearning.inginf.units.it/publications