L’IA générative peut-elle résoudre le plus grand problème non résolu de l’informatique ?

La question : est-ce que P=NP ? -- est un grand défi théorique. Les scientifiques ont adopté l’approche de l’alimentation à la cuillère pour GPT-4 pour chercher une réponse.

Les informaticiens se demandent si le temps requis pour calculer une solution est hors de portée pour les problèmes les plus difficiles. La question est-ce que P=NP ? est désormais traité comme une session à plusieurs invites avec le modèle de langage GPT-4. Le plus grand aperçu du travail pourrait être de savoir comment élaguer les sessions de chat passées pour maintenir une discussion.

Lorsque les informaticiens se retrouvent à des cocktails, ils ont tendance à discuter, entre autres choses, du problème non résolu le plus important en informatique : la question : Est-ce que P=NP ?

Formulée il y a près de 50 ans, la question de savoir si P est égal à NP est une profonde méditation sur ce qui peut finalement être réalisé avec les ordinateurs. La question, qui a des implications dans des domaines tels que la cryptographie et l’informatique quantique, n’a pas trouvé de réponse convaincante malgré des décennies d’études intenses. Aujourd’hui, cet effort a fait appel à l’IA générative.

Dans un article intitulé "Large Language Model for Science : A Study on P vs. NP", l'auteur principal Qingxiu Dong et ses collègues programment le grand modèle de langage GPT-4 d'OpenAI en utilisant ce qu'ils appellent une méthode socratique, plusieurs tours de discussion via une invite avec GPT. -4. (L'article a été publié ce mois-ci sur le serveur de pré-impression arXiv par des scientifiques de Microsoft, de l'Université de Pékin, de l'Université Beihang de Pékin et de l'Université de technologie et de commerce de Pékin.)

La méthode de l'équipe consiste à prendre les arguments d'un article antérieur et à les transmettre à GPT-4 pour susciter des réponses utiles.

Dong et son équipe observent que GPT-4 démontre des arguments permettant de conclure que P n'est pas, en fait, égal à NP. Et ils affirment que le travail montre que les grands modèles de langage peuvent faire plus que restituer de grandes quantités de texte, ils peuvent également « découvrir de nouvelles idées » qui peuvent conduire à des « découvertes scientifiques », une perspective qu’ils baptisent « LLM pour la science ».

Pour comprendre ce que font les auteurs, il est nécessaire de connaître un peu le problème P=NP.

Formulé indépendamment dans les années 1970 par les informaticiens Stephen Cook et Leonid Levin, le problème P versus NP - ou « P=NP », comme on l'appelle souvent - consiste à déterminer dans quelle mesure il est facile de résoudre un problème donné. avec un ordinateur. La lettre P représente des problèmes dont la résolution s'est avérée réalisable, ce qui signifie que le temps nécessaire pour calculer une solution n'est pas hors de portée ; et dont la solution est également facile à vérifier, c'est-à-dire vérifier que la réponse est correcte.

