Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2
Материал из MachineLearning.
м (Исправлены небольшие огрехи в спецификации функций для первого варианта) |
(→Подсказки) |
||
Строка 39: | Строка 39: | ||
==== Подсказки ==== | ==== Подсказки ==== | ||
- | + | Первое. Вероятность перехода из состояния <tex>j</tex> в состоние <tex>j</tex> начинает зависеть от длительности <tex>s</tex> нахождения в состоянии <tex>j</tex> и равна | |
+ | <tex> | ||
+ | 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> | ||
+ | p(t_{ni}|t_{n-1,j})=A_{ji}\frac{1}{\sum_{k\ne j}A_{jk}+p(t_{nj}|t_{n-1,j})} | ||
+ | </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|Vetrov]] 19:53, 30 октября 2009 (MSK) | ||
+ | |||
==== Спецификация реализуемых функций ==== | ==== Спецификация реализуемых функций ==== |
Версия 16:53, 30 октября 2009
![]() | Статья в настоящий момент дорабатывается. Д.А. Кропотов 14:18, 30 октября 2009 (MSK) |
Содержание |
Задание 2. Скрытые марковские модели.
Начало: 31 октября 2009
Срок сдачи: 15 ноября 2009
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. здесь.
Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Вариант 1
Формулировка задания
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества
. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором
, причем все
неотрицательны и в сумме дают единицу. Распределение
задается матрицей перехода
размера
, где в
-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания
и матрицы ковариации
для каждого состояния.
Таким образом, набор параметров модели определяется вектором
, матрицей
, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния
.
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ
- EM-алгоритм обучения СММ при заданном числе состояний K.
- Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, учитывающий заданное распределение на длительность нахождения в одном состоянии
Пояснения к варианту
При использовании стандартного алгоритма Витерби, описанного в лекциях легко показать, что априорное распределение на длительность нахождения в состоянии
является геометрическим, т.е. вероятность находиться в этом состоянии ровно
моментов времени равна
Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии имеет вид
Иными словами, в одном состоянии СММ не может находиться меньше моментов времни и больше
моментов времени. Частным случаем может быть
,
. В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.
Подсказки
Первое. Вероятность перехода из состояния в состоние
начинает зависеть от длительности
нахождения в состоянии
и равна
Обратите внимание, что если в качестве распределения на использовалось бы геометрическое распределение, вероятность перехода не зависела бы от длительности нахождения в состоянии
и равнялась бы
.
Тогда вероятности перехода между состояниями в силу условиях нормировки равны
Здесь дополнительный множитель появился для того, чтобы обеспечить равенство
Эти условные вероятности теперь будут подставляться в функцию Белламана и в функцию . Чтобы их корректно расчитать нам придется теперь дополнительно хранить информацию о том, сколько времени мы уже находимся в текущем состоянии (т.е. величину
для каждого
--Vetrov 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) | |||||||||
ВХОД | |||||||||
| |||||||||
ВЫХОД | |||||||||
|
Оформление задания
Вариант 2
Формулировка задания
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества
. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором
, причем все
неотрицательны и в сумме дают единицу. Распределение
задается матрицей перехода
размера
, где в
-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания
и матрицы ковариации
для каждого состояния.
Таким образом, набор параметров модели определяется вектором
, матрицей
, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния
.
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ
- EM-алгоритм обучения СММ при заданном числе состояний K.
- Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, работающий в реальном времени
Пояснения к варианту
При решении задачи сегментации с помощью алгоритма Витерби предполагаются, что наблюдаемые данные подаются последовательно. Необходимо модифицировать алгоритм ВИтерби, чтобы он был способен провеодить сегментацию сигнала по имеющимся данным. Здесь используется следующее предположение: поступающие в текущий момент данные не влияют на сегментацию отдаленных участков сигнала в прошлом. Иными словами, каковы бы не были наблюдения, например, начиная с момента времени и дальше, сегментация первых, скажем,
точек сигнала останется без изменений. Это позволяет нам провести окончательную сегментацию первых сорока точек сигнала, не дожидаясь получения всего объема данных, уже в сотый момент времени. По мере поступления новых данных граница окончательной сегментации (граница приятия решения) будет смещаться вправо.
Ваша задача для каждого момента времени определить на какой участок в прошлом новые наблюдения уже влияния не окажут и провести его сегментацию алгоритмом Витерби. При хорошо различимых состояниях задержка сегментации (разница между границей принятия решения и текущим моментом времени) будет незначительной.
Подсказки
Вариантом реализации такого алгоритма является прореживание таблицы функции , содержащей аргмаксы функции Беллмана. Кладем
, если
, т.е. если ни одна из оптимальных траекторий не проходит через
. В этом случае значения функции Беллмана и функции
для
интереса не представляют. В какой-то момент
окажется, что все
. Это и будет означать, что все оптимальные траектории проходят через состояние
в момент времени
. Но тогда мы можем провести сегментацию всего сигнала до момента
включительно и очистить память, удалив массивы со значениями функции Беллмана и функции
от начала до момента времени
- сегментация на этом участке уже не изменится.
--Vetrov 17:43, 30 октября 2009 (MSK)