Comment devenir expert en UNE leçon

Source ici

Voulez-vous devenir presque aussi bon que le meilleur expert du monde en turf – ou en Bourse si le cheval n’est pas à votre goût en ce moment- sans rien  connaître au tiercé? MUWA!!! Non ce n’est pas votre rugissement après avoir gagné (quoique), mais l’acronyme de l’algorithme qu’il vous faudra utiliser (pour Multiplicative Update Weights Algorithm) et que j’ai découvert dans les cours de Bernard Chazelle au Collège de France. Une méthode très simple malgré son nom et incroyablement performante dans un tas de domaines. Elle pourrait même expliquer l’intérêt de la sexualité dans l’évolution, c’est dire!

Pour comprendre l’idée, ce n’est pas au tiercé qu’on va jouer mais à un  jeu un peu plus simple. Chaque jour vous devez miser blanc ou noir. Si vous avez parié sur la bonne couleur, vous ne gagnez rien. Si vous vous êtes trompé, vous perdez 1€ (bon d’accord, c’est idiot comme jeu, mais ça permet de comprendre la méthode). Pour vous aider, vous pouvez vous appuyer sur les pronostics quotidiens de 5 experts. Evidemment ils ne sont pas toujours d’accord entre eux, c’est donc à vous de trouver la bonne stratégie pour minimiser vos pertes.

Faut-il se fier à au meilleur expert du moment?

La première idée qui vient à l’esprit est de se fier à l’expert qui dans le passé a eu le plus de réussite. Et en cas d’égalité, vous suivez l’avis du premier expert dans l’ordre alphabétique. Ca vous semble correct comme méthode? Et bien ça n’est pas forcément génial comme on le voit sur l’exemple suivant. Les résultats sont visualisés sous forme d’un tableau où chaque ligne correspond à une journée et chaque colonne au résultat d’un expert (1 pour une prédiction fausse, 0 pour une prédiction correcte). J’ai mis en vert, l’avis que vous avez suivi selon l’algorithme “du meilleur expert apparent”:

Journée
Alain
Bernard
Charles
David
Eric
vous!
lundi  1 0 0 1 0  1
 mardi  0  1  0  1  1  1
 mercredi 1  1  1  0  1  1
 jeudi  0  0  1  0 0  1
BILAN 2 2  2 2  2 4
Le premier jour vous ne connaissez pas la fiabilité des experts, donc vous vous fiez à Alain, le premier sur la liste. Pas de chance il s’est planté. Mardi, vous suivez Bernard, qui ne s’est pas trompé lundi. Manque de bol, il se trompe. Mercredi vous misez comme Charles qui avait vu juste lundi et mardi. Mais là encore la loi de Murphy vous guette, il se trompe ce jour là. Bref, de fil en aiguille, vous vous trompez 4 fois avec cette méthode, deux fois plus que chacun des experts et ça pourrait très bien continuer comme ça longtemps…  Vous me direz qu’on joue de pas de chance, mais on peut avoir encore moins de chance et perdre jusqu’à N fois la perte du meilleur expert (N étant le nombre d’experts)!  Se fier à “l’expert du moment” est manifestement une stratégie dangereuse!(1)

La méthode des pondérations multiplicatives

En améliorant un peu la méthode ci-dessus on arrive à limiter sa perte à Log(N) fois celle du meilleur expert, mais c’est le maximum que l’on peut faire avec une stratégie complètement déterministe (1). Comme souvent en théorie des jeux, il faut avoir recours au hasard pour faire (beaucoup) mieux. Petite parenthèse métaphysique: je suis toujours aussi fasciné de voir comment on arrive à améliorer les performances d’une décision en y ajoutant de l’aléatoire. On n’arrive à optimiser ses choix qu’à condition de savoir renoncer à tout contrôler, de laisser une petite place à la chance, à l’imprévisible. Comme si à partir d’un certain niveau il fallait savoir lâcher-prise pour booster ses performances…

