Carnet du petit Tom : Physique, biologie et évolution...

16 janvier 2007

Pensée et algorithmes génétiques

Je lis pas mal de livres sur l'optimisation numérique et ses liens avec les algorithmes génétiques en particulier. Je parcours en ce moment même Genetic Algorithms, in search, optimization and machine learning, de David E. Goldberg. Goldberg cite cet extrait d'un livre d'Hadamard , The psychology of invention in mathematical field :

We shall see a little later that the possibility of imputing discovery to pure chance is already excluded...On the conrary, that there is an intervention of chance but also a necessary work of unconsciousness, the latter implying and not contradicting the former... Indeed, it is obvious that invention or discovery, be it in mathematics or anywhere else, takes place by combining ideas


Ainsi Hadamard suggère-t-il que toute découverte est le processus d'une recombinaison aléatoire de pensées. L'homme sait ensuite reconnaître les pensées créatrices, les bonnes idées innovantes. C'est exactement le procédé à la base des algorithmes génétiques : le hasard est dans la recombinaison des différents génomes articifiels, ensuite, l'algorithme utilise une fonction de score pour évaluer l'adaptation des nouveaux circuits génétiques produits. Alors, le cerveau ne serait-il qu'une machine très perfectionnée permettant de recombiner les idées, puis d'évaluer la pertinence de celles-ci ? Autrement dit, le mécanisme de la pensée ne serait-il qu'un algorithme génétique un peu sophistiqué (*) ?


(*) Si l'on en croit le No Free Lunch Theorem, cela signifierait alors qu'il y aurait des domaines entiers tout simplement inconcevables par l'esprit humain, celui-ci étant adapté spécifiquement à certains problèmes. Poussons un peu plus loin le raisonnement pseudo-philosophique : j'imagine alors que les vérités accessibles par raisonnement sont les vérités démontrables, autrement dit tout ce qui peut être vérifié par une machine de Turing. Les vérités non accessibles par le raisonnement (non démontrables, non décidables) ne sont alors peut-être pas complètement inaccessibles, il s'agirait du domaine de l'intuition de Turing :

In his investigation, Turing introduced the idea of an ‘oracle’ capable of performing, as if by magic, an uncomputable operation. (...) An oracle is infinitely more powerful than anything a modern computer can do, and nothing like an elementary component of a computer. (...) But these oracle-machines are not purely mechanical. They are only partially mechanical, like Turing's choice-machines. Indeed the whole point of the oracle-machine is to explore the realm of what cannot be done by purely mechanical processes. Turing emphasised:

We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine.

Turing's oracle can be seen simply as a mathematical tool, useful for exploring the mathematics of the uncomputable. (...) Thus Turing opened new fields of investigation in mathematical logic. However, there is also a possible interpretation in terms of human cognitive capacity. On this interpretation, the oracle is related to the ‘intuition’ involved in seeing the truth of a Gödel statement.

12 commentaires:

seven a dit…

Très intéressant (comme d'hab)...
Un avantage dont dispose le cerveau, c'est sa grande plasticité. Il peut créer de nouvelles synapses, ou même de nouveaux neurones. Il doit avoir des limites imposées par la biologie (j'imagine) mais il semble difficile de les prédire: plus on le fait travailler, plus il devient performant, en gros (ex: plus on apprend par coeur, plus c'est facile de le faire). Je ne sais pas si je m'exprime clairement(je peux essayer développer, mais ça risque de prendre de la place!)
Seven

blop a dit…

pour bosser dans les neurosciences et dans l'optimisation (oui, oui, je me la pete) ma conclusion est : mefions-nous des generalisations hatives !!!
oui, je sais, c'est facile comme commentaire mais je vais prendre un exemple : on parle de "depression" parce qu'a la fin du 19e la thermodynamique etait a son apogee et les medecins ont cru pouvoir l'appliquer a la psychiatrie.

t'as jete un oeil du cote des essaims particulaires (dedieu j'ai eu du mal a trouver la traduction francaise) ? ou des "differential evolution" (la je cherche plus) ? c'est un peu plus recent mais ca a l'air plutot pas mal

