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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Подсказки)
(ссылка на основной курс, викификация)
 
(35 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
{{UnderConstruction|[[Участник:Kropotov|Д.А. Кропотов]] 14:18, 30 октября 2009 (MSK)}}
+
{{main|Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)}}
== Задание 2. Скрытые марковские модели. ==
== Задание 2. Скрытые марковские модели. ==
Строка 5: Строка 5:
Начало: 31 октября 2009
Начало: 31 октября 2009
-
Срок сдачи: {{ins|13 октября 2009}}
+
Срок сдачи: {{ins|15 ноября 2009}}
-
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. [[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)#Оценка за курс|здесь]].
+
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. [[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)#Оценка за курс|здесь]]. Тем, кто хочет выполнить это задание, но по каким-либо причинам не выполнял первое задание, нужно [[Служебная:EmailUser/Kropotov|написать письмо]] и получить номер варианта.
 +
 
 +
Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
=== Вариант 1 ===
=== Вариант 1 ===
==== Формулировка задания ====
==== Формулировка задания ====
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
 +
<center>
<tex>
<tex>
-
p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )</tex>
+
p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )
 +
</tex>
 +
</center>
-
Пусть скрытая компонента <tex>t_n</tex> в произвольный момент времени может принимать значения из множества <tex>{1,\ldots,К}</tex>. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором <tex>w_1,\ldots,w_K</tex>, причем все <tex>w_i</tex> неотрицательны и в сумме дают единицу. Распределение <tex>p(t_n |t_{n-1})</tex> задается матрицей перехода <tex>A</tex> размера <tex>K\times K</tex>, где в <tex>ij</tex>-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания <tex>\mu_i</tex> и матрицы ковариации <tex>\Sigma_i</tex> для каждого состояния.
+
Пусть скрытая компонента <tex>t_n</tex> в произвольный момент времени может принимать значения из множества <tex>\{1,\dots,K\}</tex>. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором <tex>w_1,\ldots,w_K</tex>, причем все <tex>w_i\ge 0</tex> и <tex>\sum_iw_i=1</tex>. Распределение <tex>p(t_n |t_{n-1})</tex> задается матрицей перехода <tex>A</tex> размера <tex>K\times K</tex>, где в <tex>ij</tex>-ой позиции стоит вероятность перехода из состояния <tex>i</tex> в состояние <tex>j</tex>. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания <tex>\mu_i</tex> и матрицы ковариации <tex>\Sigma_i</tex> для каждого состояния.
Таким образом, набор параметров модели определяется вектором <tex>\vec{w}</tex>, матрицей <tex>A</tex>, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния <tex>\{\mu_i,\Sigma_i\}_{i=1}^K</tex>.
Таким образом, набор параметров модели определяется вектором <tex>\vec{w}</tex>, матрицей <tex>A</tex>, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния <tex>\{\mu_i,\Sigma_i\}_{i=1}^K</tex>.
Строка 25: Строка 30:
==== Пояснения к варианту ====
==== Пояснения к варианту ====
-
При использовании стандартного алгоритма Витерби, описанного в лекциях легко показать, что априорное распределение на длительность <tex>l_j</tex> нахождения в состоянии <tex>j</tex> является геометрическим, т.е. вероятность находиться в этом состоянии ровно <tex>s</tex> моментов времени равна
+
При использовании стандартного алгоритма Витерби, описанного в лекциях, легко показать, что априорное распределение на длительность <tex>l_j</tex> нахождения в состоянии <tex>j</tex> является геометрическим, т.е. вероятность находиться в этом состоянии ровно <tex>s</tex> моментов времени равна
<tex>p(l_j=s)=A_{jj}^s(1-A_{jj})</tex>
<tex>p(l_j=s)=A_{jj}^s(1-A_{jj})</tex>
Строка 31: Строка 36:
Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии <tex>j</tex> имеет вид
Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии <tex>j</tex> имеет вид
<tex>
<tex>
-
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.
+
p(l_j=s)=\left{\begin{array}{cc}0, &\ s\not\in\[a,b\]\\ A_{jj}^{s-a}\frac{1-A_{jj}}{1-A_{jj}^{b-a+1}}, &\ s\in\[a,b\]\end{array}\right.
</tex>
</tex>
-
Иными словами, в одном состоянии СММ не может находиться меньше <tex>a</tex> моментов времни и больше <tex>b</tex> моментов времени. Частным случаем может быть <tex>a=0</tex>, <tex>b=+\infty</tex>. В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.
+
Иными словами, в одном состоянии СММ не может находиться меньше <tex>a</tex> моментов времени и больше <tex>b</tex> моментов времени. Частным случаем может быть <tex>a=1</tex>, <tex>b=+\infty</tex>. В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.
==== Подсказки ====
==== Подсказки ====
-
Будут, когда сам разберусь как такую задачу решать
+
Вероятность перехода из состояния <tex>j</tex> в состояние <tex>j</tex> начинает зависеть от длительности <tex>s</tex> нахождения в состоянии <tex>j</tex> и с точностью до нормировочного множителя равна
 +
<tex>
 +
\hat p(t_{nj}|t_{n-1,j})=\frac{p(l_j>s)}{p(l_j>s-1)}.
 +
</tex>
-
Среда реализации – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
+
''Обратите внимание, что если в качестве распределения на <tex>l_j</tex> использовалось бы геометрическое распределение, вероятность перехода '''не зависела''' бы от длительности нахождения в состоянии <tex>j</tex> и равнялась бы <tex>A_{jj}</tex>.
 +
''
 +
 
 +
Тогда вероятности перехода между состояниями в силу условия нормировки равны
 +
 
 +
<tex>
 +
\hat p(t_{ni}|t_{n-1,j})=A_{ji}\frac{p(l_j=s)}{p(l_j>s)},
 +
</tex>
 +
 
 +
где <tex>s</tex> — длительность нахождения в состоянии <tex>j</tex> к моменту времени <tex>n-1</tex>. Второй множитель здесь возникает из-за того, что мы точно знаем, какой длины был сегмент с <tex>j</tex>-ым состоянием (раз мы из него перешли в другое состояние, значит сегмент закончился).
 +
 
 +
Окончательно вероятности переходов рассчитываем
 +
 
 +
<tex>
 +
p(t_{ni}|t_{n-1,j})=\frac{\hat p(t_{ni}|t_{n-1,j})}{\sum_{k=1}^K \hat p(t_{nk}|t_{n-1,j})},\ \ \forall i=1,\dots,j,\ldots,K,
 +
</tex>
 +
 
 +
чтобы соблюсти условие нормировки
 +
<tex>
 +
\sum_{i=1}^K p(t_{ni}|t_{n-1,j})=1.
 +
</tex>
 +
 
 +
Эти условные вероятности теперь будут подставляться в функцию Беллмана и в функцию <tex>S(t_{n,j})</tex>. Чтобы их корректно рассчитать, нам придется теперь '''дополнительно''' хранить информацию о том, сколько времени мы уже находимся в текущем состоянии (т.е. величину <tex>l_j</tex> для каждого <tex>t_{n,j}</tex>).
 +
 
 +
— [[Участник:Dmitry Vetrov|Д.П. Ветров]] 19:53, 30 октября 2009 (MSK)
==== Спецификация реализуемых функций ====
==== Спецификация реализуемых функций ====
 +
 +
{|class="standard"
 +
!''Генерация выборки''
 +
|-
 +
|[X, T] = HMM_GENERATE(N, w, A, Mu, Sigmas)
 +
|-
 +
|ВХОД
 +
|-
 +
|
 +
{|border="0"
 +
|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 количество признаков и количество скрытых состояний определяются неявно по размеру соответствующих элементов.
 +
 +
{|class="standard"
 +
!''Сегментация''
 +
|-
 +
|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), то по умолчанию = 1
 +
|-
 +
|b — максимально возможная длина сегмента, uint16, если параметр не задан (=[] или число входных параметров <= 6), то по умолчанию = +inf
 +
|}
 +
|-
 +
|ВЫХОД
 +
|-
 +
|
 +
{|
 +
|T — полученная последовательность скрытых состояний, матрица типа double размера 1 x N
 +
|}
 +
|}
 +
 +
&nbsp;
 +
 +
{|class="standard"
 +
!''Обучение''
 +
|-
 +
|[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 и т.д. Возможны следующие параметры:
 +
|-
 +
|&nbsp;&nbsp;'w' — задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);
 +
|-
 +
|&nbsp;&nbsp;'A' — задаваемая пользователем матрица перехода;
 +
|-
 +
|&nbsp;&nbsp;'Mu' — задаваемые пользователем центры гауссиан для каждого состояния;
 +
|-
 +
|&nbsp;&nbsp;'Sigmas' — задаваемые пользователем матрицы ковариации гауссиан;
 +
|-
 +
|&nbsp;&nbsp;'num_iter' — максимально допустимое число итераций EM-алгоритма;
 +
|-
 +
|&nbsp;&nbsp;'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-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigmas', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия
 +
|}
 +
|}
 +
