D’une simplicité déconcertante

Le 9 décembre 2009  - Ecrit par  Xavier Caruso Voir les commentaires (8)

Un problème étant posé, on dispose souvent de plusieurs méthodes pour le résoudre. Les plus naïves ne sont en général pas très efficaces, mais elles peuvent parfois l’être bien plus qu’on aurait pu le penser. Dans ce billet, quelques exemples qui, j’espère, vous étonneront !

Un problème étant posé, on dispose souvent de plusieurs méthodes — on dit parfois algorithmes lorsqu’elles ressemblent à une suite d’instructions très précises — pour le résoudre. Les plus naïves ne sont en général pas très efficaces, et il est souvent intéressant de réfléchir un peu avant de se lancer. Voici un exemple idiot : si l’on vous demande de calculer $13+13+13+13+13+13+13$, il vaut mieux commencer par transformer l’opération en une multiplication et poser cette dernière. On peut
dériver presque à l’infini ce type d’exemples, et il y a d’ailleurs toute une branche de l’informatique — appelée algorithmique — qui propose des solutions objectives pour évaluer les algorithmes et cherche à obtenir les plus efficaces.

Mais, de façon plus étonnante, il existe aussi des cas où une méthode a priori naïve [1] s’avère incroyablement efficace. Dans ce billet, j’aimerais vous montrer quelques exemples.

Le Master Mind

Comme tout billet n’est somme toute qu’une occasion supplémentaire donnée à l’auteur de raconter sa vie, c’est tout naturellement que je commence par une expérience personnelle.

Il y a quelques années, j’avais eu envie de programmer un solveur de Master Mind. Il ne s’agit pas de la version du Master Mind avec les couleurs que vous connaissez peut-être, mais d’une variante avec des mots dont voici la règle. Un meneur du jeu choisit un mot de cinq lettres dans lequel aucune lettre n’apparaît deux fois [2] et le garde secret. Les autres joueurs proposent ensuite des mots. Pour chacun d’eux, le meneur du jeu indique combien de lettres apparaissent dans le mot à trouver à la bonne place, et combien apparaissent à des places différentes. Le but du jeu est de retrouver le mot mystérieux avec le plus petit nombre possible de propositions. Avec un peu d’entrainement, je pense que l’on arrive à retrouver le mot au bout du sixième ou septième essai (ou avant si on a de la chance ou si on est très fort).

J’avais donc voulu, disais-je, écrire un petit logiciel qui, selon les règles précédentes, trouverait un mot choisi par l’utilisateur en un nombre d’essais assez réduits. Vous savez probablement que lorsque l’on joue à Master Mind (avec des couleurs ou des lettres, peu importe), on raisonne sur la position des différentes lettres et on déduit tour à tour quelle lettre se trouve ou ne peut pas se trouver à tel endroit. Typiquement, voici ce que l’on peut se dire :

  • « d’après le deuxième mot proposé, il y a un A ou un E dans le mot ; or, si c’est un A, il ne peut pas être à la première place sinon il aurait été bien placé dans le troisième mot, etc. », ou encore
  • « pour tester cette possibilité, il faudrait que je propose un mot avec un S en quatrième position et dont je sais déjà ce qu’il en est des autres lettres ».

J’ai donc essayé d’apprendre à l’ordinateur à mener des raisonnements de ce genre, et je n’ai pas connu, hélas, un très grand succès dans cette entreprise. Bien sûr, j’ai réussi à lui enseigner comment faire telle ou telle déduction précise mais il restait systématiquement des « évidences »
à côté desquelles il passait. Au final, le programme n’était pas très performant : il n’arrivait à conclure qu’au bout d’un grand nombre d’essais.

J’ai donc décidé de questionner quelques uns de mes amis, et l’un d’eux m’a suggéré la méthode radicalement différente que voici. Au début, le logiciel soumet le mot du dictionnaire de son choix (par exemple le premier). La réponse du meneur du jeu élimine bien évidemment un certain
nombre de mots. Le logiciel se contente alors d’effacer ces mots du dictionnaire et propose un mot de son choix parmi ceux qui restent (par exemple à nouveau le premier). Et ainsi de suite jusqu’à tomber sur le bon mot.

Je ne vous cache pas que j’ai commencé par être très étonné par cette proposition [3]. En effet, il semble quand même que
l’information essentielle dont on dispose s’organise autour de la position des lettres, alors que la proposition de mon collègue faisait totalement abstraction de cela. Malgré tout, j’ai programmé l’algorithme de mon collègue et, comme vous pouvez vous en douter maintenant, fus complètement abasourdi de constater qu’il fonctionnait à merveille : il trouvait le mot en moyenne en cinq essais si je me rappelle bien.

