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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Литература)
(Исходный код)
 
(28 промежуточных версий не показаны.)
Строка 1: Строка 1:
== Аннотация ==
== Аннотация ==
 +
Данная работа посвящена исследованию зависимости между пространственными характеристиками (форма, период) временного ряда<ref>Стрижов В.В, Пташко Г.О. Построение инвариантов на множестве временных рядов путем динамической свертки свободной переменной. — ВЦ РАН, 2009.</ref> и распределением параметров регрессионных моделей, которые описывают эти временные ряды. Один из подходов исследовать данную зависимость - посмотреть, как распределены параметры моделей для похожих в некотором смысле временных рядов, и насколько эти распределения различаются для непохожих (различных в некотором смысле) временных рядов.
 +
 +
== Постановка задачи ==
[[временной ряд|Временным рядом]] называется последовательность упорядоченных по времени значений некоторой вещественной переменной <tex>$\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$</tex>. Элемент последовательности называется отсчетом временного ряда.
[[временной ряд|Временным рядом]] называется последовательность упорядоченных по времени значений некоторой вещественной переменной <tex>$\mathbf{x}=\{x_{t}\}_{t=1}^T\in\mathbb{R}^T$</tex>. Элемент последовательности называется отсчетом временного ряда.
Задача авторегрессионного прогноза заключается в нахождении модели <tex>$f(\mathbf{x}, \mathbf{w})$</tex>, где <tex>$\mathbf{w}\in\mathbb{R}^M$</tex> вектор параметров модели, которая наилучшим образом приближает следущее значение временного ряда <tex>$x_{T+1}:\widehat{x}_{T+1}=f(\mathbf{x}, \mathbf{w})$</tex>.
Задача авторегрессионного прогноза заключается в нахождении модели <tex>$f(\mathbf{x}, \mathbf{w})$</tex>, где <tex>$\mathbf{w}\in\mathbb{R}^M$</tex> вектор параметров модели, которая наилучшим образом приближает следущее значение временного ряда <tex>$x_{T+1}:\widehat{x}_{T+1}=f(\mathbf{x}, \mathbf{w})$</tex>.
-
Свертка временного ряда возникает в случае существования на множестве подпоследовательностей временного ряда некоторого инварианта. Примером инварианта является период временного ряда, который физически может означать сезонность в данных. При этом построенная модель должна учитывать наличие инварианта и сохранять данное свойство для ряда прогнозов: <tex>$\{\widehat{x}_{t}\}_{t=1}^T\in\mathbb{R}^T$</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}=\{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>x_{T+1}</tex>.
+
Предполагается, модель временного ряда может меняться с течением времени, т.е. для разных подпоследовательностей длины <tex>p</tex> оптимальные параметры модели <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex> будут отличаться.
-
Построим матрицу <tex>n\times{p}</tex>
+
=== Расстояние между временными рядами ===
-
<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> можно вычислить как сумму квадратов отклонений:
-
\left(
+
-
\begin{array}{l|cc}
+
-
x_{T+1} & x_{T} & \ldots & x_{T+1-(p-1)} \\
+
-
x_{(n-1)p} & x_{(n-1)p-1} & \ldots & x_{(n-1)p-(p-1)} \\
+
-
\vdots & \vdots & \ddots & \vdots \\
+
-
x_{p} & x_{p-1} & \ldots & x_1 \\
+
-
\end{array}
+
-
\right)
+
-
</tex>.
+
-
Модель имеет вид <tex>\widehat{x}_{kp} = f \left (\{x_{kp-1},\dots,x_{kp-(p-1)}\}, \mathbf{w}\right)= \sum_{i=1}^u{\sum_{j=1}^{p-1}{\phi^i(x_{kp-j})\cdot{w_j^i}}</tex>, где <tex>1\leq{k}\leq{n-1}</tex>, а <tex>\{\phi_i\}_{i=1}^u-</tex> набор порождающих функций.
+
<center><tex>SSE=\sum_{i=1}^p{(x_{n_2{p}+i}-x_{n_1{p}+i})^2}.</tex></center>
 +
 
 +
Однако этот метод учитывает только расстояния между парами отсчетов временного ряда. Метод поиска пути минимальной стоимости (warping path)<ref>Keogh E. J., Pazzani M. J. Derivative Dynamic Time Warping International Conference on Data Mining (SDM’2001) 2001</ref> учитывает не только расстояние между отсчетами рядов, но и форму самих временных рядов.
 +
 
 +
Предположим, мы имеем две последовательности <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>\gamma_{i,j}</tex> до каждого элемента матрицы <tex>\Omeg</tex>:
 +
 
 +
<center><tex>\gamma_{i,j} = \omega_{i,j}+\min(\gamma_{i,j-1}, \gamma_{i-1,j}, \gamma{i-1, j-1}).</tex></center>
 +
 
 +
=== Расстояние между параметрами модели ===
 +
Расстояние между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, \mathbb{w})+\epsilon$</tex>, настроенной на разных подпоследовательностях, можно измерить как расстояние Кульбака-Лейблера между функциями распределения 2-ух случайных величин <tex>{p(w)},{q(w)}</tex>:
 +
<center><tex>D_{KL}(p, q) = \sum\limits_{w\in \mathcal{W}} p(w) \ln \frac{p(w)}{q(w)}.</tex></center>
 +
=== Постановка задачи ===
 +
Требуется исследовать зависимость расстояния между параметрами модели <tex>$\mathbf{x}=f(\mathbf{x}, w)+\epsilon$</tex> от расстояния между подпоследовательностями, на которых эти параметры были настроены.
== Алгоритм ==
== Алгоритм ==
-
В терминах поставленной задачи следует решить следующую задачу оптимизации: <tex>||\mathbf{y}- \mathbf{X}\mathbf{w}||_2\rightarrow\min_{\mathbf{w}}</tex>, где
+
 
-
<tex>
+
Для настройки параметров модели <tex>f(\mathbf{x}, \mathbf{w})+\epsilon</tex> используется [[Связанный Байесовский вывод|связный байесовский вывод]]
-
\left(
+
 
-
\begin{array}{l|ccccc}
+
<tex>\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|,</tex>
-
x_{(n-1)p} & \phi^1(x_{(n-1)p-1})&\dots &\phi^u(x_{(n-1)p-1})& \ldots & \phi^u(x_{(n-1)p-(p-1)}) \\
+
 
-
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\
+
где <tex>S(\mathbf{w})=\frac{1}{2}\mathbf{w}^TA\mathbf{w}+\beta E_D</tex> — функция ошибки,
-
x_{p} & \phi^1(x_{p-1})&\dots &\phi^u(x_{p-1})& \ldots & \phi^u(x_{1}) \\
+
 
-
\end{array}
+
<tex>H=-\nabla\nabla S(\mathbf{w})|_{\mathbf{w}=\mathbf{w_0}}</tex> — [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%93%D0%B5%D1%81%D1%81%D0%B5 матрица Гессе] функции ошибок,
-
\right)=
+
 
-
\left(
+
<tex>E_D=\frac{1}{2}\sum^n_{i=1}(\widehat{x_i}-x_i)^2</tex> — функция ошибки в пространстве данных.
-
\begin{array}{l|l}
+
 
-
\mathbf{y} & \mathbf{X}
+
Настройка параметрической регрессионной модели происходит в 2 этапа <ref>Стрижов В.В Методы выбора регрессионных моделей. — ВЦ РАН, 2010</ref>, сначала настраиваются параметры <tex>\mathbf{w}</tex> при фиксированных гиперпараметрах <tex>\beta, A</tex>, затем при вычисленных значениях параметров функция правдоподобия <tex>\ln p(D|\beta, A)</tex> оптимизируется по гиперпараметрам. Процедура повторяется, пока настраиваемые параметры не стабилизируется.
 +
 
 +
Для простоты вычислений, считаем, что<tex> A </tex> имеет диагональный вид:
 +
 
 +
<tex>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}
\end{array}
\right).
\right).
-
</tex>
+
</tex>.
-
Если зафиксировать набор порождающих функций <tex>\{\phi_i\}_{i=1}^u-</tex>, то возникает задача линейной регрессии, которую можно решать несколькими способами. Так как за счет большого количества порождающих функций у нас появится огромное количество признаков то наиболее подходящими будут методы, проводящие отбор признаков: [[ридж-регрессия|гребневая регрессия]], [[лассо|лассо]], [[шаговая регрессия|шаговая регрессия]], метод наименьших углов(ЛАРС).
+
== Вычислительный эксперимент ==
== Вычислительный эксперимент ==
 +
