GloVe: эмбеддинги из глобальных частот совместной встречаемости

Word2Vec двигает окно по корпусу и обновляет два вектора для каждой встреченной пары — миллионы маленьких стохастических шагов. Пара слов, встретившаяся вместе тысячу раз, посещается тысячу раз. GloVe (Pennington, Socher and Manning, 2014) заходит с другого конца: один раз подсчитать все пары в матрицу совместной встречаемости, а затем подогнать векторы прямо к этой матрице. Обучение тогда стоит времени, пропорционального числу различных пар, а не длине корпуса, а функция потерь явно говорит, чему должны равняться скалярные произведения.

Обозначения. $V$ — словарь. $X_{ik}$ — (взвешенное) число раз, когда слово $k$ встречается в контексте слова $i$; $X_i = \sum_k X_{ik}$; $P_{ik} = P(k \mid i) = X_{ik} / X_i$. У каждого слова есть вектор слова $w_i \in \mathbb R^d$, вектор контекста $\tilde w_k \in \mathbb R^d$ и два смещения $b_i$, $\tilde b_k$.

Базовый подход: разложить матрицу частот#

Методы старше Word2Vec уже работали с матрицей совместной встречаемости: латентный семантический анализ (Deerwester et al., 1990) сжимает матрицу «слово — документ» усечённым SVD, а модели в духе HAL — матрицу «слово — слово». Применённые к сырым частотам, они наследуют две проблемы. Самые частые слова (the, and, ?) встречаются со всеми, поэтому их частоты доминируют в любой подгонке методом наименьших квадратов, хотя смысла несут мало; а одна квадратичная ошибка считает разницу в 10 между частотами 20 и 30 такой же, как между 10 020 и 10 030. Преобразования вроде логарифма или квадратного корня помогают, и в статье о GloVe SVD логарифмов частот достигает 60.1% на аналогиях, где GloVe достигает 71.7% (оба — 300-мерные, 6 миллиардов токенов). Вопрос в том, какую функцию от частот должны воспроизводить векторы и с какими весами.

Смысл несут отношения#

Пример из статьи сравнивает ice и steam на 6 миллиардах токенов. $P(\textit{solid} \mid \textit{ice}) / P(\textit{solid} \mid \textit{steam}) = 8.9$, для $P(\textit{gas} \mid \cdot)$ получается $0.085$, а water, связанное с обоими, даёт $1.36$, и fashion, не связанное ни с одним, — $0.96$. На 537 272 вопросах Quora, подсчитанных так, как описано в разделе с кодом, та же картина видна для tea и coffee:

Контекст $k$	$P(k \mid \textit{tea})$	$P(k \mid \textit{coffee})$	Отношение
green	$9.33 \cdot 10^{-2}$	$7.68 \cdot 10^{-3}$	12.2
starbucks	$1.42 \cdot 10^{-3}$	$1.10 \cdot 10^{-2}$	0.129
drink	$2.02 \cdot 10^{-2}$	$2.02 \cdot 10^{-2}$	1.00
india	$1.96 \cdot 10^{-3}$	$1.68 \cdot 10^{-3}$	1.16

Green — про чай, Starbucks — про кофе, drink — про оба, India — ни про один, и отношение их упорядочивает, тогда как сырые вероятности drink (0.020) и India (0.002) различаются на порядок только из-за частоты. Значения слов задаёт корпус: на Quora $P(\textit{games} \mid \textit{steam})$ в 63 раза больше $P(\textit{games} \mid \textit{ice})$, потому что большинство вопросов о Steam — про магазин игр.

Рисунок

Отношения вероятностей и вес пар в GloVe

От отношений к модели#

GloVe ищет векторы, для которых некоторая функция $F$ от разности $w_i - w_j$ и вектора контекста воспроизводит отношение. Разность сравнивает два слова, скалярное произведение с $\tilde w_k$ превращает векторы в число, а требование, чтобы разность векторов переходила в отношение вероятностей, $F(a - b) = F(a) / F(b)$, оставляет $F = \exp$:

$$\exp\big((w_i - w_j) \cdot \tilde w_k\big) = \frac{P_{ik}}{P_{jk}} \quad\Longleftarrow\quad w_i \cdot \tilde w_k = \log P_{ik} = \log X_{ik} - \log X_i .$$

Слагаемое $\log X_i$ зависит только от $i$ и становится смещением $b_i$; смещение контекста $\tilde b_k$ восстанавливает симметрию. Модель:

