Universit` a degli Studi di Torino
Dottorato di Ricerca in Informatica XVI Ciclo
Relazione sull’ attivit` a svolta dal Dott. Alessandro SERRA
Presso il
Dipartimento di Informatica
Universit` a del Piemonte Orientale ”Amedeo Avogadro”
Supervisore: Prof. Luigi Portinale
Il sottoscritto Alessandro Serra ha preso servizio come dottorando nel Gennaio del 2001 presso il Dipartimento di Scienze e Tecnologie Avanzate dell’ Universit`a del Piemonte Orientale.
Nel 2002 `e passato all’ allora appena nato Dipartimento di Informatica della stessa Universit`a.
Il supervisore di Alessandro Serra `e stato, fino a Novembre del 2002, il Prof. Attilio Giordana.
Sucessivamente, per motivi legati allo svolgimento della tesi, il supervisore `e diventato il Prof.
Luigi Portinale.
Nel Novembre del 2003, il sottoscritto Alessandro Serra, ha chiesto al Collegio dei Docenti e al Magnifico Rettore dell’ Universit`a di Torino di godere del beneficio di rinvio di un anno dell’
esame finale di dottorato. La richiesta `e stata accettata.
A partire dal 15 Marzo del 2004, il sottoscritto Alessandro Serra lavora come ricercatore nel gruppo di Informatica Medica e Telemedicina presso ITC-IRST di Trento.
Segue una descrizione dell’ attivit`a svolta nei tre anni di dottorato, anni accademici 2000/2001, 2001/2002 e 2002/2003.
Corsi Frequentati
Il sottoscritto, oltre ad aver partecipato a lezioni e seminari sia presso il Dipartimento di In- formatica dell’Universit`a di Torino che presso il Dipartimento di Informatica dell’Universit`a del Piemonte Orientale, ha frequentato i seguenti corsi.
Presso la Scuola Nazionale dei Dottorandi di Informatica (SNDIS01) tenutasi a Bertinoro (Forl`ı) dal 21 Maggio al 1 Giugno 2001:
• Sistemi Distribuiti su Larga Scala (SDLS) (20 ore) Prof. Fabio Panzieri (Universit`a di Bologna)
• Algoritmi Probabilistici (AP) (20 ore) Prof. Andrea Clementi (Universit`a di Roma ”La Sapienza”)
• Analisi e Verifica di Programmi via Interpretazione Astratta (AVPIA) (20 ore) Prof. Gior- gio Levi (Universit`a di Pisa)
Presso la facolt`a di Scienze MFN dell’Universit`a del Piemonte Orientale:
• Linguaggi di Programmazione: Linguaggi Avanzati. Prof. Daniele Theseider Dupr´e. 2 moduli 40 ore.
Presso Dipartimento di Informatica dell’Universit`a di Torino:
• Agenti Intelligenti. Responsabile Prof. Martelli. Corso di Dottorato. 2 moduli 40 ore.
Esami sostenuti Ha sostenuto i seguenti esami:
• Sistemi Distribuiti su Larga Scala (SDLS) (20 ore) Prof. Fabio Panzieri (Universit`a di Bologna)
• Algoritmi Probabilistici (AP) (20 ore) Prof. Andrea Clementi (Universit`a di Roma ”La Sapienza”)
• Linguaggi di Programmazione: Linguaggi Avanzati. Prof. Daniele Theseider Dupr´e. 2 moduli 40 ore.
• Agenti Intelligenti. Responsabile Prof. Martelli. Corso di Dottorato. 2 moduli 40 ore.
per un totale di 6 moduli (120 ore in totale) previsti per il corso di dottorato del XVI ciclo.
Attivit`a di Ricerca
L’attivit`a di ricerca si inquadra nell’ ambito del Machine Learning e del Data Mining.
Nel primo anno di dottorato ha principalmente portato avanti il lavoro della Tesi di Laurea,
”Apprendimento di Relazioni in Presenza di Transizioni di Fase”, riguardante l’apprendimento di relazioni e il loro legame con le transizioni di fase. Conseguentemente al quale sono stati presentati due articoli da conferenza.
Successivamente le tematiche affrontate sono state a supporto dei progetti di ricerca a cui ha partecipato (vedere sezione Progetti di Ricerca) con particolare attenzione verso l’ apprendimento di dati complessi, tipo immagini o sequenze, e sulla costruzione di ipotesi complesse a partire da ipotesi pi`u semplici. Quest’ultimo argomento `e alla base della Tesi di Dottorato.
L’ attivit`a di ricerca `e stata svolta principalmente in collaborazione con i Prof. Attilio Giordana e Lorenza Saitta.
Tesi: Breve Introduzione
La classificazione `e uno dei problemi base nell’analisi dei dati e nel Machine Learning. Uno dei pi`u importanti e recenti sviluppi nelle metodologie di classificazione `e il boosting. Il Boosting produce una sequenza di ipotesi e utilizza una strategia di voting pesata per combinarne le risposte. In molti problemi il boosting `e pi`u accurato di learner classici come C4.5, ma le ipotesi che esso genera sono pi`u complesse e difficilmente interpretabili. Tra i metodi di classificazione utilizzati normalmente che generano delle ipotesi semplici ci sono, oltre a quelli simbolici, le reti bayesiane. Le reti bayesiane di classificazione, na¨ıve o anche pi`u strutturate, hanno prestazioni comparabili con C4.5.
I learner tipo C4.5, o in generale quelli simbolici, ad esempio CART e RIPPER, combinano logicamente degli attributi in modo da ottenere delle formule che siano correlate con il concetto
I learner di reti bayesiane, sia generici che specializzati nel problema di classificazione sono utilizzati per ragionare o prendere decisione sotto l’incertezza utilizzando solo l’evidenza cor- rentemente disponibile. Essi cercono di costruire solo dipendenze/indipendenze probabilistiche fra gli attributi in input e il concetto da apprendere, limitando il pi`u possibile il numero di parametri da stimare. Questo `e utile se gli attributi sono indipendenti e pessimo se il concetto
`e fortemente correlato da dipendenze logiche o deterministiche fra gli attributi.
Per cercare di mettere a disposizione del learner delle feature pi`u significative si possono uti- lizzare delle tecniche di feature selection, construction e abstraction. Queste tecniche applicate precedentemente al learner, o durante l’apprendimento, dovrebbero selezionare/costruire delle feature interessanti. Nelle reti bayesiane `e spesso utilizzata la feature selection. L’astrazione viene utilizzata normalmente per aggregare i possibili valori di una variabile. La feature con- struction viene normalmente lasciata al esperto del dominio. Queste tecniche risultano essere comunque molto limitate.
Un altro problema nell’ apprendimento di reti bayesiane di classificazione `e la stima dei parametri. Nelle reti bayesiane generali i parametri vengono stimati indipendentemente uno dall’altro con tecniche di statistica frequentistica o bayesiana. I classificatori generati con questa tecnica vengono chiamati generativi. Nelle reti di classificazione il metodo precedente non `e pi`u ottimale. Esistono molti metodi alternativi per stimare parametri basati sulla massimizzazione dell’accuratezza o utilizzando tecniche di Logistic Regression. I classificatori generati con questi metodi vengono detti discriminativi e sono normalmente pi`u accurati ma computazionalmente pi`u costosi e rendono i parametri dipendenti uno dall’ altro.
Il boosting combina in modo numerico differenti ipotesi al fine di ottenere una classificazione migliore. L’insieme delle ipotesi viene chiamato ensemble ed `e un classificatore di tipo discrimi- nativo. Ogni ipotesi che compone l’ensemble ha un peso (parametro) associato che ne indica la bont`a. Il boosting si comporta quasi sempre meglio di altri learner. Una grossa limitazione `e che la bont`a di un ipotesi risulta per`o essere dipendente dalle ipotesi precedenti. Questo limita fortemente la possibilit`a di dare un’ interpretazione dell’ipotesi generata e di revisionare l’ipotesi al soppraggiungere di nuova conoscenza. Una versione pi`u generica del boosting, chiamata real adaboost, puo essere vista come un approsimazione, Additive Logistic Regression Model, della distribuzione a prosteriori delle classi del concetto condizionate algli attributi di base. Un buon esempio dell’utilizzo del boosting su delle regole `e Splipper.
Scopo delle tesi `e di presentare un nuovo modello di apprendimento di reti bayesiane di classificazione dove i nodi possono essere delle feature complesse costruite a partire dagli attributi di base. Il modello di apprendimento, chiamato BN CF C(Learning Bayesian Network Classifier using Feature Construction), `e analogo a Real Adaboost. Logicamente la maggiore differenza sta nella sostituzione di un algoritmo di feature construction al posto di un weak learner mantenendo la stessa complessit`a computazionale. Lo scopo del feature construction `e quello di combinare logicamente gli attributi di base delle istanze, mentre il goal della rete bayesiana `e di combinare probabilisticamente le nuove feature. La rete bayesiana cos`ı costruita pu`o anche essere vista come un ensemble di tipo generativo. Questo modello riesce a risolvere le limitazioni, precedentemente citate, sia delle reti bayesiane classiche che degli ensemble discriminativi.
I risultati sperimentali mostrano che l’accuratezza dei claffificatori BN CF C nei problemi di classificazione classici `e migliore sia delle tecniche classiche, come C4.5, che delle reti bayesiane di classificazione. Rispetto ai classificatori di tipo disctriminativo hanno per`o normalmente prestazioni peggiori anche se richiedono meno esempi.
Progetti di Ricerca
Durante il dottorato ha partecipato al progetto europeo MiningMart che lo ha portato a collabo- rare sia con grosse aziende, TILAB (Italy) e SwissLife (Zurich - Switzerland), che con importanti Universit`a straniere, University of Dortmund (Germany).
• Il progetto europeo MiningMart sponsorizzato da Information Societies Tecnology (IST) ha riguardato lo sviluppo di nuovi strumenti per le applicazioni di Data Mining (DM).
In particolare il sottoscritto ha lavorato su aspetti riguardanti il settaggio automatico dei parametri e sul problema dell’integrazione nell’ambiente di DM di differenti algoritmi di Machine Learning: apprendimento di alberi di decisione e di regole di decisione, segmen- tazione dati, feature construction e analisi di sequenze. Ha collaborato alla stesura
– del Deliverable 4.1. Informed Parameter Setting.
– e del Tecnical Report 12.4.
Ha inoltre collaborato con l’Alenia Spazio
• Il progetto con l’Alenia Spazio ha riguardato la semi-automatizzazione del processo dei Verifica e Testing (AIV - Assembling Integration and Verification) dei moduli spaziali.
e ha partecipato attivamente a dei progetti dei Dipartimenti di cui ha fatto parte.
• Ha collaborato, all’interno del DISTA (Dipartimento di Scienze e Tecnologie Avanzate), ad un progetto riguardante la raccolta e l’analisi di dati sullo stato di salute delle cozze. In particolare ha lavorato allo sviluppo e all’assemblaggio di algoritmi di Machine Learning.
• Ha collaborato, e sta tutt’ora collaborando, all’ amministrazione di un cluster di 32 PC del dipartimento di Informatica dell’ Universit`a Amedeo Avogadro.
Pubblicazioni
• Alessandro Serra, Attilio Giordana, Lorenza Saitta. Learning On the Phase Transition Edge. In proc. of the 17th International Joint Conference on Artificial Intelligence, Seattle, Washington, USA, August 2001.
• Lorenza Saitta, Attilio Giordana, Serra Alessandro. A Monte Carlo Approach to Hard Relational Learning Problems. In proc. of the 7th Conference of the Italian Association for Artificial Intelligence.
Partecipazione a Conferenze
• Eighteenth International Conference on Machine Learning (ICML01), Williams College, USA, June 2001
• Seventeenth International Joint Conference on Artificial Intelligence (IJCAI01), Seattle,
Presentazione a Conferenze
• Seventeenth International Joint Conference on Artificial Intelligence, Seattle, Washington, USA, August 2001. Alessandro Serra, Attilio Giordana, Lorenza Saitta. Learning On the Phase Transition Edge.
In Fede Alessandro Serra
