Негативное сэмплирование и контрастное обучение — от word2vec до CLIP

Хрестоматийная версия word2vec опирается на выходной слой softmax, который превращает сырые оценки модели в вероятность для каждого слова словаря, — и именно отсюда берётся проблема масштабирования. При обучении функция потерь использует ровно одну вероятность на пару, P(target | center). Но softmax определяет её как долю от суммы по всему словарю:

P(target) = exp(score_target) / Σ_w exp(score_w)

Знаменатель суммирует по всем V словам, поэтому, чтобы получить одно нужное вам число, приходится вычислить все V оценок — не потому что они вам нужны, а потому что они нужны нормировщику. Уберите любую отдельную оценку — и нормировка сломается.

При словаре V = 10⁶ слов и размерности эмбеддинга d = 300 оценивание центрального слова против каждого слова словаря — это матричное умножение V × d, 300 миллионов умножений-сложений, плюс миллион экспонент для знаменателя, и всё это на одну обучающую пару.

Чтобы почувствовать масштаб, сравним вычисления на один пример с MNIST:

                          INPUT      HIDDEN     OUTPUT     OUTPUT-LAYER MATMUL
MNIST                     784        128        10         128 × 10  = 1,280 ops
word2vec  (V = 10⁶)       V → 1      300        V          300 × 10⁶ = 300,000,000 ops

MNIST — задача классификации на 10 классов; word2vec — задача на миллион классов, по одному выходному нейрону на слово словаря. Любая цена в выходном слое — веса, матричное умножение, softmax — растёт линейно с этим числом классов.

Последующая работа 2013 года предложила negative sampling как альтернативу иерархическому softmax. Вместо предсказания слова решается бинарная задача: отличить наблюдаемые пары от пар из шумового распределения. Меняется сама целевая функция, а не только способ приближения знаменателя softmax.

Одна положительная пара и k отрицательных выборок требуют k+1 скалярных произведений: стоимость O((k+1)d) вместо O(Vd). Градиенты получают только выбранные выходные векторы; повторные выборки учитываются повторно. Здесь они хранятся в строках Ep формы (V, d) — транспонированном варианте E' из статьи о word2vec.

Сравнение наблюдаемых и случайных пар связывает negative sampling с контрастивным обучением. CLIP и плотные поисковые модели используют близкие идеи, но их обычные softmax-потери отличаются от независимых сигмоидных слагаемых word2vec.

От пар к негативам

Обучающие данные word2vec — пары (center, context) из скользящего окна по корпусу: the cat sat on the mat порождает (sat, cat), (sat, on), (sat, the) и так далее — миллиарды подлинных совместных встречаемостей.

Негативное сэмплирование оставляет пары в точности теми же, но вместо того, чтобы просто максимизировать правдоподобие настоящего соответствия (center, context), добавляет k случайных пар на шаг в качестве противовеса — подстраивая веса так, чтобы их правдоподобие, наоборот, минимизировалось.

Оба типа пар делят один и тот же центр, но по-разному выбирают слово-напарника:

Положительные пары берутся из контекстных окон. Отрицательные выборки получают партнёра независимо от центрального слова, обычно с вероятностью, пропорциональной count(w)^0.75. Выбранное слово может быть и настоящим контекстом: «отрицательный» описывает способ выборки, а не отсутствие совместных появлений. Возможны ложные отрицательные примеры.

Поиск вектора и скалярные произведения остаются прежними. Меняются выбор оцениваемых слов и способ включения оценок в потерю.

Сырое скалярное произведение v_c · v'_w может быть любым вещественным числом — положительным, отрицательным, большим, малым, — но функции потерь нужна вероятность от 0 до 1: «насколько вероятно, что эта пара настоящая?». К ней нас приводит сигмоида σ.

Получив оценки, мы можем превратить каждую в вероятность с помощью сигмоиды. σ сжимает любую вещественную оценку в (0, 1):

Для каждой настоящей пары мы хотим, чтобы σ ползла к 1; для каждой случайной — к 0; обучение толкает скалярные произведения в эти стороны.

На той же игрушке из пяти слов из статьи про word2vec виджет ниже проигрывает этот шаг оценивания. Выберите обучающую пару (center, target), переключите, какие слова взяты как негативы, а затем пошагово пройдите k+1 скалярных произведений — score[w] = v_c · v'_w, разложенное слагаемое за слагаемым, а потом через сигмоиду. Оцениваются только цель и негативы; остальные строки Ep остаются серыми и не читаются.

Каждая сигмоида оценивает метку «данные или шум» при выбранной схеме выборки. Это не P(контекстное слово | центральное слово); результат зависит от распределения шума и числа отрицательных примеров. Сумма значений по словам не обязана равняться единице.