$$w_i \cdot \tilde w_k + b_i + \tilde b_k = \log X_{ik} .$$

Скалярное произведение плюс два смещения должно равняться логарифму частоты. Разности векторов тогда кодируют логарифмы отношений — отсюда линейная структура аналогий из заметки об эмбеддингах.

Взвешенный метод наименьших квадратов#

Модель подгоняется методом наименьших квадратов по встретившимся парам, с весом для каждой пары:

$$J = \sum_{i,k:\, X_{ik} > 0} f(X_{ik}) \big(w_i \cdot \tilde w_k + b_i + \tilde b_k - \log X_{ik}\big)^2, \qquad f(x) = \begin{cases} (x / x_{\max})^{\alpha}, & x < x_{\max}, \\ 1, & \text{иначе}, \end{cases}$$

с $x_{\max} = 100$ и $\alpha = 3/4$ во всех экспериментах статьи. Вес выполняет три задачи. У пар, которые не встречаются, $\log 0 = -\infty$, и они исключены, так что сумма идёт только по ненулевым элементам. Редкие пары шумные и получают маленький вес: $f(1) = 0.032$, $f(10) = 0.178$. Вес частых пар ограничен единицей, так что пары ? со всеми словами не могут захватить подгонку.

Разобранный пример. Возьмём пару с $X_{ik} = 50$, тогда $\log X_{ik} = 3.912$ и $f(50) = 0.5^{3/4} = 0.595$. Если текущие векторы дают $w_i \cdot \tilde w_k + b_i + \tilde b_k = 3.0$, ошибка равна $-0.912$, и пара вносит в $J$ вклад $0.595 \times 0.912^2 = 0.495$. Градиент по $w_i$ равен $2 \times 0.595 \times (-0.912)\, \tilde w_k$: обновление сдвигает $w_i$ к $\tilde w_k$, пока их скалярное произведение вместе со смещениями не совпадёт с логарифмом частоты.

Обучение следует из вида $J$. Матрица строится за один проход по корпусу; статья использует окно в десять слов с каждой стороны, а пара на расстоянии $d$ добавляет к частоте $1/d$. Затем AdaGrad выбирает ненулевые элементы в течение 50 проходов (100 для 300-мерных векторов) с начальной скоростью обучения 0.05. Слова и контексты играют симметричные роли, поэтому два набора векторов различаются только случайной инициализацией, и итоговый вектор слова — $w_i + \tilde w_i$, что, по данным статьи, немного лучше каждого из них.

Запуск на вопросах Quora#

Чтобы увидеть GloVe рядом с моделью Word2Vec из предыдущей заметки, обучим обе на одном тексте: 537 272 вопроса Quora в нижнем регистре, разбитые на слова и знаки препинания, без английских стоп-слов, 3.9 миллиона токенов. Слова, встретившиеся меньше 5 раз, отбрасываются, остаётся $|V| = 27{,}789$. В матрице совместной встречаемости (окно 10, вес $1/d$) 6 781 251 ненулевой элемент, 0.88% от $|V|^2$ возможных пар; лишь 0.15% элементов достигают $x_{\max}$. Пятьдесят проходов AdaGrad при $d = 32$ занимают около минуты на процессоре ноутбука, и взвешенные потери на элемент падают с 0.082 после первого прохода до 0.036, 0.030, 0.023 и 0.020 после проходов 5, 10, 25 и 50.

Ближайшие соседи по косинусу, GloVe против CBOW Word2Vec с $d = 32$ и окном 5 на тех же токенах:

Слово	GloVe	Word2Vec (CBOW)
python	java 0.891, php 0.847, django 0.842	javascript 0.967, java 0.942, php 0.937
coffee	tea 0.834, starbucks 0.802, drinking 0.769	tea 0.900, beer 0.875, starbucks 0.857
word	meaning 0.888, ’? 0.880, origin 0.874	words 0.806, sentence 0.803, pronounce 0.797
learn	programming 0.840, learning 0.821, easy 0.812	learning 0.817, beginner 0.750, teach 0.743

Обе модели находят одни и те же темы. Соседи GloVe тяготеют к тому, с чем слово встречается в вопросе (learn → programming, python), соседи Word2Vec — к тому, что может его заменить (learn → teach, beginner), отчасти потому, что окно GloVe здесь вдвое шире. GloVe ещё и пускает в списки соседей токены пунктуации вроде ’?: у него нет прореживания частых токенов, а ограничение $x_{\max}$ ограничивает их вес в каждой паре, но не число пар, в которых они участвуют.

