Классификация текста без обучения: учёные предложили меру расстояния на основе вложенных повторов

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

На основе этих структур авторы определяют три меры расстояния между текстами: нормализованное расстояние сжатия (normalized compression distance, NCD), уже известный подход, использующий обычные алгоритмы сжатия (например, gzip), и две новые меры, выведенные напрямую из представления Ladderpath. Все три меры подаются на вход классификатору k ближайших соседей (k-NN), который относит текст к тому классу, чьи представители по этой мере расстояния оказались ближе всего.

Такая связка показала устойчиво высокие результаты сразу в трёх сценариях классификации текста: на данных того же распределения, что и обучающая выборка (in-distribution), на данных другого распределения (out-of-distribution, OOD) и в режиме few-shot, когда размеченных примеров крайне мало. Особо отмечается, что во всех трёх вариантах меры на основе Ladderpath и NCD обходят как классический NCD на gzip, так и модель BERT именно в условиях OOD и малых объёмов данных.

Авторы делают вывод, что структурные представления Ladderpath сохраняют внутренние свойства текстовых последовательностей и дают лёгкую, интерпретируемую и не требующую обучения альтернативу традиционным моделям для работы с текстом. Работа подчёркивает потенциал подходов на основе алгоритмической теории информации для структурного и предметно-независимого анализа последовательностей, то есть метода, который в принципе не завязан на конкретную предметную область или язык.

Ключевые факты

Метод Ladderpath извлекает вложенные и иерархические повторяющиеся подструктуры в тексте, опираясь на алгоритмическую теорию информации
На его основе построены три меры расстояния между текстами: классическое NCD (на сжатии, например gzip) и две новые меры из представления Ladderpath
Меры расстояния подаются в классификатор k ближайших соседей (k-NN), обучение модели не требуется
Проверка проведена на трёх типах задач классификации текста: in-distribution, out-of-distribution (OOD) и few-shot (мало примеров)
Во всех трёх сценариях, особенно в OOD и при малом объёме данных, новые меры обходят и gzip-based NCD, и BERT

Почему это важно

Работа продолжает линию, начатую несколько лет назад громкой находкой о том, что простое сжатие текста (gzip) в связке с k-NN может конкурировать с нейросетевыми классификаторами вроде BERT. Здесь авторы формализуют и расширяют эту идею через алгоритмическую теорию информации: вместо того чтобы полагаться только на то, насколько хорошо архиватор сжимает текст, они явно выделяют вложенную иерархию повторяющихся кусков текста (подход Ladderpath) и строят на этой структуре собственные меры расстояния. Результат, не разовое совпадение, а метод, показавший стабильное преимущество именно там, где нейросети обычно слабее: на данных другого распределения и при нехватке размеченных примеров.

Кому это важно

В первую очередь исследователям и инженерам, которым нужна классификация текста без затрат на обучение и дообучение модели, например, при работе с редкими языками, узкоспециализированными доменами или ситуациями, где размеченных данных мало или нет вовсе (few-shot). Также интересно тем, кто занимается интерпретируемыми и лёгкими (не требующими GPU и больших моделей) методами анализа текста как альтернативой тяжёлым трансформерам.

Как это применить

Метод не требует обучения: достаточно вычислить меру расстояния (NCD или одну из двух Ladderpath-мер) между новым текстом и размеченными примерами, а затем классифицировать его через k ближайших соседей, по большинству меток среди ближайших по расстоянию примеров. Это делает подход применимым там, где нет ресурсов на дообучение большой модели под конкретный домен, а также как быстрый baseline для сравнения с нейросетевыми классификаторами.

Можно ли доверять

Источник, препринт на arXiv, то есть результаты пока не прошли рецензирование в журнале или на конференции; текст на этом этапе представляет собой аннотацию (abstract) работы без деталей конкретных датасетов, числовых показателей качества и сравнения с более широким набором альтернативных методов. Общая идея (сжатие/структурные меры близости конкурируют с нейросетями на редких данных) уже подтверждалась в более ранних работах, что придаёт правдоподобие заявленным выводам, но детальную проверку методики и цифр можно дать только по полному тексту статьи.

Риски и подводные камни

Подходы на основе сжатия и структурного анализа последовательностей исторически плохо масштабируются на очень большие корпуса текста и длинные документы, вычисление меры расстояния для k-NN требует сравнения с каждым примером обучающей выборки, что может быть медленнее инференса нейросети на практике. Кроме того, преимущество над BERT заявлено именно для OOD и few-shot сценариев, не факт, что метод превосходит нейросетевые модели там, где размеченных данных достаточно и распределение данных типичное.