Tänk om en stor klass av algoritmer som används idag – från de algoritmer som hjälper oss att undvika trafik till de algoritmer som identifierar nya läkemedelsmolekyler – fungerade exponentiellt snabbare?

Datavetare vid Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS) har utvecklat en helt ny sorts algoritm, en som exponentiellt påskyndar beräkningen genom att dramatiskt minska antalet parallella steg som krävs för att nå en lösning.

Forskarna kommer att presentera sin nya metod vid två kommande konferenser:ACM Symposium on Theory of Computing (STOC), 25-29 juni och International Conference on Machine Learning (ICML), 10 -15 juli.

Många så kallade optimeringsproblem, problem som hittar den bästa lösningen av alla möjliga lösningar, som att kartlägga den snabbaste rutten från punkt A till punkt B, förlita sig på sekventiella algoritmer som inte har förändrats sedan de beskrevs första gången på 1970-talet. Dessa algoritmer löser ett problem genom att följa en sekventiell steg-för-steg-process. Antalet steg är proportionellt mot storleken på datan. Men detta har lett till en beräkningsflaskhals, resulterar i rader av frågor och forskningsområden som är alldeles för beräkningsmässigt dyra att utforska.

"Dessa optimeringsproblem har en minskande avkastningsegenskap, sa Yaron Singer, Biträdande professor i datavetenskap vid SEAS och senior författare till forskningen. "När en algoritm fortskrider, dess relativa vinst från varje steg blir mindre och mindre."

Singer och hans kollega frågade:tänk om, istället för att ta hundratals eller tusentals små steg för att nå en lösning, kan en algoritm bara ta några steg?

"Denna algoritm och allmänna tillvägagångssätt tillåter oss att dramatiskt påskynda beräkningen för en enormt stor klass av problem inom många olika områden, inklusive datorseende, informationsinhämtning, nätverksanalys, beräkningsbiologi, auktionsdesign, och många andra, " sa Singer. "Vi kan nu utföra beräkningar på bara några sekunder som tidigare skulle ha tagit veckor eller månader."

"Detta nya algoritmiska arbete, och motsvarande analys, öppnar dörrarna för nya storskaliga parallelliseringsstrategier som har mycket större hastigheter än vad som någonsin varit möjligt tidigare, sa Jeff Bilmes, Professor vid institutionen för elektroteknik vid University of Washington, som inte var involverad i forskningen. "Dessa förmågor kommer, till exempel, gör det möjligt för verkliga sammanfattningsprocesser att utvecklas i oöverträffad skala."

Traditionellt, Algoritmer för optimeringsproblem begränsar sökutrymmet för den bästa lösningen ett steg i taget. I kontrast, den här nya algoritmen samplar en mängd olika riktningar parallellt. Baserat på det provet, Algoritmen förkastar riktningar med lågt värde från sitt sökutrymme och väljer de mest värdefulla riktningarna för att gå vidare mot en lösning.

Ta det här leksaksexemplet:

Du är på humör att se en film som liknar The Avengers. En traditionell rekommendationsalgoritm skulle sekventiellt lägga till en enda film i varje steg som har liknande egenskaper som The Avengers. I kontrast, den nya algoritmen samplar en grupp filmer slumpmässigt, kasta bort de som är för olika The Avengers. Det som finns kvar är en mängd filmer som är olika (trots allt, du vill inte ha tio Batman-filmer) men liknar The Avengers. Algoritmen fortsätter att lägga till batcher i varje steg tills den har tillräckligt med filmer att rekommendera.

Denna process med adaptiv sampling är nyckeln till algoritmens förmåga att fatta rätt beslut i varje steg.

"Traditionella algoritmer för denna klass av problem lägger girigt till data till lösningen samtidigt som man tar hänsyn till hela datasetet vid varje steg, sa Eric Balkanski, doktorand vid SEAS och medförfattare till forskningen. "Styrkan med vår algoritm är att förutom att lägga till data, den beskär också selektivt data som kommer att ignoreras i framtida steg."

I experiment, Singer och Balkanski visade att deras algoritm kunde sålla igenom en datamängd som innehöll 1 miljon betyg från 6, 000 användare på 4, 000 filmer och rekommenderar en personlig och mångsidig samling filmer för en enskild användare 20 gånger snabbare än den senaste.

Forskarna testade också algoritmen på ett taxitransportproblem, där det finns ett visst antal taxibilar och målet är att välja de bästa platserna för att täcka maximalt antal potentiella kunder. Med hjälp av en datauppsättning av två miljoner taxiresor från New York Citys taxi- och limousinekommission, den adaptiva samplingsalgoritmen hittade lösningar 6 gånger snabbare.

"Denna klyfta skulle öka ännu mer avsevärt i större applikationer, som klustring av biologiska data, sponsrade sökauktioner, eller analys av sociala medier, sa Balkanski.

Självklart, Algoritmens potential sträcker sig långt bortom filmrekommendationer och optimeringar av taxitransporter. Det kan appliceras på:

• designa kliniska prövningar för läkemedel för att behandla Alzheimers, multipel skleros, fetma, diabetes, hepatit C, HIV och mer
• evolutionär biologi för att hitta bra representativa delmängder av olika samlingar av gener från stora datamängder av gener från olika arter
• designa sensormatriser för medicinsk bildbehandling
• identifiera läkemedelsinteraktionsdetektering från hälsoforum online

Denna process av aktivt lärande är nyckeln till algoritmens förmåga att fatta rätt beslut i varje steg och löser problemet med minskande avkastning.

"Denna forskning är ett verkligt genombrott för storskalig diskret optimering, sa Andreas Krause, professor i datavetenskap vid ETH Zürich, som inte var involverad i forskningen. "En av de största utmaningarna inom maskininlärning är att hitta bra, representativa delmängder av data från stora samlingar av bilder eller videor för att träna maskininlärningsmodeller. Denna forskning skulle kunna identifiera dessa delmängder snabbt och ha en betydande praktisk inverkan på dessa storskaliga datasammanfattningsproblem."

Singer-Balkanski-modellen och varianter av algoritmen som utvecklats i tidningen skulle också kunna användas för att snabbare bedöma noggrannheten hos en maskininlärningsmodell, sa Vahab Mirrokni, en huvudforskare på Google Research, som inte var involverad i forskningen.

"I vissa fall, vi har en svart låda åtkomst till modellnoggrannhetsfunktionen som är tidskrävande att beräkna, sade Mirrokni. Samtidigt, beräkningsmodellens noggrannhet för många funktionsinställningar kan göras parallellt. Detta adaptiva optimeringsramverk är en utmärkt modell för dessa viktiga inställningar och insikterna från de algoritmiska teknikerna som utvecklats i detta ramverk kan ha djup inverkan på detta viktiga område av maskininlärningsforskning."

Singer och Balkanski fortsätter att arbeta med praktiker för att implementera algoritmen.