Beam Search

Beam Search ist ein heuristisches Suchverfahren aus der Künstlichen Intelligenz, das zur Lösung von Such- und Optimierungsproblemen verwendet wird. Es stellt eine speichereffiziente Variante der Best-First Search dar und kombiniert Merkmale von Breitensuche und heuristischer Suche.

Die Grundidee besteht darin, in jeder Suchebene nur eine begrenzte Anzahl der vielversprechendsten Kandidaten weiterzuverfolgen. Dadurch wird der Speicherbedarf erheblich reduziert, allerdings besteht die Gefahr, optimale Lösungen zu verwerfen.

Beam Search wird unter anderem in folgenden Bereichen eingesetzt:

Motivation

Viele Suchprobleme besitzen einen sehr großen Suchraum.

Beispiele:

Routenplanung
Schachprogramme
Produktionsplanung
Textgenerierung durch Large Language Models
Optimierungsprobleme mit vielen Entscheidungsvariablen

Eine vollständige Suche ist häufig nicht praktikabel, da die Anzahl möglicher Zustände exponentiell wächst.

Beam Search reduziert den Suchaufwand, indem nur die besten Kandidaten jeder Ebene betrachtet werden.

Grundidee

Beam Search erweitert die aktuell vielversprechendsten Zustände.

Nach jeder Erweiterung werden die erzeugten Nachfolger bewertet.

Anschließend werden nur die besten Zustände beibehalten.

Alle anderen Zustände werden dauerhaft verworfen.

Die maximale Anzahl gespeicherter Zustände wird als Beam Width bezeichnet.

Beam Width

Die Beam Width wird häufig mit k bezeichnet.

Beispiel:

$k = 5$

Dann werden in jeder Ebene höchstens fünf Zustände weiterverfolgt.

Je größer k gewählt wird:

desto höher die Lösungsqualität
desto größer der Speicherbedarf
desto höher die Rechenzeit

Je kleiner k gewählt wird:

desto schneller die Suche
desto höher das Risiko, gute Lösungen zu verwerfen

Ablauf des Verfahrens

Schritt 1: Startzustand

Die Suche beginnt mit einem Startknoten.

Schritt 2: Erweiterung

Alle aktuell gespeicherten Zustände werden expandiert.

Schritt 3: Bewertung

Jeder Nachfolger erhält einen Bewertungswert.

Dieser kann beispielsweise durch:

Kostenfunktionen
Heuristiken
Wahrscheinlichkeiten

bestimmt werden.

Schritt 4: Auswahl

Die Nachfolger werden sortiert.

Nur die besten k Zustände bleiben erhalten.

Schritt 5: Wiederholung

Die Schritte werden solange wiederholt, bis:

eine Lösung gefunden wurde
ein Abbruchkriterium erfüllt ist

Beispiel

Angenommen, die Beam Width beträgt:

$k = 2$

Der Startknoten besitzt vier Nachfolger:

Zustand	Bewertung
A	10
B	7
C	5
D	2

Es werden nur die beiden besten Zustände weiterverfolgt:

A
B

Die Zustände C und D werden verworfen.

Pseudocode

BeamSearch(Start, k):

Beam ← {Start}

while nicht beendet:

    Kandidaten ← {}

    für jeden Zustand in Beam:
        Nachfolger erzeugen
        Kandidaten hinzufügen

    Kandidaten sortieren

    Beam ← beste k Kandidaten

return beste Lösung

Mathematische Beschreibung

Sei:

$B_{t}$

die Menge der Zustände im Suchstrahl (Beam) zum Zeitpunkt t.

Nach der Expansion entsteht:

$C_{t}$

als Menge aller Nachfolger.

Anschließend wird ausgewählt:

$B_{t + 1} = T o p_{k} (C_{t})$

wobei:

$T o p_{k}$

die Auswahl der k besten Zustände beschreibt.

Eigenschaften

Unvollständigkeit

Beam Search ist nicht vollständig.

Eine existierende Lösung kann verworfen werden.

Keine Optimalitätsgarantie

Das Verfahren garantiert nicht das Auffinden der optimalen Lösung.

Speicherbegrenzung

Der Speicherbedarf bleibt kontrollierbar.

Hohe Geschwindigkeit

Beam Search ist deutlich schneller als vollständige Suchverfahren.

Vergleich mit anderen Suchverfahren

Verfahren	Vollständig	Optimal	Speicherbedarf
Breitensuche	Ja	Ja	Sehr hoch
Tiefensuche	Nein	Nein	Gering
A*	Ja	Ja	Hoch
Beam Search	Nein	Nein	Kontrollierbar

Beam Search und A*

Beam Search wird häufig als speicherbegrenzte Variante von A* betrachtet.

Während A* alle vielversprechenden Zustände speichert, begrenzt Beam Search deren Anzahl.

Dadurch wird Speicher eingespart.

Allerdings gehen Optimalitätsgarantien verloren.

Einfluss der Beam Width

Kleine Beam Width

Beispiel:

$k = 1$

Dies entspricht einer Greedy Search.

Vorteile:

Sehr schnell
Sehr geringer Speicherbedarf

Nachteile:

Schlechte Lösungsqualität

Große Beam Width

Beispiel:

$k = 100$

Vorteile:

Höhere Wahrscheinlichkeit guter Lösungen

Nachteile:

Höherer Ressourcenverbrauch

Anwendungen in der Künstlichen Intelligenz

Maschinelle Übersetzung

Neuronale Übersetzungsmodelle erzeugen für jedes Wort mehrere mögliche Fortsetzungen.

Beam Search behält die wahrscheinlichsten Übersetzungen.

Sprachmodelle

Viele Large Language Models verwenden Beam Search zur Textgenerierung.

Dabei werden mehrere mögliche Satzfortsetzungen parallel betrachtet.

Spracherkennung

Mehrere mögliche Wortfolgen werden bewertet und verglichen.

Bildbeschreibung

KI-Systeme erzeugen mehrere Kandidatensätze für Bildbeschreibungen.

Anwendungen in der Optimierung

Beam Search wird häufig für kombinatorische Optimierungsprobleme eingesetzt.

Beispiele:

Produktionsplanung
Tourenplanung
Ressourcenallokation
Scheduling
Netzwerkoptimierung

Beispiel aus der Produktionsplanung

Eine Fabrik möchte eine optimale Produktionsreihenfolge bestimmen.

Jede Entscheidung erzeugt neue Teilpläne.

Eine vollständige Suche wäre zu teuer.

Beam Search verfolgt nur die vielversprechendsten Teilpläne weiter.

Dadurch können gute Lösungen in akzeptabler Zeit gefunden werden.

Beam Search in der Multi-Objective-Optimierung

Bei Mehrzielproblemen kann die Bewertung eines Zustands beispielsweise erfolgen durch:

gewichtete Summe der Zielfunktionen
Pareto-Rang
Dominanzbeziehungen

Beam Search dient dabei häufig als Metaheuristik zur Approximation guter Lösungen.

Varianten

Stochastic Beam Search

Die Auswahl erfolgt zufallsbasiert entsprechend einer Wahrscheinlichkeitsverteilung.

Dadurch wird die Diversität erhöht.

Local Beam Search

Mehrere lokale Suchprozesse laufen parallel.

Die besten Zustände werden gemeinsam betrachtet.

Diverse Beam Search

Zusätzlich wird die Vielfalt der Kandidaten berücksichtigt.

Dies wird häufig bei Sprachmodellen verwendet.

Beam Stack Search

Kombination aus Beam Search und Backtracking.

Dadurch können zuvor verworfene Bereiche erneut untersucht werden.

Vor- und Nachteile

Vorteile

Einfach zu implementieren
Geringer Speicherbedarf
Gute Skalierbarkeit
Schnelle Laufzeiten
Für große Suchräume geeignet

Nachteile

Keine Optimalitätsgarantie
Nicht vollständig
Empfindlich gegenüber der Wahl der Beam Width
Gute Lösungen können früh verworfen werden

Komplexität

Seien:

b = Verzweigungsfaktor
d = Suchtiefe
k = Beam Width

Dann ergibt sich näherungsweise:

Zeitaufwand:

$O (k \cdot b \cdot d)$

Speicherbedarf:

$O (k)$

Der Speicherbedarf wächst somit linear mit der Beam Width.

Literatur

Russell, S.; Norvig, P.: Artificial Intelligence: A Modern Approach. Pearson.
Pearl, J.: Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.
Jurafsky, D.; Martin, J.: Speech and Language Processing. Pearson.
Koehler, G.: Künstliche Intelligenz. Springer Vieweg.
Ghallab, M.; Nau, D.; Traverso, P.: Automated Planning. Morgan Kaufmann.

Siehe auch

Beam Search

Beam Search

Motivation

Grundidee

Beam Width

Ablauf des Verfahrens

Schritt 1: Startzustand

Schritt 2: Erweiterung

Schritt 3: Bewertung

Schritt 4: Auswahl

Schritt 5: Wiederholung

Beispiel

Pseudocode

Mathematische Beschreibung

Eigenschaften

Unvollständigkeit

Keine Optimalitätsgarantie

Speicherbegrenzung

Hohe Geschwindigkeit

Vergleich mit anderen Suchverfahren

Beam Search und A*

Einfluss der Beam Width

Kleine Beam Width

Große Beam Width

Anwendungen in der Künstlichen Intelligenz

Maschinelle Übersetzung

Sprachmodelle

Spracherkennung

Bildbeschreibung

Anwendungen in der Optimierung

Beispiel aus der Produktionsplanung

Beam Search in der Multi-Objective-Optimierung

Varianten

Stochastic Beam Search

Local Beam Search

Diverse Beam Search

Beam Stack Search

Vor- und Nachteile

Vorteile

Nachteile

Komplexität

Literatur

Siehe auch

Navigationsmenü

Suche