Beam Search

Wybierając pierwszy fragment odpowiedzi, możesz zbyt wcześnie odrzucić drogę, która później okazałaby się lepsza. Sprawdzenie wszystkich możliwych ciągów jest jednak zbyt kosztowne. Potrzebujesz ograniczonej puli alternatyw.

Beam Search zachowuje kilka najlepiej ocenionych częściowych odpowiedzi. W każdym kroku rozwija je, porównuje nowe ciągi i ponownie zostawia tylko określoną liczbę. Wielkość tej puli nazywa się beam width.

Przy szerokości dwa system może zachować początki A i B zamiast od razu wybrać A. W następnym kroku porównuje ich rozwinięcia. Podstawowa ocena łączy prawdopodobieństwa kolejnych tokenów — kawałków tekstu — choć implementacje mogą korygować wpływ długości.

Większa pula kosztuje więcej pamięci i obliczeń, a nadal może odrzucić najlepszą ścieżkę. Wysokie prawdopodobieństwo całego ciągu nie jest też gwarancją prawdziwości, różnorodności czy użyteczności wypowiedzi.

Mechanizm i szczegóły

W Autoregressive Language Modeling podstawowym wynikiem sekwencji jest suma logarytmów prawdopodobieństw jej tokenów:

$$S(x_{1:t})=\sum_{i=1}^{t}\ln p(x_i\mid x_{<i})$$

To logarytm iloczynu prawdopodobieństw. Większy wynik jest lepszy; suma unika mnożenia bardzo małych liczb. Dokumentacja Hugging Face, „Beam search” opisuje utrzymywanie wielu sekwencji. Szerokość 1 sprowadza ten podstawowy wariant do Greedy Decoding.

Który prefiks wyrzucisz za wcześnie?

Własny przykład zaczyna się od szans A = 0,45, B = 0,35 i C = 0,20. Beam o szerokości 2 wyrzuca C. Najlepsze rozwinięcie A ma później szansę 0,4, więc wynik AA wynosi 0,18. Tymczasem pominięte CA uzyskałoby $0{,}20\cdot0{,}99=0{,}198$. Szerokość 3 zachowa C i znajdzie lepszy wynik. To pełne, małe drzewo dwóch tokenów, bez wcześniejszego końca i bez normalizacji długości.

Beam Search pozostaje przybliżeniem: odrzuconego prefiksu nie rozwija ponownie. Szerokość nie oznacza liczby tokenów losowanych z jednego rozkładu, jak w Top-k Sampling.

Przy sekwencjach różnej długości znaczenie mają token końca, warunek zatrzymania i funkcja oceny. Na przykład length_penalty w GenerationConfig dzieli wynik logarytmiczny przez długość podniesioną do zadanej potęgi. Nie należy mieszać tego kryterium z czystym prawdopodobieństwem. Szerszy beam również nie gwarantuje lepszej treści; problem omawiają Holtzman et al., §2.2–3.

Wykorzystuję treści generowane przez AI jako część mojego codziennego procesu nauki.