Das Spiel von Google DeepMind

Die KI-generierten Algorithmen werden bereits von Millionen Entwicklern genutzt.

Die Entdeckungsserie von DeepMind in der Grundlageninformatik geht weiter. Letztes Jahr nutzte das Unternehmen eine Version seiner Spiele-KI AlphaZero, um neue Wege zu finden, um die Berechnung eines entscheidenden Teils der Mathematik im Herzen vieler verschiedener Arten von Code zu beschleunigen, und brach damit einen 50 Jahre alten Rekord.

Jetzt hat es den gleichen Trick erneut angewendet – und zwar zweimal. Mithilfe einer neuen Version von AlphaZero namens AlphaDev hat das in Großbritannien ansässige Unternehmen (das kürzlich nach einer Fusion mit dem KI-Labor seines Schwesterunternehmens im April in Google DeepMind umbenannt wurde) eine Möglichkeit entdeckt, Elemente in einer Liste bis zu 70 % schneller als die besten vorhandenen zu sortieren Methode.

Es wurde auch eine Möglichkeit gefunden, einen in der Kryptographie verwendeten Schlüsselalgorithmus um 30 % zu beschleunigen. Diese Algorithmen gehören zu den häufigsten Bausteinen in Software. Kleine Beschleunigungen können einen großen Unterschied machen, indem sie Kosten senken und Energie sparen.

Die neue Version von AlphaZero hat einen schnelleren Weg zur Matrixmultiplikation entdeckt, einem Kernproblem in der Informatik, das Tausende alltäglicher Computeraufgaben betrifft.

„Das Mooresche Gesetz geht zu Ende, wenn Chips an ihre grundlegenden physikalischen Grenzen stoßen“, sagt Daniel Mankowitz, Forscher bei Google DeepMind. „Wir müssen neue und innovative Wege zur Optimierung der Datenverarbeitung finden.“

„Es ist ein interessanter neuer Ansatz“, sagt Peter Sanders, der am Karlsruher Institut für Technologie in Deutschland den Entwurf und die Implementierung effizienter Algorithmen untersucht und nicht an der Arbeit beteiligt war. „Sortieren ist immer noch eines der am weitesten verbreiteten Unterprogramme in der Informatik“, sagt er.

DeepMind hat seine Ergebnisse heute in Nature veröffentlicht. Aber die Techniken, die AlphaDev entdeckt hat, werden bereits von Millionen von Softwareentwicklern genutzt. Im Januar 2022 reichte DeepMind seine neuen Sortieralgorithmen bei der Organisation ein, die C++, eine der beliebtesten Programmiersprachen der Welt, verwaltet, und nach zwei Monaten strenger unabhängiger Prüfung wurden die Algorithmen von AlphaDev der Sprache hinzugefügt. Dies war die erste Änderung an den Sortieralgorithmen von C++ seit mehr als einem Jahrzehnt und das erste Update überhaupt, das einen mithilfe von KI entdeckten Algorithmus beinhaltete.

DeepMind hat seine anderen neuen Algorithmen zu Abseil hinzugefügt, einer Open-Source-Sammlung vorgefertigter C++-Algorithmen, die von jedem verwendet werden können, der mit C++ programmiert. Diese Kryptografiealgorithmen berechnen Zahlen, sogenannte Hashes, die als eindeutige IDs für jede Art von Daten verwendet werden können. DeepMind schätzt, dass seine neuen Algorithmen mittlerweile Billionen Mal am Tag genutzt werden.

AlphaDev basiert auf AlphaZero, dem Reinforcement-Learning-Modell, das DeepMind trainiert hat, um Spiele wie Go und Schach zu meistern. Der Durchbruch von DeepMind bestand darin, das Problem, einen schnelleren Algorithmus zu finden, wie ein Spiel zu behandeln und ihn dann von seiner KI gewinnen zu lassen – dieselbe Methode, mit der das Unternehmen letztes Jahr in der Forschung Berechnungen beschleunigte.

Im Fall von AlphaDev besteht das Spiel darin, Computeranweisungen auszuwählen und sie so anzuordnen, dass die resultierenden Codezeilen einen Algorithmus bilden. AlphaDev gewinnt das Spiel, wenn der Algorithmus sowohl korrekt als auch schneller als die vorhandenen ist. Es klingt einfach, aber um gut zu spielen, muss AlphaDev eine astronomische Anzahl möglicher Züge durchsuchen.

