Metodi di Ottimizzazione per Big Data (MOBD)

A.A. 2018-2019



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:

  1. lunedì ore 9:30-11:00 in Aula C6 (Nuovo Complesso della didattica);
  2. mercoledì ore 9:30-11:00 in Aula C6 (Nuovo Complesso della didattica);
  3. giovedì ore 14:00-15:30 in Aula B2 (Nuovo Complesso della didattica);
  4. venerdì ore 14:00-15:30 in Aula C6 (Nuovo Complesso della didattica);

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

  1. Luigi Grippo, Marco Sciandrone, Metodi di Ottimizzazione Non Vincolata, Springer, Unitext 2011. Errata Corrige
  2. Marco Sciandrone, Support Vector Machines. Errata Corrige
  3. Marco Sciandrone, Clustering e metodi di decomposizione.
  4. I seguenti testi sono disponibili presso il mio ufficio:
    a. Olvi L. Mangasarian, Nonlinear Programming, SIAM Classics in Applied Mathematics.
    b. Jorge Nocedal, Stephen J. Wright, Numerical Optimization, Springer.
    c. Dimitri P. Bertsekas, Convex Analysis and Optimization, Athena Scientific.
    d. Dimitri P. Bertsekas, Nonlinear Programming, Athena Scientific.
    e. J.E. Dennis, Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM Classics in Applied Mathematics.


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. Esempi

    31. 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.