Nouvel algorithme : temps de calcul réduit d'ordres de grandeur

Un nouvel algorithme accélère exponentiellement le calcul en réduisant drastiquement le nombre d'itérations pour résoudre un problème.

Il surpasse largement les algorithmes séquentiels conventionnels sur grands jeux de données : analyse réseaux sociaux, regroupement données génétiques.

Le problème des algorithmes séquentiels

Des milliers de problèmes d'optimisation (allouer fonds pour minimiser risque, affecter employés pour maximiser flux de travail) reposent sur des algorithmes séquentiels.

Leur fonctionnement n'a pas évolué depuis les années 1970. Ils résolvent séquentiellement en « n » étapes, où n dépend de la taille du problème. Cela crée un goulot d'étranglement computationnel : le gain relatif de chaque itération diminue.

Et si un algorithme faisait quelques sauts au lieu de milliers de petits pas ? Et si on rendait exponentiellement plus rapides les algorithmes largement utilisés aujourd'hui ? Ceux qui aident à découvrir de nouveaux médicaments et éviter le trafic.

L'algorithme « Breakthrough » de Harvard

Des chercheurs de Harvard ont créé un nouvel algorithme, « Breakthrough », qui accélère exponentiellement le calcul en réduisant drastiquement les itérations nécessaires.

Il accélère une large gamme de problèmes : extraction d'information, conception d'enchères, vision par ordinateur, biologie computationnelle, analyse de réseaux, etc.

Selon les développeurs, il effectue en quelques secondes de gros calculs qui prenaient auparavant des jours ou semaines. Cela ouvre la porte à de nouvelles approches de parallélisation massive, permettant des processus de résumé pratiques à une échelle exceptionnelle.

Comment ça marche ?

Les algorithmes séquentiels réduisent les solutions faisables étape par étape. Le nouvel algorithme échantillonne parallèlement différentes directions, élimine les moins pertinentes et sélectionne les plus favorables (haute valeur) pour atteindre la solution. Il écarte sélectivement les valeurs qui seront ignorées aux itérations futures.

L'algorithme Breakthrough utilise un échantillonnage adaptatif.

Plus précisément : O(log n) étapes séquentielles, approximation arbitrairement proche de 1/3. Avec parallélisation, approximation à facteur constant exponentiellement plus rapide que toute méthode existante pour la maximisation sous-modulaire.

Référence : Harvard SEAS | Harvard Publications

Exemple : Recommander des films similaires à Star Wars. Algorithme conventionnel : ajoute un film par étape avec attributs similaires (action, aventure, fantasy). Nouvel algorithme : échantillonne aléatoirement un ensemble de films, élimine ceux qui ne correspondent pas. Donne une collection diverse (pas 10 films Superman) similaires à Star Wars. Continue d'ajouter de la variété jusqu'à avoir assez de recommandations. La clé : l'échantillonnage adaptatif à chaque étape.

Tests et applications

Testé sur 1 million de notes sur 4000 films par 6000 utilisateurs : recommandations personnalisées et variées 20 fois plus vite.

Appliqué au problème de dispatch de taxis — choisir les meilleurs emplacements pour servir le maximum de clients avec taxis limités. Pour 2 millions de courses, 6 fois plus rapide que l'état de l'art.

Bien meilleur sur grands jeux de données : analyse réseaux sociaux, regroupement données génétiques. Autres applications : essais cliniques multi-maladies, réseaux de capteurs imagerie médicale, détection interactions médicamenteuses.

Trouver des sous-ensembles efficaces de données parmi millions d'images/vidéos pour entraîner réseaux profonds est un défi. Cette étude aide à extraire rapidement des sous-ensembles précieux, impact significatif sur la synthèse de données à grande échelle.