ALGORITHMIQUE, APPRENTISSAGE ET IA un Janus à trois visages ou un mariage à trois ?

Par Dominique Barth
 

A quoi sert l’algorithmique ? De façon simple, à savoir appréhender formellement un problème, à rendre un système informatique capable soit d’analyser des données (reconnaître, catégoriser par similarité,…), soit de prendre une décision à partir des données fournies (dimensionner, piloter, optimiser,…). En pratique, quand le problème est bien défini et que l’ensemble des données d’entrée possibles est circonscrit, un algorithme de résolution spécifique est souvent la meilleure approche à adopter même dans le cas de problèmes complexes. Mais quand les contours du problème sont difficiles à cerner, que les données sont massives, mal connues, dynamiques, il peut être plus efficace d’avoir recours à des techniques d’apprentissage qui ont pour but d’apprendre à un algorithme à résoudre le mieux possible un problème, soit à partir de cas déjà résolus, soit en apprenant sur le tas.

Historiquement, dans ce contexte l’intelligence artificielle, domaine de recherche en informatique, a proposé d’utiliser les réseaux de neurones pour l’analyse de données, en particulier pour le traitement d’images ou de signal. Les réseaux de neurones sont ici considérés comme des modèles de calcul algorithmique. Après une période sans grands succès pour cette approche, la mise à disposition par certains acteurs privés de moyens de calcul importants a permis l’émergence d’applications réelles des réseaux de neurones, principalement donc pour des problèmes qui ont une certaine analogie avec l’analyse d’images. Les réseaux de neurones qui ont pu ainsi être développés ont permis non seulement une analyse de données efficace pour un ensemble croissant de domaines d’application, mais aussi de réaliser par eux-mêmes le meilleur paramétrage offline des couches des réseaux réalisant l’analyse de données (l’aspect profond du Deep Learning), paramétrage qui devait auparavant être fourni par le programmeur en amont du réseau de neurones. Ces approches nécessitent très souvent la disponibilité d’une grande quantité de données qualifiées pour entraîner ces réseaux (qualification souvent réalisée par l’emploi d’une main-d’œuvre peu qualifiée dans des pays à faible niveau de rémunération). Les performances incontestables de ces réseaux de neurones profonds, souvent obtenus grâce à des capacités de calcul massif, ont mis à mal d’autres approches spécifiques à chaque application abordée, ce qui a pu laisser penser que l’apprentissage profond pouvait permettre à un informaticien sans expertises précises ni en algorithmique, ni en Machine Learning, de pouvoir résoudre de façon générique n’importe quel problème. Une autre conséquence est que la notion d’intelligence artificielle a aujourd’hui dépassé son cadre initial centré sur les réseaux de neurones, pour s’étendre à l’utilisation de différentes techniques d’apprentissage, voire même à l’algorithmique toute entière ! Sans éviter les querelles de chapelles que cela entraîne, notamment quand nombre de marchés et sources de financement actuels sont, par principe, étiquetés « IA ».

Considérons un problème algorithmique classique et historique, la coloration de graphes où, étant donné un graphe, le but est de déterminer une coloration de sommets avec un nombre minimum de couleurs sans que deux sommets liés aient la même couleur. Ce problème étant NP-complet et inapproximable dans le cas général, la première approche peut consister à concevoir des heuristiques de coloration, basées par exemple sur la recherche de sous-graphes denses. Une approche par apprentissage profond consisterait à disposer d’une très grande quantité de graphes colorés de façon minimale (pour permettre l’apprentissage du réseau de neurones), afin d’obtenir une classification de graphes en fonction du nombre minimum de couleurs nécessaire et de caractéristiques structurelles ; ensuite, il suffirait pour un graphe candidat de déterminer la classe à laquelle il appartient pour connaître son nombre de couleurs minimum. De telles approches ont été étudiées sans grands succès voici quelques dizaines d’années. Une troisième approche possible consiste à l’utilisation d’une méthode d’apprentissage par renforcement : chaque sommet choisit une couleur parmi un nombre de couleurs possibles (ses stratégies) selon un vecteur stochastique qui évolue en fonction des conflits que ce choix entraîne avec les choix des autres sommets. En itérant ces choix simultanés, l’objectif est de faire émerger simultanément un ensemble de bons choix pour l’ensemble des sommets.

L’approche par apprentissage profond pourrait à tort donner l’impression qu’aucune compétence en algorithmique de graphes n’est requise pour l’utilisateur. Dans le cas de l’apprentissage par renforcement, une telle compétence est primordiale pour définir la meilleure mise à jour du vecteur stochastique. Dans tous les cas, l’approche heuristique reste en général la plus efficace.

Mais plutôt que de mettre de telles approches en compétition, le bon réflexe est de pouvoir les combiner : une heuristique spécifique (par exemple un algorithme de recherche locale), prenant comme entrée une situation obtenue par apprentissage par renforcement, et dont le paramétrage serait guidé par une analyse de cas par apprentissage par réseaux de neurones. La clef de résolution de nombreux problèmes est très certainement dans la capacité de pouvoir au mieux combiner ces différentes approches, qui chacune ont une base et un besoin algorithmique spécifique. Pour ce faire, et bien loin de certaines idées reçues qui se répandent, l’action d’algorithmiciens compétents, formés à toutes ces approches, reste un élément déterminant. 

Biograhie de l'auteur

 Dominique Barth est Professeur de l'Université de Versailles - St Quentin depuis 1999. Il y dirige la laboratoire "DAVID : Données et Algorithmes pour la Ville Intelligente et Durable" et la fédération de recherche "SIHS : Sciences Informatiques, Humaines et Sociales" du CNRS. Il est aussi responsable du science-Lab de l'université "Versailles Sciences Lab". Son expertise de recherche concerne l'algorithmique de graphes, l'optimisation et la théorie algorithmique des jeux, avec des domaines d'application divers comme les télécommunications, l'analyse moléculaire ou la mobilité urbaine.