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

Начало: 18 ноября 2008
Конец: 2 декабря 2008 (23:59)

Задание состоит из двух вариантов. Предполагается, что первый вариант выполняют студенты, у которых первая буква фамилии лежит в интервале от А до К, а второй вариант – от Л до Я.

Первый вариант

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

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

Пусть скрытая компонента в произвольный момент времени может принимать значения из множества {1,…,К}. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором w1,…,wK, причем все wi неотрицательны и в сумме дают единицу. Распределение задается матрицей перехода A размера K x K, где в ij-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора мат.ожидания и матрицы ковариации для каждого состояния.

Таким образом, набор параметров модели определяется вектором w, матрицей A, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния.

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

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

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

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

Сегментация
T = 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

Обучение
[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K)

ВХОД
X – входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;
K – количество скрытых состояний, число типа uint16;

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

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

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

ВХОД
NumberOfObjects – количество точек в генерируемой последовательности, 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 размера NumberOfObjects x d
T – последовательность скрытых состояний, матрица типа double размера 1 x NumberOfObjects

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

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

Архив, содержащий:
• Readme.txt – файл с ФИО сдающего + комментарии по заданию
• HMM_test.m
• HMM_EM_train.m
• HMM_generate.m
• Набор вспомогательных файлов при необходимости

Второй вариант

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

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

Все атомарные распределения задаются линейными гауссовскими моделями:


Таким образом, набор параметров модели определяется вектором mu0 и матрицами A, Gamma, C, Sigma, V0..
Для выполнения задания необходимо реализовать:

• Фильтр Калмана для фильтрации сигнала при известных значениях параметров
• РТС уравнения для фильтрации сигнала при известных значениях параметров
• EM-алгоритм обучения ЛДС при заданной размерности скрытой переменной t.
• Алгоритм генерации выборки из вероятностной модели ЛДС

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

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

Фильтр Калмана
[Mus, Sigmas, LH] = LDS_forward(X, A, G, C, S, mu0, V0)

ВХОД
X – входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – размерность пространства;
A – матрица преобразования среднего значения для скрытой переменной, матрица типа double размера K x K;
G – матрица ковариации для модели движения, матрица типа double размера K x K;
C – матрица преобразования среднего значения для модели генерации данных, матрица типа double размера d x K;
S – матрица ковариации для модели генерации данных, матрица типа double размера d x d;
mu0 – вектор средних значений для априорной вероятности первой скрытой переменной, матрица типа double размера 1 x K;
V0 – матрица ковариации для априорного распределения, матрица типа double размера K x K;

ВЫХОД
Mus – вычисленные средние значения для hat_alpha(t_n), матрица типа double размера N x K;
Sigmas – вычисленные матрицы ковариации для hat_alpha(t_n), массив типа double размера K x K x N;
LH – полученное значение логарифма правдоподобия, число типа double

РТС уравнения
[Mus_back, Sigmas_back, Mus_fwd, Sigmas_fwd, LH, J] = LDS_FORWARDBACKWARD(X, A, G, C, S, mu0, V0)

ВХОД
X – входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – размерность пространства;
A – матрица преобразования среднего значения для скрытой переменной, матрица типа double размера K x K;
G – матрица ковариации для модели движения, матрица типа double размера K x K;
C – матрица преобразования среднего значения для модели генерации данных, матрица типа double размера d x K;
S – матрица ковариации для модели генерации данных, матрица типа double размера d x d;
mu0 – вектор средних значений для априорной вероятности первой скрытой переменной, матрица типа double размера 1 x K;
V0 – матрица ковариации для априорного распределения, матрица типа double размера K x K;

ВЫХОД
Mus_back – вычисленные средние значения для gamma(t_n), матрица типа double размера N x K;
Sigmas_back – вычисленные матрицы ковариации для gamma(t_n), массив размера K x K x N;
Mus_fwd – вычисленные средние значения для hat_alpha(t_n) (фильтра Калмана), матрица типа double размера N x K;
Sigmas_fwd – вычисленные матрицы ковариации для hat_alpha(t_n) (фильтра Калмана), массив типа double размера K x K x N;
LH – полученное значение логарифма правдоподобия, число типа double;
J – вычисленные матрицы J, массив типа double размера K x K x N;

EM-алгоритм обучения

[A, G, C, S, mu0, V0, core] = LDS_EM_TRAIN(X, K)
[A, G, C, S, mu0, V0, core] = LDS_EM_TRAIN(X, K, InputParameters)

ВХОД
X – входная последовательность, матрица типа double размера N x d, где N – число точек в последовательности, d – число признаков;
K – размерность пространства скрытой переменной, uint8;
InputParameters – (необязательный аргумент) известные параметры, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2, …, значение параметра ParameterName может быть строка ‘A’, ‘G’, ‘C’, ‘S’, ‘mu0’, ‘V0’, в качестве ParameterValue передается значение соответствующего параметра

ВЫХОД
A – матрица преобразования среднего значения для скрытой переменной, матрица типа double размера K x K;
G – матрица ковариации для модели движения, матрица типа double размера K x K;
C – матрица преобразования среднего значения для модели генерации данных, матрица типа double размера d x K;
S – матрица ковариации для модели генерации данных, матрица типа double размера d x d;
mu0 – вектор средних значений для априорной вероятности первой скрытой переменной, матрица типа double размера 1 x K;
V0 – матрица ковариации для априорного распределения, матрица типа double размера K x K;
core – все параметры для всех итерация ЕМ-алгоритма, массив структур длины NumberOfIterations с полями 'A', 'G', 'C', 'S', 'mu0', 'V0', 'gamma_Mus', 'gamma_Sigmas', 'J' and 'LH'.

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

[X, T] = LDS_GENERATE(N, A, G, C, S, mu0, V0)

ВХОД
N – длина генерируемой последовательности, число типа uint32;
A – матрица преобразования среднего значения для скрытой переменной, матрица типа double размера K x K;
G – матрица ковариации для модели движения, матрица типа double размера K x K;
C – матрица преобразования среднего значения для модели генерации данных, матрица типа double размера d x K;
S – матрица ковариации для модели генерации данных, матрица типа double размера d x d;
mu0 – вектор средних значений для априорной вероятности первой скрытой переменной, матрица типа double размера 1 x K;
V0 – матрица ковариации для априорного распределения, матрица типа double размера K x K;

ВЫХОД
X – сгенерированная последовательность, матрица типа double размера N x d;
T – последовательность значений скрытой переменной, матрица типа double размера N x K

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

Генерация траектории движения объекта

X = trajectory_generate(Parameters)

ВХОД
Parameters – произвольный набор параметров (должен быть описан в теле функции!)

ВЫХОД
X – сгенерированная траектория, матрица типа double размера N x d, где N – количество точек в траектории, d – размерность пространства

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

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

• Readme.txt – файл с ФИО сдающего + комментарии по заданию
• LDS_forward.m
• LDS_forward_backward.m
• LDS_EM_train.m
• LDS_generate.m
• Trajectory_generate.m
• Набор вспомогательных файлов при необходимости

Вопросы

Вопросы по заданию можно задать либо на очередной лекции, либо на форуме.

© Лаборатория компьютерной графики при ВМиК МГУ