Графические модели (курс лекций)/2013/Задание 3

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

(Различия между версиями)

Версия 19:44, 30 марта 2013

Основная статья: Графические модели (курс лекций)

Формулировка задания находится в стадии подготовки. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.

Начало выполнения задания: 18 марта 2013 г.;
Срок сдачи: 7 апреля 2013 г. (воскресенье), 23:59.

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

Содержание

1 Модель авторегрессии
2 Авторегрессионная скрытая марковская модель
3 Формулировка задания
4 Рекомендации по выполнению задания
5 Оформление задания

Модель авторегрессии

Случайный процесс с дискретным временем $\{\vec{x}_n\}_{n=1}^N$ , $\vec{x}_n\in\mathbb{R}^d$ называется авторегрессией первого порядка, если

$\vec{x}_n = \vec{w} + A\vec{x}_{n-1} + \vec{\varepsilon}_n,\quad \vec{\varepsilon}_n\sim\mathcal{N}(\vec{0},\Sigma)$ .

Здесь $\vec{w}\in\mathbb{R}^d$ , $A\in\mathbb{R}^{d\times d}$ , $\Sigma\in\mathbb{R}^{d\times d}$ , шумовые компоненты $\vec{\varepsilon}_n$ являются независимыми. Процесс авторегрессии является стационарным, если все собственные значения матрицы $A$ (включая комплексные) по модулю меньше единицы. Мат.ожидание $\vec{\mu}$ стационарного процесса авторегрессии определяется как

$\vec{\mu} = (I-A)^{-1}\vec{w}$ ,

где $I$ — единичная матрица размера $d\times d$ .

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

$p(X|\vec{w},A,\Sigma,\vec{x}_0)=\prod_{n=1}^N\mathcal{N}(\vec{x}_n|\vec{w}+A\vec{x}_{n-1},\Sigma)$ ,

а $\vec{x}_0$ — начальная предыстория.

Авторегрессия M-го порядка задается как

$\vec{x}_n = \vec{w}+\sum_{m=1}^MA_m\vec{x}_{n-m}+ \vec{\varepsilon}_n,\quad \vec{\varepsilon}_n\sim\mathcal{N}(\vec{0},\Sigma)$ .

Здесь шумовые компоненты $\vec{\varepsilon}_n$ по-прежнему предполагаются независимыми. Очевидно, что авторегрессия M-го порядка может быть сведена к авторегрессии первого порядка как

$\tilde{\vec{x}}_n = \tilde{\vec{w}} + \tilde{A}\tilde{\vec{x}}_{n-1} + \tilde{\vec{\varepsilon}}_n,\quad \tilde{\vec{w}} = \begin{bmatrix}\vec{w}\\ 0\\ \vdots \\ 0\end{bmatrix},\quad \tilde{\vec{x}}_n = \begin{bmatrix}\vec{x}_n\\ \vec{x}_{n-1}\\ \vdots \\ \vec{x}_{n-M}\end{bmatrix},\quad \tilde{A} = \begin{bmatrix}A_1 & A_2 & A_3 & \dots & A_{M-1} & A_M\\ I & 0 & 0 & \dots & 0 & 0\\ 0 & I & 0 & \dots & 0 & 0\\ \dots \\ 0 & 0 & 0 & \dots & I & 0 \end{bmatrix},\quad \tilde{\vec{\varepsilon}}_n = \begin{bmatrix}\vec{\varepsilon}_n \\ 0 \\ \vdots \\ 0\end{bmatrix}.$

Поэтому авторегрессия M-го порядка является стационарной, если все собственные значения матрицы $\tilde{A}$ по модулю меньше единицы. Мат.ожидание стационарной регрессии M-го порядка определяется как

$\vec{\mu} = (I-A_1-\dots-A_M)^{-1}\vec{w}$ .

Авторегрессионная скрытая марковская модель

Рассматривается авторегрессионная скрытая марковская модель, в которой полное правдоподобие задается как:

$p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n,x_{n-1},\dots,x_{n-M} )$

Пусть скрытая компонента $t_n$ в произвольный момент времени может принимать значения из множества $\{1,\dots,K\}$ . Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором $w_1,\ldots,w_K$ , причем все $w_i\ge 0$ и $\sum_iw_i=1$ . Распределение $p(t_n |t_{n-1})$ задается матрицей перехода $A$ размера $K\times K$ , где в $ij$ -ой позиции стоит вероятность перехода из состояния $i$ в состояние $j$ . Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями с одинаковой матрицей ковариации $\Sigma$ и своими математическими ожиданиями $\mu_{n,j}$ для каждого состояния и каждого момента времени. Математическое ожидание зависит не только от состояния СММ, но и от предыдущих значений $x$ (авторегрессионная составляющая) и задается формулой