=== Пример на реальных данных ===
 +
[[Изображение:EnergyConsumptoin.png|thumb|left]]
 +
[[Изображение:DayPeriod.png|thumb|right]]
 +
Вычислительный эксперимент проводился на реальных данных. Использовались временные ряды потребления электроэнергии в некотором регионе с отсчетами 1 час, период ряда равен <tex>p=24</tex>.
 +
Эксперимент состоит из этапов:
 +
 +
'''1)''' из множества порождающих моделей:
 +
 +
<tex>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);
 +
</tex>
 +
 +
была построена их суперпозиция, описывающая потребление электроэнергии за сутки:
 +
 +
<center><tex>$$\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)+$$</tex></center>
 +
<center><tex>$$+w_{10}\cdot cos(t)+w_{12}\cdot t\cdot cos(t^3).$$</tex></center>
 +
 +
 +
[[Изображение:Series5.png|thumb|left]]
 +
[[Изображение:KL WarpingPath Distance.png|thumb|right]]
 +
 +
 +
'''2)''' модель настраивается на подпоследовательности
 +
 +
<tex>\mathbf{x}(n)=\{x_{pn+1},\dots,x_{pn+24}\}</tex>,
 +
 +
где <tex>n</tex> - номер суток. В результате получаем набор оптимальных параметров и гиперпараметров модели, оптимальных для данной подпоследовательности:
 +
<center><tex>\mathbf{w}(n), A(n), \beta(n)</tex></center>.
 +
 +
'''3)''' строится зависимость расстояния между последовательностями в пространстве параметров:
 +
 +
