TukTukDesign/Pixabay
Claire Mathieu, École Normale Supérieure (ENS)
Claire Mathieu est directrice de recherche au Centre national de la recherche scientifique. Elle travaille au Département d’Informatique de L’École normale supérieure et à l’Irif, Université Paris-Diderot. Elle est la toute nouvelle titulaire de la Chaire « Informatique et sciences numériques » du Collège de France où elle présente un cours intitulé « Algorithmes » (leçon inaugurale aujourd’hui, le 16 novembre 2017). Les algorithmes fascinent, peuvent inquiéter, prennent une place considérable dans nos vies. Il nous faut mieux les comprendre pour qu’ils fassent ce que nous voulons. Entrons avec Claire Mathieu, parmi les meilleurs spécialistes mondiaux du domaine, dans leur monde merveilleux. Cet article est publié en collaboration avec le blog Binaire, où Claire est aussi une éditrice invitée fidèle.
Les algorithmes, quand ils sont bien conçus car bien compris, contribuent au bien social et sont un outil de transformation de la société. Ils y prennent une place grandissante, que ce soit pour des applications informatiques telles que gérer efficacement des données, pour les transmettre rapidement et de façon fiable, pour faire des calculs, pour optimiser l’allocation de tâches, ou de plus en plus pour des usages en société comme le calcul d’itinéraire, les recommandations de lectures ou de films, l’affectation des étudiants avec APB, etc.
Très souvent, ces algorithmes sont opaques, mystérieux, voire effrayants. Comment marchent-ils ? Quelles sont les étapes du calcul ou de la prise de décision ? Pourquoi marchent-ils ? Quelles sont les propriétés mathématiques qui expliquent leurs performances ? Le « comment » et le « pourquoi » sont les deux facettes de l’étude des algorithmes : la conception (comment ça marche) et l’analyse (pourquoi ça marche).
En général, l’analyse d’algorithmes sert d’abord à montrer qu’un algorithme résout correctement un problème, puis qu’il le fait en un temps raisonnable, de façon fiable et en restant économe en ressources.
Un sous-domaine fondamental largement développé depuis une vingtaine d’années concerne les algorithmes d’approximation. Un tel algorithme, plutôt que de rechercher une solution exacte et précise, se contente d’une solution approchée. On les utilise pour résoudre les problèmes trop difficiles pour être résolus complètement en un temps raisonnable. On s’autorise alors à accepter des solutions dont la valeur serait, disons, à 5 % de la valeur optimale. Par exemple, prenons le problème de la livraison de marchandises. Comment optimiser les trajets d’un camion qui doit livrer des marchandises, connaissant le lieu de l’entrepôt, les lieux et volumes des commandes des clients, ainsi que la capacité du camion ? C’est un problème difficile lorsque le nombre de clients est élevé et on ne sait le résoudre que dans des cas particuliers qui ne correspondent pas toujours aux applications réelles rencontrées : aujourd’hui, même dans les cas les plus simples, calculer une solution approchée à 1 % prend un temps déraisonnable. L’un de nos axes de recherche est donc de continuer à développer et d’améliorer ces algorithmes d’approximation.
Modélisation mathématique et évolutions technologiques
#tembelone, CC BY
Pour les chercheurs qui comme moi travaillent en informatique théorique, l’élément non négociable est la recherche du théorème. Les problèmes sont variés, les méthodes de résolution aussi, mais à la fin, ce qui est produit, ce qui apparaît dans le paragraphe intitulé « nos résultats » dans nos introductions, est toujours un théorème. La rigueur mathématique prime. C’est un principe de base.
Cependant, avec les évolutions technologiques, de nouvelles problématiques surgissent et se traduisent de façon naturelle par des évolutions des questions mathématiques étudiées. Ainsi, les modèles de calcul évoluent, avec par exemple de plus en plus de modèles de calcul ou de communication qui limitent l’accès aux données (par exemple, dans le modèle du flux de données, l’utilisateur voit toute une suite d’informations défiler devant lui, par exemple des paquets transitant sur un réseau. Bien qu’il n’ait pas suffisamment de place en mémoire pour garder toutes les informations vues, il souhaite cependant calculer des informations statistiques sur ce flux), ou dont les données évoluent de façon dynamique, ou encore avec une incertitude sur les données (par exemple, les avis lus sur Internet sur la qualité d’un restaurant, d’un hôtel ou d’un médecin sont notoirement peu fiables, et contiennent pourtant des informations précieuses.)
Il nous faut donc non seulement travailler sur des problèmes reconnus du domaine, mais également proposer des problèmes algorithmiques nouveaux. Il s’agit de définir une question algorithmique de façon formelle, qui soit suffisamment simple dans sa structure pour que l’on puisse l’étudier avec un espoir de démontrer des résultats rigoureux. C’est ainsi qu’on peut rigoureusement démontrer l’effet de « petit monde » dans les réseaux sociaux (soit le nombre limité de degrés de séparation entre tous ses membres) : bien que leur taille aille grandissant, il demeure toujours possible à un membre du réseau social de prendre contact avec presque n’importe quel autre membre grâce à une courte chaîne de connaissances. Ici, la démonstration mathématique se fait sur un modèle simplifié, inspiré du modèle dit « de feu de forêt ». C’est en passant par ce type de modèles simplifiés que l’on peut espérer arriver à des intuitions pour une meilleure compréhension du monde.
« Pourquoi » et « Dans quel but » : des questions d’éthique
#tembelone, CC BY
Par ailleurs, comme les algorithmes agissent de plus en plus non seulement sur de simples octets mais également sur les personnes, les questions d’éthique comme l’équité ou la transparence deviennent prégnantes.
Une constante du domaine est qu’un algorithme est développé dans un but précis et analysé en relation avec la façon dont il atteint son but. Mais ces années dernières ont vu apparaître des algorithmes qui résolvent un problème imprécis, et qui ne « marchent » que dans un sens très flou – le choix d’informations à présenter au lecteur en ligne ou les recommandations de produits à acheter, par exemple. Qu’est-ce qui fait qu’une sélection donnée est le meilleur choix ? Un résultat donné est-il, ou non, satisfaisant ? Quel est le but recherché ? Ces questions sont à la périphérie de l’algorithmique classique et en même temps centrale pour l’évolution du domaine dans la décennie à venir.
Un des nouveaux enjeux de l’algorithmique est donc comprendre le « pourquoi » et le « dans quel but » des algorithmes de la famille des méthodes d’« apprentissage profond », qui se retrouvent appliqués un peu partout avant qu’on ait vraiment compris leurs aspects fondamentaux. Ici, la théorie a pris du retard sur la pratique, et ce retard de compréhension induit des risques de manipulation sans contrôle.
Il ne faut pas avoir peur des algorithmes, mais il faut apprendre à les connaître pour les apprivoiser : c’est la mission de l’algorithmique.
Dans le cadre de la chaire annuelle « Informatique et sciences numériques », leçon inaugurale au Collège de France le jeudi 16 novembre 2017 à 18h, cours les mardis à 10h à partir du 24 novembre.
Claire Mathieu, Professeur attaché au département d’informatique de l’ENS et directrice de recherche CNRS (équipe Talgo), École Normale Supérieure (ENS)
La version originale de cet article a été publiée sur The Conversation.
