Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2
Материал из MachineLearning.
(→Подсказки) |
(+ Спецификация функций для второго варианта) |
||
Строка 222: | Строка 222: | ||
==== Спецификация реализуемых функций ==== | ==== Спецификация реализуемых функций ==== | ||
+ | |||
+ | {|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 – логарифм правдоподобия | ||
+ | |} | ||
+ | |} | ||
+ | |||
==== Оформление задания ==== | ==== Оформление задания ==== | ||
Версия 17:35, 30 октября 2009
Статья в настоящий момент дорабатывается. Д.А. Кропотов 14:18, 30 октября 2009 (MSK) |
Содержание |
Задание 2. Скрытые марковские модели.
Начало: 31 октября 2009
Срок сдачи: 15 ноября 2009
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. здесь.
Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Вариант 1
Формулировка задания
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества . Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором , причем все и . Распределение задается матрицей перехода размера , где в -ой позиции стоит вероятность перехода из состояния в состояние . Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания и матрицы ковариации для каждого состояния. Таким образом, набор параметров модели определяется вектором , матрицей , значениями векторов математических ожиданий и матриц ковариаций для каждого состояния .
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ
- 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) | |||||||||
ВХОД | |||||||||
| |||||||||
ВЫХОД | |||||||||
|
Оформление задания
Архив, содержащий:
- 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) | |||||||||
ВХОД | |||||||||
| |||||||||
ВЫХОД | |||||||||
|