10.8. Лучевой поиск¶
В разделе Section 10.7 мы познакомились с архитектурой кодировщик–декодировщик и стандартными методами её сквозного обучения. Однако при обсуждении предсказаний на этапе тестирования мы упомянули лишь жадную стратегию, при которой на каждом временном шаге выбирается токен с наибольшей предсказанной вероятностью появления следующим, пока на каком-то шаге не будет сгенерирован специальный токен конца последовательности «<eos>». В этом разделе мы сначала формализуем стратегию жадного поиска и укажем на некоторые проблемы, с которыми часто сталкиваются практикующие специалисты. Затем мы сравним эту стратегию с двумя альтернативами: полным перебором (иллюстративным, но непрактичным) и лучевым поиском (стандартным методом, применяемым на практике).
Начнем с введения математических обозначений, заимствуя соглашения из Section 10.7. На любом шаге времени \(t'\) декодировщик выдает предсказания, представляющие вероятность каждого токена в словаре быть следующим в последовательности (вероятное значение \(y_{t'+1}\)), при условии предыдущих токенов \(y_1, \ldots, y_{t'}\) и переменной контекста \(\mathbf{c}\), сгенерированной кодировщиком для представления входной последовательности. Для количественной оценки вычислительных затрат обозначим через \(\mathcal{Y}\) выходной словарь (включая специальный токен конца последовательности “<eos>”). Также определим максимальное количество токенов в выходной последовательности как \(T'\). Наша цель — найти оптимальный выход из всех \(\mathcal{O}(\left|\mathcal{Y}\right|^{T'})\) возможных выходных последовательностей. Обратите внимание, что это немного завышает количество различных выходов, поскольку после появления токена “<eos>” последующие токены отсутствуют. Однако для наших целей это число примерно отражает размер пространства поиска.
10.8.1. Жадный поиск¶
Рассмотрим простую стратегию жадного поиска из Section 10.7. На каждом временном шаге \(t'\) мы просто выбираем токен с наибольшей условной вероятностью из \(\mathcal{Y}\), то есть
Как только наша модель выводит <eos> (или мы достигаем максимальной
длины \(T'\)), выходная последовательность завершается.
Эта стратегия может показаться разумной, и на самом деле она не так уж плоха! Учитывая её низкие вычислительные затраты, трудно найти более выгодное решение. Однако, если отложить в сторону вопросы эффективности, более разумным может показаться поиск наиболее вероятной последовательности, а не последовательности из (жадно выбранных) наиболее вероятных токенов. Оказывается, эти два объекта могут существенно различаться. Наиболее вероятная последовательность — это та, которая максимизирует выражение \(\prod_{t'=1}^{T'} P(y_{t'} \mid y_1, \ldots, y_{t'-1}, \mathbf{c})\). В нашем примере машинного перевода, если бы декодировщик действительно восстанавливал вероятности лежащего в основе процесса генерации, это дало бы нам наиболее вероятный перевод. К сожалению, нет никаких гарантий, что жадный поиск даст нам именно эту последовательность.
Проиллюстрируем это на примере. Предположим, что в выходном словаре содержатся четыре токена: «A», «B», «C» и «<eos>». На рисунке Fig. 10.8.1 четыре числа под каждым временным шагом обозначают условные вероятности генерации токенов «A», «B», «C» и «<eos>» соответственно в этот момент времени.
Fig. 10.8.1 На каждом временном шаге жадный поиск выбирает токен с наибольшей условной вероятностью.¶
На каждом временном шаге жадный поиск выбирает токен с наибольшей условной вероятностью. Следовательно, будет предсказана выходная последовательность «A», «B», «C» и «<eos>» (Fig. 10.8.1). Условная вероятность этой выходной последовательности составляет \(0.5\times0.4\times0.4\times0.6 = 0.048\).
Далее рассмотрим другой пример в Fig. 10.8.2. В отличие от Fig. 10.8.1, на шаге 2 мы выбираем токен «C», имеющий вторую по величине условную вероятность.
Fig. 10.8.2 Четыре числа под каждым временным шагом представляют условные вероятности генерации токенов «A», «B», «C» и «<eos>» на данном временном шаге. На втором временном шаге выбирается токен «C», имеющий вторую по величине условную вероятность.¶
Поскольку выходные подпоследовательности на шагах 1 и 2, на которых основывается шаг 3, изменились с «A» и «B» в Fig. 10.8.1 на «A» и «C» в Fig. 10.8.2, условная вероятность каждого токена на шаге 3 также изменилась в Fig. 10.8.2. Предположим, что на шаге 3 мы выбираем токен «B». Теперь шаг 4 зависит от выходной подпоследовательности за первые три шага — «A», «C» и «B», которая изменилась по сравнению с «A», «B» и «C» в Fig. 10.8.1. Следовательно, условная вероятность генерации каждого токена на шаге 4 в Fig. 10.8.2 также отличается от той, что в Fig. 10.8.1. В результате условная вероятность выходной последовательности «A», «C», «B» и «<eos>» в Fig. 10.8.2 равна \(0.5\times0.3 \times0.6\times0.6=0.054\), что больше, чем вероятность при жадном поиске в Fig. 10.8.1. В этом примере выходная последовательность «A», «B», «C» и «<eos>», полученная с помощью жадного поиска, не является оптимальной.
10.8.2. Полный перебор¶
Если цель состоит в том, чтобы получить наиболее вероятную последовательность, можно рассмотреть возможность использования полного перебора: перебрать все возможные выходные последовательности вместе с их условными вероятностями, а затем выбрать ту, которая имеет наибольшую предсказанную вероятность.
Хотя такой подход, безусловно, даст нам желаемый результат, он потребует непомерно высоких вычислительных затрат, равных \(\mathcal{O}(\left|\mathcal{Y}\right|^{T'})\), экспоненциально растущих от длины последовательности и имеющих огромный базис, определяемый размером словаря. Например, когда \(|\mathcal{Y}|=10000\) и \(T'=10\), оба значения невелики по сравнению с теми, что встречаются в реальных приложениях, нам придётся оценить \(10000^{10} = 10^{40}\) последовательностей, что уже выходит за рамки возможностей любых предсказуемых компьютеров. С другой стороны, вычислительная стоимость жадного поиска составляет \(\mathcal{O}(\left|\mathcal{Y}\right|T')\): удивительно дешево, но далеко не оптимально. Например, когда \(|\mathcal{Y}|=10000\) и \(T'=10\), нам нужно оценить лишь \(10000\times10=10^5\) последовательностей.
10.8.3. Лучевой поиск¶
Стратегии декодирования последовательностей можно рассматривать как находящиеся на одном спектре, где лучевой поиск представляет собой компромисс между эффективностью жадного поиска и оптимальностью полного перебора. Наиболее простая версия лучевого поиска характеризуется одним гиперпараметром — размером луча, \(k\). Рассмотрим эту терминологию. На шаге 1 мы выбираем \(k\) токенов с наибольшими предсказанными вероятностями. Каждый из них станет первым токеном для \(k\) кандидатных выходных последовательностей соответственно. На каждом последующем шаге, опираясь на \(k\) кандидатных выходных последовательностей с предыдущего шага, мы продолжаем выбирать \(k\) кандидатных выходных последовательностей с наибольшими предсказанными вероятностями из \(k\left|\mathcal{Y}\right|\) возможных вариантов.
Fig. 10.8.3 Процесс лучевого поиска (размер луча \(=2\); максимальная длина выходной последовательности \(=3\)). Кандидатные выходные последовательности — это \(\mathit{A}\), \(\mathit{C}\), \(\mathit{AB}\), \(\mathit{CE}\), \(\mathit{ABD}\) и \(\mathit{CED}\).¶
Fig. 10.8.3 демонстрирует процесс лучевого поиска на примере. Предположим, что выходной словарь содержит всего пять элементов: \(\mathcal{Y} = \{A, B, C, D, E\}\), среди которых есть «<eos>». Пусть размер луча равен двум, а максимальная длина выходной последовательности — трём. На шаге 1 предположим, что токены с наибольшими условными вероятностями \(P(y_1 \mid \mathbf{c})\) — это \(A\) и \(C\). На шаге 2 для всех \(y_2 \in \mathcal{Y},\) мы вычисляем
и выберем два наибольших значения из этих десяти, например \(P(A, B \mid \mathbf{c})\) и \(P(C, E \mid \mathbf{c})\). Затем на шаге 3 для всех \(y_3 \in \mathcal{Y}\) вычислим
и выбрать два наибольших среди этих десяти значений, скажем \(P(A, B, D \mid \mathbf{c})\) и \(P(C, E, D \mid \mathbf{c}).\). В результате мы получим шесть кандидатов в выходные последовательности: (i) \(A\); (ii) \(C\); (iii) \(A\), \(B\); (iv) \(C\), \(E\); (v) \(A\), \(B\), \(D\); и (vi) \(C\), \(E\), \(D\).
В итоге мы получаем множество финальных кандидатов на выходную последовательность на основе этих шести последовательностей (например, отбрасываем фрагменты, включая и после «<eos>»). Затем мы выбираем выходную последовательность, которая максимизирует следующий показатель:
где \(L\) — длина итоговой кандидатской последовательности, а \(\alpha\) обычно принимается равным 0,75. Поскольку в сумме (10.8.4) более длинная последовательность содержит больше логарифмических слагаемых, член \(L^\alpha\) в знаменателе штрафует за длинные последовательности.
Вычислительная сложность лучевого поиска составляет \(\mathcal{O}(k\left|\mathcal{Y}\right|T')\). Этот результат находится между сложностью жадного поиска и полным перебором. Жадный поиск можно рассматривать как частный случай лучевого поиска, возникающий при размере луча, равном 1.
10.8.4. Итоги¶
Стратегии поиска последовательностей включают жадный поиск, полный перебор и лучевой поиск. Лучевой поиск обеспечивает баланс между точностью и вычислительными затратами за счёт гибкого выбора размера луча.
10.8.5. Упражнения¶
Можно ли рассматривать полный перебор как частный случай лучевого поиска? Почему да или почему нет?
Примените лучевой поиск к задаче машинного перевода в Section 10.7. Как размер луча влияет на результаты перевода и скорость предсказания?
В разделе Section 9.5 мы использовали языковое моделирование для генерации текста по заданным пользователем префиксам. Какую стратегию поиска она использует? Можно ли её улучшить?