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

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

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

Перейти к: навигация, поиск

Текущая версия

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

Содержание

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

Пример сегментации сигнала, сгенерированного из авторегрессионной скрытой марковской модели с 3-мя состояниями и глубиной авторегрессии 2.

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

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

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

Графическая модель авторегрессии 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{x}}_n = \begin{bmatrix}\vec{x}_n\\ \vec{x}_{n-1}\\ \vdots \\ \vec{x}_{n-M}\end{bmatrix},\quad \tilde{\vec{w}} = \begin{bmatrix}\vec{w}\\ 0\\ \vdots \\ 0\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}$ по модулю меньше единицы. В частности, для случая $d=1,M=1$ условие стационарности эквивалентно $|A_1|<1$ , а для случая $d=1,M=2$ — условию $|A_1|<2,\ -1<A_2<1-|A_1|$ . Мат.ожидание стационарной регрессии M-го порядка определяется как

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

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

Графическая модель авторегрессии 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}\}$ — начальная предыстория.

Пример выборочной автокорреляционной функции с отсутствием значимых автокорреляций

Одним из способов определения адекватности моделирования данных с помощью модели авторегрессии является исследование остатков

$\hat{\varepsilon}_n = \vec{x}_n - \hat{\vec{w}} - \sum_{m=1}^M\hat{A}_m\vec{x}_{n-m}$ ,

где $\hat{\vec{w}},\hat{A}$ — оценки параметров авторегрессии (например, оценки максимального правдоподобия). Для успешного объяснения данных с помощью авторегрессии необходимо, чтобы остатки не были коррелированы по времени. Другими словами, выборочная автокорреляционная функция

$ACF(\tau) = c_{\tau}/c_0,\quad c_{\tau} = \frac{1}{N-\tau}\sum_{n = \tau+1}^N(\varepsilon_n - \bar{\varepsilon})(\varepsilon_{n-\tau} - \bar{\varepsilon}),\quad \bar{\varepsilon} = \frac{1}{N}\sum_n\varepsilon_n$

должна лежать в интервале $\pm \frac{z_{1-\alpha/2}}{\sqrt{N}}$ для всех $\tau$ . Здесь через $z_{\beta}$ обозначена $\beta$ -квантиль одномерного нормального распределения. Для уровня значимости $\alpha=0.05$ соответствующая квантиль равна 1.96.

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

Графическая модель авторегрессионной скрытой марковской модели 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})$ .

В результате полный набор параметров модели $\Theta$ состоит из $\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}\}$ задаются пользователем.

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

