Сравнение временных рядов при авторегрессионном прогнозе (пример)

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

Версия от 12:28, 23 декабря 2010; Strijov (Обсуждение | вклад)

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

Содержание

1 Аннотация
2 Постановка задачи
3 Алгоритм
4 Вычислительный эксперимент
- 4.1 Пример на реальных дынных
- 4.2 Пример на сгенерированных данных
5 Исходный код
6 Литература

Аннотация

Данная работа посвящена исследованию зависимости между пространственными характеристиками (форма, период) временного ряда^[1] и распределением параметров регрессионных моделей, которые описывают эти временные ряды. Один из подходов исследовать данную зависимость - посмотреть, как распределены параметры моделей для похожих в некотором смысле временных рядов, и насколько эти распределения различаются для непохожих (различных в некотором смысле) временных рядов.

Постановка задачи

Временным рядом называется последовательность упорядоченных по времени значений некоторой вещественной переменной $\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$ . Элемент последовательности называется отсчетом временного ряда.

Задача авторегрессионного прогноза заключается в нахождении модели $f(\mathbf{x}, \mathbf{w})$ , где $\mathbf{w}\in\mathbb{R}^M$ вектор параметров модели, которая наилучшим образом приближает следущее значение временного ряда $x_{T+1}:\widehat{x}_{T+1}=f(\mathbf{x}, \mathbf{w})$ .

Пусть задан временной ряд $\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$ . Предполагается, что отсчеты $t=1,\dots, T$ были сделаны через равные промежутки времени, и период временного ряда равен $p$ , при этом ${T}+1=p\cdot{n}$ , где $n\in\mathbb{N}$ . Задана модель $\mathbf{x}=f(\mathbf{x}, w)+\epsilon$ ,где случайная величина $\mathbf{\varepsilon}$ имеет нормальное распределение $\mathbf{\varepsilon} \in N(0, \sigma^2)$ . Вектор параметров модели $\mathbf{w}$ рассматривается как многомерная случайная величина. Пусть плотность распределения параметров имеет вид многомерного нормального распределения $N(\mathbf{0}, A)$ с матрицей ковариации $A$ . Модель некоторым образом учитывает период временного ряда. Предполагается, модель временного ряда может меняться с течением времени, т.е. для разных подпоследовательностей длины $p$ оптимальные параметры модели $\mathbf{x}=f(\mathbf{x}, w)+\epsilon$ будут отличаться.

Расстояние между временными рядами

Расстояние между различными подпоследовательностями $x_{n_1\cdot{p}+1},\dots,x_{(n_1+1)\cdot{p}}$ и $x_{n_2\cdot{p}+1},\dots,x_{(n_2+1)\cdot{p}}$ можно вычислить как сумму квадратов отклонений:

$SSE=\sum_{i=1}^p{(x_{n_2{p}+i}-x_{n_1{p}+i})^2}$ .

Однако этот метод учитывает только расстояния между парами отсчетов временного ряда. Метод поиска пути минимальной стоимости (warping path)^[1] учитывает не только расстояние между отсчетами рядов, но и форму самих временных рядов.

Предположим, мы имеем две последовательности $\mathbf{x}= \{x_{1},\dots,x_{n}\}\in\mathbb{R}^n$ и $\mathbf{y}= \{y_{1},\dots,y_{m}\}\in\mathbb{R}^m$ . Тогда построим матрицу $n\times m$ попарных расстояний:

$\Omega=\|\omega_{i,j}\|_{i=1,j=1}^{n, m}=\|(x_i-x_j)^2\|_{i=1,j=1}^{n, m}$ .

Далее из элементов матрицы $\Omega$ строим путь:

$\{s_1, \dots, s_C\}=\{\omega_{i_1,j_1}, \dots, \omega_{i_{n_C}, j_{m_C}}\}$ .

Построенный путь удовлетворяет следующим условиям:

'1 граничные условия:' $s_1 = \omega_{1,1},~ s_C = \omega_{n,m}$ ; '2) непрерывность:' если~ $s_k = \omega_{i,j},~ s_{k-1} = \omega_{i',j'}$ , тогда $i-i'\leq 1,~ j-j'\leq 1$ ; '3) монотонность:' если~ $s_k = \omega_{i,j},~ s_{k-1} = \omega_{i',j'}$ , тогда $i-i'\geq 0,~j-j'\geq 0$ .

Стоимостью пути $\{s_1, \dots, s_C\}$ будет

$<tex>D\left(\{s_1, \dots, s_C\}\right)=\frac{\sqrt{\sum_{c=1}^C{s_c}}}{C}$ .

Среди всех путей есть по крайней мере один с минимальной стоимостью. Его стоимость и будем считать расстоянием между последовательностями:

$DTW(\mathbf{x},\mathbf{y}) = \min\limits_{\{s_1, \dots, s_C\}}D\left(\{s_1, \dots, s_C\}\right)$ .

Алгоритм поиска пути минимальной стоимости рекурсивно находит длину пути наименьшей стоимости $\gamma_{i,j}$ до каждого элемента матрицы $\Omeg$ :

$\gamma_{i,j} = \omega_{i,j}+\min(\gamma_{i,j-1}, \gamma_{i-1,j}, \gamma{i-1, j-1})$ .

Расстояние между параметрами модели

Расстояние между параметрами модели $\mathbf{x}=f(\mathbf{x}, \mathbb{w})+\epsilon$ , настроенной на разных подпоследовательностях, можно измерить как расстояние Кульбака-Лейблера между функциями распределения 2-ух случайных величин ${p(w)},{q(w)}$ :

$D_{KL}(p, q) = \sum\limits_{w\in \mathcal{W}} p(w) \ln \frac{p(w)}{q(w)}.$

Постановка задачи

Требуется исследовать зависимость расстояния между параметрами модели $\mathbf{x}=f(\mathbf{x}, w)+\epsilon$ от расстояния между подпоследовательностями, на которых эти параметры были настроены.

Алгоритм

Для настройки параметров модели $f(\mathbf{x}, \mathbf{w})+\epsilon$ используется связный байесовский вывод

$\ln p(D|\beta, A)=-\frac{1}{2}\ln|A|-\frac{N}{2}\ln2\pi+\frac{N}{2}\ln\beta-S(\mathbf{w_0})-\frac{1}{2}\ln|H|,$

где $S(\mathbf{w})=\frac{1}{2}\mathbf{w}^TA\mathbf{w}+\beta E_D$ — функция ошибки,

$H=-\nabla\nabla S(\mathbf{w})|_{\mathbf{w}=\mathbf{w_0}}$ — матрица Гессе функции ошибок,

$E_D=\frac{1}{2}\sum^n_{i=1}(\widehat{x_i}-x_i)^2$ — функция ошибки в пространстве данных.

Настройка параметрической регрессионной модели происходит в 2 этапа ^[1], сначала настраиваются параметры $\mathbf{w}$ при фиксированных гиперпараметрах $\beta, A$ , затем при вычисленных значениях параметров функция правдоподобия $\ln p(D|\beta, A)$ оптимизируется по гиперпараметрам. Процедура повторяется, пока настраиваемые параметры не стабилизируется.

Для простоты вычислений, считаем, что $A$ имеет диагональный вид:

$A=\left( \begin{array}{cccc} \alpha_{1} & 0 & \dots & 0\\ 0 & \alpha_2 & \dots & 0 \\ \vdots & \vdots & \ddots & 0\\ 0 & \dots & 0 & \alpha_M\\ \end{array} \right).$ .

Вычислительный эксперимент

Пример на реальных дынных

Вычислительный эксперимент проводился на реальных данных. Использовались временные ряды потребления электроэнергии в некотором регионе с отсчетами 1 час, период ряда равен $p=24$ . Эксперимент состоит из этапов:

1) из множества порождающих моделей:

$f_1(x) = x; f_2(x) = \sin(x); f_3(x) = \cos(x); f_4(x) = \exp(x); f_5(x) = \ln(x); f_6(x) = \tan(x);$

