DeepMind lance un algorithme de tri révolutionnaire et la bibliothèque C++ est en train de se mettre à jour !

Cliquez pour participer au questionnaire sur le contenu du site Web 51CTO

Compilé | Wang Ruiping, Yan Zheng

AlphaGo a un autre "petit frère" " rejoindre !

Google DeepMind a "transformé" la série Alpha en algorithmes de tri et a lancé AlphaDev.

C'est comme une « méthode secrète de développement ». En utilisant l'IA d'apprentissage par renforcement pour découvrir des algorithmes de tri et des algorithmes de hachage, elle accélère de force les algorithmes conçus par des programmeurs humains d'environ 70 % et 30 % respectivement.

Une fois les résultats de la recherche publiés, ils ont instantanément enflammé le cercle des logiciels ! Soudainement, la vitesse d'exécution de millions de logiciels dans le monde a grimpé en flèche, dépassant directement les réalisations des scientifiques et des ingénieurs pendant des décennies, et la bibliothèque C++ standard LLVM qui n'avait pas été mise à jour depuis dix ans a été mise à jour.

(Source : Nature)

C'est aussi une technologie de rupture lancée après la fusion des deux départements IA de Google. L'article a été publié dans Nature sous le titre "Des algorithmes de tri plus rapides découverts grâce à l'apprentissage par renforcement profond". Le premier auteur de l'article est Daniel Mankowitz, informaticien chez DeepMind.

1. Evolution : L'origine de l'algorithme de tri

Le tri est une méthode permettant d'organiser de nombreux éléments dans un ordre spécifique, par exemple, disposer trois lettres par ordre alphabétique, de Organisez cinq nombres du plus grand au plus petit ou triez une base de données contenant des millions d'enregistrements.

La méthode de commande remonte aux deuxième et troisième siècles et continue d'évoluer. Initialement, les érudits triaient manuellement les milliers de livres sur les étagères de la Bibliothèque d’Alexandrie par ordre alphabétique.

Après la révolution industrielle, des machines à tri automatique (des machines à tabuler qui stockaient les informations sur des cartes perforées) ont été inventées pour collecter les résultats du recensement américain de 1890.

Dans les années 1950, les ordinateurs commerciaux ont commencé à se développer et des algorithmes de tri ont été immédiatement produits. Entrez des nombres non triés dans un algorithme de tri et cela produira une séquence de nombres triés.

Actuellement, de nombreuses techniques et algorithmes de tri différents sont encore utilisés partout dans les bases de code pour traiter des quantités massives de données.​​​​

Après des décennies de recherche et développement, l'efficacité de ces algorithmes de tri n'a cessé de s'améliorer et a été reconnue par les informaticiens et les programmeurs . Cependant, des défis importants restent à relever pour poursuivre son amélioration.

2. Le point fort : Comment utiliser AlphaDev pour générer un nouvel algorithme de tri ?

Les chercheurs ont initialement utilisé AlphaDev pour générer de nouveaux algorithmes afin d'accomplir efficacement une tâche donnée.

AlphaDev construit un algorithme complètement nouveau, qui n'est pas développé sur la base des algorithmes précédents, il peut donc être considéré comme original. Ce faisant, il applique un langage intermédiaire de code assembleur. AlphaDev facilite la création d'algorithmes efficaces car le langage est plus proche des instructions binaires informatiques.

Plus précisément, AlphaDev génère une instruction à chaque fois, puis teste si la sortie est correcte. Il définit également les exigences dans le modèle pour générer l'algorithme le plus court.

Lorsqu'on lui a demandé de repenser l'algorithme de tri, AlphaDev a généré aléatoirement un nouvel algorithme de tri qui était 70 % plus rapide que l'algorithme existant et pouvait trier cinq données en même temps. Il était également 1,7 % plus rapide que le meilleur algorithme lors du tri de 250 000 données.

Cette innovation aura un impact énorme sur les algorithmes globaux, car les algorithmes de tri sont largement utilisés par divers logiciels courants. DeepMind les a open-source et les a intégrés dans la bibliothèque standard Libc++.

