Spiele-KI von DeepMind lernt schnelles Programmieren

Inhaltsverzeichnis

DeepMinds Eroberungsfeldzug durch die Wissenschaften geht weiter. Vergangenes Jahr nutzte das Google gehörende Unternehmen eine Version seiner spielerischen KI AlphaZero, um eine entscheidende Berechnung der Mathematik zu beschleunigen – das vielen verschiedenen Code-Arten zugrunde liegt – und übertraf damit einen 50 Jahre alten Rekord.

Jetzt hat das Unternehmen dasselbe noch einmal geschafft, genauer gesagt gleich zweimal. Mit einer neuen Version von AlphaZero namens AlphaDev hat das in Großbritannien ansässige Unternehmen (das nach einer Fusion mit dem KI-Labor des Mutterunternehmens im April kürzlich in Google DeepMind umbenannt wurde) eine Möglichkeit gefunden, Items in einer Liste bis zu 70 Prozent schneller zu sortieren als es die beste bestehende Methode kann.

Außerdem hat es einen Weg gefunden, einen in der Kryptografie verwendeten Schlüsselalgorithmus um 30 Prozent zu beschleunigen. Diese Algorithmen gehören zu den häufigsten Bausteinen von Software. Kleine Geschwindigkeitssteigerungen können einen großen Unterschied ausmachen, Kosten senken und Energie sparen. "Das Mooresche Gesetz neigt sich dem Ende zu, und die Chips nähern sich ihren grundlegenden physikalischen Grenzen", sagt Daniel Mankowitz, ein Forscher bei Google DeepMind. "Wir müssen neue und innovative Wege finden, um die Datenverarbeitung zu optimieren."

Lob für neuen Ansatz

"Es ist ein interessanter neuer Ansatz", sagt Peter Sanders, der sich am Karlsruher Institut für Technologie (KIT) mit dem Entwurf und der Implementierung effizienter Algorithmen beschäftigt und nicht an der Arbeit beteiligt war. "Das Sortieren ist immer noch eine der am häufigsten verwendeten Subroutinen in der Informatik."

DeepMind hat seine Ergebnisse vor kurzem im Fachjournal Nature veröffentlicht. Aber die von AlphaDev entdeckten Techniken werden bereits von Millionen von Softwareentwicklern genutzt. Im Januar letztes Jahr reichte DeepMind seine neuen Sortieralgorithmen bei der Organisation ein, die für die Verwaltung von C++, einer der beliebtesten Programmiersprachen der Welt, zuständig ist. Nach einer zweimonatigen strengen unabhängigen Prüfung wurden die Algorithmen von AlphaDev in die Sprache aufgenommen. Dies war die erste Änderung der C++-Sortieralgorithmen seit mehr als einem Jahrzehnt und die erste Aktualisierung überhaupt, die einen mit KI-Hilfe entdeckten Algorithmus einbezog.

DeepMind fügte seine anderen neuen Algorithmen zu Abseil hinzu, einer quelloffenen Sammlung vorgefertigter C++-Algorithmen, die alle mit C++ Programmierenden nutzen dürfen. Diese Kryptographie-Algorithmen berechnen Hashes, die als eindeutige Identifikation für alle Arten von Daten dienen. DeepMind schätzt, dass seine neuen Algorithmen inzwischen Billionen Mal pro Tag verwendet werden.

Go, Schach, Programmieren

AlphaDev basiert auf AlphaZero, einem Modell mit Verstärkungslernen, das DeepMind trainiert hat, um Spiele wie Go und Schach zu meistern. Der Durchbruch des Unternehmens bestand darin, das Problem, einen schnelleren Algorithmus zu finden, als Spiel zu behandeln und dann die KI so zu trainieren, dass sie es gewinnt – derselbe Ansatz, den es letztes Jahr zur Beschleunigung von Matrixmultiplikationen verwendet hat.

Im Fall von AlphaDev besteht das Spiel darin, Computerbefehle 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 bestehenden Algorithmen ist. Das hört sich einfach an, aber um gut zu spielen, muss AlphaDev eine riesige Anzahl möglicher Züge durchsuchen.

DeepMind hat sich für die Hardware-nahe Programmiersprache Assembler entschieden. Nur wenige Menschen schreiben heute in Assembler. In diese Sprache wird in anderen Sprachen wie C++ geschriebener Code übersetzt, bevor er ausgeführt wird. Der Vorteil von Assembler ist, dass sich Algorithmen in fein abgestufte Schritte aufteilen lassen. Das ist ein guter Ausgangspunkt, wenn man nach Abkürzungen sucht.

AlphaDev führt einen Spielzug aus, indem es dem Algorithmus, den es gerade erstellt, eine neue Assembleranweisung hinzufügt. Zu Beginn fügte AlphaDev die Anweisungen zufällig hinzu und erzeugte Algorithmen, die nicht liefen. Mit der Zeit lernte AlphaZero, genau wie bei Brettspielen, gewinnbringende Züge zu spielen. Es fügte Anweisungen hinzu, die zu Algorithmen führten, die nicht nur funktionierten, sondern auch korrekt und schnell waren.

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