GloVe и skip-gram#

Два метода ближе, чем можно подумать по их процедурам обучения. Заметка о Word2Vec показывает, что skip-gram с негативным сэмплированием приближает $u_o \cdot v_c$ к сдвинутой поточечной взаимной информации $\log \frac{P(c, o)}{P(c) P(o)} - \log k$; GloVe приближает $w_i \cdot \tilde w_k + b_i + \tilde b_k$ к $\log X_{ik}$, и смещения могут поглотить слагаемые $\log X_i$ и $\log X_k$, которые превращают логарифм частоты в PMI. Оба раскладывают логарифмическую матрицу совместной встречаемости скалярными произведениями. Различаются они весами пар, тем, строится ли матрица явно, и стоимостью: GloVe платит один раз за корпус при подсчёте, а затем за каждый ненулевой элемент, Word2Vec — за каждый токен в каждой эпохе.

Статья о GloVe приводит точность на аналогиях 71.7% для GloVe против 65.7% для CBOW и 69.1% для skip-gram (300 измерений, 6 миллиардов токенов) и 75.0% для GloVe на 42 миллиардах токенов. Levy, Goldberg and Dagan (2015) позже показали, что большая часть таких различий идёт от решений вне алгоритма (размер окна, прореживание, сглаживание распределения контекстов, способ объединить два набора векторов) и что при одинаковых решениях ни один метод не лучше стабильно. Сегодня GloVe используют в основном через его готовые скачиваемые векторы, например векторы Twitter из заметки об эмбеддингах.

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

	Word2Vec (SGNS)	GloVe
Вход	окна, проходящие по корпусу	частоты совместной встречаемости, подсчитанные один раз
Функция потерь	логистическая на положительных и сэмплированных парах	взвешенные наименьшие квадраты для $\log X_{ik}$
Что приближают скалярные произведения	сдвинутую PMI (неявно)	логарифм частоты минус смещения (явно)
Стоимость обучения	пропорциональна длине корпуса × число эпох	пропорциональна числу ненулевых пар × число проходов
Память	две таблицы векторов	ещё и матрица частот (6.8 млн элементов для 27 789 слов здесь)
Частые слова	прореживаются	ограничиваются через $f$

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

• Один вектор на слово словаря. Как и Word2Vec, GloVe даёт bank один компромиссный вектор; контекстные векторы появляются с BERT.
• Закрытый словарь. Слово, которого нет среди частот, не получает вектора, а слово, встреченное пять раз, получает вектор, подогнанный к горстке пар. Следующая заметка строит векторы из частей слов.
• Матрица частот. Её размер растёт со словарём и окном; при больших словарях подсчёт требует внимания к памяти, за которую Word2Vec никогда не платит.
• Гиперпараметры за пределами алгоритма. Окно, веса, $x_{\max}$, $\alpha$ и сумма $w + \tilde w$ меняют результат не меньше, чем выбор между GloVe и Word2Vec.

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

• GloVe подгоняет $w_i \cdot \tilde w_k + b_i + \tilde b_k = \log X_{ik}$ по ненулевым частотам совместной встречаемости взвешенным методом наименьших квадратов.
• Мотивация — отношение $P(k \mid i) / P(k \mid j)$: оно отделяет то, что различает два слова, от того, что у них общее, а логлинейные скалярные произведения превращают его в разность векторов.
• Вес $f(x) = \min(1, (x/100)^{3/4})$ игнорирует нули, приглушает редкие пары и ограничивает частые.
• Skip-gram и GloVe оба раскладывают логарифмическую матрицу совместной встречаемости; различаются весами и стоимостью, и на практике меньше, чем гиперпараметры вокруг них.

Ноутбук#

Ни один ноутбук курса не обучает GloVe. week01_word_embeddings.ipynb скачивает предобученные 100-мерные векторы GloVe Twitter (ячейка 62; номера ячеек считают все ячейки, начиная с 1) и проверяет аналогии, разобранные в заметке об эмбеддингах. Числа этой заметки получены запуском из раздела с кодом на собственном файле курса с вопросами Quora (seminars/data/quora.txt).

Код#

GloVe примерно в сорок строк на NumPy и PyTorch, на вопросах Quora:

