Strahlsuche

Was ist Beam Search?

Beam Search ist ein heuristischer Suchalgorithmus, der den vielversprechendsten Knoten in einer begrenzten Menge zur Erkundung eines Graphen erweitert. Diese Technik verwendet einen Breitensuchalgorithmus, um eine Baumdatenstruktur aufzubauen und Nachfolger des aktuellen Zustands jeder Ebene zu erzeugen.

Anwendungen der natürlichen Sprachverarbeitung (NLP) und Spracherkennungsmodelle verwenden Beam Search als Entscheidungsschicht. Das Ziel ist es, die beste Ausgabe für Zielvariablen wie das nächste Ausgabesymbol oder die maximale Wahrscheinlichkeit zu wählen.

Der Beam Search Algorithmus wählt Tokens für eine bestimmte Position in einer Sequenz basierend auf bedingter Wahrscheinlichkeit aus. Er passt die Strahlbreite (β) an, um verschiedene Hyperparameter n Alternativen zu wählen.

Im Gegensatz zur gierigen Suche erweitert Beam Search die Suche, um mögliche Passungen für Wörter in einer Sequenz zu erkunden. Beam Search erhält seinen Namen von der Art und Weise, wie der Algorithmus einen breiten Suchstrahl wirft. 

Arten von Beam Search

Beam Search hat je nach verwendetem Algorithmus verschiedene Varianten, wie Tiefensuche (DFS), begrenzte Diskrepanzsuche und speicherbasierte Suche.

1. Beam Stack Search ist ein Suchalgorithmus, der einen Beam Stack als Datenstruktur verwendet, um Tiefensuche oder chronologisches Backtracking mit Beam Search zu kombinieren. Benutzer können ihn auch mit einem Divide-and-Conquer-Algorithmus verbinden — eine Technik, die ein Problem rekursiv in zwei oder mehr Teilprobleme zerlegt — um eine Divide-and-Conquer Beam-Stack-Suche zu erstellen.
2. Tiefenstrahlsuche verwendet einen Tiefensuchalgorithmus zur Suche in Graphdatenstrukturen. Sie verwendet zusätzlichen Speicher oder einen Stack, um erkundete Knoten entlang eines bestimmten Zweigs zu verfolgen und den Graphen zurückzuverfolgen. 
3. Lokale Strahlsuche verfolgt oder hält bis zu k zufällig generierte Zustände oder Anzahl von Zuweisungen anstelle von einem. Sie wählt k beste Nachbarn der aktuellen Individuen in jeder Phase. Der Algorithmus meldet Erfolg nur nach dem Finden einer zufriedenstellenden Zuweisung. Bei Gleichständen wählt er zufällige Werte.
4. Stochastische Strahlsuche wählt k der Individuen zufällig anstelle der besten k Individuen. Diese Variante der Strahlsuche verwendet die Wahrscheinlichkeit, ausgewählt zu werden, als Funktion der Bewertungsfunktion. Je besser die Bewertung, desto höher die Chancen, ausgewählt zu werden.
5. Strahlsuche mit begrenztem Diskrepanz-Backtracking (BULB) ist eine speicherbasierte Suchmethode, die größere Suchprobleme innerhalb einer angemessenen Laufzeit löst. BULB-Suchen tun dies, indem sie größere Strahlbreiten verwenden und kürzere Pfade finden, ohne Speicher zu verlieren.
6. Flexible Strahlsuche erhöht vorübergehend die Strahlbreite, um alle Kindknoten mit demselben heuristischen Wert einzuschließen. 

Komponenten der Strahlsuche

Beam Search hat drei Komponenten:

1. Ein Problem, das ein Graph sein kann oder eine Menge von Knoten enthält, die ein Ziel darstellen.
2. Heuristische Regeln beziehen sich auf die problemspezifischen Richtlinien, die verwendet werden, um ungünstige Knoten aus dem Speicher zu entfernen und sich auf das Problemfeld zu konzentrieren.
3. Speicher, der den Strahl speichert, aber eine begrenzte verfügbare Kapazität hat. Wenn der Speicher voll ist, löscht der Algorithmus automatisch den teuersten Knoten, um das Überschreiten des Speichers zu vermeiden. 

