Вот мы хотим классифицировать текст. Классическая задача для ML. Поэтому в основном здесь рулят deep neural networks (отныне DNN).
Да, но:
- посчитай миллионы параметров
- поднеси тонну текста
- поднеси железо
- ой иди нахуй меня на таком не учили
А теперь помните кросс-энтропию? 3b1b видос выпускал. Это когда мы оцениваем, насколько хорошо одно распределение ложится на другое. А-ля в HPACK у HTTP2 вхардкоженная в стандарт таблица Хаффмана, строили по типичным для протокола сэмплам. А теперь представьте таким какой-нибудь бинарный код или кириллицу сжимать. Не-алфавитные символы в той таблице по 30 бит занимают, если что.
Ну так вот, какой-то чувак построил флоу-чарт, какие языки из каких происходят, и он даже был достаточно точным. Но вы щас будете ржать
Он просто брал тексты на одном языке, прилеплял к ним тексты на другом, и смотрел, как хорошо gzip это сожмёт.
Идея такая: чем ближе языки, тем ближе будут их распределения - похожие слова, похожие слоги, и прочие филологические говны.
В 2023 выходит интересная бумага. Даже не потому, что в ней буквально 5.5 авторов, из которых трое с очень китайскими фамилиями, и не менее американскими именами. А потому, что они gzip'ом тексты классифицируют.
И классифируют охуенно, при том. Делают буквально так же, как и с языками - склеивают два текста и смотрят, насколько хорошо оно пожалось.
Правда, интуиция тут немного другая. Энтропия по Шеннону - классическая теория информации - это скаляр от распределения. А есть её обобщение - сложность Колмогорова, она же алгоритмическая энтропия, она же да дохуя имён там. Она определена, как минимальная длина программы, способной воспроизвести данные целиком. В оригинале - программа для машины Тьюринга.
В таком обобщённом определении, сложность Колмогорова невычислима. Но ведь никто не мешает взять что-нибудь попроще, чем МТ?
Есть класс grammar-based компрессоров, например. Они пытаются построить грамматику текста, которая и выступает программой. Тогда всё становится возможным.
Вот и мы возьмём C(x) как аппроксимацию. Пусть она возвращает длину сжатой строки x.
Собственно, теперь нам остаётся взять информационное расстояние между двумя текстами. Китаймериканцы представили Normalized Compression Distance, определённую как
NCD(x,y) = (C(xy) - min(C(x), C(y))) / max(C(x), C(y))
(простите, у меня пока нет према, чтобы в латех писать)
Интуитивно - мы просто считаем, насколько хорошо тексты пожались вместе относительно того, как они пожались по-отдельности. Чем лучше компрессор, тем лучше аппроксимация, и тем точнее классификация. Из промышленных - точнее всех gzip, оптимальней всех zstd.
Собственно, вот и всё. Берём референсы (классы), и смотрим, к какому из них текст ближе всего.
Важное замечание - идея не новая, просто раньше брали датасет, и все сэмплы из него конкатенировали в один большой документ. И дальше уже считали, насколько конкретный текст близок к этому документу. Это, конечно, быстрее на маленьких выборках, но с большими - как вот YahooAnswers - работает весьма хуёво. Во-первых медленно, во-вторых компрессор тогда не в состоянии выудить из этого все преимущества выборки. Окно компрессора маловато.
Зато способ с попарным сравнением текста с каждым сэмплом датасета охуенно профитирует.
Для тестов взяли выпуски новостей. 7 in-distribution и 5 out-of-distribution датасетов - разница в том, что DNN в сравнениях обучали на первых семи, а остальные пять в выборки не входили. Это всякие филиппинские и хуй-выговоришь новости. И в результате...
...NCD был на уровне нейронок в in-distribution новостях. А out-of-distribution рвал, потому что компрессор в целом data-type-agnostic. Даже когда нейронки слегка пре-тренили. Ему поебать, если вы ещё не поняли. Он хоть самобытный диалект с 40 носителями пожмёт и сделает это с гордостью.
Так ещё и экологичнее, потому что видюхи ненужны. Нет, они реально об этом в бумаге написали.