Более эффективная реализация классификации тем на основе сжатия.

Недавно опубликованная статья под названием Малоресурсная классификация текста: метод безпараметрической классификации с использованием компрессоров [1] в последние дни привлекла внимание общественности. Их ключевой вывод заключается в том, что в некоторых случаях они могут превзойти большие языковые модели, такие как BERT, используя простую идею о том, что два текстовых документа более похожи, если их можно сжать до меньшего размера файла (хотя есть некоторые разногласия по поводу достоверности их результатов, см. это сообщение в блоге и это обсуждение, включая ответ автора).

Основная идея их подхода заключается в том, что «информационное расстояние» между двумя документами, как это определено Bennet et. al [2], является хорошей метрикой расстояния для использования во время классификации текста. Поскольку само информационное расстояние не поддается вычислению, они аппроксимируют его с помощью нормализованного расстояния сжатия (NCD) [3], который оценивает информационное расстояние с использованием «реальных» компрессоров данных, таких как gzip. NCD обладает тем свойством, что лучшие компрессоры (т. е. компрессоры с лучшей степенью сжатия) позволяют лучше оценить истинное информационное расстояние.

В таком случае кажется естественным ожидать, что более совершенный компрессор добьется лучших результатов в классификации. Но они не могут подтвердить это экспериментально; лучший компрессор, рассмотренный в статье, bz2, по точности уступает gzip. Они объясняют это следующим образом: «[…] алгоритм Берроуза-Уилера, используемый bz2, отбрасывает информацию о порядке символов, переставляя символы во время сжатия» [1, с.6817]. Это означает, что само по себе сжатие не объясняет их выводы, но оно также имеет какое-то отношение к порядку символов.

Это заставило меня задуматься: какая часть их результатов связана со сжатием, а какая — со сравнением строк между двумя документами?

Чтобы исследовать этот вопрос, я сравниваю их результаты с двумя альтернативами: (1) простой компрессор, основанный исключительно на замене повторяющихся строк, и (2) алгоритм, который явно выполняет сопоставление подстрок между документом запроса и всеми документами, относящимися к некоторой теме.

Первая абляция: выполнит ли LZ4 эту работу?
Алгоритм сжатия gzip основан на DEFLATE, который использует LZ77 и кодирование Хаффмана для сжатия данных. Давайте рассмотрим эти два алгоритма более подробно и подумаем, что они означают применительно к нашему варианту использования.

Во время сжатия LZ77 использует скользящее окно по ранее просмотренным данным. Если строка символов повторяется, вместо самой строки сохраняется ссылка на первое вхождение строки символов. Следовательно, если мы возьмем длину двух соединенных документов в качестве метрики расстояния, документы будут ближе друг к другу, если они имеют больше перекрывающихся подстрок в пределах размера скользящего окна (обычно 32 КБ).

Кодирование Хаффмана сжимает результирующий текст еще больше: вместо использования 8 битов для каждого символа оно представляет те буквы, которые встречаются часто, меньшим количеством битов, а те буквы, которые встречаются редко, большим количеством битов. Если мы применим кодирование Хаффмана к объединенным документам, два документа будут меньше после сжатия, если они используют символы с одинаковой частотой.

Можно было бы ожидать, что совпадающие подстроки будут гораздо важнее для классификации тем, чем одинаковые частоты символов. Поэтому я провожу исследование абляции, рассматривая производительность при использовании алгоритма LZ4 [4] для сжатия (в основном LZ77, но с быстрой реализацией, доступной в python). Поскольку LZ4 имеет гораздо более низкую степень сжатия, чем gzip, их объяснение предполагает, что производительность LZ4 хуже, чем у gzip. Если, однако, главное, что происходит, это сопоставление подстрок, LZ4 будет работать так же хорошо, как и gzip.

Более явный алгоритм
Чтобы пойти еще дальше, я реализую простой алгоритм, который явно выполняет сопоставление подстрок: он назначает документы теме с наиболее похожими подстроками (подстроки на уровне символов n -граммы здесь). Это работает следующим образом:

