Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2
Материал из MachineLearning.
(→Формулировка задания) |
(→Формулировка задания) |
||
Строка 12: | Строка 12: | ||
==== Формулировка задания ==== | ==== Формулировка задания ==== | ||
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как: | Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как: | ||
- | < | + | <tex> |
- | Пусть скрытая компонента в произвольный момент времени может принимать значения из множества {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 )</tex> |
- | Таким образом, набор параметров модели определяется вектором w, матрицей A, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния. | + | |
+ | Пусть скрытая компонента <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>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\frac{1-A_{jj}}{1-A_{jj}^{b-a}} & s\in\[a,b\]\end{array}\right. | ||
+ | </tex> | ||
+ | |||
+ | Иными словами, в одном состоянии СММ не может находиться меньше <tex>a</tex> моментов времни и больше <tex>b</tex> моментов времени. Частным случаем может быть <tex>a=0</tex>, <tex>b=+\infty</tex>. В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби. | ||
+ | |||
+ | ===== Подсказки ===== | ||
+ | |||
+ | |||
+ | |||
Среда реализации – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке. | Среда реализации – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке. | ||
Версия 14:04, 30 октября 2009
Статья в настоящий момент дорабатывается. Д.А. Кропотов 14:18, 30 октября 2009 (MSK) |
Содержание |
Задание 2. Скрытые марковские модели.
Начало: 31 октября 2009
Срок сдачи: 13 октября 2009
Задание состоит из трех вариантов. Распределение вариантов задания по студентам см. здесь.
Вариант 1
Формулировка задания
Рассматривается классическая скрытая марковская модель первого порядка, в которой полное правдоподобие задается как:
Пусть скрытая компонента в произвольный момент времени может принимать значения из множества . Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором , причем все неотрицательны и в сумме дают единицу. Распределение задается матрицей перехода размера , где в -ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания и матрицы ковариации для каждого состояния. Таким образом, набор параметров модели определяется вектором , матрицей , значениями векторов математических ожиданий и матриц ковариаций для каждого состояния .
Для выполнения задания необходимо реализовать:
- Алгоритм генерации выборки из вероятностной модели СММ
- EM-алгоритм обучения СММ при заданном числе состояний K.
- Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, учитывающий заданное распределение на длительность нахождения в одном состоянии
Пояснения к варианту
При использовании стандартного алгоритма Витерби, описанного в лекциях легко показать, что априорное распределение на длительность нахождения в состоянии является геометрическим, т.е. вероятность находиться в этом состоянии ровно моментов времени равна
Необходимо обобщить алгоритм Витерби на случай, когда априорное распределение на длительность нахождения в состоянии имеет вид
Иными словами, в одном состоянии СММ не может находиться меньше моментов времни и больше моментов времени. Частным случаем может быть , . В этом случае алгоритм сегментации должен давать результаты, аналогичные алгоритму Витерби.
Подсказки
Среда реализации – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.