Тема, о которой я хочу вам рассказать, появилась не из-за какого-то оглушительного успеха, громкого провала или желания поделиться каким-то сакральным знанием с и так уже максимально искушённым читателем Хабра. Равно как эта тема не была плодом долгой и кропотливой работы — её не планировали, почти не обсуждали и тем более не утверждали заранее.

Всё выглядело как приключение, после которого остались настолько тёплые воспоминания, что захотелось ими поделиться. Проникнитесь и вы духом приключения, желанием разгадывать загадки и чувством восстановленной справедливости!

И как говорил известный персонаж: «Давай, вошли и вышли, приключение на 20 минут».

Начало приключения

Антиплагиат, несомненно, известен своими решениями по поиску заимствований. Наши возможности растут, а планы воистину грандиозны. К примеру, уже запущен сервис поиска переводных заимствований для сотни языков, среди которых есть и сравнительно редкие: аварский, якутский, эрзянский и т. п.

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

Итак, дано какое-то количество fastText-моделей для редких языков. Каждая из них весит несколько гигабайт, что для моделей fastText обычное дело. Размеры этих моделей были сопоставимы с размерами моделей для популярных языков. Однако корпусы текстов, на которых обучаются модели для популярных языков, и корпусы редких языков (на которых обучались наши модели) по своим размерам отличаются на порядки — количество уникальных слов в корпусах редких языков чаще значительно меньше. Как минимум этот факт порождает подозрение, что имеет место какая-то неэффективность или несправедливость.

А можно ли сократить или сжать модель без потерь? Конечно, можно! Ведь об этом писали и уже предложили интересные решения для fastText-моделей популярных языков Андрей Васнецов (на Medium) и Давид Дале (на Хабре, @cointegrated). Здесь же будет акцент именно на то, что языки редкие. Но, прежде чем двигаться дальше, давайте вкратце разберёмся, что такое этот fastText и эмбеддинги слов.

Что такое эмбеддинги

Для анализа текстов хорошо бы понимать смысл написанного.

А как, например, сравнивать между собой по смыслу слова? Этот вопрос касается как предложений и документов, так и других структурных единиц текста. Предположим, что близкие по контексту слова имеют схожий смысл. Эта идея есть не что иное, как дистрибутивная гипотеза (John R. Firth. A Synopsis of Linguistic Theory, 1930–1955. Studies in Linguistic Analysis, pages 1–32, 1957), одна из краеугольных концепций в области обработки текстов.

Для машинного анализа представим смысл слова как вектор в пространстве в том понимании, что близкие по контексту слова имеют близкие (в метрическом пространстве) векторные представления. Такие векторные представления называют эмбеддингами слов (далее — просто эмбеддингами). Аналогично можно определить эмбеддинги предложений, документов, параграфов и разных других лингвистических единиц, но для дальнейшего повествования интерес представляют лишь эмбеддинги слов.

Чем хороши эмбеддинги слов fastText

Один из наиболее популярных способов получать эмбеддинги слов — техника fastText, предложенная Facebook AI Research аж в 2016 году (сайт проекта, оригинальная статья). Популярной она стала не просто так. На момент её разработки уже существовали разные способы получения эмбеддингов слов, самым известным из которых был Word2vec говорящее название от «Гугла» (сайт проекта, оригинальная статья, с картинками на Хабре). Однако существующие тогда решения недостаточно эффективно работали со словами, которых не было в обучающих корпусах (т. н. Out-of-Vocabulary words, OOV), и fastText очень элегантно решил эту проблему с приемлемым ущербом для времени обучения и инференса.

Исследователи из Facebook предположили, что для получения эмбеддинга слова имеет смысл учесть не только контекст, но и структуру на символьном уровне. Для этого они выбрали концепцию эмбеддингов символьных n-грамм, которую можно проиллюстрировать простым примером. 

Возьмём слово рояль. Добавим к нему открывающий и закрывающий теги и получим <рояль>. Давайте получим n-граммы, причём пусть n_min=2, а n_max=4:

Идея заключается в том, чтобы обучать векторы именно n-грамм (а не слов, как в Word2vec), а эмбеддинг целого слова получать как взвешенную сумму векторов n-грамм. Неизвестные слова будут содержать известные n-граммы и таким образом получат адекватные эмбеддинги. Важно уточнить, что n_min и n_max задаются при обучении и их тоже желательно выбирать с умом в зависимости от особенностей языка. 

Для быстрого получения эмбеддингов векторов необходимо, чтобы в момент инференса векторы n-граммы уже были в оперативной памяти. Проблема в том, что уникальных n-грамм может быть сколько угодно и их количество также будет связано с n_min и n_max, а тогда количество требуемой памяти для хранения n-грамм должно быть очень большим. Это ненадёжно и опасно. 

Разработчики fastText учли и это, поэтому используют хеширование FNV-1a, которое ставит в соответствие n-грамме натуральное число от 1 до задаваемого при обучении числа bucket (по умолчанию bucket=2*10^6). Таким образом модель fastText ограничивает потребление памяти тем, что в ней не может быть векторов n-грамм больше, чем значение bucket. Тут у искушённого читателя сразу возникнет вопрос о коллизиях при подобном хешировании, но давайте не будем забегать вперёд. 

Итак, я постарался крайне поверхностно, но сущностно рассказать о том, что представляет из себя fastText, а теперь время продолжить историю.

Заглянем внутрь модели

Рассматривать будем содержимое модели аварского языка (современного), которая была обучена на аварской «Википедии». За основу возьмём пример Андрея Васнецова, то есть будем использовать библиотеку Gensim.

Итак, наша модель занимает 2,24 Гб (2_410_222_502 B). Загрузим её через Gensim и посмотрим параметры:

Вообще-то в модели хранятся не только векторы n-грамм, но и векторы слов (они однократно вычисляются из векторов n-грамм, чтобы их не пересчитывать каждый раз). Оба набора векторов хранятся в виде матриц соответствующих размеров, где каждая строка — это вектор, соответствующий слову/n-грамме. Размерность векторов — 300, и так как корпус текстов был настолько невелик, что в словаре оказалось всего лишь 4217 слов, то матрица векторов слов имеет размер (4217, 300). Так как bucket = 2_000_000, то и матрица n-грамм ожидаемо будет 2_000_000, 300.

Если в матрице векторов слов каждый вектор соответствует слову, то как же ставятся в соответствие n-граммы и их векторы? Как нетрудно догадаться, каждой n-грамме посредством хеширования ставится в соответствие натуральное число, которое и является номером строки в матрице n-грамм, содержащим соответствующий вектор n-граммы. Причём мы храним всю матрицу n-грамм целиком, даже если там есть нулевые строки.

И разве нормально для такого маленького словаря хранить такую большую матрицу n-грамм? Хорошо ли это? Можно ли как-то её сократить? Посмотрим на саму матрицу n-грамм и решим, есть ли там лишние строки.

Из двух миллионов векторов ненулевыми оказывается меньше трети — 613 408. Но даже это число кажется слишком большим для такого маленького словаря. Посмотрим на оставшиеся ненулевые векторы, а именно на их L2-нормы.

Если построить гистограмму L2-норм ненулевых векторов (рис. 1), то можно увидеть, что подавляющее большинство из них имеет норму, близкую к нулю. Гистограмма построена в двух смежных отрезках, чтобы контуры хоть как-то различались.

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

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

Судя по всему, та самая бо́льшая часть почти нулевых по L2-норме векторов находится в центральной части гистограммы, и её компоненты, вероятно, распределены равномерно. Красным пунктиром отмечена сетка, по которой строилась центральная гистограмма. Она обваливается вниз ровно на значениях ±1/300, и это похоже на равномерную инициализацию весов. А вот в левой и правой части гистограммы, судя по всему, находятся информативные значения.

Раз мы знаем распределение компонент околонулевых «шумовых» векторов, то можно достаточно просто отфильтровать векторы по их L2-нормам, предполагая, что значения всех компонент шумовых векторов распределены равномерно (от -1/300 до 1/300).