DeepMind entschied sich für die Arbeit mit Assembler, einer Programmiersprache, mit der spezifische Anweisungen zum Verschieben von Zahlen auf einem Computerchip gegeben werden können. Nur wenige Menschen schreiben in Assemblerform; Es ist die Sprache, in die in Sprachen wie C++ geschriebener Code übersetzt wird, bevor er ausgeführt wird. Der Vorteil der Assemblierung besteht darin, dass sie die Unterteilung von Algorithmen in feinkörnige Schritte ermöglicht – ein guter Ausgangspunkt, wenn Sie nach Abkürzungen suchen.

Computerchips verfügen über verschiedene Steckplätze, in denen Zahlen eingegeben und verarbeitet werden. Assembly enthält grundlegende Anweisungen zum Manipulieren dessen, was sich in diesen Slots befindet, wie mov(A,B), das einen Computer anweist, die Zahl in Slot A nach Slot B zu verschieben, und cmp(A,B), das den Computer anweist, zu prüfen, ob Was sich in Steckplatz A befindet, ist kleiner, gleich oder größer als das, was sich in Steckplatz B befindet. Lange Sequenzen solcher Anweisungen können alles ausführen, was Computer tun.

Jahrzehntelang haben Programmierer kritische Systeme in C und C++ geschrieben. Jetzt wenden sie sich an Rust.

AlphaDev führt einen Zug im Spiel aus, indem es dem Algorithmus, den es erstellt, eine neue Assembleranweisung hinzufügt. Zunächst fügte AlphaDev zufällig Anweisungen hinzu und generierte Algorithmen, die nicht ausgeführt werden konnten. Im Laufe der Zeit lernte es, genau wie AlphaZero bei Brettspielen, Gewinnzüge zu spielen. Es fügte Anweisungen hinzu, die zu Algorithmen führten, die nicht nur liefen, sondern auch korrekt und schnell waren.

DeepMind konzentrierte sich auf Algorithmen zum Sortieren kurzer Listen mit drei bis fünf Elementen. Solche Algorithmen werden in Programmen, die längere Listen sortieren, immer wieder aufgerufen. Beschleunigungen in diesen kurzen Algorithmen werden daher einen kumulativen Folgeeffekt haben.

Aber auch kurze Algorithmen werden seit Jahrzehnten von Menschen erforscht und optimiert. Als Machbarkeitsnachweis begannen Mankowitz und seine Kollegen mit einem Algorithmus zum Sortieren einer Liste mit drei Elementen. Die beste von Menschen entwickelte Version dieses Algorithmus umfasst 18 Anweisungen. Sie glaubten nicht, dass sie es verbessern könnten.

„Wir haben ehrlich gesagt nicht damit gerechnet, etwas Besseres zu erreichen“, sagt er. „Aber zu unserer Überraschung haben wir es geschafft, es schneller zu machen. Zuerst dachten wir, das sei ein Fehler oder ein Bug oder so, aber als wir das Programm analysierten, stellten wir fest, dass AlphaDev tatsächlich etwas entdeckt hatte.“

AlphaDev hat eine Möglichkeit gefunden, eine Liste mit drei Elementen in 17 statt 18 Anweisungen zu sortieren. Dabei wurde festgestellt, dass bestimmte Schritte übersprungen werden konnten. „Als wir es uns anschließend ansahen, dachten wir: ‚Wow, das macht auf jeden Fall Sinn‘“, sagt Mankowitz. „Aber um so etwas [ohne AlphaDev] zu entdecken, braucht es Leute, die Experten in Assemblersprache sind.“

AlphaDev konnte die beste menschliche Version des Algorithmus zum Sortieren einer Liste mit vier Elementen, die 28 Anweisungen erfordert, nicht schlagen. Aber es schlug die beste menschliche Version in fünf Punkten und reduzierte die Anzahl der Anweisungen von 46 auf 42.

Das kommt einer deutlichen Beschleunigung gleich. Der vorhandene C++-Algorithmus zum Sortieren einer Liste mit fünf Elementen benötigte auf einem typischen Intel Skylake-Chip etwa 6,91 Nanosekunden. AlphaDev benötigte 2,01 Nanosekunden, rund 70 % schneller.

Ein Jahr nachdem es Biologen überrascht hatte, hat AlphaFold die Arbeitsweise von Forschern verändert und DeepMind auf einen neuen Kurs gebracht.

