Heute hat die „Alpha“-Familie ein neues Mitglied hinzugefügt: AlphaDev.
Die Grundlage des gesamten Computer-Ökosystems könnte durch neue, von KI erstellte Algorithmen untergraben werden!
Es dauerte nicht lange, bis Google Brain und DeepMind zusammenkamen und so ein atemberaubendes Werk hervorbrachten.
AlphaDev kann den Sortieralgorithmus nicht nur um 70 % beschleunigen, sondern kann bei einigen Algorithmen sogar bis zu dreimal schneller sein als Menschen.
Die C++-Sortierbibliothek hat sich zum ersten Mal seit über einem Jahrzehnt geändert. KI optimiert den Code der Welt und erreicht einen neuen Meilenstein.
Aktuell wurden die neuesten Forschungsergebnisse in Nature veröffentlicht.
Papieradresse: https://www.nature.com/articles/s41586-023-06004-9
Durch Verstärkungslernen entdeckte AlphaDev einen effektiveren Algorithmus, der Jahrzehnte von direkt übertrifft Sorgfältiges Polieren durch Wissenschaftler und Ingenieure.
Jetzt ist der neue Algorithmus Teil von zwei Standard-C++-Codierungsbibliotheken und wird täglich Billionen Mal von Programmierern auf der ganzen Welt verwendet.
Einige Internetnutzer sagten, dass es endlich soweit ist und wir nun unbekanntes Terrain betreten: Künstliche Intelligenz baut künstliche Intelligenz auf!
Verstärktes Lernen überwindet den zehnjährigen Algorithmus-Engpass
Wie Vorgänger wie AlphaZero und AlphaFold hat auch AlphaDev Änderungen in einem Bereich direkt initiiert.
DeepMind-Informatiker und Erstautor des Artikels Daniel Mankowitz sagte: „Wir haben es zunächst nicht geglaubt.“
„Um ehrlich zu sein, haben wir nicht erwartet, bessere Ergebnisse zu erzielen: Das ist ein Sehr kurze Programme, und diese Art von Programmen wurde schon seit Jahrzehnten untersucht wachsen. In den letzten 50 Jahren haben sich die Menschen weiterhin auf Chip-Verbesserungen verlassen, um mithalten zu können.
Aber da Mikrochips an ihre physikalischen Grenzen stoßen, ist es wichtig, den Code zu verbessern, um die Datenverarbeitung leistungsfähiger und nachhaltiger zu machen. Dies gilt insbesondere für Algorithmen, die täglich Billionen von Codeläufen ausführen.
Heute stellte Google DeepMind in einem in Nature veröffentlichten Artikel zum ersten Mal den „Emporkömmling“ AlphaDev der Alpha-Familie vor.
AlphaDev hat einen schnelleren Sortieralgorithmus entdeckt, den Milliarden von Menschen jeden Tag nutzen, ohne es zu wissen.
Sie sind die Grundlage für alles, von Online-Suchergebnissen über Social-Media-Beiträge bis hin zur Art und Weise, wie Computer und Telefone Daten verarbeiten. Diese Algorithmen werden jeden Tag Billionen Mal ausgeführt.
Der Einsatz von KI zur Generierung besserer Algorithmen wird die Art und Weise, wie wir Computer programmieren, verändern und jeden Aspekt unserer digitalen Gesellschaft beeinflussen.
Laut Daten im Nature-Artikel kann der von AlphaZero entwickelte Algorithmus Daten dreimal schneller sortieren als Menschen.
Heute hat Google DeepMind auch den neuesten Sortieralgorithmus in der C++-Hauptbibliothek als Open-Source-Lösung bereitgestellt und macht ihn so für jedermann verfügbar. 
Open-Source-Adresse: https://reviews.llvm.org/D118029
Was ist Sortieren?
Sortieren ist eine Möglichkeit, mehrere Elemente in einer bestimmten Reihenfolge zu organisieren.
Zum Beispiel drei Buchstaben alphabetisch anordnen, fünf Zahlen vom größten zum kleinsten ordnen oder eine Datenbank mit Millionen von Datensätzen sortieren.
Sortiermethoden haben sich im Laufe der Menschheitsgeschichte weiterentwickelt. Die frühesten Beispiele stammen aus dem zweiten und dritten Jahrhundert, als Gelehrte Tausende von Büchern manuell in alphabetischer Reihenfolge in den Regalen der Bibliothek von Alexandria ordneten.
Nach der industriellen Revolution erfanden wir Maschinen, die bei der Klassifizierung helfen konnten – die Tabellierungsmaschine, die Informationen auf Lochkarten speicherte, wurde verwendet, um die Ergebnisse der US-Volkszählung von 1890 zu sammeln.
Mit dem Aufkommen kommerzieller Computer in den 1950er Jahren erschienen die ersten Sortieralgorithmen der Informatik.
Heutzutage werden in Codebasen auf der ganzen Welt viele verschiedene Sortiertechniken und Algorithmen verwendet, um große Datenmengen online zu organisieren.
Sortieralgorithmen, dh die Eingabe einer Reihe unsortierter Zahlen und die anschließende Ausgabe sortierter Zahlen
Diese Algorithmen sind zum Eckpfeiler der Informatik geworden.
Unsere Algorithmen erfordern heute von Informatikern und Programmierern jahrzehntelange Forschung und Entwicklung.
Das liegt daran, dass der bestehende Algorithmus so effizient ist und jeder Schritt zu seiner Verbesserung eine große Herausforderung darstellt.
Dieser Schwierigkeitsgrad ist so, als würde man einen neuen Weg finden, Strom zu sparen, oder eine effizientere mathematische Methode finden.
Neue Algorithmen finden
Die innovative Bedeutung von AlphaDev besteht darin, dass es bestehende Algorithmen nicht verbessert, sondern schnellere Algorithmen komplett von Grund auf entdeckt.
Darüber hinaus beginnt es tatsächlich an einem Ort, an den die meisten Menschen nicht denken – Computer-Montageanleitungen.
Montageanweisungen werden zum Erstellen von Binärcode verwendet. Obwohl Entwickler beim Schreiben von Code Hochsprachen wie C++ verwenden, müssen diese Hochsprachen in Assembleranweisungen auf „niedriger Ebene“ übersetzt werden, damit Computer sie verstehen können.
Normalerweise verwenden wir Programmiersprachen auf hoher Ebene wie C++, um Codes zu schreiben, und übersetzen sie dann mit einem Compiler in CPU-Anweisungen auf niedriger Ebene, bei denen es sich um Assembleranweisungen handelt. Der Assembler wandelt dann die Assembleranweisungen in ausführbaren Maschinencode um.
Forscher von Google DeepMind glauben, dass es auf dieser unteren Ebene viel Raum für Verbesserungen gibt und dass diese Verbesserungen in Programmiersprachen höherer Ebenen schwer zu erkennen sind .
Auf dieser niedrigeren Ebene ist der Computer sowohl im Speicher als auch im Betrieb flexibler, sodass ein paar weitere potenzielle Verbesserungen einen großen Einfluss auf Geschwindigkeit und Energie haben könnten.
Abbildung A: Ein C++-Algorithmus zum Sortieren von bis zu zwei Elementen
Abbildung B: Die entsprechende Assembly des Codes
AlphaDev: Assembly-Version von. AlphaZero
As wir Wie wir alle wissen, haben DeepMind Reinforcement-Lernmodelle wiederholt Weltmeister in Spielen wie Go, Schach und Shogi besiegt.
Und unser Protagonist dieses Mal – AlphaDev, basiert auf AlphaZero.
AlphaDev funktioniert ähnlich wie sein Vorgänger AlphaZero, das Computerdenken und Intuition kombinierte, um jeden Zug im Brettspiel auszuwählen.
Es ist nur so, dass AlphaDev nicht auswählt, wie es als nächstes weitergeht, sondern welche Anweisungen hinzugefügt werden sollen.
Um AlphaDev darin zu trainieren, neue Algorithmen zu entdecken, hat DeepMind das Sortierproblem in ein „Assembly Game“ umgewandelt.
In jeder Runde muss AlphaDev den von ihm generierten Algorithmus und die in der Zentraleinheit (CPU) enthaltenen Informationen beobachten und einen Schritt ausführen, indem es dem Algorithmus eine Anweisung hinzufügt.
Und dieses Assemblerspiel ist sehr schwierig, weil AlphaDev eine große Anzahl möglicher Befehlskombinationen effizient durchsuchen muss, um einen Algorithmus zu finden, der sortiert werden kann und schneller ist als der derzeit beste Algorithmus.
Die „möglichen Kombinationen von Anweisungen“ können sogar direkt mit der Anzahl der Teilchen im Universum oder den möglichen Kombinationen von Zügen im Schach (10^120 Spiele) und Go (10^700 Spiele) verglichen werden.
Darüber hinaus kann jede falsche Bewegung den gesamten Algorithmus ungültig machen.
Am Ende belohnt DeepMind AlphaDev basierend auf seiner Fähigkeit, die Zahlen richtig zu sortieren und wie schnell und effizient es die Sortierung abschließt, und AlphaDev muss das Spiel gewinnen, indem es ein korrektes und schnelleres Programm entdeckt.
Abbildung A: Montagespiel. Der Spieler AlphaDev nimmt den Systemstatus st als Eingabe und führt einen Schritt durch, indem er eine Assembleranweisung auswählt, die er dem bereits generierten Algorithmus hinzufügen möchte.
Abbildung B: Belohnungsberechnung. Nach jeder Bewegung wird der resultierende Algorithmus getestet und der Agent wird basierend auf seiner Korrektheit und Reaktionszeit belohnt.
Konkret wird AlphaZero bei der Durchführung eingehender Überlegungen (Beratungen) an jedem Entscheidungspunkt die nächste mögliche Aktion sowie den nächsten möglichen nächsten Schritt berücksichtigen. Arbeiten Sie wie bei einem Baumdiagramm Schritt für Schritt rückwärts, um herauszufinden, welche Aktionen am wahrscheinlichsten zum Erfolg führen.
Das Problem besteht jedoch darin, dass die erforderliche Zeit möglicherweise länger ist als das Alter des Universums, wenn alle möglichen Zweige der Situation berücksichtigt werden. Forscher nutzen also so etwas wie Intuition, um es einzugrenzen.
Bei jedem Schritt speist das Programm den aktuellen Zustand in ein neuronales Netzwerk (eine komplexe, anpassbare mathematische Funktion) ein, um das am besten geeignete Verhalten zu finden. Gleichzeitig wird das neuronale Netzwerk während des Trainingsprozesses basierend auf den Ergebnissen weiterhin aktualisiert. Manchmal wird das Verhalten mit der höchsten Bewertung bewusst nicht für die aktive Erkundung ausgewählt.
Es gibt vier Aktionen, die AlphaDev ausführen kann, darunter das Vergleichen verschiedener Werte, das Verschieben eines Werts an eine andere Stelle oder das Springen zu einem anderen Teil des Programms.
Versuchen Sie nach jedem Schritt, eine Reihe von Listen zu sortieren und erhalten Sie eine Belohnung basierend auf der Anzahl der Werte in der richtig sortierten Liste.
Und so weiter und so fort, bis die gesamte Liste sortiert ist oder die Programmlängenbeschränkung erreicht ist und ein neues Programm von vorne beginnt.
C++-Laufgeschwindigkeit um 70 % erhöht
AlphaDev hat einen neuen Sortieralgorithmus entdeckt und erhebliche Verbesserungen an der LLVM libc++-Sortierbibliothek vorgenommen.
Bei kürzeren Sequenzen beträgt die Beschleunigung 70 %, während sie bei Sequenzen mit mehr als 250.000 Elementen nur etwa 1,7 % beträgt.
Forscher konzentrieren sich auf die Verbesserung von Sequenzsortierungsalgorithmen mit kürzeren 3-5 Elementen.
Diese Algorithmen gehören zu den am weitesten verbreiteten, da sie im Rahmen einer größeren Sortierfunktion oft mehrfach aufgerufen werden.
Durch die Verbesserung dieser Algorithmen kann die Gesamtgeschwindigkeit beim Sortieren einer beliebigen Anzahl von Artikeln verbessert werden.
Um den neuen Sortieralgorithmus für jedermann verfügbar zu machen, haben die Forscher ihn auch rückentwickelt und in C++ übersetzt, eine Programmiersprache, die am häufigsten von „Programmierern“ verwendet wird.
Derzeit sind diese Algorithmen jetzt in der LLVM libc++-Standardsortierbibliothek verfügbar.
Hash-Funktionseffizienz um 30 % erhöht
Nachdem DeepMind einen schnelleren Sortieralgorithmus entdeckt hatte, testete DeepMind, ob AlphaDev einen anderen Informatikalgorithmus – Hashing – verallgemeinern und verbessern konnte.
Hashing ist ein grundlegender Algorithmus in der Informatik und wird zum Abrufen, Speichern und Komprimieren von Daten verwendet. So wie Bibliothekare ein Klassifizierungssystem verwenden, um bestimmte Bücher zu finden, helfen Hashing-Algorithmen den Benutzern dabei, zu wissen, wonach sie genau suchen und wo.
Diese Algorithmen hashen einen bestimmten Schlüssel (z. B. den Benutzernamen „Jane Doe“), das heißt, sie konvertieren die Originaldaten in eine eindeutige Zeichenfolge (z. B. 1234ghfty). Der Computer verwendet dann diesen Hash-Wert, um schnell Daten zum Schlüssel abzurufen, anstatt alle Daten zu durchsuchen.
Die Ergebnisse zeigen, dass der von AlphaDev entdeckte Algorithmus 30 % schneller ist als herkömmliche Algorithmen, wenn er auf den 9- bis 16-Byte-Bereich der Hash-Funktion angewendet wird.
Jetzt hat DeepMind auch den neuen Hashing-Algorithmus in der Open-Source-Abseil-Bibliothek veröffentlicht. Es versteht sich, dass dieser Algorithmus voraussichtlich jeden Tag Billionen Mal verwendet wird.
Zwei neue Strategien: „Swap-Move“ und „Copy-Move“
AlphaDev hat nicht nur schnellere Algorithmen entdeckt, sondern auch neue Methoden entdeckt.
Sein Sortieralgorithmus enthält eine neue Folge von Anweisungen, von denen bei jeder Anwendung eine gespeichert wird. Dies könnte enorme Auswirkungen haben, da diese Algorithmen jeden Tag Billionen Mal verwendet werden.
Forscher nennen es „AlphaDev Swap Move“ und „AlphaDev Copy Move“.
Die neueste Methode erinnert an AlphaGos schockierenden „Schritt 37“.
Im Mensch-Maschine-Krieg 2016 spielte AlphaGo ein Schachspiel, das der menschlichen Intuition zuwiderlief, einen einfachen Schulterangriff und besiegte den legendären Go-Spieler Lee Sedol.
Bei beiden Strategien überspringt AlphaDev einen Schritt, um Projekte auf eine Weise zu verbinden, die falsch aussieht, aber tatsächlich eine Abkürzung ist.
Dies zeigt die Fähigkeit von AlphaDev, originelle Lösungen zu entdecken und die Art und Weise, wie wir über die Verbesserung von Informatikalgorithmen nachdenken, in Frage zu stellen.
Wie in der Abbildung unten gezeigt, hat die ursprüngliche sort3-Implementierung min(A, B, C) Mit AlphaDev Swap Move hat AlphaDev festgestellt, dass Sie nur min(A, B) benötigen.
Für ein weiteres Beispiel verwendet die ursprüngliche Implementierung den größeren Sortieralgorithmus in max(B, min(A,C, D)), um 8 Elemente zu sortieren.
AlphaDev hat herausgefunden, dass die Verwendung seiner „Swap- und Copy-Moves“ nur max(B, min(A, C)) erfordert.
Optimierung des Codes der Welt, ein Algorithmus nach dem anderen
Durch die Optimierung und Einführung verbesserter Sortier- und Hashing-Algorithmen, die von Entwicklern auf der ganzen Welt verwendet werden, hat AlphaDev bewiesen, dass es in der Lage ist, die Welt zu verallgemeinern und zu entdecken -Klasse neuer Algorithmus.
Google DeepMind glaubt, dass AlphaDev ein Schritt in Richtung Entwicklung von AGI-Tools ist, die dabei helfen, das gesamte Computer-Ökosystem zu optimieren und andere Probleme zu lösen, die der Gesellschaft zugute kommen.
Allerdings geben Forscher auch zu, dass AlphaDev derzeit sehr gut in der Lage ist, Montageanweisungen auf niedriger Ebene zu optimieren, es gibt jedoch auch Einschränkungen bei der Entwicklung des Algorithmus.
Um es für Entwickler benutzerfreundlicher zu machen, wird die Fähigkeit von AlphaDev untersucht, Algorithmen in Hochsprachen (wie C++) zu optimieren.
Die neuen Entdeckungen von AlphaDev, wie „AlphaDev Swap Move“ und „AlphaDev Copy Move“, zeigen nicht nur, dass es Algorithmen verbessern, sondern auch neue Lösungen finden kann.
Die Forscher hoffen, dass diese Erkenntnisse Forscher und Entwickler dazu inspirieren werden, Technologien und Methoden zu entwickeln, um die zugrunde liegenden Algorithmen weiter zu optimieren und so ein stärkeres und nachhaltigeres Computer-Ökosystem zu schaffen.
Heiße Kommentare von Internetnutzern
NVIDIA-Wissenschaftler Jim Fan hat eine ausführliche Zusammenfassung von AlphaDev erstellt:
Der Sortieralgorithmus ist die Grundlage aller wichtigen Software. AlphaDev von DeepMind beschleunigt das Sortieren kleiner Sequenzen (3–5 Elemente) um 70 %. Wichtige Punkte:
- Der Haupt-RL-Algorithmus basiert auf AlphaZero, das ursprünglich Go, Schach und Shogi spielte. Die gleiche Idee gilt für Suchprogramme!
- Die Forscher haben nicht den C-Code optimiert, sondern den Assembler-Code. Dies ist eine bewusste Entscheidung, auf die unterste Ebene zu gehen und jede gespeicherte Anweisung zu komprimieren.
– Der Assembler-Code wurde dann in C++ rückentwickelt und in LLVM als Open Source bereitgestellt.
- Auch wenn das Repräsentationsnetzwerk Transformer verwendet, handelt es sich nicht um ein Basismodell. Der gesamte Prozess funktioniert nur zum Sortieren und muss für andere Aufgaben wie Hashing neu trainiert werden.
Ein weiterer wichtiger Meilenstein in der Algorithmenentdeckung mit ML
AlphaDev ist eine bahnbrechende künstliche Intelligenz von DeepMind, die zentrale Algorithmen der Informatik innoviert. Es werden Sequenzierungsmethoden neu konzipiert, um kurze Sequenzen um 70 % schneller zu machen. Sogar die Erkennungsgeschwindigkeit von Hashing-Algorithmen wird um 30 % erhöht. Reinforcement Learning verändert die Algorithmenlandschaft!
Einige Internetnutzer sagten, dass wir, obwohl wir von Sprachmodellen begeistert sind, die Erfolgsgeschichten anderer Deep-Learning-Algorithmen nicht vergessen sollten: AlphaZero, AlphaFold und jetzt AlphaDev.
Das obige ist der detaillierte Inhalt vonGoogle DeepMind bricht das Zehn-Jahres-Algorithmus-Siegel und AlphaDev gibt ein atemberaubendes Debüt und untergräbt die Landschaft der menschlichen Algorithmen!. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