Для модели авторегрессии M-го порядка:
- Вывести формулы для оценки параметров модели $\vec{w},\mathcal{A},\Sigma$ по наблюдениям $\{\vec{x}_n\}_{n=1}^N$ с помощью метода максимального правдоподобия;
- Реализовать процедуру генерации сигнала из модели авторегрессии;
- Реализовать процедуру оценки параметров $\vec{w},\mathcal{A},\Sigma$ по методу максимального правдоподобия;
Провести эксперименты с авторегрессией M-го порядка:
- Сгенерировать данные из модели авторегрессии, а затем восстановить параметры по методу максимального правдоподобия (рассмотреть различные значения параметров модели, а также различные размерности параметров). Как ведут себя значение правдоподобия, авторегрессионные остатки и восстановленные параметры при глубине авторегрессии меньше истинного значения, равного истинному значению и больше истинного значения? Какой объем данных необходим для адекватного восстановления параметров модели?
- Сгенерировать данные из модели случайного процесса, отличного от авторегрессии. К чему приводит попытка объяснения таких данных с помощью авторегрессии?
Для авторегрессионной скрытой марковской модели:
- Вывести формулы ЕМ-алгоритма для оценки параметров модели $\vec{\pi},R,\{\vec{w}_k,\mathcal{A}_k,\Sigma_k}_{k=1}^K$ , при этом предусмотреть ситуации, когда часть параметров задается пользователем;
- Реализовать процедуру генерации сигнала из модели;
- Реализовать процедуру вычисления маргинальных распределений для отдельных скрытых переменных $t_n$ и пар соседних переменных $t_{n-1},t_n$ при известных наблюдениях и параметрах модели с помощью алгоритма «вперёд-назад»;
- Реализовать процедуру оценки параметров модели по методу максимального правдоподобия с помощью EM-алгоритма;
- Реализовать процедуру поиска наиболее вероятной конфигурации скрытых переменных по наблюдаемым данным и параметрам модели с помощью алгоритма Витерби;
Провести эксперименты с авторегрессионной скрытой марковской моделью:
- Сгенерировать наблюдаемые и скрытые переменные из модели, а затем восстановить скрытые компоненты с помощью алгоритма Витерби при истинных параметрах модели, а также путем взятия аргмаксимумов для маргинальных распределений на $t_n$ . Рассмотреть ситуации хорошо отделимых и слабо отделимых состояний, а также различные размерности параметров модели. Привести пример ситуации, когда алгоритм Витерби и аргмаксимумы маргиналов приводят к существенно различным конфигурациям.
- Сгенерировать наблюдаемые и скрытые переменные из модели, а затем восстановить параметры модели только по наблюдаемым данным с помощью ЕМ-алгоритма. Рассмотреть различные ситуации. Имеет ли смысл в ЕМ-алгоритме задавать часть параметров модели вручную? Как параметры, задаваемые вручную, влияют на значение правдоподобия и на качество сегментации сигнала?
[Бонус] Предложить свою схему сегментации подмножества сигналов, сгенерированных из авторегрессионной скрытой марковской модели, без использования модели авторегрессии.
Составить отчёт в формате PDF с описанием всех проведённых исследований. Данный отчёт должен включать в себя вывод необходимых формул, различные графики с результатами экспериментов, а также развернутые комментарии к полученным результатам.

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

Выполненное задание следует отправить письмом по адресу 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, logLH] = 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;

logLH — логарифм правдоподобия настроенной модели авторегрессии, число.

Генерация выборки из авторегрессионной скрытой марковской модели

