Credito:CC0 Dominio Pubblico
E se un'ampia classe di algoritmi utilizzati oggi, dagli algoritmi che ci aiutano a evitare il traffico agli algoritmi che identificano nuove molecole di farmaci, funzionasse in modo esponenziale più veloce?
Gli scienziati informatici della Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS) hanno sviluppato un tipo completamente nuovo di algoritmo, uno che velocizza esponenzialmente il calcolo riducendo drasticamente il numero di passaggi paralleli necessari per raggiungere una soluzione.
I ricercatori presenteranno il loro nuovo approccio in due prossime conferenze:l'ACM Symposium on Theory of Computing (STOC), 25-29 giugno e Conferenza internazionale sull'apprendimento automatico (ICML), 10 -15 luglio.
Molti cosiddetti problemi di ottimizzazione, problemi che trovano la migliore soluzione tra tutte le possibili soluzioni, come mappare il percorso più veloce dal punto A al punto B, si basano su algoritmi sequenziali che non sono cambiati da quando sono stati descritti per la prima volta negli anni '70. Questi algoritmi risolvono un problema seguendo un processo sequenziale passo dopo passo. Il numero di passaggi è proporzionale alla dimensione dei dati. Ma questo ha portato a un collo di bottiglia computazionale, risultando in linee di domande e aree di ricerca che sono semplicemente troppo costose dal punto di vista computazionale da esplorare.
"Questi problemi di ottimizzazione hanno una proprietà di rendimenti decrescenti, "ha detto Yaron Singer, Assistant Professor di Informatica presso SEAS e autore senior della ricerca. "Mentre un algoritmo progredisce, il suo guadagno relativo da ogni passo diventa sempre più piccolo."
Singer e il suo collega hanno chiesto:e se, invece di fare centinaia o migliaia di piccoli passi per raggiungere una soluzione, un algoritmo potrebbe fare solo pochi passi?
"Questo algoritmo e questo approccio generale ci consentono di accelerare notevolmente il calcolo per una classe enormemente ampia di problemi in molti campi diversi, compresa la visione artificiale, recupero delle informazioni, analisi di rete, biologia computazionale, progettazione dell'asta, e molti altri, " ha detto Singer. "Ora possiamo eseguire calcoli in pochi secondi che in precedenza avrebbero richiesto settimane o mesi".
"Questo nuovo lavoro algoritmico, e l'analisi corrispondente, apre le porte a nuove strategie di parallelizzazione su larga scala che hanno accelerazioni molto maggiori di quanto sia mai stato possibile prima, " ha detto Jeff Bilmes, Professore presso il Dipartimento di Ingegneria Elettrica dell'Università di Washington, che non è stato coinvolto nella ricerca. "Queste capacità saranno, Per esempio, consentire lo sviluppo di processi di sintesi del mondo reale su una scala senza precedenti."
Tradizionalmente, gli algoritmi per i problemi di ottimizzazione restringono lo spazio di ricerca per la soluzione migliore un passo alla volta. In contrasto, questo nuovo algoritmo campiona una varietà di direzioni in parallelo. Sulla base di quel campione, l'algoritmo scarta le direzioni di basso valore dal suo spazio di ricerca e sceglie le direzioni più preziose per progredire verso una soluzione.
Prendi questo esempio di giocattolo:
Sei dell'umore giusto per guardare un film simile a The Avengers. Un algoritmo di raccomandazione tradizionale aggiungerebbe in sequenza un singolo film in ogni passaggio che ha attributi simili a quelli di The Avengers. In contrasto, il nuovo algoritmo campiona un gruppo di film in modo casuale, scartando quelli troppo dissimili da The Avengers. Ciò che resta è una serie di film diversi (dopotutto, non vuoi dieci film di Batman) ma simili a The Avengers. L'algoritmo continua ad aggiungere batch in ogni passaggio fino a quando non ha abbastanza film da consigliare.
Questo processo di campionamento adattivo è fondamentale per la capacità dell'algoritmo di prendere la decisione giusta in ogni fase.
"Gli algoritmi tradizionali per questa classe di problemi aggiungono avidamente dati alla soluzione considerando l'intero set di dati in ogni fase, " ha detto Eric Balkanski, studente laureato presso SEAS e coautore della ricerca. "La forza del nostro algoritmo è che oltre ad aggiungere dati, elimina inoltre selettivamente i dati che verranno ignorati nei passaggi futuri".
Negli esperimenti, Singer e Balkanski hanno dimostrato che il loro algoritmo poteva setacciare un set di dati che conteneva 1 milione di valutazioni da 6, 000 utenti su 4, 000 film e consiglia una raccolta personalizzata e diversificata di film per un singolo utente 20 volte più veloce rispetto allo stato dell'arte.
I ricercatori hanno anche testato l'algoritmo su un problema di invio di taxi, dove ci sono un certo numero di taxi e l'obiettivo è scegliere le migliori location per coprire il numero massimo di potenziali clienti. Utilizzando un set di dati di due milioni di viaggi in taxi dalla commissione taxi e limousine di New York City, l'algoritmo di campionamento adattivo ha trovato soluzioni 6 volte più velocemente.
"Questo divario aumenterebbe in modo ancora più significativo su applicazioni su larga scala, come il raggruppamento di dati biologici, aste di ricerca sponsorizzate, o analisi dei social media, " ha detto Balcani.
Certo, il potenziale dell'algoritmo si estende ben oltre i consigli sui film e le ottimizzazioni della spedizione dei taxi. Potrebbe essere applicato a:
Questo processo di apprendimento attivo è la chiave per la capacità dell'algoritmo di prendere la decisione giusta in ogni fase e risolve il problema dei rendimenti decrescenti.
"Questa ricerca è una vera svolta per l'ottimizzazione discreta su larga scala, " ha detto Andreas Krause, professore di informatica all'ETH di Zurigo, che non è stato coinvolto nella ricerca. "Una delle maggiori sfide nell'apprendimento automatico è trovare buoni, sottoinsiemi rappresentativi di dati da grandi raccolte di immagini o video per addestrare modelli di machine learning. Questa ricerca potrebbe identificare rapidamente quei sottoinsiemi e avere un impatto pratico sostanziale su questi problemi di riepilogo dei dati su larga scala".
Il modello Singer-Balkanski e le varianti dell'algoritmo sviluppati nel documento potrebbero essere utilizzati anche per valutare più rapidamente l'accuratezza di un modello di apprendimento automatico, disse Vahab Mirrokni, uno scienziato principale presso Google Research, che non è stato coinvolto nella ricerca.
"In alcuni casi, abbiamo un accesso black-box alla funzione di accuratezza del modello che richiede tempo per il calcolo, " disse Mirrokni. "Allo stesso tempo, l'accuratezza del modello di calcolo per molte impostazioni delle funzionalità può essere eseguita in parallelo. Questo framework di ottimizzazione adattiva è un ottimo modello per queste importanti impostazioni e le intuizioni delle tecniche algoritmiche sviluppate in questo framework possono avere un profondo impatto in questa importante area di ricerca sull'apprendimento automatico".
Singer e Balkanski stanno continuando a lavorare con i professionisti sull'implementazione dell'algoritmo.
