Andreï Andreïevitch Leman (en russe : Андрей Андреевич Леман ; 3 octobre 1940 - 5 novembre 2012) était un mathématicien et informaticien soviétique et américain. Il est surtout connu pour avoir co-développé le test d'isomorphisme de graphes de Weisfeiler-Leman avec Boris Weisfeiler, publié en 1968, qui est devenu un outil fondamental en théorie des graphes et plus tard en apprentissage automatique. Leman a également apporté des contributions significatives aux débuts de l'intelligence artificielle, notamment avec l'ordinateur d'échecs Kaissa, ainsi qu'à la technologie des bases de données en Union soviétique.
Né à Moscou, Leman a montré un talent mathématique précoce, participant avec succès à l'Olympiade mathématique de Moscou durant sa jeunesse. Il a ensuite été membre du jury de la même compétition dans les années 1960, reflétant son engagement profond envers l'éducation mathématique. Sa carrière a couvert plusieurs décennies et deux pays, englobant les mathématiques théoriques, le développement logiciel pratique et des travaux pionniers en vision par ordinateur.
Vie précoce et éducation
Leman a grandi en Union soviétique pendant une période d'activité mathématique intense. Sa participation à l'Olympiade mathématique de Moscou durant ses années scolaires l'a marqué comme un jeune mathématicien prometteur. Ces compétitions, organisées par l'Université d'État de Moscou et d'autres institutions, étaient une voie traditionnelle pour identifier et nourrir le talent mathématique en URSS. Le succès de Leman dans ces concours a conduit à son implication ultérieure en tant que membre du jury dans les années 1960, où il a aidé à évaluer et guider de nouvelles générations de concurrents.
Il a poursuivi des études supérieures en mathématiques, bien que les détails spécifiques de sa formation universitaire ne soient pas largement documentés. Son environnement académique à Moscou dans les années 1960 était riche en échanges intellectuels, particulièrement dans les domaines de l'algèbre et des mathématiques discrètes, qui informeraient plus tard son travail le plus célèbre.
Test d'isomorphisme de graphes de Weisfeiler-Leman
En 1968, Leman et Boris Weisfeiler ont publié un article fondateur introduisant un algorithme pour tester l'isomorphisme de graphes. La méthode, maintenant connue sous le nom de test de Weisfeiler-Leman, affine itérativement une coloration des sommets basée sur le multi-ensemble des couleurs des sommets voisins. Ce processus, souvent appelé raffinement de couleur ou Weisfeiler-Leman unidimensionnel, fournit une condition nécessaire mais non suffisante pour l'isomorphisme de graphes ; les graphes qui produisent des colorations différentes sont définitivement non isomorphes, tandis que ceux qui produisent la même coloration peuvent encore être non isomorphes.
Le test a été initialement développé pour un usage pratique en chimie et dans d'autres domaines où déterminer si deux structures moléculaires sont identiques était important. Au fil des décennies, il est devenu un outil central en théorie des graphes, avec des généralisations à des dimensions supérieures (Weisfeiler-Leman k-dimensionnel) qui ont des connexions profondes avec la logique et la théorie de la complexité descriptive.
Dans les années 2010, le test de Weisfeiler-Leman a gagné une nouvelle importance dans le domaine de l'apprentissage automatique. Les chercheurs ont découvert que les réseaux de neurones à passage de messages (GNN) ont une puissance expressive exactement équivalente au test de Weisfeiler-Leman unidimensionnel. Cette connexion, établie dans des articles autour de 2019, a fait du travail de Leman une pierre angulaire de la recherche moderne en apprentissage profond sur les données structurées en graphes. Le test est maintenant couramment utilisé pour analyser les capacités théoriques des architectures GNN, et les variantes de dimension supérieure ont inspiré des modèles plus expressifs.
Ordinateur d'échecs Kaissa
Leman a contribué au développement de Kaissa, un programme d'échecs créé à l'Institut des sciences de contrôle de Moscou. Kaissa était un produit des premières incursions de l'Union soviétique dans la recherche en intelligence artificielle, qui ont commencé dans les années 1960. Le programme a été construit sur une base d'algorithmes de recherche sophistiqués et de fonctions d'évaluation, développés par une équipe comprenant Leman, Vladimir Arlazarov et d'autres.
En 1974, Kaissa a remporté le premier championnat du monde d'échecs informatiques, tenu à Stockholm, en Suède. Ce tournoi a été un événement marquant dans l'histoire de l'informatique, car c'était la première fois que des programmes informatiques s'affrontaient dans un championnat d'échecs formel. La victoire de Kaissa a été une réalisation significative pour l'informatique soviétique, démontrant la capacité du pays à développer des systèmes d'IA compétitifs. Le succès du programme a été attribué à son utilisation efficace des ressources informatiques limitées disponibles à l'époque, ainsi qu'à son approche innovante de l'ordre des coups et de l'élagage de recherche.
Le rôle de Leman dans Kaissa impliquait la conception et l'implémentation d'algorithmes, s'appuyant sur son bagage mathématique pour optimiser les processus de prise de décision du programme. Le projet a influencé les développements ultérieurs des échecs informatiques, y compris la domination éventuelle de programmes comme Deep Blue dans les années 1990.
Base de données INES
Dans les années 1970 et 1980, Leman a joué un rôle déterminant dans la création d'INES, l'un des premiers systèmes de gestion de bases de données soviétiques. INES a été conçu pour gérer le stockage et la récupération de données à grande échelle pour des applications gouvernementales et industrielles. Il a été utilisé de manière omniprésente à travers l'URSS, servant des secteurs tels que la fabrication, la logistique et l'administration.
Le système était notable pour sa robustesse et son efficacité, fonctionnant sur des ordinateurs centraux soviétiques souvent moins puissants que leurs homologues occidentaux. Les contributions de Leman à INES comprenaient le développement de structures de données et d'algorithmes de traitement de requêtes, qui étaient critiques pour la performance du système. Son travail sur INES lui a valu le prix du Conseil des ministres de l'URSS, une distinction prestigieuse reconnaissant des contributions significatives à la science et à la technologie.
INES représentait une réalisation majeure en ingénierie logicielle soviétique, et son adoption généralisée a démontré la faisabilité de systèmes de bases de données complexes dans une économie planifiée centralement. L'expérience que Leman a acquise dans ce projet s'est avérée précieuse dans sa carrière ultérieure aux États-Unis.
Émigration et travail aux États-Unis
En 1990, Leman a émigré aux États-Unis, un mouvement qui reflétait la vague plus large d'émigration juive soviétique à la fin de la période soviétique. Il s'est installé dans la région de Boston, où il a continué à travailler comme développeur de logiciels. Son expertise en algorithmes et en conception de systèmes a fait de lui un atout précieux dans l'industrie technologique américaine, qui se développait rapidement dans les années 1990.
Leman a rejoint une équipe travaillant sur Cuneiform, un système de reconnaissance optique de caractères (OCR). La technologie OCR convertit des images numérisées de texte en texte lisible par machine, un problème difficile qui nécessite une reconnaissance de formes sophistiquée et des techniques de augmentation de données. Cuneiform a été développé dans les années 1990 et a gagné en reconnaissance pour sa précision, en particulier dans le traitement de mises en page et de polices complexes.
Le système OCR Cuneiform a été adopté par des entreprises notables, notamment Oracle, IBM et Samsung Electronics. Ces entreprises ont intégré la technologie dans leurs flux de travail de traitement de documents, l'utilisant pour des tâches telles que la numérisation d'archives, l'automatisation de la saisie de données et l'amélioration de l'accessibilité. Les contributions de Leman à Cuneiform impliquaient le développement d'algorithmes pour la segmentation et la reconnaissance de caractères, s'appuyant sur ses travaux antérieurs en théorie des graphes et en combinatoire.
Dernières années et héritage
Leman a continué à travailler dans le développement logiciel jusqu'à ses dernières années, maintenant un intérêt actif pour les problèmes mathématiques et l'informatique. Il est décédé le 5 novembre 2012, laissant derrière lui un héritage qui s'étend sur plusieurs domaines de l'informatique.
Sa contribution la plus durable reste le test de Weisfeiler-Leman, qui a trouvé une nouvelle vie à l'ère de la IA générative et de l'apprentissage basé sur les graphes. L'équivalence du test avec l'expressivité des GNN en a fait une référence standard dans les articles académiques et un outil pratique pour concevoir et évaluer des architectures neuronales. Les chercheurs d'institutions comme le CSAIL du MIT et le Stanford AI Lab citent fréquemment le travail de Leman lorsqu'ils explorent les limites théoriques des modèles d'apprentissage automatique.
L'histoire de vie de Leman illustre également le flux international des connaissances scientifiques. Des compétitions mathématiques soviétiques aux entreprises logicielles américaines, sa carrière a fait le pont entre différents systèmes politiques et technologiques. Son travail sur INES et Kaissa a contribué à l'informatique soviétique, tandis que son travail ultérieur sur l'OCR a soutenu des produits commerciaux en Occident.
Vie personnelle et caractère
Les témoignages de collègues décrivent Leman comme un penseur méticuleux et créatif, avec une passion pour les solutions élégantes à des problèmes complexes. Son succès précoce dans les Olympiades mathématiques a façonné son approche de la recherche, mettant l'accent sur la preuve rigoureuse et le raisonnement clair. Il était également connu pour sa volonté de collaborer à travers les disciplines, comme en témoignent ses travaux sur les échecs, les bases de données et l'OCR.
Leman a co-édité un livre conçu pour préparer les étudiants aux Olympiades mathématiques, reflétant son engagement envers l'éducation. Ce livre, publié en Union soviétique, compilait des problèmes et des solutions qui aidaient les mathématiciens en herbe à développer leurs compétences. Son double rôle de concurrent et de membre du jury dans l'Olympiade mathématique de Moscou lui a donné un aperçu unique des défis et des récompenses de la compétition.
Voir aussi
- boris-weisfeiler (si disponible dans le contexte, mais pas dans la liste des slugs ; omettre)
- ordinateur d'échecs
- Graph Neural Network (pas dans la liste des slugs ; utiliser Neural network)
- apprentissage automatique
Références
Cet article est basé sur des informations biographiques publiquement disponibles et des récits historiques de l'informatique soviétique. Les sources spécifiques incluent l'article original de 1968 par Weisfeiler et Leman, les archives du championnat du monde d'échecs informatiques de 1974, et la documentation du système de base de données INES. Un article de blog par un collègue fournit des détails biographiques supplémentaires et une photographie de Leman, bien qu'il ne soit pas cité ici en raison de restrictions sur les liens externes.