Добрый день, уважаемые хабражители! Как и прежде меня зовут Владимир Миронов, и я занимаюсь тестированием и оценкой синтетических данных ;) Добрались, наконец-то, до четвёртой части в этом цикле статей из (прошлые статьи можно увидеть тут, тут и тут). В этот раз разберём важный момент, связанный с анализом полученных матриц смежностей по нашим графам и представлением их свойств с позиции оптимизации и унификации. В общем, поговорим про алгоритмы, обсудим чисто технические моменты и подходы к унификации данных.
Всё идёт к тому, что интерпретируемое машинное обучение набирает всё больше оборотов, и необходима не только его визуализация, но и новые доказательные выкладки, и понимание границ формирования данных. Сформулирую несколько вопросов:
скорейшее обнаружение структур заданного порядка («синтетических» данных);
выявление первых признаков их появления на временном ряде и рассмотрение их конфигураций.
Более того, интересны будут и другие важные аспекты «жизни синтетики в дикой природе»:
Надо ли «просматривать» всю матрицу смежности по графу, или можно ограничится отдельными её областями? И сколько будет таких элементов применительно к данному типу задач?
Каков алгоритм представления указанных областей, каковы их свойства (мы частично уже выяснили эти моменты в прошлой статье), есть ли у них характерная геометрия, возможно ли её описать топологически или алгебраически?
Есть ли связь между найденными «синтетическими» элементами разных формаций?
Какую долю данных нам надо рассмотреть, чтобы промаркировать данные как «синтетику»?
Есть ли среди них «независимые» множества, которые никак не связаны с «массовыми» данными?
Это основные вопросы, которые хотелось бы осветить, или хотя бы понять, в какую сторону двигаться.
Анализ работ
Работа, на самом деле, более чем интересная и носит междисциплинарyый характер. Признаться честно, я люблю такое: взять данные из одной области и «подойти» к ним с инструментами из другой. Можно получить весьма интригующие результаты.
Напомню нашу задачу: максимально быстрое выявление макроструктуры сети, состоящей из нескольких плотно связанных компонентов («синтетических» данных) в уже построенном графе.
Почему возникают такие моменты и для чего нужно их выявлять? Сегодня есть множество инструментов для генерации «синтетики» (nlp-synt-data, synthetic-data-generator, awesome-synthetic-data, SynthEval, ydata-synthetic, sdg4idrr) и её обнаружения (LOKI (описание, и ещё тут и тут пара любопытных исследований)). Проблема в том, что степень и качество генерации постоянно повышается и агентные системы уже ведут себя практически автономно, поэтому требуется разработка новых методов для их анализа и оценки.
Отчасти мы это уже делали в прошлой работе, но хотелось бы копнуть в сторону оптимизации задачи и представления более фундаментальных оснований. Для этого надо было понять, как «прикрутить» уже известные решения к поиску «синтетических» данных в матрицах смежности. И вуаля — нашлось решение: представление скопления «синтетических» данных как структуры сообществ.
Более того, я нашёл подобную работу: «Finding community structure using the ordered random graph model» (Masaki Ochi, Tatsuro Kawamoto). Авторы предлагают новый алгоритм для упорядочивания матриц смежности, основанный на методе максимального правдоподобия. При этом предлагается использовать модели случайного графа с упорядоченными вершинами (Ordered Random Graph Model, OGRM). Алгоритм основан на максимизации вероятности матрицы смежности, учитывая её разделение на две области: внутреннюю (шардированная область около диагонали матрицы) и внешнюю.
Вероятность соединения между вершинами зависит от расстояния между ними относительно области. При применении метода максимума правдоподобия предлагается обновлять последовательность вершин таким образом, чтобы вершины внутри одной группы располагались близко друг к другу, формируя видимые блоки на визуализации матрицы смежности. Алгоритм позволяет выявить структуру сообществ гораздо точнее существующих классических методов упорядочивания матриц. Метод применили к синтетическим сетям и реальным данным. Результаты показывают эффективность предлагаемого подхода даже в сложных случаях смешанных структур.
При этом рассматривались еще дополнительные модели, которые также можно применить в работе:
Exponential random graph models: позволяют учитывать дополнительные зависимости между связями и характеристиками узлов, включая триангуляции, транзитивность и другие свойства реальной социальной динамики. Они обеспечивают гибкость в построении реалистичных сетевых топологий, учитывающих сложные взаимосвязи.
Stochastic block models: предполагают разделение узлов на группы (сообщества), внутри которых вероятность соединения отличается от межгрупповых соединений.
Small-world networks: переход от регулярных решётчатых структур к полностью случайным сетям посредством редкой вероятности перенаправления ребра.
Preferential attachment models: основаны на принципе, согласно которому новые узлы чаще всего подключаются к существующим вершинам с многочисленными связями.
Factorial Stochastic Block Models: позволяют выделять более сложную внутреннюю структуру, объединяя преимущества блочных моделей и факторизации матриц. Могут учитывать иерархию сообществ или скрытую организацию узлов.
Network growth and evolution models: пытаются смоделировать динамику развития сети, начиная с небольшого ядра и постепенно наращивая сеть новыми узлами и связями.
Решение
Не так давно анонсировали интерактивную теорема-доказывающая систему, разработанную Microsoft Research — Lean 4. Она является последней версией системы, выпущенной в 2023 году. Основное её предназначение — формализации математики и разработки программного обеспечения с высокой степенью надёжности. При этом есть уже достаточно много примеров использования Lean 4 для LLM с применением синтетических данных (раз, два, три, четыре). При этом удалось сформировать несколько теорем следующего порядка и основные идеи по ним. Они могут быть как доказаны, так и опровергнуты (я над этим пока думаю).
Теорема 1: о существовании регулярных паттернов в синтезированных данных
Формулировка: если сетевые эмбеддинги получены методом, основанным на стохастическом блочном моделировании (Stochastic Block Model, SBM), то при наличии существенных различий в связях между разными блоками графа существует непустое множество узлов, обладающих устойчивыми регулярными связями, выражающими признаки синтетических данных.
Предположение: рассмотрим графовую структуру эмбеддинга, полученную методом SBM. Поскольку SBM предполагает разделение узлов на блоки с разными плотностями внутренних и внешних связей, то в таком графе неизбежно появляются узлы, соединяющие преимущественно внутри своего блока («community») и редко вне его. Такие узлы образуют регулярные паттерны, присущие синтетическим данным.
Описание: рассмотрим граф G=(V,E), где V — множество узлов, E — множество рёбер. Предположим, что узлы разбиты на блоки V1,V2,…,Vk, причём плотность связей внутри блока заметно выше, чем между блоками. Обозначим плотность связей внутри блока pin и между блоками pbetween. Тогда пусть выполняется следующее неравенство: pin>pbetween.
Тогда существует множество узлов S⊆V, такое, что любой узел u∈S имеет гораздо больше соседей внутри своего блока, чем снаружи:
∣N(u)∩Vi∣/∣N(u)∣≥α, u∈Vi, i=1..k
где:
N(u) — множество соседей узла u;
α>0,5 — постоянная, характеризующая степень устойчивости связей.
Теорема 2: о минимальной длине пути между синтетическими узлами
Формулировка: если узел принадлежит группе синтетических данных, то расстояние (количество переходов по рёбрам) между ним и другим узлом той же группы ограничено сверху некоторой константой d{max}, зависящей от типа и масштаба данных.
Предположение: графовые эмбеддинги часто демонстрируют свойство малого мира (small-world property), означающее существование коротких путей между большинством пар узлов. Для синтетических данных этот эффект усиливается благодаря высокой внутренней когерентности узлов одного блока. Следовательно, максимальная длина пути d{max} для любого пары узлов из одной группы оказывается ограниченной и значительно меньше общего диаметра графа.
Описание: пусть G=(V,E) — граф, состоящий из k отдельных блоков, причём каждое соединение между узлами внутри блока подчиняется правилу предпочтения по связям (preferential attachment). Рассмотрим два узла u,v∈Vj, принадлежащих одному блоку j. Расстояние между ними D(u,v) определяется количеством рёбер вдоль кратчайшего пути между ними. Так как внутренняя структура блоков обусловлена сильным внутренним притяжением, справедливо утверждение:
∃ C > 0 : D(u,v) ≤ C log∣V∣,
где C — некоторая положительная константа, зависящая от размера графа и типа его организации. Она отражает small-world effect в структуре графа, который сильнее выражен в синтетических данных.
Теорема 3: о спектральных признаках синтетических данных
Формулировка: спектральные показатели (собственные значения матрицы Лапласа) для синтетических данных показывают статистически значимое отличие от аналогичных показателей реальных данных.
Предположение: собственные значения матрицы Лапласа зависят от структуры графа и отражают внутренние свойства соединений между узлами. В синтетических данных различия в связях внутри блоков приводят к изменению спектра собственных значений. Таким образом, сравнение спектров двух типов данных позволяет выявить присутствие синтетических фрагментов.
Описание: рассмотрим спектр матрицы Лапласа L(G)=D−A, где A — матрица смежности графа, D — диагональная матрица степеней вершин. Построим гистограмму собственных значений λi(L). В синтетических данных ожидается резкое увеличение концентрации собственных значений вблизи нуля, поскольку структура блока подразумевает большое количество низкоранговых узлов. Точнее, справедливы соотношения:
λ1 ≈ 0, ∣λ2−λn∣≫∣λ1−λ2∣
причём предполагается, что собственные значения будут сгруппированы около центра интервала [0,2], тогда как в природных данных спектр выглядит более равномерно распределённым.
Теорема 4: о существовании маркерных последовательностей
Формулировка: существуют уникальные последовательности символов или токенов, встречающиеся исключительно в синтетических наборах данных, что позволяет построить высокоэффективный классификатор.
Предположение: алгоритмы генерации синтетических данных используют определённые правила формирования текста, создающие шаблонные конструкции. Выявление таких конструкций позволяет создать классификационные модели, способные эффективно отделять синтетические данные от натуральных.
Описание: допустим, есть генератор синтетических данных, работающий по правилам условной вероятности токенов. Математически такую последовательность можно выразить через вероятность перехода p(wi∣wi−1,…,wi−n), где wi — токен на позиции i, а wi−j — предыдущие токены контекста длиной n. Допустим, существует некоторое слово-триггер T, встречающееся исключительно в синтетических данных. Вероятность встретить его удовлетворяет следующему критерию:
Pr(Tвстречается)={ε(для реальных данных) и α≫ε (для синтетических)}
где ε≪α — две постоянные, определяемые типом генератора. Выделяя маркеры подобного вида, можно создавать классификаторы, способствующие эффективному разделению синтетических и реальных данных.