была построена их суперпозиция, описывающая потребление электроэнергии за сутки:

$\widehat{x}_{pn+t}=w_1\cdot{\sqrt{t}}+w_2\cdot{\exp(-t)}+w_3\cdot{\exp(-24\cdot{t})}+w_4\cdot \exp\left(w_5\cdot{\sin(t^4)} \right)+w_6\cdot \exp \left( w_7\cdot cos(24\cdot t^{2,5})\right)+$ $+w_{10}\cdot cos(t)+w_{12}\cdot t\cdot cos(t^3).$

2) модель настраивается на подпоследовательности

$\mathbf{x}(n)=\{x_{pn+1},\dots,x_{pn+24}\}$ ,

где $n$ - номер суток. В результате получаем набор оптимальных параметров и гиперпараметров модели, оптимальных для данной подпоследовательности:

$\mathbf{w}(n), A(n), \beta(n)$ .

3) строится зависимость расстояния между последовательностями в пространстве параметров:

$D_{KL} \left( \mathbf{x}(n), \mathbf{x}(m) \right)= D_{KL}\left(p(w), q(w) \right) = \sum\limits_{w\in \mathcal{W}} p(w) \ln \frac{p(w)}{q(w)}$ , где $p(w),q(w)$ - плотности распределений случайных величины из $N(\mathbf{w}(n),A(n))$ и $N(\mathbf{w}(m),A(m))$ соотвественно, и расстояний в пространстве значений:

$Dintance \left( \mathbf{x}(n), \mathbf{x}(m) \right)=\sum_{t=1}^{24}\left( x_t(n)-x_t(m) \right)^2$

Результаты экспериментов на реальных данных показывают, что можно выделить среди множества пар временных рядов похожие и непохожие. Используя расстояние Кульбака-Лейблера между распределениями параметров моделей можно установить порог, который поможет определить похожие на заранее выделенный тип временных рядов. Для пояснения вышесказанного приведем пример на модельных данных, в которых участвуют временные ряды двух типов.

Пример на сгенерированных данных

Проведен для для 6 моделей распределения данных: 1) $f(\mathbf{x},\mathbf{w}) = a_1 + b_1\cdot{t}+\epsilon$ , где $\epsilon\in N(0, 1)$ ;

2) $f(\mathbf{x},\mathbf{w}) = a_1 + b_1\cdot{t}+\epsilon$ , где $\epsilon\in N(0, 5)$ ;

3) $f(\mathbf{x},\mathbf{w}) = a_1-10*\sigma_{\epsilon} + b_1\cdot{t}+\epsilon$ , где $\epsilon\in N(0, 1)$ , $\sigma_{\epsilon}$ - дисперсия случайной величины;

4) $f(\mathbf{x},\mathbf{w}) = a_1 + 1,5\cdot b_1\cdot{t}-t^2+\epsilon$ , где $\epsilon\in N(0, 5)$ ;

5) $f(\mathbf{x},\mathbf{w}) = a_1 + 1,5\cdot b_1\cdot{t}-t^2+\epsilon$ , где $\epsilon\in N(0, 10)$ ;

6) $f(\mathbf{x},\mathbf{w}) = a_1 -10*\sigma_{\epsilon} + 1,5\cdot b_1\cdot{t}-t^2+\epsilon$ , где $\epsilon\in N(0, 5)$ .

Первые три модели относится в первому типу (line), три последних модели относятся ко второму типу (parabola). Прогнозирующая модель была линейной: $\widehat{x}_{t}=w_1+w_2\cdot{t}$ .

На тестовом примере видно, что чем больше расстояние между рядами в пространстве значений, тем скорее больше будет разница между распределениями настроенных параметров. На картинках можно явно разделить увидеть, что расстояние Кульбака-Лейблера между распределениями настроенных параметров для похожих моделей (line - line или parabola - parabola) значительно меньше расстояния между параметрами непохожих моделей (line-parabola или parabola-line). Таким образом можно настроить такой порог, по которому можно было бы определить, относится ли временной ряд к заранее фиксированному типу моделей.