Archives pour la catégorie ‘Informatique’

Scientifiques, à l’assaut !

Saturday, June 21st, 2008

Il y a quelques jours a eu lieu la première conférence scientifique virtuelle, dans le monde de World of Warcraft (WoW pour les intimes). (Via gonzoscientist).

(more…)

Popularity: 46% [?]

Misc. du week-end

Thursday, February 28th, 2008

Quelques liens/commentaires :
(more…)

Popularity: 64% [?]

Bienvenue dans le Cyber Space

Sunday, October 21st, 2007

Imaginez que vous preniez toutes les photos d’un même endroit disponibles sur le Web (genre sur flicker), que vous trouviez un moyen de les recombiner ensemble pour recréer sur votre ordinateur une copie 3D du monde réel. C’est ce que semble faire Photosynth
(malheureusement préempté par Microsoft qui a racheté Seadragon software, la start-up responsable du développement).

(more…)

Popularity: 18% [?]

Wolfram, NKS et sonneries de portables

Saturday, October 6th, 2007

Stephen Wolfram est un drôle de personnage. Créateur de Mathematica, il est l’un des rares scientifiques ayant fait fortune grâce à ses idées. Mais la fortune ne l’intéresse pas : on sent bien que son nouveau rêve est de laisser son empreinte sur la science.

(more…)

Popularity: 18% [?]

Un magnifique algorithme graphique

Saturday, September 1st, 2007

Shamir

Si vous visitez ce site avec Internet Explorer, vous avez pu constater qu’il est parfois difficile de gérer des images. Apparemment, une solution extrêmement efficace vient d’être trouvée pour redimensionner les images de façon non-uniforme.

(more…)

Popularity: 18% [?]

Vote électronique et fraude

Wednesday, March 21st, 2007
On m’a signalé ce site, luttant contre le vote électronique :
http://recul-democratique.org/

Il y a des films de démonstration de fraudes; c’est assez effrayant. De la même façon, on peut assez facilement savoir pour qui vous votez en temps réel en captant les ondes radio émises par la machine.

Je ne peux que souscrire à ce genre d’arguments :

