FunSearch: fare nuove scoperte nelle scienze matematiche utilizzando modelli linguistici di grandi dimensioni

 | Intelligenza-Artificiale

Ricerca

Pubblicato
Autori

Alhussein Fawzi e Bernardino Romera Paredes

Frammenti di codice e fasci di luce colorati

Cercando “funzioni” scritte nel codice del computer, FunSearch ha fatto le prime scoperte su problemi aperti nelle scienze matematiche utilizzando LLM

I Large Language Models (LLM) sono assistenti utili: eccellono nel combinare concetti e sanno leggere, scrivere e programmare per aiutare le persone a risolvere i problemi. Ma potrebbero scoprire conoscenze completamente nuove?

Poiché è stato dimostrato che gli LLM “allucinano” informazioni fattivamente errate, utilizzarli per fare scoperte verificabilmente corrette è una sfida. Ma cosa accadrebbe se potessimo sfruttare la creatività degli LLM identificando e sviluppando solo le loro idee migliori?

Oggi, nell’a articolo pubblicato su Naturepresentiamo FunSearch, un metodo per cercare nuove soluzioni in matematica e informatica. FunSearch funziona accoppiando un LLM pre-addestrato, il cui obiettivo è fornire soluzioni creative sotto forma di codice informatico, con un “valutatore” automatizzato, che protegge da allucinazioni e idee errate. Iterando avanti e indietro tra questi due componenti, le soluzioni iniziali “evolvono” in nuova conoscenza. Il sistema ricerca “funzioni” scritte in codice informatico; da qui il nome FunSearch.

Questo lavoro rappresenta la prima volta che viene fatta una nuova scoperta per affrontare problemi aperti in scienza o matematica utilizzando i LLM. FunSearch ha scoperto nuove soluzioni per il problema del cap set, un problema aperto di lunga data in matematica. Inoltre, per dimostrare l’utilità pratica di FunSearch, lo abbiamo utilizzato per scoprire algoritmi più efficaci per il problema del “bin-packing”, che ha applicazioni onnipresenti come rendere più efficienti i data center.

Il progresso scientifico si è sempre basato sulla capacità di condividere nuove conoscenze. Ciò che rende FunSearch uno strumento scientifico particolarmente potente è che produce programmi che rivelano Come le sue soluzioni sono costruite, piuttosto che semplicemente quali siano le soluzioni. Ci auguriamo che questo possa ispirare ulteriori approfondimenti negli scienziati che utilizzano FunSearch, guidando un circolo virtuoso di miglioramento e scoperta.

Guidare la scoperta attraverso l’evoluzione con modelli linguistici

FunSearch utilizza un metodo evolutivo basato sui LLM, che promuove e sviluppa le idee con il punteggio più alto. Queste idee sono espresse come programmi per computer, in modo che possano essere eseguite e valutate automaticamente. Innanzitutto, l’utente scrive una descrizione del problema sotto forma di codice. Questa descrizione comprende una procedura per valutare i programmi e un programma seed utilizzato per inizializzare un pool di programmi.

FunSearch è una procedura iterativa; ad ogni iterazione, il sistema seleziona alcuni programmi dal pool di programmi corrente, che vengono alimentati a un LLM. Il LLM si basa in modo creativo su questi e genera nuovi programmi, che vengono valutati automaticamente. I migliori vengono aggiunti nuovamente al pool di programmi esistenti, creando un ciclo di auto-miglioramento. FunSearch utilizza PaLM2 di Googlema è compatibile con altri LLM formati sul codice.

Il processo FunSearch. A LLM viene mostrata una selezione dei migliori programmi che ha generato finora (recuperati dal database dei programmi) e gli viene chiesto di generarne uno ancora migliore. I programmi proposti dal LLM vengono eseguiti e valutati automaticamente. I migliori programmi vengono aggiunti al database, per essere selezionati nei cicli successivi. L’utente può in qualsiasi momento recuperare i programmi con il punteggio più alto scoperti finora.