import re, collections, numpy as np, torch
from sklearn.feature_extraction.text import ENGLISH_STOP_WORDS

tok = re.compile(r"\w+|[^\w\s]+")
lines = [l.strip() for l in open('quora.txt', encoding='utf-8') if l.strip()]
sents = [[t for t in tok.findall(l.lower()) if t not in ENGLISH_STOP_WORDS] for l in lines]
cnt = collections.Counter(t for s in sents for t in s)
vocab = [w for w, c in sorted(cnt.items(), key=lambda x: (-x[1], x[0])) if c >= 5]
idx = {w: i for i, w in enumerate(vocab)}; V = len(vocab)
print(len(sents), sum(map(len, sents)), V)

# частоты совместной встречаемости: окно 10 с каждой стороны, пара на расстоянии d добавляет 1/d
ids = [np.array([idx[t] for t in s if t in idx]) for s in sents]
ids = [a for a in ids if len(a)]
flat = np.concatenate(ids); sid = np.repeat(np.arange(len(ids)), [len(a) for a in ids])
keys, vals = [], []
for d in range(1, 11):
    same = sid[:-d] == sid[d:]                       # оба слова в одном вопросе
    a, b = flat[:-d][same], flat[d:][same]
    keys += [a * V + b, b * V + a]; vals += [np.full(len(a), 1 / d)] * 2
uk, inv = np.unique(np.concatenate(keys), return_inverse=True)
X = torch.tensor(np.bincount(inv, weights=np.concatenate(vals)), dtype=torch.float32)
I, J = torch.from_numpy(uk // V), torch.from_numpy(uk % V)
print(len(X), (X >= 100).float().mean().item())

# взвешенные наименьшие квадраты с AdaGrad
torch.manual_seed(0)
dim = 32
W = torch.nn.Parameter((torch.rand(V, dim) - 0.5) / dim); Wt = torch.nn.Parameter((torch.rand(V, dim) - 0.5) / dim)
b = torch.nn.Parameter(torch.zeros(V)); bt = torch.nn.Parameter(torch.zeros(V))
opt = torch.optim.Adagrad([W, Wt, b, bt], lr=0.05)
f = torch.clamp(X / 100, max=1.0) ** 0.75; logX = torch.log(X)
for epoch in range(50):
    perm, total = torch.randperm(len(X)), 0.0
    for s in range(0, len(X), 100_000):
        p = perm[s:s + 100_000]; i, j = I[p], J[p]
        err = (W[i] * Wt[j]).sum(1) + b[i] + bt[j] - logX[p]
        loss = (f[p] * err ** 2).sum()
        opt.zero_grad(); loss.backward(); opt.step(); total += loss.item()
    print(epoch + 1, total / len(X))

E = (W + Wt).detach().numpy()                      # итоговые векторы: w + w~
E /= np.linalg.norm(E, axis=1, keepdims=True)
sim = E @ E[idx['python']]
print([(vocab[k], round(float(sim[k]), 3)) for k in np.argsort(-sim)[1:4]])

Запуск печатает 537 272 вопроса, 3 883 212 токенов и $|V| = 27{,}789$, затем 6 781 251 ненулевой элемент, из которых 0.15% достигают $x_{\max}$, приведённые выше потери (0.082 после первого прохода, 0.020 после пятидесятого) и для python — java 0.891, php 0.847, django 0.842. Строки про tea и coffee получены из той же X: $P(k \mid i)$ — это $X_{ik}$, делённое на сумму строки $X_i$, 1702.8 для tea и 1954.4 для coffee.

Дальше#

GloVe и Word2Vec обрываются на границе своего словаря: опечатка, редкая словоформа или новое слово не получают ничего. Следующая заметка сохраняет функцию потерь skip-gram и строит вектор каждого слова из векторов его символьных n-грамм, так что родственные формы делят параметры, а незнакомые слова всё равно получают вектор.

Литература#

• J. Pennington, R. Socher, C. D. Manning. GloVe: Global Vectors for Word Representation. EMNLP, 2014. Table 1 (ice and steam), §3 (the model and the weighting function), §4.2 (training), Table 2 (analogies).
• O. Levy, Y. Goldberg, I. Dagan. Improving Distributional Similarity with Lessons Learned from Word Embeddings. TACL, 3, 2015.
• S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, R. Harshman. Indexing by Latent Semantic Analysis. JASIS, 41(6), 1990.