J’avoue que je n’ai toujours pas bien compris encore aujourd’hui pourquoi cette méthode est aussi efficace. Mais j’ai quand même appris quelque chose : j’ai appris qu’il ne faut jamais rejeter a priori les idées qui (me) paraissent absurdes au premier abord. Celles-ci comme les autres ont le droit d’être examinées avec autant d’attention que leurs consœurs. Bien sûr, elles seront examinées sans doute après dans la démarche de recherche [4], mais il faut toujours un argument irréfutable si on veut l’écarter définitivement.

Quand le hasard s’en mêle

Pour ajouter un peu de piquant au jeu, il est bien connu qu’il suffit d’ajouter un peu de hasard. Comme deuxième exemple, j’aimerais donc reprendre ce billet dans lequel on parlait d’un nouveau logiciel jouant particulièrement bien au go [5]. Cela pourrait paraître banal si ce n’est que la méthode utilisée pour y parvenir peut avoir de quoi surprendre.

Je vous renvoie au billet de mon collègue pour une explication un peu plus détaillée de ladite méthode, mais laissez-moi vous rappeler ci-dessous comment elle fonctionnait dans les grandes lignes. Pour savoir quel prochain coup jouer, on simulait un grand nombre de parties
totalement aléatoires (partant de la position en question) puis choisissait le coup pour laquelle la proportion de parties [6] gagnées commençant par ce coup (parmi toutes les parties commençant par ce coup) était maximale [7]. Autrement dit, on part de l’idée
que le plateau étant dans une position donnée, deux champions (qui jouent en partant de cette position) feront « en moyenne » le même résultat que deux débutants qui jouent au hasard. Et cela semble fonctionner !

À vrai dire, produire des exemples dans lesquels le hasard a un certain côté déroutant est quelque chose de relativement aisé tant notre cerveau en a une conception naturelle faussée. Peut-être donc que cet exemple n’illustre pas vraiment mon propos, mais il n’empêche que je le trouve très troublant.

L’algorithme pagerank de Google

Lorsque vous soumettez une requête à un moteur de recherche, celui-ci fouille tout le web pour trouver les pages correspondant à vos mots clés [8] puis trie ces pages selon leur pertinence. La deuxième étape est bien sûr aussi importante — si ce n’est plus — que la première. Être capable de classer les pages en
fonction de leur qualité apparaît donc comme une question de toute première importance.

Évidemment, il n’est pas envisageable de confier à une personne (ou même un groupe de personnes) la responsabilité de lire toutes les pages web et de noter chacune d’elles en fonction de leur intérêt. Éventuellement, ça pourrait l’être si le travail devait être fait une unique fois, mais
ce n’est pas du tout le cas car, ne l’oubliez pas, le web évolue continuellement. Il faut donc trouver des critères automatiques pour effectuer ce classement et pour cela, il semble a priori nécessaire
d’apprendre à l’ordinateur à lire et comprendre les différentes pages [9]... ce qui n’est pas encore à l’ordre du jour.

Mais pourtant la plupart des moteurs de recherche, et notamment Google, ont trouvé des solutions qui fonctionnent en général plutôt bien. La méthode de Google a déjà fait l’objet de nombreux articles (notamment un sur ce site) ; aussi ne vais-je pas encore une fois la détailler mais simplement me contenter de rappeler brièvement son principe. L’idée est de classer les pages simplement en fonction des liens qu’on y trouve. De façon légèrement plus précise, on attribue à chaque page une note qui est à peu près le nombre de fois qu’elle est référencée (c’est-à-dire directement accessible depuis une autre page) [10]. Cela paraît à première vue plutôt naïf : une page pourrait être très intéressante mais jamais citée (par exemple parce que personne ne l’a encore remarqué, ou parce qu’il s’agit d’un sujet très pointu dont peu de gens parlent) ou au contraire affligeante mais très souvent citée (par exemple beaucoup de gens pourraient la citer justement pour montrer l’exemple à ne pas suivre). L’algorithme de Google ne prend pas en compte ce type de considérations qu’il ne cherche même pas à comprendre ; il effectue simplement un calcul numérique à partir du décompte de nombre de liens, notamment sans jamais tenir compte du sens.

