Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2
Материал из MachineLearning.
(Новая: {{UnderConstruction|~~~~}} == Задание 2. Скрытые марковские модели. == Начало: 31 октября 2009 Срок сдачи: 13 октября 2009 ...) |
(ссылка на основной курс, викификация) |
||
(42 промежуточные версии не показаны) | |||
Строка 1: | Строка 1: | ||
- | {{ | + | {{main|Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)}} |
== Задание 2. Скрытые марковские модели. == | == Задание 2. Скрытые марковские модели. == | ||
Строка 5: | Строка 5: | ||
Начало: 31 октября 2009 | Начало: 31 октября 2009 | ||
- | Срок сдачи: | + | Срок сдачи: {{ins|15 ноября 2009}} |
- | Задание состоит из трех вариантов. | + | Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. [[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)#Оценка за курс|здесь]]. Тем, кто хочет выполнить это задание, но по каким-либо причинам не выполнял первое задание, нужно [[Служебная:EmailUser/Kropotov|написать письмо]] и получить номер варианта. |
+ | |||
+ | Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке. | ||
=== Вариант 1 === | === Вариант 1 === | ||
+ | ==== Формулировка задания ==== | ||
+ | Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как: | ||
+ | <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 ) | ||
+ | </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>\mu_i</tex> и матрицы ковариации <tex>\Sigma_i</tex> для каждого состояния. | ||
+ | Таким образом, набор параметров модели определяется вектором <tex>\vec{w}</tex>, матрицей <tex>A</tex>, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния <tex>\{\mu_i,\Sigma_i\}_{i=1}^K</tex>. | ||
+ | |||
+ | Для выполнения задания необходимо реализовать: | ||
+ | * Алгоритм генерации выборки из вероятностной модели СММ | ||
+ | * EM-алгоритм обучения СММ при заданном числе состояний K. | ||
+ | * Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, '''учитывающий''' заданное распределение на длительность нахождения в одном состоянии | ||
+ | |||
+ | ==== Пояснения к варианту ==== | ||
+ | |||
+ | При использовании стандартного алгоритма Витерби, описанного в лекциях, легко показать, что априорное распределение на длительность <tex>l_j</tex> нахождения в состоянии <tex>j</tex> является геометрическим, т.е. вероятность находиться в этом состоянии ровно <tex>s</tex> моментов времени равна | ||
+ | |||
+ | <tex>p(l_j=s)=A_{jj}^s(1-A_{jj})</tex> | ||
+ | |||
+ | Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии <tex>j</tex> имеет вид | ||
+ | <tex> | ||
+ | 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>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> | ||
+ | |||
+ | ''Обратите внимание, что если в качестве распределения на <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 | ||
+ | |} | ||
+ | |} | ||
+ | |||
+ | | ||
+ | |||
+ | {|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 и т.д. Возможны следующие параметры: | ||
+ | |- | ||
+ | | '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 === | === Вариант 2 === | ||
+ | ==== Формулировка задания ==== | ||
+ | Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как: | ||
+ | <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 ) | ||
+ | </tex> | ||
+ | </center> | ||
+ | |||
+ | Пусть скрытая компонента <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>. | ||
+ | |||
+ | Для выполнения задания необходимо реализовать: | ||
+ | * Алгоритм генерации выборки из вероятностной модели СММ | ||
+ | * EM-алгоритм обучения СММ при заданном числе состояний K. | ||
+ | * Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, работающий в '''реальном времени'''. | ||
+ | |||
+ | ==== Пояснения к варианту ==== | ||
+ | При решении задачи сегментации с помощью алгоритма Витерби предполагается, что наблюдаемые данные поступают последовательно. Необходимо модифицировать алгоритм Витерби так, чтобы он был способен проводить сегментацию сигнала по имеющимся данным. Здесь используется следующее предположение: поступающие в текущий момент данные не влияют на сегментацию отдаленных участков сигнала в прошлом. Иными словами, каковы бы не были наблюдения, например, начиная с момента времени <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> - сегментация на этом участке уже не изменится. | ||
+ | |||
+ | --[[Участник: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 | ||
+ | |} | ||
+ | |} | ||
+ | |||
+ | | ||
+ | |||
+ | {|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 и т.д. Возможны следующие параметры: | ||
+ | |- | ||
+ | | '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 === | === Вариант 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 | ||
+ | |} | ||
+ | |} | ||
+ | |||
+ | | ||
+ | |||
+ | {|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 и т.д. Возможны следующие параметры: | ||
+ | |- | ||
+ | | '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 | ||
+ | *Набор вспомогательных файлов при необходимости | ||
+ | |||
+ | == Комментарии к заданию == | ||
+ | [[Media:SMAIS2009-task2-comments.pdf|PDF, 327Кб]] | ||
+ | |||
+ | == См. также == | ||
+ | * [http://courses.graphicon.ru/main/smisa2009 Страница курса на сайте лаборатории компьютерной графики и мультимедиа ВМиК МГУ] | ||
+ | * [[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)|Курс «Структурные методы анализа изображений и сигналов»]] | ||
+ | * [[Математические методы прогнозирования (кафедра ВМиК МГУ)]] | ||
+ | |||
+ | [[Категория:Учебные курсы]] | ||
+ | [[Категория:Байесовские методы]] |
Текущая версия
Содержание |
Задание 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
- Набор вспомогательных файлов при необходимости