Vladimir Vapnik
metodi statistici per l'apprendimento

F94, 6 crediti, laurea magistrale in Informatica, secondo semestre
DOCENTE: Nicolò Cesa-Bianchi

Orario lezioni:

Materiale bibliografico:

Il materiale sarà fornito dal docente sotto forma di dispense integrate da riferimenti bibliografici.

Per colmare eventuali lacune in calcolo delle probabilità e statistica e ottimizzazione non lineare si consiglia la consultazione dei testi seguenti:

Paolo Baldi, Calcolo delle probabilità e statistica (seconda edizione). McGraw-Hill, 1998.

Vincenzo Capasso e Daniela Morale, Una guida allo studio della probabilità e statistica matematica. Società editrice Esculapio, 2009.

Dimitri P. Bertsekas and John N. Tsitsiklis, Introduction to Probability (2nd edition). Athena Scientific, 2008.

Marco Trubian, Dispensa del Corso di Complementi di Ricerca Operativa.

Obiettivi: L'apprendimento automatico si occupa dello sviluppo di algoritmi per la costruzione di modelli predittivi sulla base di un insieme di osservazioni relative ad un dato fenomeno. L'apprendimento automatico è diventato uno strumento standard nelle applicazioni industriali di analisi intelligente dei dati ed è stato applicato a domini come il web, la visione, il linguaggio naturale, la biologia, e molti altri. Il corso si propone di descrivere e analizzare in termini statistici le più diffuse tecniche di apprendimento automatico, fornendo allo studente un insieme di strumenti metodologici volti alla comprensione qualitativa e quantitativa del fenomeno dell'apprendimento nelle macchine.

Programma svolto nell'anno 2010/11:

  1. Problemi di classificazione e di regressione. Funzioni di perdita. Classificatore e regressore. Apprendimento per esempi. Training set. Algoritmo di classificazione. Test set e test error. Minimizzazione del rischio empirico.
  2. Algoritmo Nearest Neighbour (NN). Famiglia kNN e forma del classificatore al variare di k. Confronto training error e test error al variare di k. Fenomeno dell'overfitting. Cross validation interna ed esterna.
  3. Predittori ad albero.
  4. Modello statistico di generazione dei dati per classificazione binaria. Rischio statistico. Classificatore Bayesiano ottimo. Test error come stima del rischio statistico. Spazio delle ipotesi o dei modelli di un algoritmo di apprendimento. Maggiorante al rischio statistico per classi finite di ipotesi. Il regressore Bayesiano ottimo nel caso di funzione di perdita quadratica.
  5. Analisi del rischio per alberi di decisione: il rasoio di Occam. Analisi del rischio per algoritmi che usano un sottoinsieme del training set: compression bounds.
  6. Classificatori lineari e Perceptrone. Teorema di convergenza del Perceptrone per training set linearmente separabili. Hinge loss. Maggiorante sul numero di errori del Perceptrone nel caso generale. Maggiorante sul rischio nel caso linearmente separabile.
  7. L'algoritmo Online Gradient Descent. Analisi. L'algoritmo Projected Online Gradient Descent. Analisi. Calcolo del rischio per il modello medio generato da OGD. OGD per funzioni di perdita fortemente convesse. Applicazione alla minimizzazione efficiente del rischio empirico.
  8. Perceptrone su grafo. Analisi mistake bound. Resistenza effettiva. Perceptrone su alberi di copertura. Alberi di copertura casuali e cammini casuali.
  9. Complessità di Rademacher. Confronto maggioranti di rischio: OGD vs. Rademacher.
  10. Le funzioni kernel. Funzioni kernel polinomiali e Gaussiane. Costruzione dello spazio indotto da un kernel.
  11. Support vector machines. Forma della soluzione per obiettivo SVM nel caso separabile. Obiettivo nel caso non linearmente separabile. Teorema di rappresentazione. Algoritmo di discesa del gradiente per minimizzazione approssimata dell'obiettivo SVM (Pegasos). Analisi di Pegasos.
  12. Boosting. AdaBoost e analisi di rischio.
  13. Problemi multiclasse e multietichetta. La riduzione one-vs-all. Il Perceptrone multiclasse. Misure di valutazione per problemi sbilanciati. Calcolo delle misure di valutazione per problemi multietichetta.

Esami

L'esame consiste in un approfondimento teorico oppure un progetto pratico. In entrambi i casi bisogna mettersi prima d'accordo col docente. Lo studente è incoraggiato a proporre lui stesso un tema che gli interessa in modo specifico.
L'approfondimento teorico è una breve relazione (una decina di pagine) su un argomento a scelta fra quelli svolti a lezione. La relazione deve occuparsi degli aspetti concettuali e formali del problema scelto fornendo la descrizione completa e dettagliata di almeno un risultato, incluse definizioni e dimostrazione formale completa di dettagli tecnici. Una possibile scaletta è la seguente:

Il progetto pratico consiste nello sviluppo di un software che implementi uno o più algoritmi di apprendimento, o varianti di uno stesso algoritmo, o un unico algoritmo con differenti valori dei suoi parametri. L'algoritmo deve essere poi sperimentato su dati reali (forniti dal docente, o proposti dallo studente). Il linguaggio utilizzato non è importante, basta che il programma funzioni con requisiti di tempo e memoria ragionevoli. La descrizione degli algoritmi e dei dataset e i risultati sperimentali presentati in forma in tabelle e/o grafici devono essere inclusi in un documento che verrà presentato all'esame.
L'approfondimento teorico e il progetto pratico, una volta ultimati, sono discussi col docente che completerà l'orale con domande generali sul resto del programma.

Avvisi:

Sfogliate le pagine del calendario e cliccate sulle date per trovare i riassunti e le date delle prossime lezioni. Cliccate poi su "altri dettagli" per avere la formattazione corretta.