La programmation bayésienne : quésako ?
Ceux qui lisent Bishop ont peut-être remarqué qu’il encense les "Bayesian methods" depuis quelques papiers. Entrée en matière complètement pédante et étant juste un moyen de donner un lien d’autorité pour justifier un tant soit peu ce qui va suivre. Au passage, le lecteur non-fatigué, non-saoûl et intelligent de Nofrag aura remarqué que Bayesian prend un "b majuscule" contrairement à bayésien, c’est parce qu’en Anglais les adjectifs tirés des noms propres prennent une majuscule, pas comme en Français. Encore un peu de confiture sur votre tartine ?
Je me disais, avant ce baratin inutile, que ça pourrait être sympa de vulgariser ce qui est une de mes grandes révélations de l’année dans la masse de choses que j’apprend actuellement.
Partons de l’exemple de la robotique. Faire un robot qui fait pleins de choses utiles et/ou marrantes c’est simple dans la simulation, déjà un peu moins simple en expérimentation en labo (environnement controlé) ou à la coupe de France de robotique et carrément la mort en environnement réel. Pourquoi ça ? Déjà quand on écrit son propre simulateur pour sa propre expérience on a un gros biais. Ensuite quand on a des capteurs et des actionneurs bien dimensionnés par rapport à un environnement controlé (luminosité, vent, obstacles, image, bruit, poussière …), on peut assez facilement travailler avec ces données. Même si parfois il faut filtrer un bruit ou faire une analyse d’image pas évidente, ça reste du connu et maitrisé depuis longtemps. En situation réelle, il y a toujours qqch qui est comme il ne devrait PAS être. C’est le fameux gouffre théorie / pratique. Mais à quoi est-ce dû ? Je pense (en m’en étant convaincu et non persuadé) que c’est à cause d’un manque de connaissances. On a MODÉLISÉ un environnement possible et un comportement associé mais on perd forcément des paramètres variables réels en passant au modèle. C’est ces trucs à la con qui vont essayer par toutes les forces de la loi de Murphy et du "Théoriquement en pratique ça marche" de faire capoter votre expérimentation. En gros on en vient à faire un robot qui considère que son modèle mathématique est exact que c’est le monde physique qui a tort. Bah ui, patate ! [Je cite un jeune cousin]
Alors comment on fait pour traiter la feuille morte qui est passée devant la caméra dont on se sert pour faire de la vision sur notre robot ? Ou le chaos de la route imprévu lors du DARPA challenge ? On admet qu’on ne sait pas tout sur le monde réel et essaye de travailler quand même sans modifier le monde réel pour qu’il ressemble à un labo ? En simplifiant, pour raisonner avec des choses incertaines de nos jours on a les logiques floues et les méhodes bayésiennes. Les logiques floues c’est "il pleuvra certainement demain" et chacun y va de son formalisme et de sa méthode. Les méthodes bayésiennes c’est "il pleuvra avec la probabilité 0.8 demain" avec un formalisme qui commence à être solide et éprouvé. C’est numérique et ça c’est cool car les CPU, eux, ils savent bien traiter les nombres. Si on décide que l’on va inférer avec la méta-méthode bayésienne, on procède environ comme ça :
La structure du schéma est empruntée à Pierre Bessière dans son (très bon) Probabilistic Reasoning and Decision Making in Sensory Motor Systems. Note : P(A|B) c’est la probabilité d’avoir l’évènement A sachant que l’évènement B est arrivé. P(A et B) = P(A B) = P(A).P(B|A) prend donc tout son sens : la probabilité d’avoir les évènements A et B en même
temps c’est la probabilité d’avoir l’évènement A multiplié par la probabilité d’avoir l’évènement B en sachant qu’on a eu l’évènement A.
C’est donc simple : on n’as pas d’information totale, on raisonne avec des probabilités au lieu de logiques du 1er ou 2nd ordre pures. En fait on est même plus puissant dans un certain sens car on est capable de faire le Modus Ponens (si A est vrai et que A => B alors B est vrai) et le Modus Tollens (si B est faux et si A => B alors A est faux) avec notre représentation probabiliste. C’est juste pour MP : P(B=vrai | A=vrai) = 1 et pour MT : P(non(A=vrai) | non(B=vrai)) = 1 ou, si vous préférez et en vrai/faux binaire, P(A=faux | B=faux) = 1, essayez !
Mais on peut aller beaucoup plus loin grâce aux probas : P(B|A) = 1 nous apprend que P(A|B) sup ou égal à P(A) : si B est vrai, la probabilité que A soit vrai est supérieure à si on ne savait rien sur B. Ceux qui veulent se creuser un peu les méninges remplacent partout ci-dessus (ça marche à partir de MP / MT) A par "n est divisible par 9" et B par "n est divisible par 3". Ils apercevront alors la force du raisonnement via les probabilités, qui permet de faire une inférence qui est inaccessible à la logique pure : si on sait qu’un nombre est divisible par 3, il a plus de chances d’être divisible par 9 que si on se sait rien du tout. De même P(B|A) = 1 entraine que P(non(B) | non(A)) inf ou égal à P(non(B)) …
Voila, la programmation bayésienne c’est se baser sur le théorème de Bayes pour raisonner, inférer mais également en amont prévoir de traiter l’incomplétude par les probabilités. J’ai mis deux exemples plus appliqués dans un extrait de mon rapport de stage. J’espère avoir été (un peu) clair.
Là de suite je suis très fatigué et vous laisse donc un peu en plan mais n’hésitez pas à poser des questions sur ce pavé. Et si vous voulez en savoir plus, il y a google et bayesian-programming.org …
8 octobre 2008 à 7:55 Citer
intéressant; si j’essaye de resumer grossièrement, ca consiste à avoir un seuil d’erreur "intelligent", qui ne vire la portion suspecte qu’en rapport avec le taux de proba que cette anomalie arrive ?
8 octobre 2008 à 8:33 Citer
>>Modus Trollens (si B est faux et si A => B alors A est faux)
Euh, c’est pas plutôt Tollens ?
La limite que je vois à cette méthode, c’est que le Modus Tollens n’est vrai que lorsque A et B sont les seuls évènements du système : A=>B est une condition suffisante mais pas nécessaire donc s’il existe un évènement C et que C=>B, A=>B ne signifie plus que, lorsque A est faux, B l’est également. Donc, pour que la méthode bayesienne marche, il faut pouvoir être le plus précis possible en terme d’évènement, ce qui revient à émettre des hypothèses sur l’environnement d’éxécution d’un programme/robot … et comme le problème originel vient du fait qu’on est pas capable de les énumérer toute sans être limité, on retombe plus ou moins dans le même travers, non ?
8 octobre 2008 à 8:44 Citer
de mémoire, ya pas déjà une partie du processeur dédié au calcul hypothétique ? ca fait bien longtemps que j’ai pas taté le monde de l’asm (a part sur nintendo DS :D), mais jme souviens avoir entendu qu’un composant du proc calculait à l’avance les opérations les plus probables qui pouvaient être effectuées sous peu.
8 octobre 2008 à 9:22 Citer
bullshit j’ai fait la coupe de france de robotique, on a programmé en VHDL avec des pics et hop on était dans les 10 ème!
8 octobre 2008 à 10:10 Citer
@vimes
>>Modus Trollens (si B est faux et si A => B alors A est faux)
Euh, c’est pas plutôt Tollens ? ==> Bien sûr que si …
ahahah elle est énorme cette bourde ! J’étais un peu fatigué et rentrais d’une crémaillère. Pardon.
Pour ce qui est du pbm d’avoir plus de précision en terme d’évènements : je ne pense pas. Pour 2 raisons :
1) Quand tu fais de l’inférence logique tu as aussi ce travers.
2) Raisonner avec le des probas t’ajoute de l’information, ça ne pose pas de pbm tant que l’on les prend avec des "pincettes probabilistes" ;)
Pour ce qui est de C et C=>B et A=>B et non(A) ça n’a rien à avoir avec le Modus Tollens qui serait C=>B et A=>B et non(B) : dans ce cas là t’infères non(C) et non(A) mais si tu mets C dans ton savoir de départ t’as juste un clash et donc soit de mauvaises règles soit un C=vrai qui est une erreur d’observation. Ton C et C=>B et A=>B et non(A) est également (en logique pure du style 1er ordre) un clash : 1. et 2. => B et 3. et 4. => non(B) donc clash. C’est un cas qui correspond à une erreur de mesure. Si tu travaillais en bayésien et que C et non(A) sont des observations, elle ne peuvent (à moins d’avoir un modèle / des règles totalement faux(sses), ce qui est possible aussi) coexister avec la probabilité 1. Mais tu n’es as bloqué si elles ont des probas < 1.
@divide
Pas vraiment. Tu ne maitrise pas ton seuil d’erreur, tu donnes un formalisme qui permet de compléter avec des "best guess" un manque d’information et qui permet d’inférer avec justement ces connaissances "pas sûres" et en particulier ne pas se fermer de portes directement comme on le ferait en logique classique (cf. ci dessus clash direct). Ce qui est vrai c’est que tu diminues ton niveau d’incertitude en augmentant ton ignorance (correspond un peu à ton idée de seuil d’erreur).
@Rom.1
J’ai bien l’impression que tu parles de Branch Prediction (ou wikipedia), ce qui n’as pas grand chose à avoir avec la programmation bayésienne. C’est juste que si tu arrives sur un branchement conditionnel (un if ou un test de boucle par exemple) et que t’as encore de la place dans ton pipeline tu le remplis avec la suite du branchement (le jmp) le plus probable, comme ça si il arrive tu gagnes du temps, et si c’est l’autre bout de code qui doit s’éxécuter t’en perds pas beaucoup parce que oui il faut reremplir le pipeline mais de toute façon si tu le laissais vide il aurait aussi fallu le reremplir.
@mouito
J’ai souri :)
[VHDL : décrire des circuits électronique, par exemple pour les programmer sur FPGA. Pics : micro-controleurs programmables, en C, Basic, assembleur PIC si tu veux, mais certainement pas VHDL. Après on combine du FPGA et des micro-controleurs pour la commande des robots mais Coupe de France = environnement maitrisé donc HS]
8 octobre 2008 à 15:10 Citer
En tout cas, les DARPA challenges, c’est assez génial. Merci pour la découverte ! (On trouve pas mal de trucs sur Youtube sur le sujet, pour les curieux)
8 octobre 2008 à 16:45 Citer
Beaucoup de filtres anti-spam (celui de Thunderbird par exemple) utilisent des algos bayesiens. Le "bon" plugin anti-spam pour Outlook s’appelle d’ailleurs SpamBayes.
8 octobre 2008 à 19:26 Citer
Ca me fait penser à la logique flou.
9 octobre 2008 à 1:25 Citer
environnement maitrisé la coupe de France et mon cul c’est du poulet? Les seules trucs que tu sais c’est les dimensions de la trable et les régles après il t’arrive 100 milles trucs,
On avait battu une team qui avait fait des robots limites pros, tu leur dira que l’environnement est maitrisé!
9 octobre 2008 à 2:20 Citer
C’est la faute à leur putain d’éclairages de merde qui foutent la moitié des lasers en l’air !