Dans une élection traditionnelle, pour limiter le risque de fraude, il suffit de surveiller les urnes le jour de l’élection (et quelques jours après s’il y a des litiges). Mais les ordinateurs de vote, c’est en permanence, à longueur d’année et vingt-quatre heures sur vingt-quatre, qu’il faut les surveiller, comme l’explique l’informaticien Pierre Muller [On a beau mettre sous clé l’ordinateur de vote dans les jours qui précèdent les élections, la machine peut être piratée à tout moment, par exemple six mois ou un an avant le scrutin. » Une telle surveillance étant quasi impossible, il suffit d’avoir la clé du local des ordinateurs et la complicité d’un informaticien, et hop, je t’embrouille. Ni traces, ni soupçon, ni contestation possible. De plus, poursuit Pierre Muller, « les composants informatiques sont standards et programmés à l’identique sur toutes les machines. Il suffit d’en modifier un, de le dupliquer, d’en préparer un lot à l’avance qu’il suffirait d’installer dans les ordinateurs de vote et toutes les conditions sont réunies pour une fraude massive ».

Deux trucs que je ne comprends pas bien :
- on est nécessairement obligé de reprogrammer la machine à chaque élection (vu qu’on ne vote pas pour les mêmes à chaque fois), qui s’occupe de cette programmation ? Comment être sûr qu’il n’y a pas de fraudes au moment de la reprogrammation ? L’avantage de l’urne transparente et des assesseurs des différents partis politiques, c’est que là au moins, il y a plusieurs témoins, ayant des intérêts divergents qui doivent s’équilibres,
- même sans intention de fraudes, on peut laisser des bugs dans des programmes. Après chaque programmation, j’espère que quelqu’un vérifie les programmes. Et vérifie au sens mathématique : il faut être absolument sûr que la machine donne réellement le résultat, quel que soit la séquence des votes. Je pense qu’il y a des méthodes standards (encore que ces méthodes sont nécessairement approchées, puisque la prédiction de l’issue d’un programme est il me semble indécidable, cf
ce billet). Peut-être un informaticien peut-il m’éclairer, mais comment fait-on pour vérifier de tels programmes ? Le fait de savoir a priori si la machine donne le bon résultat quelle que soit la séquence des votes est-il mathématiquement décidable ?

Le “bêtisier” des partisans du vote électronique est lui aussi assez gratiné…

Popularity: 11% [?]

Platon, l’apprentissage et l’évolution

Thursday, February 22nd, 2007
Extrait d’un ouvrage résumant l’héritage de Kolmogorov en physique :

Nous sommes capables d’apprendre par l’exemple et de classifier une multitude d’objets extérieurs en des catégories distinctes. (…) En deux mots, la difficulté qui se présente est la suivante : si une règle ne peut être logiquement déduite des exemples, comment se fait-il que nous puissions la trouver ? La solution mise en avant par Platon était que la règle est déjà contenue par le cerveau humain et que les exemples n’ont d’autre effet que de sélectionner la bonne règle parmi toutes celles qui sont admissibles.
Le point de vue opposé (Aristote) soutient que cette question est mal posée et que le cerveau humain est vide (tabula rasa) avant toute expérience sensible du monde extérieur.

Pour être plus concret, considérons la suite suivante : 01010101010101010. Si je vous demande quel est le prochain chiffre de la suite, tout être humain normalement constitué devrait en toute logique répondre 1. Le problème, c’est que cela n’a en fait rien de logique : il y a une infinité de suites différentes commençant par cette séquence, et la connaissance du début de cette séquence ne nous dit absolument rien sur ce qui suivra. Simplement, nous imaginons une règle : un 0 est suivi d’un 1, un 1 d’un zero. Nous testons ensuite cette règle sur l’exemple donné : elle marche à tous les coups. Donc cette règle nous paraît valable, et nous décidons (un peu) arbitrairement de la tenir pour acquise.

Cette méthode de pensée a l’air assez mécanique, voire un peu stupide quand on y réfléchit. Cependant, c’est un problème redoutable que de faire réaliser cet exercice simple à un ordinateur. A dire vrai, la seule méthode qui me paraît réellement efficace dans l’absolu est d’utiliser l’idée de Platon : générons des règles aléatoirement, puis testons-les sur nos exemples, et on devrait pouvoir arriver à trouver une (la?) véritable règle sous-tendant l’exemple. L’idée de “tabula rasa”, si elle paraît au début plus élégante et moins arbitraire, apparaît dans la pratique bien peu réaliste : il paraît trop difficile d’un point de vue purement computationnel de créer quelque chose à partir de rien …

Il est assez étonnant pour moi de constater les ponts entre ce débat Platon/Aristote, qui est en fait un débat inné/acquis, l’informatique et bien sûr la biologie. Luria et Delbruck ont en fait posé exactement la même question dans leur fameuse expérience : les bactéries sont-elles des “tabulae rasae”, apprenant à resister à un stimulus, ou au contraire seules les bactéries ayant déjà la potentialité de resistance sont-elles effectivement sélectionnées ? Cette reformulation de l’idée de Platon est incroyablement proche du principe même de la sélection darwinienne : une règle admissible serait une mutation aléatoire, toutes deux étant sélectionnées par confrontation au réel. La théorie aristotélicienne serait au contraire une version lamarckienne de l’apprentissage. D’où une question qui se pose naturellement : le processus d’évolution ne serait-il pas d’avantage un processus d’apprentissage qu’un processus d’optimisation ?

La conséquence obervable de cette vision de l’évolution est l’existence d’étrangetés assez frappantes pour ceux qui considèrent la nature comme modèle de perfection : par exemple, ils est bien connu que l’oeil des mammifères est conçu en dépit du bon sens. Simplement, l’évolution de l’oeil a été longue et laborieuse, et des chemins de traverses ont été empruntés aboutissant à un instrument efficace sans être optimal. Qui n’a jamais utilisé des moyens détournés pour apprendre et retenir quelque chose ? En quelque sorte, la phrase mnémotechnique est à l’apprentissage ce que les organes vestigiels sont à l’évolution…

Maintenant, j’imagine qu’on peut généraliser cette idée à des processus plus actifs, comme par exemple la pensée même. Après tout, peut-on vraiment prétendre que nous sommes capables de concevoir une pensée originale par nous mêmes ? L’exercice de la pensée elle-même n’est-il pas plutôt un processus de mutation aléatoire/recombinaison/sélection ? Et si notre cerveau n’était qu’un bon gros générateur aléatoire couplé à un filtre éliminant les pensées les plus stupides ;) ?

Popularity: 13% [?]

Pensée et algorithmes génétiques

Tuesday, January 16th, 2007
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.

Popularity: 12% [?]

Jouer à Dieu

Friday, January 12th, 2007

