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

Авторы: Дмитрий Кропотов,
Дмитрий Ветров

Начало: 31 октября 2009
Конец: 15 ноября 2009 (23:59)

Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. здесь. Тем, кто хочет выполнить это задание, но по каким-либо причинам не выполнял первое задание, нужно написать письмо и получить номер варианта.

Среда реализации для всех вариантов – 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=0, 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}).

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

Генерация выборки
[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;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;
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;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;
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
  • Набор вспомогательных файлов при необходимости

Вариант 2

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

Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:

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,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
  • Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, работающий в реальном времени

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

При решении задачи сегментации с помощью алгоритма Витерби предполагается, что наблюдаемые данные поступают последовательно. Необходимо модифицировать алгоритм Витерби так, чтобы он был способен проводить сегментацию сигнала по имеющимся данным. Здесь используется следующее предположение: поступающие в текущий момент данные не влияют на сегментацию отдаленных участков сигнала в прошлом. Иными словами, каковы бы не были наблюдения, например, начиная с момента времени 100 и дальше, сегментация первых, скажем, 40 точек сигнала останется без изменений. Это позволяет нам провести окончательную сегментацию первых сорока точек сигнала, не дожидаясь получения всего объема данных, уже в сотый момент времени. По мере поступления новых данных граница окончательной сегментации (граница принятия решения) будет смещаться вправо.

Задача: для каждого момента времени определить, на какой участок в прошлом новые наблюдения уже не оказывают влияния, и провести его сегментацию алгоритмом Витерби. При хорошо различимых состояниях задержка сегментации (разница между границей принятия решения и текущим моментом времени) будет незначительной.

Подсказки

Вариантом реализации такого алгоритма является прореживание таблицы функции S(t_{n,j}), содержащей аргмаксы функции Беллмана. Кладем S(t_{n,j})=0, если \not\exist i: S(t_{n+1},i)=j, т.е. если ни одна из оптимальных траекторий не проходит через t_{n,j}. В этом случае значения функции Беллмана и функции S для t_{n,j} интереса не представляют. В какой-то момент l окажется, что все S(t_{l,j})=0,\ \ j\ne j_0. Это и будет означать, что все оптимальные траектории проходят через состояние j_0 в момент времени l. Но тогда мы можем провести сегментацию всего сигнала до момента l включительно и очистить память, удалив массивы со значениями функции Беллмана и функции S от начала до момента времени l - сегментация на этом участке уже не изменится.

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

Генерация выборки
[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, Borders] = HMM_TEST(X, w, A, Mu, Sigmas)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;
w — априорные вероятности, матрица типа double размера 1 x K, где K – количество скрытых состояний;
A — матрица перехода, матрица типа double размера K x K;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;
ВЫХОД
T — полученная последовательность скрытых состояний, матрица типа double размера 1 x N
Borders — границы принятия решений при он-лайн сегментации, матрица типа double размера 2 x num_borders, каждая граница задается парой чисел - номер во входной последовательности и соответствующая ему правая граница сегментации в последовательности скрытых состояний T
Обучение
[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;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;
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
  • Набор вспомогательных файлов при необходимости

Вариант 3

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

Рассматривается авторегрессионная скрытая марковская модель, в которой полное правдоподобие задается как:

p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n,x_{n-1},\dots,x_{n-M} )

Пусть скрытая компонента 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. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями с одинаковой матрицей ковариации \Sigma и своими математическими ожиданиями \mu_{n,j} для каждого состояния и каждого момента времени. Математическое ожидание зависит не только от состояния СММ, но и от предудыщих значений $ x $ (авторегрессионная составляющая) и задается формулой

\mu_{n,j}=d_j+\sum_{m=1}^Ma_mx_{n-m},

где d_j — вектор смещения, определяемый только номером состояния СММ, а коэффициенты авторегрессии a_m не зависят от состояния СММ.

Таким образом, набор параметров модели определяется вектором $ \vec{w} $, матрицей A, значениями векторов смещений для каждого состояния \{d_i\}_{i=1}^K, матрицей ковариций \Sigma и коэффициентами авторегрессии a_m. Глубина авторегрессии M задается пользователем.

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

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

Пояснения к заданию

Для подсчета авторегрессии в первые моменты времени вам понадобятся знания о значениях наблюдаемой компоненты x_n в отрицательные моменты времени -1,\ldots,-M+1. Считайте, что в них значение x равно среднему значению наблюдаемой компоненты, подсчитанному по всему сигналу. Обратите внимание на необходимость оценивания коэффициентов авторегрессии и сдвижки на М-шаге. Для получения аналитических формул вам придется выписать функцию правдоподобия, приравнять ее логарифм к нулю и выразить искомые величины.

Подсказки

Тут, собственно, подсказывать особенно и нечего. Отличие от того, что разобрано в лекциях, заключается в изменении функции p(x_n|\phi_j) и применении всех разобранных на лекциях алгоритмов. Подумайте, в каких местах нужна модификация формул из лекций, а в каких нет.

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

Генерация выборки
[X, T] = ARHMM_GENERATE(N, w, A, Mu, Sigma, C)
ВХОД
N — количество точек в генерируемой последовательности, uint32;
w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
A — матрица перехода, матрица типа double размера K x K;
Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;
Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;
C — коэффициенты авторегрессии, матрица типа double размера K x M;
ВЫХОД
X — сгенерированная последовательность, матрица типа double размера N x d
T — последовательность скрытых состояний, матрица типа double размера 1 x N

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

Сегментация
T = ARHMM_TEST(X, w, A, Mu, Sigma, C)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;
w — априорные вероятности, матрица типа double размера 1 x K, где K – количество скрытых состояний;
A — матрица перехода, матрица типа double размера K x K;
Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;
Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;
C — коэффициенты авторегрессии, матрица типа double размера K x M, где M — глубина авторегрессии;
ВЫХОД
T — полученная последовательность скрытых состояний, матрица типа double размера 1 x N
Обучение
[w, A, Mu, Sigma, C, core] = ARHMM_EM_TRAIN(X, K, M)
[w, A, Mu, Sigma, C, core] = ARHMM_EM_TRAIN(X, K, M, InputParameters)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;
K — количество скрытых состояний, число типа uint16;
M — глубина авторегрессии, число типа uint16;
InputParameters — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
'w' — задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);
'A' — задаваемая пользователем матрица перехода;
'Mu' — задаваемые пользователем центры гауссиан для каждого состояния;
'Sigma' — задаваемая пользователем матрица ковариации гауссиан;
'C' — задаваемые пользователем коэффициенты авторегрессии;
'num_iter' — максимально допустимое число итераций EM-алгоритма;
'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации;
ВЫХОД
w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
A — матрица перехода, матрица типа double размера K x K;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigma — матрица ковариации гауссиан, массив типа double размера d x d;
C — коэффициенты авторегрессии, матрица типа double размера K x M;
Core — все параметры для всех итераций EM-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigma', 'C', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия


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

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

  • Readme.txt — файл с ФИО сдающего + комментарии по заданию
  • ARHMM_GENERATE.m
  • ARHMM_TEST.m
  • ARHMM_EM_TRAIN.m
  • Набор вспомогательных файлов при необходимости
© Лаборатория компьютерной графики при ВМиК МГУ