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é…

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 ?

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 :

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

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 !

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 :

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.

A mon arrivée à New York il y a un an, je me disais qu’il me serait impossible de vivre sans Internet, que je ne pourrais jamais me passer de ce lien génial et indispensable avec la France. Les responsables de mon immeuble m’avaient alors garanti que d’ici à quelques semaines, tous les appartements seraient connectés à internet via l’université…

Un an après, la situation est totalement bloquée. En allant renouveler mon bail, sans surprise, j’ai appris que l’université avait renoncé et que je n’aurais jamais internet chez moi. Seulement le gros problème est que c’était l’un de mes seuls espoirs : aux Etats-Unis, à New York, à deux pas de Central Park et des Nations Unies, il n’est toujours pas possible d’avoir l’ADSL, comme le prouve la capture d’écran ci-contre. Et dans le temple mondial du capitalisme, impossible de faire jouer la concurrence à première vue : verizon est ici en position de monopôle local pour le téléphone.

Vous avez dit concurrence ? Ah oui, quand je suis arrivé, on m’a remis une feuille avec le nom des deux entreprises à contacter pour avoir respectivement le téléphone et le câble (oui, ici, les monopôles sont privés bien sûr). Verizon, donc, est hors course pour internet, après un an, j’en ai assez, je vais prendre internet sur le câble. Je me connecte donc chez Time Warner et consulte les informations sur leur plan Road Runner à 45$ par mois.

Tout commence bien : le câble est disponible dans mon immeuble, a priori c’est champagne. Sauf que en voulant faire la commande par internet une mauvaise surprise survient. Comme le prouve l’image ci-contre, avant de pouvoir commander son modem, il faut absolument cocher la case

“My computer meets the minimum system requirements.”

“Requirements” en question qui sont :

Operating System Windows 98, 2000/ME/XP; Pentium-class 400 MHz processor; 64 MB RAM; 110MB of free hard drive space

MAC: System 9.x and higher; PowerPC; 32MB physical RAM w/Virtual Memory set to 40 MB; 30 MB free hard disk space

Et oui, je l’ai encore dans l’os étant sous debian linux. Autrement dit, je suis obligé d’avoir Windows ou un Mac pour pouvoir me connecter sur Internet à New York. Aux Etats-Unis, le pays le plus libéral du monde, j’ai donc eu successivement affaire à deux monopôles : celui du téléphone est incapable d’avoir des lignes en état pour fournir l’ADSL, celui du câble vous oblige par contrat à avoir certains systèmes d’exploitation pour pouvoir surfer sur le web.

Le pire est que contrairement à la France où j’avais pu sans problèmes télécharger tous les drivers de mon modem adsl sous linux, je ne trouve pas la moindre information sur le web ici pour configurer tout comme il faut.

Comme j’en ai ras-le-bol de ne pas avoir internet à la maison, je suis donc obligé de me lancer comme périodiquement dans de charmantes et agréables geekeries. Objectif : réinstaller windows sur une partition abritant une vieille Mandrake qui me servait en cas de défaillance de ma debian (chat échaudé craint l’eau froide). Comme je commence à avoir l’habitude de de genre d’exercice, la première étape consiste à ramasser le maximum d’informations pour savoir comment je vais réussir à réinstaller GRUB sur mon disque une fois que l’ogre Windows aura fait place nette sur mon MBR. J’ai maintenant Knoppix, une live CD de debian et un CD d’installation de Debian pour avoir le mode Rescue. Je vais bientôt tester le mode rescue pour voir comment se passe la réinstallation du GRUB. Après cela, installation de Windows XP (Arghhhhh!!!). A priori, si tout va bien ensuite restauration du GRUB et nouveau dual-boot, et à moi l’internet. Prions mes amis prions…

Edit 22:22 : c’est la berezina ! il faut que je reinstalle tout ! scrogneugneu….

Edit 7 Nov, 18:32 : bon, ça a l’air de remarcher à peu près correctement, modulo les problèmes classiques à chaque réinstallation (carte son à reconfigurer, souris USB non configurée) plus quelques nouveautés (skype et xfig buggés…). Heureusement, maintenant, j’ai mon dual boot !

Via Nature, une controverse linguistique résolue concernant le premier homme sur la Lune. En tant que francophone, nous avons tous en tête la fameuse phrase :
“C’est un petit pas pour l’homme, mais un grand pas pour l’humanité”.
En fait, nous français avons légérement interprêté l’histoire, car les anglophones ont semblent-ils entendu lors de la retransmission en direct la phrase suivante :
“That’s one small step for man, one giant leap for mankind.”
, qui signifie en fait “C’est un petit pas pour l’Homme, mais un grand pas pour l’humanité”, ce qui devient ridicule car “l’Homme” avec un grand H est synonyme de l’humanité dans ce contexte.

Néanmoins Armstrong avait préparé son coup et prévu de dire :
“That’s one small step for a man, one giant leap for mankind.”
qui a exactement le sens que nous avons retenu, nous français. De fait, Armstrong a toujours affirmé avoir bien prononcé l’article indéfini “a” qui change tout. Apparemment, des informaticiens se sont penchés sur le problème et ont démontré par l’analyse des bandes de l’époque qu’il avait effectivement prononcé la phrase prévue, grammaticalement correcte, mais que le bruit a sans doute occulté le “a” décisif. L’honneur est sauf !

Je fais la plupart de mes simulations en C++.
Je trace des courbes sous gnuplot une centaine de fois par jour.
J’ai récemment découvert Matlab, et en suis totalemen fan (c’est très pratique pour faire du traitement d’image, des simulations numériques vite-fait bien-fait et des zolis films à glisser dans les présentations power-point… euh latex-beamer je veux dire).
Je fais mes figures roudoudesques sous xfig.
Je maîtrise même quelques secrets de mplayer et mencoder.
J’écris un peu moins régulièrement des scripts shells, mais je maîtrise à peu près.
Mais voilà…
Je crois que j’ai un problème avec Perl. A peu près tous les trois quatre mois, au détour d’un projet, je me retrouve à devoir traiter de façon systématique des tables données. Perl est alors tout indiqué. Le problème, c’est qu’en deux-trois mois, j’ai eu le temps d’oublier toute la syntaxe (assez obscure il faut bien le dire), tout pollué que je suis par les autres langages. Encore une fois, cet après-midi, il va falloir que j’exhume mon “Introduction to Perl” (honteusement piqué à ma môman, désolé maman…) aux fameuses éditions “O’Reilly” pour ré-apprendre la syntaxe de Perl… Mes vieux programmes aidant, peut-être un jour maîtriserai-je totalement cet outil !