Selon la description des chercheurs de DeepMind : "En raison du grand nombre de combinaisons d'instructions, le processus de recherche apparemment simple est extrêmement difficile."

3. jouer à des jeux Meilleur algorithme

De plus, AlphaDev est un modèle plus avancé conçu sur la base de la structure d'AlphaZero. AlphaZero était auparavant le modèle d'apprentissage par renforcement de DeepMind et avait vaincu les champions du monde de Go, d'échecs et d'autres jeux d'échecs.

Grâce à cette expérience, le nouveau modèle AlphaDev exerce ses avantages uniques en passant du jeu à la résolution de problèmes scientifiques, et des simulations expérimentales aux applications du monde réel.

Les chercheurs ont simulé le tri comme un « jeu d'assemblage » solo pour entraîner AlphaDev à découvrir de nouveaux algorithmes. À chaque tour de jeu, AlphaDev observe l'algorithme généré et les informations contenues dans le CPU, puis sélectionne une instruction à ajouter à l'algorithme pour effectuer chaque mouvement.

Le document mentionne que les jeux d'assemblage sont très difficiles car AlphaDev doit être capable de rechercher efficacement parmi un grand nombre de combinaisons d'instructions possibles pour obtenir un algorithme pouvant être trié.

Le nombre de combinaisons d'instructions est similaire au nombre de particules dans l'univers ou au nombre de combinaisons possibles de coups aux échecs (10120 parties) et au Go (10700 parties). Chaque mauvais coup invalidera tout l'algorithme. Le modèle génère ensuite un algorithme et le compare au résultat attendu, récompensant l'agent en fonction de l'exactitude et de la latence de l'algorithme.

