Le philosophe allemand Friedrich Nietzsche a déjà dit que « les fils invisibles sont les liens les plus forts ». Ces « fils invisibles » peuvent être imaginés comme des liens reliant des objets apparentés, comme les maisons sur l’itinéraire d’un livreur, ou des entités plus nébuleuses, telles que les transactions dans un réseau financier ou les utilisateurs dans un réseau social.
Julian Shun, informaticien, étudie ces types de connexions multifacettes mais souvent invisibles en utilisant des graphes, où les objets sont représentés par des points, ou des sommets, et les relations entre eux sont modélisées par des segments de ligne, ou des arêtes.
En tant que professeur agrégé nouvellement titularisé au Département de génie électrique et d’informatique, Shun conçoit des algorithmes de graphes qui pourraient être utilisés pour trouver le chemin le plus court entre les maisons sur l’itinéraire du livreur ou détecter les transactions frauduleuses effectuées par des acteurs malveillants dans un réseau financier.
Avec le volume croissant de données, ces réseaux incluent désormais des milliards, voire des billions d’objets et de connexions. Pour trouver des solutions efficaces, Shun construit des algorithmes haute performance qui tirent parti de l’informatique parallèle pour analyser rapidement même les graphes les plus énormes. Comme la programmation parallèle est réputée difficile, il développe également des cadres de programmation conviviaux qui facilitent l’écriture d’algorithmes de graphes efficaces pour les autres.
Ces algorithmes sont fréquemment utilisés dans les systèmes de recommandation en ligne. Recherchez un produit sur un site de commerce électronique et vous verrez rapidement une liste d’articles connexes que vous pourriez également ajouter à votre panier. Cette liste est générée à l’aide d’algorithmes de graphes qui tirent parti du parallélisme pour trouver rapidement des articles connexes à travers un vaste réseau d’utilisateurs et de produits disponibles.
En tant qu’adolescent, l’expérience de Shun avec les ordinateurs se limitait à un cours de lycée sur la création de sites web. Plus intéressé par les mathématiques et les sciences naturelles que par la technologie, il avait l’intention de se spécialiser dans l’une de ces matières lorsqu’il s’est inscrit en tant qu’étudiant de premier cycle à l’Université de Californie à Berkeley.
Mais pendant sa première année, un ami lui a recommandé de suivre un cours d’introduction à l’informatique. Bien qu’il ne sache pas à quoi s’attendre, il a décidé de s’inscrire.
« Je suis tombé amoureux de la programmation et de la conception d’algorithmes. J’ai donc changé pour l’informatique et je n’ai jamais regardé en arrière », se souvient-il.
Ce cours initial d’informatique était à son propre rythme, donc Shun a appris la plupart du matériel lui-même. Il a apprécié les aspects logiques du développement d’algorithmes et la boucle de rétroaction courte des problèmes informatiques. Shun pouvait saisir ses solutions dans l’ordinateur et voir immédiatement s’il avait raison ou tort. Et les erreurs dans les mauvaises solutions le guideraient vers la bonne réponse.
« J’ai toujours pensé que c’était amusant de construire des choses, et en programmation, vous construisez des solutions qui font quelque chose d’utile. Cela m’a plu », ajoute-t-il.
Après son diplôme, Shun a passé un certain temps dans l’industrie mais a rapidement réalisé qu’il voulait poursuivre une carrière universitaire. À l’université, il savait qu’il aurait la liberté d’étudier des problèmes qui l’intéressaient.
Il s’est inscrit comme étudiant diplômé à l’Université Carnegie Mellon, où il a concentré ses recherches sur les algorithmes appliqués et l’informatique parallèle.
En tant qu’étudiant de premier cycle, Shun avait suivi des cours sur les algorithmes théoriques et les cours de programmation pratique, mais les deux mondes ne se sont pas connectés. Il souhaitait mener des recherches combinant théorie et application. Les algorithmes parallèles étaient parfaits pour cela.
« Dans le calcul parallèle, il faut se soucier des applications pratiques. L’objectif du calcul parallèle est d’accélérer les choses dans la vie réelle, donc si vos algorithmes ne sont pas rapides en pratique, ils ne sont pas si utiles », explique-t-il.
À Carnegie Mellon, il a été introduit aux ensembles de données de graphes, où les objets dans un réseau sont modélisés comme des sommets connectés par des arêtes. Il a été attiré par les nombreuses applications de ces types de jeux de données et par le problème complexe de développer des algorithmes efficaces pour les gérer.
Après avoir terminé un postdoctorat à Berkeley, Shun a cherché un poste de professeur et a décidé de rejoindre le MIT. Il avait collaboré avec plusieurs membres du corps professoral du MIT sur des recherches en informatique parallèle et était ravi de rejoindre un institut avec une telle diversité d’expertise.
Dans l’un de ses premiers projets après avoir rejoint le MIT, Shun s’est associé à Saman Amarasinghe, professeur au Département de génie électrique et d’informatique et membre du CSAIL, pour développer un cadre de programmation pour le traitement de graphes appelé GraphIt. Ce cadre facile à utiliser, qui génère un code efficace à partir de spécifications de haut niveau, était environ cinq fois plus rapide que l’approche suivante.
« Cette collaboration a été très fructueuse. Je n’aurais pas pu créer une solution aussi puissante si j’avais travaillé seul », dit-il.
Shun a également élargi son focus de recherche pour inclure des algorithmes de regroupement, qui cherchent à regrouper des points de données apparentés. Lui et ses étudiants construisent des algorithmes et des cadres parallèles pour résoudre rapidement des problèmes de regroupement complexes, qui peuvent être utilisés pour des applications telles que la détection d’anomalies et la détection de communautés.
Récemment, lui et ses collaborateurs se sont concentrés sur des problèmes dynamiques où les données dans un réseau de graphes changent avec le temps.
Lorsqu’un ensemble de données comporte des milliards ou des billions de points de données, exécuter un algorithme à partir de zéro pour apporter un petit changement pourrait être extrêmement coûteux du point de vue informatique. Lui et ses étudiants conçoivent des algorithmes parallèles qui traitent de nombreuses mises à jour en même temps, améliorant l’efficacité tout en préservant la précision.
Mais ces problèmes dynamiques posent également l’un des plus grands défis sur lesquels Shun et son équipe doivent travailler pour les surmonter. Comme il y a peu d’ensembles de données dynamiques disponibles pour tester les algorithmes, l’équipe doit souvent générer des données synthétiques qui pourraient ne pas être réalistes et pourraient entraver les performances de leurs algorithmes dans le monde réel.
Au final, son objectif est de développer des algorithmes de graphes dynamiques qui se comportent efficacement en pratique tout en respectant des garanties théoriques. Cela garantit qu’ils seront applicables dans une large gamme de paramètres, dit-il.
Shun s’attend à ce que les algorithmes parallèles dynamiques aient encore plus de focus de recherche à l’avenir. À mesure que les ensembles de données continuent de devenir plus grands, plus complexes et plus changeants, les chercheurs devront concevoir des algorithmes plus efficaces pour suivre le rythme.
Il s’attend également à ce que de nouveaux défis proviennent des avancées en technologie informatique, car les chercheurs devront concevoir de nouveaux algorithmes pour tirer parti des propriétés des nouveaux matériels.
« C’est la beauté de la recherche – j’ai la possibilité d’essayer de résoudre des problèmes que d’autres n’ont pas encore résolus et de contribuer quelque chose d’utile à la société », conclut-il.
En savoir plus : https://news.mit.edu/2024/julian-shun-solves-complex-problems-efficiently-1004
