Théorème de Cox-Jaynes

Théorème de Cox-Jaynes

Type	Théorème
Nommé en référence à	Richard Threlkeld Cox

modifier - modifier le code - modifier Wikidata

Le théorème de Cox-Jaynes (1946) codifie et quantifie la démarche d'apprentissage en se fondant sur cinq postulats (desiderata) simples. Cette codification coïncide avec celle de probabilité, historiquement d'origine toute différente. Le théorème doit son nom au physicien Richard Threlkeld Cox qui en a formulé la version initiale.

Cox formalise la notion intuitive de plausibilité sous une forme numérique. Il démontre que, si les plausibilités satisfont à un ensemble d'hypothèses, la seule façon cohérente de les manipuler est d'utiliser un système isomorphe à la théorie des probabilités.

Ce système induit une interprétation rationnelle des probabilités qui fournit une base au mécanisme d'induction logique, et donc à l'apprentissage automatique, sans dépendre du concept statistique de fréquence. Qui plus est, le théorème, sous les conditions imposées par les postulats, implique que toute autre forme de prise en compte des informations dans le cadre de cette représentation particulière de la connaissance serait en fait biaisée. Il s'agit donc d'un résultat extrêmement fort^[1].

Les résultats de Cox n'avaient touché qu'une audience restreinte avant qu'Edwin Thompson Jaynes ne redécouvrît ce théorème et n'en défrichât une série d'implications pour les méthodes bayésiennes^{[1][source insuffisante][2]}. Irving John Good en explora les conséquences dans le domaine de l'intelligence artificielle^[3].

Stanislas Dehaene utilise le théorème, sa construction et ses applications dans le cadre de l'étude des processus cognitifs humains^[4], suivant en cela une idée déjà énoncée en 1988 par Jaynes^[5].

Problèmes de validité de la démarche inductive avant Cox

Réserves de Bertrand Russell

Dans son essai « La science est-elle superstitieuse ? », Bertrand Russell évoque le « scandale de l'induction^[6] » :

• Au nom de quoi affirmer, même de façon provisoire, que ce qui a été vérifié dans un nombre limité de cas se vérifiera aussi dans les cas qui n'ont pas été testés ?
• Au nom de quoi supposer, même sur ce qui a été mesuré, que ce qui a été vrai hier le sera toujours demain ?

Paradoxe de Hempel

