.. _sec_approx_train: Приближённое обучение ===================== Вспомним наши обсуждения в :numref:`sec_word2vec`. Основная идея модели skip-gram заключается в использовании операций софтмакс для вычисления условной вероятности появления контекстного слова :math:`w_o` при заданном центральном слове :math:`w_c` в :eq:`eq_skip-gram-softmax`, соответствующая логарифмическая потеря определяется как величина, противоположная :eq:`eq_skip-gram-log`. Из-за природы операции софтмакс, поскольку контекстное слово может быть любым из слов в словаре :math:`\mathcal{V}`, величина, обратная :eq:`eq_skip-gram-log`, содержит сумму слагаемых, количество которых равно размеру всего словаря. Следовательно, вычисление градиента для модели skip-gram в :eq:`eq_skip-gram-grad` и для модели continuous bag-of-words в :eq:`eq_cbow-gradient` включает суммирование. К сожалению, вычислительная стоимость таких градиентов, требующих суммирования по большому словарю (часто содержащему сотни тысяч или миллионы слов), оказывается огромной! Чтобы снизить указанную выше вычислительную сложность, в этом разделе будут рассмотрены два метода приближенного обучения: *отрицательная выборка* и *иерархический софтмакс*. Ввиду схожести модели skip-gram и модели непрерывного мешка слов (CBOW) в качестве примера для описания этих двух методов приближенного обучения мы будем использовать только модель skip-gram. .. _subsec_negative-sampling: Отрицательная выборка --------------------- Отрицательная выборка изменяет исходную целевую функцию. Учитывая контекстное окно центрального слова :math:`w_c`, тот факт, что любое (контекстное) слово :math:`w_o` взято из этого контекстного окна, рассматривается как событие с вероятностью, моделируемой .. math:: P(D=1\mid w_c, w_o) = \sigma(\mathbf{u}_o^\top \mathbf{v}_c), где :math:`\sigma` использует определение функции активации сигмоиды: .. math:: \sigma(x) = \frac{1}{1+\exp(-x)}. :label: eq_sigma-f Начнем с максимизации совместной вероятности всех таких событий в текстовых последовательностях для обучения векторных представлений слов. В частности, пусть дана текстовая последовательность длины :math:`T`, обозначим через :math:`w^{(t)}` слово на шаге времени :math:`t`, а размер контекстного окна примем равным :math:`m`. Рассмотрим задачу максимизации совместной вероятности .. math:: \prod_{t=1}^{T} \prod_{-m \leq j \leq m,\ j \neq 0} P(D=1\mid w^{(t)}, w^{(t+j)}). :label: eq-negative-sample-pos Однако :eq:`eq-negative-sample-pos` учитывает только те события, которые включают положительные примеры. В результате совместная вероятность в :eq:`eq-negative-sample-pos` достигает максимума, равного 1, только если все векторы слов стремятся к бесконечности. Очевидно, такие результаты бессмысленны. Чтобы сделать целевую функцию более осмысленной, *отрицательная выборка* добавляет отрицательные примеры, выбранные из заранее определённого распределения. Обозначим через :math:`S` событие, что контекстное слово :math:`w_o` взято из контекстного окна центрального слова :math:`w_c`. Для этого события, включающего :math:`w_o`, из заранее заданного распределения :math:`P(w)` выберем :math:`K` *шумовых примеров*, которые не принадлежат этому контекстному окну. Обозначим через :math:`N_k` событие, что шумовой пример :math:`w_k` (:math:`k=1, \ldots, K`) не взят из контекстного окна слова :math:`w_c`. Будем считать, что эти события, включающие как положительные примеры, так и отрицательные примеры :math:`S, N_1, \ldots, N_K`, являются взаимно независимыми. Метод отрицательной выборки переписывает совместную вероятность (включающую только положительные примеры) из :eq:`eq-negative-sample-pos` следующим образом: .. math:: \prod_{t=1}^{T} \prod_{-m \leq j \leq m,\ j \neq 0} P(w^{(t+j)} \mid w^{(t)}), где условная вероятность аппроксимируется через события :math:`S, N_1, \ldots, N_K`: .. math:: 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). :label: eq-negative-sample-conditional-prob Обозначим через :math:`i_t` и :math:`h_k` индексы слова :math:`w^{(t)}` на шаге :math:`t` в последовательности текста и шумового слова :math:`w_k` соответственно. Логарифмическая функция потерь относительно условных вероятностей в :eq:`eq-negative-sample-conditional-prob` имеет вид .. math:: \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} Мы видим, что теперь вычислительная стоимость вычисления градиентов на каждом шаге обучения не зависит от размера словаря, а линейно зависит от :math:`K`. При задании гиперпараметру :math:`K` меньшего значения вычислительная стоимость вычисления градиентов на каждом шаге обучения с отрицательной выборкой снижается. Иерархический софтмакс ---------------------- В качестве альтернативного приближённого метода обучения *иерархический софтмакс* использует бинарное дерево — структуру данных, показанную на рисунке :numref:`fig_hi_softmax`, где каждый листовой узел дерева представляет слово из словаря :math:`\mathcal{V}`. .. _fig_hi_softmax: .. figure:: ../img/hi-softmax.svg Иерархический софтмакс для приближённого обучения, где каждый листовой узел дерева представляет слово из словаря. Обозначим через :math:`L(w)` количество узлов (включая оба конца) на пути от корневого узла до листового узла, представляющего слово :math:`w` в бинарном дереве. Пусть :math:`n(w,j)` будет :math:`j^\textrm{th}` узлом на этом пути, а его вектором контекстного слова — :math:`\mathbf{u}_{n(w, j)}`. Например, :math:`L(w_3) = 4` в :numref:`fig_hi_softmax`. Иерархический софтмакс аппроксимирует условную вероятность в :eq:`eq_skip-gram-softmax` как .. math:: 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), где функция :math:`\sigma` задана в :eq:`eq_sigma-f`, а :math:`\textrm{leftChild}(n)` — левый дочерний узел узла :math:`n`: если :math:`x` истинно, то :math:`[\![x]\!] = 1`, иначе :math:`[\![x]\!] = -1`. Для наглядности рассчитаем условную вероятность генерации слова :math:`w_3` при условии появления слова :math:`w_c` в контексте :numref:`fig_hi_softmax`. Для этого необходимо вычислить скалярные произведения между вектором слова :math:`\mathbf{v}_c` для :math:`w_c` и векторами внутренних узлов на пути (выделен жирным на рисунке :numref:`fig_hi_softmax`) от корня до :math:`w_3`, который проходит влево, затем вправо и снова влево: .. math:: 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). Поскольку :math:`\sigma(x)+\sigma(-x) = 1`, сумма условных вероятностей генерации всех слов из словаря :math:`\mathcal{V}` по любому слову :math:`w_c` равна единице: .. math:: \sum_{w \in \mathcal{V}} P(w \mid w_c) = 1. :label: eq_hi-softmax-sum-one К счастью, поскольку :math:`L(w_o)-1` имеет порядок величины :math:`\mathcal{O}(\textrm{log}_2|\mathcal{V}|)` благодаря структуре бинарного дерева, при огромном размере словаря :math:`\mathcal{V}` вычислительные затраты на каждый шаг обучения с использованием иерархического софтмакса значительно снижаются по сравнению с подходом без приближённого обучения. Итоги ----- - Отрицательная выборка формирует функцию потерь, рассматривая взаимно независимые события, включающие как положительные, так и отрицательные примеры. Вычислительная стоимость обучения линейно зависит от количества шумовых слов на каждом шаге. - Иерархический софтмакс формирует функцию потерь, используя путь от корневого узла к листовому узлу в бинарном дереве. Вычислительная сложность при обучении зависит от логарифма размера словаря на каждом шаге. Упражнения ---------- 1. Как мы можем выбирать примеры шумовых слов при отрицательной выборке? 2. Проверьте, что выполняется :eq:`eq_hi-softmax-sum-one`. 3. Как обучить модель непрерывного мешка слов с использованием отрицательной выборки и иерархического софтмакса соответственно? `Обсуждения `__