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

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

Версия от 19:56, 31 марта 2013; Kropotov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

Содержание

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://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.

Содержание

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

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

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты