Comment devenir expert en UNE leçon

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…

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

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 là.

Billets connexes

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