Sugárkeresés

A számítástechnikában a Beam Search egy heurisztikus keresési algoritmus , amely egy korlátozott készletben lévő ígéretes csomópontok kiterjesztésével tár fel egy gráfot. A Beam search az első legjobb keresési optimalizálás , amely csökkenti a memóriaigényt. Az első legjobb egyezés keresése egy gráfkeresés, amely az összes konkrét megoldást (állapotot) valamilyen heurisztika szerint rendezi. De a sugárkeresésben a legjobb részmegoldásoknak csak előre meghatározott száma tárolódik jelöltként [1] . Így ez egy mohó algoritmus .

A nyalábkeresés kifejezést Raj Reddy , a Carnegie Mellon Egyetem munkatársa vezette be 1977 -ben [2] .

Részletek

A Beam keresés a szélességi keresést használja a keresési fa felépítéséhez . A fa minden szintjén minden állapotutódot generál az aktuális szinten, a heurisztikus költségek növekvő sorrendjében rendezve őket [3] . Azonban minden szinten csak előre meghatározott számú legjobb állapotot tárol (úgynevezett sugárszélesség). Továbbá csak ezek az állapotok bontakoznak ki. Minél nagyobb a nyalábszélesség, annál kevesebb állapot kerül eltávolításra. Végtelen sugárszélesség esetén egyetlen állapot sem törlődik, és a sugárkeresés megegyezik a szélesség-első kereséssel. A sugár szélessége korlátozza a keresés végrehajtásához szükséges memória mennyiségét. Mivel a célállapot potenciálisan csökkenthető, a sugárkeresés feláldozza a teljességet (a garancia arra, hogy az algoritmus megoldással zárul, ha létezik). A sugárkeresés nem optimális (vagyis nincs garancia arra, hogy a legjobb megoldást megtalálják) [4] .

Alkalmazás

A sugárkeresést leggyakrabban a kezelhetőség biztosítására használják nagy rendszerekben, amelyekben nincs elegendő memória a teljes keresési fa tárolására [5] . Például számos gépi fordítórendszerben használták [6] . (A technika jelenlegi állása szerint főként a neurális gépi fordításon alapuló módszereket alkalmazzák .) A legjobb fordítás kiválasztásához minden egyes részt feldolgoznak, és sokféle szófordítási mód jelenik meg. A mondatszerkezetüknek megfelelő legjobb fordításokat megtartjuk, a többit eldobjuk. A fordító ezután egy adott kritérium alapján értékeli a fordításokat, és kiválasztja a céloknak leginkább megfelelő fordítást. A sugárkeresést először a Harpy's Speech Recognition System, CMU 1976-ban [7] használták .

Opciók

A sugárkeresés teljes egészében úgy történt , hogy kombinálták a mélységi kereséssel , ami ray verem keresést [8] , sugármélység -első keresést [5] és korlátozott eltérésű keresést [9] eredményez, ami korlátozott visszakövetéssel történő sugárkereséshez vezet. következetlenségek [5] (BULB [10] ). Az eredményül kapott keresőalgoritmusok olyan bármikor használható algoritmusok , amelyek gyorsan megtalálják a jó, de valószínűleg nem optimális megoldásokat, például a sugárkeresést, majd visszamennek, és addig keresnek jobb megoldásokat, amíg azok egy optimális megoldáshoz nem konvergálnak.

A lokális keresés kontextusában nyalábos helyi keresésnek nevezünk egy adott algoritmust, amely a véletlenszerűen generált állapotok kiválasztásával indul , majd mindegyiknél mindig a keresési fa szintjén veszi figyelembe az aktuális állapotok lehetséges utódai közül az új állapotokat, amíg el nem éri a célt [ 11] [12] .

Mivel a lokális nyalábkeresés gyakran a lokális maximumoknál ér véget, a szokásos megoldás az, hogy a következő állapotokat véletlenszerűen választjuk ki, az állapotok heurisztikus becslésétől függő valószínűséggel. Ezt a fajta keresést sztochasztikus nyalábkeresésnek nevezik [13] .

További lehetőségek a rugalmas nyalábkeresés és a rekonstrukciós sugárkeresés [12] .

Jegyzetek

1. ↑ FOLDOC - Számítógépes szótár . foldoc.org . Letöltve: 2016. április 11. Az eredetiből archiválva : 2020. január 25. (határozatlan)
2. ↑ Reddy, Dabbala Raj . Beszédértési rendszerek: Öt év kutatásának összefoglalása. Számítástechnikai Tanszék. , 1977
3. ↑ KERESÉS A BRIT MÚZEUMBAN . bradley.bradley.edu _ Letöltve: 2016. április 11. Az eredetiből archiválva : 2018. május 6.. (határozatlan)
4. ↑ Peter Norvig . AI programozási paradigmák: Általános LISP használati példák  : [ eng. ] . – Morgan Kaufmann, 1992. 01. 01. — ISBN 9781558601918 . Archiválva : 2021. április 20. a Wayback Machine -nél
5. ↑ 1 2 3 David Fursey, Sven Koenig. Korlátozott sugárzású keresési eltérés . 2005. Levéltári másolat . Letöltve: 2007. december 22. Az eredetiből archiválva : 2008. május 16.. (határozatlan)
6. ↑ Christoph Tillmann, Hermann Ney. A szó átrendezése és a dinamikus programozási nyaláb keresési algoritmusa a statisztikai gépi fordításhoz . Archivált másolat . Letöltve: 2007. december 22. Az eredetiből archiválva : 2006. június 18.. (határozatlan)
7. ↑ Bruce Lowerr. Harpy's Speech Recognition System , PhD értekezés, Carnegie Mellon Egyetem, 1976
8. ↑ Zhou Rong, Eric Hansen. Beam Stack Search: A visszalépés integrálása a Beam Search szolgáltatással . 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php Archiválva : 2021. április 20. a Wayback Machine -nél
9. ↑ CiteSeer x :  10.1.1.34.2426
10. ↑ A BULB az angol kifejezés rövidítése Beam search Az L imitált eltérés használatával B acktracking _
11. ↑ Szvetlana Lazebnik. Helyi keresési algoritmusok . Észak-Karolinai Egyetem, Chapel Hill , Számítástechnikai Tanszék. Az eredetiből archiválva: 2011. július 5. (határozatlan)
12. ↑ 1 2 Pushpak Bhattacharya. Sugárkeresés 39-40. Indian Institute of Technology, Bombay, Számítástechnikai és Mérnöki Kar (CIS). Az eredetiből archiválva : 2018. november 21. (határozatlan)
13. ↑ James Parker. Helyi keresés . University of Minnesota (2017. szeptember 28.). Letöltve: 2018. november 21. Az eredetiből archiválva : 2017. október 13. (határozatlan)