Scoprire nuove conoscenze matematiche e algoritmi in diversi ambiti è un compito notoriamente difficile e in gran parte al di là della potenza dei sistemi di intelligenza artificiale più avanzati. Per affrontare problemi così impegnativi con FunSearch, abbiamo introdotto più componenti chiave. Invece di partire da zero, iniziamo il processo evolutivo con una conoscenza comune del problema e lasciamo che FunSearch si concentri sulla ricerca delle idee più critiche per raggiungere nuove scoperte. Inoltre, il nostro processo evolutivo utilizza una strategia per migliorare la diversità delle idee al fine di evitare la stagnazione. Infine, eseguiamo il processo evolutivo in parallelo per migliorare l’efficienza del sistema.

Nuovi orizzonti in matematica

Affrontiamo innanzitutto il problema del set di tappiuna sfida aperta, che da decenni tormenta i matematici in molteplici aree di ricerca. Il famoso matematico Terence Tao una volta lo descrisse come suo domanda aperta preferita. Abbiamo collaborato con Jordan Ellenberg, professore di matematica all’Università del Wisconsin-Madison e autore di un importante passo avanti sul problema del cap set.

Il problema consiste nel trovare l’insieme più grande di punti (chiamato a set di tappi) in una griglia ad alta dimensione, dove non esistono tre punti su una linea. Questo problema è importante perché serve da modello per altri problemi di combinatoria estrema: lo studio di quanto grande o piccola potrebbe essere una raccolta di numeri, grafici o altri oggetti. Gli approcci basati sul calcolo della forza bruta a questo problema non funzionano: il numero di possibilità da considerare diventa rapidamente maggiore del numero di atomi nell’universo.

FunSearch ha generato soluzioni, sotto forma di programmi, che in alcuni contesti hanno scoperto i set di limiti più grandi mai trovati. Questo rappresenta il aumento maggiore nella dimensione dei cap set negli ultimi 20 anni. Inoltre, FunSearch ha sovraperformato i risolutori computazionali all’avanguardia, poiché questo problema si estende ben oltre le loro attuali capacità.

Figura interattiva che mostra l’evoluzione dal programma seed (in alto) a una nuova funzione con punteggio più alto (in basso). Ogni cerchio è un programma, con le sue dimensioni proporzionali al punteggio assegnatogli. Vengono mostrati solo gli antenati del programma in basso. La funzione corrispondente prodotta da FunSearch per ciascun nodo è mostrata a destra (vedi il programma completo che utilizza questa funzione nel documento).

Questi risultati dimostrano che la tecnica FunSearch può portarci oltre i risultati consolidati su problemi combinatori difficili, dove l’intuizione può essere difficile da costruire. Ci aspettiamo che questo approccio svolga un ruolo in nuove scoperte per problemi teorici simili in combinatoria, e in futuro potrebbe aprire nuove possibilità in campi come la teoria della comunicazione.

FunSearch favorisce programmi concisi e interpretabili dall’uomo

Sebbene la scoperta di nuove conoscenze matematiche sia di per sé significativa, l’approccio FunSearch offre un ulteriore vantaggio rispetto alle tradizionali tecniche di ricerca informatica. Questo perché FunSearch non è una scatola nera che genera semplicemente soluzioni ai problemi. Invece, genera programmi che descrivono Come si è arrivati ​​a quelle soluzioni. Questo approccio “mostra il tuo lavoro” è il modo in cui generalmente operano gli scienziati, con nuove scoperte o fenomeni spiegati attraverso il processo utilizzato per produrli.

FunSearch favorisce la ricerca di soluzioni rappresentate da programmi altamente compatti – soluzioni con una bassa complessità Kolmogorov†. I programmi brevi possono descrivere oggetti molto grandi, consentendo a FunSearch di adattarsi a problemi di grandi dimensioni come un ago in un pagliaio. Inoltre, ciò rende i risultati del programma di FunSearch più facili da comprendere per i ricercatori. Ellenberg ha dichiarato: “FunSearch offre un meccanismo completamente nuovo per lo sviluppo di strategie di attacco. Le soluzioni generate da FunSearch sono concettualmente molto più ricche di una semplice lista di numeri. Quando li studio, imparo qualcosa”.

