Un nouvel algorithme réduit le temps de calcul par ordre de grandeur

• Un nouvel algorithme accélère de manière exponentielle le calcul en réduisant considérablement le nombre d'itérations nécessaires pour résoudre un problème.
• Il fonctionne bien mieux que les algorithmes (séquentiels) conventionnels sur des ensembles de données à grande échelle, tels que l'analyse des réseaux sociaux et le regroupement de données génétiques. 

Des milliers de problèmes d'optimisation (problème de trouver la meilleure solution parmi toutes les solutions possibles), comme l'allocation de fonds aux actions pour minimiser les risques sur les rendements, ou l'affectation des employés aux bureaux disponibles pour maximiser le flux de travail et le statisticien des employés, s'appuient fortement sur des algorithmes séquentiels.

Le modèle de fonctionnement de base de ces algorithmes n’a pas été modifié (amélioré) depuis leur création au début des années 1970. Ils résolvent n'importe quel problème particulier de manière séquentielle en un nombre "n" d'étapes.

Le nombre d'étapes dépend de la taille du problème (qui fournit certaines valeurs à l'algorithme en entrée). Ce type de méthode entraîne généralement un goulot d'étranglement informatique. Le gain relatif de chaque itération devient de plus en plus petit à mesure que l'algorithme progresse.

Et si un algorithme pouvait faire quelques sauts, plutôt que des milliers de petites étapes pour résoudre le problème ? Et si nous pouvions faire fonctionner un grand nombre d’algorithmes largement utilisés aujourd’hui de manière exponentielle ? Nous parlons des algorithmes qui nous aident à découvrir de nouveaux médicaments et à éviter le trafic.

Pour rendre cela possible, des chercheurs de l'Université Harvard ont mis au point un nouveau type d'algorithme, ce qu'ils appellent « Breakthrough », qui accélère de façon exponentielle le calcul en réduisant considérablement le nombre d'itérations nécessaires pour résoudre un problème.

Il accélère le calcul pour un large éventail de problèmes dans plusieurs domaines différents, tels que l'extraction d'informations, la conception d'enchères, la vision industrielle, la biologie computationnelle, l'analyse de réseau, etc.

Selon les développeurs, il est capable d’effectuer des calculs volumineux en quelques secondes, ce qui aurait auparavant pris des jours ou des semaines. Cela pourrait ouvrir la porte à de nouvelles approches de parallélisation à grande échelle, permettant de construire des processus de synthèse pratiques à une échelle exceptionnelle.

Comment ça marche ?

Les algorithmes séquentiels fonctionnent en réduisant le nombre de solutions réalisables, étape par étape. En revanche, le nouvel algorithme échantillonne en parallèle différentes directions, puis élimine les directions les moins pertinentes et sélectionne les directions les plus favorables (de grande valeur) pour atteindre la solution. Il supprime sélectivement les valeurs qui seront ignorées dans les itérations futures.

Un algorithme révolutionnaire utilise l'échantillonnage adaptatif | Avec l'aimable autorisation des chercheurs

Plus précisément, l'algorithme nécessite O (log n) étapes séquentielles et atteint une approximation arbitrairement proche de 1/3. Lors de l'activation de la parallélisation, les algorithmes atteignent une approximation à facteur constant exponentiellement plus rapidement que n'importe quelle méthode existante de maximisation sous-modulaire.

Référence :Harvard SEAS | Publications Harvard

Par exemple, si la tâche consiste à recommander des films similaires à Star Wars, un algorithme conventionnel ajouterait à chaque étape un film ayant des attributs similaires (action, aventure, fantastique) à ceux de Star Wars.

L'algorithme nouvellement développé, quant à lui, échantillonne au hasard un ensemble de films, éliminant ceux qui ne correspondent pas du tout à Star Wars. Cela donne une collection diversifiée de films (évidemment, vous ne voulez pas 10 films Superman dans votre recommandation) qui sont similaires à Star Wars.

L'algorithme continuera à ajouter une variété de films à chaque étape jusqu'à ce qu'il ait suffisamment d'éléments à recommander. La clé pour prendre des décisions utiles à chaque étape réside dans le processus d'échantillonnage adaptatif.

Nombre d'étapes effectuées par un algorithme séquentiel (noir) et révolutionnaire (rouge) pour résoudre un problème

Tests et applications

Les chercheurs ont testé leur algorithme d'échantillonnage adaptatif sur un vaste ensemble de données contenant 1 million de notes sur 4 000 films provenant de 6 000 utilisateurs. Il a recommandé avec succès des films personnalisés et variés à une personne 20 fois plus rapidement que les algorithmes conventionnels.

Ils ont également appliqué cet algorithme à un problème de répartition des taxis :choisir les meilleurs emplacements pour desservir le nombre maximum de clients avec un nombre limité de taxis. Pour 2 millions de trajets en taxi, l'algorithme a fonctionné 6 fois plus vite que l'état de l'art.

Cela peut donner de bien meilleurs résultats sur des ensembles de données à grande échelle, comme l’analyse des médias sociaux ou le regroupement de données génétiques.  En dehors de cela, l'algorithme pourrait être appliqué au développement d'essais cliniques sur plusieurs maladies, à des réseaux de capteurs pour l'imagerie médicale et à la détection d'interactions entre médicaments.

Lire :Rechercher un nouvel algorithme de véhicule autonome qui peut changer de voie de manière agressive

De nos jours, trouver un sous-ensemble efficace de données à partir de millions d’images/vidéos pour former des réseaux d’apprentissage profond est devenu une tâche difficile. Cette étude pourrait aider à extraire rapidement des sous-ensembles précieux et avoir un impact significatif sur les problèmes de synthèse de données à grande échelle.