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

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

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

Версия 21:05, 26 марта 2011

Статья в настоящий момент дорабатывается.
Формулировка задания находится в стадии формирования. Просьба не приступать к выполнению задания, пока это предупреждение не будет удалено. Д.А. Кропотов 18:25, 26 марта 2011 (MSK)

Основная статья: Структурные методы анализа изображений и сигналов (курс лекций)

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

Начало: 28 марта 2011

Срок сдачи: 11 апреля 2011, 23:59

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

Вариант 1	Вариант 2
Ромов Петр, 202	Лямаев Сергей, 202
Иванов Петър, 202	Елшин Денис, 317
Некрасов Константин, 317	Новиков Павел, 317
Меркулова Татьяна, 317	Лобачева Екатерина, 209
Батанов Павел, 321	Птенцов Сергей, 321
Сапатов Александр, 321	Новикова Татьяна, 321
Шальнов Евгений, 321	Конев Артем, 321
Костин Григорий, 320	Икрам Магжан, 325
Переходько Евгения, 325	Парамонов Сергей, 324
Русланова Анна, 421	Ермишин Федор, 321
Исламгулов Ильдар, 420	Грядицкая Юлия, 411
Касперский Иван, 417	Тихонов Андрей, 417
Колев Денис, 417	Вартанов Сергей, 427
Ермаков Михаил, 427	Баранов Леонид, 428
Пироженко Александр, 428	Рябов Сергей, 428
Кузин Сергей, 528	Светличный Дмитрий, ВВО
Заякина Ольга, ВВО	Беликов Владимир
Гребенкина Мария	Субботин Никита

Для студентов, которых нет в этом списке, механизм выбора варианта следующий: первый вариант, если первая буква фамилии А–Л, второй — иначе.

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

Вариант 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,\dots,K\}$ . Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором $w_1,\ldots,w_K$ , причем все $w_i\ge 0$ и $\sum_iw_i=1$ . Распределение $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-a}\frac{1-A_{jj}}{1-A_{jj}^{b-a+1}}, &\ s\in\[a,b\]\end{array}\right.$

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

Подсказки

Вероятность перехода из состояния $j$ в состояние $j$ начинает зависеть от длительности $s$ нахождения в состоянии $j$ и с точностью до нормировочного множителя равна

$\hat p(t_{nj}|t_{n-1,j})=\frac{p(l_j>s)}{p(l_j>s-1)}.$

Обратите внимание, что если в качестве распределения на $l_j$ использовалось бы геометрическое распределение, вероятность перехода не зависела бы от длительности нахождения в состоянии $j$ и равнялась бы $A_{jj}$ .

Тогда вероятности перехода между состояниями в силу условия нормировки равны

$\hat p(t_{ni}|t_{n-1,j})=A_{ji}\frac{p(l_j=s)}{p(l_j>s)},$

где $s$ — длительность нахождения в состоянии $j$ к моменту времени $n-1$ . Второй множитель здесь возникает из-за того, что мы точно знаем, какой длины был сегмент с $j$ -ым состоянием (раз мы из него перешли в другое состояние, значит сегмент закончился).

Окончательно вероятности переходов рассчитываем

$p(t_{ni}|t_{n-1,j})=\frac{\hat p(t_{ni}|t_{n-1,j})}{\sum_{k=1}^K \hat p(t_{nk}|t_{n-1,j})},\ \ \forall i=1,\dots,j,\ldots,K,$

чтобы соблюсти условие нормировки $\sum_{i=1}^K p(t_{ni}|t_{n-1,j})=1.$

Эти условные вероятности теперь будут подставляться в функцию Беллмана и в функцию $S(t_{n,j})$ . Чтобы их корректно рассчитать, нам придется теперь дополнительно хранить информацию о том, сколько времени мы уже находимся в текущем состоянии (т.е. величину $l_j$ для каждого $t_{n,j}$ ).

— Д.П. Ветров 19:53, 30 октября 2009 (MSK)

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

Генерация выборки

[X, T] = HMM_GENERATE(N, w, A, Mu, Sigmas)

ВХОД

N — количество точек в генерируемой последовательности, uint32;

w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;

A — матрица перехода, матрица типа double размера K x K;

Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;

Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;

ВЫХОД

X — сгенерированная последовательность, матрица типа double размера N x d

T — последовательность скрытых состояний, матрица типа double размера 1 x N

Обратите внимание: в процедуре HMM_GENERATE количество признаков и количество скрытых состояний определяются неявно по размеру соответствующих элементов.

Сегментация

T = HMM_TEST(X, w, A, Mu, Sigmas, a, b)

ВХОД

X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;

w — априорные вероятности, матрица типа double размера 1 x K, где K – количество скрытых состояний;

A — матрица перехода, матрица типа double размера K x K;

a — минимально возможная длина сегмента, uint16, если параметр не задан (=[] или число входных параметров = 5), то по умолчанию = 1

b — максимально возможная длина сегмента, uint16, если параметр не задан (=[] или число входных параметров <= 6), то по умолчанию = +inf

ВЫХОД

T — полученная последовательность скрытых состояний, матрица типа double размера 1 x N

Обучение

[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K)

[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K, InputParameters)

ВХОД

X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;

K — количество скрытых состояний, число типа uint16;

InputParameters — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:

'w' — задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);

'A' — задаваемая пользователем матрица перехода;

'Mu' — задаваемые пользователем центры гауссиан для каждого состояния;

'Sigmas' — задаваемые пользователем матрицы ковариации гауссиан;

'num_iter' — максимально допустимое число итераций EM-алгоритма;

'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации;

ВЫХОД

w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;

A — матрица перехода, матрица типа double размера K x K;

Core — все параметры для всех итераций EM-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigmas', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия

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

Архив, содержащий:

Readme.txt — файл с ФИО сдающего + комментарии по заданию
HMM_GENERATE.m
HMM_TEST.m
HMM_EM_TRAIN.m
Набор вспомогательных файлов при необходимости