Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2
Материал из MachineLearning.
Содержание |
Задание 2. Скрытые марковские модели.
Начало: 31 октября 2009
Срок сдачи: 15 ноября 2009
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. здесь. Тем, кто хочет выполнить это задание, но по каким-либо причинам не выполнял первое задание, нужно написать письмо и получить номер варианта.
Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Вариант 1
Формулировка задания
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества
. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором
, причем все
и
. Распределение
задается матрицей перехода
размера
, где в
-ой позиции стоит вероятность перехода из состояния
в состояние
. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания
и матрицы ковариации
для каждого состояния.
Таким образом, набор параметров модели определяется вектором
, матрицей
, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния
.
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ
- EM-алгоритм обучения СММ при заданном числе состояний K.
- Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, учитывающий заданное распределение на длительность нахождения в одном состоянии
Пояснения к варианту
При использовании стандартного алгоритма Витерби, описанного в лекциях, легко показать, что априорное распределение на длительность нахождения в состоянии
является геометрическим, т.е. вероятность находиться в этом состоянии ровно
моментов времени равна
Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии имеет вид
Иными словами, в одном состоянии СММ не может находиться меньше моментов времени и больше
моментов времени. Частным случаем может быть
,
. В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.
Подсказки
Вероятность перехода из состояния в состояние
начинает зависеть от длительности
нахождения в состоянии
и с точностью до нормировочного множителя равна
Обратите внимание, что если в качестве распределения на использовалось бы геометрическое распределение, вероятность перехода не зависела бы от длительности нахождения в состоянии
и равнялась бы
.
Тогда вероятности перехода между состояниями в силу условия нормировки равны
где — длительность нахождения в состоянии
к моменту времени
. Второй множитель здесь возникает из-за того, что мы точно знаем, какой длины был сегмент с
-ым состоянием (раз мы из него перешли в другое состояние, значит сегмент закончился).
Окончательно вероятности переходов рассчитываем
чтобы соблюсти условие нормировки
Эти условные вероятности теперь будут подставляться в функцию Беллмана и в функцию . Чтобы их корректно рассчитать, нам придется теперь дополнительно хранить информацию о том, сколько времени мы уже находимся в текущем состоянии (т.е. величину
для каждого
).
— Д.П. Ветров 19:53, 30 октября 2009 (MSK)
Спецификация реализуемых функций
Генерация выборки | |||||
---|---|---|---|---|---|
[X, T] = HMM_GENERATE(N, w, A, Mu, Sigmas) | |||||
ВХОД | |||||
| |||||
ВЫХОД | |||||
|
Обратите внимание: в процедуре HMM_GENERATE количество признаков и количество скрытых состояний определяются неявно по размеру соответствующих элементов.
Сегментация | |||||||
---|---|---|---|---|---|---|---|
T = HMM_TEST(X, w, A, Mu, Sigmas, a, b) | |||||||
ВХОД | |||||||
| |||||||
ВЫХОД | |||||||
|
Обучение | |||||||||
---|---|---|---|---|---|---|---|---|---|
[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K) | |||||||||
[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K, InputParameters) | |||||||||
ВХОД | |||||||||
| |||||||||
ВЫХОД | |||||||||
|
Оформление задания
Архив, содержащий:
- Readme.txt — файл с ФИО сдающего + комментарии по заданию
- HMM_GENERATE.m
- HMM_TEST.m
- HMM_EM_TRAIN.m
- Набор вспомогательных файлов при необходимости
Вариант 2
Формулировка задания
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества
. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором
, причем все
и
. Распределение
задается матрицей перехода
размера
, где в
-ой позиции стоит вероятность перехода из состояния
в состояние
. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания
и матрицы ковариации
для каждого состояния.
Таким образом, набор параметров модели определяется вектором
, матрицей
, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния
.
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ
- EM-алгоритм обучения СММ при заданном числе состояний K.
- Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, работающий в реальном времени.
Пояснения к варианту
При решении задачи сегментации с помощью алгоритма Витерби предполагается, что наблюдаемые данные поступают последовательно. Необходимо модифицировать алгоритм Витерби так, чтобы он был способен проводить сегментацию сигнала по имеющимся данным. Здесь используется следующее предположение: поступающие в текущий момент данные не влияют на сегментацию отдаленных участков сигнала в прошлом. Иными словами, каковы бы не были наблюдения, например, начиная с момента времени и дальше, сегментация первых, скажем,
точек сигнала останется без изменений. Это позволяет нам провести окончательную сегментацию первых сорока точек сигнала, не дожидаясь получения всего объема данных, уже в сотый момент времени. По мере поступления новых данных граница окончательной сегментации (граница принятия решения) будет смещаться вправо.
Задача: для каждого момента времени определить, на какой участок в прошлом новые наблюдения уже не оказывают влияния, и провести его сегментацию алгоритмом Витерби. При хорошо различимых состояниях задержка сегментации (разница между границей принятия решения и текущим моментом времени) будет незначительной.
Подсказки
Вариантом реализации такого алгоритма является прореживание таблицы функции , содержащей аргмаксы функции Беллмана. Кладем
, если
, т.е. если ни одна из оптимальных траекторий не проходит через
. В этом случае значения функции Беллмана и функции
для
интереса не представляют. В какой-то момент
окажется, что все
. Это и будет означать, что все оптимальные траектории проходят через состояние
в момент времени
. Но тогда мы можем провести сегментацию всего сигнала до момента
включительно и очистить память, удалив массивы со значениями функции Беллмана и функции
от начала до момента времени
- сегментация на этом участке уже не изменится.
--Vetrov 17:43, 30 октября 2009 (MSK)
Спецификация реализуемых функций
Генерация выборки | |||||
---|---|---|---|---|---|
[X, T] = HMM_GENERATE(N, w, A, Mu, Sigmas) | |||||
ВХОД | |||||
| |||||
ВЫХОД | |||||
|
Обратите внимание: в процедуре HMM_GENERATE количество признаков и количество скрытых состояний определяются неявно по размеру соответствующих элементов.
Сегментация | |||||
---|---|---|---|---|---|
[T, Borders] = HMM_TEST(X, w, A, Mu, Sigmas) | |||||
ВХОД | |||||
| |||||
ВЫХОД | |||||
|
Обучение | |||||||||
---|---|---|---|---|---|---|---|---|---|
[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K) | |||||||||
[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K, InputParameters) | |||||||||
ВХОД | |||||||||
| |||||||||
ВЫХОД | |||||||||
|
Оформление задания
Архив, содержащий:
- Readme.txt — файл с ФИО сдающего + комментарии по заданию
- HMM_GENERATE.m
- HMM_TEST.m
- HMM_EM_TRAIN.m
- Набор вспомогательных файлов при необходимости
Вариант 3
Формулировка задания
Рассматривается авторегрессионная скрытая марковская модель, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества
. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором
, причем все
и
. Распределение
задается матрицей перехода
размера
, где в
-ой позиции стоит вероятность перехода из состояния
в состояние
. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями с одинаковой матрицей ковариации
и своими математическими ожиданиями
для каждого состояния и каждого момента времени. Математическое ожидание зависит не только от состояния СММ, но и от предыдущих значений
(авторегрессионная составляющая) и задается формулой
где — коэффициенты авторегрессии, которые зависят от состояния СММ.
Таким образом, набор параметров модели определяется вектором , матрицей
, матрицей ковариаций
и матрицей
коэффициентов авторегрессии
Глубина авторегрессии
задается пользователем.
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ с авторегрессией;
- EM-алгоритм обучения СММ при заданном числе состояний
и глубине авторегрессии
;
- Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, учитывающий значения наблюдаемой компоненты
в предыдущие моменты времени.
Пояснения к заданию
Для подсчета авторегрессии в первые моменты времени вам понадобятся знания о значениях наблюдаемой компоненты в отрицательные моменты времени
. Считайте, что в них значение
равно среднему значению наблюдаемой компоненты, подсчитанному по всему сигналу. Обратите внимание на необходимость оценивания коэффициентов авторегрессии и сдвижки на М-шаге. Для получения аналитических формул вам придется выписать функцию правдоподобия, приравнять ее логарифм к нулю и выразить искомые величины.
Подсказки
Тут, собственно, подсказывать особенно и нечего. Отличие от того, что разобрано в лекциях, заключается в изменении функции и применении всех разобранных на лекциях алгоритмов. Подумайте, в каких местах нужна модификация формул из лекций, а в каких нет.
— Д.П. Ветров 21:16, 30 октября 2009 (MSK)
Спецификация реализуемых функций
Генерация выборки | ||||||
---|---|---|---|---|---|---|
[X, T] = ARHMM_GENERATE(N, w, A, Mu, Sigma, C) | ||||||
ВХОД | ||||||
| ||||||
ВЫХОД | ||||||
|
Обратите внимание: в процедуре ARHMM_GENERATE количество признаков, скрытых состояний и глубина авторегрессии определяются неявно по размеру соответствующих элементов.
Сегментация | ||||||
---|---|---|---|---|---|---|
T = ARHMM_TEST(X, w, A, Mu, Sigma, C) | ||||||
ВХОД | ||||||
| ||||||
ВЫХОД | ||||||
|
Обучение | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
[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) | |||||||||||
ВХОД | |||||||||||
| |||||||||||
ВЫХОД | |||||||||||
|
Оформление задания
Архив, содержащий:
- Readme.txt — файл с ФИО сдающего + комментарии по заданию
- ARHMM_GENERATE.m
- ARHMM_TEST.m
- ARHMM_EM_TRAIN.m
- Набор вспомогательных файлов при необходимости