Nature News: KI schlägt menschliche Mathematiker und löst erstmals klassische mathematische Probleme

Große Modelle der künstlichen Intelligenz (KI) schlagen menschliche Mathematiker.

In einem heute in Nature veröffentlichten Artikel stellte ein Forscherteam von Google DeepMind eine Methode namens FunSearch zur Suche nach neuen Lösungen in Mathematik und Informatik vor , die auf der Kombination vorab trainierter großer Sprachmodelle (LLMs) mit einem automatischen „Evaluator“ basiert, der Halluzinationen und falsche Vorstellungen verhindert. Durch die Iteration zwischen diesen beiden Komponenten entwickelt sich aus der anfänglichen Lösung neues Wissen.

Diese Studie ist die erste, die LLMs für anspruchsvolle offene Probleme in den Naturwissenschaften oder der Mathematik nutzt. FunSearch hat neue Lösungen für das Upper-Limit-Set-Problem entdeckt, ein seit langem ungelöstes Problem in der Mathematik. Um den praktischen Nutzen von FunSearch zu demonstrieren, nutzten die Forscher es außerdem, um effizientere Algorithmen zur Lösung des „Bin-Packing“-Problems zu entdecken, das allgegenwärtige Anwendungen hat, beispielsweise zur Verbesserung der Effizienz von Rechenzentren.

Der wissenschaftliche Fortschritt hing schon immer von der Fähigkeit ab, neue Erkenntnisse weiterzugeben. Was FunSearch zu einem besonders leistungsstarken wissenschaftlichen Werkzeug macht, ist die Tatsache, dass das ausgegebene Programm nicht nur verrät, was die Lösung ist, sondern auch, wie die Lösung erstellt wurde. Die Autoren des Artikels sagten: „Hoffentlich wird dies Wissenschaftler, die FunSearch verwenden, zu weiteren Erkenntnissen inspirieren und einen positiven Kreislauf aus Verbesserungen und Entdeckungen in Gang setzen.“

„Die von FunSearch generierten Lösungen sind konzeptionell viel umfangreicher als bloße Zahlenlisten“, sagte Jordan Ellenberg, Co-Autor und Professor für Mathematik an der University of Wisconsin-Madison. „Als ich sie studierte, habe ich etwas gelernt.“

Ermitteln der maximalen Obergrenze, Lösen des „Bin-Packing“-Problems

FunSearch verwendet einen evolutionären Ansatz auf Basis von LLMs, um die Ideen mit der höchsten Punktzahl zu fördern und zu entwickeln. Diese Ideen werden in Computerprogramme umgesetzt, sodass sie automatisch ausgeführt und ausgewertet werden können.

Zunächst schreibt der Benutzer eine Beschreibung des Problems in Form von Code, der den Prozess der Programmauswertung und das Seed-Programm enthält, das zum Initialisieren des Programmpools verwendet wird.

FunSearch ist ein iterativer Prozess. In jeder Iteration wählt das System einige Programme aus dem aktuellen Programmpool aus und gibt sie an die LLMs zurück. LLMs bauen dann kreativ darauf auf und generieren neue Programme, die automatisch ausgewertet werden. Die besten Programme werden wieder in die Bibliothek bestehender Programme aufgenommen, wodurch ein Zyklus der Selbstverbesserung entsteht.

FunSearch verwendet PaLM 2 von Google, ist aber mit anderen codetrainierten LLMs kompatibel.

Abbildung | FunSearch-Prozess

Der Schwerpunkt der Forschung lag auf dem Problem der oberen Schrankenmenge , einer ungelösten Aufgabe, die Mathematikern in zahlreichen Forschungsbereichen seit Jahrzehnten Kopfzerbrechen bereitet und die der renommierte Mathematiker Terence Tao einmal als sein liebstes ungelöstes Problem bezeichnete.

Das Problem besteht darin, die größte Menge an Punkten (die sogenannte obere Schrankenmenge) in einem hochdimensionalen Raster zu finden, in dem keine drei Punkte auf einer Linie liegen. Das Problem ist wichtig, weil es als Modell für andere Probleme der Extremalkombinatorik dient, also der Untersuchung, wie groß oder klein Sammlungen von Zahlen, Graphen oder anderen Objekten sein können. Computergestützte Ansätze zur Lösung dieses Problems mit roher Gewalt funktionieren nicht und die Zahl der Möglichkeiten, die berücksichtigt werden müssen, wird schnell größer als die Zahl der Atome im Universum.

Abbildung | Interaktives Diagramm, das die Entwicklung von einem Seed-Programm (oben) zu einer neuen Highscore-Funktion (unten) zeigt. Jeder Kreis ist ein Programm und seine Größe ist proportional zur ihm zugewiesenen Punktzahl.

