Графические модели (курс лекций)/2012/Задание 2
Материал из MachineLearning.
Строка 25: | Строка 25: | ||
Данную ЛДС нужно протестировать на модельной задаче сопровождения (трекинга) объекта в пространстве. | Данную ЛДС нужно протестировать на модельной задаче сопровождения (трекинга) объекта в пространстве. | ||
+ | |||
+ | Рассматривается также нелинейная динамическая система с нормальным шумом, в которой вероятности переходов задаются как: | ||
+ | <center> | ||
+ | <tex> | ||
+ | p(t_n|t_{n-1}) = \mathcal{N}(t_n|f(t_{n-1}),\Gamma),\\ | ||
+ | p(x_n|t_n) = \mathcal{N}(x_n|g(t_n),\Sigma),\\ | ||
+ | p(t_1) = \mathcal{N}(t_1|\mu_0,V_0). | ||
+ | </tex> | ||
+ | </center> | ||
+ | |||
+ | Здесь <tex>f</tex> и <tex>g</tex> — известные вектор-функции. | ||
+ | |||
+ | Для этой системы нужно реализовать расширенный фильтр Калмана и протестировать его работу на модельных данных. | ||
Для выполнения задания необходимо: | Для выполнения задания необходимо: | ||
- | * Реализовать алгоритм генерации выборки из вероятностной модели ЛДС; | + | * Реализовать алгоритм генерации выборки из вероятностной модели ЛДС и нелинейной ДС; |
- | * Реализовать алгоритм онлайн фильтрации сигнала с помощью фильтра Калмана | + | * Реализовать алгоритм онлайн фильтрации сигнала с помощью фильтра Калмана и с помощью расширенного фильтра Калмана; |
- | + | ||
* Реализовать обучение параметров ЛДС с учителем. При этом часть параметров ЛДС может быть задана пользователем; | * Реализовать обучение параметров ЛДС с учителем. При этом часть параметров ЛДС может быть задана пользователем; | ||
* Реализовать алгоритм генерации траектории движения абстрактного объекта в двухмерном пространстве. Способ генерации такой траектории отдается на выбор студента; | * Реализовать алгоритм генерации траектории движения абстрактного объекта в двухмерном пространстве. Способ генерации такой траектории отдается на выбор студента; | ||
Строка 38: | Строка 50: | ||
{|class="standard" | {|class="standard" | ||
- | !''Генерация выборки'' | + | !''Генерация выборки для ЛДС'' |
|- | |- | ||
- | |[X, T] = LDS_generate(N, A | + | |[X, T] = LDS_generate(N, A, C, G, S, mu0, V0) |
|- | |- | ||
|ВХОД | |ВХОД | ||
Строка 49: | Строка 61: | ||
|- | |- | ||
|A — матрица преобразования среднего в последовательности <tex>t</tex>, матрица типа double размера D x D; | |A — матрица преобразования среднего в последовательности <tex>t</tex>, матрица типа double размера D x D; | ||
- | |||
- | |||
|- | |- | ||
|C — матрица преобразования среднего при переходе от <tex>t_n</tex> к <tex>x_n</tex>, матрица типа double размера d x D; | |C — матрица преобразования среднего при переходе от <tex>t_n</tex> к <tex>x_n</tex>, матрица типа double размера d x D; | ||
+ | |- | ||
+ | |G — ковариационная матрица для распределения <tex>p(t_n|t_{n-1})</tex>, матрица типа double размера D x D; | ||
|- | |- | ||
|S — ковариационная матрица для распределения <tex>p(x_n|t_n)</tex>, матрица типа double размера d x d; | |S — ковариационная матрица для распределения <tex>p(x_n|t_n)</tex>, матрица типа double размера d x d; | ||
Строка 67: | Строка 79: | ||
|X — сгенерированная наблюдаемая последовательность, матрица типа double размера N x d | |X — сгенерированная наблюдаемая последовательность, матрица типа double размера N x d | ||
|- | |- | ||
- | |T — последовательность скрытых | + | |T — последовательность скрытых характеристик, матрица типа double размера N x D |
|} | |} | ||
|} | |} | ||
Строка 74: | Строка 86: | ||
{|class="standard" | {|class="standard" | ||
- | !''Фильтр Калмана'' | + | !''Фильтр Калмана для ЛДС'' |
|- | |- | ||
- | |[ | + | |[M, V] = LDS_filter(X, A, C, G, S, mu0, V0) |
|- | |- | ||
|ВХОД | |ВХОД | ||
Строка 85: | Строка 97: | ||
|- | |- | ||
|A — матрица преобразования среднего в последовательности <tex>t</tex>, матрица типа double размера D x D; | |A — матрица преобразования среднего в последовательности <tex>t</tex>, матрица типа double размера D x D; | ||
- | |||
- | |||
|- | |- | ||
|C — матрица преобразования среднего при переходе от <tex>t_n</tex> к <tex>x_n</tex>, матрица типа double размера d x D; | |C — матрица преобразования среднего при переходе от <tex>t_n</tex> к <tex>x_n</tex>, матрица типа double размера d x D; | ||
+ | |- | ||
+ | |G — ковариационная матрица для распределения <tex>p(t_n|t_{n-1})</tex>, матрица типа double размера D x D; | ||
|- | |- | ||
|S — ковариационная матрица для распределения <tex>p(x_n|t_n)</tex>, матрица типа double размера d x d; | |S — ковариационная матрица для распределения <tex>p(x_n|t_n)</tex>, матрица типа double размера d x d; | ||
Строка 102: | Строка 114: | ||
| | | | ||
{| | {| | ||
- | | | + | |M — мат. ожидания распределений <tex>p(t_n|x_1,\dots,x_n)</tex>, матрица типа double размера N x D; |
|- | |- | ||
- | | | + | |V — ковариационные матрицы распределений <tex>p(t_n|x_1,\dots,x_n)</tex>, массив типа double размера D x D x N; |
|- | |- | ||
|} | |} | ||
Строка 112: | Строка 124: | ||
{|class="standard" | {|class="standard" | ||
- | !''Обучение'' | + | !''Обучение с учителем для ЛДС'' |
|- | |- | ||
- | |[A | + | |[A, C, G, S] = LDS_train(X, T, ParameterName1, ParameterValue1, ParameterName2, ParameterValue2, ...) |
|- | |- | ||
|ВХОД | |ВХОД | ||
Строка 120: | Строка 132: | ||
| | | | ||
{| | {| | ||
- | |X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков; | + | |X — входная последовательность наблюдаемых переменных, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков; |
|- | |- | ||
- | | | + | |T — входная последовательность значений скрытых характеристик, матрица типа double размера N x D; |
|- | |- | ||
- | | | + | |(ParameterName, ParameterValue) — (необязательные аргументы) набор дополнительных параметров, возможны следующие названия параметров: |
|- | |- | ||
- | | 'A' — задаваемая пользователем матрица преобразования среднего в распределении <tex>p(t_n|t_{n-1})</tex>(соответственно, ее не нужно | + | | 'A' — задаваемая пользователем матрица преобразования среднего в распределении <tex>p(t_n|t_{n-1})</tex>(соответственно, ее не нужно вычислять внутри функции); |
+ | |- | ||
+ | | 'C' — задаваемая пользователем матрица преобразования среднего в распределении <tex>p(x_n|t_n)</tex>; | ||
|- | |- | ||
| 'G' — задаваемая пользователем матрица ковариации <tex>p(t_n|t_{n-1})</tex>; | | 'G' — задаваемая пользователем матрица ковариации <tex>p(t_n|t_{n-1})</tex>; | ||
- | |||
- | |||
|- | |- | ||
| 'S' — задаваемая пользователем матрица ковариации в распределении <tex>p(x_n|t_n)</tex>; | | 'S' — задаваемая пользователем матрица ковариации в распределении <tex>p(x_n|t_n)</tex>; | ||
|- | |- | ||
- | |||
- | |||
- | |||
|} | |} | ||
|- | |- | ||
Строка 145: | Строка 154: | ||
|- | |- | ||
|A — матрица преобразования среднего в последовательности <tex>t</tex>, матрица типа double размера D x D; | |A — матрица преобразования среднего в последовательности <tex>t</tex>, матрица типа double размера D x D; | ||
+ | |- | ||
+ | |C — матрица преобразования среднего при переходе от <tex>t_n</tex> к <tex>x_n</tex>, матрица типа double размера d x D; | ||
|- | |- | ||
|G — ковариационная матрица для распределения <tex>p(t_n|t_{n-1})</tex>, матрица типа double размера D x D; | |G — ковариационная матрица для распределения <tex>p(t_n|t_{n-1})</tex>, матрица типа double размера D x D; | ||
- | |||
- | |||
|- | |- | ||
|S — ковариационная матрица для распределения <tex>p(x_n|t_n)</tex>, матрица типа double размера d x d; | |S — ковариационная матрица для распределения <tex>p(x_n|t_n)</tex>, матрица типа double размера d x d; | ||
- | |||
- | |||
- | |||
- | |||
|- | |- | ||
|} | |} | ||
Строка 162: | Строка 167: | ||
{|class="standard" | {|class="standard" | ||
- | !''Генерация траектории'' | + | !''Генерация траектории объекта в двухмерном пространстве'' |
|- | |- | ||
|X = TRAJECTORY_GENERATE(N) | |X = TRAJECTORY_GENERATE(N) | ||
Строка 181: | Строка 186: | ||
|- | |- | ||
|X — сгенерированная траектория движения объекта в двухмерном пространстве, матрица типа double размера N x 2; | |X — сгенерированная траектория движения объекта в двухмерном пространстве, матрица типа double размера N x 2; | ||
+ | |- | ||
+ | |} | ||
+ | |} | ||
+ | |||
+ | | ||
+ | |||
+ | {|class="standard" | ||
+ | !''Генерация выборки для нелинейной динамической системы'' | ||
+ | |- | ||
+ | |[X, T] = EKF_generate(N, func_horiz, func_vert, G, S, mu0, V0) | ||
+ | |- | ||
+ | |ВХОД | ||
+ | |- | ||
+ | | | ||
+ | {|border="0" | ||
+ | |N — количество точек в генерируемой последовательности, uint32; | ||
+ | |- | ||
+ | |func_horiz — указатель на функцию <tex>f</tex>, сама функция должна возвращать две величины: значение и градиент; | ||
+ | |- | ||
+ | |func_vert — указатель на функция <tex>g</tex>, сама функция должна возвращать свое значение и градиент; | ||
+ | |- | ||
+ | |G — ковариационная матрица для распределения <tex>p(t_n|t_{n-1})</tex>, матрица типа double размера D x D; | ||
+ | |- | ||
+ | |S — ковариационная матрица для распределения <tex>p(x_n|t_n)</tex>, матрица типа double размера d x d; | ||
+ | |- | ||
+ | |mu0 — мат.ожидание априорного распределения <tex>p(t_1)</tex>, матрица типа double размера 1 x D; | ||
+ | |- | ||
+ | |V0 — ковариационная матрица априорного распределения <tex>p(t_1)</tex>, матрица типа double размера D x D. | ||
+ | |} | ||
+ | |- | ||
+ | |ВЫХОД | ||
+ | |- | ||
+ | | | ||
+ | {| | ||
+ | |X — сгенерированная наблюдаемая последовательность, матрица типа double размера N x d | ||
+ | |- | ||
+ | |T — последовательность скрытых характеристик, матрица типа double размера N x D | ||
+ | |} | ||
+ | |} | ||
+ | |||
+ | Обратите внимание: в процедуре EKF_generate параметры D и d определяются неявно по размеру соответствующих элементов. | ||
+ | |||
+ | {|class="standard" | ||
+ | !''Расширенный фильтр Калмана для нелинейной динамической системы'' | ||
+ | |- | ||
+ | |[M, V] = EKF_filter(X, func_horiz, func_vert, G, S, mu0, V0) | ||
+ | |- | ||
+ | |ВХОД | ||
+ | |- | ||
+ | | | ||
+ | {| | ||
+ | |X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков; | ||
+ | |- | ||
+ | |func_horiz — указатель на функцию <tex>f</tex>; | ||
+ | |- | ||
+ | |func_vert — указатель на функцию <tex>g</tex>; | ||
+ | |- | ||
+ | |G — ковариационная матрица для распределения <tex>p(t_n|t_{n-1})</tex>, матрица типа double размера D x D; | ||
+ | |- | ||
+ | |S — ковариационная матрица для распределения <tex>p(x_n|t_n)</tex>, матрица типа double размера d x d; | ||
+ | |- | ||
+ | |mu0 — мат.ожидание априорного распределения <tex>p(t_1)</tex>, матрица типа double размера 1 x D; | ||
+ | |- | ||
+ | |V0 — ковариационная матрица априорного распределения <tex>p(t_1)</tex>, матрица типа double размера D x D. | ||
+ | |- | ||
+ | |} | ||
+ | |- | ||
+ | |ВЫХОД | ||
+ | |- | ||
+ | | | ||
+ | {| | ||
+ | |M — мат. ожидания распределений <tex>p(t_n|x_1,\dots,x_n)</tex>, матрица типа double размера N x D; | ||
+ | |- | ||
+ | |V — ковариационные матрицы распределений <tex>p(t_n|x_1,\dots,x_n)</tex>, массив типа double размера D x D x N; | ||
|- | |- | ||
|} | |} |
Версия 11:53, 8 марта 2012
Внимание! Страница задания находится в стадии формирования. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено. |
Начало выполнения задания: 9 марта 2012
Срок сдачи: 21 марта 2012, 23:59
Среда реализации задания – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Формулировка задания
Рассматривается линейная динамическая система (ЛДС), в которой полное правдоподобие задается как:
Все переменные модели являются непрерывными, т.е. . Параметры модели .
Данную ЛДС нужно протестировать на модельной задаче сопровождения (трекинга) объекта в пространстве.
Рассматривается также нелинейная динамическая система с нормальным шумом, в которой вероятности переходов задаются как:
Здесь и — известные вектор-функции.
Для этой системы нужно реализовать расширенный фильтр Калмана и протестировать его работу на модельных данных.
Для выполнения задания необходимо:
- Реализовать алгоритм генерации выборки из вероятностной модели ЛДС и нелинейной ДС;
- Реализовать алгоритм онлайн фильтрации сигнала с помощью фильтра Калмана и с помощью расширенного фильтра Калмана;
- Реализовать обучение параметров ЛДС с учителем. При этом часть параметров ЛДС может быть задана пользователем;
- Реализовать алгоритм генерации траектории движения абстрактного объекта в двухмерном пространстве. Способ генерации такой траектории отдается на выбор студента;
- Протестировать реализованные алгоритмы на модельных данных;
- Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен, в частности, включать в себя графики фильтрации сгенерированных траекторий.
Спецификация реализуемых функций
Генерация выборки для ЛДС | |||||||
---|---|---|---|---|---|---|---|
[X, T] = LDS_generate(N, A, C, G, S, mu0, V0) | |||||||
ВХОД | |||||||
| |||||||
ВЫХОД | |||||||
|
Обратите внимание: в процедуре LDS_generate параметры D и d определяются неявно по размеру соответствующих элементов.
Фильтр Калмана для ЛДС | |||||||
---|---|---|---|---|---|---|---|
[M, V] = LDS_filter(X, A, C, G, S, mu0, V0) | |||||||
ВХОД | |||||||
| |||||||
ВЫХОД | |||||||
|
Обучение с учителем для ЛДС | |||||||
---|---|---|---|---|---|---|---|
[A, C, G, S] = LDS_train(X, T, ParameterName1, ParameterValue1, ParameterName2, ParameterValue2, ...) | |||||||
ВХОД | |||||||
| |||||||
ВЫХОД | |||||||
|
Генерация траектории объекта в двухмерном пространстве | |
---|---|
X = TRAJECTORY_GENERATE(N) | |
ВХОД | |
| |
ВЫХОД | |
|
Генерация выборки для нелинейной динамической системы | |||||||
---|---|---|---|---|---|---|---|
[X, T] = EKF_generate(N, func_horiz, func_vert, G, S, mu0, V0) | |||||||
ВХОД | |||||||
| |||||||
ВЫХОД | |||||||
|
Обратите внимание: в процедуре EKF_generate параметры D и d определяются неявно по размеру соответствующих элементов.
Расширенный фильтр Калмана для нелинейной динамической системы | |||||||
---|---|---|---|---|---|---|---|
[M, V] = EKF_filter(X, func_horiz, func_vert, G, S, mu0, V0) | |||||||
ВХОД | |||||||
| |||||||
ВЫХОД | |||||||
|
Рекомендации по выполнению задания
- При тестировании ЕМ-алгоритма обучения ЛДС рекомендуется убедиться в том, что значение неполного правдоподобия монотонно увеличивается в итерациях.
- Простейшим способом генерации траектории объекта является генерация по скорости и ускорению, где ускорение иногда меняет величину и направление.
- Один из вариантов тестирования реализованных алгоритмов на основе ЛДС следующий:
- Сгенерировать траекторию движения объекта
- Добавить к траектории случайный нормальный шум
- Отфильтровать зашумленную траекторию с помощью фильтра Калмана; убедиться, что отфильтрованный сигнал ближе к истинной траектории, чем входной зашумленный сигнал.
- Отфильтровать зашумленную траекторию с помощью РТС уравнений; убедиться, что результат является более точным по сравнению с фильтром Калмана.
- При тестировании генерации из модели ЛДС рекомендуется эксперимент с двухмерным сигналом, чтобы убедиться в корректности задаваемых корреляций
- Для наложения траектории движения на видео рекомендуется следующая процедура:
- Загрузить в MATLAB изображения с названиями поведенческих актов с помощью imread
- Небольшими блоками загружать в MATLAB кадры видео с помощью aviread, накладывать на них траекторию движения за последние 300 кадров и сохранять полученные кадры в виде отдельных JPG картинок на диск с помощью imwrite. Сохраненные картинки должны иметь название XXXXX.jpg, где XXXXX — номер кадра.
- Собрать полученные картинки в видео-файл с помощью бесплатной программы VirtualDub. Для этого достаточно открыть первую картинку в программе (остальные загрузятся автоматически), установить частоту кадров 25fps, установить кодек (рекомендуется DivX) и сгенерировать AVI-файл.
Оформление задания
Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 2. ФИО». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
- PDF-файл с описанием проведенных исследований
- LDS_generate.m
- LDS_filter.m
- LDS_train.m
- trajectory_generate.m
- Набор вспомогательных файлов при необходимости