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

Осень 2013 / Fall 2013

Тематический План Курса / 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. [05.09.2013] Цепи Маркова / Markov chains
   Стохастические процессы. Марковские процессы. Цепи Маркова с дискретным временем. Переходная матрица. Конечномерные распределения и матрица перехода за n шагов. Уравнение Колмогорова-Чепмена.
2. [12.09.2013] Классификация состояний цепи Маркова / Classification of states in Markov chains
   Классифиакция состояний. Достижимые и сообщающиеся состояния. Классы эквивалентности. Неразложимые классы. Неразложимая цепь Маркова. Транзитивные и рекуррентные (возвратные) состояния. Критерий возвратности. Понятие периода состояния. Периодичские состояния. Понятие времени возвращения. Вычисление среднего времени возвращения.
3. [19.09.2013] Стационарное распределение в Марковских цепях / Stationary distribution in Markov chains
   Эргодические состояние и эргодическая Марковская цепь. Стационарное состояние. Основная теорема Марковских цепей. Уравнения стационарного состояния
4. [26.09.2013] Поглощающая Марковская цепь / Absorbing Markov chains [slides] [whiteboard]
   Каноническая форма матрицы. Вероятность поглощения. Время до поглощения.
5. [03.10.2013] Цепи Маркова с непрерывным временем I/ Continuous time Markov process [whiteboard]
   Понятие процесса с непрерывным временем. Интенсивность переходов. Матрица интенсивности.
6. [10.10.2013] Цепи Маркова с непрерывным временем II/ Continuous time Markov process [whiteboard]
   Уравнение Чепмена Колмогорова. Прямое и обратное уравнения Колмогорова
7. [17.10.2013] Стационарное распределение в цепях с непрерывным временем / Stationary distribution in continuous time Markov chains [whiteboard]
   Уравнение стационарного состояния.
8. [24.10.2013] Очереди / Queuenig systems.
   Birth- Death process. Пуассоновский процесс. Время ожидания. Свойства процесса. M/M/S queues.
9. [31.10.2012] Зачет / Exam
   

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

1. [10.09.2012] 1) Моделирование дискретного Марковского процесса. На вход матрица переходов P и число шагов процесса. На выходе последовательность случайных состояний Марковского процесса. Провести несколько экспериментов. 2) Написать функцию для численного расчета стационарных состояний неразложимой конечномерной марковской цепи. Вычисления производить двумя способами: а) решением линейных уравнений b) через собственный вектор. На вход матрица переходов P. На выходе векор стационарных состояний. Провести вычисления на примерах. Сравнить результаты полученные моделированием и численным рассчетом.
2. [03.10.2012] 1) Написать функцию для расчета математического ожидания времени первого посещения состояния. На вход матрица переходов P. На выходе матрица из средних времен M. Провести вычисления на примерах 2) Написатъ функцию для расчета вероятностей поглощения в абсорбирующих состояниях конечной поглощающей марковской цепи. На вход матрица переходов P. На выходе матрица вероятностей поглощения F. Провести вычисления на примерах.
3. [18.10.2012] Написать функцию для нахождения стационарного распределения Марковской цепи с непрерывным временем для данной матрицы интенсивности Q а) решением линейных уравнений b) через собственный вектор. Провести вычисления на примерах.
4. [31.10.2012] 1) Моделирование непрерывного Марковского процесса. На вход матрица интенсивностей переходов Q, на выходе последовательность состояний и времен нахождения в каждом из состояний. Провести несколько экспериментов. Изобразить временную диаграмму переходов между состянимии, по оси Х - время, по оси Y - номер состояния. 2) Используя результаты моделирования, найти частоты стационарного распределения. Сравнить результы полученные моделированием с численным рассчетом (предыдущее задание).

Модуль 2 / Module 2

Лекции / Lectures

1. [07.11.2013] Скрытые Марковские модели I (HMM) / Hidden Markov Models I[slides][whiteboard]
   Примеры скрытых Марковских моделей. Формализм HMM. Матрица переходов и матрица сигналов. Три основные задачи теории HMM. Оценка вероятности последовательности сигналов (Evaluation). Forward-Backward Procedure.
2. [14.11.2013] Скрытые Марковские модели II (HMM) / Hidden Markv Models II [slides]
   Нахождение наиболее вероятной последовательности состояний (Decoding). Viterbi Algorithm. Нахождениe параметров модели (training HMM). Baum-Welch Algorithm.
3. [21.11.2013] Марковские случайные поля / Markov Random Fields (MRF)[slides]
   
4. [28.11.2013] Байесовские сети / Bayesian networks [slides]
   Основные определения и примеры
5. [5.12.2013] Методы Монте Карло в Марковксих цепях (MCMC) / Markov Chain Monte Carlo [slides]
   Генерация рапределений. Rejection sampling. Markov Chain Monte Carlo. Методы построения цепей
6. [12.12.2013] Алгоритм иммитации отжига и семплирование по Гиббсу/ Simulated Annealing and Gibbs Sampling [slides]
   Simulated annealing (алагоритм имитации отжига).
7. [19.12.2013] Случайные (вероятностные) алгоритмы / Randomized algorithms[slides]
   Вероятностные алгоритмы. Типы алгаритмов. Лас Вегас и Монте Карло. Оценка ошибки алгоритма. Примеры.
8. [26.12.2013] Экзамен / Exam
   

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

1. [14.11.2013]
   1. Имплементировать forward-backwаrd алгоритм для нахождения вероятности последовательности наблюдаемых сигналов для данной HMM
   2. Имплементировать алгоритм Viterbi для нахождения наиболее вероятной последовательности состояний данной HMM по последовательности наблюдаемых сигналов
   3. Имплементировать алгоритм Baum-Welch для нахождения параметров HMM по наблюдаяемой последовательности сигналов.
2. [28.11.2013]
   Используя программы из ДЗ1, вычислить наиболее вероятную последовательность состояний и параметры HMM на основе наблюдаемых сигналов. Предположить, что модель описывается двумя скрытыми состояниями.
3. [12.12.2013]
   1 .Имплементировать Simulated Annealing алгоритм для решения задачи Traveling salesman. Рассмотреть случайно распределенные (однородно) N=100 городов на квадрате 10х10. Вычислить оптимальный тур проходящий через все города с возвращением в начальный город и посещающий каждый промежуточный город ровно один раз. Визуализировать полученныей оптимальный маршрут.
   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

• Howard Taylor, Samuel Karlin. An Introduction to Stochastic Modeling, 3rd Edition, Academic Press, 1998
• 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]