Inoltre, questa interpretabilità dei programmi di FunSearch può fornire informazioni utili ai ricercatori. Utilizzando FunSearch abbiamo notato, ad esempio, intriganti simmetrie nel codice di alcuni dei suoi output ad alto punteggio. Questo ci ha fornito una nuova visione del problema e abbiamo utilizzato questa visione per perfezionare il problema introdotto in FunSearch, ottenendo soluzioni ancora migliori. Consideriamo questo un esempio di procedura collaborativa tra esseri umani e FunSearch in molti problemi di matematica.

A sinistra: l’ispezione del codice generato da FunSearch ha prodotto ulteriori informazioni utili (evidenziazioni aggiunte da noi). A destra: l’insieme grezzo “ammissibile” costruito utilizzando il programma (molto più breve) a sinistra.

Le soluzioni generate da FunSearch sono concettualmente molto più ricche di una semplice lista di numeri. Quando li studio, imparo qualcosa.

Jordan Ellenberg, collaboratore e professore di matematica all’Università del Wisconsin-Madison

Affrontare una sfida notoriamente difficile nel settore informatico

Incoraggiati dal nostro successo con il problema teorico del cap set, abbiamo deciso di esplorare la flessibilità di FunSearch applicandolo a un’importante sfida pratica nell’informatica. Il problema del “binpacking” riguarda come imballare articoli di diverse dimensioni nel minor numero di contenitori. È al centro di molti problemi del mondo reale, dal caricamento di contenitori con oggetti all’allocazione dei lavori di elaborazione nei data center per ridurre al minimo i costi.

Il problema del bin-packing online viene in genere affrontato utilizzando regole empiriche algoritmiche (euristiche) basate sull’esperienza umana. Ma trovare una serie di regole per ogni situazione specifica, con dimensioni, tempistiche o capacità diverse, può essere difficile. Nonostante sia molto diverso dal problema del cap set, impostare FunSearch per questo problema è stato semplice. FunSearch ha fornito un programma personalizzato automaticamente (adattandosi alle specifiche dei dati) che ha superato l’euristica stabilita, utilizzando meno contenitori per imballare lo stesso numero di articoli.

Esempio illustrativo di bin packaging utilizzando l’euristica esistente: l’euristica più adatta (a sinistra) e l’utilizzo di un’euristica scoperta da FunSearch (a destra).

Problemi combinatori difficili come l’imballaggio dei contenitori online possono essere affrontati utilizzando altri approcci AI, come le reti neurali e apprendimento per rinforzo. Anche tali approcci si sono rivelati efficaci, ma potrebbero anche richiedere risorse significative per essere implementati. FunSearch, d’altro canto, produce codice che può essere facilmente ispezionato e distribuito, il che significa che le sue soluzioni potrebbero essere potenzialmente inserite in una varietà di sistemi industriali del mondo reale per apportare rapidi vantaggi.

Scoperta guidata da LLM per la scienza e oltre

FunSearch dimostra che se ci si salvaguarda dalle allucinazioni dei LLM, la potenza di questi modelli può essere sfruttata non solo per produrre nuove scoperte matematiche, ma anche per rivelare soluzioni potenzialmente di impatto a importanti problemi del mondo reale.

Prevediamo che per molti problemi della scienza e dell’industria, di lunga data o nuovi, la generazione di algoritmi efficaci e su misura che utilizzano approcci guidati da LLM diventeranno una pratica comune.

In effetti, questo è solo l’inizio. FunSearch migliorerà come conseguenza naturale del progresso più ampio dei LLM e lavoreremo anche per ampliare le sue capacità per affrontare una serie di pressanti sfide scientifiche e ingegneristiche della società.

Fonte: deepmind.google

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *