DeepMind führt einen weltbewegenden Sortieralgorithmus ein und die C++-Bibliothek ist mit der Aktualisierung beschäftigt!

Klicken Sie, um am 51CTO-Website-Inhaltsfragebogen teilzunehmen

Zusammengestellt |. Wang Ruiping, Yan Zheng

AlphaGo hat einen weiteren „kleinen Bruder“ beigetreten!

Google DeepMind hat die Alpha-Serie in den Sortieralgorithmus „gerollt“ und AlphaDev gestartet .

Es ist wie eine „geheime Entwicklungsmethode“. Durch die Verwendung von Reinforcement-Learning-KI zur Entdeckung von Sortieralgorithmen und Hashing-Algorithmen werden die von menschlichen Programmierern entwickelten Algorithmen zwangsweise um etwa 70 % bzw. 30 % beschleunigt.

Sobald die Forschungsergebnisse veröffentlicht wurden, entzündeten sie sofort den Software-Kreis! Plötzlich stieg die Laufgeschwindigkeit von Millionen von Software auf der ganzen Welt in die Höhe und übertraf direkt die jahrzehntelangen Errungenschaften von Wissenschaftlern und Ingenieuren, und die LLVM-Standard-C++-Bibliothek, die seit zehn Jahren nicht aktualisiert worden war, wurde aktualisiert.

(Quelle: Nature)

Dies ist ebenfalls eine disruptive Technologie, die nach der Fusion der beiden KI-Abteilungen von Google eingeführt wurde. Der Artikel wurde in Nature unter dem Titel „Schnellere Sortieralgorithmen entdeckt mithilfe von Deep Reinforcement Learning“ veröffentlicht. Der Erstautor des Papiers ist Daniel Mankowitz, Informatiker bei DeepMind.

1. Evolution: Der Ursprung der Sortieralgorithmen

Sortieren ist eine Methode zum Organisieren vieler Elemente in einer bestimmten Reihenfolge, zum Beispiel drei Buchstaben in alphabetischer Reihenfolge, fünf Zahlen in der Reihenfolge vom größten zum kleinsten oder Elementepaare, die Sortieren enthalten Datenbanken mit Millionen von Datensätzen.

Die Bestellmethode lässt sich bis ins zweite bis dritte Jahrhundert zurückverfolgen und entwickelt sich immer noch weiter. Zunächst sortierten Wissenschaftler die Tausenden Bücher in den Regalen der Bibliothek von Alexandria manuell in alphabetischer Reihenfolge.

Nach der industriellen Revolution wurden Selbstsortiermaschinen, Tabellierungsmaschinen, die Informationen auf Lochkarten speicherten, erfunden, um die Ergebnisse der US-Volkszählung von 1890 zu sammeln.

In den 1950er Jahren begann der Aufschwung kommerzieller Computer und es wurden sofort Sortieralgorithmen entwickelt. Geben Sie einige unsortierte Zahlen in einen Sortieralgorithmus ein und er erzeugt eine sortierte Zahlenfolge.

Viele verschiedene Sortiertechniken und Algorithmen werden immer noch überall in Codebasen verwendet, um riesige Datenmengen zu verarbeiten.​​

Nach jahrzehntelanger Forschung und Entwicklung hat sich die Effizienz dieser Sortieralgorithmen immer weiter verbessert und sie wurden von Informatikern und Programmierern anerkannt. Für die weitere Verbesserung bleiben jedoch noch erhebliche Herausforderungen bestehen.

2. Der Clou: Wie generiert man mit AlphaDev einen neuen Sortieralgorithmus?

Die Forscher nutzten AlphaDev ursprünglich, um neue Algorithmen zu generieren, um eine bestimmte Aufgabe effizient zu erledigen.

AlphaDev hat einen völlig neuen Algorithmus entwickelt und basiert nicht auf früheren Algorithmen, sodass er als originell angesehen werden kann. Dabei wird eine Zwischensprache aus Assemblercode angewendet. AlphaDev erleichtert die Erstellung effizienter Algorithmen, da die Sprache näher an binären Computeranweisungen liegt.

Konkret generiert AlphaDev jedes Mal eine Anweisung und testet dann, ob die Ausgabe korrekt ist. Außerdem werden Anforderungen im Modell festgelegt, um den kürzesten Algorithmus zu generieren.

Als AlphaDev gebeten wurde, den Sortieralgorithmus neu zu gestalten, generierte es zufällig einen neuen Sortieralgorithmus, der 70 % schneller als der bestehende Algorithmus war und fünf Daten gleichzeitig sortieren konnte. Außerdem war er beim Sortieren von 250.000 Daten 1,7 % schneller als der beste Algorithmus.

Diese Innovation wird enorme Auswirkungen auf globale Algorithmen haben, da Sortieralgorithmen in verschiedenen gängigen Softwareprogrammen weit verbreitet sind. DeepMind hat sie als Open-Source-Lösung bereitgestellt und in die Libc++-Standardbibliothek integriert.