$\mu_{n,j}=c_{0,j}+\sum_{m=1}^Mc_{m,j}x_{n-m},$

где $c_{0,j},\ldots,c_{M,j}$ — коэффициенты авторегрессии, которые зависят от состояния СММ.

Таким образом, набор параметров модели определяется вектором $\vec{w}$ , матрицей $A$ , матрицей ковариаций $\Sigma$ и матрицей $C$ коэффициентов авторегрессии $\{c_{i,j}\}_{i=0,j=1}^{M,K}.$ Глубина авторегрессии $M$ задается пользователем.

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

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

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

Выполненное задание следует отправить письмом по адресу bayesml@gmail.com с заголовком письма «[ГМ13] Задание 3 <ФИО>». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Также убедительная просьба строго придерживаться заданных ниже прототипов реализуемых функций.

Присланный вариант задания должен содержать в себе:

Файл отчёта в формате PDF с указанием ФИО.
Все исходные коды с необходимыми комментариями.

Генерация выборки

[X, T] = ARHMM_GENERATE(N, w, A, Mu, Sigma, C)

ВХОД

N — количество точек в генерируемой последовательности, uint32;

w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;

A — матрица перехода, матрица типа double размера K x K;

Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;

Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;

C — коэффициенты авторегрессии, матрица типа double размера K x M;

ВЫХОД

X — сгенерированная последовательность, матрица типа double размера N x d

T — последовательность скрытых состояний, матрица типа double размера 1 x N

Обратите внимание: в процедуре ARHMM_GENERATE количество признаков, скрытых состояний и глубина авторегрессии определяются неявно по размеру соответствующих элементов.

Сегментация

T = ARHMM_TEST(X, w, A, Mu, Sigma, C)

ВХОД

X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;

w — априорные вероятности, матрица типа double размера 1 x K, где K – количество скрытых состояний;

A — матрица перехода, матрица типа double размера K x K;

Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;

C — коэффициенты авторегрессии, матрица типа double размера K x M, где M — глубина авторегрессии;

ВЫХОД

T — полученная последовательность скрытых состояний, матрица типа double размера 1 x N

Обучение

[w, A, Mu, Sigma, C, core] = ARHMM_EM_TRAIN(X, K, M)

[w, A, Mu, Sigma, C, core] = ARHMM_EM_TRAIN(X, K, M, InputParameters)

ВХОД

X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;

K — количество скрытых состояний, число типа uint16;

M — глубина авторегрессии, число типа uint16;

InputParameters — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:

'w' — задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);

'A' — задаваемая пользователем матрица перехода;

'Mu' — задаваемые пользователем центры гауссиан для каждого состояния;

'Sigma' — задаваемая пользователем матрица ковариации гауссиан;

'C' — задаваемые пользователем коэффициенты авторегрессии;

'num_iter' — максимально допустимое число итераций EM-алгоритма;

'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации;

ВЫХОД

w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;

A — матрица перехода, матрица типа double размера K x K;

Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;

Sigma — матрица ковариации гауссиан, массив типа double размера d x d;

C — коэффициенты авторегрессии, матрица типа double размера K x M;

Core — все параметры для всех итераций EM-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigma', 'C', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29/2013/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_3»

Категория: Учебные курсы

@@ Строка 8: / Строка 8: @@
 Среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
