Mois : juin 2013

« Le méta pue », ou Crédibilité des preuves

Publié le par Balise1 commentaire

Il y a quelque temps, une soumission à arXiv a fait pas mal de bruit. arXiv, pour ceux qui ne connaissent pas, est une archive d’articles scientifiques – les auteurs y soumettent en général des versions préliminaires d’articles publiés ailleurs. arXiv fait un peu de modération pour éviter le spam et les trucs vraiment délirants, mais, si je comprends bien, tant que ça a à peu près une tronche d’article scientifique dans les domaines gérés par arXiv, ça passe la modération.

Et, donc, le 26 mai, ya un article intitulé A Polynomial Time Algorithm for the Hamilton Circuit Problem, par Xinwen Jiang, qui est apparu sur arXiv. Dans la description de l’article, il y a une petite phrase : « Our result implies NP=P », c’est à dire « Notre résultat implique que P=NP ». Pour un petit rappel sur le problème en question, il se trouve que j’ai causé à ce sujet dans le billet intitulé, fort logiquement, Le problème « P est-il égal à NP ? ».

J’avoue que je ne comprends pas bien pourquoi, spécifiquement, ce papier a fait du bruit. Et par « faire du bruit », j’entends qu’il est passé plusieurs fois sur mon radar, par plusieurs sources différentes. Je ne comprends pas pourquoi, parce que des papiers qui prouvent que P = NP ou que P ≠ NP, il y en a au moins une dizaine par an – voir par exemple The P-versus-NP Page qui vise à tous les recenser. Et qu’on ne fait pas tout un pataquès tous les mois à ce sujet.

C’est bizarre, parce qu’il y a tout un tas de choses qui font que ce papier est peu crédible. Scott Aaronson a écrit des choses sur la crédibilité des articles scientifiques « révolutionnaires » : je citerai ici Ten Signs a Claimed Mathematical Breakthrough is Wrong et Eight Signs A Claimed P is not NP Proof Is Wrong. Aaronson s’intéresse plutôt aux preuves P ≠ NP, mais certains arguments sont aussi valides dans le cas des preuves P = NP.

J’avoue humblement que je n’ai pas lu le papier de Xinwen Jiang. Je ne sais pas non plus si quelqu’un (n’importe qui) a lu le papier de façon sérieuse. Je n’ai trouvé aucun article ou billet de blog disant « la preuve de Xinwen Jiang est fausse et voici pourquoi », ni d’article « meeeeerde, ça marche, son truc ». La discussion la plus fournie que j’ai vu passer est celle de Hacker News dans ce fil de discussion.

Personnellement, la raison principale pour laquelle j’ai abandonné la lecture du papier va sembler extrêmement snob. Mais le papier n’est pas écrit en \LaTeX. Du coup… ben j’ai pas eu le courage, bêtement. La mise en page est immonde, les maths sont illisibles. Je regarde ce truc et j’ai mal au crâne. Un petit morceau de moi se dit que si le type en face n’a pas pris la peine de faire en sorte que son machin soit lisible, je vois pas pourquoi je prendrais la peine de tenter de le lire. Évidemment, c’est hyper-fallacieux, comme argument. Parce que si jamais quelqu’un arrive avec une preuve qui marche, il a moyen de troller une communauté complète rien qu’en publiant sa preuve en Word 😀 Après, je peux argumenter sur le fait que j’ai jamais réussi à utiliser l’éditeur d’équations de Word de façon raisonnablement déterministe, alors que \LaTeX se comporte plutôt mieux de ce point de vue, et que j’ai donc plus confiance dans le fait qu’un papier en \LaTeX reflète effectivement ce que l’auteur voulait dire. Mais ça touche probablement à la mauvaise foi aussi.

Dans les arguments un demi-chouille plus « sérieux », mais qui touchent toujours au méta : l’auteur est tout seul, et il ne remercie aucun collègue, aucun relecteur. Sur un résultat de cette ampleur, c’est un peu bizarre. Évidemment, le concept de génie solitaire qui résout tout seul un problème qui a échappé à des milliers de chercheurs est extrêmement romantique. Mais il est aussi extrêmement peu crédible.

