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

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

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

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

Версия 16:48, 30 октября 2009

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

Содержание

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

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

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

Срок сдачи: 15 ноября 2009

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

Среда реализации для всех вариантов – 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,\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$ . В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.

Подсказки

Будут, когда сам разберусь как такую задачу решать

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

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

[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

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

Сегментация

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), то по умолчанию = 0

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-алгоритма, массив структур длины NumberOfIterations с полями ‘w’, ‘A’, ‘Mu’, ‘Sigmas’, ‘gamma’, ‘LH’, где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия

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