Добрый день, уважаемые Хабровчане :) Продолжаем наши научные изыскания в области определения «синтетических» данных. В этой статье я рассмотрю тему анализа графов с позиции анализа спектров матрицы смежности для случайных матриц. То есть мы зайдём со стороны оптимизации знаний из прошлых двух статей (раз и два) и посмотрим, как применить теорию случайных матриц к нашей исходной задаче. Основная цель — расширение диапазона исследуемых значений. 

Итак, погнали, значицо ;) 

Теория случайных матриц изучает статистические свойства матрицы случайных чисел. Она много где «засветилась», например, активно используется в квантовой и ядерной физике, стохастической математике, теории чисел, финансовой статистике и даже компьютерных сетях. При этом основной задачей является выявление и анализ различных форм, корреляционных зависимостей и функциональных представлений. Эта область знания возникла в середине XX века благодаря работам венгерского математика Юджина Вигнера, когда он пытался объяснить особенности энергетического спектра атомных ядер. 

Приведу простой пример использования этой теории в работе с финансовыми рынками. Теория случайных матриц исследует спектральные характеристики ковариационных матриц цен акций. Основная идея заключается в следующем: матрица ковариаций строится на основании исторических цен актива, далее собственные значения и собственные векторы такой матрицы позволяют выявить рыночные режимы и шумы. После этого шумы обычно проявляются в виде распределений собственных значений, близких к теоретическому пределу Марченко-Пастура (Marčenko–Pastur distribution). Таким образом, отличительные паттерны среди шумового фона указывают на наличие систематической структуры данных. Получая подобные структуры, можно решать нашу задачу — определять «синтетические» данные. 

Ещё примеры использования случайных матриц в различных областях науки:

• Матрицы Уишарта (Wishart matrices): используются в статистике для описания многомерных выборочных ковариационных матриц. Формируются так: W = X^TX, где X — случайная матрица размером m×n. Распределение вероятностей элементов матрицы W подчиняется закону Уишарта: P(W)∝|W|^(N-p-1)/2e^-(tr(W))/2, здесь ∣W∣ — определитель матрицы, tr⁡(W) — след матрицы.

• Гауcсовский унитарный ансамбль (Gaussian Unitary Ensemble, GUE): класс симметричных комплекснозначных матриц, чьи действительные и мнимые части имеют нормальное распределение, при этом плотность вероятности такой матрицы имеет вид: P(A)∝e^{−2βN​∑∣aij​−aji​∣2}, где β=2 соответствует случаю гауссова ансамбля унитарной группы (U(N)).

• Ансамбли Лагерра (Laguerre ensembles): эта модель описывает распределение собственных значений специальных классов несимметричных матриц типа BB^∗, где B — произвольная прямоугольная матрица, и такое распределение плотностей собственных значений характеризуется функцией Лагерра: p_λ​(λ₁​,…,λ_n​)=∏​∣λ_j​−λ_ℓ​∣exp(−∑​λ_k).

Графы видимости и матрицы смежности

Применить эти подходы к разработанному в прошлой статье алгоритму графа видимости по эмбедингам можно следующим образом: 

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

2. Преобразование графа в матрицу смежности. Превращаем граф в бинарную матрицу смежности, где элемент (i,j) равен единице, если существует связь между узлами i и j, иначе — нулю. Я получил такую матрицу смежности:

3. Анализ спектра матрицы смежности с помощью теории случайных матриц. Рассчитываем спектр матрицы смежности, а также её собственные значения и собственные векторы. Затем анализируем плотность распределения собственных значений. Обычно шум представлен равномерным распределением (аналогично Марченко-Пастуру), тогда как характерные сигналы будут проявляться вне основного шума, который можно будет увидеть на спектре матрицы смежности (графа), определенного собственными значениями этой матрицы.

Распределение собственных значений обычно разделяют на два типа собственных значений: 

• большинство собственных значений сосредоточено вблизи нуля и образуют основное облако, называемое шумовым компонентом;

• а некоторые крупные собственные значения выделяются за пределами облака шума, характеризуя важные структурные аспекты данных (например, циклические явления, долгосрочные тенденции и аномалии). 

Значимые собственные значения соответствуют крупным компонентам данных и показывают направления максимальной вариации в пространстве данных. Их анализ позволяет идентифицировать фундаментальные особенности временного ряда, такие как периоды роста, падения, сезонности и трендовые изменения, в нашем случае — наличие паттернов «синтетических» данных.

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