(seconda figura da: Navarra Simoncini, Springer 2010)

Matematica Computazionale:
Matrix methods for Data Science

a.a. 2022-2023. Corso opzionale della Laurea in Matematica (triennale) - Bologna
NOTA: Il corso e' fruibile anche dagli studenti delle Lauree Magistrali.

6 crediti
Lezioni: II semestre
Docente: Prof. V. Simoncini

Orari del Corso (inizio lezioni: 20/02/2023 )

Lun 14:00-16:00, Giovedi 14:00-16:00

Eventuali variazioni di orario saranno segnalate in fondo alla pagina.

Orario di Ricevimento Studenti

su appuntamento.

Programma

Il corso prevede lo studio di: Matrix methods for Data Science. L'informazione contenuta in grandi quantita' di dati, usufruita per esempio dai motori di ricerca (es. Google), od usata nello studio di dati climatici, pattern e image recognition, ecc., e' spesso gestibile grazie all'uso di tecniche matriciali e tensoriali avanzate di alto livello, che sfruttino, per esempio, fattorizzazione opportune nell'ambito di problemi di ottimizzazione matriciali. Il corso prevede di studiare queste tecniche, partendo dagli aspetti analitici di Teoria delle Matrici, e arrivando al loro utilizzo pratico in vari problemi benchmark nel Data Science.

Dettaglio

- Organizzazione dei dati e note introduttive
- Calcolo Matriciale: Autovalori e proprieta' variazionali
- Calcolo Matriciale: Valori singolari e loro proprieta'
- Calcolo tensoriale e HOSVD
- Applicazioni:
** Information retrieval in documenti mediante i problemi ai minimi quadrati
** Image classification con la fattorizzazione matriciale non negativa (NMF)
** Similarita', metodi di Clustering (Complete Linkage, kmeans, spectral clustering)
** Strategie matriciali per il Riconoscimento di Pattern/immagini
** Analisi delle Componenti Principali su osservazioni multivariate
** Strategie spettrali per il Page ranking
** Metodi matriciali per i complex networks
Applicazioni: (Handwritten digits, Text mining, Page Ranking)

Dettaglio: Registro delle lezioni completo del corso, a.a.2020-2021.

Il corso prevede 55 ore. L'attivita' didattica alternera' lezioni frontali (con lucidi) con applicazioni immediate al computer in ambiente Matlab con supervisione del docente, in cui gli studenti saranno incoraggiati ad implementare quanto appena visto a lezione.

Prerequisiti:

Concetti fondamentali di Analisi Matematica.
Algebra Lineare di base (spazi vettoriali, matrici, vettori, norma, ...) ed aspetti computazionali (QR, Choleski, LU, Autovalori, ...)
Conoscenze di base dell'ambiente computazionale Matlab.


Testi di Consultazione:


* Lucidi del corso (disponibili man mano che il corso procede). Sono possibili variazioni del materiale, quindi e' sconsigliata la stampa in anticipo rispetto alla lezione a cui si riferisce.
* Lezioni su Tensori per le lezioni sull'argomento, parte integrante del corso.

