Beam search — ketma-ket output yaratishda har bosqichda eng yaxshi cheklangan sondagi qisman yechimlarni saqlaydigan heuristic qidiruv algoritmi. U barcha mumkin bo‘lgan ketma-ketliklarni ko‘rib chiqadigan exhaustive search’dan ancha arzon, faqat bitta eng yaxshi tokenni tanlaydigan greedy search’dan esa kengroq qidiradi.
Asosiy mexanizm
Model vocabulary tokenlari uchun log probability beradi. Dastlab bo‘sh hypothesis beam ichida turadi. Har qadamda beamdagi har bir hypothesis barcha mumkin tokenlar bilan kengaytiriladi, cumulative score hisoblanadi va eng yuqori B ta candidate qoldiriladi. B beam width deb ataladi. End-of-sequence tokeni kelgan hypothesis tugallanganlar ro‘yxatiga o‘tadi.
Probability ko‘paytmasi son jihatdan juda kichraygani uchun amalda log probability yig‘iladi. Cumulative log score uzun ketma-ketlikni tabiiy ravishda jazolaydi, chunki har yangi token manfiy qiymat qo‘shadi. Length normalization yoki length penalty qisqa outputga ortiqcha moyillikni kamaytiradi.
Greedy va exact qidiruv bilan farqi
Beam width 1 bo‘lsa algoritm greedy decodingga tenglashadi. Width oshishi ko‘proq alternative’ni saqlaydi, lekin vaqt va xotira xarajati ham taxminan oshadi. Beam search global optimumni kafolatlamaydi: erta bosqichda past score olgan, keyin yaxshi bo‘lishi mumkin bo‘lgan yo‘l beamdan chiqarib yuboriladi.
Juda katta beam har doim sifatni yaxshilamaydi. Model probabilitysi human quality bilan to‘liq mos bo‘lmasa, qidiruv modelning noto‘g‘ri preferensiyasini kuchaytiradi. Machine translation’da katta beam ba’zan haddan tashqari qisqa output, ASR’da esa language model bias’i sabab acoustic signalga mos bo‘lmagan keng tarqalgan iborani tanlashi mumkin.
ASR’dagi qo‘llanish
Automatic Speech Recognition’da hypothesis text prefix, acoustic score, language model score va kerak bo‘lsa lexicon state’ni saqlaydi. CTC decoding blank va takroriy tokenlarni collapse qilish qoidalarini hisobga oladi. Prefix beam search bir xil text prefixga olib keladigan alignment score’larini yig‘adi.
External language model shallow fusion bilan qo‘shilishi mumkin:
score = acoustic_score + α × lm_score + β × word_count
α language model vaznini, β insertion yoki length bias’ini boshqaradi. Ular validation data’da sozlanadi. Hotword bonus domain terminiga yordam beradi, ammo juda katta bonus noto‘g‘ri insertion keltiradi.
Optimallashtirish
Top-k selection barcha candidate’ni to‘liq sort qilmasdan eng yaxshilarini topadi. Batched beam search hypothesislarni accelerator’da parallel hisoblaydi. Shared prefix cache transformer attention state’ini qayta ishlatadi. Vocabulary pruning va lexicon constraint qidiruv maydonini qisqartiradi.
Early stopping eng yaxshi tugallangan hypothesis qolgan faol candidate’dan yomonlashmaydigan holatda qidiruvni tugatadi. Maximum length cheksiz generationni oldini oladi. Duplicate yoki bir xil normalized outputlar birlashtirilishi mumkin. Streaming ASR’da decoding state chunk’lar orasida saqlanadi va partial result stability uchun beamdagi agreement kuzatiladi.
Baholash
Beam width accuracy, latency va memory bo‘yicha birga baholanadi. Oracle WER beam ichida mavjud eng yaxshi transcriptni ko‘rsatib, model candidate yaratganmi yoki ranking xato qilganmi degan savolni ajratadi. N-best list downstream rerankerga berilishi mumkin. Reproducible tajriba score formulasi, pruning threshold, length normalization va random tie-breaking qoidalarini qayd etadi.
Constraintlar
Ba’zi vazifada output grammar yoki ruxsat etilgan vocabulary bilan cheklanadi. Finite-state constraint faqat valid transitionlarni kengaytiradi, masalan command parser noto‘g‘ri formatli ketma-ketlikni chiqarmaydi. Constraint juda tor bo‘lsa model audio’da aytilgan, ammo ro‘yxatda yo‘q nomni majburan yaqin variantga almashtiradi. Shuning uchun fallback unknown token yoki open-vocabulary yo‘li saqlanadi. Constraintli va erkin decoding natijalari alohida metrika bilan solishtiriladi.
Bog‘liq tushunchalar
Greedy search, Automatic Speech Recognition, CTC, Language model, Decoding, Dynamic programming, N-best list