Archives de catégorie : Divers

Anne, Barnabé et Bayes participent à un jeu télévisé

Ai-je compris tous les messages de la vidéo Marilyn versus Monty Hall | Bayes 4 diffusée sur l’excellente chaîne Science4All, animée par le mathématicien Lê Nguyên Hoang ? Cette vidéo aborde un problème éponyme de probabilités conditionnelles dans lequel un participant d’un jeu télévisé doit choisir un rideau parmi trois, sachant que derrière un des rideaux se cache une voiture et derrière chacun des deux autres une chèvre. Après son premier choix, le candidat reçoit une nouvelle information qui est la localisation d’un rideau, parmi les deux qu’il n’a pas choisi, derrière lequel se trouve une chèvre. La question posée est : sur la base de cette nouvelle information, le candidat a-il intérêt à modifier son choix initial ?

La première partie de la vidéo est très intéressante et je vous invite à la regarder car elle montre que même des mathématiciens expérimentés peuvent faire des erreurs de raisonnement. Dans la deuxième partie, qui commence à 10:45, Lê explique comment utiliser la formule de Bayes pour résoudre le problème des trois rideaux. Je vais reprendre son explication avec un regard critique en tentant d’apporter quelques éléments qui, je pense, m’auraient permis comprendre plus vite la démarche proposée s’ils avaient été donnés dans la vidéo.

Tout d’abord, je vais rappeler la version la plus simple de la formule de Bayes, et je donnerai ensuite la version utilisée par Lê. La première version fait intervenir deux variables H et D qui représentent des ensembles d’observations possibles auxquelles sont associées des probabilités. L’ensemble D représente des observations pouvant être faites lors d’une expérience, et l’ensemble H les observations qui sont cohérentes avec une certaine hypothèse. On se permettra d’utiliser la même notation H pour désigner l’hypothèse et les évènements observables en cohérence avec cette hypothèse. Voici une figure illustrant cette première variante de la formule de Bayes.

La figure ne couvre pas tous les cas possibles. Il se pourrait par exemple que D soit inclus dans H, ou que H soit inclus dans D, mais la formule, elle, s’applique dans tous les cas. Elle exprime la probabilité qu’une observation soit cohérente avec l’hypothèse H sachant que cette observation est dans D, et fait intervenir les probabilités suivantes :

  • La probabilité P[D|H] qu’une donnée observée soit dans D sachant que cette donnée est cohérente avec H.
  • La probabilité P[H] qu’une observation soit cohérente avec H.
  • La probabilité P[D] qu’une observation soit dans D.

Dans la vidéo, Lê parle de théorie plutôt que d’hypothèse, et utilise la lettre T pour désigner cette théorie. Mais dans les deux cas, je pense qu’on parle bien d’un ensemble d’observations possibles ayant chacune une certaine probabilité. D’autre part, il utilise une version de la formule de Bayes dans laquelle la probabilité P[D] est décomposée sous la forme d’une somme dans laquelle apparaissent les probabilités conditionnelles d’observer une donnée de type D selon différentes théories. On considère alors implicitement un ensemble d’hypothèses (théories) qui contient une hypothèse H à laquelle on s’intéresse particulièrement, mais aussi les autres hypothèses alternatives. Voici la manière dont Lê écrit la formule. La lettre T désigne l’hypothèse à laquelle on s’intéresse, et la lettre A désigne les hypothèses alternatives.

Voici une reformulation de la décomposition qui apparait au dénominateur. J’ai utilisé les lettres A et H pour désigner respectivement l’hypothèse de référence et les hypothèses alternatives, et un H majuscule cursif pour désigner l’ensemble de toutes les hypothèses (i.e. l’hypothèse de référence et les hypothèses alternatives).

Mais attention ! Il y a quelque chose que Lê ne précise pas et qui me parait important : La décomposition de P[D] n’est correcte que si les hypothèses considérées sont mutuellement exclusives et couvrent toutes les observations possibles. En d’autres termes, chaque observation possible doit être cohérente avec une hypothèse et une seule. Il est facile de voir sur la figure ci dessus que si par exemple H2 et H3 se recouvrent, ça ne fonctionne plus.