\[ X_i \sim U[-a, a] \Rightarrow pdf_{X_i^2}(x) = \frac{1}{2a\sqrt{x}}; \ \mathbb{E}\left[X_i^2\right] = \frac{a^2}{3};\ \mathbb{D}\left[X_i^2\right] = \frac{a^2}{3\sqrt{5}} \Rightarrow \\ \Rightarrow \text{по ЦПТ} \sum_{i=1}^n X_i^2 \sim \mathcal{N}\left(n\mathbb{E}\left[X_i^2\right], n\mathbb{D}\left[X_i^2\right]\right) \]

На рис. 3 показаны зоны отсечения по сигмам. В данном случае отсекать следует по ±4σ, так как даже те доли процента оставшихся значений дают огромное количество «шумовых» векторов.

Посмотрим на имеющиеся n-граммы с другой стороны

Те манипуляции с фильтрацией, которые происходили выше, были основаны только на векторах n-грамм без принятия во внимание самих n-грамм. В обученной модели fastText осмысленные векторы n-грамм будут соответствовать только тем n-граммам, которые присутствовали в словаре корпуса текстов, на котором происходило обучение (ведь других n-грамм при обучении взять попросту неоткуда).

Посмотрим, сколько у нас в словаре уникальных n-грамм и хешей, ведь чтобы получить вектор n-граммы, нужно сначала получить её хеш. 

Для получения хешей n-грамм слова используется ft_ngram_hashes из библиотеки Gensim, в которой, в свою очередь, используются ft_hash_bytes и ompute_ngrams_bytes. 

Как видно, количество уникальных хешей меньше количества уникальных n-грамм, очевидно из-за коллизий при хешировании. Вот пример нескольких пар n-грамм из аварской модели fastText, когда разным n-граммам соответствует один хеш: (1582307: кiара, очи), (1270390: рихия, хӏмат). Из 23 552 n-грамм в модели неоднозначный хеш есть у 262 n-грамм ((23552 – 23421) * 2 = 262). И это для fastText-модели редкого языка. Если взять более популярные языки, количество встречающихся n-грамм будет сильно больше и, следовательно, будет больше коллизий. Резонно возникает опасение влияния таких коллизий хеширования на качество итоговых эмбеддингов слов. 

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

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

Отходя немного в сторону, заметим, что отфильтрованные в предыдущей части по ±4σ 23 447 векторов полностью содержат в себе те 23 421 вектор (всего 26 лишних векторов), соответствующие хешам всех имеющихся n-грамм. Это говорит о том, что для выявления значимых векторов в матрице n-грамм в данном случае могут быть применимы оба способа.

Как выбрать размер bucket-а

Вернёмся к проблеме коллизий. От чего зависит их количество? Какие есть варианты для уменьшения? Чем придётся пожертвовать для этого — каковы трейд-оффы? 

Очевидно, чем больше размер bucket-a, тем меньше количество коллизий. С другой стороны, количество коллизий будет меньше, если n-грамм также будет меньше, то есть будет меньше разница между значениями n_min и n_max при фиксированном значении bucket-a. Однако с уменьшением общего количества n-грамм будут уменьшаться и бенефиты от самой концепции символьной n-граммной модели. Поэтому имеет смысл подбирать n_min и n_max, ориентируясь не на коллизии, а на особенности каждого конкретного языка.

Остаётся вариант с выбором размера bucket-а. Вернёмся снова к модели fastText для аварского языка. 

С одной стороны, чтобы избежать коллизий, можно увеличить размер bucket-а. Но, во-первых, размер bucket-а и так составляет 2 млн, во-вторых, количество коллизий мало по сравнению с общим количеством n-грамм. Может, наоборот, стоит уменьшить размер bucket-a? 

На примере аварской модели посмотрим на зависимость количества коллизий от размера bucket-а. 

Эти графики отображают трейд-офф между размером bucket-а и количеством коллизий. На всём указанном диапазоне значений bucket-а количество коллизий никогда не достигает нуля. Зелёная пунктирная линия указывает на bucket, используемый в модели, — 2 млн. 

