Overblog Suivre ce blog
Administration Créer mon blog
4 mai 2010 2 04 /05 /mai /2010 18:47


Plutôt que de vous raconter beaucoup de choses sur ce bon livre (où les experts apprendront peu, mais les gens qui veulent une idée générale rapide auront satisfaction), je vais vous parler d'un jeu fort intéressant: le jeu du mille-pattes ("centipede game" en littérature anglo-saxonne), et puis aussi le jeu de l'ultimatum.

Je vous présente ci-dessous une variante du jeu du mille-pattes. Ce jeu présente l'intérêt qui suit:
  • Si on est très "rationnel", au sens où on prend la décision qui maximise son profit, les deux joueurs sont en très mauvaise situation.
  • Si on coopère, les deux joueurs gagnent beaucoup.
  • En pratique, les gens obtiennent une solution bien meilleure que la maximisation rationnelle du profit.

Les puristes me diront que j'ai un peu simplifié en vulgarisant... Je précise ci-dessous les choses, et puis je parlerai un peu aussi de sociologie, d'ethnologie et de psychologie.

Imaginons qu'Alice joue avec Bob. Ils ont assis face à face, avec une ligne blanche qui les sépare.

Au début, on donne 2 euros à Bob. Soit il le prend (et Alice ne gagne rien), soit il fait passer ces 2 euros par dessus la ligne blanche pour le passer à Alice. Les 2 euros deviennent 4=2+2 euros en traversant la ligne.

Ensuite, Alice a le même choix: soit elle prend 3 euros (la moitié plus un), et Bob reçoit la moitié moins un (soit 1 euro), ou bien elle fait passer les 4 euros de l'autre côté - et les 4 euros deviennent 6 euros.

Donc à chaque étape: il y a N euros sur un côté, et si le joueur "pique" l'argent il en gagne N/2+1 (l'adversaire gagne N/2-1); sinon on ajoute 2 euros, et on passe à l'autre joueur..

On continue jusqu'à ce qu'un des joueurs garde l'argent, ou jusqu'à 100 itérations; si on atteint 100 itérations, chacun gagne 100 euros.

Analysons le jeu. Le dernier joueur aurait pu gagner 101 euros, en "trichant" une étape avant.
Donc s'il est entièrement rationnel, c'est ce qu'il fait.

L'autre joueur, prévoyant son comportement, devrait donc tricher une étape plus tôt, pour gagner 100 euros plutôt que 99... Mais on peut ainsi remonter encore une étape, etc. On arrive à la conclusion stupide que Bob a intérêt, à la première étape, à prendre les 2 euros. Fort heureusement, dans la vraie vie, les humains font des choix plus courtois et plus profitables pour tout le monde.

Et que font les vrais humains ? En gros, ils deviennent parfois rationnels (méchants) vers la fin du jeu. Mais ils font toujours mieux que la solution "rationnelle". En gros, quand la somme est importante, la politesse est mise en défaut au profit de l'égoisme.

Un jeu intéressant aussi est le jeu de l'ultimatum: on donne N euros à un individu, qui doit proposer M euros (avec M compris entre 0 et N) à son partenaire de jeu. Le partenaire a le choix entre accepter et refuser; s'il refuse, personne ne gagne rien, s'il accepte, le partage est effectué, il gagne M euros et l'autre gagne N-M euros.

Que dit la théorie si les joueurs sont rationnels ? Le second joueur a toujours intérêt à accepter (du moins dès que M>0), donc il accepte s'il est rationnel. Le premier joueur, lui, a toujours intérêt à donc proposer M=1.

Et que font les vrais humains ? Ca dépend des cultures. Il y a même des peuples qui proposent M>N/2, genre 60%. Dans nos sociétés il y a beaucoup de 50%, sans doute par habitude des notions de négociations, mais en général on propose un peu moins de la moitié. Les peuples vivant de manière très collaborative sont plus polis. La politesse est plus forte pour quelqu'un du même village. Et quand la somme est très forte, les gens deviennent plus méchants. Un peu décevant, mais pas très étonnant.
Mais je vous laisse découvrir tout ça en fouillant la littérature spécialisée, je suis un béotien du sujet...

Et les applications de tout ça ? Et bien oui, ça sert parfois; en stratégie militaire, ou pour les négociations lors des prises d'otage. Ainsi, certains pays ne cèdent jamais au chantage en cas d'enlèvement; leurs ressortissants sont parait-il moins enlevés que les ressortissants d'autres pays. Tout ça demande des jeux itérés, ou multi-joueurs, à découvrir dans ce livre et d'autres.

Et vous, vous feriez quoi ? Et si les rewards étaient négatifs et l'autre joueur votre meilleur ami ? Genre on joue le nombre d'enfants qu'on n'égorge pas ? Beuh... j'ai pas envie de savoir, on sort du domaine de validité de l'espèce humaine quand on cogite trop à ce qu'on ferait dans des situations tordues :-)

 

Repost 0
Published by teytaud - dans Recherche
commenter cet article
3 mai 2010 1 03 /05 /mai /2010 09:40

L'informatique, ça bouge! Et pas seulement au niveau machine, les langages aussi ont bougé. Petite remontée dans le temps avec le "dictionnaire du basic", par David Lien, traduit par P.S.I., livre expliquant comment fonctionne le langage le plus célèbre de l'époque, le langage Basic.


Ce n'est pas la photo du livre en question! Ca c'est un autre livre, du même éditeur, qui me rappelle aussi ma jeunesse. A l'époque, on achetait les jeux en livre, on les recopiait, et du coup on comprenait les bases de la programmation, forcément, pour pouvoir jouer.


Les normes! Et oui, à l'époque, les normes étaient un peu floues. Du coup, une bonne partie du livre est centrée sur "votre programme ne marche pas parce que le Basic a changé ? Voilà comment recoder le morceau qui pose problème". On y échappe dans les langages modernes, fort heureusement.

En parlant de normes, à cette époque, sur certains ordinateurs, le O était barré au lieu du zéro!

Mon Dieu les numéros de lignes! Ca, c'est vraiment bien que ça ait changé. Pourtant, souvenez-vous, on a eu besoin d'un peu de temps pour s'acclimater au Basic sans numéro de ligne.
Quels numéros de lignes, disent les jeunots ? Autrefois, chaque instruction avait un numéro. Ce numéro était typiquement 10 pour la première instruction, 20 pour la seconde, 30 pour la troisième, et ainsi de suite. Evidemment, quand vous vouliez insérer une ligne entre deux lignes, il fallait utiliser 25, 27, 29, et de temps en temps on était bien coincé; il fallait utiliser un "goto" à la ligne 26, qui partait à la ligne 3000 (pas encore utilisée), suivie de 3010, 3020, 3030, et en 3040 on trouvait un "goto 27".

Et la fin du programme ? Comme il ne pouvait y avoir qu'une fin de programme (tout à la fin), et bien on mettait quelque chose comme "9999 END", et à la fin du programme (avant les procédures) on mettait "GOTO 9999".

Et oui, car on programmait beaucoup avec des "goto" ! Alors qu'aujourd'hui, certes on peut encore mettre des "goto", mais c'est en désuétude. A l'époque il existait néanmoins aussi une espèce de notion de fonction: le gosub! C'est-à-dire qu'on écrivait "gosub 4000", la ligne 4000 et les suivantes contenaient la fonction, et à la fin il y avait un "return". Et les paramètres de la fonction ? Tout en variables globales! Et oui c'est pas très pratique: on fait

550 ...
560 N=50
570 gosub 4000
580 REM mon resultat est dans la variable x.

4000 x=N*N+N+1
4010 return

Imaginez les fonctions récursives! Il fallait stocker les variables locales dans un tableau.