Et pourtant, vous pouvez constater chaque jour que cela fonctionne assez bien : par exemple, lorsque vous recherchez « gâteau chocolat », vous tombez en premier sur des recettes de gâteaux au chocolat en général acceptables, et seulement plus tard sur <a
href="http://www.facebook.com/pages/Gateau-au-chocolat/101369930598">cette page. Finalement, tout se passe comme si Google avait interprété correctement ce que vous vouliez et avait bien répondu à votre attente : le sens qui semblait avoir été perdu dans la notation réapparaît au final de façon un peu magique mais indéniable.

L’évaluation bibliométrique des chercheurs ?

Depuis quelques temps, vous ne l’avez sans doute pas raté, il est de plus en plus question d’évaluer les chercheurs à l’aide de critères bibliométriques. L’idée est que plutôt que de s’embêter à lire, comprendre et étudier les articles de chacun, on va se contenter de compter combien il y en a. En pondérant éventuellement par des nombres « bien choisis » (qui peuvent dépendre du nombre de pages ou de la revue dans laquelle l’article est publié), on fabrique une note qui permet de juger de la qualité du chercheur, voire même de classer ces derniers.

Évidemment, comme vous l’avez sans doute déjà entendu, beaucoup de mes confrères crient au scandale [11] jugeant la méthode beaucoup trop simpliste. Il semble difficile de leur
donner tort, je le reconnais... mais pourtant, au vu de ce qui précède et en particulier de mon baratin sur l’algorithme de Google, j’avoue que l’argument « C’est trop simple ! » ne me convainc pas totalement. C’est pourtant celui qui est le plus couramment utilisé, et je pense que si la
communauté mathématique veut pleinement s’opposer au principe de l’évaluation bibliométrique, il lui appartient de faire un effort pour étayer son principal argument.

Personnellement, je serais content de pouvoir lire — voire même savoir simplement qu’il existe — une étude (une étude statistique par exemple) qui montre clairement que les résultats fondés (uniquement) sur la bibliométrie diffèrent sensiblement de ceux fondés sur des méthodes
plus traditionnelles. Bien entendu, on peut toujours donner l’exemple du chercheur qui n’a rien publié pendant cinq ans, et reçoit la médaille Fields la sixième année. Mais, je pense qu’il est aussi possible de trouver des pages extraordinaires qui sont mal référencées par Google. Si l’on souhaite s’en tenir aux médaillés Fields qui publient peu, je pense qu’il faudrait au moins montrer que leur proportion est d’une façon ou d’une autre significative...

Comprenez-moi bien : je ne cherche pas à faire l’apologie des critères bibliométriques, mais plutôt à exprimer ma frustration devant la teneur des critiques qui lui sont faites habituellement. Il existe malgré tout d’autres arguments classiques utilisés par les opposants que je trouve légèrement plus pertinents (sans être pour autant incontestables selon moi).

Le premier auquel je pense est lié à l’enjeu. Autant se lancer dans le développement d’un moteur de recherche « bibliométrique » (de type Google) sans être certain du résultat n’est pas très dangereux, autant appliquer à grande échelle l’évaluation bibliométrique peut conduire à sacrifier toute une génération de mathématiciens. C’est certes un point délicat, mais on peut opposer à cela — ce que l’on fait d’ailleurs traditionnellement — que ce n’est pas en ne rien faisant que l’on aura une réponse.

Le deuxième argument que j’aimerais évoquer se résume par la doctrine « Attention, l’instrument de mesure perturbe la mesure ! » bien connue de tous les physiciens. Dans notre cas, cela signifie qu’à abuser des critères bibliométriques, les mathématiciens seront incités à user de techniques un peu sournoises pour augmenter la quantité de leur production, comme notamment le fait d’écrire plusieurs papiers dans des revues différentes pour présenter le même résultat, ou des variations minimes d’un unique théorème. On peut même penser que certains mathématiciens naturellement plus doués pour ce genre de jeux seront favorisés aux dépens des autres qui sont pourtant plus performants sur le plan de la recherche. En continuant le raisonnement, on peut même craindre de voir émerger des sociétés spécialisées dans la promotion des théorèmes mathématiques à l’instar des sociétés spécialisées qui vous proposent leur service pour booster le classement de votre page web sur Google. Si vous préférez, on a un peu peur de voir se développer — ou peut-être même réapparaître — le marché de la publicité au sein de la science avec les conséquences que cela implique. Par exemple, et en caricaturant volontairement, dans 50 ans, un laboratoire très riche pourra-t-il imposer que dorénavant $2+2 = 5$ ?

