145005 — Algoritmi Avanzati
145609 — Machine Learning for Data Science

Laurea Triennale in Informatica
Anno Accademico 2016-2017, secondo semestre

Avvisi

  • [2017-03-04]
    Sono disponibili le date (non definitive) degli appelli della sessione estiva.
  • [2017-02-08]
    Sono disponibili il testo del secondo appello di martedì 7 febbraio e una traccia della soluzione.

Obiettivi del corso

La figura del “Data Scientist”, sempre più richiesta dalle aziende e dai centri di ricerca, si occupa di dare un senso alla mole crescente di dati disponibili in ogni contesto, ne costruisce modelli informatici che aiutano a comprendere meglio un fenomeno noto o a scoprirne di nuovi; individua inoltre le modalità di presentazione più efficaci e guida il miglioramento dei processi che analizza.

Il corso costituisce un'introduzione teorico-pratica alle tecniche di apprendimento automatico (machine learning) che, a partire da esempi, generano modelli matematici che possono essere generalizzati a nuovi casi per operare previsioni.

Il corso può essere seguito come modulo a sé, ma può essere utilmente completato da "Intelligent Optimization for Data Science".

Programma

  • Machine Learning: costruzione di modelli a partire dai dati
  • Apprendimento supervisionato
  • Apprendimento non supervisionato
  • Selezione delle feature
  • Tecniche di visualizzazione dei dati
Le lezioni di laboratorio prevedono la verifica e la sperimentazione degli argomenti trattati a teoria tramite la scrittura di brevi programmi di prova sotto la guida del docente.

Prerequisiti

Il corso richiede nozioni di base di Programmazione, Analisi Matematica, Algebra Lineare, Statistica.

Esami

L'esame consiste in una prova scritta.

La prova scritta, con carta e penna, non richiederà la scrittura di codice. Conterrà uno o due esercizi affini agli esempi contenuti nella traccia degli argomenti del corso, e alcune domande di teoria.

I prossimi appelli d'esame avranno luogo durante la sessione estiva. Le date (provvisorie) sono le seguenti:

Prova scritta
Primo appello:Martedì 13 giugno, ore 9:00
Secondo appello:Martedì 25 luglio, ore 9:00
Terzo appello:Mercoledì 6 settembre, ore 9:00

Prove parziali

La prima prova parziale ha avuto luogo mercoledì 2 novembre alle 9.

La seconda prova parziale, accessibile a chi ha superato la prima, ha avuto luogo venerdì 23 dicembre alle 14. Un recupero è stato possibile durante il primo appello di gennaio.

Docenti

Orario

Le lezioni sono terminate.

Bibliografia

Per approfondimenti si consigliano le seguenti risorse.

Libri

  • Roberto Battiti and Mauro Brunato
    The LION Way — Machine Learning plus Intelligent Optimization
    LIONlab, 2014.
    ISBN: 978-1-49603-402-1

Pagine e siti web

Materiale del corso

Dispense del corso ed esercizi

  • Annotazioni sugli argomenti svolti a teoria, domande di autovalutazione ed esercizi
    [versione 2016-12-22]

Esercitazioni di laboratorio

  • Prima esercitazione: lettura di file CSV e semplici statistiche.
  • Seconda esercitazione: ricerca del valore migliore per il parametro K nell'algoritmo KNN.
  • Terza esercitazione: regressione polinomiale con polinomi di vari gradi.
  • Quarta esercitazione: estensione di KNN a problemi di regressione con variabili di ingresso categoriche; K-fold cross validation.
  • Quinta esercitazione: regressione lineare (e polinomiale), metodo dei minimi quadrati.
    • Script completo della quinta esercitazione: [lsq.py]
  • Sesta esercitazione: regressione logistica e determinazione dei coefficienti tramite discesa lungo il gradiente.
  • Settima esercitazione: prestazioni di un modello logistico
  • Ottava esercitazione: alberi di decisione
  • Nona esercitazione: selezione di feature
  • Decima esercitazione: clustering
  • Undicesima esercitazione: soluzione dell'esercizio 9 della dispensa

Prove d'esame


Programma svolto

Teoria