Ce paradoxe visait à montrer une faille dans le mécanisme d'induction, qui imposait que le domaine de validité de celui-ci fût précisé de façon plus rigoureuse : le contexte de ce dont on parle doit être toujours mentionné. Ainsi le comptage des oiseaux à la fois non-blancs et non-corbeaux dans une chambre ne renseigne pas sur la probabilité que tous les corbeaux soient blancs, mais que tous les corbeaux soient blancs dans cette chambre — affirmation parfaitement exacte quand il n'y a aucun corbeau dans la chambre, en vertu de la relation (qui définit l'implication logique, dans une logique purement déductive) :

${\displaystyle (p\Rightarrow q)\Leftrightarrow ((p\wedge q)\vee \neg p)}$

Concept de « Desiderata » (axiomes)

Cox pose cinq desiderata pour un robot qui raisonnerait selon une logique inductive.

Trois d'entre eux s'appliquent à la méthode :

cohérence

s'il existe plusieurs façons de trouver un résultat, elles doivent aboutir au même résultat ;

continuité de méthode

un changement de valeur d'un paramètre ne doit pas obliger à changer de méthode de calcul ;

universalité

on désire un calculateur de situations général, non destiné à un usage particulier.

Deux sont requis de l'utilisateur :

spécifications non ambiguës

une proposition doit pouvoir être comprise d'une façon et d'une seule ;

pas de rétention d'information

le robot connaît toutes les données pertinentes ^[7].

1. Des nombres peuvent représenter les degrés de plausibilité

Il faut pouvoir à tout moment dire de deux plausibilités laquelle est plus grande que l'autre. Cette relation d'ordre suggère une représentation quantitative, et la forme numérique semble commode.

Une représentation sous forme de nombres entiers poserait un problème, aucune plausibilité ne pouvant se glisser entre deux représentées par des entiers successifs. Il faut donc un ensemble dense.

Des rationnels conviendraient, à plus forte raison les nombres réels conviennent.

La convention adoptée, arbitrairement, est que des plausibilités plus grandes seront représentées par des nombres plus grands.

2. Les règles d'inférence ne doivent pas contredire les règles d'inférence communes

Ce qui nous paraît évident ne doit pas être contredit par le modèle. Cette règle simple en apparence n'est pas toujours facile à appliquer dans le cas de préférences collectives, comme le montrent le paradoxe de Condorcet et le théorème d'impossibilité d'Arrow.

Exemple de règle :

• si A est préférable à B,
• et B est préférable à C,
• alors toutes choses égales par ailleurs et en l'absence de B, A est préférable à C.

3. Règle de cohérence

Si une conclusion peut être obtenue par plus d'un moyen, alors tous ces moyens doivent bien donner le même résultat.

Cette règle élimine du champ d'examen les « heuristiques multiples » dès lors qu'elles pourraient contenir entre elles des contradictions (comme le font par exemple parfois les critères de Savage et de Wald, se réclamant tous deux du minimax de la théorie des jeux).

4. Règle d'honnêteté

Le robot doit toujours prendre en compte la totalité de l'information qui lui est fournie. Il ne doit pas en ignorer délibérément une partie et fonder ses conclusions sur le reste. En d'autres termes, le robot doit être totalement non idéologique, neutre de point de vue.

5. Règle de reproductibilité

Le robot représente des états de connaissance équivalents par des plausibilités équivalentes. Si deux problèmes sont identiques à un simple étiquetage de propositions près, le robot doit affecter les mêmes plausibilités aux deux cas.

Deux propositions doivent donc être considérées a priori comme de plausibilité équivalente quand elles ne se distinguent que par leur nom, ce qui n'arrive guère que dans des cas très particuliers, comme pour des pièces ou des dés non pipés.

Lois de composition interne

Règle de somme

Sans rentrer dans les équations, l'idée est que lorsque deux plausibilités du même état se composent, la plausibilité composée est nécessairement égale ou supérieure à la plus grande des deux.

Règle de produit

Il s'agit ici du cas inverse : quand deux plausibilités doivent toutes deux être vérifiées pour qu'un état puisse exister, cet état ne peut avoir de plausibilité plus grande que la plus petite des deux précédentes.

Résultats

Notation d'I. J. Good (weight of evidence)

Good a proposé une notation permettant de manipuler plus aisément les plausibilités. Alan Turing avait fait remarquer en son temps que l'expression des probabilités était beaucoup plus facile à manier en remplaçant une probabilité p variant de 0 à 1 par l'expression ln (p/(1-p)) permettant une meilleure discrimination des très petites valeurs (très proches de 0) comme des très grandes (très proches de 1). En particulier, sous cette forme, un apport d'information par la règle de Bayes se traduit par l'ajout d'une quantité algébrique unique à cette expression (que Turing nommait log-odd), cela quelle que soit la probabilité a priori de départ avant l'observation^{[réf. nécessaire]}. La notation de Good utilise, conformément à cette idée, une échelle logarithmique.

Échelle en décibans

Irving John Good utilisa une variante de cette idée pour faciliter le travail avec ces nouvelles quantités. À la différence de Turing :

• il utilisa un logarithme décimal plutôt que naturel, afin que l'ordre de grandeur de la probabilité associée apparaisse à simple lecture et
• adopta un facteur 10 afin d'éviter la complication de manier des quantités décimales, là où une précision de 25 % suffisait.

Il nomma la mesure correspondante, W = 10 log₁₀ (p/(1-p)), weight of evidence parce qu'elle permettait de « peser » le témoignage des faits en fonction des attentes - manifestées par des probabilités « subjectives » antérieures à l'observation - de façon indépendante de ces attentes^{[1][source insuffisante]}.

Pour éviter toute connotation parasite, Dehaene préfère parler plutôt de décibans, comme Turing, que de décibels comme Good^[8].

En bits

Les évidences sont parfois exprimées aussi en bits, en particulier dans les tests de validité de lois scalantes.

En effet, quand une loi comme la loi de Zipf ou de Mandelbrot s'ajuste mieux aux données qu'une autre loi ne nécessitant pas de tri préalable, il faut tenir compte du fait que trier une séquence de n termes sélectionne arbitrairement une permutation parmi n! possibles. Le tri représente un apport d'information (ou d'ordre) de l'ordre de n log₂ n. Cet apport d'information pourrait suffire au meilleur ajustement. On peut s'attendre à voir une répartition décroissante rendre mieux compte de ce qu'on vient de trier soi-même en ordre décroissant.