Le processus est donc le suivant: au départ tous les experts ont la même valorisation, le même poids, qui vaut 1. Chaque jour, on réévalue ce poids. Si l’expert a vu juste, sa pondération est inchangée; s’il s’est trompé, elle est réduite de 5% (par exemple). On choisit alors un expert aléatoirement, selon une probabilité proportionnelle à son “poids”. Et voilà, c’est fini. Le meilleur expert à bien sûr plus de chances d’être choisi mais le plus mauvais des experts a quand même sa (petite) chance. Une telle méthode vous garantit une perte sera à peine plus grande que celle du meilleur expert! Incroyable non?
Pour transposer cet exemple au tiercé (où l’on n’est pas obligé de perdre!) la méthode s’adapte facilement: on actualise quotidiennement le “poids” de chaque expert en le multipliant par (1+0.05 G), G étant son gain (positif) ou sa perte (négative) du jour. Plus un expert gagne, plus sa fiabilité augmente et plus vous avez de chance de suivre son avis. Sans rien connaître aux chevaux, vous êtes en mesure de faire à la longue quasiment aussi bien que le meilleur expert.
Si vous avez du mal à croire à ce petit miracle, rassurez-vous, vous n’êtes pas le seul. Les chercheurs en informatique eux-mêmes sont héberlués par cette performance mais devant les preuves de son efficacité ils déploient cette méthode d’auto-apprentissage dans de très nombreux domaines, pour çodes problèmes de congestion de réseaux, de programmation convexe, des jeux à somme nulle etc. Le principe du MUWA s’est imposé à peu près dans tous les algorithmes d’optimisation sous des formes plus ou moins sophistiquées. Malheureusement je n’ai pas réussi à trouver sur le net une démo sympa pour illustrer ce petit miracle. A votre bon coeur si vous en connaissez!

Pourquoi le sexe c’est bon? (évolutivement parlant)

Parmi les applications décoiffante, le MUWA pourrait bien être l’algorithme “naturel” à la sélection naturel… Du moins c’est la conclusion de Christos Papadimitriou, un chercheur en informatique de Berkeley qui s’est longtemps gratté la tête pour comprendre pourquoi la reproduction sexuée est aussi fréquente dans la nature. Si l’on y réfléchit, cette omniprésence du sexe dans la nature a de quoi intriguer car ce mode de reproduction présente au moins autant d’inconvénients que d’avantages: la recherche d’un(e) partenaire sexuel(le) est une activité coûteuse en énergie et risquée. Le sexe limite le nombre de gènes transmis par chaque individu ce qui n’est pas terrible quand on est un gène égoïste cherchant à maximiser sa descendance. Et surtout, le sexe ralentit l’innovation génétique : un nouvel allèle mutant et favorable ne s’exprime que s’il est dominant; le brassage sexuel s’oppose donc à la diffusion de toute nouveauté portée par un allèle récessif. Face à tous ces inconvénients la liste des avantages est assez limitée et très spéculative. Par exemple le brassage sexuel permet de limiter les effets des mutations délétères, mais de façon moins efficace que la reproduction asexuée où la sélection naturelle élimine directement toute mutation défavorable. Bref, la sexualité est une énigme évolutive encore mal résolue.

Le problème se voit vite quand on fait tourner des modèles informatique simulant la sélection naturelle. Ces modèles fonctionnent très bien pour un mode de reproduction asexuée mais ils déraillent systématiquement quand on y introduit la notion de sexualité. Pour résoudre ce paradoxe, Papadimitriou a donc fait l’hypothèse que le sexe privilégierait non pas les gènes les plus adaptés -comme le fait la reproduction asexuée- mais ceux qui fonctionnent correctement dans toutes les combinaisons génétiques. Autrement dit, c’est la “miscibilité” (mixability en anglais) du gène et non pas sa fitness qui est optimisée. C’est plus facile à comprendre avec un exemple. Supposez que le génotype ne soit composé que de deux gènes a (4 allèles possibles) et b (5 allèles possibles). La matrice de fitness se présente sous forme d’un tableau de 5 lignes par 4 colonnes:

a1
a2
a3
a4
a5
b1 3 2 5 2 4
b2 1 1 0 6 5
b3 0 1 1 2 3
b4 1 8 1 3 2

La table se lit de la façon suivante: un individu ayant l’allèle a4 et l’allèle b2 a une fitness de 6 (ou bien a 6 descendants viables). Sur cet exemple la reproduction sexuée et asexuée aboutissent à des résultats différents:

  • si la reproduction est asexuée, la sélection naturelle retient les combinaisons d’allèles donnant la fitness maximale:  (a2,b4=> fitness 8) très certainement et éventuellement une deuxième souche (a2, b4 => fitness 6).
  • si la reproduction est sexuée, l’allèle sélectionné est celui dont la fitness moyenne (le total en ligne ou en colonne) est la plus grande. Ce sont l’allèle a5 et l’allèle b1 qui seront les plus fréquents, ce qui ne procure une fitness médiane que de 4.

La reproduction sexuée ne sélectionne donc pas les combinaisons optimales d’allèles mais en contrepartie elle garantit une excellente tolérance des organismes à la variabilité génétique. La “sociabilité” des allèles sélectionnés assure que des mutations mineures n’ affectent pas trop la fitness des individus et ainsi toutes les conditions sont réunies pour que puisse se constituer  un réservoir de  diversité génétique. Ce mécanisme expliquerait donc comment certains caractères acquis, suite à un changement d’environnement, parviennent à se transmettre héréditairement et perdurer même lorsque l’environnement est redevenu comme avant. Un phénomène très néo-Lamarckien qu’a découvert Waddington  dans les années 1950 et dont je vous ai parlé dans ce billet.

