15.2. Приближённое обучение

Вспомним наши обсуждения в Section 15.1. Основная идея модели skip-gram заключается в использовании операций софтмакс для вычисления условной вероятности появления контекстного слова \(w_o\) при заданном центральном слове \(w_c\) в (15.1.4), соответствующая логарифмическая потеря определяется как величина, противоположная (15.1.7).

Из-за природы операции софтмакс, поскольку контекстное слово может быть любым из слов в словаре \(\mathcal{V}\), величина, обратная (15.1.7), содержит сумму слагаемых, количество которых равно размеру всего словаря. Следовательно, вычисление градиента для модели skip-gram в (15.1.8) и для модели continuous bag-of-words в (15.1.15) включает суммирование. К сожалению, вычислительная стоимость таких градиентов, требующих суммирования по большому словарю (часто содержащему сотни тысяч или миллионы слов), оказывается огромной!

Чтобы снизить указанную выше вычислительную сложность, в этом разделе будут рассмотрены два метода приближенного обучения: отрицательная выборка и иерархический софтмакс. Ввиду схожести модели skip-gram и модели непрерывного мешка слов (CBOW) в качестве примера для описания этих двух методов приближенного обучения мы будем использовать только модель skip-gram.

15.2.1. Отрицательная выборка

Отрицательная выборка изменяет исходную целевую функцию. Учитывая контекстное окно центрального слова \(w_c\), тот факт, что любое (контекстное) слово \(w_o\) взято из этого контекстного окна, рассматривается как событие с вероятностью, моделируемой

(15.2.1)\[P(D=1\mid w_c, w_o) = \sigma(\mathbf{u}_o^\top \mathbf{v}_c),\]

где \(\sigma\) использует определение функции активации сигмоиды:

(15.2.2)\[\sigma(x) = \frac{1}{1+\exp(-x)}.\]

Начнем с максимизации совместной вероятности всех таких событий в текстовых последовательностях для обучения векторных представлений слов. В частности, пусть дана текстовая последовательность длины \(T\), обозначим через \(w^{(t)}\) слово на шаге времени \(t\), а размер контекстного окна примем равным \(m\). Рассмотрим задачу максимизации совместной вероятности

(15.2.3)\[\prod_{t=1}^{T} \prod_{-m \leq j \leq m,\ j \neq 0} P(D=1\mid w^{(t)}, w^{(t+j)}).\]

Однако (15.2.3) учитывает только те события, которые включают положительные примеры. В результате совместная вероятность в (15.2.3) достигает максимума, равного 1, только если все векторы слов стремятся к бесконечности. Очевидно, такие результаты бессмысленны. Чтобы сделать целевую функцию более осмысленной, отрицательная выборка добавляет отрицательные примеры, выбранные из заранее определённого распределения.

Обозначим через \(S\) событие, что контекстное слово \(w_o\) взято из контекстного окна центрального слова \(w_c\). Для этого события, включающего \(w_o\), из заранее заданного распределения \(P(w)\) выберем \(K\) шумовых примеров, которые не принадлежат этому контекстному окну. Обозначим через \(N_k\) событие, что шумовой пример \(w_k\) (\(k=1, \ldots, K\)) не взят из контекстного окна слова \(w_c\). Будем считать, что эти события, включающие как положительные примеры, так и отрицательные примеры \(S, N_1, \ldots, N_K\), являются взаимно независимыми. Метод отрицательной выборки переписывает совместную вероятность (включающую только положительные примеры) из (15.2.3) следующим образом:

(15.2.4)\[\prod_{t=1}^{T} \prod_{-m \leq j \leq m,\ j \neq 0} P(w^{(t+j)} \mid w^{(t)}),\]

где условная вероятность аппроксимируется через события \(S, N_1, \ldots, N_K\):

(15.2.5)\[P(w^{(t+j)} \mid w^{(t)}) =P(D=1\mid w^{(t)}, w^{(t+j)})\prod_{k=1,\ w_k \sim P(w)}^K P(D=0\mid w^{(t)}, w_k).\]

Обозначим через \(i_t\) и \(h_k\) индексы слова \(w^{(t)}\) на шаге \(t\) в последовательности текста и шумового слова \(w_k\) соответственно. Логарифмическая функция потерь относительно условных вероятностей в (15.2.5) имеет вид