C'était ça, les anciens temps. Après il y a eu des basic qui gardaient la simplicité, les problèmes en moins: toujours pas de déclaration de variable, mais plus de numéro de ligne. Les fonctions sont restées longtemps très pénibles à mettre en oeuvre.

Pas de fonction Exp, pas de fonction Tanh, sur de nombreuses variantes de Basic! Du coup il fallait coder Exp à la ligne 30 000, et Tanh à la ligne 40 000.

Là où ça devient vraiment comique, c'est quand on parle de réutilisabilité! Si vous vouliez réutiliser dans le programme B le "tanh" que vous avez péniblement codé lundi dans un programme A, tout va se casser si vous avez des numéros de ligne qui se mélangent! Imaginez un "tanh" qui chevauche un "exp". Ca, c'était vraiment hyper pénible, ces fichus numéros de ligne!

Et les noms de variables ? Et bien le livre déconseille la tendance "littéraire" consistant à mettre des noms de variables à rallonge. Et j'ai eu des bugs dont je me rappelle encore, au début des années 80, avant que n'arrivent le Mia et les volants à moquette, parce que toutes les variables commençant par deux mêmes lettres étaient identiques! Par exemple, IndexSurLaMatrice et IndiceDeGini sont la même variable. Boa et Bois aussi. Super pratique, n'est-ce-pas ? Quand je pense que je me rappelle encore de ce bug, près de 30 ans après, j'imagine l'énervement que ça a du être.

Le livre qualifie de "programmeurs fous" les adeptes de noms de variables à rallonge. J'avoue être un peu resté sur les noms de variables courts... honte sur moi.

Que ceux qui se rappellent de "peek" et "poke" lèvent la main! Une instruction pour aller lire à une adresse mémoire, une autre instruction pour y écrire. Ouf, maintenant les langages sont suffisamment pratiques pour pouvoir se passer de ça. Mais enfin le C a longtemps gardé de l'arithmétique des pointeurs, on n'est pas si loin de peek et poke!

Y avait-il du bon là-dedans, qu'on a perdu en route ? Peut-être le fait qu'on allumait le PC d'emblée sur du Basic. On parlait à la machine dans un langage informatique. La compréhension du fond de la machine était forcée et naturelle. Et la simplicité des déclarations de variables à la volée, l'absence de compilation - finalement python c'est un peu le retour des bons côtés du basic (sans els mauvais, l'objet en plus). Globalement, les langages sont allés, je crois, dans la bonne direction (le matériel et les systèmes d'exploitation, c'est autre chose - ce ne sont pas les meilleurs systèmes qui ont envahi le marché, notamment chez les particuliers, et l'Amiga ne méritait sans doute pas son petit sort - je laisse plus expert que moi se prononcer sur les aspects Risc et Cisc).

Repost 0
Published by teytaud - dans Recherche
commenter cet article
15 avril 2010 4 15 /04 /avril /2010 23:11

Un livre intéressant quoiqu'un peu décousu, aux titres un peu trop orientés poésie et pas assez orienté précision scientifique, mais plein d'anecdotes marrantes - un bon livre donc quoiqu'un peu verbeux pour moi. Et des mots clefs qui vont faire venir sur cette page un tas de gens qui viennent chercher des photos pornographiques et vont être déçus même s'il y a le mot lingerie plus bas dans ce texte.

Je ne suis pas biologiste, juste un informaticien qui s'intéresse à l'évolution (mais surtout la sélection Darwinienne pour les robots ou contrôleurs ou logiciels, je ne triture pas de bestioles...). Pardonnez-moi les erreurs, n'hésitez pas à contester; je sais qu'il y a dans mes lecteurs des gens plus doués que moi sur le sujet.

Un hermaphrodite qui ne se rend pas compte
qu'on se pose plein de questions
sur lui: est-il un reste d'évolution incomplète, ou un
mode de reproduction meilleur que le notre ?



La sexualité n'a pas besoin des sexes, qu'on se le dise. Par exemple, les hermaphrodites, comme les escargots, qui conservent une dissymétrie dans l'acte sexuel et la fabrication du bébé, mais aussi certaines paramécies qui s'échangent comme ça en passant du matériel génétique: ça s'appelle la conjugaison.

C'est sympa, un échange de matériel génétique,
non ? Ca s'appelle la conjugaison.



Donc, l'existence de deux sexes ne s'explique pas si facilement que ça: l'avantage évolutif de mélange des bons gênes (permettant ainsi à plusieurs mutations génétiques utiles et présentes chez plusieurs individus de se combiner).Il faut qu'il y ait aussi un avantage à l'existence de deux sexes différents (et pourquoi seulement 2 ?) pour expliquer cela. Les informaticiens auront remarqué qu'en évolution de robots, on pratique allègrement la copulation entre 50 robots à la fois, sans distinction de sexe. Certains lézards ne comportent que des femelles qui se reproduisent par parthénogénèse.

Les mâles et les femelles ont des stratégies différentes, "quantité contre qualité" comme le dit crûment l'auteur: le mâle, qui dépense peu d'énergie pour chaque fécondation, a tout intérêt à y aller en force; la femelle, par contre, a tout intérêt à faire attention et à ne pas se disperser (ça me rappelle les statistiques sur la différence de taux de succès entre un homme qui aborde une femme pour proposer une copulation, par rapport à la réciproque, http://0z.fr/dxkXL).

Rien qu'à les voir elles ne sont
pas sympathiques (cf texte).



Homosexualité, bisexualité, homoparentalité, triolisme: les cygnes noirs homosexuels adoptent les bébés que leur confient une femelle désireuse d'assurer une bonne réussite à leurs enfants (qui survivent beaucoup mieux avec des parents mâles homosexuels qu'avec des parents hétérosexuels, chez les cygnes noirs: 80% au lieu de 30%). Chez les oies, deux mâles bisexuels vivent fréquemment avec une femelle; chez les goëlands, c'est plutôt deux femelles et un mâle. Madame Boutin va-t-elle s'en remettre ?

Oh le coquin.



Certaines espèces animales ne font pas dans la tendresse. Ainsi les sangsues mâles perforent les femelles pour les féconder (si!). Les femelles ne sont pas forcément beaucoup plus sympathiques puisqu'il leur arrive de dévorer leur partenaire sexuel (chez les araignées elles peuvent manger le mâle même sans copulation s'il ne leur plait pas). Le xénope mâle, quant à lui, ô le méchant, peut copuler juste pour avoir des enfants à dévorer. L'enfant nait grâce au sacrifice en ressources alimentaires de la maman et le papa se régale.
Chez les poissons gambusies le viol est la norme; chez les canards les messieurs peuvent noyer les dames en les envahissant pour obtenir une copulation. Les mâles antilopes topis s'en prennent aux enfants pour obliger les mamans à copuler. Les dauphins pratiquent abondamment le viol collectif. Une brebis peut mourir sous les coups du mâle dominant en cas d' "adultère". p236 on apprend aussi que (peut-être...) le canard mâle y va assez fort avec un organe trop gros, car ainsi la femelle n'a plus trop envie d'aller copuler ailleurs vu qu'elle ne trouve pas ça sympa du tout et préfère garder le premier qui est calmé pour quelques temps.

Vous le trouvez mignon ? Sachez qu'il pratique le viol collectif.



Pourquoi est-ce à la même page du livre que l'on apprend que plus il y a de compétition pour la fécondation des femelles et plus les organes introducteurs sont longs ? C'est toujours dans la thème de la concurrence pour la fécondation. Aussi chez certaines espèces de lions, criquets, rongeurs, oiseaux, la copulation peut être reproduite (même mâle, même femelle) des dizaines voire centaines de fois de suite. Chez d'autres espèces (crotales, putois, belettes) on remplace la fréquence par la durée (plusieurs heures).

