Reproduzieren Sie den magischen Touch von AlphaGo von damals! Die neue KI von DeepMind hat einen um 70 % schnelleren Sortieralgorithmus entdeckt und die C++-Bibliothek, die seit zehn Jahren nicht aktualisiert wurde, wurde aktualisiert

DeepMind ist erneut in der Natur aufgetaucht und hat großartige Ergebnisse erzielt!

Diesmal haben sie eine weitere KI für verstärkendes Lernen entwickelt und damit neue Durchbrüche bei den beiden grundlegendsten Algorithmen im Computerbereich erzielt:

Einer ist der Sortieralgorithmus, der eine neue Implementierung entdeckt hat, die die Geschwindigkeit um bis zu 70 erhöhen kann %;

Ein anderer ist der Hashing-Algorithmus, der ebenfalls einen neuen Weg gefunden hat, die Geschwindigkeit um 30 % zu erhöhen.

Darüber hinaus heißt die von dieser KI verwendete Methode „Wiederherstellung der damaligen magischen Berührung von AlphaGo“. Dies ist die Zeit, die die Intuition zu verletzen schien, tatsächlich aber den menschlichen Meister Lee Sedol besiegte ein Schlag.

Sobald die Nachricht herauskam, explodierte sofort der akademische Kreis. Einige Internetnutzer riefen:

Ich hätte nicht erwartet, dass ein so alter und grundlegender Algorithmus weiter verbessert werden könnte.

Und genau aufgrund dieser neuesten Errungenschaft wurde die LLVM-Standard-C++-Bibliothek, die seit zehn Jahren nicht aktualisiert wurde, aktualisiert, und Milliarden von Menschen werden davon profitieren.

Denn unabhängig davon, ob es sich um Sortierung oder Hashing handelt, können ihre Anwendungsszenarien in verschiedenen Szenarien vom Online-Shopping über Cloud Computing bis hin zum Lieferkettenmanagement usw. verwendet werden und werden täglich hunderte Millionen Mal aufgerufen!

Aber wie DeepMind sagte:

Seien Sie nicht zu aufgeregt, die Leistungsfähigkeit der KI zur Verbesserung der Codeeffizienz hat gerade erst begonnen.

Der „Emporkömmling“ der Alpha-Familie entdeckt einen schnelleren Sortieralgorithmus

Diese KI heißt AlphaDev, gehört zum „Emporkömmling“ der Alpha-Familie und basiert auf AlphaZero (der Schach-KI, die besiegt hat). Weltmeister 2017).

Seine Entdeckung basiert nicht auf vorhandenen Algorithmen, sondern beginnt mit den Montageanweisungen der untersten Ebene.

DeepMind-Forscher haben dafür ein Einzelspieler-„Assembly“-Spiel entwickelt:

Solange Sie die entsprechenden Anweisungen suchen und auswählen können (Prozess A in der Abbildung unten), die Daten korrekt und schnell anordnen (Prozess B in der Abbildung unten). Abbildung unten) können Sie Belohnungen erhalten.

Aber die Herausforderung dieses Spiels liegt nicht nur in der Größe des Suchraums (die Anzahl der kombinierbaren Anweisungen entspricht der Anzahl der Teilchen im Universum), sondern auch in der Art der Belohnung Funktion, da eine falsche Anweisung den gesamten Algorithmus zum Scheitern bringen kann. Ungültig.

AlphaDev besteht aus zwei Kernkomponenten: Lernalgorithmus und Darstellungsfunktion.

Unter diesen basiert der Lernalgorithmus hauptsächlich auf dem leistungsstarken AlphaZero, der DRL- und Zufallssuchoptimierungsalgorithmen kombinieren kann, um umfangreiche Befehlssuchen durchzuführen. Die Hauptdarstellungsfunktion basiert auf Transformer, der die zugrunde liegende Struktur des Assemblers erfassen kann. und als spezielle Sequenz ausgedrückt.

Während AlphaDev weiterhin gegen Monster kämpft und Upgrades durchführt, werden die Forscher auch die Anzahl der Schritte, die es ausführen kann, und die Länge der zu sortierenden Sequenz begrenzen.

Schließlich hat AlphaDev einen neuen Sortieralgorithmus entdeckt:

Wenn die Sequenz kurz ist, kann sie die Geschwindigkeit im Vergleich zum menschlichen Basissortieralgorithmus um 70 % erhöhen; wenn die Sequenzlänge 25.000 Elemente überschreitet, erhöht sie sich um 1,7 %. .

Kurzsequenzsortierung ist in der Praxis weit verbreitet, insbesondere als wichtiger Bestandteil größerer Sortierfunktionen und wird häufig aufgerufen. Solange kurze Sequenzen verbessert werden, kann die Sortiergeschwindigkeit aller Sequenzen verbessert werden. )

