Gli scienziati informatici trovano i limiti di un algoritmo di ricerca chiave

Molti aspetti di la moderna ricerca applicata si basa su un algoritmo cruciale chiamato discesa del gradiente. Questa è una procedura generalmente utilizzata per trovare i valori più grandi o più piccoli di una particolare funzione matematica, un processo noto come ottimizzazione della funzione. Può essere utilizzato per calcolare qualsiasi cosa, dal modo più redditizio per fabbricare un prodotto al modo migliore per assegnare i turni ai lavoratori.

Eppure, nonostante questa utilità diffusa, i ricercatori non hanno mai compreso appieno con quali situazioni l’algoritmo fa più fatica. Ora, un nuovo lavoro lo spiega, stabilendo quella discesa del gradiente, in fondo, affronta un problema computazionale fondamentalmente difficile. Il nuovo risultato pone dei limiti al tipo di prestazioni che i ricercatori possono aspettarsi dalla tecnica in particolari applicazioni.

“C’è una sorta di durezza nel peggiore dei casi che vale la pena conoscere”, ha detto Paul Goldberg dell’Università di Oxford, coautore del lavoro insieme a John Fearnley e Rahul Savani dell’Università di Liverpool e Alexandros Hollender di Oxford. Il risultato ha ricevuto un Premio Miglior Carta a giugno all’annuale Simposio sulla teoria dell’informatica.

Puoi immaginare una funzione come un paesaggio, dove l’elevazione del terreno è uguale al valore della funzione (il “profitto”) in quel particolare punto. Discesa gradiente cerca il minimo locale della funzione cercando la direzione di salita più ripida in una data posizione e cercando in discesa lontano da essa. La pendenza del paesaggio è chiamata gradiente, da cui il nome discesa gradiente.

La discesa del gradiente è uno strumento essenziale della moderna ricerca applicata, ma ci sono molti problemi comuni per i quali non funziona bene. Ma prima di questa ricerca, non c’era una comprensione completa di cosa esattamente renda difficile la discesa del gradiente e quando: domande che un’altra area dell’informatica nota come teoria della complessità computazionale ha aiutato a rispondere.

“Molto del lavoro nella discesa del gradiente non riguardava la teoria della complessità”, ha detto Costis Daskalakis del Massachusetts Institute of Technology.

La complessità computazionale è lo studio delle risorse, spesso tempo di calcolo, necessarie per risolvere o verificare le soluzioni a diversi problemi di calcolo. I ricercatori ordinano i problemi in classi diverse, con tutti i problemi nella stessa classe che condividono alcune caratteristiche computazionali fondamentali.

Per fare un esempio, rilevante per il nuovo giornale, immagina una città dove ci sono più persone che case e tutti vivono in una casa. Ti viene data una rubrica con i nomi e gli indirizzi di tutti in città e ti viene chiesto di trovare due persone che vivono nella stessa casa. Sai che puoi trovare una risposta, perché ci sono più persone che case, ma potrebbe volerci un po’ di ricerca (soprattutto se non condividono un cognome).

Questa domanda appartiene a una classe di complessità chiamata TFNP, abbreviazione di “polinomio non deterministico della funzione totale”. È la raccolta di tutti i problemi computazionali che hanno la garanzia di avere soluzioni e le cui soluzioni possono essere verificate rapidamente per verificarne la correttezza. I ricercatori si sono concentrati sull’intersezione di due sottoinsiemi di problemi all’interno di TFNP.

Il primo sottoinsieme è chiamato PLS (ricerca locale polinomiale). Questa è una raccolta di problemi che implicano la ricerca del valore minimo o massimo di una funzione in una particolare regione. Questi problemi sono garantiti per avere risposte che possono essere trovate attraverso un ragionamento relativamente semplice.

Un problema che rientra nella categoria PLS è il compito di pianificare un percorso che permetta di visitare un certo numero fisso di città con la distanza di percorrenza più breve possibile dato che è possibile modificare il viaggio solo invertendo l’ordine di una qualsiasi coppia di città consecutive nel giro. È facile calcolare la lunghezza di qualsiasi percorso proposto e, con un limite ai modi in cui puoi modificare l’itinerario, è facile vedere quali modifiche accorciano il viaggio. Hai la garanzia di trovare alla fine un percorso che non puoi migliorare con una mossa accettabile, un minimo locale.

Il secondo sottoinsieme di problemi è PPAD (argomenti di parità polinomiale su grafi orientati). Questi problemi hanno soluzioni che emergono da un processo più complicato chiamato teorema del punto fisso di Brouwer. Il teorema dice che per ogni funzione continua, è garantito che ci sia un punto che la funzione lascia invariato, un punto fisso, come è noto. Questo è vero nella vita quotidiana. Se mescoli un bicchiere d’acqua, il teorema garantisce che deve esserci assolutamente una particella d’acqua che finirà nello stesso punto da cui è partita.

Lascia un commento

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