Parfois la différence plait. Chez le poisson "guppy" ou les drosophiles, les mâles atypiques plaisent beaucoup; quoique le mécanisme ne soit pas très clair pour moi (odeur ?), une préférence pour les partenaires ayant un système immunitaire très différent apparait - ce qui semble malin pour compléter la protection immunitaire - je trouve ça carrément magique. Ce type de préférence semble en général moins marqué chez les mâles.

Le fait de connaitre un individu de longue date semble aussi réduire son attrait, ce qui évite la copulation avec des individus génétiquement proches et augmente donc la diversité et favorise un système immunitaire solide (et peut-être la diversité est-elle utile pour beaucoup d'autres choses que le système immunitaire).

La spéciation est parfois amusante. Certains poissons se spécialisent dans l'art de piquer une écaille à d'autres poissons, pour s'alimenter. Alors, parmi ces voleurs, certains ont la bouche de travers à droite, pour piquer une écaille sur leur droite en doublant la victime, et d'autre à gauche. Comme mêler les deux espèces n'est pas souhaitable (la bouche centrée n'est pas efficace), les deux catégories finissent pas devenir exclusives d'après l'auteur: deux espèces (quelqu'un peut donner un exemple d'espèce animale dissymétrique dont 50% des membres sont symétriques aux 50 autres pourcents ?).

Et la recherche en biologie ? Très biaisée par le mécanisme de publication! Car on publie mieux les résultats positifs (qui confirment la théorie dominante) que les résultats négatifs. Chez les informaticiens, je vous promets: c'est pareil :-)

Pourquoi les animaux, surtout mâles, ont parfois des attributs inutiles très visibles ? Pour montrer comme ils sont forts! Ainsi les poissons "porte-glaive" dont un appendice aussi inutile qu'étrange est bien visible. On appelle ça un attribut hypertélique.Pensez aussi à l'exemple du paon. Il parait que certains animaux vont jusqu'à prendre des risques inutiles auprès des prédateurs, juste pour montrer aux femelles à quel point ils sont forts et peuvent se le permettre. L'attribut hypertélique peut être donc une extension abusive d'un attribut qui est une réelle plus-value (dans ce cas, son existence est due à un déficit sensoriel des femelles qui ne voient pas que c'est plus que l'utile), ou bien être là simplement en tant que preuve que si le mâle peut se permettre telle excroissance inutile, c'est parce qu'il est bien vigoureux et bien en forme, donc un bon partenaire potentiel pour fabriquer de bons bébés.
Page 163, l'auteur nous dit que finalement, on obtient un succès supplémentaire en étant un crâneur. Un peu comme la symétrie serait une preuve de résistance aux parasites: en étant blindé contre les parasites, on se développe bien symétrie - donc il est normal dans cette théorie que l'on préfère un partenaire symétrique (il en va de même de l'aspect de la peau).
L'attribut hypertélique est-il limité aux animaux ? La lingerie affriolante est-elle un attribut hypertélique artificiel ? L'auteur préfère citer la sculpture grecque ou Rodin, mais aussi la cosmétique.

Quelques autres anecdotes pour la route ? La transexualité "naturelle" existe chez les poissons Xanthias, et beaucoup d'animaux pratiquent les petits cadeaux autour de la sexualité, allant chez certaines espèces jusqu'à s'auto-offrir en casse-croûte. Les petits cadeaux sont qualifiés de forme de prostitution ou de petits cadeaux selon l'humeur de la page.

L'effet dit de la reine rouge est cité; en très bref, l'existence des mâles, qui a priori réduisent l'efficacité de la propagation des gênes, s'expliquerait par le fait qu'ils limitent la disparition des gênes temporairement inutiles mais qui peuvent redevenir capitaux plus tard, après un retour d'un environnement antérieur. Le livre aurait pu faire plus clair (plus matheux ?) sur ce sujet.

Pourquoi la monogamie ? Au niveau diversité génétique c'est vraiment pas terrible. Un espèce de moyen pour la femelle d'assurer le fait qu'il y a un mâle pour s'occuper des enfants, et pour le mâle un mauvais choix parce qu'il se fait attraper (contrairement à son intérêt de quantité précédemment cité...) par la femelle (qui l'attire à répétition par stratégèmes cochons) ? La femelle étourneau multiplie les copulations, et est répudiée au premier ralentissement d'activités.

Les étourneaux mâles sont heureux selon ce livre (cf texte).
Repost 0
Published by teytaud - dans Recherche
commenter cet article
12 avril 2010 1 12 /04 /avril /2010 19:18

Quel rapport entre l'honneur de l'esprit humain et les mathématiques ?
M. Jean Dieudonné ouvre son livre par une citation du célèbre Jacobi écrivant au non moins célèbre Legendre pour lui dire "M. Fourier avait l'opinion que le but principale des mathématiques était l'utilité publique et l'explication des phénomènes naturels; mais un philosophe comme lui auriat dû savoir que le but unique de la science, c'est l'honneur de l'esprit humain, et que sous ce titre, une question de nombres vaut autant qu'une question de système du monde."

Alors, les mathématiques pour les mathématiques, c'est le saint des saints ?
C'est un peu le point qui me gêne chez Dieudonné: en effet, il considère que le top du top,
c'est de faire des mathématiques "pures", et sa conception des mathématiques pures est particulièrement rigide: au revoir probabilités, informatique même théorique. Quelque part, Gödel et Kolmogorov mettent une sacré claque à cette conception dieudonnéenne des sciences.

Et au niveau très philosophique, est-ce-que les mathématiques façon Dieudonné sont le top du top ?
Certes, l'honneur de l'esprit humain est une jolie chose, et comme beaucoup de scientifiques je trouve dans les mathématiques plus de beauté que dans la danse, la musique, et autant que dans la grandeur d'acte. Mais je trouve que résoudre P=NP ou autre conjecture mathématique est mille fois moins important que de guérir le sida ou le cancer, et, pour reste interne aux mathématiques, que l'incomplétude de Gödel ou les processus stochastiques sont aussi beaux que la conjecture de Poincaré, même s'ils ont le mauvais goût (pour une conception dieudonnéenne), d'être plus directement applicables. Et je suis pourtant, dans ces exemples, bien loin du productif direct - même au niveau philosophique, le point de vue de Dieudonné est bien limité. 

 

On a les priorités qu'on veut, et je sais que dans mes collègues il s'en trouverait pour trouver que je suis un dangereux vendu au productivisme d'avoir ces positions là. Et les réformes actuelles de la recherche en France ? et sans doute ailleurs dans le monde ? Remarquez que je ne suis pas d'accord quand on dit que les réformes actuelles sont orientées vers le fait de faire de la recherche à court terme; je dirais plutôt qu'elles sont orientées vers le fait de faire de la recherche pourrie en écrivant le plus vite possible tant l'évaluation se multiplie et se base de plus en plus sur l'impact politique ou la quantité de papier consommée que sur la profondeur de la recherche; mon avis sur le fait qu'une belle application innovante c'est bon n'est donc pas, et de beaucoup, un avis favorable à la politique de Sarkozy et Pécresse en matière de recherche; ces deux tristes individus me paraissent les plus incompétents, les plus dangereux, des politiques se mêlant à la recherche, au même titre qu'Allègre.


Revenons en à plus intéressant, avec le cas de M. Dieudonné, qui est loin au-dessus de ces petits politiciens. D'ailleurs, je l'ai un peu caricaturé ci-dessus, et il ne méprise pas tant que ça le reste des mathématiques (juste un peu de temps en temps).

