L’intelligenza artificiale generativa può risolvere il più grande problema irrisolto dell’informatica?

La domanda: P=NP? - è una grande sfida teorica. Gli scienziati hanno adottato l'approccio delle idee sull'alimentazione con il cucchiaio su GPT-4 per cercare una risposta.

Gli informatici valutano se il tempo necessario per calcolare una soluzione sia fuori portata per i problemi più difficili. La questione P=NP? viene ora trattata come una sessione con prompt multipli con il modello linguistico GPT-4. L'intuizione più importante del lavoro potrebbe essere come eliminare le sessioni di chat passate per mantenere una discussione.

Quando gli informatici si ritrovano ai cocktail party, tendono a chiacchierare, tra le altre cose, del più importante problema irrisolto dell'informatica: la domanda P=NP?

Formulata quasi 50 anni fa, la questione se P sia uguale a NP è una profonda riflessione su ciò che alla fine si può ottenere con i computer. La domanda, che ha implicazioni per campi come la crittografia e l’informatica quantistica, non ha trovato una risposta convincente nonostante decenni di intensi studi. Ora, questo sforzo si è avvalso dell’aiuto dell’intelligenza artificiale generativa.

In un articolo intitolato "Large Language Model for Science: A Study on P vs. NP", l'autore principale Qingxiu Dong e colleghi programmano il modello linguistico di grandi dimensioni GPT-4 di OpenAI utilizzando quello che chiamano metodo socratico, diversi turni di chat tramite prompt con GPT -4. (Il documento è stato pubblicato questo mese sul server di prestampa arXiv da scienziati di Microsoft, Università di Pechino, Università Beihang di Pechino e Università di tecnologia e affari di Pechino.)

Il metodo del team consiste nel prendere argomentazioni da un articolo precedente e inserirle nel GPT-4 per ottenere risposte utili.

Dong e il team osservano che GPT-4 dimostra argomenti per concludere che P non è, in effetti, uguale a NP. E sostengono che il lavoro dimostra che i grandi modelli linguistici possono fare di più che sputare grandi quantità di testo, possono anche "scoprire nuove intuizioni" che possono portare a "scoperte scientifiche", una prospettiva che chiamano "LLM per la scienza".

Per comprendere cosa stanno facendo gli autori, è necessario conoscere un po' il problema P=NP.

Formulato in modo indipendente negli anni '70 dagli scienziati informatici Stephen Cook e Leonid Levin, il problema P contro NP - o "P=NP", come viene spesso definito - è una questione di quanto sia facile risolvere un dato problema. con un computer. La lettera P rappresenta problemi che si sono rivelati fattibili da risolvere, il che significa che il tempo per calcolare una soluzione non è fuori portata; e la cui soluzione è anche facile da verificare, cioè verificare che la risposta sia corretta.