Se non specificato altrimenti, i riferimenti sono alla versione 2 del libro “The LION Way”. Le dispense contengono invece i riferimenti agli articoli più rilevanti di Wikipedia.

  • Presentazione del corso (mercoledì 14 settembre)
    • Descrizione dei contenuti del corso.
    • Modalità d'esame.
  • Introduzione alla Data Science (mercoledì 14 settembre, lunedì 19 settembre)
    • Discipline che ne fanno parte
    • Modelli di dati da utilizzare (strutturati, semi-strutturati)
    • Formalizzazione del problema dell'apprendimento automatico: problemi di regressione e di classificazione; features; modelli.
    • Training e validation set
    • Esempio di algoritmo di machine learning: K Nearest Neighbors (KNN).
    Riferimenti: cap. 1, 2.
  • Valutazione di un modello (lunedì 26 settembre, lunedì 3 ottobre)
    • Problemi di regressione: errore quadratico medio (root mean square error)
    • Problemi di classificazione: matrice di confusione, accuratezza, precisione, sensibilità, F1-score, coefficiente di correlazione di Matthews (MCC).
    • Trasformazione di feature categoriche in feature continue.
    • Utilizzo di algoritmi di classificazione su problemi di regressione e viceversa.
    • Metodologie di valutazione: leave-one-out, K-fold cross-validation.
    Riferimenti: cap. 2, 3.
  • Regressione lineare (lunedì 10 ottobre)
    • La regressione ai minimi quadrati: caso scalare, estensione al caso a più dimensioni.
    • Estensione alla combinazione lineare di funzioni di base arbitrarie.
    Riferimenti: cap. 4.
  • Regressione logistica (lunedì 17 ottobre)
    • La funzione sigmoide, suo uso per limitare l'uscita all'intervallo [0,1].
    • Uso dei minimi quadrati: calcolo del gradiente dei minimi quadrati del regressore logit.
    • Minimizzazione tramite discesa lungo il gradiente.
    Riferimenti: cap. 4.
  • Alberi di decisione (lunedì 7 novembre, lunedì 14 novembre)
    • Misure di impurità di una variabile casuale: entropia, impurità di Gini
    • Suddivisione di un dataset, entropia attesa
    • Costruzione ricorsiva di un albero di decisione, condizioni di terminazione
    • Discesa lungo un albero di decisione
    Riferimenti: cap. 5.
  • Selezione delle feature (lunedì 21 novembre, lunedì 28 novembre, mercoledì 30 novembre, lunedì 5 dicembre)
    • Coefficiente di correlazione di Pearson fra variabili casuali continue
    • Entropia condizionale e informazione mutua per variabili casuali a dominio finito
    • Quantizzazione di variabili continue
    • Uso dell'informazione mutua per una selezione “greedy” delle feature
    • Controesempi
  • Apprendimento non supervisionato (clustering) (lunedì 5 dicembre, lunedì 12 dicembre)
    • Motivazione
    • Misure di distanza e similarità: distanza euclidea, cosine similarity, coefficiente di Jaccard
    • Clustering agglomerativo gerarchico
    • Linkage criteria: single, complete, average
 

Laboratorio

  • Caricamento e analisi di un file (mercoledì 14 settembre)
    • Utilizzo dell'interprete Python
    • Caricamento di un file CSV con il modulo pandas
    • Selezioni e conteggi
    • Script per il calcolo di una semplice statistica
    Riferimento: dispensa, prima esercitazione.
  • Valutazione di un modello KNN e ricerca del parametro ottimale (mercoledì 21 settembre)
    • Caricamento di un file CSV con Python
    • Implementazione semplice dell'algoritmo KNN
    • Ripartizione del dataset in training e validation set
    • Validazione di KNN per diversi valori di K
    Riferimento: dispensa, seconda esercitazione.
  • Generazione di un dataset rumoroso e uso di un modello di regressione polinomiale (mercoledì 28 settembre)
    • Generazione di un dataset e aggiunta di errori normali
    • Uso di una funzione di libreria per la regressione polinomiale
    • Verifica del comportamento del polinomio per diversi gradi
    • Validazione del modello con gradi diversi
    Riferimento: dispensa, terza esercitazione.
  • Estensione di KNN a input categorici e output reali (mercoledì 5 ottobre)
    • Rappresentazione unaria delle colonne categoriche.
    • UTilizzo del valore medio degli output dei vicini come valore di previsione.
    Riferimento: dispensa, quarta esercitazione.
  • K-fold cross-validation (mercoledì 5 ottobre)
    • Utilizzo della libreria sklearn per generare i fold.
    • Utilizzo del regressore KNN fornito dalla libreria sklearn.
    Riferimento: dispensa, quarta esercitazione.
  • Regressione lineare e polinomiale; minimi quadrati (mercoledì 12 ottobre)
    • Uso di numpy per implementare lo stimatore ai minimi quadrati dei parametri del modello lineare.
    • Estensione al caso polinomiale tramite matrice delle potenze.
    Riferimento: dispensa, quinta esercitazione.
  • Regressione logit, discesa lungo il gradiente (mercoledì 19 ottobre)
    • Uso di numpy per implementare il modello logit e il calcolo del gradiente della somma dei quadrati degli scarti.
    • Implementazione della discesa lungo il gradiente.
    Riferimento: dispensa, sesta esercitazione.
  • Regressione logit: analisi delle prestazioni (mercoledì 26 ottobre)
    • Modifica dello script della precedente esercitazione: definizione di una funzione di decisione dipendente da un parametro, determinazione degli indici di prestazione al variare della soglia.
    • Grafici delle prestazioni.
    Riferimento: dispensa, settima esercitazione.
  • Alberi di decisione (mercoledì 9 novembre, mercoledì 16 novembre, mercoledì 23 novembre)
    • Realizzazione di uno script per la costruzione e la navigazione di un albero di decisione basato sulla minimizzazione dell'entropia attesa
    • Utilizzo della libreria scikit-learn per l'addestramento e l'uso di un albero di decisione
    • Utilizzo di scikit-learn per l'addestramento e l'uso di una random forest
  • Selezione delle feature (mercoledì 30 novembre, mercoledì 7 dicembre)
    • Quantizzazione di feature continue
    • Stima dell'informazione mutua sulla base delle osservazioni
    • Realizzazione di un algoritmo greedy per la selezione iterativa delle feature
  • Clustering (mercoledì 14 dicembre)
    • Applicazione dell'algoritmo agglomerativo gerarchico su un dataset
    • Matrice delle distanze, rappresentazione tramite heatmap
    • Uso del dendrogramma per permutare i dati e riordinare la heatmap

Pagina mantenuta da Mauro Brunato