Dieudonné commence par rappeler à quel point la vision du grand public, selon laquelle les mathématiciens ne créent pas et ne fond que transmettre les mathématiques héritées des siècles passés, est immensément fausse. Merci de le dire, ça fait toujours du bien. Les mathématiques progressent, qu'on se le dise!

Qui est fort en maths ? Dieudonné dit ensuite que le talent mathématique ne se transmet pas par hérédité et n'est pas une question de race ou de milieu d'origine; qu'il faut un milieu favorable ET des dispositions - il ne tombe donc pas dans l'extrême consistant à croire que n'importe qui peut faire un grand mathématicien. En bref, il dit que les pays où l'éducation ne permet pas un contact avec la recherche abstraite ne produit pas de grand chercheur en maths, et que le génie mathématique peut apparaitre dans tous les milieux sociaux, à part ceux où l'on assassine Mozart par manque d'accès à la culture. Ainsi, Gauss n'était pas de milieu riche, et les immenses progrès récents des maths sont liés notamment à l'existence d'emplois où l'on peut garder du temps pour la recherche autrement qu'en faisant partie d'une élite de riche - Gauss a d'autant plus mérité qu'il a du travaillé pour vivre en dehors du fait qu'il révolutionnait les maths. La non hérédité des maths serait sans doute contestée par des psychologues, mais partiellement seulement.

Critère pour reconnaître les grands mathématiciens: ceux qui ont la médaille Fields, et quelques uns qui ont eu la malchance de ne pas être là les années où il y avait de la place pour des médailles Fields - Dieudonné ne fait donc pas partie des Fields, mais fait peut-être partie des grands mathématiciens pour ses propres critères (il ne le dit pas :-) ).

Les grands matheux sont-ils toujours des gens bien ? Non, assurément. On trouve des gens de toute religion ou absence de religion, de tout parti politique. A mon avis, même si l'on cite de ci de là le cas d'un nazi, il faut quand même dire que les chercheurs sont essentiellement de gauche sans être staliniens, et ouverts - je vois rarement des chercheurs racistes, homophobes, ou votant pour Sarkozy ou Le Pen. On voit aussi pas mal de schizophrènes légers (voire lourds comme Nash) dans la profession, ou des paranoïaques (comme l'immense Gödel) - quoique je manque de chiffres (toujours difficiles à obtenir, tant savoir quels sont les grands mathématiciens est sans doute difficiles, tant il est difficile de différencier celui qui tire la couverture à lui de celui qui produit vraiment), cela me parait empiriquement vrai, et le livre http://0z.fr/0g6xB semble assez bien l'expliquer d'ailleurs (loin de moi l'idée de conclure trop vite...).

Rappelons que Gödel a tâché de démontrer mathématiquement l'existence de Dieu (mais le Dieu en question pourrait décevoir les fanatiques, pas mal d'athées seraient sans doute d'accord avec l'existence de définition comme celle de Gödel...).