Du MUWA dans le sexe?

Quel rapport avec nos algorithmes d’auto-apprentissage? Et bien on peut aussi envisager l’évolution comme un jeu de stratégie. Les gènes seraient des joueurs devant choisir astucieusement la fréquence de leurs différents allèles pour maximiser la fitness du résultat final, en fonction de la probabilité des allèles des autres gènes. C’est un jeu de coordination, car tous les gènes ont le même but: obtenir la meilleure espérance de fitness du génotype obtenu. Papadimitriou et son équipe ont étudié ce que donneraient les lois de la sélection naturelle dans un tel jeu, dans un contexte de faible sélection naturelle, c’est-à-dire quand les différences de fitness entre allèles sont minimes. Leurs résultats sont bluffants:

  • D’abord le jeu de la sélection naturelle équivaut exactement à l’algorithme MUWA, le même qui vous sert à gagner au tiercé. On peut dire qu’il mérite bien son titre d’algorithme universel.
  • Comme Papadimitriou en avait eu l’intuition, la miscibilité de l’allèle joue un rôle clé dans le processus puisqu’elle sert de facteur de pondération (celui qui ajuste la fréquence d’un allèle à chaque génération) dans l’algorithme naturel. La simple dérive génétique privilégie donc automatiquement les allèles les plus tolérants aux différentes combinaisons génétiques.
  • Enfin pour le cas de deux gènes, la sexualité ne réduit pas la diversité génétique d’une population. Bien au contraire l’algorithme MUWA préserve un maximum de variabilité génétique au cours du temps.

Ce dernier point est particulièrement intéressant car il résout un célèbre paradoxe de l’évolution appelé le paradoxe du Lek concernant la sélection sexuelle: si chaque femelle choisit systématiquement son partenaire selon les mêmes critères à chaque génération, les mâles porteurs des “bons gènes” devraient progressivement éclipser tous les autres et leur patrimoine génétique s’imposer progressivement à toute la population. On devrait donc observer une réduction drastique de la diversité génétique, la généralisation du trait favorable et -par voie de conséquence- la disparition de l’avantage sélectif associé. Comme ce n’est manifestement pas le cas, il faut supposer qu’il existe un mécanisme compensateur qui maintienne la variabilité génétique à un certain niveau. La maximisation de la miscibilité prédite par Papadimitriou apporte une réponse particulièrement convaincante à ce paradoxe.

Une 2CV bien solide plutôt qu’un bolide fragile

C’est à ma connaissance la première fois qu’une théorie démontre de façon rigoureuse à quel point la reproduction sexuée est bénéfique à l’évolution. Elle me plaît d’autant plus qu’elle s’écarte de l’image classique d’une évolution qui affûterait progressivement la fitness d’une lignée par le jeu de mutations avantageuses. Avec le sexe, les recettes les plus robustes valent mieux que le nec plus ultra de la sophistication et surtout elle corrobore les limites d’une vision trop “adaptationniste” de l’évolution. Mieux vaut une 2CV qui se répare avec trois bouts de ficelle (mes références sont datées!) qu’une formule1 performante mais fragile. Et grâce à ce changement de paradigme une population n’est pas obligée d’attendre LA mutation miraculeuse pour réagir à un changement d’environnement brutal car la diversité de son patrimoine génétique lui offre une immense réserve de résilience. 

Evidemment il reste encore à prouver que toutes ces propriétés restent valables si la sélection naturelle est intense (autrement dit si certains allèles sont beaucoup plus favorables que d’autres) et si le théorème de la diversité maximale est vrai quel que soit le nombre de gènes. Mais l’algorithme MUWA nous a déjà tellement époustouflé qu’il serait étonnant qu’il ne puisse encore faire ce genre de petit miracle… Au boulot les chercheurs!

 

(1) Il faut pour cela adapter la stratégie précédente. Le jour où on a le choix entre plusieurs “meilleurs experts du moment”, il faut non pas suivre l’avis de l’un d’eux, mais l’avis de la majorité d’entre eux.

Source:

Le cours de Bernard Chazelle sur l’algorithme des “multiplicative updates” (en video) et ce papier plus théorique.

Une conférence de Papadimitriou au Collège de France et ses papiers ici et .

Billets connexes

L’évolution, un art plastique (épisode 2 et 3)

13 comments for “Comment devenir expert en UNE leçon

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *