Processi stocastici


Insegnamento per il corso di laurea magistrale di Informatica
Università degli Studi di Milano -- Anno accademico 2010/2011

Docente: M. Goldwurm



1. Presentazione del corso
2. Programma
3. Testi di riferimento
4. Dispense introduttive
5. Orari di lezione e ricevimento
6. Modalità d'esame

PRESENTAZIONE DEL CORSO

Questo corso è principalmente dedicato alle catene di Markov e alle loro applicazioni algoritmiche. Ricordiamo che le catene di Markov sono utilizzate nella progettazione e nell’analisi di numerosi algoritmi di ottimizzazione e conteggio per svariati problemi. Esempi classici sono quelli dell’annealing simulato e dei metodi di apprendimento con rinforzo, ma numerose sono le applicazioni recenti che riguardano algoritmi di approssimazione per problemi difficili. Inoltre, i modelli stocastici di tipo Markoviano, ottenuti come varianti o estensioni delle catene di Markov, sono utilizzati in numerose aree di ricerca, per esempio in biologia computazionale e in particolare nelle analisi statistiche di sequenze di DNA, nello sviluppo di strumenti per il riconoscimento di segnali vocali (Hidden Markov Models) e nella progettazione di algoritmi di esplorazione della rete web (Pagerank).
L’obiettivo del corso è quello di introdurre i risultati principali riguardanti le catene di Markov e di presentare alcune applicazioni algoritmiche. Il corso è di sei crediti e si divide in due parti principali. La prima è dedicata alle catene di Markov finite e alle loro proprietà ergodiche. La seconda parte riguarda invece applicazioni specifiche, principalmente dedicate agli algoritmi Monte Carlo basati su passeggiate a caso in catene di Markov ergodiche.

PROGRAMMA

Generalità sui processi stocastici discreti e continui.
Matrici non negative. Matrici irriducibili e primitive. La nozione di periodo nelle matrici irriducibili. Il teorema di Perron-Frobenius. La decomposizione triangolare a blocchi. Matrici e vettori stocastici. Catene di Markov finite e omogenee. Classificazione degli stati. Classi ricorrenti e transienti. Catene di Markov irriducibili e aperiodiche. Tempi di prima entrata in uno stato. Distribuzione stazionaria. Proprietà di convergenza alla distribuzione stazionaria (ergodicità). Catene di Markov reversibili. Esempi di passeggiate a caso su grafi.
Generazione casuale non uniforme. Procedure di simulazione di catene di Markov. Metodi Monte Carlo basati su catene di Markov. Campionatori di Gibbs: generazione casuale di insiemi indipendenti o di colorazioni di un grafo. L’algoritmo di Metropolis. Analisi della velocità di convergenza alla distribuzione stazionaria: il caso generale e l’esempio della generazione casuale di colorazioni di grafi. Algoritmi di conteggio approssimato mediante catene di Markov: calcolo del numero di colorazioni di un grafo. Metodi di ottimizzazione e annealing simulato.

TESTI DI RIFERIMENTO

DISPENSE

Sono disponibili due dispense a cura del docente, la prima dedicata alle catene di Markov finite, corredata da richiami di Calcolo delle Probabilità e di Algebra Lineare, mentre la seconda riguarda alcune applicazioni algoritmiche.

MODALITÀ D'ESAME

L'esame consiste in una prova orale sugli argomenti fondamentali presentati a lezione. Per sostenere l'esame non è necessario iscriversi a terminale, si può concordare direttamente con il docente la data della prova (anche via e-mail).

LEZIONI

Il corso si svolge nel secondo semestre.

Inizio delle lezioni il 8 Marzo 2011.

Le lezioni si terranno in auletta 4, presso il D.S.I., via Comelico 39.


ORARIO DI RICEVIMENTO

Prof. Massimiliano Goldwurm, stanza P106 (primo piano), martedì ore 11-13, oppure su appuntamento (accordi per e-mail).

Ultimo aggiornamento: 30 Marzo 2011