Лучевой поиск

Лучевой поиск (Beam Search) — это эвристический алгоритм поиска, широко применяемый в задачах генерации последовательностей, таких как машинный перевод, генерация текста, распознавание речи и другие области обработки естественного языка. В отличие от жадного поиска (Greedy Search), который на каждом шаге выбирает только самый вероятный вариант, Beam Search отслеживает несколько лучших вариантов одновременно, что позволяет находить более качественные решения и избегать локальных максимумов.

🧠 Основная идея:

Алгоритм поддерживает фиксированное количество лучших гипотез (путей), называемое шириной луча (beam width). На каждом шаге:

1. Рассматриваются все возможные продолжения текущих гипотез.
2. Для каждой гипотезы вычисляется её вероятность (часто в логарифмической шкале).
3. Выбираются k самых вероятных гипотез, которые становятся основой для следующего шага.

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

⚙️ Пример работы:

Пусть модель переводит слово "I". Возможные продолжения:

• "am" (вероятность 0.6)
• "like" (0.3)
• "have" (0.1)

Если beam width = 2, алгоритм сохранит варианты "I am" и "I like". На следующем шаге для "I am":

• "happy" (0.5)
• "tired" (0.4)
  А для "I like":
• "pizza" (0.7)
• "apples" (0.2)

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

📌 Применение:

• Машинный перевод (Neural Machine Translation, NMT): улучшает качество перевода по сравнению с жадным поиском.
• Генерация текста: позволяет моделям создавать более связные и осмысленные ответы.
• Распознавание речи (ASR): повышает точность преобразования звука в текст.
• Суммаризация текста: выбор наиболее осмысленного сжатого варианта.

⚖️ Преимущества и недостатки:

Преимущества:

• Улучшает качество по сравнению с жадным поиском.
• Находит более оптимальные последовательности.
• Гибкая настройка ширины луча позволяет балансировать между качеством и скоростью.

Недостатки:

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

🧩 Связанные методы:

• Greedy Search — быстрый, но менее качественный метод.
• Top-k Sampling — выбор случайного токена из k наиболее вероятных.
• Top-p (Nucleus) Sampling — выбор токена из минимального множества с суммарной вероятностью ≥ p.
• Diverse Beam Search — модификация, снижающая склонность к однообразным результатам.

💡 Вывод:

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