Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Версия 14:04, 30 октября 2009

Статья в настоящий момент дорабатывается.
Д.А. Кропотов 14:18, 30 октября 2009 (MSK)

Содержание

1 Задание 2. Скрытые марковские модели.

Задание 2. Скрытые марковские модели.

Начало: 31 октября 2009

Срок сдачи: 13 октября 2009

Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. здесь.

Вариант 1

Формулировка задания

Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как: $p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )$

Пусть скрытая компонента $t_n$ в произвольный момент времени может принимать значения из множества ${1,\ldots,К}$ . Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором $w_1,\ldots,w_K$ , причем все $w_i$ неотрицательны и в сумме дают единицу. Распределение $p(t_n |t_{n-1})$ задается матрицей перехода $A$ размера $K\times K$ , где в $ij$ -ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания $\mu_i$ и матрицы ковариации $\Sigma_i$ для каждого состояния. Таким образом, набор параметров модели определяется вектором $\vec{w}$ , матрицей $A$ , значениями векторов математических ожиданий и матриц ковариаций для каждого состояния $\{\mu_i,\Sigma_i\}_{i=1}^K$ .

Для выполнения задания необходимо реализовать:

Алгоритм генерации выборки из вероятностной модели СММ
EM-алгоритм обучения СММ при заданном числе состояний K.
Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, учитывающий заданное распределение на длительность нахождения в одном состоянии

Пояснения к варианту

При использовании стандартного алгоритма Витерби, описанного в лекциях легко показать, что априорное распределение на длительность $l_j$ нахождения в состоянии $j$ является геометрическим, т.е. вероятность находиться в этом состоянии ровно $s$ моментов времени равна

$p(l_j=s)=A_{jj}^s(1-A_{jj})$

Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии $j$ имеет вид $p(l_j=s)=\left{\begin{array}{cc}0 & s\not\in\[a,b\]\\ A_{jj}^s\frac{1-A_{jj}}{1-A_{jj}^{b-a}} & s\in\[a,b\]\end{array}\right.$

Иными словами, в одном состоянии СММ не может находиться меньше $a$ моментов времни и больше $b$ моментов времени. Частным случаем может быть $a=0$ , $b=+\infty$ . В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.

Подсказки

Среда реализации – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.

Спецификация реализуемых функций

Оформление задания