Les lettres NP, en revanche, représentent des problèmes dont la réponse est également relativement facile à vérifier, tout comme P, mais pour lesquels il n'existe pas de moyen simple de calculer une solution. Il est courant de citer le jeu Sudoku comme exemple de NP : tout jeu de Sudoku rempli peut être assez facilement vérifié pour son exactitude, mais la tâche de trouver une solution augmente de façon exponentielle en termes de temps requis à mesure que la grille de jeu s'agrandit. (Si vous souhaitez plonger dans les détails théoriques lourds de P=NP, essayez l'article de Cook 2000 sur le problème.)

Le problème, alors, Est-ce que P=NP ? se demande si les problèmes que nous pensons difficiles à résoudre, NP, mais dont nous savons qu'ils sont faciles à vérifier, pourraient en réalité s'avérer à la fois faciles à vérifier et à résoudre, tout comme les problèmes P.

Une réponse négative, selon laquelle P n'est pas égal à NP, signifierait que certains problèmes sont au-delà de la capacité des ordinateurs à résoudre, même avec d'énormes budgets informatiques - une limite supérieure pour l'informatique, en d'autres termes. Les défis tels que le piratage de certains cryptages sembleraient alors plus redoutables, hors de portée de l'informatique.

Pour aborder P=NP, Dong et son équipe s'appuient sur une tendance des dernières années de « raisonnement » avec de grands modèles de langage. Comme l'illustre le travail de 2022 de Takeshi Kojima et de son équipe de l'Université de Tokyo et de Google Research, il est possible d'améliorer la capacité des grands modèles de langage sur certaines tâches en ajoutant simplement la phrase « Pensons étape par étape » au début du invite, accompagnée d’un exemple de réponse. Cette expression, ont-ils découvert, était suffisante pour induire des étapes de « chaîne de pensée » de la part du modèle linguistique.

Il s'agit du même type de procédure de chaîne de pensée que Dong et son équipe recherchent avec leur méthode socratique. À travers 97 séries d'invites, les auteurs amènent GPT-4 avec une variété de requêtes qui entrent dans le vif du sujet des mathématiques de P=NP, en faisant précéder chacune de leurs invites d'une déclaration principale pour conditionner GPT-4, telle que : " Vous êtes un sage philosophe », « Vous êtes un mathématicien doué en théorie des probabilités » - en d’autres termes, le jeu désormais familier consistant à faire jouer un rôle à GPT-4, ou à « persona » pour styliser sa génération de texte.

Échantillon d'un des tours de discussion de la discussion hautement théorique.

Leur stratégie est d'inciter GPT-4 à prouver que P n'est pas, en fait, égal à NP, en supposant d'abord que c'est le cas avec un exemple, puis en trouvant un moyen pour que l'exemple s'effondre -- un approche dite de la preuve par contradiction.

Ce qui est intéressant, c'est que deux des auteurs de la recherche, Ke Xu et Guangyan Zhou, ont publié séparément ce mois-ci un article dans lequel ils raisonnent directement sur P=NP en termes mathématiques formels traditionnels. Dans cet article, ils concluent que P n’est pas égal à NP.

Ce que font Dong, Xu, Zhou et leur équipe revient donc à reconstruire leur devoir de mathématiques formel en dirigeant GPT-4 à travers le langage de leur propre raisonnement, invite par invite. En fait, sur les 73 pages du document, 67 pages constituent une impression complète de chacune des 97 invites et la réponse complète de GPT-4. C'est comme un exercice géant d'ingénierie rapide pour reconstruire un argument.

Il est difficile de dire si le résultat obtenu par Dong et son équipe avec GPT-4 prouve réellement que P n'est pas égal à NP, car l'article de Xu et Zhou est lui-même très nouveau. Sur le site Semantic Scholar, qui rassemble les citations d'articles, il n'y a pas encore de citations pour l'article - autre que leur propre article avec Dong et son équipe. Il y a des discussions sur l'article GPT-4 par divers lecteurs intéressés sur le site d'IA HuggingFace que vous pouvez consulter.

Le monde n’a donc pas encore accepté leur argument.

Plus important encore, pour les personnes qui aiment la génération AI, les auteurs affirment que leurs dialogues dans les invites montrent la possibilité que de grands modèles de langage fassent plus que simplement imiter les créations textuelles humaines.

"Notre enquête met en évidence la capacité potentielle de GPT-4 à collaborer avec les humains pour explorer des problèmes exceptionnellement complexes et de niveau expert", écrivent-ils. Tout au long des 67 pages d'invites et de réponses, ils mettent en évidence des passages qu'ils considèrent comme « les parties perspicaces » de ce que GPT-4 crache.

La pertinence de ces réponses est probablement aussi un sujet qui nécessite sa propre enquête. Certains scientifiques ont trouvé que les grands modèles de langage étaient particulièrement superficiels dans la manière dont ils enchaînaient les citations et les descriptions.

Cependant, un élément révélateur intéressant apparaît dans les marges du document, où Dong et son équipe annotent les réponses du GPT-4 avec leurs observations sur la qualité des réponses.

Dans l'une de ces notes entre parenthèses, les auteurs écrivent que chacune des réponses précédentes de GPT-4 a été incorporée comme arrière-plan dans la dernière invite -- sauf où les auteurs ont choisi d'élaguer les réponses pour ne conserver que les plus bits pertinents.

"Si le modèle fournit plusieurs solutions, nous n'incluons que la solution la plus précieuse dans l'historique des conversations", écrivent-ils en marge de la page 7. "Cette stratégie permet à GPT-4 de se concentrer sur les informations pertinentes, améliorant ainsi son efficience et son efficacité globales. ".

En d’autres termes, il y a eu une certaine conservation utile de la façon dont GPT-4 a utilisé l’histoire passée dans ce qu’on appelle sa « fenêtre contextuelle », tous les cycles antérieurs sur lesquels il peut s’appuyer. Dong et son équipe se sont engagés dans une ingénierie d'invite très sélective pour guider GPT-4 à travers le fil d'un argument. Cela porte sur la pratique de la « génération augmentée par récupération » ou « RAG », l'intérêt actuel pour l'utilisation des données de discussion passées comme nouvelle entrée dans un grand modèle de langage.

C'est peut-être l'une des contributions les plus significatives de l'ensemble de l'exercice : qu'il résolve ou non P=NP, une nouvelle frontière dans l'ingénierie des invites pourrait rapprocher les programmes de RAG afin de donner plus de profondeur aux sessions de chat. . Quand on repense aux sessions de chat récentes, elles avaient tendance à être stupides, s'éloignant souvent du sujet.

Au cours des 97 rounds, Dong et son équipe ont réussi à maintenir la machine en bon état, et il y a quelque chose à dire à ce sujet.