Konkret liegt die Innovation dieses Algorithmus hauptsächlich in zwei Befehlssequenzen:

(1) AlphaDev Swap Move (Swap Move)
(2) AlphaDev Copy Move (Copy Move)

Wie in der Abbildung unten gezeigt, auf Auf der linken Seite wird die ursprüngliche sort3-Implementierung von min(A,B,C) verwendet. Die rechte Seite erfolgt über „AlphaDev Swap Move“, was nur die Implementierung von min(A,B) erfordert. Es kann festgestellt werden, dass ein Schritt der Anweisung weggelassen werden kann und nur die Mindestwerte von A und B berechnet werden müssen.

Der Autor sagte, dass diese neuartige Methode an AlphaGos „Move 37“ erinnert – eine kontraintuitive Methode, die den legendären Go-Spieler Lee Sedol direkt besiegte und das Publikum schockierte.

In ähnlicher Weise überspringt AlphaDev einen Schritt, indem es Züge austauscht und kopiert und so das Ziel auf eine Weise erreicht, die falsch erscheint, in Wirklichkeit aber eine Abkürzung ist.

Wie in der Abbildung unten gezeigt, verwendet AlphaDev im Algorithmus zum Sortieren von 8 Elementen auch „AlphaDev Copy Move“, um das komplexere Max in der ursprünglichen Implementierung durch Max (B, Min (A, C)) (B, min (A, C, D)) Befehl, und die Gesamtzahl der Befehle des gesamten Algorithmus wird ebenfalls um einen Schritt reduziert.

Nachdem der Autor einen schnelleren Sortieralgorithmus entdeckt hatte, versuchte er auch den Hash-Algorithmus mit AlphaDev, um seine Vielseitigkeit zu beweisen.

Die Ergebnisse enttäuschten nicht, AlphaDev erreichte auch eine Geschwindigkeitssteigerung von 30 % im Längenbereich von 9-16 Bytes.

Wie den Sortieralgorithmus haben sie die neue Methode in die Abseil-Bibliothek integriert, die nun Millionen von Entwicklern auf der ganzen Welt zur Verfügung steht.

Abschließend stellte der Autor fest, dass die Implementierung zweier neuer Algorithmen zeigt, dass AlphaDev über eine starke Fähigkeit verfügt, originelle Lösungen zu entdecken, und dass wir weiter darüber nachdenken werden, wie grundlegende Algorithmen im Computerbereich verbessert werden können.

Aufgrund der Einschränkungen der in dieser Studie verwendeten Assemblersprache planen sie jedoch als nächstes, die Fähigkeit von AlphaDev auszuprobieren, Algorithmen in Hochsprachen (wie C++) zu optimieren.

Netizen: Ganz zu schweigen von der Entdeckung eines neuen Sortieralgorithmus

Viele Menschen freuen sich sehr über diese Errungenschaft.

Wie dieser Internetnutzer sagte:

Was kann Verstärkungslernen noch bewirken, nachdem AlphaGo die Welt in Erstaunen versetzt hat? Kann man etwas von praktischer Bedeutung tun? Das ist die Antwort.

Aber dieses Mal wiesen viele Leute darauf hin, dass DeepMind offenbar im Verdacht stand, den Titel zu übertreiben.

Es berechnet die Algorithmusverzögerung, nicht die Zeitkomplexität im herkömmlichen Sinne. Wenn die Zeitkomplexität tatsächlich berechnet wird, sehen die Daten möglicherweise nicht gut aus.

Die Verbesserung liegt nicht im Sortieralgorithmus selbst, sondern in einer neuen Sortieroptimierung für moderne CPUs (insbesondere für kurze Sequenzen). Dieser Ansatz ist tatsächlich sehr verbreitet. Beispielsweise haben Bibliotheken wie FFTW und ATLAS diese Methode übernommen.

Einverstanden, sie haben nur eine schnellere Maschinenoptimierung für eine bestimmte CPU gefunden, keinen neuen Sortieralgorithmus, die Methode selbst ist cool, aber keine bahnbrechende Forschung.

Was meint ihr?

Papieradresse:https://www.php.cn/link/a3fefe83288ecb0e40ebe40b2bde29fe
Offizieller Blog:https://www.php.cn/link/f5b2aa928f940f3f09a0d14f45a27875

.

Referenzlink:
[1]https ://www.php.cn/link/5383c7318a3158b9bc261d0b6996f7c2
[2]https://www.php.cn/link/ecf9902e0f61677c8de25ae60b654669
[3]https://www.php.cn/ link/0383314bf626052313b8275638fcccce

Das obige ist der detaillierte Inhalt vonReproduzieren Sie den magischen Touch von AlphaGo von damals! Die neue KI von DeepMind hat einen um 70 % schnelleren Sortieralgorithmus entdeckt und die C++-Bibliothek, die seit zehn Jahren nicht aktualisiert wurde, wurde aktualisiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!