Променевий пошук
В інформатиці, променевий пошук – це евристичний алгоритм пошуку, що досліджує граф, розширюючи найперспективніші вузли в обмеженому їх наборі. Променевий пошук є оптимізацією так званого «пошуку першого-найліпшого» (best-first), що суттєво знижує його вимоги до необхідної кількості пам’яті. best-first пошук в графі, що будує усі тимчасові рішення (стани) по деяких евристиках, що намагаються передбачити наскільки близьким є частковий розв’язок до повного розв’язку (цільового стану). В променевому пошуку лише деяка частина найкращих часткових розв’язків зберігаються як кандидати.
Вперше алгоритм був використаний для системи розпізнавання мовлення HARPY, що була створена Брюсом Ловеа в 1976 році[1][2]. Сам же термін був вперше використаний Реджем Редді у 1977[3][4].
Після цього його використовували у різноманітних задачах, що потребували складних евристик, наприклад для задач планування[2].
У 2006 році Алекс Грейвс запропонував використовувати алгоритм у sequence-to-sequence моделях для перекладу[5][6].
Звичайний пошук в ширину перебирає все дерево пошуку для того щоб знайти оптимальне рішення. Такий процес може зайняти дуже довгий час, у випадку якщо на кожному етапі є багато можливих варіантів вибору, і кількість етапів є значною. Інший підхід, жадібні алгоритми на кожному кроці обирають такий варіант, що максимізує цільову функцію. Це значно зменшує час пошуку, але отриманий результат може бути далекий від оптимального у багатьох реальних задачах.
Променевий пошук є проміжним між цими двома алгоритмами. Променевий пошук характеризується числом, що називається шириною пошуку . На кожному етапі алгоритм оцінює всі можливі кроки з точок, обраних на попередньому етапі, і обирає найкращих, які і стають опорними точками для наступного етапу. Важливо, що оцінюються сумарна значущість цілої гілки, а не одного значення — наприклад, якщо ми шукаємо найкращий переклад речення, і "вага" одного вузла — умовна ймовірність того що на даній позиції стоїть дане слово, то порівнювати ми маємо добуток ймовірностей вузла на ймовірності всіх попередніх вузлів у гілці[7].
Якщо ширина пошуку зменшується до 1, то променевий пошук переходить в жадібний, а якщо збільшується до нескінченності — то у пошук в ширину.
Ширина пучка може бути або фіксованою, або змінною. Один з підходів, що використовує змінну ширину пучка стартує з мінімальною шириною. Якщо не буде знайдено розв’язку, то промінь розширюється і процедура повторюється.
Променевий пошук найчастіше використовується для підтримання поступливості у великих системах з недостатньою кількістю пам’яті для збереження всього дерева пошуку. Наприклад, він використовується в багатьох системах машинного перекладу. Щоб обрати найкращий переклад, кожна частина обробляється і з’являються різні варіанти перекладу слова. Найкращі переклади згідно з їх структурою речення зберігаються, а інші відкидаються. Перекладач потім оцінює переклади за заданими критеріями, обираючи переклад, що найкраще відповідає цілі.
- ↑ THE HARPY SPEECH RECOGNITION SYSTEM(англ.)
- ↑ а б Job shop scheduling with beam search(англ.)
- ↑ [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](англ.)
- ↑ AI Insights: Exploring Beam search - a heuristic search algorithm(англ.)
- ↑ Beam Search Strategies for Neural Machine Translation(англ.)
- ↑ Sequence Transduction with Recurrent Neural Networks(англ.)
- ↑ Foundations of NLP Explained Visually: Beam Search, How It Works(англ.)
|
Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її. |