(15.2.6)\[\begin{split}\begin{aligned} -\log P(w^{(t+j)} \mid w^{(t)}) =& -\log P(D=1\mid w^{(t)}, w^{(t+j)}) - \sum_{k=1,\ w_k \sim P(w)}^K \log P(D=0\mid w^{(t)}, w_k)\\ =&- \log\, \sigma\left(\mathbf{u}_{i_{t+j}}^\top \mathbf{v}_{i_t}\right) - \sum_{k=1,\ w_k \sim P(w)}^K \log\left(1-\sigma\left(\mathbf{u}_{h_k}^\top \mathbf{v}_{i_t}\right)\right)\\ =&- \log\, \sigma\left(\mathbf{u}_{i_{t+j}}^\top \mathbf{v}_{i_t}\right) - \sum_{k=1,\ w_k \sim P(w)}^K \log\sigma\left(-\mathbf{u}_{h_k}^\top \mathbf{v}_{i_t}\right). \end{aligned}\end{split}\]

Мы видим, что теперь вычислительная стоимость вычисления градиентов на каждом шаге обучения не зависит от размера словаря, а линейно зависит от \(K\). При задании гиперпараметру \(K\) меньшего значения вычислительная стоимость вычисления градиентов на каждом шаге обучения с отрицательной выборкой снижается.

15.2.2. Иерархический софтмакс

В качестве альтернативного приближённого метода обучения иерархический софтмакс использует бинарное дерево — структуру данных, показанную на рисунке Fig. 15.2.1, где каждый листовой узел дерева представляет слово из словаря \(\mathcal{V}\).

Fig. 15.2.1 Иерархический софтмакс для приближённого обучения, где каждый листовой узел дерева представляет слово из словаря.

Обозначим через \(L(w)\) количество узлов (включая оба конца) на пути от корневого узла до листового узла, представляющего слово \(w\) в бинарном дереве. Пусть \(n(w,j)\) будет \(j^\textrm{th}\) узлом на этом пути, а его вектором контекстного слова — \(\mathbf{u}_{n(w, j)}\). Например, \(L(w_3) = 4\) в Fig. 15.2.1. Иерархический софтмакс аппроксимирует условную вероятность в (15.1.4) как

(15.2.7)\[P(w_o \mid w_c) = \prod_{j=1}^{L(w_o)-1} \sigma\left( [\![ n(w_o, j+1) = \textrm{leftChild}(n(w_o, j)) ]\!] \cdot \mathbf{u}_{n(w_o, j)}^\top \mathbf{v}_c\right),\]

где функция \(\sigma\) задана в (15.2.2), а \(\textrm{leftChild}(n)\) — левый дочерний узел узла \(n\): если \(x\) истинно, то \([\![x]\!] = 1\), иначе \([\![x]\!] = -1\).

Для наглядности рассчитаем условную вероятность генерации слова \(w_3\) при условии появления слова \(w_c\) в контексте Fig. 15.2.1. Для этого необходимо вычислить скалярные произведения между вектором слова \(\mathbf{v}_c\) для \(w_c\) и векторами внутренних узлов на пути (выделен жирным на рисунке Fig. 15.2.1) от корня до \(w_3\), который проходит влево, затем вправо и снова влево:

(15.2.8)\[P(w_3 \mid w_c) = \sigma(\mathbf{u}_{n(w_3, 1)}^\top \mathbf{v}_c) \cdot \sigma(-\mathbf{u}_{n(w_3, 2)}^\top \mathbf{v}_c) \cdot \sigma(\mathbf{u}_{n(w_3, 3)}^\top \mathbf{v}_c).\]

Поскольку \(\sigma(x)+\sigma(-x) = 1\), сумма условных вероятностей генерации всех слов из словаря \(\mathcal{V}\) по любому слову \(w_c\) равна единице:

(15.2.9)\[\sum_{w \in \mathcal{V}} P(w \mid w_c) = 1.\]

К счастью, поскольку \(L(w_o)-1\) имеет порядок величины \(\mathcal{O}(\textrm{log}_2|\mathcal{V}|)\) благодаря структуре бинарного дерева, при огромном размере словаря \(\mathcal{V}\) вычислительные затраты на каждый шаг обучения с использованием иерархического софтмакса значительно снижаются по сравнению с подходом без приближённого обучения.

15.2.3. Итоги

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

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

15.2.4. Упражнения

1. Как мы можем выбирать примеры шумовых слов при отрицательной выборке?

2. Проверьте, что выполняется (15.2.9).

3. Как обучить модель непрерывного мешка слов с использованием отрицательной выборки и иерархического софтмакса соответственно?

Обсуждения