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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Оформление задания)
Строка 92: Строка 92:
* Файл отчёта в формате PDF с указанием ФИО.
* Файл отчёта в формате PDF с указанием ФИО.
* Все исходные коды с необходимыми комментариями.
* Все исходные коды с необходимыми комментариями.
 +
 +
 
{|class="standard"
{|class="standard"
-
!''Генерация выборки''
+
!''Генерация выборки из модели авторегрессии''
|-
|-
-
|[X, T] = ARHMM_GENERATE(N, w, A, Mu, Sigma, C)
+
|X = '''ar_generate'''(N, w, A, Sigma, X0)
|-
|-
|ВХОД
|ВХОД
Строка 102: Строка 104:
|
|
{|border="0"
{|border="0"
-
|N — количество точек в генерируемой последовательности, uint32;
+
|N — количество точек в генерируемой последовательности, число;
|-
|-
-
|w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
+
|w — параметр сдвига, вектор длины d;
|-
|-
-
|A — матрица перехода, матрица типа double размера K x K;
+
|A — набор матриц в форме <tex>[A_1\ A_2\ \dots\ A_M]</tex>, матрица размера d x Md;
|-
|-
-
|Mu константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;
+
|Sigma матрица ковариации для нормального шума, матрица размера d x d;
|-
|-
-
|Sigma общая матрица ковариации гауссиан, матрица типа double размера d x d;
+
|X0 (необязательный параметр) начальная предыстория, матрица размера M x d;
-
|-
+
-
|C — коэффициенты авторегрессии, матрица типа double размера K x M;
+
|}
|}
|-
|-
Строка 119: Строка 119:
|
|
{|
{|
-
|X — сгенерированная последовательность, матрица типа double размера N x d
+
|X — сгенерированная последовательность, матрица размера N x d.
|-
|-
-
|T — последовательность скрытых состояний, матрица типа double размера 1 x N
 
|}
|}
|}
|}
-
Обратите внимание: в процедуре ARHMM_GENERATE количество признаков, скрытых состояний и глубина авторегрессии определяются неявно по размеру соответствующих элементов.
+
Если начальная предыстория <tex>X_0</tex> не задана, то <tex>X_0</tex> выбирается равной мат.ожиданию процесса авторегрессии.
{|class="standard"
{|class="standard"
-
!''Сегментация''
+
!''Оценка параметров авторегрессии''
|-
|-
-
|T = ARHMM_TEST(X, w, A, Mu, Sigma, C)
+
|[w, A, Sigma, res, LH] = '''ar_fit'''(X, M)
|-
|-
|ВХОД
|ВХОД
Строка 136: Строка 135:
|
|
{|
{|
-
|X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;
+
|X — наблюдаемая последовательность, матрица размера N x d, первые M строк соответствуют начальной предыстории;
|-
|-
-
|w априорные вероятности, матрица типа double размера 1 x K, где K – количество скрытых состояний;
+
|M глубина авторегрессии, число;
-
|-
+
-
|A — матрица перехода, матрица типа double размера K x K;
+
|-
|-
-
|Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния;
 
-
|-
 
-
|Sigma — общая матрица ковариации гауссиан, матрица типа double размера d x d;
 
-
|-
 
-
|C — коэффициенты авторегрессии, матрица типа double размера K x M, где M — глубина авторегрессии;
 
|}
|}
|-
|-
Строка 153: Строка 145:
|
|
{|
{|
-
|T полученная последовательность скрытых состояний, матрица типа double размера 1 x N
+
|w параметр сдвига авторегрессии, вектор длины d;
 +
|-
 +
|A — набор матриц в форме <tex>[A_1\ A_2\ \dots\ A_M]</tex>, матрица размера d x Md;
 +
|-
 +
|Sigma — матрица ковариации нормального шума, матрица размера d x d;
 +
|-
 +
|res — остатки авторегрессии (набор векторов <tex>\vec{x}_n-\vec{w}-\sum_{m=1}^MA_m\vec{x}_{n-m}</tex>), матрица размера (N-M) x d;
 +
|-
 +
|LH — логарифм правдоподобия настроенной модели авторегрессии, число.
|}
|}
|}
|}
Строка 160: Строка 160:
{|class="standard"
{|class="standard"
-
!''Обучение''
+
!''Генерация выборки из авторегрессионной скрытой марковской модели''
|-
|-
-
|[w, A, Mu, Sigma, C, core] = ARHMM_EM_TRAIN(X, K, M)
+
|[X, T] = '''arhmm_generate'''(N, p, R, W, A, Sigmas, X0)
-
|-
+
-
|[w, A, Mu, Sigma, C, core] = ARHMM_EM_TRAIN(X, K, M, InputParameters)
+
|-
|-
|ВХОД
|ВХОД
Строка 170: Строка 168:
|
|
{|
{|
-
|X входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;
+
|N — количество точек в генерируемой последовательности, число;
|-
|-
-
|K количество скрытых состояний, число типа uint16;
+
|p априорное распределение на <tex>t_1</tex>, вектор длины K;
|-
|-
-
|M глубина авторегрессии, число типа uint16;
+
|R матрица перехода размера K x K;
|-
|-
-
|InputParameters (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
+
|W параметры сдвига авторегрессии для каждого состояния, матрица размера d x K;
|-
|-
-
|&nbsp;&nbsp;'w' задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);
+
|A авторегрессионные матрицы A для каждого состояния, массив размера d x Md x K;
|-
|-
-
|&nbsp;&nbsp;'A' задаваемая пользователем матрица перехода;
+
|Sigmas матрицы ковариации шума для каждого состояния, массив размера d x d x K;
|-
|-
-
|&nbsp;&nbsp;'Mu' задаваемые пользователем центры гауссиан для каждого состояния;
+
|X0 — начальная предыстория, матрица размера M x d;
 +
|}
 +
|-
 +
|ВЫХОД
 +
|-
 +
|
 +
{|
 +
|X сгенерированная наблюдаемая последовательность, матрица размера N x d;
|-
|-
-
|&nbsp;&nbsp;'Sigma' задаваемая пользователем матрица ковариации гауссиан;
+
|T сгенерированная последовательность состояния, вектор длины N.
|-
|-
-
|&nbsp;&nbsp;'C' — задаваемые пользователем коэффициенты авторегрессии;
+
|}
 +
|}
 +
 
 +
Если начальная предыстория <tex>X_0</tex> не задана, то <tex>X_0</tex> выбирается равной мат.ожиданию процесса авторегрессии, соответствующего сгенерированному состоянию <tex>t_1</tex>.
 +
 
 +
{|class="standard"
 +
!''Оценка параметров авторегрессионной скрытой марковской модели с помощью ЕМ-алгоритма''
 +
|-
 +
|[p, R, W, A, Sigmas] = '''arhmm_fit'''(X, K, M, param_name1, param_value1, ...)
 +
|-
 +
|ВХОД
 +
|-
 +
|
 +
{|
 +
|X наблюдаемая последовательность, матрица размера N x d, первые M строк соответствуют начальной предыстории;
|-
|-
-
|&nbsp;&nbsp;'num_iter' максимально допустимое число итераций EM-алгоритма;
+
|K количество скрытых состояния, число;
|-
|-
-
|&nbsp;&nbsp;'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации;
+
|M — глубина авторегрессии, число;
-
|}
+
|-
 +
|(param_name, param_value) — набор необязательных параметров, следующие имена и значения возможны:
 +
|-
 +
|
 +
{|
 +
|'max_iter' — максимальное число итераций ЕМ-алгоритма, по умолчанию = 100;
 +
|-
 +
|'num_start' — количество запусков из случайных начальных приближений, по умолчанию = 1;
 +
|-
 +
|'p' — известное априорное распределение на состояния, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
 +
|-
 +
|'R' — известная матрица перехода между состояниями, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
 +
|-
 +
|'W' — известный набор параметров сдвига, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
 +
|-
 +
|'A' — известный набор авторегрессионных матриц, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
 +
|-
 +
|'Sigmas' — известный набор матриц ковариации шума, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
 +
|-
 +
|'display' — режим отображения, true или false, если true, то отображается текущая информация, например, номер запуска, номер итерации, текущее значение правдоподобия и т.д.
 +
|}
|-
|-
|ВЫХОД
|ВЫХОД
Строка 197: Строка 236:
|
|
{|
{|
-
|w априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
+
|p априорное распределение на состояние, вектор длины K;
|-
|-
-
|A — матрица перехода, матрица типа double размера K x K;
+
|R — матрица перехода между состояниями, матрица размера K x K;
|-
|-
-
|Mu центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
+
|W параметр сдвига авторегрессий, матрица размера d x K;
|-
|-
-
|Sigma матрица ковариации гауссиан, массив типа double размера d x d;
+
|A авторегрессионные матрицы, массив размера d x Md x K;
|-
|-
-
|C коэффициенты авторегрессии, матрица типа double размера K x M;
+
|Sigmas матрицы ковариации шумов, массив размера d x d x K.
|-
|-
-
|Core — все параметры для всех итераций EM-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigma', 'C', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия
 
|}
|}
|}
|}
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Версия 22:36, 30 марта 2013


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


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

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

Содержание

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

Графическая модель авторегрессии 1-го порядка
Графическая модель авторегрессии 1-го порядка

Случайный процесс с дискретным временем \{\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}.

В дальнейшем для удобства набор матриц A_1,\dots,A_M будем обозначать через \mathcal{A}.

Графическая модель авторегрессии 2-го порядка
Графическая модель авторегрессии 2-го порядка

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

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

а X_0=\{\vec{x}_0,\vec{x}_{-1},\dots,\vec{x}_{1-M}\} — начальная предыстория.


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

Графическая модель авторегрессионной скрытой марковской модели 2-го порядка
Графическая модель авторегрессионной скрытой марковской модели 2-го порядка

Авторегрессионная скрытая марковская модель M-го порядка — это байесовская сеть, граф которой показан на рис. справа, а совместное распределение задается как

p(X,T|\theta,X_0)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(\vec{x}_n |t_n,\vec{x}_{n-1},\dots,\vec{x}_{n-M}).

Здесь t_n\in\{1,\dots,K\} — скрытые дискретные состояния, \vec{x}_n\in\mathbb{R}^d — непрерывные наблюдаемые переменные. Априорное распределение p(t_1) задается вектором [\pi_1,\ldots,\pi_K], причем все \pi_k\ge 0 и \sum_k\pi_k=1. Распределение p(t_n |t_{n-1}) задается матрицей перехода R размера K\times K, где в ij-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны, а сумма элементов по каждой строке равна единице. Модель генерации данных соответствует модели авторегрессии, в которой параметры \vec{w},\mathcal{A},\Sigma зависят от текущего состояния t_n. Таким образом,

p(\vec{x}_n|t_n,\vec{x}_{n-1},\dots,\vec{x}_{n-M})=\mathcal{N}(\vec{x}_n|\vec{w}_{t_n}+\sum_{m=1}^MA_{m,t_n}\vec{x}_{n-m},\Sigma_{t_n}).

В результате полный набор параметров модели состоит из \vec{\pi},R,\{\vec{w}_k,\mathcal{A}_k,\Sigma_k\}_{k=1}^K. Глубина авторегрессии M, количество скрытых состояний K, а также начальная предыстория X_0=\{\vec{x}_0,\vec{x}_{-1},\dots,\vec{x}_{1-M}\} задаются пользователем.

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

  1. Для модели авторегрессии M-го порядка:
    • Вывести формулы для оценки параметров модели \vec{w},A,\Sigma по наблюдениям \{\vec{x}_n\}_{n=1}^N с помощью метода максимального правдоподобия;
    • Реализовать процедуру генерации сигнала из модели авторегрессии;
    • Реализовать процедуру оценки параметров \vec{w},A,\Sigma по методу максимального правдоподобия;
    • Реализовать процедуру оценки выборочной автокорреляционной функции остатков авторегрессии;
  2. Провести эксперименты с авторегрессией M-го порядка на модельных данных:
    • в
  3. Для авторегрессионной скрытой марковской модели:
    • Вывести формулы ЕМ-алгоритма для оценки параметров модели \vec{\pi},B,\{\vec{w}_k,A_k,\Sigma_k}_{k=1}^K, при этом предусмотреть ситуации, когда часть параметров известна;
    • Реализовать процедуру генерации сигнала из модели;
    • Реализовать процедуру оценки параметров модели с помощью EM-алгоритма;
    • Реализовать процедуру оценки скрытых состояний по наблюдаемым данным и параметрам модели с помощью алгоритма Витерби;
  4. Провести эксперименты с авторегрессионной скрытой марковской моделью на модельных данных:
  5. Применить авторегрессионную скрытую марковскую модель для моделирования и сегментации движений в базе данных mocap.

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

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

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

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

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

 

Генерация выборки из модели авторегрессии
X = ar_generate(N, w, A, Sigma, X0)
ВХОД
N — количество точек в генерируемой последовательности, число;
w — параметр сдвига, вектор длины d;
A — набор матриц в форме [A_1\ A_2\ \dots\ A_M], матрица размера d x Md;
Sigma — матрица ковариации для нормального шума, матрица размера d x d;
X0 — (необязательный параметр) начальная предыстория, матрица размера M x d;
ВЫХОД
X — сгенерированная последовательность, матрица размера N x d.

Если начальная предыстория X_0 не задана, то X_0 выбирается равной мат.ожиданию процесса авторегрессии.

Оценка параметров авторегрессии
[w, A, Sigma, res, LH] = ar_fit(X, M)
ВХОД
X — наблюдаемая последовательность, матрица размера N x d, первые M строк соответствуют начальной предыстории;
M — глубина авторегрессии, число;
ВЫХОД
w — параметр сдвига авторегрессии, вектор длины d;
A — набор матриц в форме [A_1\ A_2\ \dots\ A_M], матрица размера d x Md;
Sigma — матрица ковариации нормального шума, матрица размера d x d;
res — остатки авторегрессии (набор векторов \vec{x}_n-\vec{w}-\sum_{m=1}^MA_m\vec{x}_{n-m}), матрица размера (N-M) x d;
LH — логарифм правдоподобия настроенной модели авторегрессии, число.

 

Генерация выборки из авторегрессионной скрытой марковской модели
[X, T] = arhmm_generate(N, p, R, W, A, Sigmas, X0)
ВХОД
N — количество точек в генерируемой последовательности, число;
p — априорное распределение на t_1, вектор длины K;
R — матрица перехода размера K x K;
W — параметры сдвига авторегрессии для каждого состояния, матрица размера d x K;
A — авторегрессионные матрицы A для каждого состояния, массив размера d x Md x K;
Sigmas — матрицы ковариации шума для каждого состояния, массив размера d x d x K;
X0 — начальная предыстория, матрица размера M x d;
ВЫХОД
X — сгенерированная наблюдаемая последовательность, матрица размера N x d;
T — сгенерированная последовательность состояния, вектор длины N.

Если начальная предыстория X_0 не задана, то X_0 выбирается равной мат.ожиданию процесса авторегрессии, соответствующего сгенерированному состоянию t_1.

Оценка параметров авторегрессионной скрытой марковской модели с помощью ЕМ-алгоритма
[p, R, W, A, Sigmas] = arhmm_fit(X, K, M, param_name1, param_value1, ...)
ВХОД
X — наблюдаемая последовательность, матрица размера N x d, первые M строк соответствуют начальной предыстории;
K — количество скрытых состояния, число;
M — глубина авторегрессии, число;
(param_name, param_value) — набор необязательных параметров, следующие имена и значения возможны:
'max_iter' — максимальное число итераций ЕМ-алгоритма, по умолчанию = 100;
'num_start' — количество запусков из случайных начальных приближений, по умолчанию = 1;
'p' — известное априорное распределение на состояния, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
'R' — известная матрица перехода между состояниями, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
'W' — известный набор параметров сдвига, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
'A' — известный набор авторегрессионных матриц, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
'Sigmas' — известный набор матриц ковариации шума, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
'display' — режим отображения, true или false, если true, то отображается текущая информация, например, номер запуска, номер итерации, текущее значение правдоподобия и т.д.
ВЫХОД
p — априорное распределение на состояние, вектор длины K;
R — матрица перехода между состояниями, матрица размера K x K;
W — параметр сдвига авторегрессий, матрица размера d x K;
A — авторегрессионные матрицы, массив размера d x Md x K;
Sigmas — матрицы ковариации шумов, массив размера d x d x K.