Le più grandi scoperte dell'informatica nel 2023 | Rivista Quanti

Nel 2023, l’intelligenza artificiale ha dominato la cultura popolare, apparendo ovunque, dai meme di Internet alle udienze al Senato. Grandi modelli linguistici come quelli dietro ChatGPT hanno alimentato molta di questa eccitazione, anche se i ricercatori faticavano ancora ad aprire la “scatola nera” che descrive il loro funzionamento interno. Anche i sistemi di generazione delle immagini ci impressionavano e turbavano abitualmente con le loro capacità artistiche, eppure su queste erano esplicitamente fondate concetti presi in prestito dalla fisica.

L'anno ha portato molti altri progressi nell'informatica. I ricercatori hanno compiuto progressi sottili ma importanti su uno dei problemi più antichi del settore, una domanda sulla natura dei problemi difficili denominata “P contro NP”. Ad agosto, il mio collega Ben Brubaker esplorato questo problema fondamentale e i tentativi dei teorici della complessità computazionale di rispondere alla domanda: perché è difficile (in senso quantitativo preciso) capire cosa rende difficili i problemi difficili? "Non è stato un viaggio facile: il percorso è disseminato di false svolte e blocchi stradali, e ritorna su se stesso ancora e ancora", ha scritto Brubaker. “Tuttavia, per i ricercatori della meta-complessità, quel viaggio in un paesaggio inesplorato è già una ricompensa”.

L'anno è stato ricco anche di progressi individuali più discreti ma pur sempre importanti. L’algoritmo di Shor, la killer app dell’informatica quantistica promessa da tempo, ha ottenuto il suo successo primo aggiornamento significativo dopo quasi 30 anni. I ricercatori hanno finalmente imparato come trovare il percorso più breve attraverso un tipo generale di rete quasi il più velocemente possibile teoricamente. E i crittografi, creando una connessione inaspettata con l’intelligenza artificiale, hanno mostrato come anche i modelli di machine learning e i contenuti generati dalle macchine debbano fare i conti con vulnerabilità e messaggi nascosti.

Alcuni problemi, a quanto pare, vanno ancora oltre la nostra capacità di risolverli, per ora.

Per 50 anni, gli informatici hanno cercato di risolvere la più grande questione aperta nel loro campo, nota come “P contro NP”. Chiede, più o meno, quanto siano difficili certi problemi difficili. E per 50 anni i loro tentativi si sono conclusi con un fallimento. Molte volte, proprio quando cominciavano a fare progressi con un nuovo approccio, si scontravano con un ostacolo che dimostrava che la tattica non avrebbe mai funzionato. Alla fine, hanno cominciato a chiedersi perché sia ​​così difficile dimostrare che alcuni problemi sono difficili. I loro sforzi per rispondere a queste domande interiori sono sbocciati in un sottocampo, chiamato meta-complessità, che ha fornito le più grandi intuizioni finora sulla questione.

In un agosto articolo e breve video documentario, Quanta ha spiegato esattamente cosa sappiamo, come lo sappiamo e cosa stiamo appena iniziando a capire quando si tratta di meta-complessità. In gioco non è solo la curiosità dei ricercatori coinvolti: risolvere P rispetto a NP potrebbe risolvere innumerevoli problemi logistici, rendere discutibile tutta la crittografia e persino svelare la natura ultima di ciò che è conoscibile e di ciò che è per sempre fuori dalla nostra portata.

Metti insieme abbastanza cose e potresti rimanere sorpreso da ciò che può accadere. Le molecole d'acqua creano onde, stormi di uccelli piombano e si librano in volo all'unisono e gli atomi inconsci si uniscono nella vita. Gli scienziati chiamano questi “comportamenti emergenti” e lo hanno fatto ho visto di recente la stessa cosa accadere con modelli linguistici di grandi dimensioni: programmi di intelligenza artificiale addestrati su enormi raccolte di testo per produrre una scrittura simile a quella umana. Dopo aver raggiunto una certa dimensione, questi modelli possono improvvisamente fare cose inaspettate che i modelli più piccoli non possono, ad esempio risolvere alcuni problemi di matematica.

Tuttavia, l’aumento dell’interesse per i grandi modelli linguistici ha sollevato nuove preoccupazioni. Questi programmi inventano falsità, perpetrare pregiudizi socialie non riuscire a gestire anche alcuni degli elementi più elementari del linguaggio umano. Inoltre, questi programmi rimangono una scatola nera, la cui logica interna è inconoscibile, sebbene alcuni ricercatori lo abbiano fatto idee su come cambiarlo.

Gli informatici conoscono da tempo algoritmi che possono sfrecciare attraverso i grafici – reti di nodi collegati da bordi – dove le connessioni hanno un certo costo, come una strada a pedaggio che collega due città. Ma per decenni non sono riusciti a trovare alcun algoritmo veloce per determinare il percorso più breve quando una strada poteva avere un costo o una ricompensa. Alla fine dell'anno scorso, un trio di ricercatori ha fornito un algoritmo funzionante è quasi il più veloce teoricamente possibile.

