FunSearch (kurz für „Suche im Funktionsraum“) ist eine von Google DeepMind entwickelte Methode der künstlichen Intelligenz zur Entdeckung von Computerprogrammen, die mathematische und algorithmische Probleme lösen. Sie kombiniert ein großes Sprachmodell mit einem automatisierten Bewerter und einem evolutionären Suchverfahren, generiert Kandidatenprogramme, bewertet sie und nutzt leistungsstarke Programme, um neue Kandidaten zu erzeugen. Das System wurde 2023 angekündigt, mit einem in der Zeitschrift Nature veröffentlichten Artikel, und wurde auf Probleme der extremalen Kombinatorik und des Online-Bin-Packings angewendet.
FunSearch stellt eine Verschiebung in der Nutzung von großen Sprachmodellen für Entdeckungen dar. Anstatt direkt Antworten zu generieren, formuliert es ein Problem als Suche über Computerprogramme, wodurch das Modell Code vorschlagen kann, der anschließend rigoros getestet wird. Dieser Ansatz nutzt die generativen Fähigkeiten von Modellen wie denen, die in Generative AI verwendet werden, während er sicherstellt, dass die Ausgaben verifizierbar und oft von Forschern interpretierbar sind.
Methode
FunSearch funktioniert durch iterative Generierung und Bewertung von Kandidatenprogrammen. Der Benutzer stellt eine Problemspezifikation, eine Bewertungsfunktion und ein anfängliches Programmskelett bereit. Bei jedem Schritt entnimmt das System bestehende Programme aus einer Datenbank, bevorzugt solche mit höheren Bewertungen, und erstellt einen Prompt für ein vortrainiertes großes Sprachmodell. Das Modell generiert ein modifiziertes Programm, das dann ausgeführt und vom Bewerter bewertet wird. Gültige Programme werden zur Datenbank hinzugefügt, wodurch die Suche auf früheren Erfolgen aufbauen kann.
Die Suche verwendet eine inselbasierte evolutionäre Methode, um die Vielfalt der Kandidatenprogramme zu erhalten und das Risiko einer Konvergenz zu lokalen Optima zu verringern. Ein wesentlicher Vorteil, wie im ursprünglichen Artikel vermerkt, ist, dass FunSearch Programme ausgibt, die von Forschern inspiziert, vereinfacht und interpretiert werden können, anstatt nur eine endgültige numerische Antwort oder eine große Liste von Objekten zu liefern.
Algorithmische Formulierung
FunSearch kann als Suche über einen Raum von Programmfragmenten beschrieben werden, typischerweise Funktionen, die in einem festen Skelett eingebettet sind. Sei \(\mathcal{F}\) der Raum der Kandidatenfunktionen und \(S: \mathcal{F} \to \mathbb{R}\) eine Bewertungsfunktion, die durch Ausführen eines festen Lösers erhalten wird, der die Kandidatenfunktion aufruft. Gegeben eine anfängliche Funktion \(f_0\), unterhält FunSearch eine Datenbank \(D\) bewerteter, gültiger Funktionen. Es entnimmt wiederholt hochbewertete Funktionen aus \(D\), verwendet sie zur Konstruktion von Prompts für ein großes Sprachmodell und bittet das Modell, eine neue Kandidatenfunktion \(f'\) zu generieren. Die neue Funktion wird innerhalb des problemspezifischen Skeletts ausgeführt und bewertet. Wenn sie gültig ist, wird sie zu \(D\) hinzugefügt, sodass spätere Prompts auf stärkeren Kandidaten aufbauen können.
Das idealisierte Ziel ist es, eine Kandidatenfunktion mit hoher Bewertung zu finden, \(f^* \in \arg\max_{f \in \mathcal{F}} S(f)\), obwohl FunSearch in der Praxis die beste gültige Funktion zurückgibt, die während der Suche entdeckt wurde. Die ursprüngliche Implementierung verwendet einen inselbasierten evolutionären Prozess, um Vielfalt zu erhalten und gleichzeitig höher bewertete Programme zu bevorzugen.
Anwendungen
Cap-Set-Problem
FunSearch wurde erstmals am Cap-Set-Problem demonstriert, einem Problem der additiven Kombinatorik, das die größtmögliche Teilmenge von \(\mathbb{Z}_3^n\) ohne drei Punkte auf einer Linie betrifft. In Dimension 8 fand FunSearch ein Cap-Set der Größe 512, was frühere bekannte Konstruktionen verbesserte. Der Artikel berichtete auch über verbesserte untere Schranken für die Cap-Set-Kapazität durch die Entdeckung von Konstruktionen im Zusammenhang mit zulässigen Mengen. Google DeepMind beschrieb das Ergebnis als Beispiel für die Nutzung großer Sprachmodelle zur Generierung verifizierbaren neuen Wissens in der Mathematik. Ein Nature-News-Artikel berichtete, dass das System menschliche Bemühungen bei einem Kombinatorikproblem im Zusammenhang mit dem Kartenspiel Set verbesserte.
Online-Bin-Packing
FunSearch wurde auch auf das Online-Bin-Packing-Problem angewendet, bei dem Elemente beim Eintreffen Behältern zugewiesen werden müssen. In diesem Kontext entwickelte FunSearch programmatische Heuristiken, die entscheiden, welcher Behälter ein neues Element erhalten soll. Der ursprüngliche Artikel berichtete, dass die entdeckten Heuristiken die üblichen First-Fit- und Best-Fit-Baselines auf simulierten Daten und OR-Library-Benchmark-Instanzen übertrafen.
Software
Google DeepMind veröffentlichte die FunSearch-Software in einem öffentlichen GitHub-Repository, sodass Forscher die Ergebnisse reproduzieren und die Methode auf andere Probleme anwenden können. Die Veröffentlichung umfasst den Code für die evolutionäre Suche, die Bewerterschnittstelle und Beispiele für die Cap-Set- und Bin-Packing-Probleme. Diese offene Verfügbarkeit unterstützt weitere Experimente im Bereich des maschinellen Lernens und der künstlichen Intelligenz.
Bedeutung
FunSearch ist bemerkenswert für seine Integration von großen Sprachmodellen mit evolutionärer Berechnung, eine Richtung, die im breiteren Feld des Deep Learnings Aufmerksamkeit erlangt hat. Durch die Erzeugung interpretierbarer Programme bietet es einen Weg zu KI-Systemen, die nicht nur Probleme lösen, sondern auch Erkenntnisse liefern, die Menschen verstehen und darauf aufbauen können. Die Methode wurde im Kontext der breiteren Bemühungen von Google DeepMind diskutiert, KI für wissenschaftliche Entdeckungen einzusetzen, neben anderen Initiativen im Bereich Generative AI.
Obwohl FunSearch bei spezifischen mathematischen und algorithmischen Aufgaben vielversprechend war, bleibt seine allgemeine Anwendbarkeit ein Bereich aktiver Forschung. Die Abhängigkeit von einem vortrainierten Sprachmodell und die Notwendigkeit eines klar definierten Bewerters sind Einschränkungen, die seine Verwendung in anderen Bereichen begrenzen könnten. Dennoch hat der Ansatz weitere Arbeiten zur Nutzung von Sprachmodellen für Programmsynthese und -optimierung inspiriert und trägt zur sich entwickelnden Landschaft der KI-Forschung bei.