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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Литература)
Строка 8: Строка 8:
Пусть задан временной ряд <tex>$\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$</tex>. Предполагается, что отсчеты <tex>t=1,\dots, T</tex> были сделаны через равные промежутки времени, и период временного ряда равен <tex>$p$</tex>, при этом <tex>$ {T}+1=p\cdot{n}$</tex>, где <tex>n\in\mathbb{N}</tex>.
Пусть задан временной ряд <tex>$\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$</tex>. Предполагается, что отсчеты <tex>t=1,\dots, T</tex> были сделаны через равные промежутки времени, и период временного ряда равен <tex>$p$</tex>, при этом <tex>$ {T}+1=p\cdot{n}$</tex>, где <tex>n\in\mathbb{N}</tex>.
Задана модель <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex>,где случайная величина <tex>\mathbf{\varepsilon}</tex> имеет нормальное распределение <tex>\mathbf{\varepsilon} \in N(0, \sigma^2)</tex>. Вектор параметров модели <tex>\mathbf{w}</tex> рассматривается как многомерная случайная величина. Пусть плотность распределения параметров имеет вид многомерного нормального распределения <tex>N(\mathbf{0}, A)</tex> с матрицей ковариации <tex>A</tex>. Модель некоторым образом учитывает период временного ряда.
Задана модель <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex>,где случайная величина <tex>\mathbf{\varepsilon}</tex> имеет нормальное распределение <tex>\mathbf{\varepsilon} \in N(0, \sigma^2)</tex>. Вектор параметров модели <tex>\mathbf{w}</tex> рассматривается как многомерная случайная величина. Пусть плотность распределения параметров имеет вид многомерного нормального распределения <tex>N(\mathbf{0}, A)</tex> с матрицей ковариации <tex>A</tex>. Модель некоторым образом учитывает период временного ряда.
-
Предполагается, модель временного ряда может меняться с течением времени, т.е. для разных подпоследовательностей длины <tex>p</tex> оптимальные параметры модели <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex> будут отличаться. Расстояние между различными подпоследовательностями <tex> x_{n_1\cdot{p}+1},\dots,x_{(n_1+1)\cdot{p}}</tex> и <tex> x_{n_2\cdot{p}+1},\dots,x_{(n_2+1)\cdot{p}}</tex> измеряется как сумма квадратов отклонений:
+
Предполагается, модель временного ряда может меняться с течением времени, т.е. для разных подпоследовательностей длины <tex>p</tex> оптимальные параметры модели <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex> будут отличаться.
-
<center><tex>SSE=\sum_{i=1}^p{(x_{n_2{p}+i}-x_{n_1{p}+i})^2}</tex></center>.
+
-
Расстояние между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex>, настроенной на разных подпоследовательностях, можно измерить как расстояние Кульбака-Лейблера между функциями распределения 2-ух случайных величин <tex>{p(x)},{q(x)}</tex>:
+
-
<center><tex>D_{KL}(p, q) = \sum\limits_{x\in \mathcal{X}} p(x) \ln \frac{p(x)}{q(x)}.</tex></center>
+
 +
=== Расстояние между временными рядами ===
 +
Расстояние между различными подпоследовательностями <tex> x_{n_1\cdot{p}+1},\dots,x_{(n_1+1)\cdot{p}}</tex> и <tex> x_{n_2\cdot{p}+1},\dots,x_{(n_2+1)\cdot{p}}</tex> можно вычислить как сумму квадратов отклонений:
 +
 +
<center><tex>SSE=\sum_{i=1}^p{(x_{n_2{p}+i}-x_{n_1{p}+i})^2}</tex></center>.
 +
 +
Однако этот метод учитывает только расстояния между парами отсчетов временного ряда. Метод поиска пути минимальной стоимости (warping path) учитывает не только расстояние между отсчетами рядов, но и форму самих временных рядов.
 +
 +
Предположим, мы имеем две последовательности <tex>\mathbf{x}= \{x_{1},\dots,x_{n}\}\in\mathbb{R}^n</tex> и <tex>\mathbf{y}= \{y_{1},\dots,y_{m}\}\in\mathbb{R}^m</tex>. Тогда построим матрицу <tex>n\times m</tex> попарных расстояний:
 +
 +
<center><tex>\Omega=\|\omega_{i,j}\|_{i=1,j=1}^{n, m}=\|(x_i-x_j)^2\|_{i=1,j=1}^{n, m}</tex></center>.
 +
 +
Далее из элементов матрицы <tex>\Omega</tex> строим путь:
 +
 +
<center><tex>\{s_1, \dots, s_C\}=\{\omega_{i_1,j_1}, \dots, \omega_{i_{n_C}, j_{m_C}}\}</tex></center>.
 +
 +
Построенный путь удовлетворяет следующим условиям:
 +
 +
''''1 граничные условия:'''' <center> <tex>s_1 = \omega_{1,1},~ s_C = \omega_{n,m}</tex>;</center>
 +
 +