Laut DeepMind-Forschern: „Aufgrund der großen Anzahl an Befehlskombinationen ist der scheinbar einfache Rechercheprozess äußerst schwierig.“

3 Ursprung: Den besten Algorithmus beim Spielen finden

Darüber hinaus ist AlphaDev ein fortgeschritteneres Modell basierend auf der Struktur von AlphaZero. AlphaZero war zuvor das Reinforcement-Learning-Modell von DeepMind, das Weltmeister in Go, Schach und anderen Schachspielen besiegte.

Durch dieses Experiment nutzt das neue Modell AlphaDev seine einzigartigen Vorteile beim Übergang vom Spielen zum Lösen wissenschaftlicher Probleme und von experimentellen Simulationen zu realen Anwendungen.

Forscher simulierten das Sortieren als Einzelspieler-„Zusammenbauspiel“, um AlphaDev darin zu trainieren, neue Algorithmen zu entdecken. Während jeder Spielrunde beobachtet AlphaDev den generierten Algorithmus und die in der CPU enthaltenen Informationen und wählt dann eine Anweisung aus, die dem Algorithmus hinzugefügt werden soll, um jeden Zug auszuführen.

In dem Artikel wird erwähnt, dass Assembler-Spiele sehr schwierig sind, da AlphaDev in der Lage sein muss, eine große Anzahl möglicher Befehlskombinationen effizient zu durchsuchen, um einen sortierbaren Algorithmus zu erhalten.

Die Anzahl der Befehlskombinationen ist ähnlich der Anzahl der Teilchen im Universum oder der Anzahl möglicher Zugkombinationen im Schach (10120 Partien) und Go (10700 Partien). Jeder falsche Zug macht den gesamten Algorithmus ungültig.

Das Modell gibt dann einen Algorithmus aus und vergleicht ihn mit der erwarteten Ausgabe, wobei der Agent basierend auf der Korrektheit und Latenz des Algorithmus belohnt wird.

Beim Erstellen eines Algorithmus prüft AlphaDev jedes Mal, wenn eine Anweisung eingegeben wird, die Richtigkeit, indem es den Ausgabealgorithmus mit dem erwarteten Ergebnis vergleicht (für einen Sortieralgorithmus bedeutet dies, dass er nach der Eingabe ungeordneter Zahlen korrekt sortierte Zahlen ausgeben kann).

Das Modell belohnt AlphaDev für die korrekte Reihenfolge der Zahlen und seine Effizienz. Am Ende gewann AlphaDev den Wettbewerb, indem es ein genaueres und schnelleres Programm entdeckte.

4. Algorithmusinnovation: Bewegungsbefehlssequenzen tauschen und kopieren

AlphaDev generiert nicht nur einen schnelleren Algorithmus, sondern entwickelt auch zwei Befehlssequenzen.

Konkret umfasst der von ihm generierte Sortieralgorithmus zwei neue Befehlssequenzen, Swap Move und Copy Move, und bei jeder Verwendung wird ein Befehl gespeichert. Die Forscher nennen es „AlphaDevs Swap-Move und Copy-Move“.

Dieser neuartige Ansatz erinnert an AlphaGos „Step 37“ – ein „kontraintuitives“ Schachspiel, das die Zuschauer schockierte und zur Niederlage eines legendären Schachspielers führte.

Durch den Austausch von Bewegungs- und Kopierbefehlssequenzen überspringt AlphaDev einen Schritt und erreicht das Ziel auf eine Weise, die wie ein Fehler aussieht, in Wirklichkeit aber eine Abkürzung ist. Dies bedeutet, dass AlphaDev in der Lage ist, erste Lösungen zu finden und zu versuchen, Informatikalgorithmen zu verbessern.

5. Test: Förderung und Verbesserung des Hash-Algorithmus

Nachdem Forscher einen schnelleren Sortieralgorithmus entdeckt hatten, versuchten sie, ihn auf die Förderung und Verbesserung eines anderen Informatikalgorithmus anzuwenden – des Hash-Algorithmus.

Hash-Algorithmus ist ein grundlegender Algorithmus in der Informatik und wird zum Abrufen, Speichern und Komprimieren von Daten verwendet. So wie Bibliothekare ein Klassifizierungssystem verwenden, um ein bestimmtes Buch zu finden, helfen Hashing-Algorithmen den Benutzern dabei, zu wissen, wonach sie suchen und wo sie es finden können.

Diese Algorithmen sind in der Lage, Daten für einen bestimmten Schlüssel (z. B. Benutzername „Jane Doe“) zu nehmen und sie nach einem Hash zu sortieren – und dabei die Rohdaten in eine eindeutige Zeichenfolge (z. B. 1234ghty) umzuwandeln.

Der Computer verwendet diesen Hash, um schnell Daten zum Schlüssel abzurufen, anstatt alle Daten zu durchsuchen.

