Генерация синтетических данных для LLM. Часть 4: теоремы

Добрый день, уважаемые хабражители! Как и прежде меня зовут Владимир Миронов, и я занимаюсь тестированием и оценкой синтетических данных ;) Добрались, наконец-то, до четвёртой части в этом цикле статей из (прошлые статьи можно увидеть тут ^[1], тут ^[2] и тут ^[3]). В этот раз разберём важный момент, связанный с анализом полученных матриц смежностей по нашим графам и представлением их свойств с позиции оптимизации и унификации. В общем, поговорим про алгоритмы, обсудим чисто технические моменты и подходы к унификации данных. 

Всё идёт к тому, что интерпретируемое машинное обучение ^[4] набирает всё больше оборотов, и необходима не только его визуализация, но и новые доказательные выкладки, и понимание границ формирования данных. Сформулирую несколько вопросов: 

• скорейшее обнаружение структур заданного порядка («синтетических» данных); 

• выявление первых признаков их появления на временном ряде и рассмотрение их конфигураций. 

Более того, интересны будут и другие важные аспекты «жизни синтетики в дикой природе»: 

• Надо ли «просматривать» всю матрицу смежности по графу ^[5], или можно ограничится отдельными её областями? И сколько будет таких элементов применительно к данному типу задач?

• Каков алгоритм представления указанных областей, каковы их свойства (мы частично уже выяснили эти моменты в прошлой статье ^[3]), есть ли у них характерная геометрия, возможно ли её описать топологически или алгебраически?

• Есть ли связь между найденными «синтетическими» элементами разных формаций?

• Какую долю данных нам надо рассмотреть, чтобы промаркировать данные как «синтетику»?

• Есть ли среди них «независимые ^[6]» множества, которые никак не связаны с «массовыми» данными?

Это основные вопросы, которые хотелось бы осветить, или хотя бы понять, в какую сторону двигаться.

Анализ работ

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

Напомню нашу задачу: максимально быстрое выявление макроструктуры сети, состоящей из нескольких плотно связанных компонентов («синтетических» данных) в уже построенном графе. 

Почему возникают такие моменты и для чего нужно их выявлять? Сегодня есть множество инструментов для генерации «синтетики» (nlp-synt-data ^[7], synthetic-data-generator ^[8], awesome-synthetic-data ^[9], SynthEval ^[10], ydata-synthetic ^[11], sdg4idrr ^[12]) и её обнаружения (LOKI ^[13] (описание ^[14], и ещё тут ^[15] и тут ^[16] пара любопытных исследований)). Проблема в том, что степень и качество генерации постоянно повышается и агентные системы уже ведут себя практически автономно ^[17], поэтому требуется разработка новых методов для их анализа и оценки. 

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

Более того, я нашёл подобную работу: «Finding community structure using the ordered random graph model ^[18]» (Masaki Ochi, Tatsuro Kawamoto). Авторы предлагают новый алгоритм для упорядочивания матриц смежности, основанный на методе максимального правдоподобия ^[19]. При этом предлагается использовать модели случайного графа с упорядоченными вершинами (Ordered Random Graph Model ^[20], OGRM). Алгоритм основан на максимизации вероятности матрицы смежности, учитывая её разделение на две области: внутреннюю (шардированная область около диагонали матрицы ^[21]) и внешнюю. 

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

При этом рассматривались еще дополнительные модели, которые также можно применить в работе:

• Exponential random graph models ^[22]: позволяют учитывать дополнительные зависимости между связями и характеристиками узлов, включая триангуляции, транзитивность и другие свойства реальной социальной динамики. Они обеспечивают гибкость в построении реалистичных сетевых топологий, учитывающих сложные взаимосвязи.

• Stochastic block models ^[23]: предполагают разделение узлов на группы (сообщества), внутри которых вероятность соединения отличается от межгрупповых соединений.

• Small-world networks ^[24]: переход от регулярных решётчатых структур к полностью случайным сетям посредством редкой вероятности перенаправления ребра.

