Beam Search

Beam Search przeszukuje możliwe wyjścia modelu, zachowując ograniczoną liczbę najlepiej ocenionych częściowych sekwencji. Ta liczba to beam width. W każdym kroku rozwija zachowane prefiksy, porównuje kandydatów i odrzuca nadmiar. W opisanym tutaj wariancie wybór jest deterministyczny.

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.