Rentrons maintenant dans le vif du sujet. Lê introduit trois hypothèses (théories) correspondant aux trois emplacements possibles de la voiture. Il attribue la probabilité 1/3 à chacune de ces hypothèses, ce qui me parait raisonnable puisqu’on a aucune information et qu’on peut même supposer que cet emplacement a été choisi aléatoirement. Il appelle préjugé ces trois probabilités. Sans perte de généralité, il suppose que le candidat a choisi le rideau du milieu, puis se place dans le cas où le présentateur a révélé qu’une chèvre se trouvait derrière le rideau de droite. Au regard de cette information, Lê calcule les probabilités de la donnée observée D = [il y a une chèvre à droite] pour chacune des des trois théories, à savoir T1 : la voiture est à gauche, T2 : la voiture est au milieu, et T3 : la voiture est à droite. Sauf qu’il ne numérote pas explicitement les théories et utilise à chaque fois la lettre T. Je pense que le raisonnement aurait été plus facile à suivre avec une numérotation des trois hypothèses.

Quoi qu’il en soit, on a P[D|T3] = 0 parce que sous l’hypothèse T3 où la voiture est à droite, la probabilité d’observer une chèvre à droite est nulle. Ce terme P[D|T3] est appelé terme d’expérience de pensée de la théorie T3. Ensuite, on a P[D|T1] = 1 car sous l’hypothèse T1 où la voiture est à gauche, le présentateur ouvre forcément le rideau de droite (puisqu’il ne veut pas montrer la voiture ni lever le rideau initialement désigné par le candidat). Enfin P[D|T2] = 1/2 car sous l’hypothèse T2 où la voiture est au milieu, le présentateur peut choisir de révéler soit la chèvre de droite, soit la chèvre de gauche. Lê traduit cela par la phrase “Dans la théorie T2, on prédit la donnée observée avec probabilité 1/2”.

Ensuite, Lê calcule le score de chaque théorie, c’est à dire les termes P[D|T1] P[T1] = 1/3, P[D|T2] P[T2] = 1/6 et P[D|T3] P[T3] = 0. On perçoit ici qu’au regard de l’information D dont on dispose, la théorie T1 (la voiture est à gauche) est deux fois plus probable que la théorie T2 (la voiture est au milieu). On applique alors la formule de Bayes pour chacune des trois théories. Lê fait un raccourci en s’appuyant implicitement sur le fait que les trois théories sont équiprobables. Sans ce raccourci, le dénominateur vaut 1x(1/3) + (1/2)x(1/3) + 0x(1/3) = 1/2. Les probabilités des trois théories sachant la donnée connue sont respectivement P[T1|D] = 2/3, P[T2|D] = 1/3 et P[T3|D] = 0. Donc le candidat a deux fois plus de chance de gagner la voiture s’il change d’avis et choisi le rideau de gauche.

La question importante que Lê n’aborde pas, peut être parce qu’il trouve la réponse évidente, c’est l’utilité de la décomposition de la probabilité P[D]. Aurait-on pu calculer facilement cette probabilité et utiliser directement la première variante de la formule de Bayes ? J’ai l’impression que la réponses est non. Il est difficile d’appréhender cette probabilité que l’animateur révèle une chèvre derrière le rideau de droite sans prendre en compte les différentes théories T1, T2 et T3 et cela méritait d’être dit. Une autre petite critique est qu’il est difficile de bien se représenter ce que sont les observations élémentaires pouvant appartenir aux ensembles T1, T2, T3 et D, et un effort explicatif aurait pu être fait à ce niveau. Si j’ai bien compris, une observation combine deux informations : la position de la voiture et le rideau levé par l’animateur. Voici une illustration graphique qui montre ce que je considère être les 4 observations possibles (de probabilités non nulles) si le candidat choisit initialement le rideau du milieu. Chacune de ces observations inclut tout l’historique, depuis la position de la voiture et des chèvres jusqu’au rideau levé par l’animateur. On voit notamment que P[D] vaut 1/3 + 1/6 = 1/2.

Pour conclure, ma principale critique de la vidéo objet de ce billet, c’est qu’il manque une explication de la nature des objets mathématiques représentés par les lettres T (théorie) et D (donnée connue ou observée). A tel point que j’espère ne pas m’être fourvoyé en considérant que T (ou les Ti) et D sont des ensembles d’évènements élémentaires, chacun pouvant être observés avec une certaine probabilité. Mais si je me suis trompé, j’espère que l’auteur passera par là et pourra apporter des précisions qui me permettront de modifier ce billet.

Concernant le choix de ce problème particulier pour illustrer la puissance de la formule de Bayes, je dirais que le caractère contrintuitif de la solution et le fait que le problème soit célèbre sont des facteurs positifs. Mais par contre, le fait que les “possibles” soit des objets assez complexes, incluant la position de la voiture et le rideau levé par l’animateur, fait qu’il me serait assez difficile de faire le raisonnement “Bayésien” sans être guidé par un spécialiste. En outre, il y a un raisonnement très simple et pas spécialement Bayésien qui permet de conclure de manière convaincante, en imaginant qu’il y a deux candidats, Anne et Barnabé.