Comment fait-on de grandes maths ? En travaillant beaucoup, et en s'isolant beaucoup. Poincaré, grand matheux s'il en est, le disait beaucoup; et selon Dieudonné il faut beaucoup s'isoler pour arriver à faire de grandes choses, même si la pratique (récente) du séminaire aide beaucoup, et si Dieudonné reconnait que fréquenter des grands aide beaucoup à se lancer, il cite néanmoins des mathématiciens réussissant dans un isolement quasi-total (Grassman, Cartan, Hensel); début 19ème, les publications scientifiques régulières permettent l'essort des mathématiques (témoin évident de l'impact du milieu), trop limité par la publication par lettres; l'essort de la pratique du séminaire, à partir du milieu du 19ème, est aussi un grand outil. L'explosion du principe du séminaire, en grandes conférences très chères et dont l'objectif essentiel est de donner une évaluation quantitative stupide mais compréhensible par des "décideurs" bornés est une dérive bien gênante de ce système, qui n'est pas citée par Dieudonné - ça n'était sans doute pas pareil à son époque.

Pourquoi y a-t-il plein de grands chercheurs en Russie et dans les pays de l'est ? Un système éducatif très performant sans doute, mais Dieudonné ne commente pas ce point et le cite en le laissant inexpliqué; il explique aussi que l'Allemagne a détruit la recherche polonaise (par massacre) et sa propre recherche (beaucoup de chercheurs, notamment juifs, ont fui). Les Etats-Unis ont décollé tardivement, tant la construction du pays a accaparé les énergie; mais en récupérant les scientifiques en fuite ou ayant besoin de financements, ils ont rattrapé leur retard.

Et en France ? Si l'Ecole Polytechnique fournissait autrement les grands mathématiciens, c'est aujourd'hui plutôt l'école normale supérieure qui s'en charge.
La première guerre mondiale a ravagé la France, qui s'est bien remise par la suite.

Y a-t-il des bons chercheurs parmi les vieux ? Plutôt non, quoiqu'il y ait des exceptions, selon Dieudonné. C'est sans doute beaucoup moins vrai sur des maths moins abstraites, moins "pures" (je n'aime pas ce mot) que les seules maths que Dieudonné considère comme étant vraiment des mathématiques. Pour Dieudonné, vers 60 ans, c'est un peu cuit.

En conclusion ?
Voilà! Des points de vue qui m'irritent (et que je revois trop encore aujourd'hui), mais une lecture sympa quand même. Peut-être n'est-il pas faux néanmoins de dire que l'influence de Dieudonné a étouffé l'informatique en France et que c'est bien dommage.
Enfin, ce livre me donne l'occasion d'écrire quelque chose que mes confrères vont mépriser peut-être; ça fait du bien, quand mon entourage est d'accord avec moi je finis par croire que j'ai tort, et quand j'ai dit que j'ai aimé le film Watchmen je n'ai pas réussi à tellement fâcher les gens :-)

Repost 0
Published by teytaud - dans Recherche
commenter cet article
10 avril 2010 6 10 /04 /avril /2010 10:21

Quand votre PC ne vous sert pas à jouer, la carte graphique est un peu surdimensionnée. Alors qu'en faire ? La revendre est un peu laborieux, mais vous pouvez l'utiliser pour faire du calcul général: c'est le GPGPU (General-purpose computing on graphics processing units).

Attention! Je ne suis pas expert. Je découvre le sujet et écris ces lignes en vue de les améliorer au fil de ce que j'apprendrai sur le sujet. Tout commentaire bienvenu! Et si vous êtes anglophone vous trouverez plein de jolies choses ici: http://people.maths.ox.ac.uk/gilesm/cuda/

Version NVIDIA.



Pour que ceci soit accessible au plus grand nombre, je mets un peu de lexique en bas de page.

Comment coder sur GPU ?

CUDA est le langage le plus classique pour ça. Très proche du C, vous faites très vite un code qui écrit "hello world" et après vous pouvez décoller vers de vraies applications très rapidement.

Cela dit, c'est plus dur que de coder en C ou autre: en particulier, on ne peut pas faire un hello world super facilement (il faut une couche CPU et une couche GPU mise en place par le couche CPU), et le code produit est forcément modérément portable, puisqu'il ne marchera pas (sauf en émulation) sur une machine qui n'a pas de GPU...

La compilation est assez simple:

nvcc -o monBinaire moncode.cu

où ".cu" est l'extension des programmes cuda.

Quelques morceaux de code ?

Voilà un exemple:

  • cudaMalloc(): pour allouer de la mémoire sur GPU.
  • cudaMemcpy(): pour copier de la mémoire du GPU vers le CPU.
  • cudaFree(): libérer un bloc mémoire sur le GPU.
  • maFonction<<<nbBlocs, nbThreads>>>( mes arguments);
    execute maFonction sur nbThreads dans chacun des nbBlocs.
  • __shared__ int maVariable: pour une variable partagée entre tous les threads d'un bloc.
  • __syncThreads: on attend que tous les threads soient arrivés à cette ligne pour pouvoir continuer.


La page http://llpanorama.wordpress.com/2008/05/21/my-first-cuda-program/ fournit un très joli premier exemple, que je vous recopie en bas de cette page par peur qu'il ne disparaisse d'internet.

Et pour débugguer / optimiser un peu ?

Pour trouver les erreurs, avoir des printf est drôlement commode.
Or, pas de "printf" sur GPU. Ouf! Compiler avec

nvcc --device-emulation -o monexecutable moncode.cu

permet d'avoir un executable émulé, et là les printf sont autorisés.

Votre premier programme devrait être lent, c'est normal.
Comment accélérer ?

  • rendre local à chaque thread toutes les lectures mémoires possibles. C'est là que l'on gagne le plus vite et le plus facilement.
  • rendre local à chaque bloc toues les lectures mémoires possibles. Ce n'est pas pareil que ci-dessus! Il faut veiller à lire "en interne au thread", dès que possible, et en interne au bloc sinon, et seulement en dernier recours revenir à la mémoire du CPU.


Pour aller plus loin, il y a des profileurs CUDA qui trouveront où vous perdez du temps.

Et l'installation de CUDA pour coder sur GPU ?

Ca implique
d'avoir récupéré les ".run" (pour Linux) ici:
http://developer.nvidia.com/object/cuda_3_0_downloads.html

et de les installer:
chmod +x cudadriver_2.3_linux_64_19

0.18.run cudatoolkit_2.3_linux_64_ubuntu9.04.run cudasdk_2.3_linux.run
(ou cf http://doc.ubuntu-fr.org/cuda).

Forcément, c'est moins "tout inclus" que du C ou C++ ou java
où tout est par défaut dans linux, mais j'imagine que ça viendra.

Est-ce un outil générique de calcul parallèle ?



Comparaison entre puissance CPU et puissance GPU d'après
http://people.maths.ox.ac.uk/gilesm/cuda/lecture1.pdf
Vu comme ça ça fait envie, mais ça n'est pas si puissant que ça pour tout.
Il y a des choses particulières quant on programme sur GPU:
  • La mémoire est d'une part sur le GPU central et d'autre part sur chacun des blocs.
  • L'accès à la mémoire est:
    • assez lent dans tous les cas; au sein d'un bloc, il faut éviter d'avoir trop de threads qui accèdent simultanément à la mémoire d'un bloc (limite aux alentours de 16, sinon il y a ralentissement).
    • très lent pour ce qui est du transfert de la mémoire "centrale" de l'ordinateur vers la mémoire du GPU.
    • limité aussi de chaque bloc vers la mémoire centrale.
  • Le GPU est composé d'environ 128 blocs qui peuvent calculer indépendamment (mais avec un accès à la mémoire globale limitée).
  • Au sein d'un bloc, on travaille essentiellement en "stream processing", sur flux: c'est-à-dire qu'on ne fait pas (pas trop) de branchements qui ne donnent pas la même branche. Idéalement on peut avoir parait-il 512 threads par bloc, mais en pratique ils vont forcément se marcher un peu dessus.

  • Petite mémoire sur chaque bloc; de l'ordre de 16Ko; ça va vite!
  • Le calcul flottant est (sur beaucoup de GPU) en 32bits, alors que sur les CPU le 64bits se répand. Cela dit pour beaucoup de gens, 32bits ça suffit.

Méfiez-vous des comparatifs de puissance de calcul qui oublient souvent le temps de transfert vers la mémoire du GPU!

Alors, qu'est-ce-qui se programme bien sur GPU ?

Deux niveaux de parallélisme: 128 blocs, avec des threads plutôt SIMD sur chaque bloc.
Le cas idéal: beaucoup de donner à traiter, sans avoir des branchements sur chaque donnée.

Et ce que j'en ai vu ?

Les gens trichent parfois! Ils disent qu'ils ont un speed-up X ou Y mais ils ne prennent pas en compte les transferts mémoire. Obtenir des super-grosses
accélérations n'est pafs trivial. Sur le papier on peut atteindre des chiffres mirifiques avec 128 blocs de 512 threads, mais les threads d'un bloc ont un accès très limité à la mémoire et il est donc rare que l'on puisse atteindre des chiffres pareils. Les blocs sont supposés pouvoir travailler à peu près indépendamment, mais les premiers essais que l'on a fait ici n'étaient pas fantastiques.

Monte-Carlo Tree Search is a great algorithm which can be very efficient for the game of Go, and also for difficult planning.


Les jeunes centraliens qui par ici se sont lancés dans le codage de MCTS
(http://teytaud.over-blog.com/article-35709049.html) en GPU ont fait de l'honnête travail, et néanmoins leurs performances sur GPU restent loin en dessous d'un simple CPU. Le travail d'optimisation ne fait que commencer et j'espère rectifier ces nouvelles dans un sens plus optimiste prochainement...


Glossaire.

  • Cuda: le langage le plus classique pour coder sur GPU.

  • GPU: processeur graphique! le truc qui fait que les jeux vidéos vont vite.

  • GPGPU: le fait d'utiliser le GPU pour faire autre chose que du graphique.

  • Parallélisme: le fait d'effectuer un grand nombre d'opérations en même temps.

  • MIMD: parallélisme permettant d'effectuer un grand nombre d'instructions différentes à un grand nombre de données différentes ("multiple instructions multiple data").

  • SIMD: parallélisme basé sur le fait d'appliquer une même instruction à plein de données différentes en même temps ("single instruction multiple data"). Le GPU peut faire du MIMD, mais au prix d'un très fort ralentissement; il convient d'être "aussi SIMD" que possible dans du code GPU.



Un échantillon provenant de http://llpanorama.wordpress.com/2008/05/21/my-first-cuda-program/ et que je recopie ici par peur que ce très bel exemple disparaisse d'internet (ce programme élève au carré chaque élément d'un tableau).

// example1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <stdio.h>
#include <cuda.h>

// Kernel that executes on the CUDA device
__global__ void square_array(float *a, int N)
{
int idx = blockIdx.x * blockDim.x + threadIdx.x;
if (idx<N) a[idx] = a[idx] * a[idx];
}

// main routine that executes on the host
int main(void)
{
float *a_h, *a_d; // Pointer to host & device arrays
const int N = 10; // Number of elements in arrays
size_t size = N * sizeof(float);
a_h = (float *)malloc(size); // Allocate array on host
cudaMalloc((void **) &a_d, size); // Allocate array on device
// Initialize host array and copy it to CUDA device
for (int i=0; i<N; i++) a_h[i] = (float)i;
cudaMemcpy(a_d, a_h, size, cudaMemcpyHostToDevice);
// Do calculation on device:
int block_size = 4;
int n_blocks = N/block_size + (N%block_size == 0 ? 0:1);
square_array <<< n_blocks, block_size >>> (a_d, N);
// Retrieve result from device and store it in host array
cudaMemcpy(a_h, a_d, sizeof(float)*N, cudaMemcpyDeviceToHost);
// Print results
for (int i=0; i<N; i++) printf("%d %f\n", i, a_h[i]);
// Cleanup
free(a_h); cudaFree(a_d);
}
Repost 0
Published by teytaud - dans Recherche
commenter cet article
16 février 2010 2 16 /02 /février /2010 23:46
ATTENTION CECI EST UN BROUILLON, je me suis un peu embrouillé dans mes notes de lecture et doit revoir.

A. Demaret a écrit "Ethologie et psychiatrie" , qui étudie l'origine des maladies mentales, et dont je vais vous parler. Je ne suis pas expert et risque donc d'être imprécis; en outre, j'ai lu ce livre il y a fort longtemps et écrit de mémoire à partir de notes trop brèves. En tout cas, le livre a le mérite de tenter une explication intéressante. Ca donne envie d'essayer de faire du calcul sur des chiffres pour voir si tout colle; matheux, informaticiens, on pourrait avoir du pain sur la planche...

Une stimulante lecture pour expliquer l'origine des maladies mentales.



Tout d'abord les maladies qui sont peut-être utiles.

Tout d'abord on parle de phylogénèse des maladies mentales; d'où viennent ces étranges maladies mentales ? Pour y répondre l'auteur fait le louable effort d'être quantitatif.

Certaines maladies seraient trop fréquentes pour être un hasard (au vu du risque de mutation malvenue); on peut donc soupçonner que, de même que l'anémie drépanocytaire semble avoir des avantages contre le paludisme (ainsi que, peut-être, le diabète et la mucoviscidose auraient des avantages cachés), les maladies mentales pourraient avoir un atout indirect. N'oublions pas aussi que parfois, une maladie correspond à un coup de pas de chance génétique, explicable par l'intérêt du gêne quand il n'est présent qu'à moitié (pour faire simplifié, biologistes pardonnez-moi).

La schizophrénie est naturellement un candidat de choix. Les schizophrènes ont une vie amoureuse faible, et un goût intense pour la vie intellectuelle (comme M. Nash célèbre pour ses travaux sur les jeux qui justement auraient des applications pour la compréhension de l'existence de la schizophrénie). Quel est l'intérêt caché du schizophrène ? Il serait exceptionnellement résistant à certaines infections et atteintes physiques, et d'autres parts les schizoides, qui sont pour simplifier un cas léger de schizophrènes, ont eux une forte capacité à la reproduction pour l'attrait qu'ils entrainent. En outre, le schizophrène peut être très utile au groupe par son investissement intellectuel, et peut donc être sélectionné par une pression sélective à l'échelle d'une population et non de l'individu.

De même, les maniaco-dépressifs, via leurs périodes de fort dynamisme, sont fort utiles parfois - le livre "psychoportraits du 20ème siècle", dont je vous parlerai un de ces jours, fournit de nombreux exemples.

Mais à quoi servent les psychopathes ?
Ils prennent des risques, ils recherchent des satisfactions immédiates, des nouveautés; ils sont utiles pour les métiers à risques ou pour des temps troubles. Là encore, le livre "psychoportraits" peut être appelé à la rescousse pour illustrer le propos.

Les informaticiens qui pratiquent l'évolution artificielles pour des problèmes d'ingénierie penseront peut-être au phénomène dit de "bloat", où des choses bizarres sont sélectionnées alors qu'elles conduisent à des individus forts bizarres occasionnellement.

Seconde partie: les comportements étranges hérités des animaux ?

Une seconde partie du livre parle de la phylogénèse des comportements; on parle des 3 cerveaux dits (i) reptilien (ii) paléomammifère (iii) néomammifère; on évoque ensuite l'homologie (similitude d'origine phylogénétique) et l'analogie (similitude de pression environnementale) comme explications possibles de ressemblances entre des espèces.

On y développe ensuite des exemples de mémoire génétique comportementale:

  • la prédisposition à fuir vers le noir chez le rat; cet apprentissage n'est pas exempt d'a priori bien sûr; et si le rat peut avoir des tendances génétiques comme celles-ci, possiblement mal venues pour pas mal de cas, on peut s'interroger si on a le même phénomène chez l'homme.
  • Prédisposition à apprendre les aversions alimentaires, notamment avec délai entre ingestion et trouble (point dont on devine qu'il est dur à apprendre vu la pénalité décalée dans le temps avec l'acte, et que donc une prédisposition génétique semble utile).



Sur ces bases, l'auteur explique des comportements psychologiques non standards par la phylogénétique.

D'abord, qu'en est-il des substitutions constatées chez les animaux, où un comportement est remplacé par un comportement sans rapport, comme l'abandon d'un combat qui devient dormir ou manger ou faire la toilette; l'explication étant l'évitement d'un conflit interne trop violent entre la tendance au combat et la tendance à fuir.

A partir de là, l'auteur essaie d'expliquer de similaires substitutions chez l'homme:

  • masturbation inconsciente (main dans le pantalon pour un enfant qui regarde un jeu auquel il aurait envie de participer),
  • éjaculation au moment d'un rendu de copie (situation tendue),
  • sommeil soudain chez des soldats au front,
  • rire nerveux en situation tendue.


L'auteur évoque aussi le fait de se tonger les ongles, ou les rituels comme les toilettes aberrantes (j'imagine qu'on parle actuellement de T.O.C.), et des troubles psychosomatiques.

Les maniaco-dépressifs (chez qui se succèdent manie et mélancolie) ont beaucoup de similitudes avec des comportements animaux: souvent, ils sont, comme le suicide, liés au printemps ou à l'automne qui ont de l'impact sur des espèces animales; ils subissent aussi l'effet du matin; ils ont parfois des cycles de 48h ou un an; souvent, des parents de maniaco-dépressifs conçoivent des bébés au 2ème trimestre (ce qui n'est pas le cas du reste de la population); ils ont enfin une force musculaire particulière ainsi qu'une absence de fatigue malgré inappétence et insomnie. Tout cela évoque un comportement de type territorial de groupe (classique dans le règne animal); ce comportement animal apparait à l'âge adulte, est lié à la conception de bébé et à l'alimentation, a des liens avec printemps et automne; la mélancolie pourrait être associée aux "sorties de territoire". Signalons que les déménagements sont très générateurs de dépressions.

D'autres particularités psychologiques sont esquissées sous le même angle de l'éthologie:

  • l'anorexie, souvent corrélée avec la tendance au soin, à l'altruisme alimentaire, à l'aide aux femmes enceintes et aux enfants;
  • les phobies pourraient être ataviques; en effet, l'auteur signale qu'il n'y a pas de phobies pour des outils ne faisant du sens qu'à l'époque moderne comme les voitures. L'agoraphobie serait liée à la peur de quitter le territoire
  • l'hystérie pourrait dans cette analyse être un comportement territorial individuel (classique dans le règne animal).



On peut continuer avec les catatonies en cas de stress, liées au cerveau sous-cortical: l'analogie est proposée avec la simulation de mort pour échapper aux prédateurs. La tendance à répéter des mouvements parfois constatée peut être analogue à la tendance à se fondre dans un décor agité par le vent ou à la tendance à suivre le troupeau pour fuite sûre; la provocation de cette catatonie par hypnose évoque les paralysies face aux regards des prédateurs (mécanisme utilisé par les papillons dotés de "faux yeux" sur leurs ailes pour terroriser leurs éventuels prédateurs).

L'hystérie de conversion s'explique-t-elle par divers comportements de sactifices pour le groupe ?
Le comportement de bouc émissaire pour augmenter la cohésion de groupe ? Serait-elle analogue à la tendance à attirer le prédateur avant de fuir dans les arbres ou les airs ? On observe parait-il chez ces humains une tendance à se jeter en arrière et à "battre des ailes". L'hystérie de conversion entraine aussi un comportement sexuel particulier propre, peut-être, à favoriser la cohésion de groupe. Les individus touchés peuvent aussi tendre à agripper, comme pour protéger des enfants; et avoir une paralysie de la main, qui évoque la "feinte de l'aile brisée", utilisée par certains animaux qui feignent une blessure au bras pour attirer le prédateur (loin des enfants) qui croit voir une proie facile.

Voilà. On trouvera ça tiré par les cheveux, peut-être (mais pas autant que Freud dans ses moments disons de grande forme); intéressant livre en tout cas, lecture stimulante. Je suis preneur d'avis pour améliorer cette discussion.

Repost 0
Published by teytaud - dans Recherche
commenter cet article
16 février 2010 2 16 /02 /février /2010 22:49
J'ai beaucoup aimé "Les sociétés animales: lions, fourmis et ouistitis", de Cézilly, Giraldeau et Théraulaz, aux éditions Le Pommier.

Les troupeaux de lionnes sont plus grands qu'ils ne devraient pour une chasse optimale. Est-ce-que c'est parce que les lionnes sont bêtes ? Un peu. Profondément, elles sont sélectionnés par l'efficacité individuelle, or dans ce cas comme dans beaucoup l'optimum pour chacun n'est pas l'optimum pour le groupe. Les théoriciens des jeux ne seront pas surpris. Le point sympathique dans cet exemple est qu'il est numérique et pas seulement qualitatif, contrairement à la plupart des cas cités plus bas.

Du bon livre à 8 euros, facile à transporter en métro.


Citons un deuxième cas "assez" quantitatif, avec la prévision du taux de capucins damiers qui préfèrent voler la nourriture de leurs collègues, plutôt que participer aux recherches de nourriture; prévision en fonction de la densité des ressources et du volume des ressources. Les damiers capucins sont instinctivement doués en théorie des jeux semble-t-il. Qui fait le calcul du taux de voleurs attendu chez l'espèce humaine ?

Pour la suite, rappelons que polyandrie signifie plusieurs mâles pour une femelle et polygynie plusieurs femelles pour un mâle.

Que penser de ces femelles qui se regroupent pour séduire un mâle ? Chez les lions, c'est ainsi que les femelles attirent un mâle tout en gardant la force d'empêcher l'infanticide. Le mâle, en effet, s'il le peut, préfère largement tuer les enfants déjà présents pour favoriser sa propre descendance. On peut pas dire que ça ait l'air optimal globalement pour l'espèce. Il serait élégant de mathématiquement prédire la taille des groupes de lionnes dans ces polygynies, pour voir si on est dans une situation évolutivement stable, c'est-à-dire individuellement optimale, ou si une sélection naturelle à l'échelle du groupe a développé quelque chose d'un peu plus près d'un optimum global (même si on se doute que ça ne peut être une coopération totale, vu l'espèce d'équilibre complexe pour éviter que monsieur ne consomme les enfants).

Parlons des leks. La compétition sexuelle peut conduire à des situations où les mâles s'entassent à des endroits parfois complètement dépourvus de toute ressource naturelle, ce qui est sans doute dommageable à l'espèce. Les femelles viennent, choisissent le mâle qu'elles veulent (et souvent il y en a un ou deux qui récupèrent toutes les occasions de procréer) et repartent. La compétition sexuelle chez les animaux me laisse parfois pantois; il faudrait voir la part de sélection au niveau du groupe et au niveau de l'individu pour y comprendre quelque chose, et puis mieux comprendre le mécanisme peut-être... Là j'ai eu le sentiment de ne pas vraiment avoir compris le fond de l'affaire; comment l'évolution produit elle ces cas où un très grand nombre d'individus acceptent de n'avoir aucune chance de se reproduire ? Peut-être qu'il y a matière à analyse mathématique, comme dans le cas de la taille des troupeaux de lionnes, pour voir si on est dans un optimum au niveau individuel, ou si un niveau plus global a pu opérer par sélection de groupes vis à vis d'autres groupes...

Ah, la réutilisation de techniques acquises pour une tâche pour une autre tâche, ça va plaire aux informaticiens. Ainsi, les fourmis gèrent-elles l'agrégation des cadavres de congénères comme elles transportent des boules de terre (les connaisseurs parleront mieux que moi du langage à ce propos, qui est peut-être né incidemment à d'autres progrès de l'homme). Sacrés bestioles ces fourmis. Les informaticiens aimeront aussi les discussions sur la stigmergie, qui est l'art de trouver quoi faire juste en fonction de ce qu'on observe immédiatement sans trop de mémoire, à l'opposé des cas de séquentialité où l'on agit en fonction de sa mémoire seulement. Les matheux pourront faire l'analogie avec les catégories de planification.

On trouvera aussi dans le livre une analyse (un peu vite fait) de l'organisation sexuelle en fonction des contraintes physiologiques et des ressources naturelles présentes, supposée prédire les variantes de polygynies. On s'éloigne un peu du quantitatif, mais sans sombrer dans le flou.

On apprendra que la polyandrie est observée seulement chez quelques oiseaux et primates, et aussi que les hippocampes sont de sacrés amoureux.
L'hippocampe très tendre et très monogame ?


On verra des exemples d'espèces où des individus deviennent physiologiquement incapables de descendance et s'investissent dans l'aide à leurs proches (au sens génétique), de manière à diffuser leurs gênes.

L'éthologie est un domaine toujours amusant où l'on pourra trouver la prostitution chez les animaux, le mensonge au conjoint, la monogamie, toutes ces choses pas si spécifiquement humaines que ça. Et oui, il y a des insectes monogames. Dans d'autres livres sur l'éthologie on trouvera une explication de l'avantage reproductif de l'homosexualité chez les oies (ce n'est pas dans ce livre-ci je crois). Dans le livre "Life at small scale" on trouvera des cas intéressants de très forte collaboration entre animaux, puisque certains microbes sont capables de suicide dans l'intérêt de la communauté. La valeur n'attend pas le nombre de micromètres.

Voilà, un peu, mais peu quand même, de quantitatif de théorie des jeux. Il reste des choses à faire sans doute. Signalons pour ceux qui veulent adapter la théorie des jeux à la nature que la schizophrénie a parfois été interprêtée comme un moyen individuellement très sous-optimal mais collectivement utile; bientôt plus sur ce sujet dans ces lignes. Mais je doute que la théorie des jeux arrive à nous faire comprendre qu'un type décède en copulant avec une pelleteuse (voir mon article sur le médicolégal pour plus d'informations là-dessus).
Ca vous fait envie, vous ?
Repost 0
Published by teytaud - dans Recherche
commenter cet article
11 novembre 2009 3 11 /11 /novembre /2009 09:47



Imaginez que votre ordinateur soit incapable de résoudre un problème. Par exemple, lire un mot manuscrit passé par un scanner, chose utile pour traiter automatiquement des chèques ou des adresses postales par contre. Les ordinateurs font ça plus ou moins bien, mais sans arriver à résoudre les cas vraiment difficiles. Alors comment faire ? Faites en un jeu!

Vous ouvrez un site internet. A chaque fois que votre programme n'arrive pas à lire un mot, paf! il l'envoie sur le site. Les joueurs ont pour tâche de lire le mot.

Ok, mais et si le joueur essaie de tout faire foirer, en disant n'importe quoi ? C'est là que le jeu est trop fort: vous gagnez des points si vous trouvez la même réponse que les autres. Si la plulpart des joueurs jouent vraiment, alors ils ont intérêt à trouver la bonne réponse. Ca y est, vous avez un programme de Gwap.

La même chose permet d'étiqueter des images; si vous cherchez un nounours sur google "images", il faut que google images soit capable de trier les images. Alors comment faire ? Et bien les petits robots google qui se promènent sur internet collectent des images, les étiquettent avec les mots qui la décrivent sur le web quand une description est disponible, et ensuite complètent les étiquettes avec des Gwap: les joueurs voient des images, et doivent trouver des descripteurs pertinents.

Voilà. D'un côté ça permet difficilement de faire de l'intelligence artificielle vraiment au dessus de ce que peut faire l'humain - mais comme on n'arrête pas de voir que l'humain a encore beaucoup de marge avant que les machines ne le rattrapent, c'est une solution amusante pour certains problèmes. Enfin, tant qu'il y a des gens qui trouvent ça drôle de jouer aux Gwaps. Des Gwaps rémunérés bientôt peut-être ? Comme ça on aura des patrons "machines" au lieu d'avoir des ressources humaines imbéciles, ça sera pas plus mal finalement. Au moins les critères de revenu pourraient être transparents.

Repost 0
Published by teytaud - dans Recherche
commenter cet article
29 octobre 2009 4 29 /10 /octobre /2009 15:49
99a
The first ever win of a computer as black in 9x9 Go against a 9P.


Our Taiwanese partners for a ANR grant have organized public demonstration games between

MoGoTW (based on MoGo 4.86.Soissons + the "TW" modifications developped
jointly with our Taiwanese colleagues), with support by Grid5000
and
C.-H. Chou 9P, top pro player winner of the LG Cup 2007.


The algorithm is presented in another page http://teytaud.over-blog.com/article-35709049.html .
This was during a press conference at Taipei around a French-Taiwanese grant for joint research.

Comments by the pro:
He told the jounalists that he made a mistake on move 26 - an error hard to read, even for a professional Go player (see picture below).


99b.jpg
The suboptimal move made by the pro (move 24, on the left, center).


However, he was so surprised that MoGoTW found this mistake that he made during the game. That means the level of MoGoTW in 9x9 game has made an improvement than last time (08/2009).

In addition, he also told the journalists that MoGoTW made a good move at Move 29 (see picture below). He thought that the main reason that MoGoTW won the game was Move 29 and MoGoTW didn't make any mistake after Move 29.

99c.jpg
Very good move by mogoTW (move 29, on the upper right part).


The final position is indicated below; the big white group F6 is dead.



Authors of MoGo:
Contributors include all the mogo-people, plus Mei-Hui Wang, Chang-Shing Lee, Shi-Jim Yen, Hsien-Der Huang and Cheng-Wei Chou.

Details:
a) MoGoTW was running on 32 eight-cores in Taiwan.
b) There were two blitz games (15 minutes per side), won by the pro.
c) There was one non-blitz game (45 minutes per side). MoGo was unlucky
as it was black, but it nonetheless won the game. This game is enclosed.
All games can be found on KGS (account nutngo)



