Processi stocastici


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

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 28 Febbraio 2012.

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: 24 Febbraio 2012