Apprendimento Automatico - A.A. 2007-2008

Docente: Roberto Navigli

Docente	Telefono	Orario di ricevimento	Studio
Roberto Navigli	06-49918472	Lunedì 14:00-15:00	Via Salaria 113 - 3° Piano st. 312

Orari del corso

Quando	Dove
Martedì 13.00-15.00	aula V (matematica)
Venerdì 8.30-10.30	aula seminari DI (via salaria 113)

Introduzione

Il corso introduce un'area dell'Intelligenza Artificiale, detta appunto Apprendimento Automatico (Machine Learning). Il corso si svolge in circa 40-45 ore di lezione frontale (10-11 settimane). L'esame consiste in una prova orale, per verificare la conoscenza degli algoritmi studiati, ed una prova pratica (il progetto), sull'uso di (alcuni) degli algoritmi studiati, in vari ambiti applicativi. La prova orale può essere sostituita da una prova scritta che si terrà nei mesi di gennaio e febbraio. Verrà svolta una prova scritta in itinere (a mo' di esonero per la prima parte del programma), come per tutti gli altri corsi, nella settimana prestabilita a tale scopo ogni anno.

Durante il corso, verranno introdotti e discussi i principali algoritmi di apprendimento automatico. Gli studenti potranno, praticamente per ciascun algoritmo, effettuare delle esercitazioni pratiche utilizzando il software Weka, che mette a disposizione implementazioni dei vari algoritmi, e utilities varie per lo studio dei risultati. Viene anche messo a disposizione un sito che raccoglie dati pre-elaborati e praticamente pronti per l'utilizzo da parte di algoritmi di ML, in ambiti vari (medicina, biologia, marketing, riconoscimento di immagini, ecc.).

Avvisi

Il ricevimento del 22 settembre 2008 è spostato al 23 settembre, stessa ora.
Il ricevimento del 7 e del 21 luglio 2008 è annullato. Per favore, inviate un'email al docente per prendere appuntamento durante la settimana.
Causa esami, il ricevimento del 18 febbraio 2008 è anticipato alle ore 11.00 (fino alle ore 12.00).
Il docente sarà all'estero per motivi di ricerca dal 25 gennaio al 15 febbraio. Il ricevimento è pertanto sospeso durante quel periodo. Per qualsiasi necessità, potete contattare il docente via email.
La lezione di venerdì 14 dicembre 2007 non avrà luogo per la concomitanza con il diciottesimo incontro con le aziende: siete tutti invitati (e interessati) a partecipare! L'incontro si terrà in Aula Alfa (piano terra, via salaria), dalle ore 9.
La lezione di venerdì 30 novembre 2007 non avrà luogo.
La lezione di venerdì 2 novembre 2007 non avrà luogo.
La lezione di venerdì 5 ottobre 2007 non avrà luogo.

Appelli 2007/2008

Il prossimo appello d'esame (orale) per l'A.A. 2007/2008 si terrà il 16 settembre alle ore 9 in aula alfa (via salaria). Per prenotarvi, inviate un'email al docente.

Testi e risultati delle prove precedenti:

Argomenti trattati nel corso

Data	Argomenti	MS	PDF	Note
25 settembre 2007	Introduzione	ppt	pdf
28 settembre 2007	Apprendimento dei concetti (1)	ppt	pdf
2 ottobre 2007	Esercitazione sull'algoritmo VersionSpace	ppt	pdf
9 ottobre 2007	Apprendimento dei concetti (2), Alberi di decisione (1)	ppt	pdf
12 ottobre 2007	Alberi di decisione (2)
16 ottobre 2007	Introduzione a Weka, Reti neurali (1)	ppt ppt	pdf pdf	fino alla diapositiva 56
19 ottobre 2007	Reti neurali (2), Valutazione delle prestazioni	ppt	pdf
23 ottobre 2007	Reti neurali (3)
26 ottobre 2007	Reti neurali (4) Esercitazione su Reti neurali	doc	pdf
30 ottobre 2007	Esercitazione su alberi di decisione, Richiamo di concetti di probabilità	doc ppt	pdf
6 novembre 2007	Apprendimento Bayesiano (1)	ppt	pdf
9 novembre 2007	Esercitazione di preparazione all'esonero
13 novembre 2007	Prova intermedia		pdf
20 novembre 2007	Apprendimento Bayesiano (2), Esercitazione su Naive Bayes, Weka per Reti Neurali e Naive Bayes	doc	pdf	File ARFF per XOR e risoluzione dell'ambiguità delle parole (training e test set)
23 novembre 2007	Algoritmi Genetici, Programmazione Genetica	ppt	pdf	Funzione di fitness per JGap: il valore della f è il valore decimale dell'istanza Semplice esempio di AG con JGap
27 novembre 2007	Apprendimento non supervisionato	ppt	pdf
4 dicembre 2007	Presentazione dei progetti
7 dicembre 2007	Apprendimento per Rinforzo	ppt	pdf
11 dicembre 2007	Support Vector Machines (1)	ppt	pdf
18 dicembre 2007	Support Vector Machines (2), Metodi di Ensemble (1)	ppt	pdf
21 dicembre 2007	Metodi di Ensemble (2), Valutazione delle Prestazioni (2)	ppt
8 gennaio 2008	Esercitazione di preparazione all'esame
11 gennaio 2008	Esercitazione di preparazione all'esame
15 gennaio 2008	Secondo esonero			Portate una calcolatrice scientifica!

Programma dettagliato

Introduzione. Il problema dell'apprendimento. Classificatori. Addestramento. Rappresentazione del dominio. Funzione obiettivo e funzione appresa.

Apprendimento di concetti. Rappresentazione delle ipotesi, spazio delle ipotesi. Algoritmo FIND-S. Algoritmo VersionSpace. Concetto di bias o inclinazione. Studio delle curve di apprendimento. Sovradattamento, rumore, attributi irrilevanti.

Alberi di decisione. Caratteristiche. Principio del rasoio di Occam. Algoritmo ID3, concetto di entropia, stima dell'entropia di una classificazione, misure di impurità di una classificazione. Scelta dell'attributo migliore: guadagno informativo e gain ratio. Problemi dell'apprendimento: sovradattamento (reduced error pruning, rule error pruning), valori mancanti. Alberi di decisione con Weka.

Reti Neurali. Storia delle reti neurali. Neurone, rete neurale, caratteristiche. Percettrone, funzione somma e funzione soglia o di attivazione, funzione obiettivo. Funzioni rappresentabili con il percettrone, algoritmo di addestramento del percettrone, convergenza del percettrone. Discesa del gradiente (delta rule), discesa del gradiente stocastica. Reti stratificate alimentate in avanti, algoritmo di Back Propagation. Condizioni di terminazione, convergenza, momento. MultilayerPerceptron con Weka.

Apprendimento Bayesiano. Richiami di calcolo delle probabilità: spazio di campionamento, esiti, eventi, probabilità, probabilità condizionata, somma di probabilità, probabilità congiunte, proprietà fondamentali, teorema di Bayes, variabili aleatorie discrete e continue, massa di probabilità, densità di probabilità, distribuzione di probabilità, valore atteso, varianza, scarto quadratico, distribuzione gaussiana. Teorema di Bayes nell'Apprendimento Automatico, MAP (Maximum A Posteriori) learning, MAP learning per l'apprendimento di concetti, Maximum Likelihood Learning, Optimal Bayes, Naive Bayes. Naive Bayes con Weka.

Algoritmi Genetici. AG: Motivazioni. Algoritmo tipo. Rappresentazione delle ipotesi. Operatori per gli algoritmi genetici. Selezione delle ipotesi migliori. GABIL. Il problema del crowding e possibili soluzioni. Programmazione genetica. Passi preparatori per la PG. Il problema dei blocchi. Algoritmi genetici con JGap.

Apprendimento Non Supervisionato. Unsupervised Learning: Motivazioni. Tecniche di clustering: clustering gerarchico e clustering partitivo. Clustering gerarchico agglomerativo e divisivo. Clustering partitivo: k-means, metriche di distanza, scelta dei semi per k-means. Hard e soft clustering. Fuzzy k-means. Problemi nell'apprendimento non supervisionato.

Apprendimento per Rinforzo. Apprendimento per Rinforzo: Motivazioni. Definizione del modello. Obiettivi. Varianti. Q-Learning: algoritmo, condizioni di convergenza, scelta delle azioni future. Q-Learning per il caso non deterministico.

Support Vector Machine. Macchine a vettori di supporto. Margine di classificazione. Vettori di supporto. SVM lineare. Moltiplicatori Lagrangiani: problema primario e problema duale. Soft Margin Classification. SVM non lineare. Funzioni kernel.

Metodi di Ensemble. Combinare i classificatori: voting semplice e pesato. Generare i classificatori: Bagging, Boosting, AdaBoost.

Valutazione delle Prestazioni. Modalità di test di un classificatore. Matrice di confusione. Misure per valutare le prestazioni: precisione, recall, TP e FP rate, accuratezza, F1 measure, scelta delle misure appropriate. Test chi quadrato per l'indipendenza statistica, applicazione al confronto tra risultati su campioni e classificatori differenti.

Testi

Il testo adottato è:

Tom Mitchell, Machine Learning, Mc Graw-Hill, 1997, testo aderente a una buona parte del corso, da complementare con il materiale fornito

Per approfondire alcuni argomenti, si consiglia il seguente testo:

Ethem Alpaydin, Introduction to Machine Learning, MIT Press, 2004

cui si aggiungono i lucidi usati dal docente e alcuni articoli di approfondimento.

Progetto

Il progetto per l'A.A. 2007-2008 può essere scelto da un insieme di 6 proposte del docente (o anche proposto dallo studente, previa accettazione del docente). Informazioni dettagliate sul progetto su questa pagina.

Materiale utile

Di seguito trovate materiale utile per lo svolgimento delle esercitazioni e del progetto:

C4.5: un tool per l'apprendimento di alberi di decisione (programma C4.5)
WEKA:Suite che implementa vari metodi di apprendimento automatico. Il sito WEKA contiene un ambiente sperimentale Java in cui sono implementati i più noti algoritmi di apprendimento automatico (apprendimento rule-based, apprendimento bayesiano, reti neurali, ecc.). La documentazione di Weka è disponibile cliccando qui.
Come utilizzare Weka per apprendere alberi di decisione. Contiene anche una discussione dei parametri del classificatore J48
JGap: una suite per lo sviluppo di algoritmi genetici in Java
Dal sito Machine Learning Repository Content Summary potete scaricare vari data set che si riferiscono a diverse possibili applicazioni di data-mining e classificazione automatica (dati genetici, medici, transazioni commerciali, immagini,...)
L'uso di Java per l'Apprendimento Automatico (in inglese)
Repository per algoritmi e programmazione genetica
Servizio online per test chi quadro per l'uguaglianza di distribuzioni (utilizza il fattore correttivo 0.5)