==== Оформление задания ====
==== Оформление задания ====
 +
 +
Архив, содержащий:
 +
*Readme.txt — файл с ФИО сдающего + комментарии по заданию
 +
*HMM_GENERATE.m
 +
*HMM_TEST.m
 +
*HMM_EM_TRAIN.m
 +
*Набор вспомогательных файлов при необходимости
=== Вариант 2 ===
=== Вариант 2 ===
==== Формулировка задания ====
==== Формулировка задания ====
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
 +
<center>
<tex>
<tex>
-
p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )</tex>
+
p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )
 +
</tex>
 +
</center>
-
Пусть скрытая компонента <tex>t_n</tex> в произвольный момент времени может принимать значения из множества <tex>{1,\ldots,К}</tex>. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором <tex>w_1,\ldots,w_K</tex>, причем все <tex>w_i</tex> неотрицательны и в сумме дают единицу. Распределение <tex>p(t_n |t_{n-1})</tex> задается матрицей перехода <tex>A</tex> размера <tex>K\times K</tex>, где в <tex>ij</tex>-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания <tex>\mu_i</tex> и матрицы ковариации <tex>\Sigma_i</tex> для каждого состояния.
+
Пусть скрытая компонента <tex>t_n</tex> в произвольный момент времени может принимать значения из множества <tex>\{1,\ldots,K\}</tex>. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором <tex>w_1,\ldots,w_K</tex>, причем все <tex>w_i\ge 0</tex> и <tex>\sum_iw_i=1</tex>. Распределение <tex>p(t_n |t_{n-1})</tex> задается матрицей перехода <tex>A</tex> размера <tex>K\times K</tex>, где в <tex>ij</tex>-ой позиции стоит вероятность перехода из состояния <tex>i</tex> в состояние <tex>j</tex>. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания <tex>\mu_i</tex> и матрицы ковариации <tex>\Sigma_i</tex> для каждого состояния.
Таким образом, набор параметров модели определяется вектором <tex>\vec{w}</tex>, матрицей <tex>A</tex>, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния <tex>\{\mu_i,\Sigma_i\}_{i=1}^K</tex>.
Таким образом, набор параметров модели определяется вектором <tex>\vec{w}</tex>, матрицей <tex>A</tex>, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния <tex>\{\mu_i,\Sigma_i\}_{i=1}^K</tex>.
Строка 57: Строка 212:
* Алгоритм генерации выборки из вероятностной модели СММ
* Алгоритм генерации выборки из вероятностной модели СММ
* EM-алгоритм обучения СММ при заданном числе состояний K.
* EM-алгоритм обучения СММ при заданном числе состояний K.
-
* Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, работающий в '''реальном времени'''
+
* Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, работающий в '''реальном времени'''.
==== Пояснения к варианту ====
==== Пояснения к варианту ====
-
При решении задачи сегментации с помощью алгоритма Витерби предполагаются, что наблюдаемые данные подаются последовательно. Необходимо модифицировать алгоритм ВИтерби, чтобы он был способен провеодить сегментацию сигнала по имеющимся данным. Здесь используется следующее предположение: поступающие в текущий момент данные не влияют на сегментацию отдаленных участков сигнала в прошлом. Иными словами, каковы бы не были наблюдения, например, начиная с момента времени <tex>100</tex> и дальше, сегментация первых, скажем, <tex>40</tex> точек сигнала останется без изменений. Это позволяет нам провести '''окончательную''' сегментацию первых сорока точек сигнала, не дожидаясь получения всего объема данных, уже в сотый момент времени. По мере поступления новых данных граница окончательной сегментации (граница приятия решения) будет смещаться вправо.
+
При решении задачи сегментации с помощью алгоритма Витерби предполагается, что наблюдаемые данные поступают последовательно. Необходимо модифицировать алгоритм Витерби так, чтобы он был способен проводить сегментацию сигнала по имеющимся данным. Здесь используется следующее предположение: поступающие в текущий момент данные не влияют на сегментацию отдаленных участков сигнала в прошлом. Иными словами, каковы бы не были наблюдения, например, начиная с момента времени <tex>100</tex> и дальше, сегментация первых, скажем, <tex>40</tex> точек сигнала останется без изменений. Это позволяет нам провести '''окончательную''' сегментацию первых сорока точек сигнала, не дожидаясь получения всего объема данных, уже в сотый момент времени. По мере поступления новых данных граница окончательной сегментации (граница принятия решения) будет смещаться вправо.
 +
 
 +