Теперь, когда понятна структура и особенности этой модели, пришло время сохранить её в сжатом виде.

Сохранение модели в виде numpy structured array

После всего вышесказанного кажется очевидным, что сжатие модели для аварского языка без потерь возможно путём сохранения только информативных векторов матрицы n-грамм. Таким образом, нам нужно сохранить матрицы n-грамм и векторов слов, а также сами n-граммы и слова.

По принципиальным соображениям не хотелось бы:

• сохранять модель с помощью библиотеки Gensim, хотя в ней есть подходящий тип данных KeyedVectors,  

• писать свою библиотеку, как у Давида Дале (у него такой способ сохранения оправдан, но у нас слишком простая для этого задача), 

• превращать пары <n-грамма: вектор> и <слово: вектор> в оригинальный питоновский dict. 

Выбор пал на numpy structured array — так мы сохраним обе матрицы как numpy-матрицы, но при этом сможем обращаться к векторам слов или n-грамм, как если бы мы это делали в словаре, например, как data['слово']. 

Если читатель уже сталкивался с numpy structured array, то он может смело пропускать эту часть повествования, а тем, кто сталкивается с этим впервые или почти не сталкивался (как я), постараюсь продемонстрировать, каким образом функционирует numpy structured array (ссылка на документацию numpy).  

Уточню, что этот тип данных в numpy поддерживается только с версий numpy>1.14.1. 

Представим таблицу размером 2 х 2 (рис. 5) со строками 'Поле1' и 'Поле2', в которой мы хотим создать такую переменную data типа numpy structured array, чтобы при обращении к ней data["Поле1"] мы получали numpy.ndarray вида [1.0, 2.0].

Создаём кастомный dtype (ссылка), чтобы данные в обоих столбцах были типа 'float32' и в «таблице» были две записи.

Добавляем вложенные поля: расширим таблицу, вставив 'Поле3', а поля из предыдущего примера вложим в 'Область1' (рис. 6). В этом примере мы хотим при обращении вида data["Область1"]["Поле1"] получить numpy.ndarray вида [1.0, 2.0], а при вызове data["Поле3"] — numpy.ndarray вида [5.0, 6.0].

Этого можно достичь с помощью создания ещё одного dtype, в одном из полей которого типом данных будет dtype из предыдущего примера.

Теперь читателю нетрудно догадаться, каким образом мы запакуем две матрицы, которые нам нужно сохранить (слов и n-грамм). Однако вместе с матрицами следует сохранить ещё три параметра, необходимые для использования модели: минимальный и максимальный размер n-грамм (n_min и n_max) и размерность векторов (да-да, это значение имеется в размере матрицы в неявном виде, но всё же). Для n слов и m n-грамм я выбрал способ, показанный в таблице (рис. 7).

Как видно, для хранения min_n, max_n и dim я использовал три первые записи специального поля 'model info'. Для хранения каждой из матриц слов и n-грамм создан свой dtype. 

Создав numpy structured array со своим dtype, соответствующим таблице выше и с количеством записей, равным 300, пополняем его парами <n-грамма: вектор> и <слово: вектор> и сохраняем через np.save. Подробный код для создания такого numpy structured array, а также код для инференса модели, сохранённой подобным образом, можно найти. 

Любопытно, что размер сокращённой модели составил 32.3 Мб (33_930_400 Байт). Напомню, что размер исходной fastText-модели составлял 2.24 Гб (2_410_222_502 B). Таким образом, удалось сократить размер модели в 71 раз!

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

Итоги

Ну вот и всё, получилось здорово: углубились в fastText, посмотрели, как он устроен, сжали аварскую модель в 70+ раз

Однако стоит напомнить, что всё это работает только с редкими языками, когда обучающие корпусы — маленькие. Ибо вся техника, описанная в статье, базируется на предположении, что большая часть векторов матрицы n-грамм – нулевые или шумовые. Естественно, это не так для языков и моделей с большими обучающими корпусами, большими словарями и огромным количеством разнообразных n-грамм.