-==== Формулировка задания ====
+== Модель авторегрессии ==
+Случайный процесс с дискретным временем <tex>\{\vec{x}_n\}_{n=1}^N</tex>, <tex>\vec{x}_n\in\mathbb{R}^d</tex> называется ''авторегрессией первого порядка'', если
+:<tex>\vec{x}_n = \vec{w} + A\vec{x}_{n-1} + \vec{\varepsilon}_n,\quad \vec{\varepsilon}_n\sim\mathcal{N}(\vec{0},\Sigma)</tex>.
+Здесь <tex>\vec{w}\in\mathbb{R}^d</tex>, <tex>A\in\mathbb{R}^{d\times d}</tex>, <tex>\Sigma\in\mathbb{R}^{d\times d}</tex>, шумовые компоненты <tex>\vec{\varepsilon}_n</tex> являются независимыми. Процесс авторегрессии является стационарным, если все собственные значения матрицы <tex>A</tex> (включая комплексные) по модулю меньше единицы. Мат.ожидание <tex>\vec{\mu}</tex> стационарного процесса авторегрессии определяется как
+:<tex>\vec{\mu} = (I-A)^{-1}\vec{w}</tex>,
+где <tex>I</tex>&nbsp;— единичная матрица размера <tex>d\times d</tex>.
+В терминах графических моделей авторегрессия первого порядка представляет собой байесовскую сеть с графом вида цепочка (см. рис.), где совместное распределение задается как
+:<tex>p(X|\vec{w},A,\Sigma,\vec{x}_0)=\prod_{n=1}^N\mathcal{N}(\vec{x}_n|\vec{w}+A\vec{x}_{n-1},\Sigma)</tex>,
+а <tex>\vec{x}_0</tex> — начальная предыстория.
+''Авторегрессия M-го порядка'' задается как
+:<tex>\vec{x}_n = \vec{w}+\sum_{m=1}^MA_m\vec{x}_{n-m}+ \vec{\varepsilon}_n,\quad \vec{\varepsilon}_n\sim\mathcal{N}(\vec{0},\Sigma)</tex>.
+Здесь шумовые компоненты <tex>\vec{\varepsilon}_n</tex> по-прежнему предполагаются независимыми. Очевидно, что авторегрессия M-го порядка может быть сведена к авторегрессии первого порядка как
+:<tex>\tilde{\vec{x}}_n = \tilde{\vec{w}} + \tilde{A}\tilde{\vec{x}}_{n-1} + \tilde{\vec{\varepsilon}}_n,\quad \tilde{\vec{w}} = \begin{bmatrix}\vec{w}\\ 0\\ \vdots \\ 0\end{bmatrix},\quad \tilde{\vec{x}}_n = \begin{bmatrix}\vec{x}_n\\ \vec{x}_{n-1}\\ \vdots \\ \vec{x}_{n-M}\end{bmatrix},\quad \tilde{A} = \begin{bmatrix}A_1 & A_2 & A_3 & \dots & A_{M-1} & A_M\\ I & 0 & 0 & \dots & 0 & 0\\ 0 & I & 0 & \dots & 0 & 0\\ \dots \\ 0 & 0 & 0 & \dots & I & 0 \end{bmatrix},\quad \tilde{\vec{\varepsilon}}_n = \begin{bmatrix}\vec{\varepsilon}_n \\ 0 \\ \vdots \\ 0\end{bmatrix}.</tex>
+Поэтому авторегрессия M-го порядка является стационарной, если все собственные значения матрицы <tex>\tilde{A}</tex> по модулю меньше единицы. Мат.ожидание стационарной регрессии M-го порядка определяется как
+:<tex>\vec{\mu} = (I-A_1-\dots-A_M)^{-1}\vec{w}</tex>.
+== Авторегрессионная скрытая марковская модель ==
 Рассматривается авторегрессионная скрытая марковская модель, в которой полное правдоподобие задается как:
 <center>
@@ Строка 26: / Строка 57: @@
 Таким образом, набор параметров модели определяется вектором <tex>\vec{w}</tex>, матрицей <tex>A</tex>, матрицей ковариаций <tex>\Sigma</tex> и матрицей <tex>C</tex> коэффициентов авторегрессии <tex>\{c_{i,j}\}_{i=0,j=1}^{M,K}.</tex> Глубина авторегрессии <tex>M</tex> задается пользователем.
-Для выполнения задания необходимо реализовать:
+== Формулировка задания ==
 * Алгоритм генерации выборки из вероятностной модели СММ с авторегрессией;
 * EM-алгоритм обучения СММ при заданном числе состояний <tex>K</tex> и глубине авторегрессии <tex>M</tex>;
 * Алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ, '''учитывающий''' значения наблюдаемой компоненты <tex>x</tex> в предыдущие моменты времени.
-==== Пояснения к заданию ====
+== Рекомендации по выполнению задания ==
-Для подсчета авторегрессии в первые моменты времени вам понадобятся знания о значениях наблюдаемой компоненты <tex>x_n</tex> в отрицательные моменты времени <tex>-1,\ldots,-M+1</tex>. Считайте, что в них значение <tex>x</tex> равно среднему значению наблюдаемой компоненты, подсчитанному по всему сигналу. Обратите внимание на необходимость оценивания коэффициентов авторегрессии и сдвижки на М-шаге. Для получения аналитических формул вам придется выписать функцию правдоподобия, приравнять ее логарифм к нулю и выразить искомые величины.
-==== Оформление задания ====
+== Оформление задания ==
 Выполненное задание следует отправить письмом по адресу ''bayesml@gmail.com'' с заголовком письма «[ГМ13] Задание 3 <ФИО>». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Также убедительная просьба строго придерживаться заданных ниже прототипов реализуемых функций.

Графические модели (курс лекций)/2013/Задание 3

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

Версия 19:44, 30 марта 2013

Содержание

Модель авторегрессии

Авторегрессионная скрытая марковская модель

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

Рекомендации по выполнению задания

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

Просмотры

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

Навигация

Поиск

Инструменты