Задача: для каждого момента времени определить, на какой участок в прошлом новые наблюдения уже не оказывают влияния, и провести его сегментацию алгоритмом Витерби. При хорошо различимых состояниях задержка сегментации (разница между границей принятия решения и текущим моментом времени) будет незначительной.
-
Ваша задача для каждого момента времени определить на какой участок в прошлом новые наблюдения уже влияния не окажут и провести его сегментацию алгоритмом Витерби. При хорошо различимых состояниях задержка сегментации (разница между границей принятия решения и текущим моментом времени) будет незначительной.
 
==== Подсказки ====
==== Подсказки ====
Вариантом реализации такого алгоритма является прореживание таблицы функции <tex>S(t_{n,j})</tex>, содержащей аргмаксы функции Беллмана. Кладем <tex>S(t_{n,j})=0</tex>, если <tex>\not\exist i: S(t_{n+1},i)=j</tex>, т.е. если '''ни одна''' из оптимальных траекторий не проходит через <tex>t_{n,j}</tex>. В этом случае значения функции Беллмана и функции <tex>S</tex> для <tex>t_{n,j}</tex> интереса не представляют. В какой-то момент <tex>l</tex> окажется, что все <tex>S(t_{l,j})=0,\ \ j\ne j_0</tex>. Это и будет означать, что '''все''' оптимальные траектории проходят через состояние <tex>j_0</tex> в момент времени <tex>l</tex>. Но тогда мы можем провести сегментацию всего сигнала до момента <tex>l</tex> включительно и '''очистить память''', удалив массивы со значениями функции Беллмана и функции <tex>S</tex> от начала до момента времени <tex>l</tex> - сегментация на этом участке уже не изменится.
Вариантом реализации такого алгоритма является прореживание таблицы функции <tex>S(t_{n,j})</tex>, содержащей аргмаксы функции Беллмана. Кладем <tex>S(t_{n,j})=0</tex>, если <tex>\not\exist i: S(t_{n+1},i)=j</tex>, т.е. если '''ни одна''' из оптимальных траекторий не проходит через <tex>t_{n,j}</tex>. В этом случае значения функции Беллмана и функции <tex>S</tex> для <tex>t_{n,j}</tex> интереса не представляют. В какой-то момент <tex>l</tex> окажется, что все <tex>S(t_{l,j})=0,\ \ j\ne j_0</tex>. Это и будет означать, что '''все''' оптимальные траектории проходят через состояние <tex>j_0</tex> в момент времени <tex>l</tex>. Но тогда мы можем провести сегментацию всего сигнала до момента <tex>l</tex> включительно и '''очистить память''', удалив массивы со значениями функции Беллмана и функции <tex>S</tex> от начала до момента времени <tex>l</tex> - сегментация на этом участке уже не изменится.
 +
 +
