Графические модели (курс лекций)/2012/Задание 2

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

(Различия между версиями)
Перейти к: навигация, поиск

Kropotov (Обсуждение | вклад)
(Новая: {{stop|Внимание! Страница задания находится в стадии формирования. Убедительная просьба не приступать к...)
К следующему изменению →

Версия 11:00, 8 марта 2012

Внимание! Страница задания находится в стадии формирования. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.


Начало выполнения задания: 9 марта 2012

Срок сдачи: 21 марта 2012, 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.

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

Рекомендации по выполнению задания

Пример модельного сигнала для тестирования СММ
Пример модельного сигнала для тестирования СММ
  • При тестировании ЕМ-алгоритма обучения СММ рекомендуется убедиться в том, что значение неполного правдоподобия \log p(X|w,A,\mu,\Sigma) монотонно увеличивается в итерациях.
  • В качестве простейшего модельного сигнала для тестирования генерации, обучения и сегментации с помощью СММ можно взять одномерный сигнал с тремя состояниями, в котором два состояния хорошо отличимы друг от друга, а третье состояние является промежуточным. Например, в первом состоянии мат.ожидание = 0 и дисперсия маленькая (скажем, 0.1). Во втором состоянии мат.ожидание = 1 и такая же дисперсия, как и в первом состоянии. В третьем состоянии мат.ожидание = 0, а дисперсия в несколько раз больше (скажем, 0.5).
  • При тестировании генерации из модели СММ рекомендуется эксперимент с двухмерным сигналом, чтобы убедиться в корректности задаваемых корреляций
  • Для наложения поведенческих актов на видео рекомендуется следующая процедура:
    • Загрузить в MATLAB изображения с названиями поведенческих актов с помощью imread
    • Небольшими блоками загружать в MATLAB кадры видео с помощью aviread, накладывать на них картинки с названиями поведенческих актов и сохранять полученные кадры в виде отдельных JPG картинок на диск с помощью imwrite. Сохраненные картинки должны иметь название XXXXX.jpg, где XXXXX — номер кадра.
    • Собрать полученные картинки в видео-файл с помощью бесплатной программы VirtualDub. Для этого достаточно открыть первую картинку в программе (остальные загрузятся автоматически), установить частоту кадров 25fps, установить кодек (рекомендуется DivX) и сгенерировать AVI-файл.

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

Видео-файл

MAT-файл, содержащий данные для каждого кадра видео. В нем находится массив структур, где каждая структура соответствует одному кадру, а поля структуры имеют следующее значение:

  • frame_number — номер кадра видео
  • centre — координаты центра масс мыши
  • nose — координаты предполагаемой точки носа мыши
  • tail — координаты предполагаемой точки основания хвоста мыши
  • contour — координаты точек контура мыши
  • dist_centre — расстояние от центра масс мыши до центра арены
  • dist_border — расстояние от центра масс мыши до ближайшей границы арены
  • eigen_features — проекции контура мыши на собственные контура, полученные с помощью метода главных компонент

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

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

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

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

Вариант 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 ),\\
p(t_n|t_{n-1})=\mathcal{N}(t_n|At_{n-1},\Gamma),\\
p(x_n|t_n)=\mathcal{N}(x_n|Ct_n,\Sigma),\\
p(t_1)=\mathcal{N}(t_1|\mu_0,V_0).

Все переменные модели являются непрерывными, т.е. t_n\in\mathbb{R}^D,\ x_n\in\mathbb{R}^d. Параметры модели A,\Gamma,V_0\in\mathbb{R}^{D\times D},\ C\in\mathbb{R}^{d\times D},\ \Sigma\in\mathbb{R}^{d\times d},\ \mu_0\in\mathbb{R}^D.

Данную ЛДС нужно использовать для решения задачи сопровождения (трекинга) объекта в пространстве. В частности, необходимо отфильтровать центр масс мыши на каждом кадре в видео-записи ее поведения в клетке.

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

  • Реализовать алгоритм генерации выборки из вероятностной модели ЛДС;
  • Реализовать алгоритм онлайн фильтрации сигнала с помощью фильтра Калмана;
  • Реализовать алгоритм уточнения фильтрации сигнала с помощью РТС уравнений;
  • Реализовать ЕМ-алгоритм обучения СММ при заданной размерности D. При этом часть параметров ЛДС также может быть задана пользователем;
  • Реализовать алгоритм генерации траектории движения абстрактного объекта в двухмерном пространстве. Способ генерации такой траектории отдается на выбор студента;
  • Протестировать реализованные алгоритмы на модельных данных;
  • Отфильтровать центр масс мыши в видео-сигнале с помощью реализованных алгоритмов. Выбор параметров фильтрации отдается на выбор студента. Способ выбора этих параметров необходимо отразить в отчете;
  • Наложить исходную траекторию центра масс мыши и отфильтрованную траекторию на видео с поведением;
  • Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен, в частности, включать в себя графики фильтрации сгенерированных траекторий, а также графики фильтрации центра масс мыши в увеличенном разрешении.

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

Генерация выборки
[X, T] = LDS_GENERATE(N, A, G, C, S, mu0, V0)
ВХОД
N — количество точек в генерируемой последовательности, uint32;
A — матрица преобразования среднего в последовательности t, матрица типа double размера D x D;
G — ковариационная матрица для распределения p(t_n|t_{n-1}), матрица типа double размера D x D;
C — матрица преобразования среднего при переходе от t_n к x_n, матрица типа double размера d x D;
S — ковариационная матрица для распределения p(x_n|t_n), матрица типа double размера d x d;
mu0 — мат.ожидание априорного распределения p(t_1), матрица типа double размера 1 x D;
V0 — ковариационная матрица априорного распределения p(t_1), матрица типа double размера D x D.
ВЫХОД
X — сгенерированная наблюдаемая последовательность, матрица типа double размера N x d
T — последовательность скрытых состояний, матрица типа double размера N x D

Обратите внимание: в процедуре LDS_GENERATE параметры D и d определяются неявно по размеру соответствующих элементов.

Фильтр Калмана и РТС уравнения
[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 — матрица преобразования среднего в последовательности t, матрица типа double размера D x D;
G — ковариационная матрица для распределения p(t_n|t_{n-1}), матрица типа double размера D x D;
C — матрица преобразования среднего при переходе от t_n к x_n, матрица типа double размера d x D;
S — ковариационная матрица для распределения p(x_n|t_n), матрица типа double размера d x d;
mu0 — мат.ожидание априорного распределения p(t_1), матрица типа double размера 1 x D;
V0 — ковариационная матрица априорного распределения p(t_1), матрица типа double размера D x D.
ВЫХОД
Mus_back — мат. ожидания распределений p(t_n|X), матрица типа double размера N x D;
Sigmas_back — ковариационные матрицы распределений p(t_n|X), массив типа double размера D x D x N, где Sigmas(:,:,n) является матрицей ковариации для момента времени n;
Mus_fwd — мат. ожидания распределений p(t_n|x_1,\dots,x_n), матрица типа double размера N x D;
Sigmas_fwd — ковариационные матрицы распределений p(t_n|x_1,\dots,x_n), массив типа double размера D x D x N;
LH — логарифм неполного правдоподобия \log p(X|A,\Gamma,C,\Sigma,\mu_0,V_0), double;
J — матрицы J, массив типа double размера D x D x N-1;

 

Обучение
[A, G, C, S, mu0, V0] = LDS_EM_TRAIN(X, D, InputParameters)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;
D — размерность пространства скрытых состояний, число типа uint16;
InputParameters — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
  'A' — задаваемая пользователем матрица преобразования среднего в распределении p(t_n|t_{n-1})(соответственно, ее не нужно определять в процессе EM-итераций);
  'G' — задаваемая пользователем матрица ковариации p(t_n|t_{n-1});
  'C' — задаваемая пользователем матрица преобразования среднего в распределении p(x_n|t_n);
  'S' — задаваемая пользователем матрица ковариации в распределении p(x_n|t_n);
  'num_iter' — максимально допустимое число итераций EM-алгоритма (по умолчанию = 100);
  'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации (по умолчанию = 10^{-2});
ВЫХОД
A — матрица преобразования среднего в последовательности t, матрица типа double размера D x D;
G — ковариационная матрица для распределения p(t_n|t_{n-1}), матрица типа double размера D x D;
C — матрица преобразования среднего при переходе от t_n к x_n, матрица типа double размера d x D;
S — ковариационная матрица для распределения p(x_n|t_n), матрица типа double размера d x d;
mu0 — мат.ожидание априорного распределения p(t_1), матрица типа double размера 1 x D;
V0 — ковариационная матрица априорного распределения p(t_1), матрица типа double размера D x D.

 

Генерация траектории
X = TRAJECTORY_GENERATE(N)
ВХОД
N — длина генерируемой траектории, uint32;
ВЫХОД
X — сгенерированная траектория движения объекта в двухмерном пространстве, матрица типа double размера N x 2;

Рекомендации по выполнению задания

  • При тестировании ЕМ-алгоритма обучения ЛДС рекомендуется убедиться в том, что значение неполного правдоподобия \log p(X|A,\Gamma,C,\Sigma,\mu_0,V_0) монотонно увеличивается в итерациях.
  • Простейшим способом генерации траектории объекта является генерация по скорости и ускорению, где ускорение иногда меняет величину и направление.
  • Один из вариантов тестирования реализованных алгоритмов на основе ЛДС следующий:
    • Сгенерировать траекторию движения объекта
    • Добавить к траектории случайный нормальный шум
    • Отфильтровать зашумленную траекторию с помощью фильтра Калмана; убедиться, что отфильтрованный сигнал ближе к истинной траектории, чем входной зашумленный сигнал.
    • Отфильтровать зашумленную траекторию с помощью РТС уравнений; убедиться, что результат является более точным по сравнению с фильтром Калмана.
  • При тестировании генерации из модели ЛДС рекомендуется эксперимент с двухмерным сигналом, чтобы убедиться в корректности задаваемых корреляций
  • Для наложения траектории движения на видео рекомендуется следующая процедура:
    • Загрузить в MATLAB изображения с названиями поведенческих актов с помощью imread
    • Небольшими блоками загружать в MATLAB кадры видео с помощью aviread, накладывать на них траекторию движения за последние 300 кадров и сохранять полученные кадры в виде отдельных JPG картинок на диск с помощью imwrite. Сохраненные картинки должны иметь название XXXXX.jpg, где XXXXX — номер кадра.
    • Собрать полученные картинки в видео-файл с помощью бесплатной программы VirtualDub. Для этого достаточно открыть первую картинку в программе (остальные загрузятся автоматически), установить частоту кадров 25fps, установить кодек (рекомендуется DivX) и сгенерировать AVI-файл.

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

Видео-файл

MAT-файл, содержащий данные для каждого кадра видео. В нем находится массив структур, где каждая структура соответствует одному кадру, а поля структуры имеют следующее значение:

  • frame_number — номер кадра видео
  • centre — координаты центра масс мыши
  • nose — координаты предполагаемой точки носа мыши
  • tail — координаты предполагаемой точки основания хвоста мыши
  • contour — координаты точек контура мыши
  • dist_centre — расстояние от центра масс мыши до центра арены
  • dist_border — расстояние от центра масс мыши до ближайшей границы арены
  • eigen_features — проекции контура мыши на собственные контура, полученные с помощью метода главных компонент

Для фильтрации траектории движения мыши понадобятся только значения координат центра масс мыши.

RAR архив с процедурой для MatLab, которая строит пиксельное представление линии по координатам начала и конца линии.

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

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

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

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