Poi, a marzo, i ricercatori hanno pubblicato un nuovo algoritmo che può determinare quando due tipi di oggetti matematici conosciuti come gruppi sono gli stessi in modo preciso; il lavoro potrebbe portare ad algoritmi in grado di confrontare rapidamente gruppi (e forse altri oggetti) più in generale, un compito sorprendentemente difficile. Un'altra grande novità dell'algoritmo quest'anno includeva un nuovo modo di calcolo dei numeri primi incorporando approcci casuali e deterministici, il confutazione di una vecchia congettura sulle prestazioni di algoritmi con informazioni limitate e un'analisi che mostra come può farlo un'idea non intuitiva migliorare le prestazioni di algoritmi di discesa del gradiente, che sono onnipresenti nei programmi di apprendimento automatico e in altre aree.

Quest'anno gli strumenti per la generazione di immagini come DALL·E 2 hanno registrato un'esplosione di popolarità. Basta dare loro un suggerimento scritto e sputeranno indietro un quadro artistico raffigurante tutto ciò che hai richiesto. Ma il lavoro che ha reso possibile la maggior parte di questi artisti artificiali è stato birra da molti anni. Basati su concetti fisici che descrivono la diffusione dei fluidi, questi cosiddetti modelli di diffusione imparano effettivamente come decodificare il rumore informe in un'immagine nitida, come se si riportasse indietro l'orologio su una tazza di caffè per vedere la crema uniformemente distribuita ricostituirsi in una crema ben distribuita. dose definita.

Anche gli strumenti di intelligenza artificiale hanno avuto successo migliorare la fedeltà delle immagini esistenti, anche se siamo ancora lontani dal cliché televisivo di un poliziotto che grida ripetutamente "Potenzia!" Più recentemente, i ricercatori si sono rivolti a processi fisici oltre alla diffusione esplorare nuovi modi in cui le macchine possono generare immagini. Un approccio più recente governato dall’equazione di Poisson, che descrive come le forze elettriche variano sulla distanza, si è già dimostrato più capace di gestire gli errori ed è più facile da addestrare rispetto ai modelli di diffusione, in alcuni casi.

Per decenni, l’algoritmo di Shor è stato l’esempio della potenza dei computer quantistici. Sviluppato da Peter Shor nel 1994, questo insieme di istruzioni consente a una macchina in grado di sfruttare le stranezze della fisica quantistica di scomporre grandi numeri nei loro fattori primi molto più velocemente di un normale computer classico, distruggendo potenzialmente gran parte dei sistemi di sicurezza di Internet. Ad agosto, informatico ha sviluppato una variazione ancora più veloce dell’algoritmo di Shor, il primo miglioramento significativo dalla sua invenzione. “Avrei pensato che qualsiasi algoritmo che avesse funzionato con questo schema di base sarebbe stato condannato”, ha detto Shor. "Ma mi sbagliavo."

Tuttavia, i computer quantistici pratici sono ancora fuori portata. Nella vita reale, piccoli errori possono sommarsi rapidamente, rovinando i calcoli e portando via qualsiasi vantaggio quantistico. Infatti, alla fine dell'anno scorso, un team di scienziati informatici ha mostrato che per un problema specifico, un algoritmo classico funziona più o meno altrettanto bene di uno quantistico che include errori. Ma c’è speranza: i lavori di agosto hanno dimostrato che alcuni codici di correzione degli errori, noti come codici di controllo della parità a bassa densità, sono almeno 10 volte più efficiente rispetto allo standard attuale.

In una scoperta insolita all'incrocio tra crittografia e intelligenza artificiale, un team di scienziati informatici ha dimostrato che era possibile inserire nei modelli di machine learning alcune backdoor praticamente invisibili, la cui non rilevabilità è supportata dalla stessa logica dei migliori metodi di crittografia moderni. I ricercatori si sono concentrati su modelli relativamente semplici, quindi non è chiaro se lo stesso valga per i modelli più complicati alla base di gran parte della tecnologia AI di oggi. Ma i risultati suggeriscono modi in cui i futuri sistemi possono proteggersi da tali vulnerabilità della sicurezza, segnalando anche un rinnovato interesse su come i due campi possono aiutarsi a vicenda a crescere.

Questi tipi di problemi di sicurezza sono parte del motivo Cinzia Rudin ha sostenuto l’utilizzo di modelli interpretabili per comprendere meglio cosa sta succedendo all’interno degli algoritmi di apprendimento automatico; piace ai ricercatori Yael Tauman Kalai, nel frattempo, hanno fatto avanzare le nostre nozioni di sicurezza e privacy, anche di fronte all’incombente tecnologia quantistica. E un risultato nel campo correlato della steganografia ha mostrato come nascondere un messaggio con perfetta sicurezza all'interno dei media generati dalla macchina.

Per quanto potente sia diventata l’intelligenza artificiale, le reti neurali artificiali che sono alla base della maggior parte dei sistemi moderni condividono due difetti: richiedono enormi risorse per addestrarsi e funzionare, ed è troppo facile per loro diventare scatole nere imperscrutabili. Molti ricercatori sostengono che forse è giunto il momento un altro approccio. Invece di utilizzare neuroni artificiali che rilevano tratti o caratteristiche individuali, i sistemi di intelligenza artificiale potrebbero rappresentare concetti con infinite variazioni di vettori iperdimensionali – matrici di migliaia di numeri. Questo sistema è più versatile e meglio attrezzato per gestire gli errori, rendendo i suoi calcoli molto più efficienti, e consente ai ricercatori di lavorare direttamente con le idee e le relazioni prese in considerazione da questi modelli, fornendo loro una visione più approfondita del ragionamento del modello. Il calcolo iperdimensionale è ancora agli inizi, ma man mano che verrà sottoposto a test più ampi, potremmo vedere il nuovo approccio iniziare a prendere piede.