Remarks:


a) Fuego won as white against a 9P a few months ago. Therefore computers
have won both as white and black against top players :-) We now should
win on a complete game like 4 out of 7 games and the job would be
completly done for 9x9 Go :-)

b) MoGo already won a game as black, against Catalin Taranu, but I guess
the pro, at that time, had played an original opening somehow for fun
(I'm not sure of that, however).

c) My feeling is that blitz games are not favorable to computers... Statistics
are in accordance with this I guess. Humans are stronger for short time
settings.

d) The game was longer than most important games I've seen (59 moves).

All comments welcome.

Best regards
Olivier


============= the SGF file =========================================
(;GM[1]FF[4]CA[UTF-8]AP[CGoban:3]ST[2]
RU[Chinese]SZ[9]KM[7.50]TM[2700]
PW[nutngo]PB[MoGoTW9X9]DT[2009-10-26]PC[The KGS Go Server at http://www.gokgs.com/]C[MoGoTW9X9 [-\]: GTP Engine for MoGoTW9X9 (black): MoGo version MoGo version 4.86.Soissons: I'll resign if you win and playing until you pass if I win. If you passed and I did not, it often means that the status of some stones are not clear enough for me (I want to be sure we will agree on dead stones). Clarify them. Maybe I am losing, but have not enough time to be sure I should resign. In this case play until the end :'( (very rare cases)
]RE[B+Resign]
;B[ee]BL[2699.494]
;W[ge]WL[2652.472]
;B[gf]BL[2699.208]
;W[ce]WL[2597.429]
;B[cd]BL[2698.918]
;W[ff]WL[2574.488]
;B[fe]BL[2698.64]
;W[gg]WL[2573.551]
;B[hf]BL[2698.336]
;W[gd]WL[2572.792]
;B[fg]BL[2490.513]
;W[ef]WL[2569.373]
;B[de]BL[2283.362]
;W[fh]WL[2451.256]
;B[eg]BL[2092.766]
;W[df]WL[2436.298]
;B[gh]BL[1919.531]
;W[dg]WL[2431.654]
;B[hg]BL[1757.395]
;W[bd]WL[2340.808]
;B[cc]BL[1756.26]
;W[ec]WL[2283.551]
;B[be]BL[1755.969]
;W[cf]WL[2281.403]
;B[bf]BL[1755.694]
;W[eh]WL[2271.753]
;B[dd]BL[1610.253]
;W[bg]WL[2268.966]
;B[gc]BL[1476.576]
;W[fd]WL[2260.802]
;B[hc]BL[1354.659]
;W[fc]WL[2151.486]
;B[db]BL[1243.165]
;W[hd]WL[2141.275]
;B[gb]BL[1140.924]
;W[fa]WL[2119.7]
;B[id]BL[1047.266]
;W[ie]WL[2112.227]
;B[he]BL[961.171]
;W[ic]WL[2109.32]
;B[ib]BL[882.168]
;W[ha]WL[2104.112]
;B[id]BL[809.979]
;W[bc]WL[2100.375]
;B[bb]BL[743.745]
;W[ic]WL[2097.445]
;B[fb]BL[683.217]
;W[eb]WL[2094.669]
;B[id]BL[626.972]
;W[af]WL[2082.434]
;B[ga]BL[576.013]
;W[ab]WL[2068.078]
;B[ea]BL[529.084]
;W[ba]WL[2060.281]
;B[cb]BL[486.46]
;W[gg]WL[2057.484]
;B[hi]BL[447.483]
;W[fg]WL[2053.419]
;B[ih]BL[411.532])