Le lettere NP, al contrario, indicano problemi la cui risposta è anche relativamente facile da verificare, proprio come P, ma per i quali non esiste un modo semplice noto per calcolare una soluzione. È comune citare il gioco Sudoku come esempio di NP: qualsiasi gioco Sudoku compilato può essere controllato abbastanza facilmente per verificarne la precisione, ma il compito di trovare una soluzione cresce esponenzialmente in termini di tempo richiesto man mano che la griglia di gioco diventa più grande. (Se vuoi approfondire i dettagli teorici di P=NP, prova l'articolo di Cook del 2000 sul problema.)

Il problema, quindi, P=NP? si chiede se quei problemi che pensiamo siano difficili da risolvere, NP, ma che sappiamo essere facili da verificare, potrebbero effettivamente rivelarsi facilmente verificabili e facilmente risolvibili, proprio come i problemi P.

Una risposta negativa, cioè che P non è uguale a NP, significherebbe che alcuni problemi vanno oltre la capacità dei computer di risolverli anche con enormi budget informatici: in altre parole, un limite superiore all'informatica. Sfide come decifrare parte della crittografia sembrerebbero quindi più formidabili, oltre la portata dell'informatica.

Per affrontare P=NP, Dong e il team si basano su una tendenza degli ultimi anni di "ragionare" con ampi modelli linguistici. Come esemplificato nel lavoro del 2022 di Takeshi Kojima e del suo team presso l'Università di Tokyo e Google Research, è possibile migliorare la capacità di modelli linguistici di grandi dimensioni su determinati compiti semplicemente aggiungendo la frase "Pensiamo passo dopo passo" all'inizio del prompt, accompagnato da una risposta di esempio. Quella frase, hanno scoperto, era sufficiente per indurre passaggi di "catena di pensiero" da parte del modello linguistico.

È lo stesso tipo di procedura basata sulla catena di pensiero che Dong e il suo team stanno cercando con il loro Metodo Socratico. Attraverso 97 round di prompt, gli autori convincono GPT-4 con una varietà di richieste che entrano nel nocciolo della matematica di P=NP, anteponendo a ciascuno dei loro prompt un'affermazione principale per condizionare GPT-4, come ad esempio " Sei un saggio filosofo", "Sei un matematico esperto nella teoria della probabilità" - in altre parole, il gioco ormai familiare di far sì che GPT-4 svolga un ruolo, o "persona" per stilizzare la sua generazione di testo.

Esempio di uno dei round di chat della discussione altamente teorica.

La loro strategia è quella di indurre GPT-4 a dimostrare che P non, in effetti, è uguale a NP, assumendo prima che lo sia con un esempio e poi trovando un modo in cui l'esempio fallisce: un approccio noto come prova per contraddizione.

La cosa interessante è che due degli autori della ricerca, Ke Xu e Guangyan Zhou, questo mese hanno pubblicato separatamente un articolo in cui ragionano direttamente su P=NP in termini matematici formali tradizionali. In quell’articolo concludono che P non è uguale a NP.

Ciò che Dong, Xu, Zhou e il team stanno facendo, quindi, è come ricostruire il loro elaborato di matematica formale guidando GPT-4 attraverso il linguaggio del loro stesso ragionamento, suggerimento dopo suggerimento. Infatti, delle 73 pagine del documento, 67 pagine rappresentano la stampa completa di ciascuno dei 97 suggerimenti e la risposta completa di GPT-4. È come un gigantesco esercizio di ingegneria tempestiva per ricostruire una discussione.

È difficile dire se il risultato ottenuto da Dong e dal team con GPT-4 dimostri effettivamente che P non è uguale a NP perché lo stesso articolo di Xu e Zhou è molto nuovo. Sul sito Semantic Scholar, che raccoglie citazioni di articoli, non ci sono ancora citazioni per l'articolo, a parte il loro articolo con Dong e il suo team. Ci sono alcune discussioni sul documento GPT-4 da parte di vari lettori interessati sul sito AI HuggingFace a cui puoi dare un'occhiata.

Quindi, il mondo deve ancora accettare la loro argomentazione.

Ancora più importante per le persone a cui piace la Gen AI, gli autori sostengono che il loro dialogo nei suggerimenti mostra la prospettiva che modelli linguistici di grandi dimensioni facciano di più che limitarsi a imitare le creazioni testuali umane.

"La nostra indagine evidenzia la potenziale capacità di GPT-4 di collaborare con gli esseri umani nell'esplorazione di problemi eccezionalmente complessi e di livello esperto", scrivono. Nelle 67 pagine di suggerimenti e risposte, evidenziano i passaggi che ritengono "le parti più penetranti" di ciò che GPT-4 sputa.

Quanto siano penetranti queste risposte è probabilmente anche un argomento che necessita di un’indagine propria. Alcuni scienziati hanno scoperto che i modelli linguistici di grandi dimensioni sono particolarmente superficiali nel modo in cui mettono insieme citazioni e descrizioni.

Tuttavia, ai margini del documento emerge un interessante elemento rivelatore, in cui Dong e il team annotano le risposte di GPT-4 con le loro osservazioni sulla qualità delle risposte.

In una di queste note tra parentesi, gli autori scrivono che ciascuna delle risposte precedenti di GPT-4 è stata incorporata come sfondo nell'ultimo prompt - tranne dove gli autori hanno scelto di sfoltire le risposte per mantenere solo quelle più bit rilevanti.

"Se il modello prevede più soluzioni, includiamo solo la soluzione più preziosa nella cronologia delle conversazioni", scrivono a margine a pagina 7. "Questa strategia consente a GPT-4 di concentrarsi sulle informazioni pertinenti, migliorando così la sua efficienza ed efficacia complessiva ."

In altre parole, c'è stata una certa utile cura nel modo in cui GPT-4 ha utilizzato la storia passata in quella che viene chiamata la sua "finestra di contesto", tutti i round precedenti da cui può attingere. Dong e il team sono stati impegnati in un'ingegneria tempestiva molto selettiva per guidare GPT-4 attraverso il filo di una discussione. Ciò si ripercuote sulla pratica della "retrieval-augmented generation" o "RAG", l'attuale interesse nell'utilizzare i dati delle chat passate come nuovo input per un ampio modello linguistico.

Questo potrebbe essere uno dei contributi più significativi dell'intero esercizio: che risolva o meno P=NP, una nuova frontiera nel prompt engineering potrebbe avvicinare i programmi a RAG per dare alle sessioni di chat maggiore profondità . Quando ripensi solo di recente in tempo alle sessioni di chat, tendevano ad essere insensate, spesso vagando fuori tema.

Durante 97 round, Dong e il suo team sono riusciti a mantenere la macchina in posizione, e c'è qualcosa da dire al riguardo.