Jenseits von A*: Bessere Planung mit Transformern

 (arxiv.org)
2 Punkte von GN⁺ 2024-02-25 | 1 Kommentare | Auf WhatsApp teilen
  • Transformer und LLMs sind stark bei Dialog, Bildverständnis und Code-Vervollständigung, liefern aber bei mehrstufiger Planung und höherwertigem Schlussfolgern nur schwer stabile Leistung
  • Diese Arbeit wandelt Planungsaufgaben und optimale Lösungen in Tokensequenzen um und nimmt sogar den Ausführungspfad von A* in die Trainingsdaten auf
  • Searchformer imitiert zunächst den Suchprozess von A* und wird dann so feinabgestimmt, dass es kürzere Suchsequenzen erzeugt, ohne die optimalen Pläne zu verlieren
  • In Sokoban-Experimenten lösten Modelle der Searchformer-Familie 93,7 % der Testaufgaben und verwendeten im Schnitt 26,8 % weniger Suchschritte als eine A*-Referenzimplementierung
  • Ausführungspfade vergrößern die erzeugten Sequenzen zwar um 10× bis 100×, ermöglichen aber trotzdem, mit weniger Trainingssequenzen als größere reine Lösungsmodelle auf unbekannten Aufgaben häufiger optimale Pläne zu erzeugen

Worin Transformer gut sind und wo Planungsaufgaben schwächeln

  • Transformer-basierte Architekturen zeigen in vielen Aufgaben hohe Leistung
    • Dialoge auf menschlichem Niveau
    • Hochwertiges Bildverständnis
    • Videogenerierung
    • Multimodale Generierung
    • Code-Vervollständigung
  • Modelle wie LLMs, die auf Daten im Internetmaßstab trainiert wurden, können in realen Anwendungsfällen gut generalisieren
  • Bei Planungs- und Schlussfolgerungsaufgaben bestehen jedoch weiterhin Grenzen
    • LLMs zeigen Schwächen bei mehrstufigen Planungsaufgaben
    • Auch bei höherwertigem Schlussfolgern treten Schwierigkeiten auf

Grenzen von Prompts für schrittweises Denken

  • Jüngere Ansätze versuchen, die Leistung zu steigern, indem Transformer zunächst Zwischen-„Gedanken“ erzeugen und erst danach antworten
  • Chain-of-Thought(CoT)-Prompting und Tree-of-thoughts(ToT) ermutigen Modelle dazu, schrittweise zu „denken“
  • Solche Techniken sind oft wirksam, können die Leistung aber aus Gründen wie self-enforcing auch verschlechtern
  • Ein Verfahren, das auf einem Datensatz gut funktioniert, kann auf einem anderen scheitern
    • Ein Beispiel dafür sind unterschiedliche benötigte Schlussfolgerungstypen wie räumliches und mathematisches Schlussfolgern
  • Wie sich Transformer und LLMs zu stabiler Planung, mehrstufiger Entscheidungsfindung und Schlussfolgerung befähigen lassen, ist weiterhin ein aktives Forschungsthema

A*-Suchdynamik als Teil der Trainingsdaten

  • Dieser Ansatz konzentriert sich darauf, Transformer so zu trainieren, dass sie komplexe Planungsaufgaben robuster lösen
  • Das Modell wird wie ein LLM darauf trainiert, bei gegebener Wortsequenz das nächste Wort vorherzusagen
  • Die Experimente wurden auf synthetisch erzeugten Datensätzen mit synthetischer Sprache und synthetischem Vokabular durchgeführt
  • Planungsaufgaben und optimale Lösungspläne werden als Wortsequenzen dargestellt, die als Token bezeichnet werden
  • Der von A* ausgeführte Rechenprozess wird als Tokensequenz eines Ausführungspfads aufgezeichnet
    • Der Ausführungspfad bildet einen Sequenzdatensatz, der die Suchdynamik von A* enthält
    • Der Transformer wird mithilfe suchverstärkter Sequenzen darauf trainiert, Tokensequenzen zu erzeugen, die sowohl die Suchdynamik von A* als auch optimale Pläne kodieren

Trainingsverfahren von Searchformer

  • Das Endmodell Searchformer entsteht in zwei Schritten
    • Zuerst wird ein Transformer darauf trainiert, den Suchprozess von A* nachzuahmen
    • Anschließend wird es so feinabgestimmt, dass es optimale Pläne ausgibt und dabei den Plan mit weniger Suchschritten findet
  • Dieser Prozess wird search dynamics bootstrapping genannt
  • Das Ziel ist ein Transformer, der komplexe Planungsaufgaben mit weniger Suchschritten als eine A*-Referenzimplementierung löst

