Die neuesten Ergebnisse von Google DeepMind werden in Nature veröffentlicht, indem große Modelle zur Lösung von Problemen verwendet werden, die Mathematiker seit mehr als 60 Jahren beschäftigen.Pushmeet Kohli, einer der Autoren und Vizepräsident für Forschung bei Google DeepMind, sagte:Dieses Schema wird nicht in den Trainingsdaten enthalten sein und es wird den Menschen vorher noch nicht einmal bekannt sein.
Diese Technologie heißt FunSearch, wobei Fun die Abkürzung für Funktion ist.
Nutzen Sie große Modelle, um seit langem bestehende wissenschaftliche Herausforderungen zu lösen und neue, überprüfbare und wertvolle* Informationen zu generieren, die vorher nicht existierten.
In der dem Nature-Artikel beigefügten Nachrichteninterpretation erklärte der Verantwortliche von DeepMind: „Die Art und Weise, wie wir große Modelle nutzen, dient als Kreativitätsmotor.“
Dies ist das erste Mal, dass jemand gezeigt hat, dass Systeme, die auf großen Modellen basieren, die Erkenntnisse von Mathematikern und Informatikern übertreffen können.
Es ist nicht nur neu, es ist auch effektiver als alles andere, was es heute gibt.
Als Reaktion auf diesen Erfolg beklagten einige Internetnutzer:
Wenn das wahr ist, handelt es sich um die wichtigste Entdeckung der Menschheit seit dem Brand.
Welche Probleme löst FunSearch?
Finden Sie bessere Lösungen für NP-schwere Probleme
DeepMind demonstriert speziell zwei Arten von Problemen, bei denen es sich beide um NP-schwere Probleme handelt.
Nach Ansicht der akademischen Gemeinschaft gibt es keinen Algorithmus und wird es möglicherweise auch nie geben, der unter allen Umständen exakte Lösungen für NP-schwere Probleme in polynomieller Zeit finden kann.
Angesichts solcher Probleme suchen Forscher in der Regel nach Näherungslösungen oder effizienten Algorithmen, die für bestimmte Situationen geeignet sind.
Spezifisch für FunSearch ist die erste Art von NP-schweren Problemen, die es löst, das Capset-Problem, bei dem es sich um eine Art Obergrenzensatzproblem handelt. Seine Beschreibung lautet wie folgt:
In jeder Dimension eines n-dimensionalen Raums gibt es n Punkte mit gleichem Abstand (n^n insgesamt, zum Beispiel sind 3 Dimensionen 3*3*3). Finden Sie so viele Punkte wie möglich, um eine Menge zu bilden. Es ist erforderlich, dass drei beliebige Punkte in der Menge nicht kollinear sind. Wie viele Punkte hat ein solcher Satz maximal?
Wenn es etwas schwierig zu verstehen erscheint, können Sie sich genauso gut über den Vorgänger des Capset-Problems informieren – ein Kartenspiel, das in den 1970er Jahren von der Genetikerin Marsha Falco erfunden wurde.
Insgesamt gibt es in diesem Kartenspiel 81 Karten. Jede Karte hat 1 bis 3 Farbmuster. Die Farben, Formen und Schatten der Muster auf derselben Karte sind genau gleich.
Dieses Deck hat insgesamt 3 Farben, 3 Formen und 3 Farbtöne. Inklusive der Anzahl der Muster ergeben sich insgesamt 3*3*3*3=81 Karten. Die Spieler müssen einige Karten umdrehen, um die spezielle Kombination aus 3 Karten zu finden.
Wenn die spezifische Art dieser „speziellen Kombination“ in diskreter geometrischer Form ausgedrückt wird, erhalten wir das Capset-Problem.
Das Capset-Problem wurde ebenfalls in den 1970er Jahren geboren und vom Mathematiker der Universität Oxford, Ron Graham, vorgeschlagen, aber die ersten wichtigen Ergebnisse erschienen erst in den 1990er Jahren.
Im Jahr 2007 erwähnte Terence Tao in einem Blogbeitrag, dass dies sein liebstes offenes Mathematikproblem sei.
Vor der Entstehung von FunSearch wurde der bedeutendste Durchbruch beim Capset-Problem 2016 vom amerikanischen Mathematiker Jordan Ellenberg und dem niederländischen Mathematiker Dion Gijswijt vorgeschlagen.
Durch die Polynommethode reduzierten Ellenberg und Gijswijt die Obergrenze der Lösung für diese Art von Problem auf 2,756^n, wenn n>6 (die maximale Menge kann genau gefunden werden, wenn n≤6).
Auch wenn n>6 ist, beträgt die neuere Zahl der Untergrenze 2,218^n, vorgeschlagen von Fred Tyrrell, einem Doktoranden an der University of Bristol im Jahr 2022.
Aber diese Untergrenze existiert nur in der Theorie – wenn n=8, gibt es nur 496 Punkte in der größten Menge, die Menschen konstruieren können, und laut Tyrrells Schlussfolgerung sollte die Anzahl der Punkte nicht weniger als 585,7 betragen.
FunSearch hat die Setgröße auf 512 Punkte erweitert – obwohl noch immer eine Lücke zum theoretischen Wert besteht, gilt es immer noch als der bedeutendste Durchbruch zu diesem Thema seit 20 Jahren.
Gleichzeitig wurde die Untergrenze der Capset-Set-Größe von FunSearch auf 2,2202^n angehoben.
Die zweite Kategorie sind Probleme beim Online-Boxen:
Angenommen, es gibt einen Satz Standardbehälter mit einer Kapazität C und einer Folge von n Artikeln (die Größe der Artikel überschreitet C nicht). Diese Artikel kommen in einer bestimmten Reihenfolge an.
„Online“ bedeutet, dass der Bediener nicht alle Artikel im Voraus sehen kann, sondern sofort entscheiden muss, in welchen Container er die Artikel verlädt, wenn diese ankommen.
Oberstes Ziel ist es, die Anzahl der verwendeten Behälter so gering wie möglich zu halten.
Das Online-Binning-Problem hat seit den 1970er Jahren umfangreiche Forschungen hervorgerufen, und die frühesten lassen sich auf das von Gauß im Jahr 1831 untersuchte Layoutproblem zurückführen.
Nach fast 200 Jahren Forschung gibt es immer noch keine ausgereifte Theorie und effektive numerische Berechnungsmethode.
Zu den traditionell häufig verwendeten Greedy-Algorithmen gehören FirstFit und BestFit:
FirstFit bedeutet, jeden Artikel in die erste Box zu legen, die ihn aufnehmen kann. BestFit legt jeden Artikel in den Karton, der ihn aufnehmen kann und in dem der kleinste verbleibende Platz im Karton vorhanden ist.
FunSearch schlug einen neuen Algorithmus vor, der die Anzahl der in OR- und Weibull-Testdatensätzen verwendeten Container erheblich reduzierte.
Insbesondere wenn die Anzahl der Elemente im Testsatz 100.000 erreicht, verbraucht die von FunSearch gefundene Lösung nur 0,03 % mehr Container als die theoretische Untergrenze.
(Die Daten in der Tabelle unten stellen die Differenz zur theoretischen Untergrenze dar. Je kleiner die Zahl, desto besser die Leistung)
Wie wird FunSearch implementiert?
Suchen Sie nach „Programm“ statt nach „Antworten“
Im Großen und Ganzen ist der Arbeitsablauf von FunSearch ein iterativer Prozess, und der Kern besteht darin, nach Programmen zu suchen, die das Problem lösen können, und nicht in der Antwort auf die Frage selbst.
Die Suche ist genau das, was DeepMind seit AlphaGo erforscht.
Mitbegründer Shane Legg erklärte einmal in einem Interview:
Woher kam der entscheidende „Schritt 37“ bei AlphaGos Sieg über Lee Sedol? Nicht aus menschlichen Spieldaten, sondern aus einer Suche im Wahrscheinlichkeitsraum.
Aktuelle große Modelle imitieren und mischen lediglich unterschiedliche Trainingsdaten. Um echte Kreativität zu erzeugen und die aktuelle Architektur zu übertreffen, muss sie mit der Suche kombiniert werden.
Zurück zur neuesten Errungenschaft FunSearch: Es gibt eine Programmbibliothek im System. Bei jeder Iteration sucht das System nach dem ursprünglichen Programm und gibt das große Modell ein (für das Experiment wird PaLM2 verwendet, andere Codes sind ebenfalls kompatibel, sofern sie es unterstützen).
Auf dieser Basis wird das Großmodell zur Generierung neuer Programme aufgebaut und dem automatischen Auswertesystem übergeben. Das Programm mit der höchsten Punktzahl wird zur Programmbibliothek hinzugefügt, wodurch eine Selbstzirkulation realisiert wird.
Unter anderem generiert das Bewertungssystem Testfälle basierend auf Benutzerfragen und bestimmt dann, ob die Ausgabe des Kandidatenprogramms korrekt ist.
Methoden zur Bestimmung der Korrektheit umfassen je nach Komplexität die direkte Überprüfung des Ausgabewerts oder den Aufruf verwandter Funktionen.
Gleichzeitig ist das Auswertesystem mit einer fehlertoleranten Logik ausgestattet, um zu verhindern, dass Timeouts und andere Probleme den Gesamtprozess beeinträchtigen.
Abschließend gibt das System eine Gesamtbewertung basierend auf dem Verhalten des Kandidatenprogramms in diesen Testfällen ab und bietet so eine Grundlage für die Ergebnisgenerierung und nachfolgende Programmbibliotheksaktualisierungen.
Jordan Ellenberg von der University of Wisconsin-Madison, Co-Autor des Papiers, glaubt, dass ein wichtiges Merkmal von FunSearch darin besteht, dass Menschen die erfolgreichen Lösungen sehen können, die durch KI generiert werden, und daraus lernen können, was sich völlig vom vorherigen Black-Box-Modell der KI unterscheidet.
Das Spannendste für mich ist die Entwicklung neuer Modelle der Mensch-Maschine-Kollaboration, die ich hoffentlich nicht als Ersatz für menschliche Mathematiker, sondern als Kraftmultiplikator einsetzen möchte.