DeepMind vergleicht AlphaDevs Entdeckung mit einem der seltsamen, aber siegreichen Züge von AlphaGo in seinem Go-Match gegen Großmeister Lee Sedol im Jahr 2016. „Alle Experten haben sich diesen Zug angesehen und gesagt: ‚Das ist nicht das Richtige. Das ist ein schlechter Schachzug.‘ ,‘“, sagt Mankowitz. „Aber eigentlich war es der richtige Schachzug, und AlphaGo hat am Ende nicht nur das Spiel gewonnen, sondern auch die Strategien beeinflusst, die professionelle Go-Spieler zu verwenden begannen.“

Sanders ist beeindruckt, glaubt aber nicht, dass die Ergebnisse überbewertet werden sollten. „Ich stimme zu, dass Techniken des maschinellen Lernens die Programmierung zunehmend verändern und jeder erwartet, dass KIs bald in der Lage sein werden, neue, bessere Algorithmen zu erfinden“, sagt er. „Aber wir sind noch nicht ganz am Ziel.“

Zum einen weist Sanders darauf hin, dass AlphaDev nur einen Teil der in Assembler verfügbaren Anweisungen verwendet. Viele bestehende Sortieralgorithmen verwenden Anweisungen, die AlphaDev nicht ausprobiert habe, sagt er. Dies macht es schwieriger, AlphaDev mit den besten Konkurrenzansätzen zu vergleichen.

Es stimmt, dass AlphaDev seine Grenzen hat. Der längste von ihm erstellte Algorithmus umfasste 130 Anweisungen zum Sortieren einer Liste mit bis zu fünf Elementen. Bei jedem Schritt wählte AlphaDev aus 297 möglichen Montageanweisungen (von vielen weiteren) aus. „Abgesehen von 297 Anleitungen und Montagespielen mit mehr als 130 Anleitungen wurde das Lernen langsam“, sagt Mankowitz.

Denn selbst mit 297 Anweisungen (oder Spielzügen) ist die Anzahl möglicher Algorithmen, die AlphaDev konstruieren könnte, größer als die mögliche Anzahl an Schachpartien (10120) und die Anzahl an Atomen im Universum (ca. 1080).

Für längere Algorithmen plant das Team, AlphaDev so anzupassen, dass es mit C++-Anweisungen statt mit Assembler arbeitet. Mit einer weniger feinkörnigen Steuerung könnte AlphaDev bestimmte Verknüpfungen übersehen, aber der Ansatz wäre auf eine breitere Palette von Algorithmen anwendbar.

Sanders würde sich außerdem einen ausführlicheren Vergleich mit den besten von Menschen entwickelten Ansätzen wünschen, insbesondere für längere Algorithmen. DeepMind sagt, das sei Teil seines Plans. Mankowitz möchte AlphaDev mit den besten von Menschen entwickelten Methoden kombinieren und die KI dazu bringen, auf der menschlichen Intuition aufzubauen, anstatt bei Null anzufangen.

Schließlich könnte es noch weitere Beschleunigungen geben. „Damit ein Mensch dies tun kann, sind erhebliche Fachkenntnisse und eine Menge Stunden – vielleicht Tage, vielleicht Wochen – erforderlich, um diese Programme durchzusehen und Verbesserungen zu identifizieren“, sagt Mankowitz. „Deshalb wurde es noch nie zuvor versucht.“

„Ich habe plötzlich meine Meinung darüber geändert, ob diese Dinger intelligenter sein werden als wir.“

Hinton wird am Mittwoch bei EmTech Digital sprechen.

ChatGPT hat Spekulationen über künstliche allgemeine Intelligenz ausgelöst. Aber die nächste echte Phase der KI wird in bestimmten Bereichen und Kontexten stattfinden.

Sehen Sie, wie Hinton mit Will Douglas Heaven, dem leitenden Redakteur für KI bei MIT Technology Review, bei EmTech Digital spricht.

Entdecken Sie Sonderangebote, Top-Storys, bevorstehende Veranstaltungen und mehr.

Vielen Dank für die Übermittlung Ihrer E-Mail!

Es sieht so aus, als wäre etwas schief gelaufen.

Beim Speichern Ihrer Einstellungen ist ein Problem aufgetreten. Versuchen Sie, diese Seite zu aktualisieren und sie noch einmal zu aktualisieren. Wenn Sie diese Nachricht weiterhin erhalten, wenden Sie sich an [email protected] mit einer Liste der Newsletter, die Sie erhalten möchten.