Sokoban-Experimente und Generalisierungsleistung

  • Bei Sokoban-Rätseln lösten Modelle der Searchformer-Familie 93,7 % aller Testaufgaben
  • Die durchschnittliche Zahl der Suchschritte lag 26,8 % niedriger als bei einer A*-Referenzimplementierung
  • In Experimenten mit kontrollierter Aufgabenkomplexität, Datensatzgröße und Modellgröße wurde der Effekt der Einbeziehung von Ausführungspfaden bestätigt
  • Werden Ausführungspfade in die Trainingsdaten aufgenommen, wächst die Länge der erzeugten Sequenzen um 10× bis 100×
  • Trotzdem steigt die Leistung auf einem unabhängigen Testset
  • Search-augmented-Modelle erzeugen auf unbekannten Aufgaben häufiger optimale Pläne als größere solution-only-Modelle, obwohl sie mit zehnmal weniger Trainingssequenzen trainiert wurden
    • Search-augmented-Modelle werden mit Daten trainiert, die Aufgabenbeschreibung, Lösung und Ausführungspfad enthalten
    • Solution-only-Modelle werden nur mit Sequenzen trainiert, die Aufgabenbeschreibung und Aufgabenlösung enthalten
  • Diese Ergebnisse zeigen, dass die Einbeziehung der Suchdynamik von A* in den Trainingsprozess von Transformern die Leistung bei Planungsaufgaben verbessern kann

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-02-25
Meinungen auf Hacker News

  • Es gab auch interessantere Arbeiten zum Einsatz von Transformern für Robot Motion Planning 0
    Das Problem, einen Roboterarm von Punkt A nach Punkt B zu bewegen und dabei Kollisionen zu vermeiden, ist hochdimensional und kontinuierlich und daher sehr schwierig; klassische Planungsverfahren sind rechenintensiv und liefern dennoch oft keine gute Leistung.
    Das ist einer der Gründe, warum Roboterbewegungen „unnatürlich“ wirken und Roboter viele Aufgaben, die wir von ihnen erwarten, nicht gut erledigen. Dieser Ansatz scheint nahezu optimale Pfade schneller zu planen und wirkt im Vergleich zu anderen Methoden ziemlich konkurrenzfähig.

  • Bevor man in diese Forschungsrichtung geht, frage ich mich, ob sie den Modified-J-Algorithmus* ausprobiert haben, eine A*-Optimierung für Spielgraphen/Pfadsuche.
    Wer neugierig ist: Er steht in Game AI Pro 2 0

    • Dazu gibt es auch https://github.com/anvaka/ngraph.path
    • Fairerweise sagen sie am Ende des Papers, dass ihr Pfadfinder noch nicht auf dem Niveau der State-of-the-Art-Verfahren konkurriert.
      Das Paper testet, wie gut Transformer Ausführungsspuren vorhersagen können, etwa wie bei JIT-Compilern, und ob das zur Verbesserung von Heuristiken in Bereichen wie der Pfadsuche beitragen kann.
      Allerdings sind Transformer langsam, daher sehe ich das mit Vorsicht.
    • Ich mag diese Bücher und freue mich, dass Steve Rabin weiter daran arbeitet, aber dass das E-Book 120 Dollar kostet, hatte ich nicht erwartet.

  • Planungsprobleme werden bereits gut von etablierten Verfahren wie Graphsuche, SAT-Solvern, Operations Research und Prolog abgedeckt.
    Meist geht es im Kern um Optimierung zwischen mehreren möglichen Alternativen; ich bin mir nicht sicher, ob Transformer dafür geeignet sind.
    Die Rolle von LLM-basierten Methoden scheint eher darin zu liegen, natürlichsprachliche Beschreibungen in ausführbare Programme zu übersetzen. Prolog liegt dem aber ohnehin schon ziemlich nahe, da es ursprünglich für klassische Verarbeitung natürlicher Sprache entworfen wurde.

    • Es wäre interessant, Prolog und LLMs mit einem ähnlichen Ziel zu vergleichen.

  • Maschinelle Übersetzung brauchte früher komplexes Grammatik-Decoding mit Suche, heute nutzt man Transformer mit einem deutlich einfacheren Decoding, das praktisch ohne Suche auskommt.
    Jetzt könnte man sogar bis zu vollständig rekursiven Strukturen gehen.
    Die Idee wäre, mit den derzeit besten Vorhersagemodellen Heuristiken für Neural Architecture Search (NAS) zu lernen und neue neuronale Netzwerkblöcke zu finden, die besser sind als Transformer oder Mamba.

    • „Jedes Mal, wenn ich einen Linguisten entlasse, verbessert sich die Leistung des Spracherkenners.“ — Frederick Jelinek
    • Am Ende könnten wir in eine Welt geraten, in der selbst die Menschen, die die Technologie entwickeln, nicht mehr verstehen, wie sie funktioniert.
      Die Singularität kommt …

  • Wenn dich Spiele im Stil von Sokoban interessieren, lohnt sich ein Blick auf https://thinky.gg
    Dort gibt es eine interessante Sokoban-Variante namens Sokopath sowie eine weitere NP-schwere Variante namens Pathology, bei der das Ziel ist, mit der kürzesten Schrittzahl von Punkt A nach Punkt B zu gelangen.
    Die Community hat versucht, mehrere Solver zu bauen, aber sobald das Raster größer als 5x5 wird, wird es sehr schwierig. Außerdem hat die thinky-Community per Simulated Annealing interessante Level mit sehr hoher maximaler Schrittzahl gefunden.

  • „26,8 % weniger Suchschritte als die Standard-A*-Suche“
    Also ist es in Sokoban nur etwas besser als A*, das weit vom Stand der Technik entfernt ist (https://festival-solver.site/)
    Ich weiß nicht, was an diesem Paper beeindruckend sein soll oder warum es auf Hacker News gelandet ist.

    • A* ist unter den von ihm ausdrücklich angenommenen Einschränkungen der optimale Suchalgorithmus; besser geht es dort nicht.
      Wenn es im Zielbereich der Suche aber weitere nutzbare Einschränkungen gibt, kann man besser sein als A*.
      Jump Point Search nutzt zum Beispiel Eigenschaften der Rastersuche aus, bei der man sich nur auf bestimmte Weise bewegen kann.
      Es wäre doch nützlich, wenn man einen allgemeinen Suchalgorithmus bauen könnte, der die besonderen Eigenschaften der zugrunde liegenden Domäne effektiv „automatisch“ ausnutzt, ohne dass Menschen sie manuell analysieren müssen.
    • Weil sie mit Transformern eine ordentliche Lösung erreicht haben, die besser ist als die standardmäßige A*-Suche.
      A* ist eher die „naive“ Basislösung, und sie haben sich nicht selbst um Algorithmendesign gekümmert.
      Dass ein einfacher Encoder-Decoder-Transformer so etwas leisten kann, ist ziemlich beeindruckend.
    • Das steht direkt in der ersten Zeile des Abstracts:
      “Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ...”
      Das Paper ist interessant, weil es ein Beispiel für den Einsatz von Transformern bei Entscheidungsfindung ist; ob es schon jetzt auf A-Niveau* ist, interessiert mich eher wenig.
    • Es ist auf HN gelandet, weil die Community es mochte.
    • Es ist ein weiterer Beleg für die unvernünftige Effektivität von Transformern: Sie sind nicht nur für Next-Token Prediction geeignet, sondern als vollständig allgemeiner Ansatz auf alle möglichen Lernaufgaben anwendbar.
      Natürlich gibt es von dieser Hypothese eine starke und eine schwache Version, und die starke Version ist wahrscheinlich nicht wahr. Aber solange es so aussieht, als kämen wir einer „einzig wahren Art“, wie die Natur Dinge lernt, näher, wirkt das wie eine wichtige Nachricht.

  • Wenn Transformer planen können, bedeutet das vielleicht, dass allgemeine künstliche Intelligenz nur bessere Ausbildung braucht.

    • Die Approximation vollständiger Suche ist keine Logik oder Kausalität.
    • Es braucht sehr viel mehr Bausteine, und Agency macht einen großen Teil davon aus.
      Online Learning ist ebenfalls nötig, und darüber hinaus braucht es noch mehrere weitere Ebenen.
    • Für die absehbare Zukunft wird die Richtung wahrscheinlich sein, immer mehr Daten hineinzufüttern, um Halluzinationen zu verhindern.

  • Für auditive Lerntypen gibt es eine Zusammenfassung dieses Papers im Audiobook-Format.
    https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f

  • Ich bin sehr optimistisch, was gelernte Heuristiken für diskrete Algorithmen wie A*, Focal Search und verschiedene Klassen der ganzzahligen linearen Programmierung angeht.
    Bei den meisten modernen Bibliotheken für diskrete Optimierung wie CPLEX erklären Heuristiken und Tuning die Leistungsunterschiede.
    Gut verstandene optimale Suchroutinen durch einen End-to-End-Lernansatz zu ersetzen, überzeugt mich weniger, aber das könnte auch eine unbegründete Sorge sein.
    Allerdings wirkt es so, als hätten die Autoren diese Chance verpasst.

    • Das wirkt einfach wie der Hype-/Übertreibungseffekt rund um Transformer und AI.
      Vielleicht sollte ich auch Tic-Tac-Toe mit einem Transformer lösen und VC-Geld beantragen.
      In ein paar Jahren schreiben vielleicht alle darüber, wie viel effizienter echter Code als AI ist ;)
    • Zustimmung.
      Wenn man zulässige Heuristiken lernt, kann man die Worst-Case-Leistung erhalten, und genau das war immer der Maßstab für solche Algorithmen.
      Es ist keineswegs selten, Lösungen zu finden, die im Durchschnitt oder im p99-Fall schneller sind, aber keine Worst-Case-Garantien bieten.

  • Ich frage mich, ob jemand eine Liste klassischer Algorithmen oder NP-vollständiger Probleme pflegt, die durch Deep Learning besser gelöst werden.

    • Der Einfachheit halber hier eine Liste NP-vollständiger Probleme, bei denen „AI“ im Worst Case besser ist als der Stand der Technik:
    • Soweit ich es verstehe, ist das noch ein sehr aktives Forschungsfeld, und es gibt noch keine klaren Siege, die in Produktionsumgebungen ausgerollt wurden.