Tom Roud a dit…

A seven : merci pour la précision. Cependant, les limitations dont je parle ici ne sont pas des limitations dues au "hardware", mais bien des limitations intrinsèques, exactement comme le problème de la décidabilité (c'est une limitation algorithmique, une limitation du logiciel si tu veux ; tu auras beau avoir un cerveau 10 fois plus gros, ton "algorithme" de pensée sera a priori identique )

A blop : merci de l'avertissement ;) . Je l'avoue, c'était un petit peu un billet free-style, résultant précisément d'une recombinaison aléatoire entre deux de mes lectures actuelles. Mon algorithme de sélection des idées n'est peut-être pas si performant !
Je ne connaissais ni les essaims particulaires, ni la differential evolution, je vais me pencher dessus...

Matthieu a dit…

j'étais d'accord avec toi jusqu'au moment ou tu compares le cerveau avec un machine de Turing. Avec son fonctionnement partiellement aléatoire et ses "recombinaisons" d'idées, j'aurais imaginé que l'on puisse voir le cerveau comme une non-machine de Turing, qui explore justement d'autres espaces (intuition, art, tout ca) mais à laquelle un certain nombre de problèmes restent inaccessible, par le no free lunch theorem.

dvanw a dit…

Je n'avais jamais entendu parler de cettre notion d'oracle chez Turing... Je n'arrive pas bien d'ailleurs à comprendre ce qu'elle recouvre ? Le cerveau humain - qui peut, lui, accéder à la vérité d'une assertion de Gödel - est-il un oracle au sens de Turing ?

Et puis, autre question : qu'est-ce que les algorithmes géntiques changent au tableau ? Ne sont-ils pas soumis exactement aux mêmes limitations que leurs collègues en dur ? Ou me trompe-je ?

Merci en tous cas pour ce billet très inspirational !

Tom Roud a dit…

Merci pour vos commentaires
N'étant pas spécialiste, peut-être me trompé-je, mais voilà ce que je pense en fonction de mes lectures :

à Matthieu : en fait mon idée était que la machine de Turing permet de vérifier les propriétés mathématique trouvées par le cerveau par raisonnement. Si je découvre un théorème par association d'idée, la machine de Turing est capable de vérifier que le théorème est vrai (en vérifiant la démonstration si tu veux), de la même façon que le cerveau est capable de démontrer le théorème. Apparemment la machine de Tuing a été précisément imaginée pour donner une définition claire à la décidabilité et à la calculabilité, qui me semblent être les propriétés trouvables justement sans intuition, sans apport extérieur, par seule force "brute" du raisonnement.
Sinon, en ce qui concerne le hasard, toi-même sais bien qu'on peut simuler le hasard avec un algorithme purement déterministe (http://chezmatthieu.blogspot.com/2007/01/dynamic-days-6-la-rgle-30-hasard-et.html), donc rien de contradictoire !

à dvanw : oui le cerveau humain est un oracle au sens de Turing ! C'est tout le problème de la décidabilité qui a révélé cela : il y a des choses qu'on sait par intuition, et qu'on est obligé d'admettre comme axiome. Apparememnt, la notion d'ordre sur les nombres entiers fait aussi partie de ses notions qu'on possède par pure intuition. Après, je ne suis pas spécialiste, je ne peux pas en dire plus !

Mon point pour les algorithmes génétiques était qu'ils peuvent résoudre a priori uniquement les problèmes accessibles par recombinaison d'autres atomes. Exactement comme une démonstration mathématique en fait, où tu combines des hypothèses pour arriver à ta conclusion. Dans ce cadre, ils ne peuvent résoudre que des problèmes décomposables en petits sous-problèmes; ils ne peuvent optimiser que sur des espaces analogues aux espaces mathématiques des problèmes décidables (il me semble). Or, il y a peut-être des problèmes où il n'y a aucune structure permettant de décomposer en petits sous problèmes (typiquement imagine un paysage d'énergie purement aléatoire) : les algorithmes génétiques n'ont aucune chance de trouver les solutions de ce problème, de la même façon que si tu n'as pas d'indices, d'atomes de raisonnement, tu ne pourras jamais décider si tel ou tel théorème est vrai. Là était mon analogie...

