Beam search

Beam search is een manier waarop een AI-model zijn woorden kiest door meerdere versies tegelijk open te houden. In plaats van elke keer het waarschijnlijkste volgende woord vast te leggen, volgt het een handvol veelbelovende halve zinnen en kiest het aan het eind de beste complete zin. Vertaaltools en spraak-naar-teksttools gebruiken het, omdat je daar het ene waarschijnlijkste antwoord wilt.

Hoe werkt het?

Een taalmodel schrijft token voor token (zie autoregressieve generatie). Greedy decoding neemt steeds het waarschijnlijkste volgende token, en kan zo een betere zin missen die met een minder waarschijnlijk woord begint. Alle mogelijke zinnen nalopen zou de beste vinden, maar dat duurt veel te lang. Beam search, in 1976 voor het eerst voorgesteld door Lowerre, zit daartussenin, zoals Jurafsky en Martin in hun leerboek beschrijven:

1. Houd de k beste halve zinnen bij, de hypotheses. Het getal k heet de beam width, naar de lichtbundel van een zaklamp die je breder of smaller kunt zetten.
2. Breid elke hypothese uit met elk mogelijk volgend token, en geef elk resultaat een score door de log-kansen van zijn tokens op te tellen.
3. Houd alleen de k beste resultaten over en herhaal.
4. Eindigt een hypothese met een eindtoken, zet hem dan apart en maak de bundel één kleiner, tot er k complete hypotheses zijn.
5. Geef de hoogst scorende terug, of alle k met hun scores.

Zonder toeval geeft dezelfde invoer altijd dezelfde uitvoer. Beam search blijft een heuristiek: het vindt niet gegarandeerd de waarschijnlijkste uitvoer.

Welke instellingen tellen?

De beam width. Volgens Jurafsky en Martin gebruikt machinevertaling meestal 5 tot 10. De oorspronkelijke transformer gebruikte 4 voor vertalen. Het vertaalsysteem GNMT van Google hield 8 tot 12 hypotheses bij en zag dat 4 of 2 maar weinig kwaliteit kostte. Elke hypothese vraagt een eigen ronde door het model, dus een bredere bundel kost meer rekenwerk.

Lengtenormalisatie. Log-kansen zijn negatief en tellen op, dus langere zinnen scoren lager en gewone beam search geeft de voorkeur aan korte uitvoer. De oplossing is de score te delen door de lengte, of door een macht daarvan: GNMT vond waarden tussen 0,6 en 0,7 meestal het best, en de transformer gebruikte 0,6.

Varianten. Diverse beam search (Vijayakumar e.a., 2016) pakt het probleem aan dat de bundels maar weinig van elkaar verschillen. Grid beam search (Hokamp en Liu, 2017) dwingt opgegeven woorden of zinsdelen in de uitvoer af, zoals vaste terminologie in een vertaling.

Waar gaat het mis?

Beam search past volgens de handleiding van Hugging Face bij taken waarvan de lengte van het antwoord redelijk voorspelbaar is, zoals vertalen en samenvatten. In open tekst zoals dialogen of verhalen gaat het zich vaak herhalen. Holtzman e.a. (2019) zagen dat tekst die op de hoogste kans wordt gekozen flauw en vreemd repetitief uitvalt. Voor open tekst geeft de handleiding de voorkeur aan sampling, met instellingen als temperature en top-p, en merkt daarbij op dat ook sampling kan herhalen en dat geen enkele methode bij elke taak past.

Spraakherkenning laat de andere kant zien. Whisper van OpenAI (2022) gebruikt voor lange opnames beam search met 5 bundels, juist om de herhalingslussen te beperken die bij greedy decoding vaker optreden.

Voorbeeld

De handleiding van Hugging Face gebruikt een speelgoedvoorbeeld. Na "The" is "nice" het waarschijnlijkste volgende woord (kans 0,5), en na "The nice" is dat "woman" (0,4), dus greedy decoding eindigt bij "The nice woman" met een kans van 0,5 × 0,4 = 0,2. Beam search met 2 bundels houdt ook de nummer twee, "The dog", vast. Een stap later ziet het dat "The dog has" 0,36 scoort, hoger dan de 0,2 van greedy, en houdt het die zin.