Vorteile der Verwendung von Beam Search 

Beam Search versucht, das Optimum auf heuristische Weise zu finden. Die Vorteile der Verwendung von Beam Search zur Lösung von Optimierungsproblemen sind:

• Reduzierte Berechnung: Beam Search verwendet eine begrenzte Anzahl von Knoten oder Ressourcen gleichzeitig. Dadurch benötigt sie weniger Berechnung und Speicherverbrauch im Vergleich zu anderen Suchmethoden. Die Entwicklung effektiver heuristischer Regeln zum Beschneiden ist entscheidend, um diesen Vorteil zu realisieren, was ohne Domänenwissen eine Herausforderung sein kann.
• Verbesserte suboptimale Entscheidungen: Gierige Suche betrachtet jede Position isoliert. Im Gegensatz dazu betrachtet Beam Search mehr als eine Option gleichzeitig und verbessert suboptimale Entscheidungen. 

Nachteile der Verwendung von Beam Search 

Der Hauptnachteil der Verwendung von Beam Search ist, dass Benutzer möglicherweise am Ende kein optimales Ziel erreichen. Die meisten Beam Search Algorithmen enden in zwei Szenarien: Entweder hat der Benutzer noch keinen Zielknoten erreicht und es gibt keinen Knoten mehr zu erkunden, oder er hat den erforderlichen Zielknoten erreicht. 

Darüber hinaus kann Beam Search aufgrund ihrer probabilistischen Natur unvollständig sein. Trotz dieser Nachteile haben Beam Search Algorithmen Erfolge in Spracherkennung, Vision, Planung und maschinellem Lernen erzielt. 

Verwendungen von Beam Search

Beam Search hat mehrere Anwendungen in maschinellen Übersetzungssystemen, NLP und Spracherkennung. Große Systeme mit unzureichendem Speicher, um den gesamten Suchbaum zu speichern, greifen häufig auf Beam Search zurück, um handhabbar zu bleiben.

Neuronale maschinelle Übersetzungssysteme (NMT) verwenden Beam Search, um die beste Übersetzung zu wählen und jeden Teil zu verarbeiten. Sie behalten die besten Übersetzungen mit den richtigen Satzstrukturen und verwerfen den Rest. Der Übersetzer überprüft dann die Übersetzungen und wählt die beste aus, die die Ziele erfüllt. Im Jahr 1976 war das Harpy-Spracherkennungssystem der Carnegie-Mellon-Universität das erste, das eine Strahlsuche verwendete. 

Beam Search vs. Gierige Suche vs. Best-First-Suche

Eine gierige Suche folgt der Problemlösungsheuristik, um eine Lösung schrittweise aufzubauen, einen Schritt nach dem anderen. Das System priorisiert die Auswahl des nächsten Teils, der klare und unmittelbare Vorteile bietet. Gierige Algorithmen funktionieren am besten bei Problemen, bei denen es wichtig ist, lokal optimale Lösungen zu wählen.

Beam Search optimiert die Best-First-Suche, um den Speicherbedarf zu reduzieren.

Sowohl gierige als auch Beam Searches verwenden Sequenz-zu-Sequenz-Modelle, um Sequenzausgaben oder Tokens aus einem neuronalen Netzwerk zu erzeugen. Der erstere bewertet jedoch jede Position unabhängig, während der letztere mehr als eine gleichzeitig betrachtet.

Best-First-Suche ist eine Graphsuchtechnik, die Teillösungen basierend auf Heuristiken sortiert und ordnet. Beam Search betrachtet jedoch eine vorbestimmte Anzahl der besten Teillösungen als Kandidaten. Deshalb wird Beam Search als gieriger Algorithmus behandelt. 

Möchten Sie Daten auf verständliche Weise interpretieren? Entdecken Sie die besten natürlichen Sprachgenerierungssoftware (NLG) zur Verarbeitung von Datensätzen.