В своей статистике Кеннел использует квадрат евклидова расстояния:
Где - -ый ближайший сосед вложенного вектора .
Применив логику, изложенную выше, мы можем перейти от -мерного пространства к -мерному пространству, добавив новое квадратное расстояние между и тем же -ым ближайшим соседом:
Как упоминалось ранее, если одномерный временной ряд уже правильно вложен в измерений, то расстояние между соседями не должно сильно изменяться и будет оставаться в рамках какого-то критерия :
Кеннел предложил в качестве стандартного значения.
Применение этого метода к каждому ближайшему соседу каждого наблюдения приведет к нахождению нескольких или отсутствию ближайших ложных соседей, если вложение было достаточным. Таким образом, мы можем подсчитать количество ближайших ложных соседей, которые не удовлетворяют критерию (2.10) и подсчитать их процентное содержание:
Где - количество вложенных векторов.
Тогда для наименьшего достаточного количества измерений , должно стремиться к нулю.
Тем не менее, для ограниченного числа наблюдений Кеннел заметил, что одного критерия (2.10) может быть недостаточно, поэтому предложил еще второй критерий для нахождения ложных ближайших соседей:
Где - размерность перестроенного аттрактора, которая оценивается как:
Где . В своей работе Кеннел предложил в качестве стандартной статистики.
21.5.2 Средние ложные соседи
Несмотря на относительную простоту применения метода ближайших ложных соседей по Кеннелу, Цао в своей работе (Cao, 1997) заметил, что метод может быть слишком чувствителен к свободным параметрам и при зашумленности данных. В связи с этим Цао предложил свой метод усредненных ложных соседей, который учитывает среднее изменение расстояния между вектором и его ближайшим соседом при увеличении размерности вложения.
Для начала, для каждого вектора находится отношение как:
Где расстояние в отличие от евклидова расстояния в формуле (2.8) рассчитывается с помощью максимальной нормы между векторами, известной также как расстояние Чебышева, что позволяет сократить время вычисления:
Чтобы избежать выбор свободных параметров для критериев (2.10) и (2.12), Цао предложил рассчитывать среднее значение всех как:
Тогда при переходе к -мерному пространству можем вывести следующую переменную:
Цао в своей работе выявил, что значение стабилизируется, когда достигает оптимального значения размерности вложения. Так как для случайного набора данных никогда не стабилизируется, автор посчитал необходимым также отличать детерминистическую хаотическую систему от случайных последовательностей и предложил следующую метрику , которая оценивается как:
Тогда при переходе к -мерному пространству получаем
Так как для случайного набора данных будущие значения никак не связаны с прошлыми значениями, будет единым для любого . В отличие от случайных данных детерминистические системы зависят от размерности , поэтому для них должны существовать значения Таким образом, Цао в своей работе рекомендует считать оба показателя и для определения оптимального .
21.6 Предсказание значений во вложенном пространстве
21.6.1 Ближайшие соседи
Способы прогнозирования в рамках метода вложенных координат имеют долгую и богатую историю в анализе нелинейной динамики. Например, в 1969 году Лоренц предложил свой метод аналогов, который ищет известную траекторию состояния пространства для ближайшего соседа данной точки и принимает путь этого соседа в качестве прогноза (Lorenz, 1969). В контексте статистических подходов для обучения метод известен как метод ближайших соседей. Вместо использования тренировочных выборок для обучения в модели выполняется поиск по прошлым наблюдениям, которые затем используются в качестве предикторов. В прогнозировании временных рядов алгоритм выбирает прошлые последовательности, похожие на текущую, и использует их для точечного прогноза.
Для динамической системы набор векторов в определенный момент времени описывается как , где некая эволюционная функция. Допуская, что отображение в дискретном времени является непрерывным относительно своего аргумента, мы можем предсказать будущее состояние с помощью поиска прошлых состояний наиболее близких к . Если состояние близко к состоянию , то предположение о непрерывности гарантирует, что состояние будет близко к (Moore & Little, 2014).
Для -мерного вложенного пространства простой предикат является средним значением соседствующих векторов:
Где - следующая точка после вложенного вектора , - окрестность радиуса и , а -свободный параметр количества ближайших соседей.
Муур и Литтл в своей работе предложили небольшие модификации для метода ближайших соседей:
В формуле (2.20) предполагается, что прогнозные вектора близки к текущему состоянию . Однако в случае, когда ложные ближайшие вектора попадают в окрестность, это предположение нарушается. Последствия этого эффекта устраняются с помощью использовании медианы вместо среднего в качестве предиката:
Для временных рядов, полученных из детерминированных систем, где динамика системы фиксирована и известна и можно точно оценить значения временного лага и количества измерений , использование минимального радиуса окрестности для выбора прогнозных векторов обеспечивает наиболее точную аппроксимацию к текущему состоянию. Однако если оптимальное измерение для вложения неизвестно, произвольный радиус грозит попаданием ложных ближайших векторов в окрестность. Чтобы решить эту проблему, авторы используют фиксированный радиус окрестности, снижая порядок измерения для вложения для поиска векторов.
21.6.2 Регрессия опорных векторов
Метод опорных векторов является одним из наиболее популярных алгоритмов машинного обучения, который используется для задач линейной и нелинейной классификации и регрессии. В отличие от обычной задачи классификации, где мы пытаемся найти такую разделяющую гиперплоскость, которая приводит к максимально длинному расстоянию между двумя классами, регрессия опорных векторов несет в себе цель уместить как можно больше наблюдений между найденными опорными векторами. Таким образом, нам необходимо найти некую линейную функцию :
Тогда в случае линейно-неразделимой выборки мы приходим к следующей постановке задачи (Vapnik, 1995):
Где так называемые слак параметры, которые вводятся в качестве эвристики, чтобы перейти от линейно разделимых выборок к линейно-неразделимым; некая погрешность, в рамках которой мы позволяем значениям нашей регрессии отклоняться; некая константа, которая отражает чувствительность к отклонениям . Графическую интерпретацию можно увидеть на Рис. 2.
Рис. 2. Регрессия опорных векторов
В литературе (2.22) называют задачей квадратичного программирования с линейными ограничениями-неравенствами, которая решается сведением к двойственной задаче, используя множители Лагранжа (Fletcher, 1989):
Где Лагранжиан с множителями больше нуля.
Также должны соблюдаться необходимые условия седловой точки функции Лагранжа:
Где относится к и .
Подставив (2.24) в (2.23) получаем следующую двойственную задачу:
Тогда решение прямой задачи выражается через решение двойственной:
Таким образом, мы находим искомую функцию в (2.26). Более подробное решение задачи квадратичного программирования (2.22) можно найти в (Smola & Schцlkopf, 2004).
Стоит отметить, что мы можем перейти к нелинейной регрессии опорных векторов путем замены скалярного произведения на нелинейную функцию , чтобы перейти к пространству более высокой размерности.
Приведем пример квадратичного ядра, описанного у Вапника (1995). Пусть , где . Тогда найдем преобразование , при которых . Для этого разложим квадрат скалярного произведения:
Таким образом, . Линейной поверхности в пространстве соответствует квадратичная поверхность в исходном пространстве .
21.7 Оценка точности предсказаний
В качестве численной меры точности предсказания мы вычисляем среднюю абсолютную масштабированную ошибку (MASE) между прогнозными и реальными значениями:
Масштабирование осуществляется с помощью среднего значения прогнозной ошибки случайного блуждания в знаменателе. Таким образом, если значение , то прогнозная ошибка была в среднем меньше, чем ошибка прогнозных значений, полученных с помощью случайного блуждания.
Глава 3
2. Синтетические примеры
32.1 Синтетический пример анализа методом вложенных координат
В этом разделе приводится синтетический пример анализа временных рядов с помощью метода вложенных координат по Такенсу, чтобы дать читателю интуитивное понимание метода, используемого в этой работе. Как уже упоминалось ранее, синтетические данные, полученные из динамических систем, являются детерминированными, поэтому мы сможем точно определить значения временного лага и количества измерений для вложения. В качестве детерминистической хаотической системы мы рассмотрим ранее затрагиваемый аттрактор Рёсслера.
32.2 Аттрактор Рёсслера
Пожалуй, одна из самых популярных хаотических систем была представлена Рёсслером в 1976. Система состоит из трех обычных дифференциальных уравнений:
С постоянными параметрами и начальными значениями . Хаотический аттрактор Рёсслера, используемый в нашем примере изображен на Рис. 3.
Рис. 3. Аттрактор Рёсслера при постоянных a=0.2,b=0.2,c=5.7
Рис. 4. Первые 500 значений из аттрактора Рёсслера
Сгенерировав 10 тыс. значений из системы Рёсслера, мы можем приступить к поиску свободных параметров временного лага и количества измерений для вложения.
32.2.1 Оценка временного лага
Основываясь на методах из главы (2.4), сравним оценки временного лага, полученные с помощью автокорреляционной функции и первого локального минимума функции взаимной информации.
Как видно из Рис. 5, значения временного лага совпадает для первого нуля автокорреляционной функции и первого локального минимума функции взаимной информации.
Рис. 5. Оценка временного лага ф для аттрактора Рёсслера
Временной ряд с лагом из аттрактора Рёсслера при значении изображен на Рис. 6.
Рис. 6. Аттрактор Рёсслера с временным лагом ф=14
32.2.2 Оценка количества измерений
Оценив временной лаг, можем приступить к оценке размерности вложения . Как уже обсуждалось в главе (2.5), одним из подходов для оценки размерности вложения является метод ближайших ложных соседей по Кеннелу.
Рис. 7. Ближайшие ложные соседи для аттрактора Рёсслера при лаге ф=14
Судя по количеству ближайших ложных соседей для набора измерений из Рис. 7, оптимальной размерностью для вложения является , где процент ложных соседей стремится к нулю для обоих критериев (см. формулы (2.10) и (2.12)).
Тем не менее, в соответствии с вторым требованием классической теоремы вложенных координат (см. Глава 21.3) оптимальная размерность вложения должна быть больше , где - истинное измерение лежащей в основе динамики, которое для аттрактора Рёсслера равно двум. Следовательно, оптимальная размерность вложения должна быть .
Чтобы подтвердить это, применим алгоритм среднего ложного соседа и оценим оптимальное измерение по критерию (2.17).
Рис. 8. Средние ложные соседи для аттрактора Рёсслера при лаге ф=14
Из Рис. 8 можем заметить, что значение стабилизируется в при . Также значение для многих значений не равно единице, что говорит нам о принадлежности данных к детерминистической системе.
23.2.3 Вложение и предсказание
Зная временной лаг и количество измерений , мы можем вложить исходные данные по Такенсу на основе формулы (2.2). Так как данные принадлежат к детерминистической системе, в качестве входных данных для модели подаются вложенные вектора , а на выходе мы должны получить предсказание последующего вектора .
Стоит отметить, что используемый классификатор ближайшего соседа немного отличается от модели, представленной в Главе 12.6.1: чтобы избежать выбор радиуса окрестности для ближайших соседей, на практике, как правило, используется поиск по дереву решений. В частности, в нашей работе мы используем реализацию BallTree из библиотеки scikit-learn для Python. В отличие от привычного KDtree, выбранный метод хорошо справляется с задачей поиска ближайших соседей при увеличении размерности пространства (Kibriya & Frank, 2007; Kumar, Zhang, & Nayar, 2008).