Променевий пошук

В інформатиці, променевий пошук – це евристичний алгоритм пошуку, що досліджує граф, розширюючи найперспективніші вузли в обмеженому їх наборі. Променевий пошук є оптимізацією так званого «пошуку першого-найліпшого» (best-first), що суттєво знижує його вимоги до необхідної кількості пам’яті. best-first пошук в графі, що будує усі тимчасові рішення (стани) по деяких евристиках, що намагаються передбачити наскільки близьким є частковий розв’язок до повного розв’язку (цільового стану). В променевому пошуку лише деяка частина найкращих часткових розв’язків зберігаються як кандидати.

Історія

Вперше алгоритм був використаний для системи розпізнавання мовлення HARPY, що була створена Брюсом Ловеа в 1976 році[1][2]. Сам же термін був вперше використаний Реджем Редді у 1977[3][4].

Після цього його використовували у різноманітних задачах, що потребували складних евристик, наприклад для задач планування[2].

У 2006 році Алекс Грейвс запропонував використовувати алгоритм у sequence-to-sequence моделях для перекладу[5][6].

Опис алгоритму

Приклад дерева, де жадібний алгоритм зазнає невдачі

Звичайний пошук в ширину перебирає все дерево пошуку для того щоб знайти оптимальне рішення. Такий процес може зайняти дуже довгий час, у випадку якщо на кожному етапі є багато можливих варіантів вибору, і кількість етапів є значною. Інший підхід, жадібні алгоритми на кожному кроці обирають такий варіант, що максимізує цільову функцію. Це значно зменшує час пошуку, але отриманий результат може бути далекий від оптимального у багатьох реальних задачах.

Променевий пошук гілки, загальна вага якої є максимальною. Ширина променя дорівнює трьом. Вузли що знаходяться в промені позначені червоним, виключені з променя — сірим.

Променевий пошук є проміжним між цими двома алгоритмами. Променевий пошук характеризується числом, що називається шириною пошуку ${\displaystyle \beta }$. На кожному етапі алгоритм оцінює всі можливі кроки з точок, обраних на попередньому етапі, і обирає ${\displaystyle \beta }$ найкращих, які і стають опорними точками для наступного етапу. Важливо, що оцінюються сумарна значущість цілої гілки, а не одного значення — наприклад, якщо ми шукаємо найкращий переклад речення, і "вага" одного вузла — умовна ймовірність того що на даній позиції стоїть дане слово, то порівнювати ми маємо добуток ймовірностей вузла на ймовірності всіх попередніх вузлів у гілці[7].

Якщо ширина пошуку зменшується до 1, то променевий пошук переходить в жадібний, а якщо збільшується до нескінченності — то у пошук в ширину.

Ширина пучка може бути або фіксованою, або змінною. Один з підходів, що використовує змінну ширину пучка стартує з мінімальною шириною. Якщо не буде знайдено розв’язку, то промінь розширюється і процедура повторюється.

Використання променевого пошуку

Променевий пошук найчастіше використовується для підтримання поступливості у великих системах з недостатньою кількістю пам’яті для збереження всього дерева пошуку. Наприклад, він використовується в багатьох системах машинного перекладу. Щоб обрати найкращий переклад, кожна частина обробляється і з’являються різні варіанти перекладу слова. Найкращі переклади згідно з їх структурою речення зберігаються, а інші відкидаються. Перекладач потім оцінює переклади за заданими критеріями, обираючи переклад, що найкраще відповідає цілі.

Примітки

1. THE HARPY SPEECH RECOGNITION SYSTEM(англ.)
2. Job shop scheduling with beam search(англ.)
3. [http://www.eil.utoronto.ca/wp-content/uploads/speech/papers/hearsay77.pdf Speech understanding systems: summary of results of the five-year research effort at Carnegie-Mellon University](англ.)
4. AI Insights: Exploring Beam search - a heuristic search algorithm(англ.)
5. Beam Search Strategies for Neural Machine Translation(англ.)
6. Sequence Transduction with Recurrent Neural Networks(англ.)
7. Foundations of NLP Explained Visually: Beam Search, How It Works(англ.)

Джерела

• http://rriai.org.ru/lokalnyiy-luchevoy-poisk.html