Lors de la construction d'un algorithme, chaque fois qu'une instruction est saisie, AlphaDev vérifie l'exactitude en comparant la sortie de l'algorithme avec le résultat attendu (pour un algorithme de tri, cela signifie qu'après avoir saisi des nombres non ordonnés, il peut produire des nombres correctement triés) ).

Le modèle récompense AlphaDev pour son ordonnancement correct des chiffres et son efficacité. Finalement, AlphaDev a remporté le concours en découvrant un programme plus précis et plus rapide.

4. Innovation en matière d'algorithme : échanger les séquences d'instructions de déplacement et de copie

AlphaDev a non seulement généré un algorithme plus rapide, mais a également innové avec deux séquences d'instructions.

Plus précisément, l'algorithme de tri qu'il génère comprend deux nouvelles séquences d'instructions : le déplacement d'échange et le déplacement de copie, et une instruction sera enregistrée à chaque utilisation. Les chercheurs l’appellent « le mouvement d’échange et le mouvement de copie d’AlphaDev ».

Cette nouvelle méthode n'est pas sans rappeler le "Move 37" d'AlphaGo - une méthode de jeu d'échecs "contre-intuitive", qui a choqué les spectateurs et provoqué la défaite d'un joueur d'échecs légendaire.

En échangeant les séquences d'instructions de déplacement et de copie, AlphaDev saute une étape, complétant l'objectif d'une manière qui ressemble à une erreur mais qui est en réalité un raccourci. Cela signifie qu’AlphaDev a la capacité de découvrir des premières solutions et de tenter d’améliorer les algorithmes informatiques.

5. Test : Promouvoir et améliorer les algorithmes de hachage

Après que les chercheurs ont découvert un algorithme de tri plus rapide, ils ont essayé de l'appliquer à un autre algorithme informatique—— Sur la promotion et l'amélioration d'algorithmes de hachage.

L'algorithme de hachage est un algorithme de base en informatique et est utilisé pour récupérer, stocker et compresser des données. Tout comme les bibliothécaires utilisent un système de classification pour localiser un livre donné, les algorithmes de hachage aident les utilisateurs à savoir ce qu'ils recherchent et où le trouver.

Ces algorithmes sont capables de prendre des données pour une clé spécifique (par exemple, le nom d'utilisateur "Jane Doe") et de les trier par hachage - en convertissant les données brutes en une chaîne unique (par exemple, 1234ghty).

L'ordinateur utilise ce hachage pour récupérer rapidement les données liées à la clé, plutôt que de rechercher dans toutes les données.

Les chercheurs ont appliqué AlphaDev à l'un des algorithmes de hachage les plus couramment utilisés dans les structures de données dans le but de découvrir un algorithme plus rapide. Lorsqu'il est appliqué à la plage de 9 à 16 octets de la fonction de hachage, AlphaDev a produit un algorithme 30 % plus rapide.

Plus tôt cette année, le nouvel algorithme de hachage généré par AlphaDev a été publié dans la bibliothèque open source Abseil, le rendant accessible à des millions de développeurs à travers le monde. On estime qu'il est désormais utilisé chaque jour par des milliards. de fois.

6. Prendre de l'ampleur : faire le premier pas dans le développement de l'AGI

En optimisant les "algorithmes de tri et de hachage", AlphaDev a démontré sa capacité à générer différents nouveaux algorithmes pratiques.

C'est également la première étape d'AlphaDev vers le développement d'outils généraux d'intelligence artificielle (AGI). Des outils d'IA similaires peuvent également aider à optimiser l'ensemble de l'écosystème informatique et à résoudre d'autres problèmes qui profitent à la société.

Bien que l'algorithme d'optimisation dans l'espace des instructions d'assemblage de bas niveau soit très puissant, il a également des limites. Actuellement, l'équipe étudie la capacité d'AlphaDev à optimiser les algorithmes dans des langages de haut niveau (comme le C++), ce qui sera plus bénéfique pour les développeurs.

En bref, on espère que ces nouvelles découvertes inciteront les développeurs à créer de nouvelles technologies et méthodes, à optimiser davantage les algorithmes de base et à créer un écosystème informatique plus fort et plus durable.

7. Open source : une avancée majeure dans le code d'optimisation de l'IA

Auparavant, les algorithmes de tri étaient utilisés des milliards de fois chaque jour. Avec la croissance des besoins informatiques, les utilisateurs ont des exigences de performances de plus en plus élevées pour les algorithmes. Bien que les ingénieurs humains aient découvert différents algorithmes de tri, après des décennies d'optimisation, il est difficile de faire des percées et ne peut pas répondre à la demande croissante.

Aujourd'hui, AlphaDev a découvert un algorithme de tri plus rapide pour trier les données.

Le nouvel algorithme de classement peut tout faire, du classement des résultats de recherche en ligne et des publications sur les réseaux sociaux à l'analyse des données sur les ordinateurs et les téléphones mobiles.

Cela vaut la peine de célébrer que le nouvel algorithme de tri soit open source dans la bibliothèque principale C++. Il est actuellement utilisé par des millions de développeurs et d'entreprises à travers le monde pour le cloud computing, les achats en ligne, la gestion de la chaîne d'approvisionnement, etc.

En bref, utiliser des outils d'intelligence artificielle pour optimiser les algorithmes va complètement changer la manière traditionnelle de programmer. C'est la première fois en plus de dix ans que la bibliothèque de tri est modifiée, et la première fois que des algorithmes conçus par des modèles d'apprentissage par renforcement sont ajoutés à la bibliothèque de tri. C'est donc une avancée majeure dans l'utilisation de l'intelligence artificielle. optimiser le code.

8. Utilisateurs : C'est peut-être juste un gadget

Les utilisateurs ont des opinions mitigées sur les résultats de la recherche, avec des voix majoritairement élogieuses sur Twitter :

# 🎜 🎜#

Apprendre les tâches de tri de base est l'une des compétences que les programmeurs maîtrisent très tôt, et cette compétence augmente la vitesse de 70 %. C'est passionnant de voir tirer parti de l'IA pour fournir une accélération significative des algorithmes et des bibliothèques sur lesquels nous comptons tous. juste un gadget et DeepMind exagère la fonction de l'algorithme. #Tout d'abord, du point de vue de l'efficacité, il ne compte que le retard de l'algorithme, plutôt que de modifier réellement la complexité temporelle. cela ne change pas vraiment le tri. Ce type d'opération est courant dans diverses autres opérations Code base

Références :

1. .deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

3.https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised- outils ai

4 https://twitter.com/demishassabis

.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!