Gennembrudsalgoritme eksponentielt hurtigere end nogen tidligere

Hvad hvis en stor klasse af algoritmer, der bruges i dag – fra de algoritmer, der hjælper os med at undgå trafik til de algoritmer, der identificerer nye lægemiddelmolekyler – virkede eksponentielt hurtigere?

Dataloger ved Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS) har udviklet en helt ny form for algoritme, en, der eksponentielt fremskynder beregningen ved dramatisk at reducere antallet af parallelle trin, der kræves for at nå en løsning.

Forskerne vil præsentere deres nye tilgang på to kommende konferencer:ACM Symposium on Theory of Computing (STOC), juni 25-29 og International Conference on Machine Learning (ICML), 10. -15. juli.

En masse såkaldte optimeringsproblemer, problemer, der finder den bedste løsning fra alle mulige løsninger, såsom at kortlægge den hurtigste rute fra punkt A til punkt B, stole på sekventielle algoritmer, der ikke har ændret sig, siden de først blev beskrevet i 1970'erne. Disse algoritmer løser et problem ved at følge en sekventiel trin-for-trin proces. Antallet af trin er proportionalt med størrelsen af ​​dataene. Men dette har ført til en beregningsmæssig flaskehals, resulterer i rækker af spørgsmål og forskningsområder, der bare er for beregningsmæssigt dyre at udforske.

"Disse optimeringsproblemer har en aftagende afkastegenskab, " sagde Yaron Singer, Adjunkt i datalogi ved SEAS og seniorforfatter af forskningen. "Som en algoritme skrider frem, dens relative gevinst fra hvert trin bliver mindre og mindre."

Singer og hans kollega spurgte:hvad nu hvis, i stedet for at tage hundredvis eller tusindvis af små skridt for at nå frem til en løsning, en algoritme kunne tage nogle få spring?

"Denne algoritme og generelle tilgang giver os mulighed for dramatisk at fremskynde beregningen af ​​en enormt stor klasse af problemer på tværs af mange forskellige felter, herunder computersyn, informationssøgning, netværksanalyse, beregningsbiologi, auktionsdesign, og mange andre, " sagde Singer. "Vi kan nu udføre beregninger på blot et par sekunder, som tidligere ville have taget uger eller måneder."

"Dette nye algoritmiske arbejde, og den tilsvarende analyse, åbner dørene til nye storstilede paralleliseringsstrategier, der har meget større speedups end hvad der nogensinde har været muligt før, " sagde Jeff Bilmes, Professor ved Institut for Elektroteknik ved University of Washington, som ikke var involveret i undersøgelsen. "Disse evner vil for eksempel, gør det muligt at udvikle opsummeringsprocesser i den virkelige verden i hidtil uset omfang."

Traditionelt, algoritmer til optimeringsproblemer indsnævrer søgerummet for den bedste løsning et trin ad gangen. I modsætning, denne nye algoritme sampler en række forskellige retninger parallelt. Baseret på denne prøve, Algoritmen kasserer retninger med lav værdi fra sit søgeområde og vælger de mest værdifulde retninger for at komme videre mod en løsning.

Tag dette legetøjseksempel:

Du er i humør til at se en film, der ligner The Avengers. En traditionel anbefalingsalgoritme ville sekventielt tilføje en enkelt film i hvert trin, som har lignende egenskaber som The Avengers. I modsætning, den nye algoritme prøver tilfældigt en gruppe film, kassere dem, der er for ulige med The Avengers. Tilbage er en masse film, der er forskellige (trods alt, du vil ikke have ti Batman-film), men ligner The Avengers. Algoritmen fortsætter med at tilføje batches i hvert trin, indtil den har nok film at anbefale.

Denne proces med adaptiv sampling er nøglen til algoritmens evne til at træffe den rigtige beslutning på hvert trin.

"Traditionelle algoritmer til denne problemklasse tilføjer grådigt data til løsningen, mens hele datasættet tages i betragtning ved hvert trin, " sagde Eric Balkanski, kandidatstuderende ved SEAS og medforfatter til forskningen. "Styrken ved vores algoritme er, at udover at tilføje data, det beskærer også selektivt data, der vil blive ignoreret i fremtidige trin."

I eksperimenter, Singer og Balkanski demonstrerede, at deres algoritme kunne gennemsøge et datasæt, som indeholdt 1 million vurderinger fra 6, 000 brugere på 4, 000 film og anbefale en personlig og forskelligartet samling af film til en individuel bruger 20 gange hurtigere end den nyeste.

Forskerne testede også algoritmen på et problem med taxaafsendelse, hvor der er et vist antal taxier, og målet er at vælge de bedste lokationer for at dække det maksimale antal potentielle kunder. Ved at bruge et datasæt på to millioner taxature fra New York City taxa- og limousinekommission, den adaptive-sampling-algoritme fandt løsninger 6 gange hurtigere.

"Denne kløft ville stige endnu mere markant ved større applikationer, såsom at klynge biologiske data, sponsorerede søgeauktioner, eller analyse af sociale medier, sagde Balkanski.

Selvfølgelig, algoritmens potentiale strækker sig langt ud over filmanbefalinger og optimeringer af taxaforsendelser. Det kan anvendes til:

• design af kliniske forsøg med lægemidler til behandling af Alzheimers, multipel sclerose, fedme, diabetes, hepatitis C, HIV og mere
• evolutionær biologi for at finde gode repræsentative delmængder af forskellige samlinger af gener fra store datasæt af gener fra forskellige arter
• design af sensorarrays til medicinsk billeddannelse
• identifikation af påvisning af interaktion mellem lægemidler fra online sundhedsfora

Denne proces med aktiv læring er nøglen til algoritmens evne til at træffe den rigtige beslutning på hvert trin og løser problemet med faldende afkast.

"Denne forskning er et reelt gennembrud for storskala diskret optimering, sagde Andreas Krause, professor i datalogi ved ETH Zürich, som ikke var involveret i undersøgelsen. "En af de største udfordringer i maskinlæring er at finde gode, repræsentative delmængder af data fra store samlinger af billeder eller videoer for at træne maskinlæringsmodeller. Denne forskning kunne identificere disse undergrupper hurtigt og have væsentlig praktisk indvirkning på disse store dataopsummeringsproblemer."

Singer-Balkanski-modellen og varianter af algoritmen udviklet i papiret kunne også bruges til hurtigere at vurdere nøjagtigheden af ​​en maskinlæringsmodel, sagde Vahab Mirrokni, en ledende videnskabsmand ved Google Research, som ikke var involveret i undersøgelsen.

"I nogle tilfælde, vi har en black-box-adgang til modelnøjagtighedsfunktionen, som er tidskrævende at beregne, " sagde Mirrokni. "På samme tid, beregningsmodellens nøjagtighed for mange funktionsindstillinger kan udføres parallelt. Denne adaptive optimeringsramme er en fantastisk model for disse vigtige indstillinger, og indsigten fra de algoritmiske teknikker, der er udviklet i denne ramme, kan have dyb indvirkning på dette vigtige område af maskinlæringsforskning."

Singer og Balkanski fortsætter med at arbejde med praktikere om implementering af algoritmen.