OPTIMIZATION | Università degli studi di Bergamo

OPTIMIZATION

Modulo Generico
Codice dell'attività formativa: 
38091-MOD1

Scheda dell'insegnamento

Per studenti immatricolati al 1° anno a.a.: 
2021/2022
Insegnamento (nome in italiano): 
OPTIMIZATION
Tipo di attività formativa: 
Attività formativa Affine/Integrativa
Tipo di insegnamento: 
Opzionale
Settore disciplinare: 
RICERCA OPERATIVA (MAT/09)
Anno di corso: 
1
Anno accademico di offerta: 
2021/2022
Crediti: 
3
Responsabile della didattica: 

Altre informazioni sull'insegnamento

Ciclo: 
Secondo Semestre
Obbligo di frequenza: 
No
Ore di attività frontale: 
24
Ore di studio individuale: 
45
Ambito: 
Attività formative affini o integrative
Prerequisiti

Algebra lineare e funzioni reali di variabile reale.

Obiettivi formativi

Scopo del corso è di fornire una panoramica dei moderni metodi e algoritmi di ottimizzazione per applicazioni all’apprendimento statistico e il data science. Verrà discussa la teoria alla base di questi metodi (ad esempio, condizioni di ottimalità e teoria della dualità) e come scegliere i giusti metodi di ottimizzazione per diverse applicazioni di apprendimento statistico.
Al termine del corso lo studente sarà in grado di:
• Valutare gli algoritmi, le classi di funzioni e velocità di convergenza degli algoritmi più importanti.
• Implementare i più importanti algoritmi di ottimizzazione per il data science in ambiente MATLAB.
• Comprendere il trade-off tra tempo computazionale e precisione di algoritmi per l’apprendimento statistico.
Dal punto di vista empirico, gli algoritmi presentati verranno applicati a database del mondo reale.

Contenuti dell'insegnamento

Nello specifico il corso coprirà i seguenti argomenti:
• Fattorizzazione di sistemi lineari, condizioni di ottimalità, Metodi di Ottimizzazione univariata e multivariata senza l’utilizzo di derivate (Derivative-Free), Metodo del Gradiente, Metodo del Gradiente Stocastico, Metodo del Subgradient, Metodo di Newton e Quasi-Newton, Metodo di Quasi-Newton Stocastico, Metodo del Gradiente Coniugato, Metodi Penalty Function, Metodo al Punto Interno, Cenni all’Algoritmo Genetico.
• Support Vector Machines (SVM): classificatori Soft and hard Maximum Margin e loro formulazione di programmazione quadratica (PQ). Metodo dei kernel. Condizioni di Karush-Kuhn-Tucker (KKT). Formulazione duale del problema PQ primale. Teoria della dualità di Wolfe per PQ. Metodi di decomposizione. Problemi SVM multiclasse: uno contro uno e uno contro tutti.
• Alberi decisionali ottimali.

Uso pratico di algoritmi di apprendimento. Confronto tra algoritmi di apprendimento dal punto di vista dell'ottimizzazione. Utilizzo di software standard (Matlab).

Metodi didattici

Il corso sarà organizzato in lezioni frontali, esercitazioni e tutorato comprensive dello svolgimento di esempi e esercizi. Alcune lezioni si svolgeranno presso il laboratorio informatico in cui verranno implementate in ambiente Matlab le metodologie descritte a lezione su dati provenienti da vari contesti applicativi (business analytics, news, diagnosi medica ecc.).

Modalità verifica profitto e valutazione

L'esame si svolge in due parti: una prova scritta e una prova orale. La prova scritta prevede la risoluzione di esercizi inerenti il programma. L’esame orale è volto a valutare la conoscenza dei temi oggetto del corso. Il voto finale è unico e tiene conto per il 50% della valutazione della prova scritta per il 50% del colloquio orale.

Altre informazioni

Materiale relativo al corso verrà inserito dal docente tramite la piattaforma "e-learning" dell'Università degli studi di Bergamo.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte modifiche rispetto a quanto dichiarato nel syllabus per rendere il corso e gli esami fruibili anche secondo queste modalità.

Per maggiori informazioni scrivere a: francesca.maggioni@unibg.it

Prerequisites

Basic knowledge of Linear Algebra and Calculus.

Educational goals

This course teaches an overview of modern optimization methods and algorithms for applications in statistical learning and data science. In particular, scalability of algorithms to large datasets will be discussed in theory and in implementation. Theory behind these methods (e.g., optimality conditions and duality theory) will be discussed as well as how to choose the right optimization methods for different statistical learning applications.
By the end of the course, the student must be able to:
• Evaluate the most important algorithms, function classes, and algorithm convergence guarantees.
• Formulate scalable and accurate implementations of the most important optimization algorithms for data science.
• Characterize trade-offs between time, data and accuracy, for machine learning methods.
On the practical side, application of the considered algorithms on real-world databases will be investigated.

Course content

Specifically, the course will cover the following topics:
• Factorizations of linear systems, Optimality Conditions, Derivative-free Optimization Methods, Gradient Method, Stochastic Gradient Descent Method, Subgradient Method, Netwon and Quasi-Newton Methods, Stochastic Quasi-Newton Method, Conjugate Gradient Method, Penalty Function Method, Interior Point Method, Genetic Algorithm.
• Supervised Learning
Support Vector Machines (SVM): Soft and hard Maximum Margin Classifiers. Quadratic programming (QP) formulation of the soft/hard maximum margin separators. Kernels methods. Karush-Kuhn-Tucker (KKT) conditions. Dual formulation of the primal QP problem. Wolfe duality theory for QP. Decomposition methods. Multiclass SVM problems: one-against-one and one-against-all.
• Optimal Decision Trees.

Practical use of learning algorithms. Comparing learning algorithms from the optimization point of view. Use of standard software (Matlab).

Teaching methods

The course is structured into lectures in class, in which the context and methodologies are explained, and computer lab sessions (using MATLAB software), in which the students apply the methodologies to real-world data sets coming from various fields (business analytics, news, medical diagnosis etc).

Assessment and Evaluation

The final exam is based on a written test followed by an oral interview. The written test is composed of exercises. The oral exam is aimed at assessing the knowledge of the theory covered by the course. The final mark takes into account both the parts of the exam (50% of the written and 50% of the oral).

Further information

The course material will be provided by means of the e-learning platform of the University of Bergamo.
If the teaching activity will be mixed or in remote mode, changes can be done compared to what stated in the syllabus, to make the course and the exams available also in these modalities.

For more details write to: francesca.maggioni@unibg.it