Anne joue en premier et choisi le rideau central. Elle ne change pas d’avis. Puis le présentateur dévoile une chèvre, et ensuite Barnabé choisi le rideau restant qui n’a pas été choisi par Anne. Clairement, l’un des deux candidats gagne la voiture. Comme la voiture a une probabilité 1/3 d’être remportée par Anne, alors elle a une probabilité 2/3 d’être gagnée par Barnabé.

Lê anticipe cette critique en disant que le but de la vidéo n’est pas spécifiquement de monter la manière la plus simple de résoudre le problème donné en exemple, mais de montrer comment le résoudre de manière “Bayésienne”. Mais il reste qu’il y a un gouffre entre la simplicité de la résolution de ce problème avec Anne et Barnabé et la relative complexité de sa résolution avec Bayes.

Ordinateurs sans microprocesseurs

microproAvant l’apparition des microprocesseurs, les ordinateurs étaient réalisés uniquement à partir de deux sortes de “briques de construction”, les portes logiques et les bistables (eux-mêmes constitués de portes logiques). Les premiers microprocesseurs, apparus dans les années 1970, comportaient des milliers de portes logiques et de bistables rassemblés sur une même puce qui valait tout de même près de 200 dollars de l’époque, ce qui représente (compte tenu de l’inflation) de l’ordre de 1000 dollars actuels.

Depuis cette époque, tous les ordinateurs commercialisés comportent des microprocesseurs. Mais il existe quelques passionnés qui construisent eux-mêmes des ordinateurs “à l’ancienne”, sans microprocesseur. Pourquoi se lancent-ils dans un tel projet ? Par défit intellectuel, par passion, pour comprendre et faire comprendre le fonctionnement d’un ordinateur en s’appuyant sur un système à dimension humaine, pour revisiter un pan entier de l’histoire de l’informatique… Fabriquer un ordinateur de toute pièce est une démarche d’ingénierie dans laquelle il faut faire preuve d’une grande exigence intellectuelle pour décomposer de manière simple et efficace un système complexe en parties plus simples dont les rôles sont clairement spécifiés. Et une fois que la partie physique est terminée, il reste à l’exploiter en réalisant des programmes, qui ne sont rien d’autre que des systèmes complexes constitués de “briques logicielles” plus simples. Quiconque parvient à ce stade a les idées parfaitement claires sur tous les concepts sous-jacents.

Si tous les ordinateurs “faits mains” dont j’ai trouvé des descriptions sur le WEB m’ont impressionnés, j’ai été vraiment bluffé par certaines réalisations particulièrement élégantes, telle que “The Anitra Computer”, un ordinateur 8 bits pouvant adresser 32K octets de mémoire réalisé par un thésard du MIT à titre de loisir ! Cet ordinateur a été conçu de manière à simplifier au maximum son circuit électronique et à minimiser le nombre de composants utilisés. Le langage machine de cet ordinateur ne comporte que deux instructions placées dans 16 blocs de 8 instructions consécutives. L’une permet de transférer une valeur d’une adresse A vers une adresse B, et l’autre additionne une valeur située à une adresse A et une autre située à une adresse B, place le résultat à l’adresse B, et réalise un saut en avant jusqu’au début du bloc suivant s’il y a un débordement arithmétique (retenue). L’ensemble du programme est constitué d’une séquence de 16 blocs d’instructions qui est répétée indéfiniment. A première vue, la taille du programme est très limitée, mais elle est suffisante pour réaliser un interpréteur capable d’exécuter un programme plus long – et écrit dans un langage de plus haut niveau – situé dans le reste de la mémoire.

Dans le même esprit, Jack Eisenmann a conçu et réalisé un ordinateur 8 bits adressant 64K de mémoire appelé “DUO COMPACT” dont le langage machine ne comporte qu’une seule instruction : NOR A B C D, où A, B, C et D sont des adresses mémoire, qui effectue une opération logique OU / NON entre les valeurs pointées par A et B, place le résultat dans B, puis branche en C si le résultat est 0 ou en D sinon. Cette seule instruction permet de simuler toutes les instructions d’un microprocesseur classique. L’auteur a réalisé un programme calculant une racine carrée et même un petit jeu vidéo de plateforme s’exécutant en mode texte sur un écran à cristaux liquides acheté dans le commerce.