--[[Участник:Dmitry Vetrov|Vetrov]] 17:43, 30 октября 2009 (MSK)
==== Спецификация реализуемых функций ====
==== Спецификация реализуемых функций ====
 +
 +
{|class="standard"
 +
!''Генерация выборки''
 +
|-
 +
|[X, T] = HMM_GENERATE(N, w, A, Mu, Sigmas)
 +
|-
 +
|ВХОД
 +
|-
 +
|
 +
{|border="0"
 +
|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 количество признаков и количество скрытых состояний определяются неявно по размеру соответствующих элементов.
 +
 +
{|class="standard"
 +
!''Сегментация''
 +
|-
 +
|[T, Borders] = 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
 +
|-
 +
|Borders — границы принятия решений при он-лайн сегментации, матрица типа double размера 2 x num_borders, каждая граница задается парой чисел - номер во входной последовательности и соответствующая ему правая граница сегментации в последовательности скрытых состояний T
 +
|}
 +
|}
 +
 +
&nbsp;
 +
 +
{|class="standard"
 +
!''Обучение''
 +
|-
 +
|[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 и т.д. Возможны следующие параметры:
 +
|-
 +
|&nbsp;&nbsp;'w' — задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);
 +
|-
 +
|&nbsp;&nbsp;'A' — задаваемая пользователем матрица перехода;
 +
|-
 +
|&nbsp;&nbsp;'Mu' — задаваемые пользователем центры гауссиан для каждого состояния;
 +
|-
 +
|&nbsp;&nbsp;'Sigmas' — задаваемые пользователем матрицы ковариации гауссиан;
 +
|-
 +
|&nbsp;&nbsp;'num_iter' — максимально допустимое число итераций EM-алгоритма;
 +
|-
 +
|&nbsp;&nbsp;'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-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigmas', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия
 +
|}
 +
|}
 +
