Des chercheurs de Harvard ont créé un nouvel algorithme d'optimisation
Qui augmente de manière exponentielle la vitesse de calcul des ordinateurs
Le 2018-07-08 18:38:13, par Bill Fassinou, Chroniqueur Actualités
Entre le temps de calcul qui peut s’avérer relativement long et les résultats qui ne sont pas toujours les meilleurs, les algorithmes d’optimisation semblaient avoir atteint leurs limites jusqu’à ce que des chercheurs de l'université Harvard décident de s’y pencher. Yaron Singer et Eric Balkanski, deux chercheurs de Harvard, ont développé un algorithme qui serait capable de résoudre les problèmes d’optimisation à un niveau de vitesse largement au-dessus de celui que les algorithmes existants peuvent atteindre. La méthode étape par étape qu’utilisaient les autres algorithmes avait déjà démontré qu’elle offrait des résultats de moins en moins bons le long des étapes.
Les deux chercheurs se sont donc dit qu’ils pourraient grandement augmenter la vitesse de calcul de leur algorithme si le nombre d’étapes nécessaires était proportionnellement réduit. Le risque avec cette méthode, c’est qu’elle pourrait, elle aussi, grandement compromettre la qualité des résultats de l’algorithme. Les deux chercheurs de Harvard rassurent cependant qu’il n’en est rien. Ils annoncent que les résultats de leurs expériences ont montré que l’algorithme pourrait analyser 20 fois plus vite, un ensemble de données avec 1 million d'évaluations de 4 000 films de 6 000 utilisateurs et donner des recommandations de films similaires à des algorithmes de pointe.
L’algorithme serait aussi capable d’analyser plus de 2 millions de voyages en taxi de la compagnie de taxis et de limousines de New York pour déterminer, six fois plus vite que n’importe quel autre algorithme, les emplacements où les véhicules sont susceptibles de couvrir le plus de clients. Contrairement aux autres algorithmes qui n’analysaient que dans une seule direction, le nouvel outil échantillonnerait plusieurs directions parallèles à la fois ; ce qui aurait réglé le problème de la baisse progressive de la qualité des résultats le long des étapes. Les deux chercheurs disent avoir basé le fonctionnement de leur algorithme sur deux aspects spécifiques qu'ils ont dénommés « la courbure et l’homogénéité ».
Ils ont expliqué ces deux aspects sur la base des recommandations de films et de la répartition des taxis. Ils disent qu’en matière de films, les objectifs avec des « courbures » élevées sont les films ressemblant beaucoup aux films qu’on a déjà vus et que les objectifs avec une grande « homogénéité » sont ceux qui sont du même genre que les films qu’on a vus. En matière de taxis, par contre, la « courbure » représente le temps de réactivité moyen des taxis dans une zone ; et l’homogénéité représente la répartition des clients entre les sites. Les deux chercheurs de Harvard finissent en disant que cet algorithme, du fait de l’accélération du temps de fonctionnement qu’il provoque, pourrait avoir des possibilités d’applications dans des domaines tels que la santé, la biologie, l’intelligence artificielle, etc.
Détail de la recherche
Source : IEEE Spectrum
Et vous ?
Que pensez-vous de ce nouvel algorithme d'optimisation ?
Voir aussi
Notes de cours Python scientifique : Apprendre l'optimisation du code avec Python
Le Ministère de l'Enseignement Supérieur publie l'algorithme de Parcoursup à la veille de ses premières réponses
OpenAI conçoit un algorithme basé sur l'IA qui permet à un robot d'imiter des tâches réalisées par des humains dans un environnement virtuel
Les deux chercheurs se sont donc dit qu’ils pourraient grandement augmenter la vitesse de calcul de leur algorithme si le nombre d’étapes nécessaires était proportionnellement réduit. Le risque avec cette méthode, c’est qu’elle pourrait, elle aussi, grandement compromettre la qualité des résultats de l’algorithme. Les deux chercheurs de Harvard rassurent cependant qu’il n’en est rien. Ils annoncent que les résultats de leurs expériences ont montré que l’algorithme pourrait analyser 20 fois plus vite, un ensemble de données avec 1 million d'évaluations de 4 000 films de 6 000 utilisateurs et donner des recommandations de films similaires à des algorithmes de pointe.
L’algorithme serait aussi capable d’analyser plus de 2 millions de voyages en taxi de la compagnie de taxis et de limousines de New York pour déterminer, six fois plus vite que n’importe quel autre algorithme, les emplacements où les véhicules sont susceptibles de couvrir le plus de clients. Contrairement aux autres algorithmes qui n’analysaient que dans une seule direction, le nouvel outil échantillonnerait plusieurs directions parallèles à la fois ; ce qui aurait réglé le problème de la baisse progressive de la qualité des résultats le long des étapes. Les deux chercheurs disent avoir basé le fonctionnement de leur algorithme sur deux aspects spécifiques qu'ils ont dénommés « la courbure et l’homogénéité ».
Ils ont expliqué ces deux aspects sur la base des recommandations de films et de la répartition des taxis. Ils disent qu’en matière de films, les objectifs avec des « courbures » élevées sont les films ressemblant beaucoup aux films qu’on a déjà vus et que les objectifs avec une grande « homogénéité » sont ceux qui sont du même genre que les films qu’on a vus. En matière de taxis, par contre, la « courbure » représente le temps de réactivité moyen des taxis dans une zone ; et l’homogénéité représente la répartition des clients entre les sites. Les deux chercheurs de Harvard finissent en disant que cet algorithme, du fait de l’accélération du temps de fonctionnement qu’il provoque, pourrait avoir des possibilités d’applications dans des domaines tels que la santé, la biologie, l’intelligence artificielle, etc.
Source : IEEE Spectrum
Et vous ?
Voir aussi
-
dourouc05Responsable Qt & LivresSauf qu'ici le mot est bien utilisé : cet algorithme permet de se débarrasser d'une exponentielle dans la complexité de résolution d'un problème — maximisation d'une fonction sous-modulaire monotone sur un ensemble discret assez simple — au prix d'une solution approchée plutôt qu'exacte.le 10/07/2018 à 15:12
-
Optimiser une fonction f, ça veut dire trouver le point x du domaine de f pour lequel la valeur f(x) est maximale.
Donc ça n'a à peu près aucun rapport avec l'optimisation de code python, la publication de parcoursup ou l'algo de deep-learning d'openai.le 09/07/2018 à 18:57 -
Matthieu76Membre éclairéOui mais dans l'article c'est il est question de log(x)/log(log(x)) et -log(x)/log(log(x)) tend plus rapidement vers +Inf que exp(x) donc le terme exponentielle est largement justifier ici.le 11/07/2018 à 18:06
-
MClercMembre régulierLe titre de l'article est « The Adaptive Complexity of Maximizing a Submodular Function ».
Sauf que, quand on lit le papier, on voit qu'il s'agit du cas particulier « monotone submodular functions » (en gros, si f est définie sur des sous-ensembles et que A est inclus dans B, alors f(A)< f(B)).le 17/07/2018 à 22:59 -
Matthieu76Membre éclairéAu temps pour moi.
-log(x)/log(log(x)) tend vers +INF lors que x tend vers 10 et -log(x)/log(log(x)) tend extrêmement lentement vers -INF lors que x tend vers +INF.
Désoléle 27/08/2018 à 13:58 -
fodgerMembre confirméQuasi impossible à mettre en œuvre de manière simple pour le commun des devs, il faut être un sacré gros matheux
! le 09/07/2018 à 10:46 -
redcurveMembre extrêmement actifça me f'ra de la lecture pour la semainele 09/07/2018 à 11:35
-
zoonelMembre actifj'ai pas trop pigé le rapport entre l'article et le papier du coup j'ai cherché un peu sur le net pour tomber sur ça:
This is specifically talking about submodular function maximization problems. A submodular set function is a function f(S) that takes a set S and returns a "score". The objective is to find the set S with the highest score. The "submodular" property means that f(S) has "diminishing returns", meaning roughly that each new element contributes less to the score as the set S gets bigger. It turns out that this is hard to maximize exactly, but the simplest possible greedy algorithm already achieves an impressive approximation ratio of 1 - 1/e. The downside is that even the fully greedy algorithm is still pretty slow if you need to find a large set S, which is what this paper is addressing with a parallelizable randomized algorithm. (It's not the first such algorithm, but it's apparently much faster than the previous state of the art.)
[disclaimer: not an expert in any of this]
Submodular maximization is indeed NP-complete, but we can find approximate solutions in polynomial time. This paper speeds up the parallel running time of the approximation from O(n) to O(log n), meaning that they've found a way to make the algorithm more parallelizable, though you still have to do the same amount of work.
Je pense que ça explique bien mieux le papier des chercheurs.le 09/07/2018 à 20:26 -
domi65Membre éclairéBonjour. J'ai tiqué aussi sur le mot « exponentielle ». Sur une courbe exponentielle, on place une abscisse et une ordonnée. Que met ont-on ici dans ces deux coordonnées, puisqu'il n'est question que de « vitesse de calcul des ordinateurs » ?le 18/07/2018 à 15:56
-
Matthieu76Membre éclairéC'est de la complexité algorithmique, il s'agit de minimiser le nombre d'instructions en fonction de la taille des données d'entrée. Et je parle de « nombre d'instructions » et non de « vitesse de calcul » car peu importe la vitesse du processeur, cela fonctionnera toujours. D'ailleurs il s'agirait plus d'une fonction avec 2 paramètres du genre z = f(x, y), le second paramètre étant le nombre de thread, même si ce paramètre semble linéaire : avec 1000 threads on va 10 fois plus vite qu'avec 100.le 18/07/2018 à 17:57