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

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

Версия от 21:56, 26 марта 2011; Kropotov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья в настоящий момент дорабатывается.
Формулировка задания находится в стадии формирования. Просьба не приступать к выполнению задания, пока это предупреждение не будет удалено. Д.А. Кропотов 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$ .

Данную СММ нужно использовать для сегментации поведения мыши в клетке на набор т.н. поведенческих актов. Поведенческие акты — это элементарные единицы в описании поведения. Примерами поведенческих актов для мыши в клетке являются «бежит», «роется», «сидит на месте», «встает на задние лапы», «крутится на месте» и т.д. В качестве входных данных для этой задачи выступают видео с записью поведения мыши в клетке (см. фрагмент ниже) и набор параметров мыши для каждого кадра видео: координаты центра масс, точки носа и хвоста, координаты пикселей контура мыши. Необходимо на основе этих данных рассчитать набор признаков (например, скорости, ускорения, различные углы) и с помощью ЕМ-алгоритма обучения СММ выделить 3 поведенческих акта. Например, при использовании только скорости можно выделить поведенческие акты вида «бежит», «идет», «стоит на месте». Набор используемых признаков и интерпретация полученных поведенческих актов отдаются на выбор студента. Полученные поведенческие акты необходимо наложить на видео с поведением.

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

Реализовать алгоритм генерации выборки из вероятностной модели СММ
Реализовать EM-алгоритм обучения СММ при заданном числе состояний K.
Реализовать алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ
Протестировать реализованные алгоритмы на модельных сигналах
Рассчитать набор признаков для описания поведения мыши и на их основе найти 3 осмысленных поведенческих акта с помощью ЕМ-алгоритма обучения СММ, проинтерпретировать полученные поведенческие акты
Наложить полученные поведенческие акты на видео с поведением
Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен, в частности, включать в себя графики сегментации модельных сигналов.

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

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

[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)

ВХОД

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

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

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

ВЫХОД

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-алгоритма (по умолчанию = 100);

'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации (по умолчанию = $10^{-2}$ );

ВЫХОД

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

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

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

Данные для выполнения задания

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

Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 1. ФИО, номер группы». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.

Письмо должно содержать:

PDF-файл с описанием проведенных исследований
HMM_GENERATE.m
HMM_TEST.m
HMM_EM_TRAIN.m
Ссылка на видео-файл, размещенный на файлообменнике или на видео-хостинге, с наложенными поведенческими актами. Лучше вставить видео-файл непосредственно внутрь PDF-файла с отчетом (это можно сделать, например, в программе Adobe Acrobat 9 и выше). Тогда нужно прислать ссылку на этот PDF-файл.
Набор вспомогательных файлов при необходимости