==== Оформление задания ====
==== Оформление задания ====
 +
 +
Архив, содержащий:
 +
*Readme.txt — файл с ФИО сдающего + комментарии по заданию
 +
*HMM_GENERATE.m
 +
*HMM_TEST.m
 +
*HMM_EM_TRAIN.m
 +
*Набор вспомогательных файлов при необходимости
=== Вариант 3 ===
=== Вариант 3 ===
==== Формулировка задания ====
==== Формулировка задания ====
 +
Рассматривается авторегрессионная скрытая марковская модель, в которой полное правдоподобие задается как:
 +
<center>
 +
<tex>
 +
p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n,x_{n-1},\dots,x_{n-M} )
 +
</tex>
 +
</center>
 +
 +
Пусть скрытая компонента <tex>t_n</tex> в произвольный момент времени может принимать значения из множества <tex>\{1,\dots,K\}</tex>. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором <tex>w_1,\ldots,w_K</tex>, причем все <tex>w_i\ge 0</tex> и <tex>\sum_iw_i=1</tex>. Распределение <tex>p(t_n |t_{n-1})</tex> задается матрицей перехода <tex>A</tex> размера <tex>K\times K</tex>, где в <tex>ij</tex>-ой позиции стоит вероятность перехода из состояния <tex>i</tex> в состояние <tex>j</tex>. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями с одинаковой матрицей ковариации <tex>\Sigma</tex> и своими математическими ожиданиями <tex>\mu_{n,j}</tex> для каждого состояния и каждого момента времени. Математическое ожидание зависит не только от состояния СММ, но и '''от предыдущих значений''' <tex>x</tex> (авторегрессионная составляющая) и задается формулой
 +
 +
<tex>
 +
\mu_{n,j}=c_{0,j}+\sum_{m=1}^Mc_{m,j}x_{n-m},
 +
</tex>
 +
 +
где <tex>c_{0,j},\ldots,c_{M,j}</tex> — коэффициенты авторегрессии, которые зависят от состояния СММ.
 +
 +
Таким образом, набор параметров модели определяется вектором <tex>\vec{w}</tex>, матрицей <tex>A</tex>, матрицей ковариаций <tex>\Sigma</tex> и матрицей <tex>C</tex> коэффициентов авторегрессии <tex>\{c_{i,j}\}_{i=0,j=1}^{M,K}.</tex> Глубина авторегрессии <tex>M</tex> задается пользователем.
 +
 +
