Стохастическое 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

Основная / Main Дополнительная / Additional Статьи / Papers