Si le gain d'évidence qu'apporte le tri représente moins de bits que celui qu'a coûté le tri, l'information apportée par la considération d'une loi scalante est nulle. L'ordre apporté est simplement celui que nous venons de mettre : le modèle ne doit donc pas dans ce cas être conservé. Dans d'autres, sa validité ressort nettement : voir Loi de Zipf-Mandelbrot^[9].

Conséquences du théorème

Unification de l'algèbre de Boole et de la théorie des probabilités

On remarque que l'algèbre de Boole est isomorphe à la théorie des probabilités réduite aux seules valeurs 0 et 1.

• Et logique = produit de probabilités
• Ou logique = somme moins produit de deux probabilités (p+p'-p.p')
• Non logique = complément d'une probabilité (p → 1-p)

Cette considération conduisit à l'invention dans les années 1970 des calculateurs stochastiques promus par la société Alsthom (qui s'écrivait avec un h à l'époque) et qui entendaient combiner le faible coût des circuits de commutation avec la puissance de traitement des calculateurs analogiques. Quelques-uns furent réalisés à l'époque.

Abandon du paradigme « fréquentiste »

Myron Tribus propose de considérer la probabilité comme la simple traduction numérique d'un état de connaissance et non comme le passage à la limite de la notion de fréquence. À l'appui, il prend l'image classique du dé dont la probabilité de sortie de chaque face est considérée au départ de 1/6^e même si le dé est en glace, donc ne peut être lancé plus d'un petit nombre de fois, ce qui interdit tout passage à la limite.

Il imagine alors l'objection d'un interlocuteur : « Si je me représente mentalement mille dés, je peux bel et bien envisager un passage à la limite, » à laquelle il répond : « Tout à fait. Et si donc vous ne vous les représentez que mentalement, c'est parce qu'il s'agit bien là seulement d'un état de connaissance^[a]»

Les divergences entre approches fréquentistes et bayésiennes ont suscité beaucoup de passion dans les années 1970, où elles prenaient alors presque l'aspect d'une « guerre de religion. » Leur coexistence « pacifique » est aujourd'hui admise, chacune ayant son domaine d'efficacité maximale et les deux approches convergeant de toute façon lorsqu'on passe aux grands nombres d'observations^[10]. Il n'y a pas de conflit pour les petits nombres, les méthodes fréquentistes (statistiques) ne concernant pas ce domaine d'application.

Bases rationnelles de l'apprentissage machine

Edwin Thompson Jaynes, dans sa reprise et son approfondissement du théorème de Cox, utilise celui-ci pour montrer que tout apprentissage y compris automatique devra nécessairement soit utiliser l'inférence bayésienne (à un homomorphisme près si on le désire, comme un passage par une transformation logarithme simplifiant les calculs pratiques), soit donner quelque part des résultats incohérents et être, en conséquence, inadapté. Ce résultat extrêmement fort, nécessite l'acceptation de cinq desiderata simples, dont celui de la continuité de méthode (ne pas changer brusquement d'algorithme simplement parce qu'une donnée est modifiée de façon infinitésimale)^{[11][source insuffisante]}.

Voir également l'article Logit.

Rapport avec la « logique floue »

Les approches sont différentes : la logique dite floue est d'origine pragmatique (un exemple de "logique floue" est le classement d'élèves à un examen général par emploi de coefficients arbitraires pour chaque matière) et sans véritables théorèmes : il s'agit d'une simple technique. L'apprentissage bayésien relève d'une théorie solide fondée sur un édifice mathématique et des notions quantitatives, comme la maximisation d'entropie (MAXENT). Il est vrai que les deux approches ont fini par converger (détection automatique des scènes pour les appareils photo numériques, reconnaissance de voix et de caractères), mais uniquement parce que les approches bayésiennes ont largement phagocyté le reste.

Limitations importantes du théorème

Le théorème suppose qu'une décomposition en propositions lui est préalable et qu'il ne reste qu'à estimer la valeur de chacune. Par la suite, Satosi Watanabe (en) fit observer que toute décomposition en critères est, par construction, arbitraire (Ugly-Duckling Theorem^[12]), et ne saurait donc prétendre à une quelconque impersonnalité. Murphy et Medin l'illustrèrent de façon sarcastique en 1985 :

« Supposons que l'on liste les attributs que les prunes et les tondeuses à gazon ont en commun afin de juger de leur similitude Il est facile de voir que la liste pourrait être infinie. Les deux pèsent moins de 10 tonnes (et moins de 11), n'existaient pas il y a 10 millions d’années (ni 11), les deux ne disposent pas d’organes auditifs, les deux peuvent être abandonnées, les deux prennent de l'espace, et ainsi de suite. de même, la liste des différences pourrait être infinie ... Les deux entités peuvent être considérées arbitrairement similaires ou dissemblables par le simple choix des attributs que l’on choisit de considérer comme pertinents^[b],[13] »

