Wyszukiwanie promieniowe: Znajdowanie dobrych sekwencji bez brutalnego obliczania

Trudności z dekodowaniem żądnym

Najprostszym sposobem generowania sekwencji z modelu językowego jest dekodowanie żądne: w każdym kroku wybieramy pojedynczy token o najwyższej prawdopodobieństwie i przechodzimy dalej. Jest szybkie i łatwe do wdrożenia, ale jednocześnie krótkowzroczne. Model może przypisać najwyższą prawdopodobieństwo idealnie rozsądnemu słowu, które jednak prowadzi do martwego impasu językowego, zmuszając do niezręcznych lub niskiej jakości wyborów później, po prostu dlatego, że ścieżka żądna już się w tym zatwierdziła. Ponieważ dekodowanie żądne nigdy nie rozważa decyzji podjętej w jednym kroku, lokalnie optymalny token może cicho zrujnować całą sekwencję, nawet jeśli nieco mniej prawdopodobne pierwsze słowo otworzyło drzwi do znacznie lepszego zdania. Głównym problemem jest to, że najlepsza sekwencja jest właściwością całego ścieżki, a nie pojedynczego kroku, a dekodowanie żądne rozważa jedynie jeden krok naprzód.

Dlaczego brutalne przeszukiwanie jest niemożliwe

Naturalnym rozwiązaniem jest rozważenie każdej możliwej sekwencji i wybranie tej o najwyższym całkowitym prawdopodobieństwie. Jednak przestrzeń wszystkich możliwych sekwencji wybuchana kombinatorycznie: przy słowniku o wielkości V i długości celu T, istnieje w przybliżeniu V^T sekwencji do oceny. Nawet umiarkowany słownik liczący 30 000 tokenów i zdanie o długości 20 tokenów generuje liczbę kandydatów znacznie większą niż liczba atomów we wszechświecie widzialnym. Przeszukiwanie wyczerpujące jest więc obliczeniowo niemożliwe dla jakiegokolwiek realistycznego zadania językowego, co oznacza, że praktykowa dekodacja musi być zawsze przybliżeniem — prawdziwe pytanie brzmi, w jaki sposób przybliżyć to inteligentnie, a nie ślepo.

Utrzymywanie najlepszych kandydatów z górki

Wyszukiwanie promieniowe stanowi kompromis pomiędzy krótkowzrocznością dekodowania głupiego a niemożliwością brutalnego obliczania. Zamiast przechowywać tylko jedną najlepszą niekompletną sekwencję, utrzymuje stałą liczbę najbardziej obiecujących niekompletnych sekwencji, zwanych wiązkami, na każdym kroku. W każdym kroku algorytm rozszerza każdą bieżącą wiązkę o każdy możliwy następny token, ocenia wszystkie te rozszerzone kandydatury według ich sumy log-prawdopodobieństwa i następnie redukuje listę tylko do k najlepszych wyników, zanim przejdzie do kolejnego kroku. Oznacza to, że sekwencja, która na początku wyglądała nieznacznie suboptymalnie, nadal może przetrwać w wiązce i później okazać się częścią najlepszej ogólnej ścieżki, coś, czego nigdy nie byłaby w stanie odzyskać czyste dekodowanie głupie. Wyszukiwanie kończy się, gdy wiązki osiągną maksymalną długość lub wszystkie wyprodukują token końca sekwencji, a najwyżej oceniona ukończona wiązka jest zwracana jako ostateczna odpowiedź.

Wybór szerokości wiązki

Liczba wiązek utrzymanych na każdym kroku, szerokość wiązki k, jest centralnym pokrętłem algorytmu. Ustawienie k=1 powoduje zawężenie przeszukiwania wiązkami z powrotem do prostego dekodowania przy wyborze, a zwiększenie k pozwala wyszukiwaniu na eksplorację większej liczby alternatywnych ścieżek, co zazwyczaj poprawia jakość wyjściową poprzez zmniejszenie prawdopodobieństwa zbyt wczesnego odrzucenia dobrej sekwencji. Jednakże ta poprawa nie jest bezpłatna: zarówno pamięć, jak i wymagania obliczeniowe rosną w przybliżeniu liniowo wraz z k, ponieważ każda wiązka musi być rozszerzona i ponownie oceniona na każdym kroku. Po przekroczeniu pewnego punktu, większe szerokości wiązki również dają spadek lub nawet negatywne zwroty na temat jakości, ponieważ zbyt szerze wyszukiwanie może faworyzować ogólne, wysokoprawdopodobne, ale nudne sekwencje kosztem bardziej charakterystycznych, zjawisko to zostało udokumentowane w zadaniach takich jak tłumaczenie maszynowe. Dlatego wybór k jest praktycznym kompromisem między jakością wyjściową, opóźnieniem i budżetem sprzętowym, a nie tylko maksymalizacją szerokości poszukiwań.

Gdzie żyje przeszukiwanie wiązkowe

Przeszukiwanie wiązkowe stało się podstawowym narzędziem w tłumaczeniach maszynowych z tekstu na mowę, systemach rozpoznawania mowy na tekst i generowaniu opisów obrazów, gdzie celem jest pojedynczy, dobrze ukształtowany, o wysokiej prawdopodobieństwie wynik i szerokości wiązki wynoszącej zazwyczaj 4 do 10, co wystarcza. Nadal jest to powszechne w tych zadaniach o charakterze deterministycznym, ponieważ niezawodnie poprawia wyniki w stosunku do dekodowania głupiego bez kosztów przeszukiwania całego wsadu. W przypadku otwartej generacji tekstu – chatboty, historie, twórcze pisanie – przeszukiwanie wiązkowe zostało w dużej mierze zastąpione metodami opartymi na próbkowaniu, takimi jak próbkowanie top-k, próbkowanie jądra (top-p) i próbkowanie sterowane temperaturą, które celowo wprowadzają losowość, ponieważ czysty wyszukiwanie maksymalizujące prawdopodobieństwo prowadzi do powtarzalnego, ogólnego tekstu, gdy nie ma pojedynczej „prawidłowej” odpowiedzi, którą należy zbieżnie. Wybór między przeszukiwaniem wiązki a próbkowaniem odzwierciedla wreszcie naturę zadania: przeszukiwanie wiązki sprawdza się, gdy można znaleźć najlepszą odpowiedź, podczas gdy próbkowanie sprawdza się, gdy liczy się różnorodność i kreatywność bardziej niż ranking prawdopodobieństwa.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Beam Search: Finding Good Sequences Without Brute Force i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.