Docente: Dario Fasino.

Quando e dove: Il corso verrà svolto nel periodo didattico 24/09 -- 30/11/2007 con il seguente orario settimanale:

• martedì ore 08:30--10:15 aula 46,
• mercoledì ore 10:30--12:15 aula 46,
• giovedì ore 10:30--12:15 aula 48.

Di che si tratta: Insegnamento obbligatorio per studenti iscritti alla Laurea Specialistica in Tecnologie dell'Informazione (6 CFU).

Finalità: Il corso esporrà le basi teoriche e implementative di alcune tecniche matematiche per il trattamento di problemi relativi al recupero di documenti sul web, alla loro classificazione e ordinamento, quali il Latent Semantic Indexing, l'algoritmo PageRank, i metodi per il data clustering. Il corso prevede la trattazione di vari esempi, casi di studio e lo svolgimento di attività sperimentali in laboratorio. Dopo aver superato l'esame, si ritiene che lo studente conosca e sappia utilizzare tecniche dell'algebra lineare numerica nell'ambito dell'Information Retrieval e del Data Mining.

Programma provvisorio: Richiami di algebra lineare: spazi vettoriali Rⁿ, matrici, norme vettoriali e matriciali, prodotti scalari, fattorizzazioni notevoli di matrici. Decomposizione ai valori singolari. Problemi ai minimi quadrati lineari. Regolarizzazione di Tikhonov. Elaborazione numerica delle immagini: Il modello lineare dello sfocamento delle immagini; Point Spread Function; ricostruzione di immagini sfocate e affette da rumore; compressione di immagini. Modelli matematici per l'Information Retrieval: Matrice termini-documenti e modello dello spazio vettoriale. Strategia del Latent Semantic Indexing (LSI). Tecniche numeriche per il clustering e la classificazione automatica dei documenti: ordinamento di documenti in un ipertesto in base all'analisi dei link; l'algoritmo di Kleinberg; hub e authorities. Il modello probabilistico di navigazione in un ipertesto; catene di Markov; la Google matrix e il vettore PageRank; metodi per il calcolo di densità stazionarie e loro utilizzo negli algoritmi di page ranking.

Modalità d'esame: Due prove di valutazione intermedia, un progettino in Matlab, una eventuale prova orale. Primi appelli utili: 11/12/2007 ore 9:30 aula 48, 08/01/2008 ore 9:30 aula 48.

Riferimenti bibliografici:

• M. W. Berry, M. Browne. Understanding Search Engines: Mathematical Models and Text Retrieval. SIAM, 1999. [025.4 BER]
• A. N. Langville, C. D. Meyer: Google's PageRank and beyond. Princeton Univ. Press, 2006. [025.04 LAN]
• Materiale didattico a cura del docente.

• 25--27 settembre 2007: Presentazione del corso. Richiami di Algebra Lineare: Spazi e sottospazi vettoriali, indipendenza lineare, basi, applicazioni lineari. Nucleo, immagine, rango, nullità di una applicazione lineare. Matrici. Prodotto matrice-vettore. Composizione di applicazioni lineri e prodotto matriciale. Matrici invertibili. Inversa e trasposta del prodotto di due matrici. Costo computazionale delle operazioni principali dell'algebra lineare.
   
• 2--4 ottobre 2006: Prodotto scalare in Rⁿ. Norma euclidea. Angolo tra due vettori. Norma euclidea di una matrice. Esempi. Angolo tra vettori in Rⁿ. Vettori ortogonali e ortonormali. Matrici ortogonali: definizione e proprietà algebriche e geometriche; esempi. Decomposizione ai valori singolari (SVD): introduzione.
   
• 9--11 ottobre 2006: Decomposizione ai valori singolari (SVD): interpretazione geometrica e proprietà principali. Teorema di Eckart-Young. Matrici di rango uno; approssimazione di rango basso. Compressione di immagini via SVD troncata. Esempi in Matlab. Latent Semantic Indexing: Introduzione. Matrice termini-documenti, vettore query, sinonimia e polisemia.
   
• 16--19 ottobre 2006: Latent Semantic Indexing: spazi vettoriali per la descrizione di termini e documenti; uso della SVD troncata; lo spazio LSI; misure di similarita' tra query e documenti, nello spazio dei termini e nello spazio LSI; effetti di classificazione e clustering dei documenti mediante LSI. Folding-in di termini e documenti. Esempi. Introduzione a Matlab: variabili, linguaggio, interprete, M-file, funzioni matematiche e grafiche.
   
• 23--25 ottobre 2007: Rifocamento di immagini sfocate e affette da rumore. Point Spread Function. Condizioni al contorno (nulle, periodiche, riflettenti). Analisi degli errori inerenti nella risoluzione dei sistemi lineari (ben determinati) mediante SVD. Numero di condizionamento di una matrice.
   
• 30--31 ottobre, 6 novembre 2007: Sistemi lineari: risoluzione mediante la SVD. Algoritmi di sostituzione (in avanti, all'indietro). Richiami sull'algoritmo di Gauss (con pivot parziale). Regolarizzazione di Tikhonov: funzionamento, analisi mediante SVD. Esempi in Matlab. Esercitazioni.
   
• 7 novembre 2007: Prima prova di valutazione intermedia.
   
• 13--15 novembre 2007: Il criterio della curva-L per la scelta del parametro di regolarizzazione. Esempi in Matlab. Problemi ai minimi quadrati: forma del problema, risoluzione mediante equazioni normali, SVD, fattorizzazione QR. Applicazioni ed esempi: Regressione lineare. Autovalori e autovettori; fattorizzazione spettrale di matrici diagonalizzabili. Matrici semidefinite positive.
   
• 20--22 novembre 2007: Il metodo delle potenze: definizione e proprietà principali. Metodi numerici per il Web Information Retrieval: L'algoritmo di Kleinberg (HITS); hub e authority di documenti in un ipertesto; esempi. Catene di Markov; matrici stocastiche, matrici di transizione, matrici (e catene) riducibili, irriducibili, regolari. Esempi.
   
• 27--29 novembre 2007: Metodi Numerici per l'Information Retrieval: PageRank, SALSA. Esercitazioni sulla seconda parte del corso.
   
• 11 dicembre 2007: Seconda prova di valutazione intermedia.
   

Il materiale didattico di questo corso (slides delle lezioni, riferimenti bibliografici, dispense) è disponibile sul sito materialedidattico.uniud.it