* R. Horn e C. Johnson, Matrix Analysis , Cambridge Univ. Press, 1985.
* Lars Elden, Matrix Methods in Data Mining and Pattern Recognition , SIAM, 2^ edizione, 2019.
*R. Johnson e D. Wichern, Applied Multivariate Statistical Analysis, Prentice-Hall, (V ed.) 2002. Dati relativi alle tabelle del libro.
* E. Estrada, The Structure of Complex Networks, Theory and Applications, Oxford Univ. Press, 2011.
* M.W. Berry and M. Browne, Understanding Search Engines: Mathematical Modeling and Text Retrieval , SIAM Book Series: Software, Environments, and Tools, Second Edition (Maggio 2005).
* Extrapolation Methods for Accelerating PageRank Computations Sep Kamvar, Taher Haveliwala, Chris Manning, and Gene Golub. Proceedings of the Twelfth International World Wide Web Conference, May, 2003.
* Algorithms for Non-negative Matrix Factorization Daniel D. Lee and H. Sebastian Seung, Advances in Neural Information Processing Systems 13, (2001), 556-562.
* Non-negative Matrix Factorization Nicolas Gillis, SIAM, 2020. Matlab software .
*Jingu Kim. Matlab software per non-negative matrix and tensor factorization
* Non-negative Matrix and Tensor Factorization. Applications to exploratory multi-way... A. Cichocki, R. Zdunek, A.~H. Phan and S.-i. Amari, Wiley, 2009.
* Algorithms, Initializations, and Convergence for the Nonnegative Matrix Factorization Russell Albright, James Cox, David Duling, Amy N. Langville, and Carl D. Meyer, NCSU Technical Report Math 81706.
* A tutorial on spectral clustering Ulrike von Luxburg, Statistics and COmputing, 17 (4), 2007.
* Spectral and Algebraic Graph Theory Incomplete Draft, dated December 4, 2019, Daniel A. Spielman, Yale University.
* Definizioni di funzione di matrice Nick Higham, estratto da "Functions of matrices, theory and computation", SIAM 2008.
* Network properties revealed through matrix functions Ernesto Estrada and Desmond J. Higham, SIAM Review, 52 (4), 2010.
* LSI Latent Semantic Indexing, sito di riferimento (non aggiornato di recente) Dataset per Inf Retr: Corpora/Glasgow Repository
* Tensor Decompositions and Applications T. Kolda and B. Bader, SIAM Review, 51 (3), 2009.
* Capitolo sui Tensori, in "Matrix Computations", G. Golub and Ch. Van Loan, 4 Ed, (2013) Johns Hopkins Univ.Press.
* SVD and applications Z. Zhang, arXiv n.1510.08532v1 (2015).
* Efficiency seminario del prof. L. De Angelis, UniBO, del 12 Aprile 2023.
altri testi....

* Funzioni per lezione su tensori. hosvd3.m , nmodeproduct.m , store_data.m , Dati: coil20.tar.gz, faces96.zip. Funzioni: svdtrunc_coil20.m , svdtrunc_faces96.m , svdtrunc_mnist.m
Toolbox: tensor toolbox v.3.2.1 release v3.2.1, tensor toolbox v3.5 release attuale , tensor_toolbox-v3.5.tar --> vedi: Toolbox homepage, e la sezione "Functionality" per la documentazione.


Laboratorio Informatico:


Esercizi del 27/02/23 Dati: zmi-geonode.png, query.png
Esercizi del 13/03/23. Dati: A_med.mat . Q_med.mat . dict_med.mat . Codice: lsqr.m
Esercizi del 23/03/23. Dati: protein.m.
Esercizi del 30/03/23. Dati: Esercizio 1: digits mnist_all.mat. Codici: ima2.m. Esercizio 2: faces96.zip, faces95.zip. codice testFace_U.m.
Esercizi del 17/04/23. Funzione matlab per Splitting in training/test sets split_dataset.m. FaceRec_HOSVD3.m. Dati: orl_faces.tar.gz, yalefaces.tar.gz FaceBase_png.zip (file molto grosso)
Esercizi del 27/04/23. Dati: stanford-berkeley-web.tar.gz. non zippato: stanford-berkeley-web.tar.
Esercizi del 28/04/23. Dati: protein.m. clustering.m.
Esercizi del 05/05/23. Codice per le k-medie: test1_kmeans.m. Dati: sample_orl.tar. get_matrices.m.
Esercizi del 15/05/23.
Esercizio del 22/05/2023. Dati citta' distanzecitta.txt ( con nomi )
Esercizi del 25/05/25.

Prova d'esame:

L'esame consiste in una prova orale che prevede due parti: i) Risposte a domande sugli argomenti svolti a lezione; ii) Presentazione orale di un progetto su argomenti svolti nel corso e nel laboratorio informatico. (E' a disposizione un file (gzipped tar) con un esempio di semplice presentazione. Altri files utili: sem-page.sty. seminar.cls. Altrimenti si puo' usare il pacchetto beamer di latex.)

Problemi per l'esame :

testo.

Link utili:

  • Arithmetic Formats for Machine Learning - Working group

    Informazioni utili:




    (Yale Face Dataset, http://vision.ucsd.edu/datasetsAll)