<center><tex> 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)} </tex>,</center> где <tex>p(w),q(w)</tex> - плотности распределений случайных величины из <tex>N(\mathbf{w}(n),A(n))</tex> и <tex>N(\mathbf{w}(m),A(m))</tex> соотвественно, и расстояний в пространстве значений:
 +
 +
[[Изображение:KL SSE Distance.png|thumb|right]]
 +
 +
<center><tex>Dintance \left( \mathbf{x}(n), \mathbf{x}(m) \right)=\sum_{t=1}^{24}\left( x_t(n)-x_t(m) \right)^2 </tex></center>
 +
 +
Результаты экспериментов на реальных данных показывают, что можно выделить среди множества пар временных рядов похожие и непохожие. Используя расстояние Кульбака-Лейблера между распределениями параметров моделей можно установить порог, который поможет определить похожие на заранее выделенный тип временных рядов. Для пояснения вышесказанного приведем пример на модельных данных, в которых участвуют временные ряды двух типов.
 +
 +
=== Пример на сгенерированных данных===
 +
[[Изображение:TestExample.png|thumb|left]]
 +
[[Изображение:GeterateSeries5.png|thumb|right]]
 +
 +
Проведен для для 6 моделей распределения данных:
 +
'''1)''' <tex>f(\mathbf{x},\mathbf{w}) = a_1 + b_1\cdot{t}+\epsilon</tex>, где <tex>\epsilon\in N(0, 1)</tex>;
 +
 +
'''2)''' <tex>f(\mathbf{x},\mathbf{w}) = a_1 + b_1\cdot{t}+\epsilon</tex>, где <tex>\epsilon\in N(0, 5)</tex>;
 +
 +
'''3)''' <tex>f(\mathbf{x},\mathbf{w}) = a_1-10*\sigma_{\epsilon} + b_1\cdot{t}+\epsilon</tex>, где <tex>\epsilon\in N(0, 1)</tex>, <tex>\sigma_{\epsilon}</tex> - дисперсия случайной величины;
 +
 +
'''4)''' <tex>f(\mathbf{x},\mathbf{w}) = a_1 + 1,5\cdot b_1\cdot{t}-t^2+\epsilon</tex>, где <tex>\epsilon\in N(0, 5)</tex>;
 +
 +
'''5)''' <tex>f(\mathbf{x},\mathbf{w}) = a_1 + 1,5\cdot b_1\cdot{t}-t^2+\epsilon</tex>, где <tex>\epsilon\in N(0, 10)</tex>;
 +
 +
'''6)''' <tex>f(\mathbf{x},\mathbf{w}) = a_1 -10*\sigma_{\epsilon} + 1,5\cdot b_1\cdot{t}-t^2+\epsilon</tex>, где <tex>\epsilon\in N(0, 5)</tex>.
 +
 +
Первые три модели относится в первому типу (line), три последних модели относятся ко второму типу (parabola).
 +
Прогнозирующая модель была линейной: <tex>\widehat{x}_{t}=w_1+w_2\cdot{t}</tex>.
 +
 +
[[Изображение:TestSample KL SSE Distance.png|thumb|left]]
 +
[[Изображение:TestSample KL WarpingPath Distance.png|thumb|right]]
 +
На тестовом примере видно, что чем больше расстояние между рядами в пространстве значений, тем скорее больше будет разница между распределениями настроенных параметров. На картинках можно явно разделить увидеть, что расстояние Кульбака-Лейблера между распределениями настроенных параметров для похожих моделей (line - line или parabola - parabola) значительно меньше расстояния между параметрами непохожих моделей (line-parabola или parabola-line). Таким образом можно настроить такой порог, по которому можно было бы определить, относится ли временной ряд к заранее фиксированному типу моделей.
 +
== Исходный код ==
== Исходный код ==
-
== Смотри также ==
+
[https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group874/Romanenko2010Compare/ Romanenko2010Compare]
 +
 
== Литература ==
== Литература ==
-
# {{книга
+
{{список примечаний}}
-
|автор = Стрижов В.В, Пташко Г.О.
+
 
-
|заглавие = Построение инвариантов на множестве временных рядов путем динамической свертки свободной переменной
+
{{ЗаданиеВыполнено|Алексей Романенко|В.В.Стрижов|24 декабря 2010||Strijov}}
-
|издательство = ВЦ РАН
+
[[Категория:Практика и вычислительные эксперименты]]
-
|год = 2009
+
-
}}
+
-
# {{книга
+
-
|автор = Стрижов В.В
+
-
|заглавие = Методы выбора регрессионных моделей
+
-
|издательство = ВЦ РАН
+
-
|год = 2010
+
-
}}
+

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

Содержание

Аннотация

Данная работа посвящена исследованию зависимости между пространственными характеристиками (форма, период) временного ряда[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). Таким образом можно настроить такой порог, по которому можно было бы определить, относится ли временной ряд к заранее фиксированному типу моделей.

Исходный код

Romanenko2010Compare

Литература


Данная статья была создана в рамках учебного задания.
Студент: Участник:Алексей Романенко
Преподаватель: В.В.Стрижов
Срок: 24 декабря 2010


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

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