Je ne sais pas bien ce qu’il faut penser de tout cela, mais si l’on reprend la comparaison avec le web, autant il est clair que la présence de Google a une très grande influence (notamment par le fait que beaucoup de gens s’inquiètent de leur classement dans le moteur de recherche), autant je n’ai pas vraiment l’impression qu’en son absence le contenu des pages web aurait été autrement meilleur [12]. Jusqu’à quel point peut-on poursuivre le parallèle dans le monde de la science, ou de façon plus restrictive dans celui des mathématiques ? C’est une question à laquelle je n’ai pas de réponse.

Notes

[1Par exemple simpliste, ou aussi qui n’utilise pas toute l’information à disposition.

[2Dans la suite, lorsque je dirai « mot », il sera toujours sous-entendu qu’il s’agit d’un mot de cinq lettres dans lequel aucune lettre n’apparaît deux fois.

[3Enfin, je ne doutais pas que l’on arrive comme ceci à trouver le mot mystérieux, mais je pensais que le nombre de propositions avant d’y arriver serait immense.

[4En général, on commence par le chemin dont on pense qu’il a le plus de chance d’aboutir.

[5Particulièrement bien pour un programme informatique. Il faut savoir que, contrairement aux échecs par exemple, au go, les meilleurs humains sont bien plus forts que les meilleurs logiciels.

[6Les parties aléatoires simulées, j’entends

[7En fait, je ne suis pas vraiment au courant de l’algorithme exact, et j’imagine qu’en vrai, de nombreuses corrections viennent se fixer sur la trame générale que je viens de décrire.

[8Ce travail de fouille est bien sûr fait en amont et les résultats sont très soigneusement triés et référencés de façon à pouvoir y accéder ensuite le plus rapidement possible.

[9En général, on s’attend à ce que ce soit un préliminaire à la notation. On n’imagine pas par exemple un professeur noter correctement ses copies sans les comprendre.

[10On attribue en fait un poids différent à chaque lien en fonction de la page depuis laquelle il pointe, ce poids étant lui-même (proportionnel à) une note
jugeant de la qualité de chaque page à émettre des liens pertinents. Comprenez bien que le serpent ne se mord pas la queue dans le sens où l’on n’a pas besoin d’attribuer d’abord ces deuxièmes notes. En fait, tout se fait en même temps : on commence par attribuer la note de pertinence à chaque page, on les utilise pour attribuer la deuxième note, on utilise ensuite ces nouvelles données pour corriger les premières notes, ce qui permet maintenant de recorriger les deuxièmes notes, et ainsi de suite jusqu’à ce que le tout se stabilise. Enfin, peu importe, ce n’est pas essentiel pour la suite de mon propos.

[11Avec quand même quelques petites nuances. Par exemple, certains rejettent complètement la méthode, tandis que d’autres, tout en reconnaissant ses défauts et qu’elle
n’est pas adaptée pour l’évaluation individuelle des chercheurs, pensent qu’elle peut-être utilisée — au moins en partie — pour évaluer des structures plus grosses comme des laboratoires, ou même des pays.

[12Bien sûr, quoique l’on fasse maintenant, Google existe... donc ma phrase n’a pas vraiment de sens, mais vous comprenez je pense ce que je veux dire par là.

Partager cet article

Pour citer cet article :

Xavier Caruso — «D’une simplicité déconcertante» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • D’une simplicité déconcertante

    le 9 décembre 2009 à 20:06, par Jean-Paul Allouche

    Joli article en effet. L’exemple de Google montre à la fois l’intérêt et les limites des procédures automatiques (surtout si elles sont utilisées sans recul). Sur les questions de bibliométrie : il existe une recherche en bibliométrie qui montre les biais de telle ou telle mesure mais qui — malheureusement — semble admettre comme certains collègues qu’on peut à force de perfectionnement et de réflexion fabriquer un indice pertinent, intelligent, efficace etc. C’est évidemment absurde que de vouloir « quantifier la qualité ». La vraie question, en amont, est de savoir pourquoi on veut quantifier. Réfléchissons aux vraies raisons et convenons qu’elles ne sont guère reluisantes. Pour comprendre les enjeux politiques (plus dans le cas des sciences humaines il est vrai), on lira avec profit le numéro 37 (2009) de la revue Cités,
    intitulé « L’idéologie de l’évaluation. La grande imposture ».
    (Voir ici, et dans toutes les bonnes librairies.)

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?