Corso di Apprendimento Automatico - A.A. 2008/2009

Docente	Telefono	Orario di ricevimento	Studio
Roberto Navigli	06-49918472	Per appuntamento	Via Salaria 113 - 3° Piano st. 312

Orari del corso

Quando		Dove
Martedì	15.45-17.15	Aula I NEC
Mercoledì	14.10-15.45	Aula I NEC

Avvisi

• Sono online le soluzioni delle prove intermedie del 21 aprile (compito A, compito B)
• Sono online i risultati della prova intermedia del 21 aprile.
• Le lezioni del 31 marzo e 1 aprile non avranno luogo, causa partecipazione del docente a una conferenza.

Importante! Iscrizione al gruppo Google

Tutti gli studenti del corso sono pregati di iscriversi al gruppo Google accessibile cliccando qui. Il gruppo ha diversi fini:

• Permettere agli studenti di scambiarsi opinioni e informazioni sul corso e sul progetto
• Ricevere informazioni relative al corso dal docente
• Colloquiare col docente fuori dell'orario di lezione
• Discutere il progetto

Introduzione

Il corso introduce un'area fondamentale dell'Intelligenza Artificiale, detta Apprendimento Automatico (Machine Learning). Il corso si svolge in circa 40-45 ore di lezione frontale (10-11 settimane). Durante il corso, verranno introdotti e discussi i principali approcci all'apprendimento automatico (metodi supervisionati, non supervisionati, apprendimento per rinforzo, ecc.). Gli studenti potranno effettuare delle esercitazioni pratiche utilizzando il software Weka, che mette a disposizione implementazioni dei vari algoritmi e utilità varie per lo studio dei risultati.

Testi

Il testo adottato è:

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

Per approfondire alcuni argomenti, si consigliano i seguenti testi:

• Ethem Alpaydin, Introduction to Machine Learning, MIT Press, 2004
• Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining, Pearson Addison Wesley, 2005

cui si aggiungono i lucidi usati dal docente.

Modalità d'esame

L'esame consiste in una prova orale, per verificare la conoscenza degli algoritmi studiati, ed un progetto, sull'uso di (alcuni) degli algoritmi studiati, in vari ambiti applicativi. La prova orale può essere sostituita da una prova di esonero che si terrà all'incirca a metà corso (il 21 aprile 2009, in orario di lezione).

Il progetto può essere svolto da soli o in gruppo (normalmente 2 studenti, eccezionalmente 3 se giustificato adeguatamente). In un progetto di gruppo dovrà essere messo in evidenza il contributo di ciascun partecipante mediante una chiara suddivisione in moduli. Ciascuno studente sarà esaminato su tutto il progetto e, in profondità, sul modulo di sua competenza. Il progetto viene assegnato dal docente. L'elenco dei progetti si trova sul gruppo Google del corso, che permette l'interazione tra studenti e docente sul progetto.

Testi d'esame degli anni precedenti

• Esonero 13/11/2007
• Esonero 15/01/2008
• Esame 22/01/2008
• Esame 21/02/2008

Diario delle lezioni

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.

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.

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. Teorema di Bayes nell'Apprendimento Automatico, Naive Bayes.

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. II problema del commesso viaggiatore. Applicazioni. Programmazione genetica. Passi preparatori per la PG. Il problema dei blocchi. Meta-programmazione genetica. Applicazioni.

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.

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 prossimità (distanza e similarità), scelta dei semi per k-means. Clustering basato su grafi. Clustering basato sul minimo albero ricoprente. Hard e soft clustering. Problemi nell'apprendimento non supervisionato. Misure di valutazione esterna: entropia e purezza.

Apprendimento basato su istanze. Motivazioni. Lazy learning. Algoritmo k-nearest neighbour (k-NN).

Valutazione delle Prestazioni. Modalità di test di un classificatore. Matrice di confusione. Misure per valutare le prestazioni: precisione, recall, accuratezza, F1 measure, scelta delle misure appropriate.

-- RobertoNavigli - 06 Oct 2009