Bon, tout cela est hautement spéculatif, je risque fort de me faire taper sur les doigts par des vrais matheux !

PS : mes références sur Turing viennent du Pour la Science spécial génie de la Science sur Turing, en plus d'autres choses que j'ai lues par ailleurs.

blop a dit…

-- si ce message est poste plusieurs fois, merci de l'effacer, j'ai quelsques difficultes a le faire passer... -

"Mon point pour les algorithmes génétiques était qu'ils peuvent résoudre a priori uniquement les problèmes accessibles par recombinaison d'autres atomes."
C'est vrai que les algo genetiques (GA) sont principalement guides par les croisements (cross-over), les recombinaisons d'individus (j'utilise "individu" plutot qu'"atome", c'est par habitude, mais je n'ai rien contre "atome"). Mais les GA font partie d'un ensemble plus vaste, celui des algorithmes evolutionnaires, parmis lesquels on trouve les strategies d'evolution (ES) et les evolutions differentielles (DE) citees dans mon commentaire precedent. Or tous ces algo (GA inclus) utilisent les croisements mais aussi les mutations pour evoluer.
Ensuite, ces recombinaisons produisent de nouveaux individus qui ne peuvent pas etre "décomposables en petits sous-problèmes", exactement comme un humain ne peut pas etre decomposable en ses parents (meme s'il a le nez de son pere).

Je connais mal la machine de Turing. Mais je suis sur que les GA ne fonctionnent par decomposition du probleme. J'espere ne pas trop te decevoir... :-)

Tom Roud a dit…

Salut,
Je suis d'accord que les algorithmes d'évolution ne se limitent sûrement pas aux GA (et pour cause, je m'en sers régulièrement moi aussi).
Cependant je ne suis pas complètement d'accord avec toi concernant l'importance des mutations . p110 du Holland, tu peux par exemple lire :
"Since enumerative plans are, at best, useful in very limited situations, it would seem that mutation's primary role is not one of generating new structures for trial - a role very efficiently filled by crossing-over."
Plus loin, Holland précise le rôle essentiel des mutations : conserver la diversité allélique

"Here, then, is a role uniquely filled by mutation, because it assures that no allele pemranently disappears from the population".

Donc il me semble que ce sont bien les recombinaisons qui sont les moteurs pour ces algorithmes : par ailleurs, c'est ce qui explique leur puissance car cela assure le parallélisme. Il me semble que les recombinaisons permettent de créer des "schemata" performant à partir de sous "schemata" moins performants mais plus performants que l'aléatoire, c'est en cela que j'avais le sentiment que les GA divisaient les problèmes en sous-problèmes.

Maintenant, pour élargir à la biologie, il me semble très clair que l'évolution fonctionne beaucoup plus par réarrangement d'éléments existants, et qu'il y a assez peu de "création" de nouveaux éléments en fait.

seven a dit…

Suite à échange avec Tom...

Je n'ai certes pas le background nécéssaire pour saisir toute la discussion...

Simplement, plus je lis de papiers en biologie fondamentale, plus j'ai l'impression qu'on court après la compréhension de systèmes dont notre évaluation de la complexité n'est limitée que par nos moyens d'exploration. Du coup, l'idée d'algorithmes susceptibles de prévoir le fonctionnement cérébral, cognitif ou autre me semble parfois utopiste. C'est une vision simpliste, et pessimiste? Non, pas pessimiste, parce que je trouve tout ça passionnant.

blop a dit…

Ave,

C'est vrai pour les GA (je l'ai d'ailleurs écrit : les GA "sont principalement guidés par les croisements"), pas pour les ES par exemple. J'ai pas mes bouquins sous la main, là, mais la plus belle démonstration c'est que tu peux faire tourner un ES avec une population d'1 seul individu (donc pas de cross-over possible). Les premiers ES fonctionnaient d'ailleurs comme cela.
Sur la page GA de wikipedia, tu trouves
"Evolution strategies (ES) evolve linear individuals by means of mutation. ES algorithms are designed particularly to solve problems in the real-value domain."
La diversite est donc créée soit par croisement soit par mutation, avec une préférence pour l'un ou pour l'autre selon les algorithmes.

Bon, au point où j'en suis, et pour expliquer ce que j'entends par diversité et pourquoi ce que dit Holland est parfois vrai mais limité, autant parler de la balance exploitation/exploration. Tout algorithme doit trouver la bonne balance entre les deux, en fonction du problème. Exploitation : on cherche de nouvelles solutions à partir des solutions existantes qui marchent bien (on exploite les connaissances déjà acquises). Exploration : on va voir ailleurs si j'y suis (ce qui permet de sortir des extrema locaux). Si le problème est simple : exploitation au maximum pour aller aussi vite que possible. Si le problème est complexe (bruit, plein d'extrema, régions interdites, etc) plus d'exploration. C'est pour cela qu'il n'y a pas d'algorithme parfait, parce que cette balance ne doit pas etre la même pour les différents problèmes. Mais les algo comme GA, ES, PSO, etc ont cet avantage que tu peux modifier cette balance en changeant la taille de la population, le taux de mutation, le type de croisement, etc. C'est ce qui les rend chiant aussi : ils ont leur propres paramètres qu'il faut ajuster.

Pour en revenir aux citations de Holland. C'est vrai pour les problèmes simples : le croisement sert à l'exploitation et la mutation à l'exploration. Maintenant prenons un problème plus complexe : je te donne une carte du monde, vierge. Deux paramètres : latitude et longitude. Le but, trouver le point culminant. Tu commences par qq points au hasard. Tu en a deux au dessus du niveau de la mer : Paris et NY. Tu fais un croisement (à la maniere de l'ES pour faire plus simple : une moyenne), tu te retrouves au fin fond de l'océan. On a bien augmenté la diversité dans ce cas, exploré une region nouvelle. Preuve que l'exploration peut se faire aussi par croisement. De même, si tu es dans l'himalaya, au pied de l'everest et que tu fais de petites mutations, tu vas exploiter une bonne solution pour en trouver une meilleure et gravir la pente.