Для выполнения задания необходимо реализовать:
 +
* Алгоритм генерации выборки из вероятностной модели СММ с авторегрессией;
 +
* EM-алгоритм обучения СММ при заданном числе состояний <tex>K</tex> и глубине авторегрессии <tex>M</tex>;
 +
* Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, '''учитывающий''' значения наблюдаемой компоненты <tex>x</tex> в предыдущие моменты времени.
 +
 +
==== Пояснения к заданию ====
 +
Для подсчета авторегрессии в первые моменты времени вам понадобятся знания о значениях наблюдаемой компоненты <tex>x_n</tex> в отрицательные моменты времени <tex>-1,\ldots,-M+1</tex>. Считайте, что в них значение <tex>x</tex> равно среднему значению наблюдаемой компоненты, подсчитанному по всему сигналу. Обратите внимание на необходимость оценивания коэффициентов авторегрессии и сдвижки на М-шаге. Для получения аналитических формул вам придется выписать функцию правдоподобия, приравнять ее логарифм к нулю и выразить искомые величины.
 +
 +
==== Подсказки ====
 +
Тут, собственно, подсказывать особенно и нечего. Отличие от того, что разобрано в лекциях, заключается в изменении функции <tex>p(x_n|\phi_j)</tex> и применении всех разобранных на лекциях алгоритмов. Подумайте, в каких местах нужна модификация формул из лекций, а в каких нет.
 +
 +
— [[Участник:Dmitry Vetrov|Д.П. Ветров]] 21:16, 30 октября 2009 (MSK)
 +
==== Спецификация реализуемых функций ====
==== Спецификация реализуемых функций ====
 +
{|class="standard"
 +
!''Генерация выборки''
 +
|-
 +
|[X, T] = ARHMM_GENERATE(N, w, A, Mu, Sigma, C)
 +
|-
 +
|ВХОД
 +
|-
 +
|
 +
{|border="0"
 +
|N — количество точек в генерируемой последовательности, uint32;
 +
|-
 +
|w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
 +
|-
 +
|A — матрица перехода, матрица типа double размера K x K;
 +
|-
 +
|Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;
 +
|-
 +
|Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;
 +
|-
 +
|C — коэффициенты авторегрессии, матрица типа double размера K x M;
 +
|}
 +
|-
 +
|ВЫХОД
 +
|-
 +
|
 +
{|
 +
|X — сгенерированная последовательность, матрица типа double размера N x d
 +
|-
 +
|T — последовательность скрытых состояний, матрица типа double размера 1 x N
 +
|}
 +
|}
 +
 +
Обратите внимание: в процедуре ARHMM_GENERATE количество признаков, скрытых состояний и глубина авторегрессии определяются неявно по размеру соответствующих элементов.
 +
 +
{|class="standard"
 +
!''Сегментация''
 +
|-
 +
|T = ARHMM_TEST(X, w, A, Mu, Sigma, C)
 +
|-
 +
|ВХОД
 +
|-
 +
|
 +
{|
 +
|X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;
 +
|-
 +
|w — априорные вероятности, матрица типа double размера 1 x K, где K – количество скрытых состояний;
 +
|-
 +
|A — матрица перехода, матрица типа double размера K x K;
 +
|-
 +
|Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;
 +
|-
 +
|Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;
 +
|-
 +
|C — коэффициенты авторегрессии, матрица типа double размера K x M, где M — глубина авторегрессии;
 +
|}
 +
|-
 +
|ВЫХОД
 +
|-
 +
|
 +
{|
 +
|T — полученная последовательность скрытых состояний, матрица типа double размера 1 x N
 +
|}
 +
|}
 +
 +