[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$ .

Оценка маргиналов на скрытые переменные

[gamma, ksi, logLH] = arhmm_posterior(X, p, R, W, A, Sigmas)

ВХОД

X — наблюдаемая последовательность, матрица размера N x d, первые M строк соответствуют начальной предыстории;

p — априорное распределение на состояния, вектор длины K;

R — матрица перехода между состояниями, матрица размера K x K;

W — параметр сдвига авторегрессий, матрица размера d x K;

A — авторегрессионные матрицы, массив размера d x Md x K;

Sigmas — матрицы ковариации шумов, массив размера d x d x K;

ВЫХОД

gamma — вероятности вида $p(t_n=k|X,\Theta)$ , матрица размера K x (N-M);

ksi — вероятности вида $p(t_{n-1}=k_1,t_n=k_2|X,\Theta)$ , массив размера K x K x (N-M-1);

logLH — логарифм неполного правдоподобия, число.

Оценка параметров авторегрессионной скрытой марковской модели с помощью ЕМ-алгоритма

[p, R, W, A, Sigmas, logLH] = 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' — количество запусков из случайных начальных приближений, по умолчанию = 10;

'tol_LH' — точность оптимизации по значению логарифма правдоподобия, по умолчанию = 1e-4;

'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;

logLH — логарифм неполного правдоподобия, число.

Сегментация выборки с помощью алгоритма Витерби

[T, logLH] = arhmm_segment(X, p, R, W, A, Sigmas)

ВХОД

X — наблюдаемая последовательность, матрица размера N x d, первые M строк соответствуют начальной предыстории;

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;

ВЫХОД

T — номера состояний в каждый момент времени, вектор длины N-M;

logLH — логарифм полного правдоподобия для найденного T, число.

Источник — «http://www.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»

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

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

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

Текущая версия

Содержание

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

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

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
 {{main|Графические модели (курс лекций)}}
-{{stop|Формулировка задания находится в стадии подготовки. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.}}
+{{TOCright|300px}}
-'''Начало выполнения задания''': 18 марта 2013 г.;<br>
+{|
-'''Срок сдачи''': {{ins|7 апреля 2013 г. (воскресенье), 23:59.}}
+ |[[Изображение:GM13_task3_intro.png|мини|300px|Пример сегментации сигнала, сгенерированного из авторегрессионной скрытой марковской модели с 3-мя состояниями и глубиной авторегрессии 2.]]
+ |}
+'''Начало выполнения задания''': 1 апреля 2013 г.;<br>
+'''Срок сдачи''': {{ins|11 апреля 2013 г. (четверг), 23:59.}}
 Среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
@@ Строка 16: / Строка 20: @@
 :<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{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>,
@@ Строка 32: / Строка 36: @@
 :<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>\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>
+:<tex>\tilde{\vec{x}}_n = \tilde{\vec{w}} + \tilde{A}\tilde{\vec{x}}_{n-1} + \tilde{\vec{\varepsilon}}_n,\quad \tilde{\vec{x}}_n = \begin{bmatrix}\vec{x}_n\\ \vec{x}_{n-1}\\ \vdots \\ \vec{x}_{n-M}\end{bmatrix},\quad \tilde{\vec{w}} = \begin{bmatrix}\vec{w}\\ 0\\ \vdots \\ 0\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-го порядка определяется как
+Поэтому авторегрессия M-го порядка является стационарной, когда все собственные значения матрицы <tex>\tilde{A}</tex> по модулю меньше единицы. В частности, для случая <tex>d=1,M=1</tex> условие стационарности эквивалентно <tex>|A_1|<1</tex>, а для случая <tex>d=1,M=2</tex> — условию <tex>|A_1|<2,\ -1<A_2<1-|A_1|</tex>. Мат.ожидание стационарной регрессии M-го порядка определяется как
 :<tex>\vec{\mu} = (I-A_1-\dots-A_M)^{-1}\vec{w}</tex>.
@@ Строка 50: / Строка 54: @@
 а <tex>X_0=\{\vec{x}_0,\vec{x}_{-1},\dots,\vec{x}_{1-M}\}</tex> — начальная предыстория.
+[[Изображение:ACF.png|thumb|300px|Пример выборочной автокорреляционной функции с отсутствием значимых автокорреляций]]
+Одним из способов определения адекватности моделирования данных с помощью модели авторегрессии является исследование остатков
+:<tex>\hat{\varepsilon}_n = \vec{x}_n - \hat{\vec{w}} - \sum_{m=1}^M\hat{A}_m\vec{x}_{n-m}</tex>,
+где <tex>\hat{\vec{w}},\hat{A}</tex> — оценки параметров авторегрессии (например, оценки максимального правдоподобия). Для успешного объяснения данных с помощью авторегрессии необходимо, чтобы остатки не были коррелированы по времени. Другими словами, выборочная автокорреляционная функция
+:<tex>ACF(\tau) = c_{\tau}/c_0,\quad c_{\tau} = \frac{1}{N-\tau}\sum_{n = \tau+1}^N(\varepsilon_n - \bar{\varepsilon})(\varepsilon_{n-\tau} - \bar{\varepsilon}),\quad \bar{\varepsilon} = \frac{1}{N}\sum_n\varepsilon_n</tex>
+должна лежать в интервале <tex>\pm \frac{z_{1-\alpha/2}}{\sqrt{N}}</tex> для всех <tex>\tau</tex>. Здесь через <tex>z_{\beta}</tex> обозначена <tex>\beta</tex>-квантиль одномерного нормального распределения. Для уровня значимости <tex>\alpha=0.05</tex> соответствующая квантиль равна 1.96.
 == Авторегрессионная скрытая марковская модель ==
@@ Строка 55: / Строка 70: @@
 [[Изображение:ARHMM2.png|thumb|300px|Графическая модель авторегрессионной скрытой марковской модели 2-го порядка]]
-Авторегрессионная скрытая марковская модель M-го порядка — это байесовская сеть, граф которой показан на рис. справа, а совместное распределение задается как
+''Авторегрессионная скрытая марковская модель M-го порядка'' — это байесовская сеть, граф которой показан на рис. справа, а совместное распределение задается как
-:<tex>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})</tex>.
+:<tex>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})</tex>.
 Здесь <tex>t_n\in\{1,\dots,K\}</tex> — скрытые дискретные состояния, <tex>\vec{x}_n\in\mathbb{R}^d</tex> — непрерывные наблюдаемые переменные. Априорное распределение <tex>p(t_1)</tex> задается вектором <tex>[\pi_1,\ldots,\pi_K]</tex>, причем все <tex>\pi_k\ge 0</tex> и <tex>\sum_k\pi_k=1</tex>. Распределение <tex>p(t_n |t_{n-1})</tex> задается матрицей перехода <tex>R</tex> размера <tex>K\times K</tex>, где в <tex>ij</tex>-ой позиции стоит вероятность перехода из состояния <tex>i</tex> в состояние <tex>j</tex>. Все элементы этой матрицы неотрицательны, а сумма элементов по каждой строке равна единице. Модель генерации данных соответствует модели авторегрессии, в которой параметры <tex>\vec{w},\mathcal{A},\Sigma</tex> зависят от текущего состояния <tex>t_n</tex>. Таким образом,