Je profite de mes actuelles insomnies new yorkaises pour lire et bloguer. Au détour d’un livre très intéressant de Gerhart et Kirschner, Cells, Embryos ans Evolution, j’ai découvert que Richard Dawkins ne se contentait pas d’écrire pour le grand public, mais menait aussi de vrais travaux de recherche. Ainsi a-t-il mis au point il y a un peu plus de 20 ans (une éternité dans le domaine de la biologie !) un programme sympathique permettant de générer des “biomorphs”. L’idée est d’encoder un genome artificiel contrôlant le développement d’une créature virtuelle. Un jeu de mutations/sélection (où vous faites vous-mêmes la sélection) permet de créer des formes très variées, rappelant certaines formes naturelles. Je vous présente ci-dessus ma création d’insectes/sauterelles !
Au delà de l’intérêt esthétique, cet algorithme montre comment un génome a priori simple permet de générer (de façon émergente ou auto-organisée diraient certains) des formes complexes, et comment la sélection naturelle permet de changer rapidement ces formes - certaines transitions sont en effet assez spectaculaires.
A vous de jouer ici !

Popularity: 10% [?]

Le “No Free Lunch Theorem”

Tuesday, January 9th, 2007
Il existe beaucoup de théorèmes d’impossibilités dans les sciences dures. L’exemple le plus connu est le fameux “théorème d’incomplétude de Gödel“, affirmant en gros que certains énoncés ne peuvent être démontrés ou réfutés (voir aussi sur ce blog ce billet). Un des théorèmes assez récents dans le domaine de l’optimisation numérique ferait le malheur de Mike Slackenerny : il s’agit du “No Free Lunch Theorem”. Ce théorème concerne les algorithmes d’optimisation numérique.
On passe notre vie à essayer optimiser quelque chose, à arbitrer entre plusieurs contraintes pour choisir ce qui nous semble le plus adapté. Par exemple, toute la microéconomie est basée sur l’idée d’optimisation sous contrainte, et le but du marché libre est de trouver un optimum collectif. Dans un registre plus légers, certains essaient de minimiser le nombre de mouvements à faire pour aller aux toilettes
Mathématiquement, on définit alors une fonction de coût associée à un problème donné. La fonction de coût peut être très simple à définir : imaginons par exemple que vous soyez un représentant devant visiter plusieurs villes, et souhaitant minimiser votre fatigue, votre fonction de coût sera alors la distance totale parcourue. Il serait très utile, étant donnée une liste de villes, de connaître alors un moyen simple de minimiser cette distance totale. C’est un problème très classique en optimisation numérique : le problème du voyageur de commerce.
La plupart des scientifiques sont de gros paresseux, et aimeraient bien disposer de recettes toutes faites pour aborder ce genre de problème d’optimisation. Il serait formidable d’avoir une méthode générale, applicable à tous les problèmes sans exception, permettant d’optimiser à coup sûr une fonction de coût, quelle que soit sa forme, quel que soit le problème. Tout serait tellement plus simple… Et bien c’est peine perdue : le “No Free Lunch Theorem” affirme qu’une telle méthode n’existe pas. Le monde est trop complexe, et il n’existe pas de recette générale permettant d’optimiser n’importe quel problème. On peut formuler ce théorème de deux autres façons différentes :
  • sur le gigantesque ensemble de tous les problèmes d’optimisation numérique, aucun algorithme n’est meilleur que les autres, i.e. le coût moyen (sur l’ensemble des problèmes) trouvé par un algorithme ne dépend pas de l’algorithme (et n’est donc pas le coût minimum a priori)
  • Le seul moyen de trouver un algorithme plus efficace qu’un autre est d’adapter l’algorithme au problème, i.e. de connaître certaines structures mathématiques sous-jacente du problème d’optimisation permettant d’améliorer la performance de celui-ci.
La conclusion de tout ça, c’est que les numériciens et les spécialistes d’optimisation numérique ne seront jamais au chômage : chaque problème nécessite une étude approfondie et un algorithme spécifique pour être résolu. Ce genre de résultats affirme donc également que certains algorithmes très utilisés (par exemple les algorithmes génétiques, ou le recuit simulé) ne peuvent pas marcher de façon générale : ils ne seront efficaces que sur des problèmes avec des structures mathématiques bien précises. Je trouve également cette idée intéressante du point de vue de l’évolution : “l’algorithme” d’évolution darwinienne n’est efficace que s’il est adapté au problème (”sélection du plus adapté”). Si on connaît l’algorithme, cela signifie qu’on peut avoir des informations théoriques sur la structure du problème, et sur la fameuse “fitness function” chère aux biologistes…

Références :

Le papier original (merci Timothée) : Wolpert, D.H., Macready, W.G. (1997), No Free Lunch Theorems for Optimization, IEEE Transactions on Evolutionary Computation 1, 67.
Une démonstration assez simple du NFLT est proposée dans Ho, Y.C., Pepyne, D.L. (2002), Simple Explanation of the No-Free-Lunch Theorem and Its Implications, Journal of Optimization Theory and Applications 115, 549.

Popularity: 11% [?]