Dans une autre optique, un ingénieur électronicien nommé Dennis Kuschel a réalisé un ordinateur 8 bits complètement câblé avec des circuits logiques TTL (technologie datant des années 1960) nommé “MyCPU”. Il supporte le jeu d’instructions du microprocesseur 6502 qui équipait l’Apple II. Dennis a également réalisé un contrôleur vidéo permettant à cet ordinateur de réaliser des affichages graphiques sur écran, une carte lui permettant d’utiliser une mémoire de masse, et une carte réseau lui permettant de se connecter à Internet. C’est un travail absolument énorme qui relève de l’exploit.

Pour découvrir d’autres exemple de réalisations extraordinaires, vous pouvez consulter le site Home build computers web ring.

Scrivener, un traitement de texte non linéaire.

machchine-a-ecrirePour rédiger un document scientifique de quelques pages, l’idéal est de disposer d’un traitement de texte permettant un formatage immédiat dans un style agréable à lire, ainsi que la création, l’insertion et la modification intuitive, rapide et confortable de figures, dessins, équations, et courbes ayant un aspect professionnel, sobre et esthétique.

J’avoue n’avoir jamais trouvé un logiciel, ni même une combinaison de plusieurs logiciels, qui réponde à ces critères au niveau d’exigence correspondant à mes attentes, mais c’est un sujet que je ne développerai pas dans ce billet. Aujourd’hui, je vous présente un traitement de texte dédié à la conception et la réalisation de documents comportant des dizaines, voire des centaines de pages recelant des milliers d’informations, de concepts, d’idées, de descriptions, etc.

De tels documents sont constitués de très nombreuses briques documentaires, entendez par là de petits morceaux de textes à différents stades de maturité, allant d’une simple idée ou observation jusqu’à une partie finalisée du document en cours de réalisation. La force de Scrivener est de permettre d’organiser ces briques documentaires dans une structure arborescente, c’est à dire constituée de dossiers pouvant contenir des briques documentaires et des dossiers pouvant eux-même avoir une structure arborescente.

Chaque élément (brique documentaire ou dossier) peut être facilement déplacé à l’aide de la souris. On peut lui associer des notes, commentaires, étiquettes, un résumé, une couleur. Il est possible de sélectionner un ou plusieurs dossiers et/ou briques documentaires dont les contenus s’affichent les uns à la suite des autres sous la forme d’un document continu pouvant être lu et modifié. Cette « vue » particulière d’une partie du contenu en cours de rédaction est préservée lorsque le l’utilisateur quitte l’application.

Cette fonctionnalité, qui change complètement la manière de travailler, n’existe pas (jusqu’à plus ample informé) dans les traitements de textes classiques tels que Word et OpenOffice. Ce qui s’en rapproche le plus dans Word est la possibilité de « replier » des chapitres et sections pour ne rendre visibles que certaines parties du document. Mais la « vue » ainsi créée est malheureusement perdue lorsqu’on quitte l’application. Par ailleurs, Word permet de visualiser l’arborescence des sections d’un document, mais la réorganisation de ces sections ne peut se faire qu’avec des « copier / coller » laborieux.

Scrivener permet de produire le document final sous différents formats, tels que pdf, word, et les deux principaux formats de livres électroniques, Epub et Kindle. C’est lors de cette étape dite de “compilation” qu’est réalisée la mise en forme définitive d’après un modèle définit par l’utilisateur.

En revanche, il faut bien admettre que les possibilités offertes par Scrivener pour l’édition de chaque brique documentaire sont très limitées au regard de celles de Word ou même d’OpenOffice. Scrivener est encore loin de répondre complètement à mes besoins en matière de rédaction de documents scientifiques, mais c’est ce que j’ai trouvé de mieux pour la prise de notes, le suivi, et la rédaction progressive de rapports dans le cadre de projets de recherche. Il est à mon avis tout aussi adapté à la réalisation de supports de cours et autres documents pédagogiques, ainsi que de mémoires et rapports d’étudiants.

Une machine de Turing

mt-all-1000J’ai enfin terminé cette réalisation qui m’a occupé pendant de nombreuses soirées cet hiver. Son originalité réside dans l’utilisation d’une même brique de construction (constituée d’une bascule D et de quelques portes NAND) pour élaborer toutes les parties de la machine : bande, tête de lecture/écriture, automate de contrôle… La finalité est essentiellement pédagogique.

Une présentation plus détaillée est proposée sur ce site.