Стохастическое Mоделирование. Теория Случайных Процессов. Stochastic Modeling.

Осень 2012 / Fall 2012

Тематический План Курса / Course outline

1. Понятие случайного процесса / Random process
2. Марковские процессы с дискретным времeнем / Descrete time Markov process
3. Марковские процессы с непрерывным времeнем / Continuous time Markov process
4. Скрытые Марковские модели (HMM) / Hidden Markov models
5. Методы Монте Карло (MC) / Monte Carlo methods
6. Байсовские сети / Bayesian networks

Модуль 1 / Module 1

Лекции / Lectures

1. [06.09.2012] Цепи Маркова / Markov chains
   Стохастические процессы. Марковские процессы. Цепи Маркова с дискретным временем. Переходная матрица. Конечномерные распределения и матрица перехода за n шагов. Уравнение Колмогорова-Чепмена.
2. [27.09.2012] Классификация состояний цепи Маркова / Classification of states in Markov chains
   Классифиакция состояний. Достижимые и сообщающиеся состояния. Классы эквивалентности. Неразложимые классы. Неразложимая цепь Маркова. Транзитивные и рекуррентные (возвратные) состояния. Критерий возвратности. Понятие периода состояния. Периодичские состояния. Понятие времени возвращения. Вычисление среднего времени возвращения.
3. [02.10.2012] Стационарное распределение в Марковских цепях / Stationary distribution in Markov chains
   Эргодические состояние и эргодическая Марковская цепь. Стационарное состояние. Основная теорема Марковских цепей. Уравнения стационарного состояния
4. [09.10.2012] Поглощающая Марковская цепь / Absorbing Markov chains
   Каноническая форма матрицы. Вероятность поглощения. Время до поглощения.
5. [16.10.2012] Цепи Маркова с непрерывным временем / Continuous time Markov process
   Понятие процесса с непрерывным временем. Интенсивность переходов. Матрица интенсивности. Уравнение Чепмена Колмогорова
6. [24.10.2012] Зачет / Exam
   

Домашние задания / Home Assignments

1. [6.09.2012] Моделирование дискретного Марковского процесса.На вход матрица переходов P и число шагов процесса. На выходе последовательность случайных состояний Марковского процесса.Провести несколько экспериментов.
2. [27.09.2012] Написать функцию для расчета математического ожидания времени первого посещения состояния. На вход матрица переходов P. На выходе матрица из средних времен M. Провести эксперименты, сравнить ресультаты численного решения с результатами моделирования процесса. В результате моделирование получается распределение времен посещения каждого состояния. Нарисовать гистограммы для некоторых значений М, вычислить и сравнить средние значения полученные при моделировании процесса с результатами численного решения.
3. [02.10.2012] Написать функцию для численного расчета стационарных состояний неразложимой конечномерной марковской цепи. Вычисления производить двумя способами: а) решением линейных уравнений 2) через собственный вектор. На вход матрица переходов P. На выходе векор стационарных состояний. Провести эксперименты, сравнить ресультаты численного решения с результатами моделирования процесса. В результате моделирование получается распределение частот посещения каждого состояния. Нарисовать гистограммы и сравнить средние значения с результатами численного решения.
4. [09.10.2012] Написатъ функцию для расчета вероятностей поглощения в абсорбирующих состояниях конечной поглощающей марковской цепи. На вход матрица переходов P. На выходе матрица вероятностей поглощения F. Провести эксперименты, сравнить ресультаты численного решения с результатами моделирования процесса. В результате моделирование получается распределение частот поглощения каждым абсорбирующим состоянием. Нарисовать гистограммы и сравнить средние значения с результатами численного решения.
5. [16.10.2012] 1. Найти P(t) для данной Q решением матричного дифф. уравнения. 2. Написать функцию для нахождения стационарного распределения Марковской цепи с непрерывным временем для данной матрицы интенсивности Q.

Модуль 2 / Module 2

Лекции / Lectures

1. [30.10.2012] Скрытые Марковские модели I (HMM) / Hidden Markov Models I
   Примеры скрытых Марковских моделей. Формализм HMM. Матрица переходов и матрица сигналов. Три основные задачи теории HMM. Оценка вероятности последовательности сигналов (Evaluation). Forward-Backward Procedure.
2. [13.11.2012] Скрытые Марковские модели II (HMM) / Hidden Markv Models II [slides]
   Нахождение наиболее вероятной последовательности состояний (Decoding). Viterbi Algorithm. Нахождениe параметров модели (training HMM). Baum-Welch Algorithm.
3. [28.11.2012] Применения HMM для распознaвания речи / Markov chains for speech recognition [slides]
   Вероятностные модели распознавания. Звуковая и языковая модели. Распознование отдельных слов.
