Іздеу алгоритмі: Beam Search – жадты үнемдейтін, ең жақсы нұсқаларды таңдайтын, бағалау функциясына негізделген алгоритм. Компьютер ғылымында қолданылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Эвристикалық іздеу алгоритмі
Heuristic search algorithm
Компьютерлік ғылымда, сәулелік іздеу – шектеулі жиынтықтағы ең үміткер түйінді кеңейту арқылы графты зерттейтін эвристикалық іздеу алгоритмі. Сәулелік іздеу – жады талаптарын азайтатын, ең жақсы бірінші іздеудің модификациясы. Ең жақсы бірінші іздеу – белгілі бір эвристикаға сәйкес барлық ішінара шешімдерді (күйлерді) реттейтін граф іздеуі. Бірақ сәулелік іздеуде тек алдын ала белгіленген ең жақсы ішінара шешімдердің саны ғана кандидаттар ретінде сақталады. Осылайша, бұл ашкөз алгоритм.
In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an modification of best first search that reduces its memory requirements. Best first search is a graph search which orders all partial solutions (states) according to some heuristic. But in beam search, only a predetermined number of best partial solutions are kept as candidates. It is thus a greedy algorithm.
Егжей-тегжейлер
Сәулелік іздеу іздеу ағашын құру үшін ендік бірінші іздеуді пайдаланады. Ағаштың әр деңгейінде ол ағымдағы деңгейдегі күйлердің барлық ұрпақтарын жасайды, оларды эвристикалық бағасының өсу ретімен сұрыптайды. Дегенмен, ол әр деңгейдегі ең жақсы күйлердің белгілі бір санын ғана сақтайды (сәуле ені деп аталады). Келесі кезекте тек осы күйлер ғана кеңейтіледі. Сәуле ені неғұрлым үлкен болса, күйлерді қысқару соғұрлым аз болады. Шегі жоқ сәуле ені болса, ешқандай күйлер қысқартылмайды және сәулелік іздеу ең жақсы бірінші іздеумен толықтай сәйкес келеді. Керісінше, сәуле ені 1-ге тең болса, ол төбеге қарай жылғалау алгоритміне ұқсас. (Қазіргі заманғы технология негізінен нейрондық машиналық аудармаға негізделген әдістерді, әсіресе үлкен тілдік модельдерді қолданады). Ең жақсы аударманы таңдау үшін әр бөлік өңделеді, сөздерді аударудың көптеген әртүрлі тәсілдері пайда болады. Сөйлем құрылымы бойынша ең жақсы аудармалар сақталады, ал қалғандары жойлады. Содан кейін аудармашы белгілі бір критерий бойынша аудармаларды бағалайды, мақсаттарға ең сәйкес келетін аударманы таңдайды.
Beam search uses breadth first search to build its search tree. At each level of the tree, it generates all successors of the states at the current level, sorting them in increasing order of heuristic cost. However, it only stores a predetermined number, , of best states at each level (called the beam width). Only those states are expanded next. The greater the beam width, the fewer states are pruned. With an infinite beam width, no states are pruned and beam search is identical to best first search. Conversely, a beam width of 1 corresponds to a hill climbing algorithm. (The state of the art now primarily uses neural machine translation based methods, especially large language models) To select the best translation, each part is processed, and many different ways of translating the words appear. The top best translations according to their sentence structures are kept, and the rest are discarded. The translator then evaluates the translations according to a given criterion, choosing the translation which best keeps the goals.
Тарих
Harpy сөйлеуді тану жүйесі (1976 жылғы диссертацияда ұсынылған) – бұл кейіннен сәулелік іздеу деп аталатын әдістің алғашқы қолданылуы болды. Бұл процедура бастапқыда «іздеудің локустық моделі» деп аталғанмен, «сәулелік іздеу» термині 1977 жылға қарай қолданысқа енген еді.
The Harpy Speech Recognition System (introduced in a 1976 dissertation) was the first use of what would become known as beam search. While the procedure was originally referred to as the "locus model of search", the term "beam search" was already in use by 1977.