Troisième point : les références bibliographiques. Il y a 12 références bibliographiques dans cet article. Dix d’entre elles sont des auto-références (l’auteur fait référence à des travaux personnels précédents). La première de la liste est un bouquin très classique, genre bouquin de cours sur le sujet. Là encore, c’est douteux.

Pour finir, l’article se termine par « Until now, since 2010.10.06, more than 52 millions of instances have been generated randomly, each of which has 100 vertices. Some instances contain a simple path while others (it is the majority in all the generated instances) do not. All the results show that our polynomial time algorithm can get the same answer as the backtracking algorithm does. No exception. », ce qui se traduit par « Jusqu’à présent, depuis le 6 juin 2010, nous avons généré aléatoirement plus de 52 millions d’instances sur 100 sommets chacunes. Certaines instances contiennent un chemin simple tandis que d’autres (la majorité des instances générées) non. Tous les résultats montrent que notre algorithme polynomial ont le même résultat que l’algorithme de backtracking. Aucune exception. ». Ça pourrait sembler être un argument en faveur de la preuve. Mais il y a plusieurs choses qui sont discutables sur cet argument. Déjà, il se peut que le générateur aléatoire d’instances soit biaisé, et se trouve louper les instances pour lesquelles ça ne marche pas. D’autre part, le nombre de sommets considéré est relativement bas. Si ça se trouve, ça plante pour 1000 sommets. Ou pour 101. Tertio, il se peut que les instances « difficiles » du problème soient rares. Ça fait partie des choses qu’on ne sait pas, d’ailleurs : si P ≠ NP, les instances d’un problème NP donné pour lesquelles c’est effectivement un facteur (c’est-à-dire qui n’ont pas de caractéristique permettant de résoudre l’instance par un algorithme rapide) sont-elles rares ou fréquentes ? Quatro, l’argument « ça fait un moment que je cherche et j’ai toujours pas trouvé de truc qui fait que ça marche pas »… j’ai essayé, hein, ben souvent les gens qui corrigent mes copies sont pas pour 😀

Bref, comme dit précédemment, c’est un peu des arguments fallacieux, tout ça, parce que ça serait facile de transformer n’importe quel papier « crédible » en papier « absolument pas crédible », et là j’aurai l’air très très bête. Je ne sais pas exactement ce que je veux dire, en fait. Dans un sens, ça me gène de recourir à ce genre d’argument pour décider que « ça sent pas bon, son truc », parce qu’il y a toujours le doute, dans un coin de neurone, du « oui, mais si les apparences étaient trompeuses ? ». D’un autre côté, comme dit Aaronson, il y a suffisamment de papiers sur le sujet pour que des heuristiques de crédibilité soient nécessaires. Quelque part, c’est peut-être à relier au processus de recrutement d’un candidat. Un candidat à un job doit souvent passer par des « formes obligées » qui démontrent sa crédibilité. Et il y a probablement un certain nombre de « faux négatifs » dans tout ce processus de formes obligées. On peut le déplorer. Et, dans le cas d’une preuve P = NP, un faux négatif serait… intéressant 😀

Mais dans le cas d’une preuve P = NP, je soupçonne qu’il faille redoubler d’attention à la crédibilité du papier. L’immense majorité de la communauté scientifique est raisonnablement convaincue que P ≠ NP. Du coup, arriver en affirmant l’inverse… ben ça part pas bien, déjà. Et si « le méta pue », il y a peu de chance que quiconque prenne la peine d’examiner le papier.