Forscher wandten AlphaDev auf einen der am häufigsten verwendeten Hashing-Algorithmen in Datenstrukturen an, um einen schnelleren Algorithmus zu entdecken. Bei der Anwendung auf den 9-16-Byte-Bereich der Hash-Funktion erstellte AlphaDev einen Algorithmus, der 30 % schneller war.

Anfang des Jahres wurde der neue Hashing-Algorithmus von AlphaDev in der Open-Source-Bibliothek Abseil veröffentlicht, wodurch er Millionen von Entwicklern auf der ganzen Welt zur Verfügung steht. Schätzungen zufolge wird er mittlerweile jeden Tag Billionen Mal verwendet.

6. Nehmen Sie Fahrt auf: Machen Sie den ersten Schritt bei der Entwicklung von AGI

Durch die Optimierung von „Sortier- und Hashing-Algorithmen“ hat AlphaDev die Fähigkeit bewiesen, verschiedene praktische neue Algorithmen zu generieren.

Dies ist auch der erste Schritt von AlphaDev zur Entwicklung allgemeiner künstlicher Intelligenz (AGI)-Tools. Ähnliche KI-Tools können auch dazu beitragen, das gesamte Computer-Ökosystem zu optimieren und andere Probleme zu lösen, die der Gesellschaft zugute kommen.

Obwohl die Optimierung von Algorithmen im Low-Level-Assembly-Anweisungsraum sehr leistungsfähig ist, weist sie auch Einschränkungen auf. Derzeit untersucht das Team die Fähigkeit von AlphaDev, Algorithmen in Hochsprachen (wie C++) zu optimieren, was für Entwickler von größerem Nutzen sein wird.

Kurz gesagt besteht die Hoffnung, dass diese neuen Entdeckungen Entwickler dazu inspirieren, neue Technologien und Methoden zu entwickeln, grundlegende Algorithmen weiter zu optimieren und ein stärkeres und nachhaltigeres Computer-Ökosystem zu schaffen.

7. Open Source: Meilenstein im KI-Optimierungscode

Früher wurden Sortieralgorithmen jeden Tag Billionen Mal verwendet. Mit dem wachsenden Computerbedarf stellen die Menschen immer höhere Leistungsanforderungen an Algorithmen. Obwohl menschliche Ingenieure verschiedene Sortieralgorithmen entdeckt haben, ist es nach jahrzehntelanger Optimierung schwierig, einen Durchbruch zu erzielen, und kann die wachsende Nachfrage nicht erfüllen.

Jetzt hat AlphaDev einen schnelleren Sortieralgorithmus zum Sortieren von Daten entdeckt.

Der neue Ranking-Algorithmus ist vielseitig einsetzbar und kann zum Ranking von Online-Suchergebnissen und Social-Media-Beiträgen sowie zur Verarbeitung von Daten auf Computern und Mobiltelefonen verwendet werden.

Es lohnt sich zu feiern, dass der neue Sortieralgorithmus als Open Source in der C++-Hauptbibliothek verfügbar ist. Es wird derzeit von Millionen von Entwicklern und Unternehmen auf der ganzen Welt für Cloud Computing, Online-Shopping, Lieferkettenmanagement und mehr verwendet.

Kurz gesagt: Der Einsatz von Tools der künstlichen Intelligenz zur Optimierung von Algorithmen wird die traditionelle Art der Programmierung völlig verändern. Dies ist das erste Mal seit mehr als zehn Jahren, dass die Sortierbibliothek geändert wurde, und der vom Reinforcement-Learning-Modell entworfene Algorithmus wurde zum ersten Mal zur Sortierbibliothek hinzugefügt. Dies ist ein Meilenstein bei der Verwendung künstlicher Intelligenz Intelligenz zur Codeoptimierung.

8. Benutzer: Vielleicht ist es nur eine Spielerei

Die meisten Stimmen auf Twitter loben:

Das Erlernen grundlegender Sortieraufgaben gehört zu den Fähigkeiten, die Programmierer schon früh beherrschen. Diese Fertigkeit erhöhte die Geschwindigkeit um 70 %. Es ist spannend zu sehen, wie KI genutzt wird, um die Algorithmen und Bibliotheken, auf die wir alle angewiesen sind, deutlich zu beschleunigen.“

Einige Programmierer denken jedoch, dass dies nur eine Spielerei ist, und DeepMind übertreibt die Funktion des Algorithmus.

Erstens zählt es nur die Verzögerung des Algorithmus, anstatt die Zeit wirklich zu ändern Komplexität.

Außerdem ändert es nicht wirklich die Reihenfolge, diese Art von Operation ist in verschiedenen anderen Codebasen üblich

Referenz:

1. 06004- 9

2.https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

3.https://www.deepmind.com/blog/optimising-computer-systems- mit-more-generalized-ai-tools

4

Das obige ist der detaillierte Inhalt vonDeepMind führt einen weltbewegenden Sortieralgorithmus ein und die C++-Bibliothek ist mit der Aktualisierung beschäftigt!. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!