FastText: векторы слов из символьных n-грамм

Word2Vec и GloVe дают каждому слову словаря собственный вектор, выученный только по контекстам этой самой строки. Coffee и coffees обучаются по отдельности, у learnig вектора нет вовсе, а в языке вроде русского, где у существительного около дюжины падежных и числовых форм, большинство форм редки даже в большом корпусе. FastText (Bojanowski et al., 2017) сохраняет функцию потерь skip-gram и меняет само понятие слова: это мешок символьных n-грамм, у каждой из которых свой вектор, так что слова, написанные похоже, делят параметры, а любая строка, встреченная или нет, получает вектор.

Обозначения. Для слова $w$ $\mathcal G_w$ — множество его символьных n-грамм вместе с самим словом; у каждой $g \in \mathcal G_w$ есть вектор $z_g \in \mathbb R^d$. У контекстных слов векторы $v_c$, как в Word2Vec. $K$ — число корзин хеширования.

Базовый подход: один вектор на слово словаря#

В 537 272 вопросах Quora из предыдущих заметок, в нижнем регистре и без стоп-слов, 87 511 различных слов. При обычном пороге в 5 вхождений 59 722 из них, 68% словаря, вектора не получают. Это лишь 2.4% токенов, но в 14% вопросов есть хотя бы одно такое слово: опечатки (programing, 35 раз), редкие словоформы, имена, новые слова. А 27 789 слов, которые векторы получают, ничему не учатся друг у друга: вектор learns обучается по его собственным немногим контекстам и не пользуется многочисленными контекстами learn.

Слово — мешок символьных n-грамм#

Пример из статьи — where. С границами оно становится <where>, его 3-граммы — <wh, whe, her, ere, re>; вместе с 4-, 5- и 6-граммами получается 14 n-грамм, а с самим <where> — 15 векторов. Границы важны: 3-грамма her внутри where — это другая часть, чем слово her, то есть <her>.

Оценка пары «слово — контекстное слово», которая в Word2Vec была скалярным произведением $u_w \cdot v_c$, становится

$$s(w, c) = \sum_{g \in \mathcal G_w} z_g \cdot v_c ,$$

а всё остальное — функция потерь с негативным сэмплированием и выбор негативных примеров — остаётся как было. Градиент каждой обучающей пары доходит до каждого вектора n-граммы слова, поэтому learns, learnt и learner вместе обучают векторы <le, lea, ear, arn и более длинных частей, общих с learn.

Рисунок

Слово как сумма векторов n-грамм

Шаги рисунка:

1. Границы. < и > отмечают начало и конец, так что приставки и окончания становятся отдельными частями.
2. N-граммы. Все подстроки длины от 3 до 6 и само слово как ещё одна часть: 15 частей для where.
3. Поиск. Каждая часть хешируется в строку одной таблицы векторов n-грамм.
4. Сумма. Вектор слова — сумма этих строк. (Реализации вроде gensim делят на число частей; для косинуса масштаб не важен.)

Хеширование#

Словарь всех символьных n-грамм большого корпуса был бы огромным, поэтому n-граммы не хранятся по имени. Каждая хешируется (в статье — FNV-1a) в одну из $K = 2 \cdot 10^6$ корзин, и строка корзины служит её вектором. Две n-граммы в одной корзине делят вектор — такие совпадения метод принимает в обмен на память, фиксированную заранее: $2 \cdot 10^6 \times 300$ чисел по 4 байта — это 2.4 ГБ для 300-мерных векторов и 256 МБ для 32-мерных векторов ниже.

Векторы для незнакомых слов#

У слова, которое ни разу не встречалось, всё равно есть n-граммы, и большинство из них встречалось в других словах. Его вектор — сумма их векторов. Обученная на вопросах Quora (gensim, вариант CBOW, $d = 32$, окно 5, слова не реже 5 вхождений, 5 эпох), модель отвечает на запросы о строках, которых нет в её словаре:

Запрос (нет в словаре)	Ближайшие слова по косинусу
coffeee	coffee 0.988, koffee 0.928, coffees 0.904
learnig	learnt 0.963, learns 0.955, learnings 0.950, learn 0.943
blockchainify	blockchain 0.967, access 0.864, blockade 0.861
unfriendliness	friendly 0.905, confess 0.893, unfriend 0.884
pyhton	von 0.943, ton 0.941, peyton 0.939

Первые три работают, потому что опечатка или производное слово сохраняют большинство частей: coffeee делит с coffee 15 из своих 22 n-грамм, learnig с learning — 14. Unfriendliness оказывается рядом с friendly, но и рядом с confess, у которого нет ничего общего по смыслу и три части окончания (ess, ss>, ess>) из 50 n-грамм unfriendliness. Pyhton не работает: перестановка двух букв ломает каждую n-грамму, которая через них проходит, и с python у него общие лишь <py и on>, 2 из 18. Подслова помогают с вариантами написания, сохраняющими подстроки, но не с любой опечаткой.

