Et si une grande classe d'algorithmes utilisés aujourd'hui, des algorithmes qui nous aident à éviter le trafic aux algorithmes qui identifient de nouvelles molécules médicamenteuses, fonctionnaient de manière exponentielle plus rapidement ?

Les informaticiens de la Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS) ont développé un tout nouveau type d'algorithme, celui qui accélère de façon exponentielle le calcul en réduisant considérablement le nombre d'étapes parallèles nécessaires pour parvenir à une solution.

Les chercheurs présenteront leur nouvelle approche lors de deux conférences à venir :le Symposium ACM sur la théorie de l'informatique (STOC), 25-29 juin et Conférence internationale sur l'apprentissage automatique (ICML), 10 -15 juillet.

Beaucoup de soi-disant problèmes d'optimisation, problèmes qui trouvent la meilleure solution parmi toutes les solutions possibles, comme la cartographie de l'itinéraire le plus rapide du point A au point B, reposent sur des algorithmes séquentiels qui n'ont pas changé depuis leur première description dans les années 1970. Ces algorithmes résolvent un problème en suivant un processus séquentiel étape par étape. Le nombre d'étapes est proportionnel à la taille des données. Mais cela a conduit à un goulot d'étranglement de calcul, résultant en des lignes de questions et des domaines de recherche qui sont tout simplement trop coûteux en calcul à explorer.

"Ces problèmes d'optimisation ont une propriété de rendement décroissant, " a déclaré Yaron Singer, Professeur adjoint d'informatique à SEAS et auteur principal de la recherche. "Au fur et à mesure qu'un algorithme progresse, son gain relatif à chaque étape devient de plus en plus petit."

Le chanteur et son collègue ont demandé :et si, au lieu de faire des centaines ou des milliers de petits pas pour parvenir à une solution, un algorithme pourrait faire quelques bonds ?

"Cet algorithme et cette approche générale nous permettent d'accélérer considérablement le calcul d'une classe de problèmes extrêmement vaste dans de nombreux domaines différents, y compris la vision par ordinateur, récupération de l'information, Analyse de réseau, biologie computationnelle, conception d'enchères, et plein d'autres, ", a déclaré Singer. "Nous pouvons maintenant effectuer des calculs en quelques secondes qui auraient auparavant pris des semaines ou des mois."

« Ce nouveau travail algorithmique, et l'analyse correspondante, ouvre les portes à de nouvelles stratégies de parallélisation à grande échelle qui ont des accélérations beaucoup plus importantes que ce qui n'a jamais été possible auparavant, " a déclaré Jeff Bilmes, Professeur au Département de génie électrique de l'Université de Washington, qui n'a pas participé à la recherche. "Ces capacités seront, par exemple, permettent de développer des processus de résumé du monde réel à une échelle sans précédent. »

Traditionnellement, les algorithmes pour les problèmes d'optimisation réduisent l'espace de recherche de la meilleure solution une étape à la fois. En revanche, ce nouvel algorithme échantillonne une variété de directions en parallèle. Sur la base de cet échantillon, l'algorithme élimine les directions de faible valeur de son espace de recherche et choisit les directions les plus précieuses pour progresser vers une solution.

Prenons cet exemple de jouet :

Vous êtes d'humeur à regarder un film similaire à The Avengers. Un algorithme de recommandation traditionnel ajouterait séquentiellement un seul film à chaque étape ayant des attributs similaires à ceux de The Avengers. En revanche, le nouvel algorithme échantillonne un groupe de films au hasard, jeter ceux qui sont trop différents de The Avengers. Ce qui reste, c'est un lot de films divers (après tout, vous ne voulez pas dix films Batman) mais similaire à The Avengers. L'algorithme continue d'ajouter des lots à chaque étape jusqu'à ce qu'il ait suffisamment de films à recommander.

Ce processus d'échantillonnage adaptatif est essentiel à la capacité de l'algorithme à prendre la bonne décision à chaque étape.

"Les algorithmes traditionnels pour cette classe de problèmes ajoutent avidement des données à la solution tout en considérant l'ensemble de données entier à chaque étape, " a déclaré Eric Balkanski, étudiant diplômé à SEAS et co-auteur de la recherche. "La force de notre algorithme est qu'en plus d'ajouter des données, il élague également de manière sélective les données qui seront ignorées dans les étapes futures. »

Dans les expériences, Singer et Balkanski ont démontré que leur algorithme pouvait passer au crible un ensemble de données contenant 1 million de notes sur 6, 000 utilisateurs sur 4, 000 films et recommander une collection de films personnalisée et diversifiée pour un utilisateur individuel 20 fois plus rapide que l'état de l'art.

Les chercheurs ont également testé l'algorithme sur un problème de répartition des taxis, où il y a un certain nombre de taxis et l'objectif est de sélectionner les meilleurs emplacements pour couvrir le maximum de clients potentiels. À l'aide d'un ensemble de données de deux millions de trajets en taxi de la commission des taxis et des limousines de New York, l'algorithme d'échantillonnage adaptatif a trouvé des solutions 6 fois plus rapidement.

"Cet écart augmenterait encore plus significativement sur des applications à plus grande échelle, telles que le regroupement de données biologiques, enchères de recherche sponsorisées, ou analyse des médias sociaux, " a déclaré Balkanki.

Bien sûr, le potentiel de l'algorithme s'étend bien au-delà des recommandations de films et des optimisations de répartition des taxis. Il pourrait s'appliquer à :

• concevoir des essais cliniques de médicaments pour traiter la maladie d'Alzheimer, sclérose en plaque, obésité, Diabète, hépatite C, VIH et plus
• biologie évolutive pour trouver de bons sous-ensembles représentatifs de différentes collections de gènes à partir de grands ensembles de données de gènes de différentes espèces
• conception de réseaux de capteurs pour l'imagerie médicale
• identifier la détection des interactions médicamenteuses à partir des forums de santé en ligne

Ce processus d'apprentissage actif est la clé de la capacité de l'algorithme à prendre la bonne décision à chaque étape et résout le problème des rendements décroissants.

"Cette recherche est une véritable avancée pour l'optimisation discrète à grande échelle, " a déclaré Andreas Krause, professeur d'informatique à l'ETH Zurich, qui n'a pas participé à la recherche. "L'un des plus grands défis de l'apprentissage automatique est de trouver de bons, des sous-ensembles représentatifs de données provenant de grandes collections d'images ou de vidéos pour former des modèles d'apprentissage automatique. Cette recherche pourrait identifier ces sous-ensembles rapidement et avoir un impact pratique substantiel sur ces problèmes de résumé de données à grande échelle. »

Le modèle Singer-Balkanski et les variantes de l'algorithme développé dans l'article pourraient également être utilisés pour évaluer plus rapidement la précision d'un modèle d'apprentissage automatique, dit Vahab Mirrokni, un scientifique principal chez Google Research, qui n'a pas participé à la recherche.

"Dans certains cas, nous avons un accès en boîte noire à la fonction de précision du modèle qui prend beaucoup de temps à calculer, " dit Mirrokni. " En même temps, le calcul de la précision du modèle pour de nombreux paramètres de caractéristiques peut être effectué en parallèle. Ce cadre d'optimisation adaptative est un excellent modèle pour ces paramètres importants et les informations issues des techniques algorithmiques développées dans ce cadre peuvent avoir un impact profond dans ce domaine important de la recherche en apprentissage automatique."

Singer et Balkanski continuent de travailler avec des praticiens sur la mise en œuvre de l'algorithme.