Extreme Kombinatorik: Chatbots können offene mathematische Probleme lösen
Forschern im Bereich der künstlichen Intelligenz (KI) ist es nach eigenen Angaben gelungen, mit Sprachmodellen wie ChatGPT bislang offene wissenschaftliche Probleme zu lösen. Durch die Kopplung eines vortrainierten Modells mit einem systematischen Evaluator seien Fortschritte im Bereich der extremen Kombinatorik und bei Optimierungsproblemen erzielt worden, berichteten Forscher von Google Deepmind in London zusammen mit Wissenschaftlern aus den USA und Frankreich im Fachmagazin Nature(öffnet im neuen Fenster). Solche Lösungen könnten beispielsweise beim effizienten Betrieb von Rechenzentren zum Einsatz kommen.
"Als wir mit dem Projekt begannen, gab es keine Anzeichen dafür, dass es etwas tatsächlich Neues hervorbringen würde", sagte Pushmeet Kohli, Leiter der wissenschaftlichen KI-Forschung bei Deepmind nach Angaben des Guardian(öffnet im neuen Fenster). "Soweit wir wissen, ist dies das erste Mal, dass eine echte neue wissenschaftliche Entdeckung durch ein großes Sprachmodell gemacht wurde", ergänzte Kohli.
Evaluator entwickelt
Für das Verfahren entwickelten die Forscher den Evaluator Funsearch, was für "Searching in the function space" ("Suche im Funktionenraum") steht. Funsearch soll dem 33-seitigen Papier (PDF)(öffnet im neuen Fenster) zufolge vor sogenannten Konfabulationen oder Halluzinationen sowie falschen Ideen schützen. "Funsearch iteriert über diese beiden Komponenten und entwickelt aus anfänglich schwach bewerteten Programmen solche mit hoher Punktzahl, die neues Wissen entdecken", heißt es weiter.
Für dieses Verfahren würden mehrere Bestandteile kombiniert. Zunächst würden die besten Programme ausgewählt und in Prompts für das Sprachmodell (Large Language Model/LLM) zurückgegeben, um die Programme zu verbessern. Diese Verfahren werde als "Best-Shot-Prompting" bezeichnet. "Zweitens starten wir mit einem Programm in Form eines Gerüsts (das Standardcode und möglicherweise eine vorherige Struktur des Problems enthält) und entwickeln nur den Teil weiter, der die kritische Programmlogik steuert", schreiben die Forscher.
Drittens nutzten die Entwickler einen großen Pool unterschiedlicher Programme, "indem wir eine inselbasierte Evolutionsmethode verwenden, die die Exploration fördert und lokale Optima vermeidet". Zu guter Letzt nutzten sie demnach "die hochgradige Parallelität von Funsearch, um es asynchron zu skalieren und so den Anwendungsbereich dieses Ansatzes erheblich zu erweitern". Das soll auch die Gesamtkosten der Experimente niedrig halten.
Kombinatorik und Optimierungsprobleme
Beispiele für neue Lösungen gab es im Bereich des sogenannten Cap-Set-Problems(öffnet im neuen Fenster) und des Behälterproblems(öffnet im neuen Fenster). Beim Cap-Set-Problem geht es darum, die größte Punktmenge in einem n-dimensionalen Raum zu finden, bei der keine drei Punkte eine gerade Linie bilden. Dem Papier zufolge hat Funsearch bei n = 8 mehr Lösungen (512 statt 496) gefunden, als zuvor bekannt waren. Eine Brute-Force-Lösung scheitere, da der Suchraum schnell astronomisch groß werde und für n = 8 schon bei n hoch 1.600 liege.
Bei dem Behälterproblem geht es darum, eine Menge von Gegenständen unterschiedlicher Größe in die kleinste Anzahl von Behältern fester Größe zu packen. Das Problem finde in vielen Bereichen Anwendung, vom Schneiden von Materialien bis hin zur Planung von Aufträgen in Rechenzentren. Dabei wird zwischen Offline- und Onlinevarianten unterschieden. Bei der Onlinevariante sind die Daten nicht vorab bekannt.
Bei der Lösung des Problems kommen die Verfahren First Fit und Best Fit zum Einsatz. Bei First Fit wird der Gegenstand in den ersten Behälter gepackt, in den er noch passt. Best Fit packt den Gegenstand hingegen in den Behälter, in dem noch am wenigsten Platz übrig ist. Funsearch fand dabei Heuristiken, die die Behälter effizienter als bestehende Datensätze nutzten.
Dabei griff die KI nur dann zum Best-Fit-Verfahren, wenn nur noch sehr wenig Platz in dem Behälter übrig blieb. Sonst wurde ein anderer Behälter gewählt. Damit wird verhindert, dass Lücken bestehen bleiben, die nicht mehr gefüllt werden können. Nach Ansicht der Forscher demonstriert dieses Beispiel die Möglichkeit der KI, für die Lösung von solchen Optimierungsproblemen in der Praxis eingesetzt zu werden.
- Anzeige Hier geht es zu Künstliche Intelligenz: Wissensverarbeitung bei Amazon Wenn Sie auf diesen Link klicken und darüber einkaufen, erhält Golem eine kleine Provision. Dies ändert nichts am Preis der Artikel.