@@ Строка 63: / Строка 78: @@
 :<tex>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})</tex>.
-В результате полный набор параметров модели состоит из <tex>\vec{\pi},R,\{\vec{w}_k,\mathcal{A}_k,\Sigma_k\}_{k=1}^K</tex>. Глубина авторегрессии <tex>M</tex>, количество скрытых состояний <tex>K</tex>, а также начальная предыстория <tex>X_0=\{\vec{x}_0,\vec{x}_{-1},\dots,\vec{x}_{1-M}\}</tex> задаются пользователем.
+В результате полный набор параметров модели <tex>\Theta</tex> состоит из <tex>\vec{\pi},R,\{\vec{w}_k,\mathcal{A}_k,\Sigma_k\}_{k=1}^K</tex>. Глубина авторегрессии <tex>M</tex>, количество скрытых состояний <tex>K</tex>, а также начальная предыстория <tex>X_0=\{\vec{x}_0,\vec{x}_{-1},\dots,\vec{x}_{1-M}\}</tex> задаются пользователем.
 == Формулировка задания ==
 # Для модели авторегрессии M-го порядка:
-#* Вывести формулы для оценки параметров модели <tex>\vec{w},A,\Sigma</tex> по наблюдениям <tex>\{\vec{x}_n\}_{n=1}^N</tex> с помощью метода максимального правдоподобия;
+#* Вывести формулы для оценки параметров модели <tex>\vec{w},\mathcal{A},\Sigma</tex> по наблюдениям <tex>\{\vec{x}_n\}_{n=1}^N</tex> с помощью метода максимального правдоподобия;
 #* Реализовать процедуру генерации сигнала из модели авторегрессии;
-#* Реализовать процедуру оценки параметров <tex>\vec{w},A,\Sigma</tex> по методу максимального правдоподобия;
+#* Реализовать процедуру оценки параметров <tex>\vec{w},\mathcal{A},\Sigma</tex> по методу максимального правдоподобия;
-#* Реализовать процедуру оценки выборочной автокорреляционной функции остатков авторегрессии;
+# Провести эксперименты с авторегрессией M-го порядка:
-# Провести эксперименты с авторегрессией M-го порядка на модельных данных:
+#* Сгенерировать данные из модели авторегрессии, а затем восстановить параметры по методу максимального правдоподобия (рассмотреть различные значения параметров модели, а также различные размерности параметров). Как ведут себя значение правдоподобия, авторегрессионные остатки и восстановленные параметры при глубине авторегрессии меньше истинного значения, равного истинному значению и больше истинного значения? Какой объем данных необходим для адекватного восстановления параметров модели?
-#* в
+#* Сгенерировать данные из модели случайного процесса, отличного от авторегрессии. К чему приводит попытка объяснения таких данных с помощью авторегрессии?
 # Для авторегрессионной скрытой марковской модели:
-#* Вывести формулы ЕМ-алгоритма для оценки параметров модели <tex>\vec{\pi},B,\{\vec{w}_k,A_k,\Sigma_k}_{k=1}^K</tex>, при этом предусмотреть ситуации, когда часть параметров известна;
+#* Вывести формулы ЕМ-алгоритма для оценки параметров модели <tex>\vec{\pi},R,\{\vec{w}_k,\mathcal{A}_k,\Sigma_k}_{k=1}^K</tex>, при этом предусмотреть ситуации, когда часть параметров задается пользователем;
 #* Реализовать процедуру генерации сигнала из модели;
-#* Реализовать процедуру оценки параметров модели с помощью EM-алгоритма;
+#* Реализовать процедуру вычисления маргинальных распределений для отдельных скрытых переменных <tex>t_n</tex> и пар соседних переменных <tex>t_{n-1},t_n</tex> при известных наблюдениях и параметрах модели с помощью алгоритма «вперёд-назад»;
-#* Реализовать процедуру оценки скрытых состояний по наблюдаемым данным и параметрам модели с помощью алгоритма Витерби;
+#* Реализовать процедуру оценки параметров модели по методу максимального правдоподобия с помощью EM-алгоритма;
-# Провести эксперименты с авторегрессионной скрытой марковской моделью на модельных данных:
+#* Реализовать процедуру поиска наиболее вероятной конфигурации скрытых переменных по наблюдаемым данным и параметрам модели с помощью алгоритма Витерби;
-# Применить авторегрессионную скрытую марковскую модель для моделирования и сегментации движений в базе данных mocap.
+# Провести эксперименты с авторегрессионной скрытой марковской моделью:
+#* Сгенерировать наблюдаемые и скрытые переменные из модели, а затем восстановить скрытые компоненты с помощью алгоритма Витерби при истинных параметрах модели, а также путем взятия аргмаксимумов для маргинальных распределений на <tex>t_n</tex>. Рассмотреть ситуации хорошо отделимых и слабо отделимых состояний, а также различные размерности параметров модели. Привести пример ситуации, когда алгоритм Витерби и аргмаксимумы маргиналов приводят к существенно различным конфигурациям.
+#* Сгенерировать наблюдаемые и скрытые переменные из модели, а затем восстановить параметры модели только по наблюдаемым данным с помощью ЕМ-алгоритма. Рассмотреть различные ситуации. Имеет ли смысл в ЕМ-алгоритме задавать часть параметров модели вручную? Как параметры, задаваемые вручную, влияют на значение правдоподобия и на качество сегментации сигнала?
+# '''[Бонус]''' Предложить свою схему сегментации подмножества сигналов, сгенерированных из авторегрессионной скрытой марковской модели, без использования модели авторегрессии.
+# Составить отчёт в формате PDF с описанием всех проведённых исследований. Данный отчёт должен включать в себя вывод необходимых формул, различные графики с результатами экспериментов, а также развернутые комментарии к полученным результатам.
 == Рекомендации по выполнению задания ==
 . Вывод формул для авторегрессии и авторегрессионной скрытой марковской модели удобно осуществлять путем введения обозначений
-::<tex>\vec{y}_n = [\vec{x}_{n-1}^T\ \vec{x}_{n-2}^T\ \dots \vec{x}_{n-M}^T\ 1]^T,\quad B = [A_1\ A_2\ \dots A_M\ \vec{w}]</tex>
+::<tex>\vec{y}_n = [\vec{x}_{n-1}^T\ \vec{x}_{n-2}^T\ \dots \vec{x}_{n-M}^T\ 1]^T,\quad B = [A_1\ A_2\ \dots A_M\ \vec{w}]</tex>.
 Тогда выражение <tex>\vec{x}_n - \vec{w} - \sum_{m=1}^MA_m\vec{x}_{n-m}</tex> можно лаконично записать как <tex>\vec{x}_n-B\vec{y}_n</tex>.