4. [5.12.2012] Методы Монте Карло в Марковксих цепях (MCMC) / Markov Chain Monte Carlo [slides]
   Генерация рапределений. Rejection sampling. Markov Chain Monte Carlo. Методы построения цепей
5. [12.12.2012] Алгоритм иммитации отжига и семплирование по Гиббсу/ Simulated Annealing and Gibbs Sampling [slides]
   Simulated annealing (алагоритм имитации отжига).
6. [19.12.2012] Байесовские сети / Bayesian networks [slides]
   Основные определения и примеры
7. [25.12.2012] Экзамен / Exam
   

Домашние задания / Home Assignments

1. [13.11.2012] 1. Написать функцию оценки параметров матрицы перехода Марковской цепи методом наибольшего правдоподобия. На вход последовательность состояний. На выходе матрица переходов P. 2. Смоделировать генерацию последовательности HMM. 3. Имплементироватъ brute-force алгоритм для вероятности последовательности наблюдаемых сигналов для данной HMM
2. [21.11.2012] 1. Имплементировать forward-backwаrd алгоритм для нахождения вероятности последовательности наблюдаемых сигналов для данной HMM 2. Имплементировать алгоритм Viterbi для нахождения наиболее вероятной последовательности состояний данной HMM по последовательности наблюдаемых сигналов
3. [28.11.2012] Имплементировать алгоритм Baum-Welch для нахождения параметров HMM по наблюдаяемой последовательности сигналов. Провести численные эксперименты
4. [7.12.2012] Имплеметировать Metropolis-Hasting алгоритм. Протестировать используя функцию humps в Матлабе
5. [12.12.2012] 1. Имплементировать методы диагностики MCMC по автокорреляции и Z-test 2. Имплементировать Gibbs Sampler метод для двумерного распределения f(x,y), где каждое из из условных распределений имеет экспоненциальный вид: f(x|y)~ y*exp(-y*x), f(y|x)~x*exp(-x*y). Построить гистограммы полученных случайных чисел. Вычислить и построить f(x) = E[f(x|y)] = 1/m Sum_i f(x|y_i) y_i случайная последовательность из Gibbs Sampler. Для генерации экспоненциального распределения В Матлабе можно использвать встроенную функцию exprnd

Литература по курсу / References

• Sheldon M. Ross. Introduction to Probability Models, Tenth Edition. Academic Press, 2009.
• Olive Ibe. Markov Processes for Stochastic Modeling. Academic Press 2008.
• Frederick Hillier. Introduction to Operations Research. McGraw-Hill Science, 9th edition ,2009

• J. R. Norris. Markov Chains. Cambridge University Press, 1998.
• William J. Stewart. Introduction to the Numerical Solution of Markov Chains. Princeton University Press, 1994.

• A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Lawrence R. Rabiner. Proc of IEEE, Vol 77, N 2, 1989, pp 257-286. [paper]
• Hidden Markov Models for Speech Recognition. B. H. Juang; L. R. Rabiner, Technometrics, Vol. 33, No. 3. (Aug., 1991), pp. 251-272. [paper]
• The Application of Hidden Markov Models in Speech Recognition, Mark Gales and Steve Young, Foundations and Trends in Signal Processing Vol. 1, No. 3 (2007) 195–304. [paper]
• Understanding the Metropolis-Hastings Algorithm. S. Chib, E. Greenberg, The American Statistician, Vol. 49, No. 4. ,1995, pp. 327-335. [paper]
• A guided walk Metropolis algorithm. Paul Gustafson, Statistics and computing (1998) 8, 357-364 [paper]
• Monte Carlo sampling methods using Markov chains and their applications. W. K. Hastings, Biometrika, 57,1, 1970, p. 97. [paper]
• Equation of State Calculations by Fast Computing Machines. Metropolis, N.,Rosenbluth, A. W.. Rosenbluth, M. N., Teller. A. H.. and Teller, E, Journal of Chemichal Physics, 21, 1953, p 1087-1092. [paper]
• Markov Chain Monte Carlo and Gibbs Sampling. Lecture notes. B. Walsh [paper]
• Explaining the Gibbs Sampler. G. Casella, E.I. Georrge. The American Statistician, V 46, N3, 1992, pp 167-174 [paper]
• Introduction to Monte Carlo methods. Notes. D.J.C. Mackay. [paper]
• Optimization by Simulated Annealing. S. Kirkpatrick et al. Science, Vol. 220, No. 4598, 1983, pp. 671-680. [paper]
• Bayesian Networks without Tears. Eugene Charniak, AI magazine, vol 12, No4 , 1991 pp 50-63 [paper]
• A Tutorial on Learning With Bayesian Networks, David Heckerman, Technical Report MSR-TR-95-06, 2006. [paper]
• Pattern Recognition and Machine Learning, Chapter 6, Christopher Bishop, Springer 2006. [paper]