Что подслова делают с соседями#

Тот же механизм меняет соседей обычных слов. Для слов из словаря ближайшие соседи FastText определяются в основном общим написанием:

Слово	FastText	Word2Vec (CBOW, те же данные)
learn	learnt 0.965, learns 0.955, unlearn 0.939	learning 0.817, beginner 0.750, teach 0.743
coffee	coffees 0.914, koffee 0.897, tea 0.856	tea 0.900, beer 0.875, starbucks 0.857
india	indias 0.933, indiape 0.917, indiana 0.882	indian 0.778, overseas 0.753, usa 0.750

Словоформы и варианты написания сближаются, для чего модель и нужна, но сближаются и строки, которые лишь похожи: Indiana, indigo и Indira входят в пятёрку ближайших к India. Для задач, где важна морфология (синтаксические аналогии, редкие слова, морфологически богатые языки), это выигрыш; для задач о теме это может быть шумом.

Статья измеряет обе стороны. На сходстве слов вычисление векторов для слов вне словаря поднимает корреляцию с оценками людей на русском наборе HJ с 59 (skip-gram) до 66, а на английском наборе редких слов — с 43 до 47. На аналогиях точность синтаксических вопросов резко растёт в морфологически богатых языках, с 52.8% до 77.8% в чешском и с 44.5% до 56.4% в немецком, а в английском с 70.1% до 74.9%, тогда как точность семантических вопросов в английском немного падает, с 78.5% до 77.8%.

fastText как классификатор#

В той же библиотеке, от той же группы, есть классификатор текстов на той же идее (Joulin et al., 2017): документ — среднее эмбеддингов его слов, при желании с добавлением хешированных биграмм слов, а линейный слой с softmax предсказывает метку. Это CBOW с меткой вместо центрального слова. Скрытой нелинейности нет; в экспериментах статьи у эмбеддингов всего 10 измерений, а биграммы дают немного локального порядка слов почти бесплатно.

На AG News, датасете заметок курса о классификации, статья сообщает 91.5% правильных ответов на тесте только со словами и 92.5% с биграммами — против 87.2% у символьной CNN и 91.3% у 29-слойной, примерно за секунду на эпоху вместо часов. Повторная реализация на PyTorch (эмбеддинги слов и хешированных биграмм размера 10, усреднённые через EmbeddingBag, линейный слой, SGD с линейно убывающей скоростью, выбранной на 12 000 отложенных обучающих статьях, 5 эпох, код ниже) даёт ту же картину:

Модель	Параметры	Секунд на эпоху (CPU)	Доля правильных ответов на тесте
только слова, скорость 0.05	650 474	2.2	0.914
слова + биграммы в 2 000 000 корзин, скорость 0.1	20 650 474	3.0	0.922

Для сравнения: TF-IDF с логистической регрессией даёт 0.918 на том же разбиении, а лучшая CNN — 0.911. Линейную модель над усреднёнными эмбеддингами стоит запустить прежде чего-то тяжелее.

Что изменилось#

	Word2Vec / GloVe	FastText
Единица с вектором	слово словаря	символьные n-граммы длины от 3 до 6 плюс слово
Вектор слова	одна строка таблицы	сумма примерно 15 строк
Незнакомое слово	вектора нет	сумма его известных n-грамм
Параметры	$\lvert V \rvert \times d$	$(\lvert V \rvert + K) \times d$, где $K = 2 \cdot 10^6$
Соседи	по контексту	по контексту и по написанию

Ограничения#

• Написание — не смысл. Похожие строки получают близкие векторы, связаны они или нет (India и Indiana, unfriendliness и confess).
• Не каждая опечатка исправляется. Перестановка ломает n-граммы, через которые проходит; pyhton оказывается рядом с von и ton.
• Память. Доминирует таблица корзин: 2.4 ГБ при $d = 300$ ещё до векторов слов.
• Всё ещё статичность. Один вектор на строку, каким бы ни было предложение; это устраняет заметка о BERT. Токенизация на подслова, которой пользуются все трансформеры курса (заметка о токенизации), решает проблему открытого словаря иначе: она делит редкое слово на несколько выученных частей, а не суммирует все n-граммы.

Что нужно запомнить#

• Слово — это < + слово + >, нарезанное на все n-граммы длины от 3 до 6, плюс само слово; его вектор — сумма их векторов, а функция потерь skip-gram не меняется.
• N-граммы хешируются в $2 \cdot 10^6$ корзин, поэтому память фиксирована и для любой n-граммы есть строка, которую можно найти. Хеширование убирает отсутствующие записи словаря, но не отсутствие данных: строка n-граммы, не встречавшейся при обучении, не обучалась, а одну строку могут делить не связанные между собой n-граммы.
• Незнакомое слово получает вектор из своих частей; опечатки, сохраняющие большинство частей, оказываются рядом с правильным словом, перестановки — нет.
• Соседи смешивают смысл и написание; выигрыш больше всего для морфологии и редких слов.
• Классификатор fastText — усреднённые эмбеддинги слов и биграмм с линейным softmax — достигает 0.922 на AG News за секунды на эпоху.

