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.