Repost 0
Published by teytaud - dans Recherche
commenter cet article
20 septembre 2009 7 20 /09 /septembre /2009 09:20

 On embauche sur deux profils:
- vous avez un master 2: venez en thèse
- vous avez une thèse: venez en post-doc

Compétences requises:
- Solide expérience de programmation
- Un premier contact avec optimisation ou intelligence artificielle est un plus
- De bonnes bases de mathématiques appliquées ou statistiques sont un plus
- Bonnes capacités relationnelles très bienvenues.

Key words:
- Machine learning
- Open source & collaborative development
- Video games (first person shooting)
- Robotics

Contact:
olivier.teytaud@inria.fr
http://www.lri.fr/~teytaud/

Localisation:
Ile-De-France sud (RER B Orsay Ville)

Sujet:

This project aims at developing new machine learning methods relying on very large number of hand-designed heuristics, together with statistical tools to facilitate the design of these heuristics in an open and collaborative framework.
We define an heuristic to be any algorithm processing raw inputs to produce values relevant to the problem at hand. This purposely very general definition encompasses techniques spanning from simple signal processing to symbolic modeling or locally trained predictors. Since we assume high performance can only be achieved by combining hundreds of such heuristics, we propose to develop them collaboratively, in a way similar to the successful development process of open-source software or collaborative encyclopedia.
We will assess the performance of that strategy on the control of an avatar in a realistic 3D simulator and on the control of a real robotic arm, and we aim at creating a generic software platform usable on alternative applications.
Hence, the key aspects of this proposal are to:
- develop novel statistical techniques for prediction and goal-planning with a very large heterogeneous set of features,
- develop statistical tools such as similarity measures in the space of features to help the design of very large sets of heuristics by many contributors,
- assess the efficiency of this approach on a series of complex tasks in a realistic simulated 3D environment and with a real robot arm.

The five partners of the consortium are from the fields of applied and theoretical statistical learning, reinforcement learning, artificial vision and robotics.

Repost 0
Published by teytaud - dans Recherche
commenter cet article