Artificial Intelligence Toolkit définit la forme de la prochaine génération de prouveurs automatiques de théorèmes, et avec elle la relation entre les mathématiques et les machines.
On raconte qu'en 1970 le mathématicien aujourd'hui décédé Paul Cohen , seul lauréat de la médaille Fields pour ses travaux sur la logique mathématique , a fait des prédictions sans fondement qui continuent encore comme un plaisir ou irriter les mathématiciens: "un jour remplacera les mathématiciens à l'avenir des ordinateurs ". Cohen, connu pour ses méthodes audacieuses de travail avec la théorie des ensembles, a prédit que toutes les mathématiques pourraient être automatisées, y compris l'écriture de preuves.
La preuve est un raisonnement logique étape par étape qui confirme la véracité d'une hypothèse ou d'une hypothèse mathématique. Après l'apparition d'une preuve, une hypothèse devient un théorème. Cela confirme à la fois l'exactitude de l'énoncé et explique pourquoi il est vrai. Mais la preuve est étrange. C'est abstrait et non lié à l'expérience matérielle. "Ils sont le résultat d'un contact insensé entre un monde fictif et non physique et des créatures issues de l'évolution biologique", a déclaré Simon Dedeo , scientifique cognitif de l'Université Carnegie Mellon, qui étudie la certitude mathématique à travers l'analyse des structures de preuves. "L'évolution ne nous a pas préparés à cela."
Les ordinateurs sont bons pour le calcul en masse, mais la preuve nécessite quelque chose de différent. Les hypothèses découlent d'un raisonnement inductif - une intuition particulière associée à un problème intéressant - et les preuves suivent généralement une logique déductive, étape par étape. Ils nécessitent souvent une pensée créative complexe ainsi que le travail acharné de combler les vides, et les machines ne peuvent pas gérer cette combinaison de compétences.
Les prouveurs de théorèmes informatisés se divisent en deux catégories. Les prouveurs de théorèmes automatisés (ATP) utilisent généralement des méthodes de force brute pour broyer d'énormes tas de nombres. Les prouveurs de théorèmes interactifs (ITP) servent d'assistants humains et sont capables de vérifier l'exactitude des arguments, ainsi que de rechercher des erreurs dans les preuves existantes. Cependant, même si vous combinez ces deux stratégies (comme le font des prouveurs plus modernes), un système de raisonnement automatique n'en émergera pas.
Le scientifique cognitif Simon Dedeo de l'Université Carnegie Mellon a aidé à démontrer que les humains et les machines créent des preuves mathématiques de la même manière.
De plus, ces outils sont très peu appréciés et la plupart des mathématiciens ne les utilisent ni ne les approuvent. «C'est un sujet controversé pour les mathématiciens», a déclaré Dedeo. "La plupart d'entre eux n'aiment pas l'idée."
L'un des problèmes difficiles à résoudre dans ce domaine est la question de savoir dans quelle mesure le processus de création de preuves peut être automatisé. Le système pourra-t-il générer une hypothèse intéressante et la prouver d'une manière compréhensible pour les gens? Un ensemble de percées récentes réalisées par des laboratoires du monde entier offrent des moyens d'intelligence artificielle (IA) pour répondre à cette question. Joseph Urban, de l'Institut tchèque d'informatique, de robotique et de cybernétique à Prague, explore diverses approches qui utilisent l'apprentissage automatique pour augmenter l'efficacité des prouveurs existants. En juillet, son groupea montré un ensemble d'hypothèses originales et de preuves créées et validées par des machines. En juin, un groupe de Google Research dirigé par Christian Szegedi a publié les résultats de tentatives visant à utiliser les forces des systèmes de traitement du langage naturel pour rendre les preuves informatiques plus similaires en structure et en explication à celles des humains.
Certains mathématiciens considèrent les prouveurs de théorèmes comme des outils qui peuvent révolutionner la façon dont les élèves apprennent à écrire des preuves. D'autres disent qu'avoir des ordinateurs pour écrire des preuves pour les mathématiques avancées est inutile, voire impossible. Cependant, un système capable de prédire une hypothèse utile et de prouver un nouveau théorème peut réaliser quelque chose de nouveau - une sorte de version machine de la compréhension, a déclaré Szegedi. Et cela indique la possibilité d'un raisonnement automatique.
Machines utiles
Les mathématiciens, les logiciens et les philosophes débattent depuis longtemps de la part de la preuve humaine par nature, et le débat sur la mécanisation des mathématiques se poursuit aujourd'hui - en particulier là où l'informatique fusionne avec les mathématiques pures.
Pour les informaticiens, les prouveurs de théorèmes ne sont pas controversés. Ils fournissent un moyen clair de confirmer que le programme fonctionne, et les arguments sur l'intuition et la créativité sont moins importants que de trouver des moyens efficaces de résoudre les problèmes. Par exemple, Adam Chlipala , informaticien au Massachusetts Institute of Technology, a développé des outils de démonstration de théorèmes qui génèrentalgorithmes cryptographiques qui protègent les transactions sur Internet - malgré le fait que les gens proposent généralement de tels algorithmes. Son code de groupe est déjà utilisé dans la plupart des communications dans le navigateur Google Chrome.
Emily Riel de l'Université Johns Hopkins utilise des prouveurs de théorèmes pour former des étudiants et des assistants informatiques.
«Vous pouvez prendre n'importe quelle déclaration mathématique et la coder avec un seul outil, puis combiner tous les arguments et obtenir une preuve de sécurité», a déclaré Chlipala.
En mathématiques, les prouveurs de théorèmes ont aidé à produire des preuves complexes et intensives en calcul qui auraient autrement pris des milliers d'années-hommes mathématiques. Un exemple frappant est l'hypothèse de Keplerà propos de l'emballage le plus dense de balles dans l'espace tridimensionnel (historiquement, il s'agissait d'oranges ou de boulets de canon). En 1998, Thomas Hales et son élève, Sam Ferguson, ont complété cette preuve en utilisant une variété de techniques mathématiques informatisées. Le résultat était si lourd - la preuve a pris 3 Go - que 12 mathématiciens l'ont analysé pendant plusieurs années avant d'annoncer qu'ils étaient sûrs à 99% de sa véracité.
L'hypothèse de Kepler n'est pas le seul problème célèbre résolu par les machines. Avec le théorème des quatre couleurs, affirmant que quatre couleurs suffisent toujours pour peindre toute carte bidimensionnelle dans laquelle il n'y a pas deux zones contiguës de la même couleur, a été triée en 1977 à l'aide d'un programme informatique qui traitait des cartes en cinq couleurs, et a montré que toutes peuvent être transformées en quatre couleurs. En 2016, trois mathématiciens ont utilisé un programme informatique pour prouver le problème booléen de longue date des triplés de Pythagore , mais la première version de la preuve était de 200 To. Si vous disposez d'une connexion Internet suffisamment rapide, vous pouvez la télécharger en trois semaines.
Sentiments partagés
Ces exemples sont souvent présentés comme des réussites, mais ils ajoutent également leur propre saveur à la controverse. Le code informatique qui a prouvé le théorème des quatre couleurs il y a plus de 40 ans n'a pas pu être vérifié par les humains. «Les mathématiciens ont depuis débattu de la question de savoir si c'est une preuve ou non», a déclaré le mathématicien Michael Harris de l'Université de Columbia.
De nombreux mathématiciens, avec Michael Harris de l'Université de Columbia, remettent en question la nécessité de créer des prouveurs de théorèmes informatisés - et que ce dernier rendrait les mathématiciens inutiles.
Un autre mécontentement des mathématiciens est lié au fait que s'ils veulent utiliser des prouveurs de théorèmes, ils doivent d'abord apprendre à programmer, puis trouver comment exprimer leur problème dans un langage compréhensible par ordinateur - et tout cela les distrait des mathématiques. «Au moment où je reformulerai la question d'une manière adaptée à cette technologie, je résoudrai ce problème moi-même», a déclaré Harris.
Beaucoup de gens ne voient tout simplement pas la nécessité de résoudre des théorèmes. «Ils ont leur propre système, crayon et papier, et cela fonctionne», a déclaré Kevin Buzzard, mathématicien à l'Imperial College de Londres, qui a changé la direction de la recherche il y a trois ans, passant des mathématiques pures aux prouveurs de théorèmes et aux preuves formelles. «Les ordinateurs font des calculs étonnants pour nous, mais ils n'ont jamais résolu seuls un problème difficile», a-t-il déclaré. "Et tant que cela ne se produira pas, les mathématiciens ne l'achèteront pas."
Mais Buzzard et d'autres pensent qu'ils pourraient encore avoir besoin d'examiner de plus près la technologie. Par exemple, «les preuves informatiques peuvent ne pas être aussi étrangères que nous le pensons», a déclaré Dedeo. Récemment, avec Scott Viteri, informaticien à Stanford, il a procédé à la rétro-ingénierie de plusieurs preuves canoniques bien connues (y compris certaines de BeginningsEuclid) et des dizaines de preuves générées par un programme informatique pour prouver les théorèmes de Coq à la recherche de similitudes. Ils ont constaté que la structure de ramification des preuves de la machine était remarquablement similaire à celle des preuves fabriquées par l'homme. Cette propriété commune, a-t-il dit, pourrait aider les chercheurs à trouver un moyen faire les programmes d'aide expliquent.
« preuves de la machine peuvent ne pas être aussi énigmatiques qu'ils semblent, » Dedeo dit. d'
autres disent que le théorème expérimentateurs peuvent être des outils utiles pour l' enseignement à la fois en informatique et en mathématiques. Université Johns Hopkins mathématicien Emily Riela développé des cours dans lesquels les étudiants écrivent des preuves à l'aide de prouveurs de théorèmes. «Cela les rend très organisés et pensent clairement», dit-elle. "Les élèves qui rédigent une preuve pour la première fois peuvent ne pas comprendre immédiatement ce qui est attendu d'eux ou saisir la structure logique."
Riel dit également qu'il utilise de plus en plus de prouveurs de théorèmes dans son travail ces derniers temps. "Ils ne doivent pas être utilisés tout le temps, et ils ne remplaceront jamais les gribouillis sur un morceau de papier", a-t-elle dit, "mais l'utilisation d'assistants informatiques pour la preuve a changé ma compréhension de la façon d'écrire des preuves.
Les Provers de Théorème offrent également un moyen de garder les mathématiques équitables. En 1999, un mathématicien soviétique, russe et américainVladimir Alexandrovitch Voevodsky , a découvert une erreur dans l'une de ses preuves. Depuis lors jusqu'à sa mort en 2017, il a activement encouragé l'utilisation d'ordinateurs pour vérifier les preuves. Hales a déclaré que lui et Ferguson avaient trouvé des centaines d'erreurs dans leurs preuves originales en les testant avec des ordinateurs. Même les tout premiers théorèmes des éléments d'Euclide ne sont pas idéaux. Si une machine peut aider les mathématiciens à éviter de telles erreurs, pourquoi ne pas en profiter? Harris a émis une objection pratique à cette proposition, cependant, on ne sait pas dans quelle mesure est raisonnable: si les mathématiciens doivent passer du temps à formaliser les mathématiques pour qu'un ordinateur les comprenne, ils ne pourront pas consacrer ce temps à de nouvelles mathématiques.
Cependant, Timati Gowers, mathématicien et mathématicien lauréat du prix Cambridge Fields, veut aller encore plus loin: il envisage comment les prouveurs de théorèmes remplaceront à l'avenir les critiques humains dans les grandes revues. "Je vois comment cela peut devenir une pratique courante - si vous voulez que votre travail soit accepté, vous devez le faire passer par un réviseur automatisé."
Conversation avec des ordinateurs
Avant que les ordinateurs puissent tester ou développer des preuves, les chercheurs doivent d'abord surmonter un obstacle important: la barrière de communication entre les langues des humains et des ordinateurs.
Les prouveurs de théorèmes d'aujourd'hui ont été conçus sans tenir compte de la convivialité des mathématiciens. Le premier type, ATP, était couramment utilisé pour tester la véracité d'une déclaration, souvent en testant toutes les options possibles. Demandez à l'ATP s'il est possible de voyager de Miami à Seattle, et il passera probablement par toutes les villes auxquelles mènent les routes de Miami, et à la fin il trouvera une ville qui mène à Seattle.
Timati Gowers de l'Université de Cambridge pense que les prouveurs de théorèmes remplaceront un jour les critiques humains
En utilisant ATP, le programmeur peut coder toutes les règles, ou axiomes, puis se poser la question de savoir si une hypothèse particulière suit ces règles. Et puis l'ordinateur fait tout le travail. «Vous entrez simplement l'hypothèse que vous voulez prouver et espérez obtenir une réponse», a déclaré Daniel Huang, un informaticien qui a récemment quitté l'UC Berkeley pour démarrer une startup.
Mais il y a un problème: ATP n'explique pas son travail. Tous les calculs ont lieu à l'intérieur d'une machine et, pour une personne, ils ressemblent à une longue séquence de zéros et de uns. Huang a déclaré qu'il était impossible de regarder la preuve et de tester le raisonnement, car tout cela ressemble à un tas de données aléatoires. «Personne ne peut regarder de telles preuves et dire: tout est clair», a-t-il déclaré.
La deuxième catégorie, l'ITP, contient d'énormes ensembles de données contenant des dizaines de milliers de théorèmes et de preuves avec lesquels ils peuvent vérifier l'exactitude d'une preuve. Contrairement aux ATP, qui fonctionnent dans une boîte noire qui émet simplement des réponses, les ITP nécessitent une interaction et parfois une direction d'une personne, de sorte qu'ils ne sont pas si inaccessibles. «Une personne peut s'asseoir et déterminer quelles techniques sont utilisées pour prouver», a déclaré Huang. Ces preuves ont été étudiées par Dedeo et Viteri.
Ces dernières années, les ITP sont devenus de plus en plus populaires. En 2017, la trinité qui a prouvé le problème booléen des triplets de Pythagore a utilisé un ITP appelé Coq pour créer et tester une version formelle de leur preuve. En 2005, Georges Gontier de Microsoft Research Cambridge a utilisé Coq pour formaliser le théorème des quatre couleurs. Hales a également utilisé des ITP appelés HOL Light et Isabelle pour prouver formellement la conjecture de Kepler (HOL signifie logique d'ordre supérieur).
Aujourd'hui, l'avant-garde de ce domaine essaie de combiner l'apprentissage et le raisonnement. ATP est souvent combiné avec ITP pour intégrer l'apprentissage automatique afin d'améliorer les performances des deux techniques. Les experts estiment que les programmes ATP / ITP peuvent utiliser le raisonnement déductif et même échanger des idées mathématiques de la même manière que les humains, ou du moins d'une manière similaire.
Limites du raisonnement
Joseph Urban pense qu'une telle approche combinée peut marier le raisonnement déductif et inductif, qui est nécessaire pour obtenir des preuves. Son groupe a créé des prouveurs de théorèmes alimentés par l'apprentissage automatique, permettant aux ordinateurs d'apprendre par eux-mêmes. Au cours des dernières années, ils ont exploré la puissance des réseaux neuronaux - des couches d'unités de calcul qui aident les machines à traiter les informations d'une manière à peu près similaire au fonctionnement des neurones de notre cerveau. En juillet, leur groupe a rapporté de nouvelles hypothèses générées par un réseau de neurones formé à la démonstration de théorèmes.
En partie, Urban s'est inspiré du travail d'Andrei Karpaty, qui a formé il y a plusieurs années un réseau de neurones pour produire des absurdités mathématiques convaincantes pour les non-professionnels. Mais Urban n'avait pas besoin du non-sens - lui et le groupe ont développé leur propre outil de recherche de preuves, après s'être entraîné sur des millions de théorèmes. Ils ont utilisé le réseau pour générer de nouvelles hypothèses et tester leur validité avec un programme ATP appelé E.
Le réseau a publié plus de 50 000 nouvelles formules, bien que des dizaines de milliers d'entre elles aient été répétées. «Il semble que nous ne pouvons pas encore prouver des hypothèses plus intéressantes», a déclaré Urban.
Szegedi de Google Research voit le problème du raisonnement automatique dans les preuves informatiques comme faisant partie d'un domaine beaucoup plus large: le traitement du langage naturel, qui comprend la reconnaissance de modèles dans l'utilisation des mots et des phrases. La reconnaissance de formes est également une idée centrale de la vision par ordinateur, sur laquelle Szegedi a déjà travaillé chez Google. Comme d'autres groupes, son équipe souhaite créer des prouveurs de théorèmes capables de rechercher des preuves utiles et de les expliquer.
Inspiré par le développement rapide d'outils d'intelligence artificielle comme AlphaZero - le logiciel de DeepMind qui peut battre les humains aux échecs, au go et au shogi - le groupe Szegedi souhaite utiliser les dernières avancées en matière de reconnaissance linguistique pour enregistrer des preuves. Il a dit que les modèles de langage peuvent démontrer un raisonnement mathématique étonnamment précis.
Son groupe chez Google Research a récemment décrit un moyen d'utiliser des modèles de langage - que les réseaux de neurones utilisent souvent - pour générer de nouvelles preuves. Après avoir appris au modèle à reconnaître la structure arborescente des théorèmes éprouvés, ils ont lancé une expérience gratuite, demandant simplement aux réseaux de neurones de générer et de prouver des théorèmes sans supervision. Sur les milliers d'hypothèses générées, 13% se sont avérées prouvables et nouvelles (ne répétant pas les autres théorèmes de la base de données). Il a dit qu'une telle expérience dit que les réseaux de neurones peuvent apprendre, dans un certain sens, à comprendre à quoi ressemblent les preuves.
"Les réseaux de neurones sont capables de développer un semblant artificiel d'intuition", a déclaré Szegedi.
Bien sûr, il n'est toujours pas clair si ces tentatives réaliseront la prophétie de Cohen il y a 40 ans. Gowers a déclaré qu'il pensait que les ordinateurs pourraient dépasser les mathématiciens dans le raisonnement d'ici 2099. Au début, dit-il, les mathématiciens connaîtront un âge d'or, «lorsqu'ils font des choses intéressantes et que les ordinateurs sont ennuyeux. Mais je pense que ça ne durera pas longtemps. "
Après tout, si les machines continuent à se développer de plus en plus et ont accès à une énorme quantité de données, elles doivent apprendre à faire des choses très bien et intéressantes. «Ils apprendront à faire leurs propres demandes», a déclaré Gowers.
Harris n'est pas d'accord. Il ne pense pas que les preuves informatiques soient nécessaires, ou qu'elles finiront par "rendre les mathématiciens humains inutiles." "Même si les ordinateurs comprennent, ils ne comprendront pas au sens humain."