Benvenuto alla pagina del corso di Metodi di Ottimizzazione per Big Data. Il corso è destinato agli studenti del primo anno dei Corsi di Laurea Magistrale in Ingegneria Informatica e Ingegneria dell'Automazione.
Consulta questa pagina per ottenere informazioni aggiornate sui seguenti argomenti:
Per ogni richiesta o dubbio scrivi a: veronica.piccialli@uniroma2.it .
Bacheca
Qui sono riportati gli avvisi e le informazioni più urgenti.
Orario delle lezioni
Semestre: II
Orari:
Ricevimento
lunedì ore 11:30 - 12:30 (stanza D2-10, Edifici Ingegneria dell'Informazione.) Per il ricevimento è necessario prenotarsi inviando un mail all'indirizzo veronica.piccialli@uniroma2.it
Obiettivi e Prerequisiti del corso
Il corso vale 12 crediti.
Obiettivi. L'obiettivo del corso è quello di introdurre all'ottimizzazione non vincolata e vincolata con attenzione alle applicazioni nel campo dell'apprendimento statistico con particolare attenzione a SVM (Support Vector Machine) e tecniche di clustering.
Prerequisiti. è raccomandabile aver seguito i moduli di Analisi Matematica 1 e 2, di Geometria 1, e di Ricerca Operativa.
Programma di massima del corso
Introduzione all'ottimizzazione: approccio modellistico
Problemi di ottimizzazione: classificazione
Problemi di Programmazione Matematica: condizioni di esistenza della soluzione
Ottimizzazione non vincolata: condizioni di ottimo, algoritmi di soluzione: condizioni di convergenza globale, ricerca di linea, cenni sul metodo del gradiente. Metodi di decomposizione.
Ottimizzazione vincolata: condizioni di ottimo e algoritmi di soluzione
Duale di Wolfe e SVM
Clustering non supervisionato: formulazione e algoritmo k-means batch e on line
Classificazione robusta
Testo adottato e altro materiale
Testi d'esame
Modalità d'esame
Date d'esame
Link utili
Questi link contengono dispense, esercizi, software freeware, curiosità relativi al mondo della ricerca operativa.
Agenda del corso
1. lunedì 04/03/19.
Introduzione al corso: esempi di problemi di decisione (Slide della lezione).
2. mercoledì 06/03/19.
Definizioni di punto di minimo locale e punto di minimo globale. Caso convesso: definizioni di insieme e funzione convessi.
3. giovedì 07/03/19.
Proposizione 1.1 del libro di testo. Convessità e differenziabilità. Esempi.
4. venerdì 08/03/19.
Esempio di funzioni convesse. Criteri per decidere se una matrice è semidefinita o definita positiva. Esercizi.5. lunedì 11/03/19.
Condizioni sufficienti di esistenza: teorema di Weierstrass (senza dimostrazione).Insiemi di livello inferiori di una funzione, coercività. Esempi di funzioni coercive. Condizioni sufficienti di esistenza basate sulla coercività della funzione obiettivo. Esempi.6. mercoledì 13/03/19.
Direzione di discesa e direzione ammissibile. Condizioni necessarie di ottimalità locale per problemi vincolati. Caso convesso. Direzioni ammissibili per insiemi descritti da vincoli lineari.7. giovedì 14/03/19.
Condizioni di ottimo per problemi con vincoli di box e per problemi con vincoli di simplesso. Esempi e esercizi.8. venerdì 15/03/19.
AMPL: introduzione al linguaggio. Esempio di file .mod e .dat.
9. lunedì 18/03/19.
Proiezione su un insieme convesso. Proprietà (con dimostrazione), riformulazione delle condizioni di ottimo tramite proiezione. Esempi di proiezione: ortante non negativo, vincoli di box.
10. mercoledì 20/03/19.
Condizioni di Fritz John. Qualificazione dei vincoli. Indipendenza lineare dei gradienti dei vincoli attivi.
11. giovedì 21/03/19.
Condizioni per problemi con vincoli di box e di simplesso tramite KKT. Proiezione su una sfera. Esercizi.
12. venerdì 22/03/19.
AMPL: esempio di problema di PL. Esempio di problema di programmazione non lineare.
13. lunedì 25/03/19.
Caso convesso: condizioni di KKT anche sufficienti. Esempi.
14. mercoledì 27/03/19.
Risultato di Vapnik. Minimizzazione del rischio strutturale: SVM e reti neurali. Iperpiano con gap di tolleranza ottimo. Caratterizzazione della distanza da un iperpiano.
15. giovedì 28/03/19.
Riformulazione del problema dell'iperpiano ottimo (Lemma 1 e Lemma 2). Esempio.
16. venerdì 29/03/19.
AMPL: problema del poligono di massima area. Introduzione agli script. Esempio di script per il problema del poligono di massima area.17. lunedì 1/04/19.
Riformulazione del problema dell'iperpiano ottimo come problema quadratico convesso. Esempi.
18. mercoledì 03/04/19.
Teoria della dualità di Wolfe. Caso generale e caso quadratico. Esempi.19. giovedì 04/04/19.
SVM lineari per insiemi linearmente separabili e non linearmente separabili.20. venerdì 05/04/19.
SVM non lineari. Funzioni kernel. Esempi.21. lunedì 08/04/19.
SVM per regressione. Esercizi.22. mercoledì 10/04/19.
Condizioni di ottimo per il problema duale di addestramento di una SVM.23. giovedì 11/04/19.
Direzioni ammissibili e di discesa a due componenti non nulle per il problema duale di addestramento di una SVM.24. venerdì 12/04/19.
SVM light: scelta del working set e criterio di arresto. Esercizi.25. lunedì 15/04/19.
Metodo delle coordinate per SVM lineari.26. mercoledì 17/04/19.
Riepilogo su SVM. Esercizi.27. giovedì 18/04/19.
Clustering. Formulazione continua del problema di k-means e equivalenza con quella binaria.28. mercoledì 24/04/19.
Algoritmo di k-means batch. Convergenza ed esempio.29. lunedì 29/04/19.
Concetti generalizzati di distanza. Clustering combinatorio: k-medoids.30. giovedì 02/05/19.
Clustering gerarchico. Esempi31. venerdì 03/05/19.
Esercitazione sul clustering. Esempi in matlab.32. lunedì 06/05/19.
Introduzione a R.33. mercoledì 08/05/19.
Data preparation in R.34. giovedì 09/05/19.
Analisi outliers, missing values e rimozione duplicati. Esempio su un dataset.35. venerdì 10/05/19.
Problemi di classificazione in R.36. lunedì 13/05/19.
Scelta del classificatore per problemi di classificazione.37. mercoledì 15/05/19.
Introduzione alla feature selection.38. giovedì 16/05/19.
Feature selection in R. Esempio.39. venerdì 17/05/19.
Descrizione del dataset del progetto.40. lunedì 20/05/19.
Alberi di decisione e classificazione. CART (Classification And Regression Trees): introduzione, notazione, pro and cons. Induction task: TDIDT e approccio Top-Down. Esempi (svolta dal Prof. Pacifici).41. mercoledì 22/05/19.
Scelta dello split test. Misure di “impurità” ai nodi: Gini index, Chi-quadro. (svolta dal Prof. Pacifici).42. giovedì 23/05/19.
Ancora sulle misure di “impurità” ai nodi: Entropia, Information Gain, Gain Ratio ed Errore di Classificazione. Cenni di complessità computazionale: definizione di Exact Cover by 3 Sets e Optimal Decision Tree. (svolta dal Prof. Pacifici).43. venerdì 24/05/19.
Riduzione di Exact Cover by 3 Sets a Optimal Decision Tree: sketch della prova. Disegno di un Optimal Classification Tree (OCT) come modello di ottimizzazione intera: preliminari. (svolta dal Prof. Pacifici).44. mercoledì 29/05/19.
OCT-MIO (Bertsimas e Dunn). Caso univariato: Definizione delle variabili. Modellare la struttura ad albero. Pruning. Consistenza con l’output dei test. Assegnamento di class-label ai nodi foglia (svolta dal Prof. Pacifici).45. giovedì 30/05/19.
Ancora sul modello MIO di Bertsimas e Dunn. Misura dell’errore di classificazione (misclassification error). Definizione della funzione obiettivo. Fattore di complessità(svolta dal Prof. Pacifici).46. venerdì 31/05/19.
Miglioramenti di OCT: warm starts. Addestramento di un albero di decisione/classificatore generato da OCT (svolta dal Prof. Pacifici).47. lunedì 3/06/19.
Estensione di OCT-MIO al caso multivariato: OCT-H (svolta dal Prof. Pacifici).48. mercoledì 05/05/19.
Bagging, Random Forests e Boosting. Stima dell’errore out-of-bag (svolta dal Prof. Pacifici).49. giovedì 06/06/19.
Un modello alternativo per la definizione di un albero di decisione/classificatore con numero massimo di nodi fissato (caso univariato) (svolta dal Prof. Pacifici).50. venerdì 07/06/19.
Classificazione robusta: robustificazione rispetto ad incertezza nella valutazione delle feature e rispetto ad incertezza nella valutazione delle label (svolta dal Prof. Pacifici).51. lunedì 10/06/19.
Ricevimento collettivo.52. mercoledì 12/06/19.
Simulazione esame.