-. При тестировании ЕМ-алгоритма рекомендуется отследить монотонное возрастание логарифма правдоподобия в итерациях.
+После вывода необходимых формул рекомендуется убедиться в том, что эти формулы переходят в стандартные формулы для оценки параметров многомерного нормального распределения (в том числе в рамках скрытой марковской модели) при обнулении всех A.
+В случае вывода формул для <tex>\vec{w}</tex> при известном <tex>\mathcal{A}</tex> или, наоборот, формул для <tex>\mathcal{A}</tex> при фиксированном <tex>\vec{w}</tex> нотация через <tex>B,\vec{y}_n</tex> не подходит.
+. При тестировании ЕМ-алгоритма рекомендуется отслеживать монотонное возрастание логарифма неполного правдоподобия в итерациях. При этом вблизи локального максимума правдоподобия возможны небольшие нарушения монотонности из-за вычислительных погрешностей.
+. Обратите внимание, что для возможности реализации в сигналах сегментов типа <tex>k</tex> некоторой длины <tex>N_e</tex> необходимо, чтобы величина <tex>R_{kk}^{N_e}</tex> была существенно отлична от нуля.
 == Оформление задания ==
@@ Строка 95: / Строка 120: @@
 Присланный вариант задания должен содержать в себе:
-* Файл отчёта в формате PDF с указанием ФИО.
+* Файл отчёта в формате PDF с указанием ФИО;
 * Все исходные коды с необходимыми комментариями.
@@ Строка 134: / Строка 159: @@
  !''Оценка параметров авторегрессии''
  |-
- |[w, A, Sigma, res, LH] = '''ar_fit'''(X, M)
+ |[w, A, Sigma, res, logLH] = '''ar_fit'''(X, M)
  |-
  |ВХОД
@@ Строка 158: / Строка 183: @@
   |res — остатки авторегрессии (набор векторов <tex>\vec{x}_n-\vec{w}-\sum_{m=1}^MA_m\vec{x}_{n-m}</tex>), матрица размера (N-M) x d;
   |-
-  |LH — логарифм правдоподобия настроенной модели авторегрессии, число.
+  |logLH — логарифм правдоподобия настроенной модели авторегрессии, число.
   |}
  |}
@@ Строка 185: / Строка 210: @@
   |Sigmas — матрицы ковариации шума для каждого состояния, массив размера d x d x K;
   |-
-  |X0 — начальная предыстория, матрица размера M x d;
+  |X0 — (необязательный параметр) начальная предыстория, матрица размера M x d;
   |}
  |-
@@ Строка 194: / Строка 219: @@
   |X — сгенерированная наблюдаемая последовательность, матрица размера N x d;
   |-
-  |T — сгенерированная последовательность состояния, вектор длины N.
+  |T — сгенерированная последовательность состояний, вектор длины N.
   |-
   |}
@@ Строка 200: / Строка 225: @@
 Если начальная предыстория <tex>X_0</tex> не задана, то <tex>X_0</tex> выбирается равной мат.ожиданию процесса авторегрессии, соответствующего сгенерированному состоянию <tex>t_1</tex>.