&nbsp;
 +
 +
{|class="standard"
 +
!''Обучение''
 +
|-
 +
|[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)
 +
|-
 +
|ВХОД
 +
|-
 +
|
 +
{|
 +
|X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;
 +
|-
 +
|K — количество скрытых состояний, число типа uint16;
 +
|-
 +
|M — глубина авторегрессии, число типа uint16;
 +
|-
 +
|InputParameters — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
 +
|-
 +
|&nbsp;&nbsp;'w' — задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);
 +
|-
 +
|&nbsp;&nbsp;'A' — задаваемая пользователем матрица перехода;
 +
|-
 +
|&nbsp;&nbsp;'Mu' — задаваемые пользователем центры гауссиан для каждого состояния;
 +
|-
 +
|&nbsp;&nbsp;'Sigma' — задаваемая пользователем матрица ковариации гауссиан;
 +
|-
 +
|&nbsp;&nbsp;'C' — задаваемые пользователем коэффициенты авторегрессии;
 +
|-
 +
|&nbsp;&nbsp;'num_iter' — максимально допустимое число итераций EM-алгоритма;
 +
|-
 +
|&nbsp;&nbsp;'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации;
 +
|}
 +
|-
 +
|ВЫХОД
 +
|-
 +
|
 +
{|
 +
|w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
 +
|-
 +
|A — матрица перехода, матрица типа double размера K x K;
 +
|-
 +
|Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
 +
|-
 +
|Sigma — матрица ковариации гауссиан, массив типа double размера d x d;
 +
|-
 +
|C — коэффициенты авторегрессии, матрица типа double размера K x M;
 +
|-
 +
|Core — все параметры для всех итераций EM-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigma', 'C', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия
 +
|}
 +
|}
 +
==== Оформление задания ====
==== Оформление задания ====
 +
 +
Архив, содержащий:
 +
*Readme.txt — файл с ФИО сдающего + комментарии по заданию
 +
*ARHMM_GENERATE.m
 +
*ARHMM_TEST.m
 +
*ARHMM_EM_TRAIN.m
 +
*Набор вспомогательных файлов при необходимости
 +
 +
== Комментарии к заданию ==
 +
[[Media:SMAIS2009-task2-comments.pdf|PDF, 327Кб]]
 +
 +
== См. также ==
 +
* [http://courses.graphicon.ru/main/smisa2009 Страница курса на сайте лаборатории компьютерной графики и мультимедиа ВМиК МГУ]
 +
* [[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)|Курс «Структурные методы анализа изображений и сигналов»]]
 +
* [[Математические методы прогнозирования (кафедра ВМиК МГУ)]]
 +
 +
[[Категория:Учебные курсы]]
 +
[[Категория:Байесовские методы]]

Текущая версия

Содержание

Задание 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,\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.

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

  • Алгоритм генерации выборки из вероятностной модели СММ
  • 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-a}\frac{1-A_{jj}}{1-A_{jj}^{b-a+1}}, &\ s\in\[a,b\]\end{array}\right.

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

Подсказки

Вероятность перехода из состояния j в состояние j начинает зависеть от длительности s нахождения в состоянии j и с точностью до нормировочного множителя равна


\hat p(t_{nj}|t_{n-1,j})=\frac{p(l_j>s)}{p(l_j>s-1)}.

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

Тогда вероятности перехода между состояниями в силу условия нормировки равны


\hat p(t_{ni}|t_{n-1,j})=A_{ji}\frac{p(l_j=s)}{p(l_j>s)},

где s — длительность нахождения в состоянии j к моменту времени n-1. Второй множитель здесь возникает из-за того, что мы точно знаем, какой длины был сегмент с j-ым состоянием (раз мы из него перешли в другое состояние, значит сегмент закончился).

Окончательно вероятности переходов рассчитываем


p(t_{ni}|t_{n-1,j})=\frac{\hat p(t_{ni}|t_{n-1,j})}{\sum_{k=1}^K \hat p(t_{nk}|t_{n-1,j})},\ \ \forall i=1,\dots,j,\ldots,K,

чтобы соблюсти условие нормировки 
\sum_{i=1}^K p(t_{ni}|t_{n-1,j})=1.

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

Д.П. Ветров 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), то по умолчанию = 1
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-алгоритма, массив структур длины num_iter с полями '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,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.

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

  • Алгоритм генерации выборки из вероятностной модели СММ
  • 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)

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

Генерация выборки
[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, Borders] = 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
Borders — границы принятия решений при он-лайн сегментации, матрица типа double размера 2 x num_borders, каждая граница задается парой чисел - номер во входной последовательности и соответствующая ему правая граница сегментации в последовательности скрытых состояний T

 