Как сэмплируются негативы?

Есть два полезных способа получить отрицательные примеры: выбирать слова из распределения шума, как в word2vec, или использовать другие примеры батча, как в CLIP и DPR.

Возведение частот в степень меньше единицы снижает преобладание частых слов, сохраняя их порядок. Доля вероятности служебных слов зависит от корпуса; универсального процента нет.

В работе о negative sampling показатель 0.75 дал лучшие результаты, чем униграммная и равномерная выборки в проведённых экспериментах:

P(w) — вероятность шумовой выборки. Знаменатель нормализует частоты, возведённые в степень; он вычисляется по корпусу, а не по текущим оценкам модели.

Когда распределение готово, сэмплирование тривиально: вычислите P(w) для каждого слова словаря по формуле выше, а затем для каждой позитивной пары (center, context) вытяните k случайных слов из этого распределения — взвешенный бросок кости по словарю, повторённый k раз, где слова с бо́льшим P(w) выпадают чаще.

При внутрибатчевых отрицательных примерах кандидатами для сравнения служат остальные элементы текущего батча.

В батче из N размеченных пар (Qi, Pi) берём Pi как положительный пример для Qi, остальные — как отрицательные. Это назначение обучающих меток, а не доказательство отсутствия смысловой связи вне диагонали:

batch:    (Q1, P1)   (Q2, P2)   (Q3, P3)   (Q4, P4)

for Q1:   positive = P1,   negatives = {P2, P3, P4}
for Q2:   positive = P2,   negatives = {P1, P3, P4}
for Q3:   positive = P3,   negatives = {P1, P2, P4}
for Q4:   positive = P4,   negatives = {P1, P2, P3}

Энкодеры уже вычислили все N векторов кандидатов. Их повторное использование не требует новых проходов энкодера, но матрица оценок N×N всё равно требует вычислений и памяти. Батч из 256 примеров даёт 255 отрицательных кандидатов на запрос.

Другие кандидаты тоже могут быть релевантны запросу, создавая ложные отрицательные примеры. На обучение влияют состав батча, обработка дубликатов и выбор сложных отрицательных примеров; внутрибатчевые примеры не обязательно лучше.

Функция потерь

Функция потерь. Потери на пару — это сумма k+1 слагаемых log-сигмоиды (одно для позитива, по одному на каждый негатив) вместо −log P(target | center) полного softmax:

loss = − log σ(v_c · v'_t)  −  Σ log σ(−v_c · v'_n)
       ─────────────────       ───────────────────────
       true (positive) pair     k sampled negatives

Здесь v_c — входной эмбеддинг центрального слова, v'_t — выходной эмбеддинг настоящей цели, v'_n — выходной эмбеддинг засэмплированного негативного слова, а σ — сигмоида. Первое слагаемое толкает скалярное произведение настоящей пары вверх (к σ(·) = 1); второе толкает скалярное произведение каждого негатива вниз (к σ(·) = 0).

