Beam Search (Işın Araması)

#Algoritmalar #DoğalDilİşleme #DiziÜretimi #MetinÜretimi #SıraArama

Beam Search, dizi üretiminde en iyi k adayı eş zamanlı izleyerek en yüksek olasılıklı çıktıyı bulan bir arama algoritmasıdır.

Beam Search (Işın Araması), doğal dil işleme ve konuşma tanıma alanlarında kullanılan sezgisel bir arama algoritmasıdır. Dizi üretimi görevlerinde, olası çıktı dizileri arasından en yüksek olasılıklı olanı bulmak amacıyla kullanılır. Açgözlü aramanın (greedy search) aksine, her adımda yalnızca tek en iyi seçeneği takip etmek yerine, belirlenen sayıda (ışın genişliği — beam width) en iyi adayı eş zamanlı olarak izler. Algoritma şöyle çalışır: Başlangıçta boş bir dizi ile başlanır ve her adımda mevcut adayların tüm olası genişlemeleri hesaplanır. Bu genişlemeler, toplam log-olasılık skorlarına göre sıralanır ve yalnızca en yüksek skorlu k aday (ışın genişliği) bir sonraki adıma aktarılır. Süreç, tüm diziler bir bitiş simgesi üretene ya da maksimum uzunluğa ulaşana dek devam eder. Işın genişliği (k) belirleyici bir hiperparametredir: k=1 durumu açgözlü aramaya eşdeğerdir ve en hızlı ama en az kapsamlı çözümdür. k değeri arttıkça çıktı kalitesi genel olarak yükselir; ancak hesaplama maliyeti de orantılı biçimde artar. Pratik uygulamalarda k=4 ile k=10 arasındaki değerler yaygındır. Beam Search, özellikle makine çevirisi, metin özetleme, konuşma sentezi ve konuşma tanıma sistemlerinde standart çözüm olarak kullanılmaktadır. Google Sinirsel Makine Çeviri sistemi ve pek çok modern dil modeli bu algoritmayı benimsemiştir. Bununla birlikte, açık uçlu metin üretiminde (yaratıcı yazım, diyalog sistemleri) tekrarlayıcı ve generik çıktılar üretme eğilimi nedeniyle nucleus sampling ve sıcaklık örneklemesi gibi stokastik yöntemler ön plana çıkmıştır. Tarihsel olarak 1977 yılında konuşma tanıma araştırmalarında kullanılan Beam Search, derin öğrenme çağında NLP'nin temel bileşenlerinden biri haline gelmiştir. Algoritmanın hesaplama karmaşıklığı O(k × V × L) olup V sözcük dağarcığı boyutunu, L ise dizi uzunluğunu ifade eder; bu nedenle büyük dil modellerinde inference maliyetini doğrudan etkiler. 2024-2026 döneminde büyük dil modellerinin yaygınlaşmasıyla Beam Search yeni varyantlar kazanmıştır. Constrained Beam Search, JSON şema doğrulama ve yapılandırılmış çıktı görevlerinde belirli token dizilerinin çıktıda yer almasını zorunlu kılar. Speculative decoding mimarisiyle birleştirildiğinde ise küçük bir taslak model beam adayları üretirken büyük model paralel doğrulamayı yürütür; bu yaklaşım GPU inference gecikmesini önemli ölçüde azaltır. Hugging Face Transformers kütüphanesi her iki tekniği generate() API'si üzerinden destekler.

Beam Search Nedir?

Beam search (ışın araması), olası çıktı dizilerinin tamamını değerlendirmek yerine her adımda yalnızca k adet en yüksek olasılıklı adayı canlı tutarak ilerleyen sezgisel bir arama algoritmasıdır. 1977 yılında konuşma tanıma araştırmalarında ortaya çıkan bu yöntem, makine çevirisi ve metin özetleme gibi sıra-üretim (sequence generation) görevlerinde standart çözüm haline geldi. Açgözlü aramadan (greedy search) farkı birden fazla alternatifi paralel olarak izlemesidir; tam aramadan (exhaustive search) farkı ise tüm olası genişlemeleri değil yalnızca k tane en iyi adayı tutmasıdır. Bu denge, pratik hesaplama maliyetiyle makul kalite arasında değiş tokuş yaparak büyük söz dağarcığı boyutlarında kullanılabilir bir çıktı kalitesi elde etmeyi mümkün kılar.

Algoritmanın Çalışma Mantığı

Algoritma başlangıç tokeninden itibaren çalışır. Her adımda mevcut k adet aday dizi, söz dağarcığındaki tüm olası tokenlerle genişletilerek k × |V| aday üretilir; bunlar log-olasılıklarına göre sıralanır ve yalnızca en yüksek k tanesi bir sonraki adıma taşınır. Bir dizi bitiş tokenına (EOS) ulaştığında tamamlananlar listesine eklenir ve arama devam eder. Tüm ışınlar tamamlandığında ya da maksimum uzunluğa ulaşıldığında en yüksek toplam log-olasılığa sahip dizi seçilir. Uzunluk normalleştirmesi (length penalty) kısa dizilerin haksız avantajını gidermek için toplam skora uygulanır; tipik formül log-prob / L^α şeklindedir, α 0.6-0.7 arasında seçilir.