+{|class="standard"
+ !''Оценка маргиналов на скрытые переменные''
+ |-
+ |[gamma, ksi, logLH] = '''arhmm_posterior'''(X, p, R, W, A, Sigmas)
+ |-
+ |ВХОД
+ |-
+ |
+ {|
+  |X — наблюдаемая последовательность, матрица размера N x d, первые M строк соответствуют начальной предыстории;
+  |-
+  |p — априорное распределение на состояния, вектор длины K;
+  |-
+  |R — матрица перехода между состояниями, матрица размера K x K;
+  |-
+  |W — параметр сдвига авторегрессий, матрица размера d x K;
+  |-
+  |A — авторегрессионные матрицы, массив размера d x Md x K;
+  |-
+  |Sigmas — матрицы ковариации шумов, массив размера d x d x K;
+  |}
+ |-
+ |ВЫХОД
+ |-
+ |
+ {|
+  |gamma — вероятности вида <tex>p(t_n=k|X,\Theta)</tex>, матрица размера K x (N-M);
+  |-
+  |ksi — вероятности вида <tex>p(t_{n-1}=k_1,t_n=k_2|X,\Theta)</tex>, массив размера K x K x (N-M-1);
+  |-
+  |logLH — логарифм неполного правдоподобия, число.
+  |}
+ |}
+&nbsp;
 {|class="standard"
  !''Оценка параметров авторегрессионной скрытой марковской модели с помощью ЕМ-алгоритма''
  |-
- |[p, R, W, A, Sigmas] = '''arhmm_fit'''(X, K, M, param_name1, param_value1, ...)
+ |[p, R, W, A, Sigmas, logLH] = '''arhmm_fit'''(X, K, M, param_name1, param_value1, ...)
  |-
  |ВХОД
@@ Строка 212: / Строка 273: @@
   |X — наблюдаемая последовательность, матрица размера N x d, первые M строк соответствуют начальной предыстории;
   |-
-  |K — количество скрытых состояния, число;
+  |K — количество скрытых состояний, число;
   |-
   |M — глубина авторегрессии, число;
@@ Строка 222: / Строка 283: @@
     |'max_iter' — максимальное число итераций ЕМ-алгоритма, по умолчанию = 100;
     |-
-    |'num_start' — количество запусков из случайных начальных приближений, по умолчанию = 1;
+    |'num_start' — количество запусков из случайных начальных приближений, по умолчанию = 10;
+    |-
+    |'tol_LH' — точность оптимизации по значению логарифма правдоподобия, по умолчанию = 1e-4;
     |-
-    |'p' — известное априорное распределение на состояния, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
+    |'p' — задаваемое пользователем априорное распределение на состояния (в случае задания не оптимизируется ЕМ-алгоритмом), по умолчанию = [];
     |-
-    |'R' — известная матрица перехода между состояниями, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
+    |'R' — задаваемая пользователем матрица перехода между состояниями, по умолчанию = [];
     |-
-    |'W' — известный набор параметров сдвига, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
+    |'W' — задаваемый пользователем набор параметров сдвига, по умолчанию = [];
     |-
-    |'A' — известный набор авторегрессионных матриц, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
+    |'A' — задаваемый пользователем набор авторегрессионных матриц, по умолчанию = [];
     |-
-    |'Sigmas' — известный набор матриц ковариации шума, в случае задания не оптимизируется ЕМ-алгоритмом, по умолчанию = [];
+    |'Sigmas' — задаваемый пользователем набор матриц ковариации шума, по умолчанию = [];
     |-
     |'display' — режим отображения, true или false, если true, то отображается текущая информация, например, номер запуска, номер итерации, текущее значение правдоподобия и т.д.
@@ Строка 241: / Строка 304: @@
  |
  {|
-  |p — априорное распределение на состояние, вектор длины K;
+  |p — априорное распределение на состояния, вектор длины K;
   |-
   |R — матрица перехода между состояниями, матрица размера K x K;
@@ Строка 249: / Строка 312: @@
   |A — авторегрессионные матрицы, массив размера d x Md x K;
   |-
-  |Sigmas — матрицы ковариации шумов, массив размера d x d x K.
+  |Sigmas — матрицы ковариации шумов, массив размера d x d x K;
   |-
+  |logLH — логарифм неполного правдоподобия, число.
   |}
  |}
@@ Строка 259: / Строка 323: @@
  !''Сегментация выборки с помощью алгоритма Витерби''
  |-
- |T = '''arhmm_segment'''(X, p, R, W, A, Sigmas)
+ |[T, logLH] = '''arhmm_segment'''(X, p, R, W, A, Sigmas)
  |-
  |ВХОД
@@ Строка 283: / Строка 347: @@
  |
  {|
-  |T — номера состояний в каждый момент времени, вектор длины N.
+  |T — номера состояний в каждый момент времени, вектор длины N-M;
   |-
+  |logLH — логарифм полного правдоподобия для найденного T, число.
   |}
  |}
 [[Категория:Учебные курсы]]