В негативном слагаемом стоит σ(−v_c · v'_n) — минус скалярное произведение, — и это работает благодаря тождеству σ(−x) = 1 − σ(x). Так что −log σ(−v_c · v'_n) — это просто −log(1 − σ(v_c · v'_n)): стандартная половина кросс-энтропии «неверный класс», применённая в направлении «это не настоящая пара». Каждое слагаемое функции потерь — это бинарная кросс-энтропия (BCE), применённая к одной паре (center, w): метка 1 для позитива, метка 0 для каждого негатива. Суммарные потери — это k+1 сложенных BCE.

Потеря растёт, когда модель даёт низкую вероятность наблюдаемой метке. Производная по логиту равна σ(z) − y и ограничена диапазоном от −1 до 1. Большая потеря не означает неограниченный градиент по логиту.

Каждое оценённое слово вносит одно слагаемое — −log σ для позитива, −log(1 − σ) для каждого негатива:

Итого: L ≈ 1.95. Больше всех вносит mat — его σ (0.56) дальше всего от того, где должен быть негатив (0).

Метки выборок моделируются как условно независимые наблюдения Бернулли при заданных оценках. Произведение их правдоподобий после отрицательного логарифмирования даёт эту сумму. При этом слагаемые разделяют параметры центрального вектора.

P(all right)  =  P(positive right) × P(neg₁ right) × … × P(neg_k right)

−log превращает произведение в сумму:

−log P(all right)  =  −log P(positive)  +  −log P(neg₁)  +  …  +  −log P(neg_k)

Softmax моделирует категорию контекстного слова, а negative sampling — метку «данные или шум». Они оптимизируют разные правдоподобия и отвечают на разные вопросы. Ни один из методов не гарантирует калибровку на новых данных.

Градиент

В обычном SGD без регуляризации обновляются только входная строка центрального слова и выбранные выходные строки. Для повторных выборок вклады суммируются. Все градиенты нужно вычислять по одним и тем же значениям параметров до обновления.

Чтобы минимизировать L, нам нужен её градиент по каждому параметру, участвовавшему в прямом проходе: v_c (строка центра в E), v'_t (строка цели в Ep) и каждый v'_n (по строке на негатив). С одним фактом из анализа —

d/dz [ −log σ(z) ] = σ(z) − 1

— цепное правило даёт все три:

∂L / ∂v'_t = (σ_t − 1) · v_c                       ← выходная строка цели
∂L / ∂v'_n = σ_n · v_c                             ← выходная строка каждого негатива
∂L / ∂v_c  = (σ_t − 1) · v'_t  +  Σ_n σ_n · v'_n   ← входная строка центра

где σ_t = σ(v_c · v'_t) и σ_n = σ(v_c · v'_n) — ровно те числа, что в разделе ### Функция потерь выше.

Обратите внимание на симметрию: любой градиент по выходной строке (∂L/∂v'_t, ∂L/∂v'_n) — это скаляр, умноженный на v_c, а градиент центра — взвешенная сумма выходных строк, против которых он оценивался. Это прямое следствие симметричности скалярного произведения по своим аргументам: дифференцирование любого f(v_c · v'_w) по v'_w всегда даёт нечто, пропорциональное v_c, и наоборот.

Обновление положительного выходного вектора добавляет кратное v_c, а отрицательного — вычитает. При фиксированном v_c это увеличивает или уменьшает скалярное произведение. «Притяжение» и «отталкивание» описывают изменение оценки, а не гарантированное изменение евклидова расстояния.

По неокруглённым значениям сигмоиды из виджета оценок получаем градиент центрального вектора:

∂L/∂v_c = (σ_on − 1) · v'_on + σ_cat · v'_cat + σ_mat · v'_mat
        ≈ [−0.0435, 0.5269, 0.0717]

Положительные обновления имеют общий множитель η(1 − σ_t), но их длины равны η(1 − σ_t)‖v_c‖ и η(1 − σ_t)‖v'_t‖. Они совпадают только при равных нормах векторов. Центральный вектор также получает все отрицательные вклады.

Обновление

Градиентный спуск со скоростью обучения η:

v'_t ← v'_t + η · (1 − σ_t) · v_c                    ← шаг к v_c
v'_n ← v'_n − η · σ_n · v_c                          ← шаг прочь от v_c
v_c  ← v_c  + η · (1 − σ_t) · v'_t  −  η · Σ_n σ_n · v'_n
                                                      ← к v'_t, прочь от каждого v'_n

Большая ошибка сигмоиды даёт больший коэффициент, но длина обновления зависит и от нормы вектора. Разные пары могут давать конфликтующие градиенты, а большой шаг — перескакивать минимум. Потеря не обязана уменьшаться на каждом шаге.

Подстановка градиента сверху при η = 0.1 сдвигает центр:

v_c     = [0.33, −0.27, 0.84]
v_c_new = v_c − 0.1 · ∂L/∂v_c ≈ [0.3344, −0.3227, 0.8328]

Шаг маленький, но в том направлении, которого требует функция потерь. v'_on, v'_cat и v'_mat получают в тот же момент свои собственные обновления по формулам выше; мы сосредоточились на v_c, чтобы не растягивать разбор.

Проверяем шаг

Сначала обновим только v_c, зафиксировав выходные векторы, чтобы выделить вклад центрального:

При обновлении только центрального вектора потеря снижается с 1,9512 до 1,9229. Одновременное обновление выходных векторов по тем же старым значениям даёт 1,8626. Это результат данного примера и шага обучения, а не гарантия для каждого обновления.

Почему negative sampling обучает полезные векторы

Negative sampling не является несмещённой оценкой градиента полного softmax. Обе цели поощряют наблюдаемые связи, но по-разному взвешивают конкурирующие слова. Различение совместных появлений и шума позволяет учить полезные представления без воспроизведения решения softmax.

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

Следующий виджет обучается на нескольких парах и показывает изменение входных векторов:

Демонстрация обучается на специально составленном синтетическом корпусе. Каждый шаг обрабатывает пару и выбирает пять отрицательных примеров с возвращением из сглаженного частотного распределения; возможны совпадения с положительным словом. График показывает только входные векторы; выходные обучаются отдельно. Цвета служат читателю и не участвуют в обучении. Два измерения выбраны для визуализации и не гарантируют чёткие семантические группы.

Шаг NumPy ниже копирует нужные векторы до обновления обеих таблиц. np.add.at правильно накапливает вклады повторных выходных индексов, включая слово, выбранное и положительным, и отрицательным. E и Ep — отдельные вещественные массивы формы (V, d).

import numpy as np

def sgns_step(E, Ep, c, t, negatives, lr=0.1):
    rows = np.r_[t, np.asarray(negatives, dtype=int)]
    labels = np.zeros(len(rows))
    labels[0] = 1
    center = E[c].copy()
    outputs = Ep[rows].copy()
    logits = outputs @ center
    z = np.exp(-np.abs(logits))
    probabilities = np.where(logits >= 0, 1 / (1 + z), z / (1 + z))
    errors = probabilities - labels
    grad_center = errors @ outputs
    grad_outputs = errors[:, None] * center
    loss = np.sum(np.logaddexp(0, logits) - labels * logits)
    np.add.at(Ep, rows, -lr * grad_outputs)
    E[c] -= lr * grad_center
    return float(loss)  # loss before the update

# rng is a NumPy Generator; neg_dist sums to 1 over V words.
for c, t in pairs:
    negatives = rng.choice(len(E), size=k, replace=True, p=neg_dist)
    loss = sgns_step(E, Ep, c, t, negatives, lr)

Для неограниченной оценки и k независимых отрицательных выборок из q популяционный оптимум равен s*(c,w) = log[P_data(w|c) / (k q(w))]. При q(w) = P_data(w) получаем PMI(c,w) − log(k). Распределение q(w) ∝ count(w)^0.75 меняет поправку. Векторы конечной размерности лишь приближают эту матрицу идеальных оценок.

Эта связь лежит в основе анализа сдвинутой PMI Леви и Голдберга. Она объясняет смысл оценок SGNS, но не делает цели SGNS, SVD и полного softmax взаимозаменяемыми.

Что и когда использовать

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

Предсказание маскированных токенов BERT и авторегрессионное языковое моделирование обычно используют softmax по словарю. Поисковые системы часто сравнивают релевантный объект с выбранными или внутрибатчевыми кандидатами. Выбор кандидатов — отдельный вопрос от выбора сигмоидной или softmax-потери.

DPR обучает оценки запрос–пассаж через softmax по кандидатам. Модели награды учат относительные оценки ответов, часто через −log σ(r_preferred − r_rejected); это ранжирование, а не шумовая цель word2vec. CLIP — ещё один пример контрастивного обучения с softmax.

CLIP: сравнение изображений и подписей

CLIP обучали на 400 миллионах пар изображение–текст. Несопоставленные пары батча служат отрицательными примерами, но потеря — симметричная кросс-энтропия с softmax, а не независимые бинарные потери negative sampling word2vec.

В исходных экспериментах CLIP текстовый трансформер сочетался с ResNet или визуальным трансформером. Проекционные слои переводят оба выхода в общее пространство, размерность которого зависит от варианта модели.

Для каждого обучающего батча из N пар (I_1, T_1), ..., (I_N, T_N):

Нормализуем оба набора векторов по L2 и вычисляем S[i,j] = exp(t) × dot(image[i], text[j]), где t — обучаемый логарифм масштаба. Скалярное произведение теперь равно косинусному сходству. Вычисляем кросс-энтропию по строкам и столбцам с целевым индексом i, затем усредняем две средние потери. Диагональ помечена положительной, но вне неё возможны ложные отрицательные пары. См. реализацию CLIP.

Исходный обучающий батч содержал 32 768 пар: по 32 767 отрицательных кандидатов-подписей на изображение. Выходы энкодеров используются повторно, но попарные оценки и синхронизация векторов между устройствами всё равно требуют ресурсов.

Что вы получаете: пространство эмбеддингов, где семантически связанные изображения и тексты оказываются рядом, а несвязанные — далеко. Поэтому CLIP умеет zero-shot-классификацию изображений: вычислите текстовые эмбеддинги для названий классов («фотография собаки», «фотография кошки» и т. д.), а затем классифицируйте изображение по тому, к какому эмбеддингу класса оно ближе. Геометрия, вырезанная контрастной функцией потерь, уже кодирует смысл в обеих модальностях; размеченный классификатор не нужен.

Обычное скалярное произведение не равно косинусу: SGNS может менять и нормы векторов, и углы. CLIP нормализует векторы и обучает масштаб оценок. Эти различия не задают универсальный целевой угол для отрицательных пар и сами по себе не объясняют требуемый размер батча.

Общая идея — обучение на сравнениях. Детали важны: SGNS классифицирует выбранные пары независимо, а CLIP заставляет кандидатов конкурировать через softmax. Схему выборки и потерю нужно выбирать вместе, исходя из смысла требуемых оценок.