Un paradoxe apparent

Chaque discipline possède ses mesures favorites : si la thermique s'occupe principalement de températures, la thermodynamique sera plus attachée à des mesures de quantité de chaleur, voire d'entropie. L'électrostatique s'intéresse plus aux tensions qu'aux intensités, tandis que c'est l'inverse pour les courants faibles, et qu'en électrotechnique c'est davantage en termes de puissance qu'on aura tendance à raisonner. Selon sa discipline d'origine, chaque expérimentateur tendra donc à effectuer ses estimations sur les unités auxquelles il est habitué^{[réf. souhaitée]}.

Dans le cas d'un montage électrique, un spécialiste d'électrotechnique fera peut-être une estimation de puissance dissipée (RI²) tandis qu'un spécialiste des courants faibles préférera estimer l'intensité elle-même (I). Si la convergence à terme des estimations est assurée dans les deux cas, elle ne se fera pas de la même façon, même avec des distributions a priori identiques, car l'espérance mathématique d'un carré n'est pas mathématiquement liée au carré d'une espérance. Il s'agit là de la principale pierre d'achoppement des méthodes bayésiennes^{[source insuffisante]}.

Rôle du langage

Indépendamment des probabilités a priori que nous attribuons aux événements, nos estimations sont également en partie « formatées » par le langage et la « déformation professionnelle » qui s'y attachent. Concrètement, cela rappelle qu'il n'existe pas seulement une, mais deux sources d'arbitraire dans les méthodes bayésiennes : celle, de mesure, qui entache les probabilités a priori choisies^[c] et celle, de méthode, qui correspond à notre représentation du problème. En revanche, l'arbitraire se limite à ces deux éléments, et les méthodes bayésiennes sont ensuite totalement impersonnelles.

Annexes

Bibliographie

Cox et Jaynes

• (en) R. T. Cox, Probability, Frequency, and Reasonable Expectation, Am. Jour. Phys., 14, 1–13, (1946).
• (en) R. T. Cox, The Algebra of Probable Inference, Johns Hopkins University Press, Baltimore, MD, (1961).
• (en) Edwin Thompson Jaynes, Probability Theory : The Logic of Science, Cambridge University Press, 2003, 727 p. (ISBN 978-0-521-59271-0, lire en ligne). Conformément à la demande de Jaynes, décédé en 1998, son ouvrage est publiquement lisible en PDF sur la Toile :
  • (en) Edwin Thompson Jaynes, Probability Theory : The Logic of Science, Cambridge University Press, 1994 (lire en ligne) (Fragmentary Edition of June 1994) ;
  • (en) Edwin Thompson Jaynes, Probability Theory : The Logic of Science, Cambridge University Press, 1996 (lire en ligne) (Chapters 1 to 3 of published version) ;
  • Cox-Jaynes (PDF)
• (en) Edwin Thompson Jaynes, « How Does the Brain Do Plausible Reasoning », dans G. J. Erikson et C. R. Smith (eds.), Maximum Entropy and Bayesian Methods in Science and Engineering, vol. 1, Kluwer Academic Publishers, 1988 (lire en ligne)

Autres

