Imaginez que vous deviez envoyer une équipe de joueurs de football sur un terrain pour évaluer l’état du gazon. Si vous les positionnez au hasard, ils pourraient se concentrer sur certaines zones et en négliger d’autres. Cependant, en leur donnant une stratégie de répartition uniforme, vous obtiendriez une image plus précise de l’état du gazon.
Maintenant, imaginez que vous deviez vous étendre non seulement sur deux dimensions, mais sur des dizaines, voire des centaines. C’est le défi auquel sont confrontés les chercheurs du Laboratoire d’informatique et d’intelligence artificielle (CSAIL) du MIT. Ils ont développé une approche basée sur l’IA pour « l’échantillonnage à faible divergence », une méthode qui améliore la précision des simulations en distribuant plus uniformément les points de données dans l’espace.
La nouveauté réside dans l’utilisation de réseaux de neurones graphiques (GNN), permettant aux points de « communiquer » et de s’auto-optimiser pour une meilleure uniformité. Cette approche représente une avancée cruciale pour les simulations dans des domaines tels que la robotique, la finance et l’informatique, en particulier pour gérer des problèmes complexes et multidimensionnels essentiels à des simulations et des calculs numériques précis.
« Dans de nombreux problèmes, plus les points sont répartis uniformément, plus la simulation de systèmes complexes est précise », explique T. Konstantin Rusch, auteur principal de l’étude et postdoctorant au MIT CSAIL. « Nous avons développé une méthode appelée Message-Passing Monte Carlo (MPMC) pour générer des points uniformément espacés en utilisant des techniques d’apprentissage géométrique profond. Cela nous permet de générer des points qui mettent l’accent sur les dimensions importantes pour un problème donné, une propriété cruciale dans de nombreuses applications. Les réseaux neuronaux graphiques sous-jacents permettent aux points de « communiquer » entre eux, obtenant ainsi une bien meilleure uniformité que les méthodes précédentes. »
Leur travail a été publié dans le numéro de septembre des Actes de l’Académie nationale des sciences.
Emmène-moi à Monte-Carlo
Les méthodes de Monte Carlo consistent à simuler un système avec un échantillonnage aléatoire pour en apprendre davantage sur celui-ci. L’échantillonnage est la sélection d’un sous-ensemble d’une population pour estimer les caractéristiques de l’ensemble de la population. Historiquement, cette méthode était déjà utilisée au XVIIIe siècle par le mathématicien Pierre-Simon Laplace pour estimer la population de la France sans avoir à compter chaque individu.
Les séquences à faible divergence, comme celles de Sobol’, Halton et Niederreiter, ont longtemps été la référence en matière d’échantillonnage quasi aléatoire, qui remplace l’échantillonnage aléatoire par l’échantillonnage à faible divergence. Elles sont largement utilisées dans des domaines tels que l’infographie et la finance informatique, pour des tâches allant de la tarification des options à l’évaluation des risques, où une répartition uniforme des points peut conduire à des résultats plus précis.
Le cadre MPMC proposé par l’équipe transforme des échantillons aléatoires en points présentant une grande uniformité. Cela se fait en traitant les échantillons aléatoires avec un GNN qui minimise une mesure de divergence spécifique.
L’un des principaux défis de l’utilisation de l’IA pour générer des points hautement uniformes est que la manière habituelle de mesurer l’uniformité des points est lente à calculer et difficile à utiliser. Pour résoudre ce problème, l’équipe a opté pour une mesure d’uniformité plus rapide et plus flexible appelée écart L2. Pour les problèmes de grande dimension, ils utilisent une nouvelle technique qui se concentre sur d’importantes projections de points de moindre dimension, créant ainsi des ensembles de points mieux adaptés à des applications spécifiques.
Les implications de cette recherche vont bien au-delà du monde académique. En finance computationnelle, par exemple, les simulations dépendent fortement de la qualité des points d’échantillonnage. « Avec ce type de méthodes, les points aléatoires sont souvent inefficaces, mais nos points à faible écart générés par GNN conduisent à une plus grande précision », explique Rusch. « Par exemple, dans un problème classique de finance informatique en 32 dimensions, nos points MPMC surpassent les méthodes d’échantillonnage quasi-aléatoire de pointe d’un facteur de quatre à 24. »
Des robots à Monte-Carlo
En robotique, la planification des trajectoires et des mouvements repose souvent sur des algorithmes basés sur l’échantillonnage, qui guident les robots dans leurs processus de prise de décision en temps réel. L’uniformité améliorée du MPMC pourrait conduire à une navigation robotique plus efficace et à des adaptations en temps réel pour des technologies comme la conduite autonome ou les drones. « Dans une prépublication récente, nous avons démontré que nos points MPMC sont quatre fois plus performants que les méthodes précédentes à faible écart lorsqu’ils sont appliqués à des problèmes réels de planification de mouvements robotiques », explique Rusch.
« Les séquences traditionnelles à faible écart constituaient une avancée majeure à leur époque, mais le monde est devenu plus complexe et les problèmes que nous résolvons aujourd’hui existent souvent dans des espaces à 10, 20 ou même 100 dimensions », explique Daniela Rus, directrice du CSAIL et professeure de génie électrique et d’informatique au MIT. « Nous avions besoin de quelque chose de plus intelligent, qui s’adapte à mesure que la dimensionnalité augmente. Les GNN constituent un changement de paradigme dans la génération de points à faible écart. Contrairement aux méthodes traditionnelles, où les points sont générés indépendamment, les GNN permettent aux points de « discuter » entre eux pour réduire le regroupement et les écarts – des problèmes courants avec les approches classiques. »
À l’avenir, l’équipe prévoit de rendre les points MPMC encore plus accessibles, en s’attaquant à la limitation actuelle de la formation d’un nouveau GNN pour chaque nombre fixe de points et de dimensions.
« Une grande partie des mathématiques appliquées utilise des quantités qui varient continuellement, mais le calcul nous permet généralement d’utiliser uniquement un nombre fini de points », explique Art B. Owen, professeur de statistiques à l’Université de Stanford, qui n’a pas participé à la recherche. « Le domaine des divergences, vieux de plus d’un siècle, utilise l’algèbre abstraite et la théorie des nombres pour définir des points d’échantillonnage efficaces. Cet article utilise des réseaux de neurones graphiques pour trouver des points d’entrée présentant un faible écart par rapport à une distribution continue. Cette approche se rapproche déjà beaucoup des ensembles de points à faible écart les plus connus dans les petits problèmes et se révèle très prometteuse pour une intégrale à 32 dimensions issue de la finance computationnelle. Nous pouvons nous attendre à ce que ce soit le premier d’une longue série d’efforts visant à utiliser des méthodes neuronales pour trouver de bons points d’entrée pour le calcul numérique. »
Rusch et Rus ont rédigé l’article avec Nathan Kirk, chercheur à l’Université de Waterloo, Michael Bronstein, professeur d’IA DeepMind à l’Université d’Oxford et ancien affilié du CSAIL, et Christiane Lemieux, professeure de statistiques et de sciences actuarielles à l’Université de Waterloo. Leurs recherches ont été soutenues, en partie, par le programme AI2050 de Schmidt Futures, Boeing, le laboratoire de recherche de l’armée de l’air américaine et l’accélérateur d’intelligence artificielle de l’armée de l’air américaine, la Fondation nationale suisse, le Conseil de recherches en sciences naturelles et en génie du Canada, et une bourse de recherche de pointe EPSRC Turing AI.