Et peut-être que demain je vais me prendre une grosse baffe dans la figure parce qu’un papier dont « le méta pue » va démontrer correctement un résultat que personne n’attend. Je crois que P ≠ NP. Et quand je dis « je crois », c’est vraiment exactement ça : une croyance, peut-être même une foi. N’empêche que j’adorerais avoir tort. Ça serait profondément drôle.. Si ça se trouve, on va trouver demain un algorithme pour SAT en n¹⁰⁰⁰⁰. Ben on sera bien avancés avec ça. Les années qui suivront seraient probablement super marrantes – parce que probablement on se tirerait tous la bourre pour faire descendre ce fichu 10000, et ça finirait probablement par arriver. Ça serait marrant.

Probabilités – Partie 2

Publié le par Balise2 commentaires

This post was translated to English here: Intro to probability theory – part 2.

Bon. Donc, je vous ai lâchement abandonnés après une première partie sur les probabilités, et puis ça fait un peu trois mois. Mes excuses. On va quand même reprendre comme si de rien n’était, parce que c’est mon blog et que je fais ce que je veux.

Donc, aujourd’hui, c’est raviolisvariables aléatoires. Le concept des variables aléatoires, c’est de réussir à faire des trucs qui se tiennent à peu près quand on ne sait pas exactement ce qui se passe (par exemple on jette un dé) – mais qu’on veut quand même avoir une idée de ce qui peut se passer. Dans le cas d’un seul dé, c’est peut-être un peu overkill, mais gardons les exemples simples pour l’instant.

L’idée, c’est qu’on prend une variable, mettons X, et qu’on considère toutes les valeurs qu’elle peut avoir, avec la probabilité associée. Pour reprendre les exemples de la partie 1, on peut par exemple définir une variable aléatoire sur la valeur d’un dé à six faces, et appeler ça X. Pour que ma définition soit complète, il faut que j’énonce toutes les valeurs possibles de X : si j’ai un dé à 6 faces, ben ça sera les valeurs de 1 à 6, et il faut que je dise quelle probabilité a chaque valeur : pour un dé non pipé, toutes ces probabilités sont égales à 1/6. On peut écrire ça rapidement comme ça :

\forall i \in \{1,2,3,4,5,6\}, \Pr[X = i] = \frac 1 6

Ça se lit « Pour tout élément i de l’ensemble {1,2,3,4,5,6}, la probabilité que X soit égal à i est égale à 1/6 ». On dit aussi que l’ensemble des valeurs qu’une variable aléatoire X est le domaine de X.

Un truc qu’on fait très, très souvent avec des variables aléatoires, c’est de calculer leur espérance. L’espérance d’une variable aléatoire, on peut voir ça comme sa valeur moyenne, ou comme un « si je lance mon dé 1000 fois, et que je fais la moyenne de tous mes résultats (somme des résultats divisée par 1000), qu’est-ce que je m’attends à avoir comme nombre ? ». Notons que l’explication que je donne là n’est pas très rigoureuse, mais j’espère qu’elle donne une idée de la chose.

Il se trouve qu’on peut calculer cette espérance (notée E[X]) de façon assez simple avec la formule suivante :

E[X] = \sum_{i} \Pr[X = i] \times i

ce qui se lit « somme pour tous les éléments i de i fois la probabilité que X soit égal à i ». Bon, ma définition n’est pas tout à fait correcte, parce que je ne définis pas ce sur quoi la somme se fait exactement. Pour corriger ça, je m’en vais faire ça de ce pas : je fais la somme sur tout le domaine de X. On va prendre un exemple, parce que je sens que ça va aider. Si je reprends mon exemple précédent avec mon dé, le domaine c’est {1,2,3,4,5,6}, donc j’ai

E[X] = \sum_{i = 1}^6 \Pr[X = i] \times i

et ça je peux l’étendre comme ça :

E[X] = 1 \times \Pr[X = 1] + 2 \times \Pr[X = 2] + 3 \times \Pr[X = 3] + 4 \times \Pr[X = 4] + 5 \times \Pr[X = 5] + 6 \times \Pr[X = 6]

Comme, dans le cas de mon dé, toutes les probabilités sont égales à 1/6, je conclus par

E[X] = \frac 1 6 \times (1 + 2 + 3 + 4 + 5 + 6) = \frac{21}{6} = 3.5