FunSearch hat jedoch in einigen Settings in einer Verfahrensform die größte jemals entdeckte Menge an Kappen gefunden, was den größten Anstieg der Kappengröße in den letzten 20 Jahren darstellt . Darüber hinaus übertrifft FunSearch modernste Computerlöser.

Darüber hinaus wandten die Forscher FunSearch auf praktische Herausforderungen in der Informatik an, um die Flexibilität von FunSearch zu untersuchen. Das Problem des „Behälterpackens“ befasst sich mit der Frage, wie man Gegenstände unterschiedlicher Größe in möglichst wenige Kartons packt. Es ist der Kern vieler Probleme der realen Welt.

Es ist erst der Anfang

Die Entdeckung neuer mathematischer Erkenntnisse und Algorithmen in unterschiedlichen Bereichen ist eine bekanntermaßen schwierige Aufgabe, die die Fähigkeiten hochmoderner KI-Systeme bei weitem übersteigt. Um solche anspruchsvollen Probleme mit FunSearch zu lösen, wurden in dieser Studie mehrere Schlüsselkomponenten eingeführt.

Es ist erwähnenswert, dass FunSearch keine Blackbox ist, die einfach nur Problemlösungen generiert. Stattdessen werden Verfahren generiert, die beschreiben, wie diese Lösungen erreicht wurden, und diese Methode zur Darstellung der Arbeit entspricht der typischen Arbeitsweise von Wissenschaftlern .

FunSearch bevorzugt die Suche nach Lösungen, die durch hochkompakte Programme dargestellt werden, Lösungen mit geringer Kolmogorov-Komplexität . Kurze Programme können sehr große Objekte beschreiben, sodass FunSearch auf große Probleme wie die Suche nach der Nadel im Heuhaufen skaliert werden kann. Darüber hinaus erleichtert diese Funktion von FunSearch auch das Verständnis der Programmausgaben für Forscher.

Noch wichtiger ist, dass diese Interpretierbarkeit des FunSearch-Programms den Forschern umsetzbare Erkenntnisse liefern kann. Wenn Sie beispielsweise FunSearch verwenden, weisen einige der Ausgaben mit hoher Punktzahl interessante Symmetrien in ihrem Code auf.

Abbildung | Die Untersuchung des von FunSearch generierten Codes liefert weitere umsetzbare Erkenntnisse (links). der ursprüngliche „akzeptable“ Satz, der mit dem (kürzeren) Programm links (rechts) erstellt wurde.

Die Ergebnisse zum Problem der begrenzten Menge zeigen, dass die FunSearch-Technik etablierte Ergebnisse bei schwierigen kombinatorischen Problemen übertreffen kann, bei denen es schwierig ist, Intuition aufzubauen. Die Forscher erwarten, dass dieser Ansatz zu neuen Entdeckungen ähnlicher theoretischer Probleme in der Kombinatorik beitragen und neue Möglichkeiten in Bereichen wie der Kommunikationstheorie eröffnen wird.

Alternativ können schwierige kombinatorische Probleme wie Online-Bin-Packing mithilfe anderer KI-Methoden wie neuronalen Netzwerken und bestärkendem Lernen gelöst werden. Der Ansatz von FunSearch hat sich ebenfalls als effektiv erwiesen, seine Implementierung kann jedoch ressourcenintensiv sein. Andererseits lässt sich der von der Methode ausgegebene Code leicht überprüfen und einsetzen, was bedeutet, dass die Lösung das Potenzial hat, in eine Vielzahl realer Industriesysteme eingebettet zu werden und so schnell Vorteile zu bringen.

FunSearch zeigt, dass die Leistungsfähigkeit dieser Modelle nicht nur zur Generierung neuer mathematischer Entdeckungen genutzt werden kann, sondern auch zur Aufdeckung potenziell wirksamer Lösungen für wichtige Probleme der realen Welt, wenn man sich vor den Illusionen der LLMs hütet.

Das Forschungsteam geht davon aus, dass es in Zukunft üblich werden wird, LLM-basierte Ansätze zu verwenden, um effiziente und maßgeschneiderte Algorithmen für viele – sowohl alteingesessene als auch neue – Probleme in Wissenschaft und Industrie zu entwickeln.

Tatsächlich ist dies erst der Anfang. „Wir werden auch daran arbeiten, seine Fähigkeiten zu erweitern, um eine Vielzahl dringender wissenschaftlicher und technischer Herausforderungen der Gesellschaft zu bewältigen“, sagten die Forscher.

Referenzlinks:

https://deepmind.google/discover/blog/funsearch-making-new-discoveries-in-mathematical-sciences-using-large-lingual-models/

https://www.nature.com/articles/s41586-023-06924-6