Прогнозирование функциями дискретного аргумента (пример)

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

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

Версия 08:59, 6 сентября 2011

Содержание

1 Введение
2 Постановка задачи
3 Пути решения задачи
4 Литература

Введение

В статье представлена попытка прогнозирования таких специфических временных рядов, как монофонические мелодии. Были осуществлены три различных подхода: экспоненциальное сглаживание, локальное прогнозирование и поиск постоянных закономерностей.

Предлагается опробовать первый метод в традиционной его форме, чтобы ответить на вопрос, пригоден ли он для решения данной задачи. Затем предлагается во втором методе проверить работоспособность коэффициента корреляции Пирсона в качестве меры сходства. Третий будет использоваться в упрощенном варианте.

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

Мелодия есть функция $m: \ T \rightarrow X\times Y$ , где $T = 0, 1, 2, ...$ — позиция ноты, $X = 0, 1, 2, ...$ — конечное множество нот, занумерованных в порядке увеличения тона, $Y$ — длительность ноты, в секундах. Таким образом, будем работать с пучком из двух временных рядов.

Предполагается, что мелодия дана законченная, но без нескольких финальных нот(в данной статье одной). Необходимо их предсказать.

Пути решения задачи

Экспоненциальное сглаживание

Пусть $X=\{x_1, ... x_T\}$ — временной ряд.

Экспоненциальное сглаживание ряда осуществляется по рекуррентной формуле: $S_t=\alpha x_t + \left( 1-\alpha \right) S_{t-1},\ \alpha \in (0,1).$

Чем меньше $\alpha$ , тем в большей степени фильтруются, подавляются колебания исходного ряда и шума. Если последовательно использовать рекуррентное это соотношение, то экспоненциальную среднюю $S_t$ можно выразить через значения временного ряда $X$ . $S_t =\alpha x_t + (1-\alpha)\left( \alpha x_{t-1} + (1-\alpha)S_{t-2}\right)= \cdot\cdot\cdot = \alpha \sum_{i=0}^{t-1} (1-\alpha)^i x_{t-i} + (1-\alpha)^t S_0.$

После появления работ Р. Брауна экспоненциальное сглаживание часто используется для решения задачи краткосрочного прогнозирования временных рядов следующим способом. Пусть задан временной ряд: $y_i \cdot\cdot\cdot y_t,\; y_i \in R$ . Необходимо решить задачу прогнозирования временного ряда, т.е. найти

$\hat{y}_{t+d}=f_{t,d}\left(y_{1} ... y_{t} \right),\; d \in \{1,2, ... D\},\; D$ — горизонт прогнозирования, необходимо, чтобы

$Q_T=\sum_{i=1}^T \left( y_i-\hat{y}_i \right) \rightarrow \min$ .

Предположим, что D - невелико (краткосрочный прогноз), то для решения такой задачи используют модель Брауна. $\hat{y}_{t+d}=\alpha y_t + ( 1-\alpha ) \hat{y}_t,\; \hat{y}_0 = y_0,\; \alpha \in (0,1)$ . Если рассматривать прогноз на 1 шаг вперед, то $\left(y_t - \hat{y}_t\right)$ — погрешность этого прогноза, а новый прогноз $\hat{y}_{t+1}$ получается в результате корректировки предыдущего прогноза с учетом его ошибки — суть адаптации.

При краткосрочном прогнозировании желательно как можно быстрее отразить новые изменения и в то же время как можно лучше "очистить" ряд от случайных колебаний. Т.о. следует увеличивать вес более свежих наблюдений: $\alpha \rightarrow 1,\; \hat{y}_{t+d} \rightarrow y_t$ . С другой стороны, для сглаживания случайных отклонений, $\alpha$ нужно уменьшить: $\alpha \rightarrow 0,\; \hat{y}_{t+1} \rightarrow \bar{y}_t$ . Т.о. эти два требования находятся в противоречии. Мы будем брать $\alpha$ из интервала (0,0.5).

Локальные методы прогнозирования

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

Регулярной структурой назовем кусок временного ряда, обладающий автономностью по отношению к остальному временному ряду, склонный к повторению в немного искаженной форме. Очевидно, что "немного" должно определяться некой функцией близости. В работе использовался вариант коэффициента корреляции Неймана-Пирсона:

$k(f,g) = \frac{\int fg}{\sqrt{\int f^2}\cdot\sqrt{\int g^2}},$

где интеграл понимается в смысле суммы в силу дискретности функций. Прогноз будет строиться на естественном предположении компактности регулярных структур: у похожих кусков временного ряда должны быть похожие продолжения. Воспользуемся самым простым локальным алгоритмом, который ищет ближайшего соседа к прогнозируемому участку.

Поиск постоянных закономерностей

Рассмотрим один из подходов к поиску закономерностей в пучках временных рядов, который предполагает отсутствие изменений в закономерностях с течением времени. Для простоты будем рассматривать единственный временной ряд длины $T$ вместо пучка.