Ноутбук#

Ни один ноутбук курса не обучает FastText. Числа этой заметки получены запуском из раздела с кодом на собственных данных курса: seminars/data/quora.txt и разбиениях AG News ag_news_train.csv и ag_news_test.csv из репозитория курса.

Код#

Векторы подслов в gensim на вопросах Quora, токенизированных как в заметке о GloVe:

from gensim.models import FastText, Word2Vec

# sents: список списков токенов (нижний регистр, без стоп-слов); запуск с PYTHONHASHSEED=0
ft = FastText(sents, vector_size=32, window=5, min_count=5, min_n=3, max_n=6,
              bucket=2_000_000, workers=1, seed=0)
w2v = Word2Vec(sents, vector_size=32, window=5, min_count=5, workers=1, seed=0)
for w in ['coffeee', 'learnig', 'blockchainify', 'unfriendliness', 'pyhton']:
    print(w, w in w2v.wv.key_to_index, ft.wv.most_similar(w, topn=3))

Классификатор fastText на AG News со словами и хешированными биграммами (скорости выбраны из 0.05, 0.1, 0.25 и 0.5 обучением на первых 108 000 обучающих статьях и проверкой на оставшихся 12 000):

import re, zlib, numpy as np, pandas as pd, torch, torch.nn as nn

tr = pd.read_csv('ag_news_train.csv', sep='\t'); te = pd.read_csv('ag_news_test.csv', sep='\t')
toks = lambda t: re.findall(r"\w+", t.lower())
Xtr, Xte = [toks(t) for t in tr.text], [toks(t) for t in te.text]
ytr, yte = torch.tensor(tr.label.values), torch.tensor(te.label.values)
vocab = {w: i for i, w in enumerate(sorted({w for s in Xtr for w in s}))}
V, B = len(vocab), 2_000_000
BIGRAMS, LR = True, 0.1                            # только слова: False, 0.05

def feats(s):                                      # номера слов, затем хешированные номера биграмм
    ids = [vocab[w] for w in s if w in vocab]
    if BIGRAMS:
        ids += [V + zlib.crc32(f'{a} {b}'.encode()) % B for a, b in zip(s, s[1:])]
    return ids

def batch(F, idx):                                 # склеенные номера и смещения для EmbeddingBag
    parts = [torch.tensor(F[i] if F[i] else [0]) for i in idx]
    return torch.cat(parts), torch.tensor([0] + [len(p) for p in parts[:-1]]).cumsum(0)

torch.manual_seed(0); rng = np.random.default_rng(0)
Ftr, Fte = [feats(s) for s in Xtr], [feats(s) for s in Xte]
emb = nn.EmbeddingBag(V + (B if BIGRAMS else 0), 10, mode='mean', sparse=True)
lin = nn.Linear(10, 4)
nn.init.uniform_(emb.weight, -0.1, 0.1)
opt = torch.optim.SGD(list(emb.parameters()) + list(lin.parameters()), lr=LR)
epochs, bs = 5, 16
steps, step = epochs * ((len(Ftr) + bs - 1) // bs), 0
for epoch in range(epochs):
    order = rng.permutation(len(Ftr))
    for s in range(0, len(Ftr), bs):
        idx = order[s:s + bs]; x, off = batch(Ftr, idx)
        for g in opt.param_groups:
            g['lr'] = LR * (1 - step / steps)        # линейное убывание до 0
        loss = nn.functional.cross_entropy(lin(emb(x, off)), ytr[idx], reduction='sum')
        opt.zero_grad(); loss.backward(); opt.step(); step += 1

with torch.no_grad():
    x, off = batch(Fte, range(len(Fte)))
    print((lin(emb(x, off)).argmax(1) == yte).float().mean().item())

Запуск печатает 0.9216 с биграммами и 0.9142 при BIGRAMS, LR = False, 0.05.

Дальше#

Векторы слов, статические или из подслов, всё равно нужно как-то объединить в представление документа, а усреднение, как в классификаторе fastText, не видит порядка слов дальше биграмм. Следующая заметка возвращается к AG News с сетью, которая читает последовательность эмбеддингов, и спрашивает, побеждает ли видение фраз мешок частот.

Литература#

• P. Bojanowski, E. Grave, A. Joulin, T. Mikolov. Enriching Word Vectors with Subword Information. TACL, 5, 2017. §3.2 (n-grams of length 3 to 6, FNV-1a hashing into $2 \cdot 10^6$ buckets), Tables 1 and 2.
• A. Joulin, E. Grave, P. Bojanowski, T. Mikolov. Bag of Tricks for Efficient Text Classification. EACL, 2017. Table 1 (AG News 91.5 and 92.5), Table 2 (training time).