Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2
Материал из MachineLearning.
(→Подсказки) |
(→Вариант 2) |
||
Строка 47: | Строка 47: | ||
=== Вариант 2 === | === Вариант 2 === | ||
==== Формулировка задания ==== | ==== Формулировка задания ==== | ||
+ | Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как: | ||
+ | <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> | ||
+ | |||
+ | Пусть скрытая компонента <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>\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>l</tex> окажется, что все <tex>S(t_{l,j})=0,\ \ j\ne 0</tex>. Это и будет означать, что '''все''' оптимальные траектории проходят через состояние <tex>j_0</tex> в момент времени <tex>l</tex>. Но тогда мы можем провести сегментацию всего сигнала до момента <tex>l</tex> вкллючительно и '''очистить память''', удалив массивы со значениями функции Беллмана и функции <tex>S</tex> от начала до момента времени <tex>l</tex> - сегментация на этом участке уже не изменится. | ||
==== Спецификация реализуемых функций ==== | ==== Спецификация реализуемых функций ==== | ||
==== Оформление задания ==== | ==== Оформление задания ==== |
Версия 14:40, 30 октября 2009
Статья в настоящий момент дорабатывается. Д.А. Кропотов 14:18, 30 октября 2009 (MSK) |
Содержание |
Задание 2. Скрытые марковские модели.
Начало: 31 октября 2009
Срок сдачи: 13 октября 2009
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. здесь.
Вариант 1
Формулировка задания
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества . Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором , причем все неотрицательны и в сумме дают единицу. Распределение задается матрицей перехода размера , где в -ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания и матрицы ковариации для каждого состояния. Таким образом, набор параметров модели определяется вектором , матрицей , значениями векторов математических ожиданий и матриц ковариаций для каждого состояния .
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ
- EM-алгоритм обучения СММ при заданном числе состояний K.
- Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, учитывающий заданное распределение на длительность нахождения в одном состоянии
Пояснения к варианту
При использовании стандартного алгоритма Витерби, описанного в лекциях легко показать, что априорное распределение на длительность нахождения в состоянии является геометрическим, т.е. вероятность находиться в этом состоянии ровно моментов времени равна
Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии имеет вид
Иными словами, в одном состоянии СММ не может находиться меньше моментов времни и больше моментов времени. Частным случаем может быть , . В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.
Подсказки
Будут, когда сам разберусь как такую задачу решать
Среда реализации – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Спецификация реализуемых функций
Оформление задания
Вариант 2
Формулировка задания
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества . Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором , причем все неотрицательны и в сумме дают единицу. Распределение задается матрицей перехода размера , где в -ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания и матрицы ковариации для каждого состояния. Таким образом, набор параметров модели определяется вектором , матрицей , значениями векторов математических ожиданий и матриц ковариаций для каждого состояния .
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ
- EM-алгоритм обучения СММ при заданном числе состояний K.
- Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, работающий в реальном времени
Пояснения к варианту
При решении задачи сегментации с помощью алгоритма Витерби предполагаются, что наблюдаемые данные подаются последовательно. Необходимо модифицировать алгоритм ВИтерби, чтобы он был способен провеодить сегментацию сигнала по имеющимся данным. Здесь используется следующее предположение: поступающие в текущий момент данные не влияют на сегментацию отдаленных участков сигнала в прошлом. Иными словами, каковы бы не были наблюдения, например, начиная с момента времени и дальше, сегментация первых, скажем, точек сигнала останется без изменений. Это позволяет нам провести окончательную сегментацию первых сорока точек сигнала, не дожидаясь получения всего объема данных, уже в сотый момент времени. По мере поступления новых данных граница окончательной сегментации (граница приятия решения) будет смещаться вправо.
Ваша задача для каждого момента времени определить на какой участок в прошлом новые наблюдения уже влияния не окажут и провести его сегментацию алгоритмом Витерби. При хорошо различимых состояниях задержка сегментации (разница между границей принятия решения и текущим моментом времени) будет незначительной.
Подсказки
Вариантом реализации такого алгоритма является прореживание таблицы функции , содержащей аргмаксы функции Беллмана. Кладем , если , т.е. если ни одна из оптимальных траекторий не проходит через . В этом случае соответствующие значения функции Беллмана и функции интереса не представляют. В какой-то момент окажется, что все . Это и будет означать, что все оптимальные траектории проходят через состояние в момент времени . Но тогда мы можем провести сегментацию всего сигнала до момента вкллючительно и очистить память, удалив массивы со значениями функции Беллмана и функции от начала до момента времени - сегментация на этом участке уже не изменится.