• Preferential attachment models ^[25]: основаны на принципе, согласно которому новые узлы чаще всего подключаются к существующим вершинам с многочисленными связями.

• Factorial Stochastic Block Models ^[26]: позволяют выделять более сложную внутреннюю структуру, объединяя преимущества блочных моделей и факторизации матриц. Могут учитывать иерархию сообществ или скрытую организацию узлов.

• Network growth and evolution models ^[27]: пытаются смоделировать динамику развития сети, начиная с небольшого ядра и постепенно наращивая сеть новыми узлами и связями.

Решение

Не так давно анонсировали интерактивную теорема-доказывающая систему, разработанную Microsoft Research — Lean 4. Она является последней версией системы, выпущенной в 2023 году. Основное её предназначение — формализации математики ^[28] и разработки программного обеспечения с высокой степенью надёжности. При этом есть уже достаточно много примеров использования Lean 4 для LLM с применением синтетических данных (раз ^[29], два ^[30], три ^[31], четыре ^[32]). При этом удалось сформировать несколько теорем следующего порядка и основные идеи по ним. Они могут быть как доказаны, так и опровергнуты (я над этим пока думаю).

Теорема 1: о существовании регулярных паттернов в синтезированных данных

Формулировка: если сетевые эмбеддинги получены методом, основанным на стохастическом блочном моделировании (Stochastic Block Model, SBM ^[33]), то при наличии существенных различий в связях между разными блоками графа существует непустое множество узлов, обладающих устойчивыми регулярными связями, выражающими признаки синтетических данных.

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

Описание: рассмотрим граф G=(V,E), где V — множество узлов, E — множество рёбер. Предположим, что узлы разбиты на блоки V₁,V₂,…,V_k, причём плотность связей внутри блока заметно выше, чем между блоками. Обозначим плотность связей внутри блока p_in и между блоками p_between​. Тогда пусть выполняется следующее неравенство: p_in​>p_between.

Тогда существует множество узлов S⊆V, такое, что любой узел u∈S имеет гораздо больше соседей внутри своего блока, чем снаружи:

∣N(u)∩V_i​∣/∣N(u)∣​≥α, u∈V_i​, i=1..k

где:

• N(u) — множество соседей узла u;

• α>0,5 — постоянная, характеризующая степень устойчивости связей.

Теорема 2: о минимальной длине пути между синтетическими узлами

Формулировка: если узел принадлежит группе синтетических данных, то расстояние (количество переходов по рёбрам) между ним и другим узлом той же группы ограничено сверху некоторой константой d{max}, зависящей от типа и масштаба данных.

Предположение: графовые эмбеддинги часто демонстрируют свойство малого мира (small-world property ^[34]), означающее существование коротких путей между большинством пар узлов. Для синтетических данных этот эффект усиливается благодаря высокой внутренней когерентности узлов одного блока. Следовательно, максимальная длина пути 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, ∣λ₂​−λ_n​∣≫∣λ₁​−λ₂​∣

причём предполагается, что собственные значения будут сгруппированы около центра интервала [0,2], тогда как в природных данных спектр выглядит более равномерно распределённым.

Теорема 4: о существовании маркерных последовательностей

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

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

Описание: допустим, есть генератор синтетических данных, работающий по правилам условной вероятности токенов. Математически такую последовательность можно выразить через вероятность перехода p(w_i∣w_i−1,…,w_i−n), где w_i​ — токен на позиции i, а w_i−j​ — предыдущие токены контекста длиной n. Допустим, существует некоторое слово-триггер T, встречающееся исключительно в синтетических данных. Вероятность встретить его удовлетворяет следующему критерию:

Pr(Tвстречается)={ε(для реальных данных) и α≫ε ​(для синтетических)}​

где ε≪α — две постоянные, определяемые типом генератора. Выделяя маркеры подобного вида, можно создавать классификаторы, способствующие эффективному разделению синтетических и реальных данных.