Donc mutation et croisement participent à l'exploitation et l'exploration.

Pour finir (pour aujourd'hui :-), encore une fois, en reprenant l'exemple de la carte vierge, quel que soit l'algorithme évolutionnaire que tu utilises, je n'en voies pas un qui fonctionne par décomposition du problème en sous-problèmes.

Tom Roud a dit…

A seven : commme je te le disais, attention aux théoriciens fous !!! C'est sûr qu'on ne connaît pas encore tout. Ce qui est bien avec les blogs est qu'on peut ainsi échanger avec des gens d'horizons différents sur ce genre de sujet.

A Blop : merci pour la distinction entre exploration et exploitation. Ce qui est bien avec les GA est qu'on peut effectivement ajuster ces paramètres aux problèmes. J'imagine donc qu'il y a des gens qui doivent étudier des algorithmes adaptatifs, modifiant eux-mêmes cette dose d'exploration/exploitation. Une des questions que je me pose alors est de savoir si le NFLT s'applique toujours : peut-être bien en fait car modifier le préconçu sur l'espace lui-même peut très bien dépendre de la région de l'espace qu'on est en train d'explorer et donc être spécifique à la variabilité de l'espace considéré.

blop a dit…

desole sur ce coup la, je ne connais pas assez le NFLT pour pouvoir repondre a ta question...