Кодирование текста:
1. Извлечь все n-граммы символов в тексте с 5 ≤ n ≤ 50.
2. Для извлеченных n-грамм вычислить 8-значный хэш-код, используя `hash(n_gram ) % int(10e8)` в python (поскольку я хочу контролировать, сколько разных вещей нужно отслеживать).
3. Отслеживать это в наборах (таким образом теряя информацию о том, сколько раз данный код встречается ).

Обучение:
1. Вычислить множество хэш-кодов для каждого текста заданной темы.
2. Взять объединение множества, чтобы получить множество хэш-кодов, встречающихся в теме.

Вывод:
1. Для некоторого текста запроса вычислить множество его хешированных n-грамм.
2. Для каждой темы, встречающейся во время обучения, вычислить размер пересечения между наборами тем и набором запросов. .
3. Назначьте текст запроса теме с наибольшим пересечением.

Эксперимент и результаты
Я сравниваю результаты gzip, lz4 и алгоритма хеширования n-грамм в настройке 100 выстрелов с 5 запусками, как описано в их статье. Для всех трех методов я придерживаюсь их экспериментальной установки, чтобы воспроизвести их результаты (опять же, оставляя нам потенциально завышенные показатели точности). Код можно найти на github.

Вы можете увидеть производительность на трех наборах данных из torchtext (AG_NEWS [5], DBpedia [6] и YahooAnswers [5]) в следующей таблице:

Мы видим, что lz4 и хешированные n-граммы превосходят gzip по всем трем рассмотренным наборам данных, при этом алгоритм хэшированных n-грамм лучше всего подходит для 2 из 3 данных. Но он по-прежнему не конкурирует с BERT, который имеет производительность 0,82 на AG_NEWS и близок к 1 на DBpedia, согласно их статье, при настройке 100 кадров.

Эти результаты имеют важные практические последствия: в нашем эксперименте алгоритм на основе lz4 работает примерно в 10 раз быстрее, чем алгоритм на основе gzip. И что еще более важно, алгоритм хеширования n-грамм даже повышает вычислительную сложность во время вывода: вместо того, чтобы сравнивать документ запроса с любым другим документом в текстовом корпусе, вам просто нужно провести сравнение с каждым набором тем.

Что мы извлекаем из этого?
Мои результаты показывают, что движущей силой впечатляющей производительности gzip, о которой сообщают, может быть тот факт, что их метод неявно сравнивает n-граммы на уровне символов между документы. Это открытие позволяет использовать более быстрые компрессоры, такие как lz4, без потери производительности. Кроме того, можно даже переписать их алгоритм, чтобы иметь постоянную сложность по отношению к размеру набора данных во время вывода, что делает их метод на большой шаг ближе к практическому использованию на больших наборах данных. Если вы хотите использовать его на практике, я начал реализацию предложенного мной алгоритма в соответствии с API scikit-learn здесь.

Остается один вопрос: почему это превосходит подход TF-IDF, который также сравнивает слова между документами?

Возможно, рассмотрение n-грамм на уровне символов лучше подходит для некоторых задач, чем разбиение текста на отдельные слова. Но, вероятно, более важно то, что метод здесь придает равный вес всем n-граммам, независимо от количества их вхождений. Это означает, что он придает большое значение так называемой длинной (читай: редкой) информации, которая, по-видимому, актуальна для некоторых текстовых задач, таких как определение темы. Обратите внимание, что трансформаторные сети не слишком хорошо справляются с моделированием такой информации с длинным хвостом (доказательства см., например, в [5]), поэтому эти очень простые подходы являются очень интересным эталоном для сравнения вашей модели с миллионом параметров. .

Ссылки
[1] Z. Jiang, M. Yang, M. Tsirlin, R. Tang, Y. Dai, J. Lin. Текстовая классификация с низким уровнем ресурсов: метод безпараметрической классификации с компрессорами (2023 г.), ACL 2023
[2] Ч. Х. Беннетт, П. Гач, М. Ли, П. М. Б. Витаньи и В. Х. Зурек, Информация расстояние (1998 г.), IEEE Transactions по теории информации.
[4] Н. Кандпал, Х. Денг, А. Робертс, Э. Уоллес, К. Раффел, Большие языковые модели борются за изучение знаний с длинным хвостом (2022), arxiv.org/abs/2211.08411

Спасибо Джоэлу Никлаусу и Марселю Гигли за наши обсуждения и ваши отзывы.