A la une
Bien qu’on utilise couramment ce terme, que désigne vraiment un « algorithme » ? En se plongeant dans l’histoire de son utilisation, les chercheurs ont constaté une évolution dans son usage et surtout l’absence d’une définition formelle de ces objets manipulés par de nombreux scientifiques. Alberto Naibo, Thomas Seiller et leurs collègues proposent une manière de les définir, basées sur les graphes, qui permet à tout un chacun de s’interroger sur l’utilisation du mot « algorithme ».
Art généré de façon algorithmique. © Jeux_Mathinfo (Pixabay)
Algorithmes de recommandations, algorithmes de reconnaissance faciale, algorithmes de navigation GPS... Les « algorithmes » semblent omniprésents dans nos vies. Mais que sont-ils vraiment ? « On entend parler d’algorithmes partout, mais quand on demande - même à un expert - de définir ce que c’est, la définition est plutôt informelle », constate Alberto Naibo, enseignant-chercheur à l’Institut d'Histoire et de Philosophie des Sciences et des Techniques (IHPST)1. Généralement, on a en tête qu’un algorithme est une procédure faite d’étapes à suivre pour aboutir à un résultat. Dans ce contexte, faire une règle de trois est un algorithme. Car peu importe ce qu’on calcule, on doit suivre la procédure d’une multiplication suivie d’une division. Mais plus on s’interroge sur les contours de cette définition et plus elle se trouble : est-ce qu’un système d’intelligence artificielle est un algorithme ? Quelle est la différence entre un algorithme et un programme ? Est-ce qu’un algorithme doit forcément être implémenté sur un ordinateur ?
En réalité, la définition proposée a quelque chose d’insatisfaisant : elle est trop vague. Pour les mathématiciens et informaticiens, il est difficile d’étudier les algorithmes dans ce cadre et surtout sans une définition « formelle », c’est-à-dire basée sur les mathématiques. « Le fait qu’on n’ait pas de telle définition montre un manque de recul sur les objets qu’on manipule », analyse Thomas Seiller, chercheur au Laboratoire d'Informatique de Paris-Nord (LIPN)2. Mais dans le cadre du projet ANR « La géométrie des algorithmes », Alberto Naibo, Thomas Seiller et leurs collègues - dont Walter Dean, l’un des premiers philosophes à s’interroger sur le statut des algorithmes - ont formalisé une définition des algorithmes basée sur la notion de graphes. Ils espèrent que cela précisera le débat sur le numérique et l’IA.
Le projet a débuté avec les réflexions de Thomas Seiller, qui s’est plongé dans les fondements de la théorie de la calculabilité. « Cette théorie des années 1920 n’est pas informatique mais mathématique, elle ne s'intéresse qu’à ce qu’il est possible de calculer et pas à la manière de faire », précise-t-il. Plutôt que de regarder les différentes méthodes pour trier un jeu de cartes, la théorie de la calculabilité s’intéresse à savoir si le tri est possible ou non.
Le chercheur a alors constaté le manque de définition formelle d’une notion centrale : un modèle de calcul, c’est-à-dire une machine qui effectue des opérations comme un ordinateur à la différence près qu’elle n’existe que théoriquement. « Cela a été le point de départ de la discussion avec Alberto Naibo », retrace Thomas Seiller. De fil en aiguille, ils ont été confrontés à la notion d’algorithme et les limites de sa définition. En effet, algorithmes et modèles de calcul sont souvent utilisés comme synonymes dans la littérature. Or pour eux, cette correspondance ne marche pas.
Les algorithmes ont des centaines d’années
Pour le comprendre, il faut remonter le temps. Les algorithmes voient le jour dans les travaux des mathématiciens arabes, notamment dans ceux d’Al-Khwârizmî aux VIIIe et IXe siècles. Il s’agit alors de procédures de calcul basées sur la position des chiffres de chaque nombres - comme ce qu’on fait en posant une addition.
« Puis, l’usage commence à devenir plus large. L’algorithme devient une méthode plus générale où on suit des règles pour résoudre des problèmes, qui n’a plus de lien avec la représentation des nombres », poursuit Alberto Naibo. La règle de trois est donc un algorithme par exemple : il s’agit d’une méthode pour trouver une quatrième proportionnelle, peu importe comment nous faisons la multiplication ou la division.
La théorie de la calculabilité produit un nouveau glissement dans la notion d’algorithme. La représentation des objets redevient ici essentielle. Pour que la machine théorique implémente une règle de trois, il faut lui décrire ce qu’est un nombre. Il faut transformer l’entier en un objet manipulable par la machine - un ensemble de 0 et de 1 par exemple. Ainsi, en associant “algorithme” et “modèle de calcul” la généralité est perdue, il faut tout représenter et préciser.
« Vous voyez, quand on commence à rentrer dans les détails, on sait vraiment plus ce qu'est un algorithme ! », met en évidence Alberto Naibo. Au fil des années, les visions de ce qu’est un algorithme divergent. La notion qui paraît triviale au départ montre toute l'ambiguïté de sa définition. Avec ses collègues, ils ont tenté de l’éclaircir. « Si je regarde tous ces usages, ils ont quand même quelque chose en commun : l’idée qu’un algorithme c’est une liste d’instructions structurées pour exécuter une tâche », décrit Alberto Naibo. Un algorithme n’est pas qu’une procédure mécanique aveugle, il a une finalité.
Des graphes pour orchestrer la procédure
« Et cela, mathématiquement, il est possible de le représenter ! », annonce-t-il. Inspirés par leurs définitions formelles de modèle de calcul et de programme, les chercheurs se servent de la notion de graphes pour expliciter la notion d’algorithme. Un graphe, c’est un ensemble de points reliés entre eux par des lignes appelées arêtes. « Il nous a fallu plusieurs itérations avant de trouver la bonne structure, mais dès la première il semblait que le graphe capture quelque chose qui ressemble à un algorithme », apprécie Thomas Seiller.
En effet, le graphe permet de représenter la chronologie des instructions de l’algorithme. Ici, les points sont les espaces dans lesquels les instructions agissent - les entiers positifs par exemple. Les arêtes reliant ces points décrivent la transformation que ces objets subissent une addition ou une multiplication par exemple.
Si on reprend l’exemple de la règle de trois, au départ nous sommes sur le sommet 1 (le cercle bleu le plus à gauche) qui représente l’ensemble fait de triplets de nombres réels, (a,b,c). L’arête 1 (la première flèche rouge) transforme la première position du triplet en le produit de a par b. Le sommet 2 est donc l’ensemble des triplets (a × b, b,c). L’arête 2 transforme enfin la première position en divisant par c. Il ne reste plus qu’à retourner la solution de la règle de trois, (a × b):c. © Marie Rossolini
Mais tous les graphes ne sont pas aussi simples et linéaires que celui de la règle de trois. Ces deux exemples d’algorithmes de calcul du plus grand diviseur commun (PGCD) illustrent des exemples de graphes plus sophistiqués. © Alberto Naibo / IHPST / CNRS
Dans ce cadre, il faut que tous les éléments qui entrent en jeu (les nombres ou les opérations par exemple) soient définis mathématiquement, par un système d’axiomes. Il faudra par contre décrire tous ces éléments au moment d'implémenter l'algorithme, au moment de le transformer en programme informatique. « Cette définition capture bien l’idée intuitive qu’on se fait d’un algorithme notamment du fait du lien avec la notion de programme. Ici, l’algorithme est quelque part une description plus ou moins précise de ce qu'on attend d’un programme. C’est à peu près l’idée qu’on s’en fait en tant qu’informaticien », apprécie Thomas Seiller.
Les systèmes d’IA sont-ils des algorithmes ?
Avec une telle définition, il devient plus facile d’utiliser correctement le terme d’algorithme. En particulier, ils permettent de voir différemment les systèmes d’IA et leurs limites. La version la plus courante de l’IA aujourd’hui est l'apprentissage automatique, c’est-à-dire un système qui apprend à accomplir une tâche à partir de données. Par exemple, il peut apprendre à distinguer les chats des chiens après avoir vu des milliers de photos de ces deux animaux. Cette méthode est singulière dans la programmation car le programme est obtenu directement, sans étape préliminaire de conception d’un algorithme et sa traduction en langage informatique. « Avec le machine learning, il nous manque l’algorithme, on n’y a pas accès. Cela implique qu’on n’a aucune garantie sur ce qu’il fait vraiment », souligne Thomas Seiller. Le programme est lui bien trop compliqué pour être analysé.
Pourtant le terme d’algorithme a tendance à se diffuser dans le monde de l’IA pour désigner de façon générique les systèmes d’IA - comme les algorithmes de recommandations. « Certains diront que c’est la notion d’algorithme qui est en train d’évoluer avec l’IA et qu’on a une vision traditionaliste. Mais je ne suis pas d’accord : l’IA transforme la notion d’algorithme en quelque chose qui est presque incomparable avec ce qu’était un algorithme avant », souligne Alberto Naibo.
En tout cas, par leurs travaux les chercheurs espèrent bien nous pousser à réfléchir quant à l’usage du mot d’algorithme. « Le mot algorithme est aujourd’hui un mot fort qu’on emploie pour faire passer une idéologie. Certains l'emploient pour faire peur, pour faire passer une certaine dystopie de notre monde. Tandis que d’autres en parlent sous un angle positif, prétextant qu’ils pourraient améliorer notre vie, analyse Alberto Naibo. Nous ne souhaitons pas faire de la notion d’algorithme une notion idéologique, mais plutôt scientifique. Un algorithme est avant tout un objet mathématique ». Cela n’aurait pas de sens de dire « la multiplication nous protège » simplement parce que des protocoles de cybersécurité l’utilisent. C'est la même chose pour les algorithmes : dire qu’ils nous menacent ou nous protègent est une aberration car on parle d’un objet mathématique.
« Par nos travaux, nous espérons mettre la puce à l’oreille sur l’usage du mot algorithme qui devrait être un peu plus surveillé », ajoute le philosophe. Bien nommer les choses, c’est une première étape essentielle pour clarifier le débat autour de l’éthique et de l’intelligence artificielle.
-----------------------------------------------------------------------------------------------------------------------
Ces recherches ont été financées tout ou en partie par l’Agence Nationale de la Recherche (ANR) au titre du projet « La géométrie des algorithmes », par la Mission pour les initiatives transverses et interdisciplinaires (MITI) du CNRS au titre du projet « Algorithms: a formalisation and its impact », et par l’Agence Nationale de la Recherche (ANR) au titre du projet « Dynamical Systems and Computation ».