• Myron Tribus (trad. Jacques Pézier), Décisions rationnelles dans l'incertain [« Rational descriptions, decisions and designs »], Paris, Masson, 1974 (1^re éd. 1969).
• (de) Niels Henrik Abel, « Untersuchung der Functionen zweier unabhängig veränderlichen Gröszen x und y, wie f(x, y), welche die Eigenschaft haben, dasz f[z, f(x,y)] eine symmetrische Function von z, x und y ist », J. reine angew. Math., vol. 1,‎ 1826, p. 11-15.
• (en) Janos Aczél (en), Lectures on Functional Equations and their Applications, Academic Press, New York, 1966.
• (en) Stefan Arnborg and Gunnar Sjödin, On the foundations of Bayesianism, Preprint : Nada, KTH (1999) ps, pdf
• (en) Stefan Arnborg and Gunnar Sjödin, A note on the foundations of Bayesianism, Preprint : Nada, KTH (2000a), ps, pdf
• (en) Stefan Arnborg and Gunnar Sjödin, « Bayes rules in finite models », dans European Conference on Artificial Intelligence, Berlin, (2000b), ps, pdf
• (en) Pierre Baldi et Søren Brunak, Bioinformatics: The Machine Learning Approach, MIT Press, 2.2 The Cox-Jayes approach, pages 50-57
• (en) Terrence L. Fine, Theories of Probability: An Examination of Foundations, Academic Press, New York, 1973.
• (en) Michael Hardy, « Scaled Boolean algebras », Advances in Applied Mathematics, vol. 29, n^o 2, 2002, p. 243-292, DOI 10.1016/S0196-8858(02)00011-8, arXiv:math.PR/0203249
• (en) Joseph Y. Halpern, « A counterexample to theorems of Cox and Fine », Journal of AI research, vol. 10, 1999, p. 67-85
• (en) Joseph Y. Halpern, « Technical Addendum, Cox's theorem Revisited », Journal of AI research, vol. 11, 1999, p. 429-435
• (en) Myron Tribus, Rational Descriptions, Decisions and Designs, Pergamon Press, 1969, 479 p.
• (en) Kevin S. Van Horn, « Constructing a logic of plausible inference: a guide to Cox’s theorem », International Journal of Approximate Reasoning, vol. 34, n^o 1, 2003, p. 3-24, DOI 10.1016/S0888-613X(03)00051-3.

Articles connexes

• Apprentissage automatique
• Bertrand Russell
• Inférence bayésienne
• Logique floue
• Probabilité
• Théorème de Bayes

Liens externes

• (en) Some Key References on the Cox Proof of Bayesianism Liste bibliographique plus détaillée, et annotée.
• P. Bessière et al., Fondements mathématiques de l'approche F+D [PDF] : détails sur le théorème de Cox, implications et application.
• Université de Valenciennes, E-Diagnostic : Cours de sensibilisation aux techniques de diagnostic; méthodes déductives, inductives et abductives.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cox's theorem » (voir la liste des auteurs).

1. Tribus 1969, p. 60, qui dit s'être inspiré de Probability and Scientific Inference de G.S. Brown (1957)
2. « Suppose that one is to list the attributes that plums and lawnmowers have in common in order to judge their similarity. It is easy to see that the list could be infinite: Both weigh less than 10,000 kg (and less than 10,001 kg), both did not exist 10,000,000 years ago (and 10,000,001 years ago), both cannot hear well, both can be dropped, both take up space, and so on. Likewise, the list of differences could be infinite… any two entities can be arbitrarily similar or dissimilar by changing the criterion of what counts as a relevant attribute »^[13]
3. Le choix d'une distribution d'entropie maximale (« MAXENT ») parmi celles qui satisfont aux contraintes garantit que l'on choisit la moins arbitraire. Loi normale de Gauss, loi exponentielle décroissante, loi de Zipf-Mandelbrot sont respectivement d'entropie maximale quand on fixe moyenne et écart-type, moyenne seule ou rang moyen seul

1. Tribus 1969, Tribus 1974.
2. Jaynes 2003, p. ch. 1 à 3.
3. Irving John Good, « Speculations concerning the first ultraintelligent machine », Advances in Computers, vol. 6,‎ 1965 (lire en ligne [archive du 4 mars 2016], consulté le 26 mars 2016).
4. Cours au Collège de France (2011-2012), 10 janvier 2012 : Introduction au raisonnement Bayésien et à ses applications.
5. Jaynes 1988
6. Bertrand Russell, Essais sceptiques, Paris, Les Belles Lettres, 2011 (1^re éd. 1928), chap. 3.
7. Tribus 1969, p. 5-6.
8. S. Dehaene, « Les mécanismes Bayésiens de l'induction chez l'enfant », sur Collège de France, 17 janvier 2012.
9. Léon Brillouin, La science et la théorie de l'information, Paris, Masson, 1959 (1^re éd. 1955), p. 45-48.
10. (en) Jordi Vallverdú, « The False Dilemma: Bayesian vs. Frequentist », E-Logos,‎ 2003 (lire en ligne, consulté le 20 octobre 2013)
11. Jaynes 2003
12. (en) Satosi Watanabe, Knowing and Guessing: A Quantitative Study of Inference and Information, New York, Wiley, 1969 (ISBN 0-471-92130-0, lire en ligne), p. 376–377 .
13. (en) G. L. Murphy et D. L. Medin, « The Role of Theories in Conceptual Coherence », Psychological Review, vol. 92, n^o 3,‎ 1985, p. 289-316