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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Подсказки)
(Задание 2. Скрытые марковские модели.)
Строка 5: Строка 5:
Начало: 31 октября 2009
Начало: 31 октября 2009
-
Срок сдачи: {{ins|13 октября 2009}}
+
Срок сдачи: {{ins|13 ноября 2009}}
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. [[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)#Оценка за курс|здесь]].
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. [[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)#Оценка за курс|здесь]].

Версия 14:55, 30 октября 2009

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


Содержание

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

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

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

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

Вариант 1

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

Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как: 
p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )

Пусть скрытая компонента t_n в произвольный момент времени может принимать значения из множества {1,\ldots,К}. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором w_1,\ldots,w_K, причем все w_i неотрицательны и в сумме дают единицу. Распределение p(t_n |t_{n-1}) задается матрицей перехода A размера K\times K, где в ij-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания \mu_i и матрицы ковариации \Sigma_i для каждого состояния. Таким образом, набор параметров модели определяется вектором \vec{w}, матрицей A, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния \{\mu_i,\Sigma_i\}_{i=1}^K.

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

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

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

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

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

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

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

Подсказки

Будут, когда сам разберусь как такую задачу решать


Среда реализации – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.

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

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

Вариант 2

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

Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как: 
p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )

Пусть скрытая компонента t_n в произвольный момент времени может принимать значения из множества {1,\ldots,К}. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором w_1,\ldots,w_K, причем все w_i неотрицательны и в сумме дают единицу. Распределение p(t_n |t_{n-1}) задается матрицей перехода A размера K\times K, где в ij-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания \mu_i и матрицы ковариации \Sigma_i для каждого состояния. Таким образом, набор параметров модели определяется вектором \vec{w}, матрицей A, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния \{\mu_i,\Sigma_i\}_{i=1}^K.

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

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

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

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

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

Подсказки

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

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

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

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

Вариант 3

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

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

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

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