Işın Genişliği (Beam Width) ve Etkisi

  • check_circle k = 1 (Açgözlü Arama): Her adımda yalnızca en olası token seçilir. En hızlı ama en az çeşitli çıktı; yerel optimumlara takılma riski yüksek.
  • check_circle k = 4-10 (Pratik Aralık): Makine çevirisi ve özetlemede standart değer. Hesaplama maliyeti k ile doğru orantılı; kalite artışı belirgin ama diminishing returns başlar.
  • check_circle Büyük k (Tam Aramaya Yakın): k arttıkça tam aramaya (tüm yolları değerlendirme) yaklaşılır. Bellek ve hesaplama maliyeti k × V × L ile orantılı artar; pratikte k > 20 nadiren kullanılır.
  • check_circle Constrained Beam Search: Belirli token kısıtlamalarını (JSON şema, anahtar kelime zorunluluğu) güvence altına alır. Yapılandırılmış çıktı görevlerinde ve 2025-2026 itibarıyla LLM API'lerinde giderek yaygın.

Kullanım Alanları

Beam search, dizi-üretim görevlerinin geniş bir yelpazesinde uygulanır. Makine çevirisinde Google Translate ve DeepL gibi sistemler beam search ile kaynak dilde en olası çeviriyi belirler; özellikle kısa-orta uzunluktaki cümlelerde yüksek BLEU skorları elde edilir. Metin özetlemede BART ve T5 gibi modeller, özetin hem anlamlı hem gramer açısından doğru olmasını güvence altına almak için beam search kullanır. Konuşma tanımada akustik model çıktıları dil modeliyle birleştirilerek en olası transkripsiyon seçilir. Protein dizisi tasarımında ve molekül üretiminde de aynı ilke uygulanmakta; biyomedikal alanda beam search tabanlı üretim pipeline'ları aktif araştırma konusu olmaya devam etmektedir.

Sınırlamalar: Tekrar ve Generiklik

Beam search'in en bilinen zayıflığı yüksek olasılıklı ama sıkıcı ya da tekrarlayan metinler üretme eğilimidir. Model öğrendiği kalıpların ağırlığı nedeniyle kısa ve güvenli cümleleri tercih eder; bu durum çeviri kalitesini düşürür ya da yaratıcı metin üretimini kısıtlar. Tekrarları önlemek için n-gram cezası (n-gram repetition penalty) uygulanır: belirli bir n-gram bir kez görülmüşse, tekrar üretildiğinde olasılığı sıfırlanır ya da ağır şekilde penalize edilir. Açık uçlu yaratıcı üretim görevlerinde nucleus sampling (top-p), top-k örnekleme ve temperature ayarı daha çeşitli ve özgün çıktılar ürettiği için beam search'e tercih edilir.

Alternatif Örnekleme Yöntemleri

  • check_circle Greedy Search (Açgözlü): k=1 beam search; her adımda en yüksek olasılıklı token. Hızlı ama tekrarlayıcı ve yerel optimumlara takılabilir.
  • check_circle Top-k Sampling: Her adımda k en olası token arasından rastgele örnekleme. Çeşitlilik artırır; sabit k değeri düşük entropi durumlarında sorun yaratabilir.
  • check_circle Nucleus Sampling (Top-p): Kümülatif olasılık p eşiğine kadar olan tokenlerin kümesinden örnekleme. Dinamik aday havuzu; GPT ailesinde varsayılan örnekleme stratejisi.
  • check_circle Constrained / Guided Decoding: JSON şema veya regex kısıtını karşılayan tokenler filtrelenip beam search ile üretilir. Outlines ve SGLang kütüphaneleri bu yaklaşımı LLM API seviyesine taşıdı.

Sık Sorulan Sorular

  • check_circle Beam search mi, örnekleme mi seçmeliyim? Deterministik ve yapısal çıktı gereken görevlerde (çeviri, özetleme, JSON üretimi) beam search tercih edilir. Yaratıcı yazarlık, sohbet ve çeşitlilik gerektiren görevlerde nucleus sampling (top-p) daha iyi sonuç verir.
  • check_circle Işın genişliğini nasıl ayarlamalıyım? Makine çevirisi için k=4-6, özetleme için k=5-8 pratik başlangıç noktaları. Küçük k'dan başlayın; geliştikçe BLEU/ROUGE gibi metriklerle değerlendirin. Büyük k değerleri bellek ve gecikme artırır, kazanım azalır.
  • check_circle Beam search n-gram cezası neden önemli? Ceza olmadan model aynı ifadeyi döngüsel üretebilir. no_repeat_ngram_size=3 parametresi (Hugging Face) bir trigram ikinci kez göründüğünde olasılığını sıfırlar; bu özetleme görevlerinde standarttır.
  • check_circle Constrained beam search ile JSON üretimi nasıl çalışır? Outlines, SGLang ve LM Format Enforcer gibi kütüphaneler her adımda geçerli JSON şemasını karşılayan tokenleri maskeleyerek yalnızca uyumlu tokenler arasında beam search çalıştırır. Bu sayede her çıktı şemaya garantili uyar.
  • check_circle Beam search PyTorch'ta nasıl uygulanır? Hugging Face model.generate(num_beams=5, ...) ile hazır implementasyon kullanılabilir. Ham PyTorch'ta log-softmax çıktıları kümülatif toplanarak k adet en yüksek skor izlenir; EOS tespitiyle dizi tamamlananlar listesine alınır.
  • check_circle Beam search LLM'lerde hala geçerli mi? Evet. GPT-4o, Claude ve Gemini gibi büyük modeller çıkarım sırasında örnekleme ile hybrid stratejiler kullanır; ancak makine çevirisi ve özetleme gibi alanlarda beam search hala standart. Constrained decoding ise 2025 itibarıyla hızla yaygınlaşıyor.