Quadro tentativo delle lezioni, aggiornato via via CT: Cover e Thomas: Elements of Information Theory CT2: Cover e Thomas: Elements of Information Theory - II Edizione (2006) SC: Sequenze-complementi.pdf (Caglioti, in queste pagine) S: Sequenzetesto.pdf (Caglioti, in queste pagine) G: Gnedenko - Teoria della Probabilita' (in Biblioteca ce ne sono due copie in inglese) SH: Shirayaev: Probability (due copie in biblioteca) K: Ioannis Kontoyiannis: Asymptotic Recurrence and Waiting Times for Stationary Processes, Journal of Theoretical Probability July 1998, Volume 11, Issue 3, pp 795-811; (scaricabile da Sapienza, su MathSciNet MR1633403) B: Chiara Basile, tesi di dottorato http://amsdottorato.unibo.it/3224/ BBCD: Basile, Benedetto, Caglioti, Degli Esposti: "An example of mathematical authorship attribution" Jour. Math. Phys. 49, 12511 (2008) DOI: 10.1063/1.2996507 (scaricabile da Sapienza) UR: Introduzione ai calcolatori e a R, su http://brazil.mat.uniroma1.it/dario/ASD/calcol.pdf BSA: Durbin, Eddy, Krogh, Mitchinson: "Biological sequence analysis", Cambridge University Press (c'e' una sola copia sapienza e ce l'ho io) OTTOBRE 1 Presentazione del corso; materiale (divulgativo) su http://brazil.mat.uniroma1.it/dario/PLS/PLS-BIT/ 3 entropia per una variabile aleatoria; entropia per una coppia di variabili; distribuzioni congiunte e indipendenza di variabili; entropia condizionata; entropia relativa; disuguaglianza di Jensen. CT capitolo 2 8 mutua informazione e suo significato. Disuguaglianze: H(X) \le log n (con uguale se e solo se X e' uniforme) H(Y|X) \le H(X) (con = se e solo se X e Y indipendenti) H(X;Y) \le H(X) + H(Y) (con = se e solo se X e Y indipendenti) Regola della catena per n variabili, e stima dell'entropia congiunta con la somma di entropie (CT capitolo 2). Esempi e esercizi (2.2 2.5 2.23 su CT) 9 Esercizi 2.14 2.28, 2.30-2.1 su CT altre disuguaglianze: somma log, convessita' di D(p||q), concavita' di H(p). Introduzione all'AEP per variabili aleatorie indipendenti, 15 AEP per variabili iip, conseguenze sulla compressione Introduzione ai processi di markov (a un passo). Definizione. Vari esempi di catene e relazioni con i cammini sui grafi. Misure invarianti, casi con unicita' e casi senza unicita'; un esempio di catena periodica. 16 Convergenza all'equilibrio per catene di Markov con matrici di transizione positive: 1. decrescita dell'entropia relativa, 2. esistenza dell'equilibrio per compatezza 3. unicita' dell'equilibrio (vedi SC pagine 1,2,3 pero' Caglioti fa la decrescita a mano, mentre io ho usato la disuguaglianza somma-log che abbiamo fatto sul CT) Convergenza delle matrici di transizione a k passi (vedi G, pararafago 19 capitolo III nell'edizione italiana, o anche S, paragrafo 1.12) 22 Definizione di tasso di entropia per processi stazionari. Monotonia delle entropie condizionate a n passi. Esempio di mistura di processi: un caso di non equipartizione. Legge dei grandi numeri per processi di Markov ergodici (vedi S paragrafo 1.12), teorema di equipartizione per processi di Markov ergodici (appunti lezione). Sistemi dinamici discreti e processi stazionari: definizione, esempio della rotazione rigida della circonverenza, esempio della mappa da [0,1] in se con lo shift a sinistra. Teo: se la misura e' invariante allora il processo associato e' stazionario. [vedi SH capitolo V]. 23 Teorema: a ogni processo stazionario si puo' associare un sistema dinamico discreto con una misura invariante. Esempio: la misura bernoulli 1/3 2/3. Osservazione sul supporto della misura rispetto al supporto della misura di Lebesgue, attraverso Borel-Cantelli. Definizione di sistema ergodico, definizioni equivalenti; conseguenze sui processi (vedi S capitol V). Sample a frequenze definite, cenni alla decomposizione ergodica. Esempio della mappa dell'intervallo che da' Bernoulli 1/3 2/3 con la misura di Lebesgue invariante. 29 Codici, codici non singolari, codici univocamente decodificabili, codici prefissi. Disuguaglianza di Kraft. Stime della lunghezza media del codice per codici ottimali (CT) 30 Codifica di Huffman, ottimalita' per la codifica di Huffman (CT) NOVEMBRE 5 LZ77, dettagli implementativi per gzip (vedi https://www.ietf.org/rfc/rfc1951.txt) 6 saltata per allarme meteo 12 prove in itinere 13 prove in itinere 19 Lemma di Kac, idee sull'ottimalita' di LZ77 (CT) 20 Approssimazioni markoviane di processi. L'entropia relativa tra due sorgenti. Il teorema di Shannon McMillan Breiman nel caso di due distribuzioni. Match tra due sorgenti differenti; risultati asintotici. (vedi K, solo enunicati, o anche B, capitolo 1). 26 Stima dell'entropia relativa mediante LZ77 (B, capitolo 1). Uso delle stime di entropia per l'authorship attibution (AA). Attribuzione al primo vicino. Il problema delle classifiche. 27 Costruzione degli indici di autorialita' in base alle classifiche per i problemi a due autori. Il metodo degli n-grammi di Keselj. (su BBCD) Qualche osservazione sui test diagnostici e i test di autorialita'. (su qualunque testo di prob. elementare, a proposito della formula di Bayes). DICEMBRE 3 Alberi filogenetici. I tipi di dati: frequenze geniche (cenni all'equilibrio di Hardy-Weinberg e alla deriva genetica). Alberi ultrametrici, algoritmo UPGMA (S e SC) 4 salta per concomitante impegno dottorale del docente 10 Alberi additivi; condizione dei quattro punti. L'algoritmo Neighbor Joining e la ricostruzione degli alberi (su S par 7.3 e su SC par 2) 11 Esercitazione in lab. 17 Riduzione della dimensionalita' dei dati: il metodo delle componenti principali. Elementi di *nix (vedi UR) il filesystem, la shell, i comandi; il programm R 18 Esercitazione in lab. GENNAIO 7 HMM: algoritmo di Viterbi (su S, par 5.2 e su BSA, par 3.2) 8 Esercitazione in lab. 14 HMM: algoritmi Forward e Backward, Baum-Welch e Viterbi training (su BSA, par 3.2-3.3) 15 Esercitazione in lab.