Маской $\omega$ на отрезке назовем булеву строку длины $N$ (здесь параметр $N$ определяет максимальный отступ по времени). Число единиц в маске $\omega$ будем называть весом маски и обозначать $H(\omega)$ . Элемент маски, находящийся на $i$ -ом месте будем обозначать $\omega(i)$ или $\omega_i$ . Закономерностью $R$ назовем пару $(\omega; f)$ , где маска $\omega$ указывает на значения ряда, являющиеся аргументами функции $f$ , а частично-определенная функция $f$ задает зависимость значений целевого ряда от переменных, на которые указывает маска $\omega$ .

$f: X^{H(\omega)} \rightarrow X\cup\{\lambda\},$

где $\lambda$ означает, что функция не определена на соответствующем наборе переменных.

Зафиксировав теперь маску $\omega = [1, 1, 1]$ , построим множество пар $(\alpha_t, v_t)$ , где $\alpha_t = [m(t), m(t+1), m(t+2)]$ , а $v_t = m(t+3)<tex>, <tex>t\in\{1, 2, \dots , T-3\}$ .

Полученное множество пар записывается в виде таблицы частот $\|\nu_{\alpha, v}\|$ с числом строк, равным числу всех возможных наборов из $X^{H(\omega)}=x^3$ , и числом столбцов, равным $|X|$ . Элемент таблицы частот $\|\nu_{\alpha, v}\| \ (0\le\alpha\le |X|^3-1,\ 0\le v\le |X|-1)$ — это число раз, которое значение $v$ встречается во входных данных на наборе $\tilde{\alpha}$ c номером $\alpha$ из $X^3$ .

(Предполагается, что наборы расположены в лексикографическом порядке.)

Обозначим $\nu_{\alpha, max} = \max_{v\in\{1, 2, \dots , |X|-1\}} \nu_{\alpha, v}$ и $v_{m} = \arg\max_{v\in\{1, 2, \dots , |X|-1\}} \nu_{\alpha, v}$ (в случае, если максимум достигается на нескольких значениях, $v_m$ выбирается среди этих значений произвольным образом).

Обозначим также $\nu_{\alpha, max-1} = \max_{v\in\{1, 2, \dots , |X|-1\}, v\ne v_m} \nu_{\alpha, v}$ и $\nu_{\alpha} = \sum_{v=0}^{|X|-1}\nu_{\alpha, v}$ .

На основе таблицы частот порождается закономерность $(\omega; f)$ , где частично-определенная функция $f$ задается на каждом наборе $\tilde{\alpha}$ из $X^3$ следующим образом:

$f(\tilde{\alpha}) = \left\{ \begin{array}{ll} v_m,\ if\ \nu_{\alpha, max}-\nu_{\alpha, max-1}\ge k\cdot\nu_{\alpha}\\ \lambda,\ else\end{array} \right.$

Здесь символ $\lambda$ обозначает отсутствие значения на данном наборе, а $k$ — параметр алгоритма, $0 < k < 1$ .

Литература

Данная статья является непроверенным учебным заданием.

Студент: Егор Будников

Преподаватель: В.В.Стрижов

Срок: 24 мая 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

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

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D0%B3%D0%BD%D0%BE%D0%B7%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F%D0%BC%D0%B8_%D0%B4%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D1%80%D0%B3%D1%83%D0%BC%D0%B5%D0%BD%D1%82%D0%B0_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»

Категории: Непроверенные учебные задания | Практика и вычислительные эксперименты

@@ Строка 23: / Строка 23: @@
 </tex>
-Чем меньше <tex>\alpha</tex>, тем в большей степени фильтруются, подавляются колебания исходного ряда и шума.
+Чем меньше <tex>\alpha</tex>, тем в большей степени фильтруются, подавляются колебания исходного ряда и шума. Если последовательно использовать рекуррентное это соотношение, то экспоненциальную среднюю <tex>S_t</tex> можно выразить через значения временного ряда <tex>X</tex>.
-Если последовательно использовать рекуррентное это соотношение, то экспоненциальную среднюю <tex>S_t</tex> можно выразить через значения временного ряда <tex>X</tex>.
 <tex>
 S_t =\alpha x_t + (1-\alpha)\left( \alpha x_{t-1} + (1-\alpha)S_{t-2}\right)= \cdot\cdot\cdot = \alpha \sum_{i=0}^{t-1} (1-\alpha)^i x_{t-i} + (1-\alpha)^t S_0.
 </tex>
-После появления работ Р. Брауна экспоненциальное сглаживание часто используется для решения задачи краткосрочного прогнозирования временных рядов следующим способом.
+После появления работ Р. Брауна экспоненциальное сглаживание часто используется для решения задачи краткосрочного прогнозирования временных рядов следующим способом. Пусть задан временной ряд: <tex>y_i \cdot\cdot\cdot y_t,\; y_i \in R</tex>.
-Пусть задан временной ряд: <tex>y_i \cdot\cdot\cdot y_t,\; y_i \in R</tex>.
 Необходимо решить задачу прогнозирования временного ряда, т.е. найти
@@ Строка 42: / Строка 39: @@
 Если рассматривать прогноз на 1 шаг вперед, то <tex>\left(y_t - \hat{y}_t\right)</tex> — погрешность этого прогноза, а новый прогноз <tex>\hat{y}_{t+1}</tex> получается в результате корректировки предыдущего прогноза с учетом его ошибки — суть адаптации.
-При краткосрочном прогнозировании желательно как можно быстрее отразить новые изменения и в то же время как можно лучше "очистить" ряд от случайных колебаний.
+При краткосрочном прогнозировании желательно как можно быстрее отразить новые изменения и в то же время как можно лучше "очистить" ряд от случайных колебаний. Т.о. следует увеличивать вес более свежих наблюдений:
-Т.о. следует увеличивать вес более свежих наблюдений:
 <tex>
 \alpha \rightarrow 1,\; \hat{y}_{t+d} \rightarrow y_t
 </tex>.
-С другой стороны, для сглаживания случайных отклонений, <tex>\alpha</tex> нужно уменьшить: <tex> \alpha \rightarrow 0,\; \hat{y}_{t+1} \rightarrow \bar{y}_t</tex>.
+С другой стороны, для сглаживания случайных отклонений, <tex>\alpha</tex> нужно уменьшить: <tex> \alpha \rightarrow 0,\; \hat{y}_{t+1} \rightarrow \bar{y}_t</tex>. Т.о. эти два требования находятся в противоречии. Мы будем брать <tex>\alpha</tex> из интервала (0,0.5).
-Т.о. эти два требования находятся в противоречии. Мы будем брать <tex>\alpha</tex> из интервала (0,0.5).
 <b><big>Локальные методы прогнозирования</big></b>
@@ Строка 54: / Строка 49: @@
 Музыкальный временной ряд отличается от обычного хаотического: он почти не хаотичен. В нем встречаются похожие, повторяющиеся и прочие регулярные структуры.
-<i>Регулярной структурой</i> назовем кусок временного ряда, обладающий автономностью по отношению к остальному временному ряду, склонный к повторению в немного искаженной форме.
+<i>Регулярной структурой</i> назовем кусок временного ряда, обладающий автономностью по отношению к остальному временному ряду, склонный к повторению в немного искаженной форме. Очевидно, что "немного" должно определяться некой функцией близости. В работе использовался вариант коэффициента корреляции Неймана-Пирсона:
-Очевидно, что "немного" должно определяться некой функцией близости. В работе использовался вариант коэффициента корреляции Неймана-Пирсона:
 <center><tex>k(f,g) = \frac{\int fg}{\sqrt{\int f^2}\cdot\sqrt{\int g^2}},</tex></center>
-где интеграл понимается в смысле суммы в силу дискретности функций.
+где интеграл понимается в смысле суммы в силу дискретности функций. Прогноз будет строиться на естественном предположении компактности регулярных структур: у похожих кусков временного ряда должны быть похожие продолжения. Воспользуемся самым простым локальным алгоритмом, который ищет ближайшего соседа к прогнозируемому участку.
-Прогноз будет строиться на естественном предположении компактности регулярных структур: у похожих кусков временного ряда должны быть похожие продолжения.
-Воспользуемся самым простым локальным алгоритмом, который ищет ближайшего соседа к прогнозируемому участку.
 <b><big>Поиск постоянных закономерностей</big></b>
@@ Строка 76: / Строка 68: @@
 (Предполагается, что наборы расположены в лексикографическом порядке.)
-Обозначим <tex>\nu_{\alpha, max} = \max_{v\in\{1, 2, \dots , |X|-1\}} \nu_{\alpha, v}</tex> и <tex>v_{m} = \arg\max_{v\in\{1, 2, \dots , |X|-1\}} \nu_{\alpha, v}</tex> (в случае, если максимум достигается на нескольких значениях, <tex>v_m</tex> выбирается среди этих значений произвольным образом).
+Обозначим
+<tex>\nu_{\alpha, max} = \max_{v\in\{1, 2, \dots , |X|-1\}} \nu_{\alpha, v}</tex>
+и
+<tex>v_{m} = \arg\max_{v\in\{1, 2, \dots , |X|-1\}} \nu_{\alpha, v}</tex>
+(в случае, если максимум достигается на нескольких значениях, <tex>v_m</tex> выбирается среди этих значений произвольным образом).
 Обозначим также <tex>\nu_{\alpha, max-1} = \max_{v\in\{1, 2, \dots , |X|-1\}, v\ne v_m} \nu_{\alpha, v}</tex> и <tex>\nu_{\alpha} = \sum_{v=0}^{|X|-1}\nu_{\alpha, v}</tex>.

Прогнозирование функциями дискретного аргумента (пример)

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

Версия 08:59, 6 сентября 2011

Содержание

Введение

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

Пути решения задачи

Литература

Просмотры

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

Навигация

Поиск

Инструменты