Aber auch kurze Algorithmen werden seit Jahrzehnten von Menschen untersucht und optimiert. Um ihr Konzept zu testen, begannen Mankowitz und seine Kollegen mit einem Algorithmus zum Sortieren einer Liste mit sogar nur drei Einträgen. Die beste von Menschen entwickelte Version dieses Algorithmus umfasst 18 Instruktionen.

"Wir haben ehrlich gesagt nicht erwartet, dass wir etwas Besseres erreichen würden", sagt Mankowitz. "Aber zu unserer Überraschung haben wir es geschafft, den Algorithmus schneller zu machen. Wir dachten zunächst, es handele sich um einen Fehler, aber als wir das Programm analysierten, stellten wir fest, dass AlphaDev hier tatsächlich etwas entdeckt hatte."

Mensch bleibt bei anderem Algorithmus ungeschlagen – noch

AlphaDev hat einen Weg gefunden, eine Liste mit drei Items in 17 statt 18 Anweisungen zu sortieren. Die KI hatte entdeckt, dass bestimmte Schritte übersprungen werden konnten. "Als wir uns das im Nachhinein ansahen, dachten wir: 'Wow, das ist definitv sinnvoll'", sagt Mankowitz. "Aber um so etwas [ohne AlphaDev] zu entdecken, braucht man viele Leute, die Experten in Assembler sind."

AlphaDev konnte die beste menschliche Version des Algorithmus für die Sortierung einer Liste mit vier Elementen, die 28 Anweisungen benötigt, nicht schlagen. Bei fünf Einträgen schlug es jedoch die beste menschliche Version, indem es die Anzahl der Anweisungen von 46 auf 42 reduzierte.

Das bedeutet eine erhebliche Beschleunigung. Der bestehende C++-Algorithmus zum Sortieren einer Liste mit fünf Elementen benötigte auf einem typischen Intel-Skylake-Chip etwa 6,91 Nanosekunden. Der von AlphaDev schaffte es in 2,01 Nanosekunden, also etwa 70 Prozent schneller.

Experte: Nicht überbewerten

DeepMind vergleicht die Entdeckung von AlphaDev mit einem der seltsamen, aber erfolgreichen Züge von AlphaGo in seinem Go-Match gegen Großmeister Lee Sedol im Jahr 2016. "Alle Experten sahen sich ihn an und sagten: 'Das ist nicht der richtige Zug. Das ist ein schlechter Zug'", sagt Mankowitz. "Aber tatsächlich war es der richtige Zug, 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, dass die Ergebnisse nicht überbewertet werden sollten. "Ich stimme zu, dass die Techniken des maschinellen Lernens die Programmierung zunehmend verändern, und jeder erwartet, dass KI bald in der Lage sein wird, neue, bessere Algorithmen zu entwickeln", sagt er. "Aber wir sind noch nicht ganz so weit."

Zum einen weist Sanders darauf hin, dass AlphaDev nur eine Teilmenge der in der Assemblerprogrammierung verfügbaren Anweisungen verwendet. Viele bestehende Sortieralgorithmen würden Anweisungen verwenden, die AlphaDev nicht ausprobiert hat. Das macht es schwieriger, AlphaDev mit den besten konkurrierenden Ansätzen zu vergleichen.

Tatsächlich hat AlphaDev Grenzen. Sein längster Algorithmus war 130 Anweisungen lang, um eine Liste mit bis zu fünf Elementen zu sortieren. Bei jedem Schritt wählte AlphaDev aus 297 möglichen Assembleranweisungen aus. "Bei mehr als 297 Anweisungen und "Spielen" mit einer Länge von mehr als 130 Anweisungen wurde das Lernen langsam", sagt Mankowitz.

Irgendwann wird es langsam

Das liegt daran, dass selbst bei 297 Anweisungen (oder Spielzügen) die Zahl der möglichen Algorithmen, die AlphaDev konstruieren könnte, größer ist als die Zahl der möglichen Schachspiele (10¹²⁰) und die Zahl der Atome im Universum (die vermutlich bei 10⁸⁰ liegt).

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

Sanders würde auch gerne einen umfassenderen Vergleich mit den besten von Menschen entwickelten Ideen sehen, insbesondere bei längeren Algorithmen. Das plant DeepMind nach eigenen Angaben bereits. Mankowitz möchte AlphaDev mit menschlichen Methoden kombinieren und die KI dazu bringen, auf deren Intuition aufzubauen, anstatt bei Null anzufangen.

Schließlich lassen sich vielleicht noch weitere Beschleunigungsmöglichkeiten finden. "Damit ein Mensch das tun kann, braucht er viel Fachwissen und viele Stunden – vielleicht Tage, vielleicht Wochen –, um diese Programme durchzusehen und Verbesserungen zu finden", sagt Mankowitz. "Deshalb wurde das bisher noch nicht versucht."

(vsz)