Bon, maintenant, on va prendre un exemple un peu plus compliqué. Supposons que je lance n dés, et que je m’intéresse au nombre de 6 qu’il y a dans mes n dés. Déjà, je vous pose la question : d’après vous, si je lance n dés, combien de 6 y aura-t-il ? Évidemment, c’est difficile de répondre exactement. Par contre, on peut se dire qu’il n’y a pas vraiment de raison qu’il y ait plus ou moins de 6 que de 1, de 2, de 3, de 4 ou de 5, et que globalement les dés devraient se répartir à peu près équitablement dans les 6 nombres, et que donc il y aurait à peu près 1/6 n six sur mes n dés. (Bon, sauf quand on joue les orks à Warhammer 40k, là il y a à peu près 3 six sur 140 dés). Donc, on va essayer de prouver ça un peu proprement.

Donc, je définis Y comme la variable aléatoire « nombre de six sur n dés ». Et là, ben on est bien avancés. Le domaine de Y, c’est tous les nombres de 0 à n. Je peux réussir à trouver la probabilité d’avoir, par exemple, exactement 3 dés avec la valeur 6 sur mes n dés, et même une formule générale pour k dés, mais faire la somme de tout ça, ben j’ai un peu la flemme. Alors, je vais ruser.

Ya un truc super pratique qui s’appelle la linéarité de l’espérance qui dit que l’espérance de la somme de plusieurs variables est égale à la somme de l’espérance des variables en question. En plus compact :

E[A + B] = E[A] + E[B]

Ça, c’est vrai pour toutes les variables aléatoires A et B. Par contre, attention, c’est assez spécifique à l’addition en général. Par exemple, on ne peut pas, en général, dire que E[A \times B] = E[A] \times E[B] – c’est vrai, en particulier, si les variables aléatoires A et B sont indépendantes, mais ce n’est pas vrai en général. Fin de l’aparté.

Et donc, la ruse, là, c’est de définir n variables, qu’on va appeler Y_1, Y_2, ..., Y_n, et on va se débrouiller pour que la variable Y soit la somme de toutes ces variables. Et pour ça, on définit chaque variable Y_1 comme suit : elle a pour domaine {0,1} (c’est-à-dire qu’elle ne peut prendre que la valeur 0 ou 1), et elle a la valeur 1 exactement lorsque le dé numéro 1 a la valeur 6. On définit les valeurs suivantes de la même manière. Puisque j’ai n variables, et qu’elles ont la valeur 1 quand le dé qui leur correspond vaut 6, je peux écrire que

Y = \sum_{i = 1}^{n} Y_i

Et, par linéarité de l’espérance, du coup, j’ai

E[Y] = E[\sum_{i=1}^n Y_i] = \sum_{i=1}^n E[Y_i]

L’astuce, c’est que mes variables Y_i, elles sont vachement plus simples. Avec une probabilité 1/6, elles ont la valeur 1, et avec une probabilité 5/6, elles ont la valeur 0 (puisqu’avec une probabilité 1/6, le dé i a la valeur 6). Du coup, l’espérance de Y_i, elle est aussi vachement plus simple à calculer :

E[Y_i] = 1 \times \frac 1 6 + 0 \times \frac 5 6 = \frac 1 6

et ça, ben ça me donne directement l’espérance de Y :

E[Y] = \sum_{i=1}^n E[Y_i] = \sum_{i=1}^n \frac 1 6 = \frac 1 6 n

comme intuité au départ. Fou, non ?

Bon, évidemment, mes exemples là sont plutôt simples. Mais on peut utiliser le même genre d’outils dans des cas beaucoup plus compliqués. Et il existe tout un tas d’autres outils qui permettent d’évaluer des choses autour de variables aléatoires, et d’avoir une assez bonne idée de ce qui se passe, même quand on jette des dés. Il est probable que j’y revienne si/quand j’en aurai besoin, mais les bases sont là ! Des questions ? 🙂