Einfach erklärt
Methoden zur Texterzeugung in Sprachmodellen – Beam Search ist wie Tippen mit mehreren Autovervollständigungen gleichzeitig. Statt immer nur das eine wahrscheinlichste nächste Wort zu nehmen, behält das Verfahren gleichzeitig die besten K Möglichkeiten im Blick (K = Beam‑Breite). Bei jedem Schritt werden diese Möglichkeiten weitergeführt, und es bleiben wieder die K besten. So findet das Modell oft bessere, vollständigere Sätze als mit reiner Greedy‑Wahl.
Kurz: Greedy = „nur die aktuell beste Idee“.
Beam Search = „halte mehrere gute Ideen offen und entscheide später“.
Ganz einfache Beispiele (mit Alltagsbildern):
• Navigation im Labyrinth: Du merkst dir die K vielversprechendsten Wege. An jeder Kreuzung gehst du alle ein Stück weiter, bewertest neu und behältst wieder die K besten.
• Satz vervollständigen: Nach „Ich trinke gern …“ könntest du „Kaffee“, „Tee“, „Wasser“ beginnen. Beam Search verfolgt alle drei und schaut, welche Fortsetzung am Ende am sinnvollsten ist.
• Einkaufslisten‑Plan: Du prüfst mehrere (K) plausible Menüs parallel und streichst nach und nach die, die unpraktisch oder teuer werden.
Professionelle Definition (verständlich)
Wir erzeugen ein Sequenz‑Output y = (y₁,…,y_T). Beim Schritt t hat das Modell Wahrscheinlichkeiten P(y_t | y_{<t}, x). Beam Search hält eine Liste der K besten Teilsequenzen (Beams) mit ihren Log‑Wahrscheinlichkeiten. Für jeden Beam werden alle Kandidaten‑Wörter erweitert, die Scores addiert, und aus allen Erweiterungen werden die K höchsten wieder behalten.
Wichtige Details in der Praxis:
- Beam‑Breite K: Größeres K → gründlichere Suche, aber langsamer.
- Längen‑Normalisierung: Lange Sätze haben mehr Additionen von Log‑Wahrscheinlichkeiten und werden sonst zu stark bestraft. Man teilt daher durch eine Längenfunktion (z. B. Google NMT‑Formel), damit faire Vergleiche entstehen.
- Abbruch/Ende‑Token: Ein Beam ist fertig, wenn ein Ende‑Symbol erzeugt wurde; oft vergleicht man fertige mit unfertigen Hypothesen.
- Diversity‑Tricks: Diverse Beam Search teilt die K Beams in Gruppen und belohnt Unterschiede, damit nicht alle Varianten gleich sind.
- Coverage/Verb‑Nomen‑Abdeckung (Übersetzung): Zusätzliche Strafen/Bonusse verhindern, dass Wörter fehlen oder zu oft wiederholt werden.
Stärken vs. Schwächen:
- Stark bei zielgerichteten Aufgaben (z. B. Übersetzung, Zusammenfassung mit klarer Quelle): bessere Kohärenz als reines Greedy.
- Schwächer bei offenen, kreativen Aufgaben (freies Schreiben) – kann zu langweiligen oder wiederholten Texten führen; hier sind Sampling‑Methoden (top‑p/top‑k/Temperature) oft besser.
Quellen
- Sutskever, Vinyals, Le (2014) – Sequence to Sequence Learning with Neural Networks
https://arxiv.org/abs/1409.3215 - Bahdanau, Cho, Bengio (2015) – Neural Machine Translation by Jointly Learning to Align and Translate
https://arxiv.org/abs/1409.0473 - Wu et al. (2016) – Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation (Längen‑Normalisierung)
https://arxiv.org/abs/1609.08144 - Vijayakumar et al. (2016) – Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models
https://arxiv.org/abs/1610.02424 - Holtzman et al. (2019) – The Curious Case of Neural Text Degeneration (Beam vs. Sampling)
https://arxiv.org/abs/1904.09751 - Koehn (2020) – Neural Machine Translation (Lehrbuch, Decoding‑Kapitel)
https://arxiv.org/abs/2004.11867