Czym jest Przeszukiwanie wiązkowe (Beam search)?
Przeszukiwanie wiązkowe, określane w literaturze jako Beam search, należy do grupy heurystycznych algorytmów przeszukiwania grafu. Metoda polega na równoległym rozwijaniu kilku najbardziej obiecujących ścieżek zamiast jednej, dzięki czemu algorytm szybciej zbliża się do rozwiązania bez konieczności eksplorowania całej przestrzeni stanów. Liczba aktywnych ścieżek określana jest parametrem beam width, co odróżnia tę technikę od klasycznego przeszukiwania zachłannego lub pełnego przeszukiwania w głąb.
Krótki rys historyczny
Koncepcję wiązkowego ograniczania przestrzeni poszukiwań przypisuje się Edwardowi A. Feigenbaumowi i Julianowi Feldmanowi, którzy w latach sześćdziesiątych badali algorytmy heurystyczne dla gier logicznych. Formalny opis metody pojawił się w 1977 r. w pracy Johna Lowerre’a na Carnegie Mellon University dotyczącej rozpoznawania mowy, a następnie został rozszerzony przez Fredericka Jelineka w zespole IBM. Od tamtej pory algorytm znalazł zastosowanie w tłumaczeniu maszynowym, analizie sekwencji biologicznych i generowaniu tekstu przez sieci neuronowe.
Jak dokładnie działa Przeszukiwanie wiązkowe (Beam search)
Działanie opiera się na iteracyjnym budowaniu drzewiastej struktury stanów. Po wygenerowaniu startowych kandydatów każdy otrzymuje ocenę heurystyczną. W każdej kolejnej rundzie algorytm rozwija jedynie k kandydatów o najwyższej łącznej ocenie, gdzie k to szerokość wiązki. Pozostałe ścieżki zostają odrzucone, co redukuje zapotrzebowanie na pamięć i czas. Proces trwa do osiągnięcia stanu końcowego lub wyczerpania głębokości. W praktyce, zwłaszcza w modelach językowych, często stosuje się dodatkowe strategie takie jak normalizacja długości czy losowe odrzucanie zbyt podobnych sekwencji, aby przeciwdziałać faworyzowaniu krótkich wyników.
Zastosowania w praktyce
Metoda jest powszechnie używana w dekoderach sieci neuronowych. W tłumaczeniu maszynowym NMT algorytm wybiera najbardziej prawdopodobne zdania wyjściowe, zamiast ograniczać się do pojedynczego słowa prognozowanego w danym kroku. W rozpoznawaniu mowy beam search łączy prawdopodobieństwa akustyczne i językowe, co znacznie ułatwia dekodowanie długich fraz. W bioinformatyce wspiera identyfikację homologii białek, a w planowaniu ruchu robotów ogranicza liczbę badanych trajektorii.
Zalety i ograniczenia
Najważniejszym atutem jest kompromis między dokładnością a złożonością obliczeniową. Dzięki parametrowi beam width można płynnie przechodzić od zachłannego algorytmu do pełnego przeszukiwania sterowanego heurystyką. W odróżnieniu od metod takich jak BFS beam search zużywa znacznie mniej pamięci, a w porównaniu z DFS rzadziej gubi optymalne rozwiązanie. Niemniej zbyt wąska wiązka może prowadzić do przedwczesnego odrzucenia najlepszej ścieżki, natomiast zbyt szeroka redukuje zysk wydajności. Algorytm pozostaje deterministyczny przy stałych warunkach, co upraszcza replikację wyników, ale utrudnia eksplorację przestrzeni w zastosowaniach kreatywnych.
Na co uważać?
W praktyce kluczowe jest dobranie szerokości wiązki do zadania, rozmiaru korpusu treningowego oraz oczekiwanego czasu odpowiedzi. W modelach generatywnych z nieskutecznie ustawioną normalizacją wynik może być nadmiernie skracany. W aplikacjach czasu rzeczywistego, takich jak systemy dialogowe, zbyt duża wiązka niepotrzebnie opóźnia odpowiedź użytkownikowi. Warto również monitorować dywersyfikację ścieżek, aby uniknąć zbieżności kandydatów do niemal identycznych sekwencji.
Subtelne porównanie z klasycznymi rozwiązaniami
W porównaniu z algorytmem zachłannym, który w każdej turze wybiera jednego najlepszego kandydata, beam search utrzymuje kilka potencjalnych ścieżek, co zwiększa szanse na wyjście z rejonu lokalnego optimum. W zestawieniu z algorytmem A* brak gwarancji optymalności nadrabia znaczną redukcją pamięci, zwłaszcza gdy funkcja heurystyczna jest trudna do zdefiniowania lub kosztowna obliczeniowo.
Dodatkowe źródła
Rozszerzone omówienie można znaleźć w haśle Beam search – Wikipedia. Szczegóły zastosowania do tłumaczenia maszynowego opisuje publikacja Sequence to Sequence Learning with Neural Networks. W dziedzinie rozpoznawania mowy historyczne tło przedstawia praca A* Search Algorithm for Large Vocabulary Continuous Speech Recognition.