Обучение
[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-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigmas', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия

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

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

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

Вариант 3

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

Рассматривается авторегрессионная скрытая марковская модель, в которой полное правдоподобие задается как:


p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n,x_{n-1},\dots,x_{n-M} )

Пусть скрытая компонента 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. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями с одинаковой матрицей ковариации \Sigma и своими математическими ожиданиями \mu_{n,j} для каждого состояния и каждого момента времени. Математическое ожидание зависит не только от состояния СММ, но и от предыдущих значений x (авторегрессионная составляющая) и задается формулой


\mu_{n,j}=c_{0,j}+\sum_{m=1}^Mc_{m,j}x_{n-m},

где c_{0,j},\ldots,c_{M,j} — коэффициенты авторегрессии, которые зависят от состояния СММ.

Таким образом, набор параметров модели определяется вектором \vec{w}, матрицей A, матрицей ковариаций \Sigma и матрицей C коэффициентов авторегрессии \{c_{i,j}\}_{i=0,j=1}^{M,K}. Глубина авторегрессии M задается пользователем.

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

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

Пояснения к заданию

Для подсчета авторегрессии в первые моменты времени вам понадобятся знания о значениях наблюдаемой компоненты x_n в отрицательные моменты времени -1,\ldots,-M+1. Считайте, что в них значение x равно среднему значению наблюдаемой компоненты, подсчитанному по всему сигналу. Обратите внимание на необходимость оценивания коэффициентов авторегрессии и сдвижки на М-шаге. Для получения аналитических формул вам придется выписать функцию правдоподобия, приравнять ее логарифм к нулю и выразить искомые величины.

Подсказки

Тут, собственно, подсказывать особенно и нечего. Отличие от того, что разобрано в лекциях, заключается в изменении функции p(x_n|\phi_j) и применении всех разобранных на лекциях алгоритмов. Подумайте, в каких местах нужна модификация формул из лекций, а в каких нет.

Д.П. Ветров 21:16, 30 октября 2009 (MSK)

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

Генерация выборки
[X, T] = ARHMM_GENERATE(N, w, A, Mu, Sigma, C)
ВХОД
N — количество точек в генерируемой последовательности, uint32;
w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
A — матрица перехода, матрица типа double размера K x K;
Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;
Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;
C — коэффициенты авторегрессии, матрица типа double размера K x M;
ВЫХОД
X — сгенерированная последовательность, матрица типа double размера N x d
T — последовательность скрытых состояний, матрица типа double размера 1 x N

Обратите внимание: в процедуре ARHMM_GENERATE количество признаков, скрытых состояний и глубина авторегрессии определяются неявно по размеру соответствующих элементов.

Сегментация
T = ARHMM_TEST(X, w, A, Mu, Sigma, C)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;
w — априорные вероятности, матрица типа double размера 1 x K, где K – количество скрытых состояний;
A — матрица перехода, матрица типа double размера K x K;
Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;
Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;
C — коэффициенты авторегрессии, матрица типа double размера K x M, где M — глубина авторегрессии;
ВЫХОД
T — полученная последовательность скрытых состояний, матрица типа double размера 1 x N

 

Обучение
[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)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;
K — количество скрытых состояний, число типа uint16;
M — глубина авторегрессии, число типа uint16;
InputParameters — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
  'w' — задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);
  'A' — задаваемая пользователем матрица перехода;
  'Mu' — задаваемые пользователем центры гауссиан для каждого состояния;
  'Sigma' — задаваемая пользователем матрица ковариации гауссиан;
  'C' — задаваемые пользователем коэффициенты авторегрессии;
  'num_iter' — максимально допустимое число итераций EM-алгоритма;
  'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации;
ВЫХОД
w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
A — матрица перехода, матрица типа double размера K x K;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigma — матрица ковариации гауссиан, массив типа double размера d x d;
C — коэффициенты авторегрессии, матрица типа double размера K x M;
Core — все параметры для всех итераций EM-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigma', 'C', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия

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

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

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

Комментарии к заданию

PDF, 327Кб

См. также

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