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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Подсказки)
(+ Оформление задания для первого варианта)
Строка 177: Строка 177:
==== Оформление задания ====
==== Оформление задания ====
 +
 +
Архив, содержащий:
 +
*Readme.txt — файл с ФИО сдающего + комментарии по заданию
 +
*HMM_GENERATE.m
 +
*HMM_TEST.m
 +
*HMM_EM_TRAIN.m
 +
*Набор вспомогательных файлов при необходимости
=== Вариант 2 ===
=== Вариант 2 ===

Версия 16:56, 30 октября 2009

Статья в настоящий момент дорабатывается.
Д.А. Кропотов 14:18, 30 октября 2009 (MSK)


Содержание

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

Начало: 31 октября 2009

Срок сдачи: 15 ноября 2009

Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. здесь.

Среда реализации для всех вариантов – 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,\ldots,К}. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором w_1,\ldots,w_K, причем все w_i неотрицательны и в сумме дают единицу. Распределение 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.

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

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

Пояснения к варианту

При использовании стандартного алгоритма Витерби, описанного в лекциях легко показать, что априорное распределение на длительность l_j нахождения в состоянии j является геометрическим, т.е. вероятность находиться в этом состоянии ровно s моментов времени равна

p(l_j=s)=A_{jj}^s(1-A_{jj})

Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии j имеет вид 
p(l_j=s)=\left{\begin{array}{cc}0 & s\not\in\[a,b\]\\ A_{jj}^s\frac{1-A_{jj}}{1-A_{jj}^{b-a}} & s\in\[a,b\]\end{array}\right.

Иными словами, в одном состоянии СММ не может находиться меньше a моментов времни и больше b моментов времени. Частным случаем может быть a=0, b=+\infty. В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.

Подсказки

Первое. Вероятность перехода из состояния j в состоние j начинает зависеть от длительности s нахождения в состоянии j и равна 
p(t_{nj}|t_{n-1,j})=\frac{p(l_j>s)}{p(l_j>s-1)}

Обратите внимание, что если в качестве распределения на l_j использовалось бы геометрическое распределение, вероятность перехода не зависела бы от длительности нахождения в состоянии j и равнялась бы A_{jj}.

Тогда вероятности перехода между состояниями в силу условиях нормировки равны 
p(t_{ni}|t_{n-1,j})=A_{ji}\frac{1}{\sum_{k\ne j}A_{jk}+p(t_{nj}|t_{n-1,j})}

Здесь дополнительный множитель появился для того, чтобы обеспечить равенство 
\sum_{i=1}^K p(t_{ni}|t_{n-1,j})=1.

Эти условные вероятности теперь будут подставляться в функцию Белламана и в функцию S(t_{n,j}). Чтобы их корректно расчитать нам придется теперь дополнительно хранить информацию о том, сколько времени мы уже находимся в текущем состоянии (т.е. величину l_j для каждого t_{n,j}

--Vetrov 19:53, 30 октября 2009 (MSK)


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

Генерация выборки
[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, a, b)
ВХОД
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-ого состояния;
a — минимально возможная длина сегмента, uint16, если параметр не задан (=[] или число входных параметров = 5), то по умолчанию = 0
b — максимально возможная длина сегмента, uint16, если параметр не задан (=[] или число входных параметров <= 6), то по умолчанию = +inf
ВЫХОД
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-алгоритма;
  'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации;
ВЫХОД
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 – логарифм правдоподобия

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

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

  • Readme.txt — файл с ФИО сдающего + комментарии по заданию
  • HMM_GENERATE.m
  • HMM_TEST.m
  • HMM_EM_TRAIN.m
  • Набор вспомогательных файлов при необходимости

Вариант 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 )

Пусть скрытая компонента t_n в произвольный момент времени может принимать значения из множества {1,\ldots,К}. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором w_1,\ldots,w_K, причем все w_i неотрицательны и в сумме дают единицу. Распределение 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.

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

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

Пояснения к варианту

При решении задачи сегментации с помощью алгоритма Витерби предполагаются, что наблюдаемые данные подаются последовательно. Необходимо модифицировать алгоритм ВИтерби, чтобы он был способен провеодить сегментацию сигнала по имеющимся данным. Здесь используется следующее предположение: поступающие в текущий момент данные не влияют на сегментацию отдаленных участков сигнала в прошлом. Иными словами, каковы бы не были наблюдения, например, начиная с момента времени 100 и дальше, сегментация первых, скажем, 40 точек сигнала останется без изменений. Это позволяет нам провести окончательную сегментацию первых сорока точек сигнала, не дожидаясь получения всего объема данных, уже в сотый момент времени. По мере поступления новых данных граница окончательной сегментации (граница приятия решения) будет смещаться вправо.

Ваша задача для каждого момента времени определить на какой участок в прошлом новые наблюдения уже влияния не окажут и провести его сегментацию алгоритмом Витерби. При хорошо различимых состояниях задержка сегментации (разница между границей принятия решения и текущим моментом времени) будет незначительной.

Подсказки

Вариантом реализации такого алгоритма является прореживание таблицы функции S(t_{n,j}), содержащей аргмаксы функции Беллмана. Кладем S(t_{n,j})=0, если \not\exist i: S(t_{n+1},i)=j, т.е. если ни одна из оптимальных траекторий не проходит через t_{n,j}. В этом случае значения функции Беллмана и функции S для t_{n,j} интереса не представляют. В какой-то момент l окажется, что все S(t_{l,j})=0,\ \ j\ne j_0. Это и будет означать, что все оптимальные траектории проходят через состояние j_0 в момент времени l. Но тогда мы можем провести сегментацию всего сигнала до момента l включительно и очистить память, удалив массивы со значениями функции Беллмана и функции S от начала до момента времени l - сегментация на этом участке уже не изменится.

--Vetrov 17:43, 30 октября 2009 (MSK)

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

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

Вариант 3

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

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

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

Личные инструменты