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

Осень 2011 / Fall 2011

Тематический План Курса / 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. Вероятностные (случайные) алгоритмы / Randomized algorithms

Модуль 1 / Module 1

Лекции / Lectures

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

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

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

Модуль 2 / Module 2

Лекции / Lectures

1. [16.11.2010] Скрытые Марковские модели I (HMM) / Hidden Markov Models I
   Примеры скрытых Марковских моделей. Формализм HMM. Матрица переходов и матрица сигналов. Три основные задачи теории HMM. Оценка вероятности последовательности сигналов (Evaluation). Forward-Backward Procedure.
2. [23.11.2010] Скрытые Марковские модели II (HMM) / Hidden Markv Models II
   Нахождение наиболее вероятной последовательности состояний (Decoding). Viterbi Algorithm. Нахождениe параметров модели (training HMM). Baum-Welch Algorithm.
3. [30.11.2010] Применения HMM для распознaвания речи / Markov chains for speech recognition
   Вероятностные модели распознавания. Звуковая и языковая модели. Распознование отдельных слов.
4. [07.12.2010] Методы Монте Карло в Марковксих цепях (MCMC) / Markov Chain Monte Carlo
   Генерация рапределений. Rejection sampling. Markov Chain Monte Carlo. Методы построения цепей.
5. [14.12.2010] Алгоритм иммитации отжига / Simulated Annealing
   Алгоритмы глобальной оптимизации. Simulated annealing (алагоритм имитации отжига). Дискретная и комбинаторная оптимизация. Нахождение минимума многомерной непрерывной функции.
6. [21.12.2010] Случайные (вероятностные) алгоритмы / Randomized algorithms
   Вероятностные алгоритмы. Типы алгаритмов. Лас Вегас и Монте Карло. Оценка ошибки алгоритма. Примеры. Polynomial identity и Min-cut algorithms.
7. [26.12.2011] Зачет / Exam
   

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

1. (6) [16.11.2010] 1) Смоделировать генерацию последовательности HMM. 2) Имплементировать forward-backword алгоритм для нахождения вероятности последовательности наблюдаемых сигналов для данной HMM 3) Имплементировать алгоритм Viterbi для нахождения наиболее вероятной последовательности состояний данной HMM по последовательности наблюдаемых сигналов
2. (7) [23.11.2010] Имплементировать алгоритм Baum-Welch для нахождения параметров HMM по наблюдаяемой последовательности сигналов. Провести численные эксперименты
3. (8) [30.11.2010] 1). Написать функцию оценки параметров матрицы перехода Марковской цепи методом наибольшего правдоподобия. На вход последовательность состояний. На выходе матрица переходов P. 2). Построить статистическую лингвистическую модель (bi-grams) русского языка. Использовать тексты по усмотрению. Показать 10 наиболее частотных слов и 10 наиболее частотных bi-gram. Сгенерировать случайный фрагмент текста используя полученную модель.
4. (9)[07.12.2010] 1). Вычислить объем многомерного шара методом Монте Карло, оценить значение числа "пи" 2). Имплементировать acceptance-rejection метод. Проверить используя функцию humps в Матлабе 3). Имплеметировать Metropolis-Hasting алгоритм. Детали алгоритмов
5. (10)[14.12.2010] Имплементировать Simulated Annealing алгоритм для решения задач 1) дискретной или 2) непрерывной оптимизации. В случае (1) претестировать на примере задачи Traveling salesman, в случае (2) на данной двумерной функции. Детали алгоритмов

Литература по курсу / 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]
• Markov Chain Monte Carlo and Gibbs Sampling. Lecture notes. B. Walsh [paper]
• Optimization by Simulated Annealing. S. Kirkpatrick et al. Science, Vol. 220, No. 4598, 1983, pp. 671-680. [paper]
• An introduction to randomized algorithms. Richard M. Karp. Discrete Applied Math. 34, 1991, pp 165-201 [paper]