''''2) непрерывность:'''' <center>если~<tex> s_k = \omega_{i,j},~ s_{k-1} = \omega_{i',j'}</tex>, тогда <tex>i-i'\leq 1,~ j-j'\leq 1</tex>;</center>
 +
 +
''''3) монотонность:'''' <center>если~<tex> s_k = \omega_{i,j},~ s_{k-1} = \omega_{i',j'}</tex>, тогда <tex>i-i'\geq 0,~j-j'\geq 0</tex>.</center>
 +
 +
Стоимостью пути <tex>\{s_1, \dots, s_C\}</tex> будет
 +
 +
<center><tex><tex>D\left(\{s_1, \dots, s_C\}\right)=\frac{\sqrt{\sum_{c=1}^C{s_c}}}{C}</tex>.</center>
 +
 +
Среди всех путей есть по крайней мере один с минимальной стоимостью. Его стоимость и будем считать расстоянием между последовательностями:
 +
 +
<center><tex>DTW(\mathbf{x},\mathbf{y}) = \min\limits_{\{s_1, \dots, s_C\}}D\left(\{s_1, \dots, s_C\}\right)</tex></center>.
 +
 +
=== Расстояние между параметрами модели ===
 +
Расстояние между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, \mathbb{w})+\epsilon$</tex>, настроенной на разных подпоследовательностях, можно измерить как расстояние Кульбака-Лейблера между функциями распределения 2-ух случайных величин <tex>{p(x)},{q(x)}</tex>:
 +
<center><tex>D_{KL}(p, q) = \sum\limits_{x\in \mathcal{X}} p(x) \ln \frac{p(x)}{q(x)}.</tex></center>
 +
=== Постановка задачи ===
Требуется исследовать зависимость расстояния между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex> от расстояния между подпоследовательностями, на которых эти параметры были настроены.
Требуется исследовать зависимость расстояния между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex> от расстояния между подпоследовательностями, на которых эти параметры были настроены.
Строка 78: Строка 110:
[[Изображение:KL SSE Distance.png|thumb|left]]
[[Изображение:KL SSE Distance.png|thumb|left]]
 +
Результаты экспериментов на реальных данных опровергают утверждение о зависимости расстояния между временными рядами в пространстве значений от расстояния между распределениями параметров соответствующей им модели.
== Исходный код ==
== Исходный код ==
== Смотри также ==
== Смотри также ==
Строка 92: Строка 125:
|издательство = ВЦ РАН
|издательство = ВЦ РАН
|год = 2010
|год = 2010
-
}}
 
-
# {{книга
 
-
|автор = Keogh E. J., Pazzani M. J.
 
-
|заглавие = Derivative Dynamic Time Warping
 
-
|издательство = International Conference on Data Mining
 
-
|гордо = Chicago
 
-
|год = 2001
 
}}
}}

Версия 18:14, 21 декабря 2010

Содержание

Аннотация

Временным рядом называется последовательность упорядоченных по времени значений некоторой вещественной переменной $\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})$. Свертка временного ряда возникает в случае существования на множестве подпоследовательностей временного ряда некоторого инварианта. Примером инварианта является период временного ряда, который физически может означать сезонность в данных. При этом построенная модель должна учитывать наличие инварианта и сохранять данное свойство для ряда прогнозов: $\{\widehat{x}_{t}\}_{t=1}^T\in\mathbb{R}^T$.

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

Пусть задан временной ряд $\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) учитывает не только расстояние между отсчетами рядов, но и форму самих временных рядов.

Предположим, мы имеем две последовательности \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)
.

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

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

D_{KL}(p, q) = \sum\limits_{x\in \mathcal{X}} p(x) \ln \frac{p(x)}{q(x)}.

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

Требуется исследовать зависимость расстояния между параметрами модели $\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 этапа, сначала настраиваются параметры \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*t)}+w_4\cdot \exp\left(w_5\cdot{\sin(t^4)} \right)+w_6\cdot \exp \left( w_7\cdot cos(24*t^{2,5})\right)+$$

$$+w_8\cdot \exp\left(w_9\cdot sin(t^{-0,5}) \right)+w_{10}\cdot cos(t)+w_{11}\cdot cos(\frac{2}{15}\cdot t+\frac{1}{3}))+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

Результаты экспериментов на реальных данных опровергают утверждение о зависимости расстояния между временными рядами в пространстве значений от расстояния между распределениями параметров соответствующей им модели.

Исходный код

Смотри также

Литература

  1. Стрижов В.В, Пташко Г.О. Построение инвариантов на множестве временных рядов путем динамической свертки свободной переменной. — ВЦ РАН, 2009.
  2. Стрижов В.В Методы выбора регрессионных моделей. — ВЦ РАН, 2010.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D1%80%D1%8F%D0%B4%D0%BE%D0%B2_%D0%BF%D1%80%D0%B8_%D0%B0%D0%B2%D1%82%D0%BE%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D0%BE%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BF%D1%80%D0%BE%D0%B3%D0%BD%D0%BE%D0%B7%D0%B5_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»