В задачах машинного перевода или распознавания речи недостаточно просто выдать случайную последовательность слов — необходимо найти наиболее вероятный и грамматически верный вариант. В этом видео Эндрю Ын, основатель DeepLearning.AI, подробно разбирает алгоритм Beam Search (лучевой поиск), который является промышленным стандартом для выбора оптимальных последовательностей в нейронных сетях.
🔍 Проблема выбора в генеративных моделях 0:00
В контексте машинного перевода, имея на входе предложение на французском (например, «Jane visite l'Afrique en septembre»), мы хотим получить на выходе не просто корректный, а максимально вероятный перевод на английский — «Jane visits Africa in September» . Аналогично в системах распознавания речи: по входному аудиоклипу алгоритм должен восстановить наиболее точную текстовую транскрипцию, а не случайный набор слов, похожих на звуки .
Beam Search — это наиболее широко используемый алгоритм для решения подобных задач поиска оптимального пути в пространстве возможных последовательностей .
📏 Понятие ширины луча (Beam Width) 1:20
Основное отличие Beam Search от «жадного поиска» (Greedy Search) заключается в количестве рассматриваемых вариантов на каждом шаге.
- Greedy Search: выбирает только одно самое вероятное слово на текущем шаге и переходит к следующему.
- Beam Search: использует специальный параметр B, называемый шириной луча (beam width) .
Если мы установим ширину луча $B = 3$, алгоритм будет одновременно отслеживать три наиболее вероятных варианта последовательности, а не один . Если $B = 10$, в памяти будут удерживаться десять лучших кандидатов .
🔢 Первый шаг: выбор начального слова 1:59
Процесс начинается с пропуска входного французского предложения через энкодер (зеленый блок нейросети) и первый блок декодера (фиолетовый блок) .
- Декодер выдает распределение вероятностей через softmax по всему словарю (в примере используется словарь из 10 000 слов) .
- Вместо выбора одного слова, Beam Search сохраняет в памяти $B$ слов с самой высокой вероятностью $P(y^{<1>} | x)$ .
- Например, если самыми вероятными оказались слова «in», «Jane» и «September», алгоритм запоминает их все для следующего этапа .
🌳 Расширение дерева поиска: второй шаг 2:50
Для каждого из выбранных на первом шаге слов алгоритм пытается определить второе слово . Теперь задача усложняется: нам нужно найти не просто самое вероятное второе слово, а наиболее вероятную пару слов .
Согласно правилам условной вероятности, вероятность пары выражается формулой: $P(y^{<1>}, y^{<2>} | x) = P(y^{<1>} | x) \times P(y^{<2>} | x, y^{<1>})$ .
Процесс выглядит следующим образом:
- Если первым словом было «in», мы подставляем его в декодер и смотрим вероятности для второго слова («in Africa», «in September» и т.д.) .
- Если первым словом было «Jane», мы делаем то же самое («Jane visits», «Jane is» и т.д.) .
- Для каждой из 10 000 позиций словаря для каждого из $B$ вариантов вычисляется итоговая вероятность пары .
В итоге на втором шаге мы рассматриваем $B \times 10,000$ (в данном случае 30 000) возможных комбинаций . Из этого огромного списка алгоритм снова выбирает только три самые вероятные пары и сохраняет их в памяти .
Важный нюанс: если в тройку лучших пар попали, например, «in September», «Jane is» и «Jane visits», это означает, что слово «September» как вариант первого слова теперь отброшено алгоритмом, так как оно не вошло ни в одну из топовых пар .
⚙️ Вычислительная эффективность 8:25
Несмотря на то что на каждом шаге рассматривается 30 000 вариантов, нет необходимости создавать 30 000 копий нейронной сети. Эндрю Ын подчеркивает, что достаточно иметь лишь столько копий, какова ширина луча ($B = 3$) . Эти три копии позволяют эффективно вычислить значения softmax для всех 10 000 слов одновременно, что значительно ускоряет работу .
🏁 Завершение процесса 9:33
Алгоритм продолжает добавлять по одному слову на каждом шаге:
- Берет лучшие фрагменты из предыдущего шага (например, «Jane visits») .
- Оценивает вероятность третьего слова («Jane visits Africa») при условии входного текста и уже выбранного префикса .
- Снова выбирает топ-3 комбинации .
Процесс повторяется итеративно, пока алгоритм не придет к символу завершения предложения
