Wat als een grote klasse van algoritmen die tegenwoordig worden gebruikt - van de algoritmen die ons helpen verkeer te vermijden tot de algoritmen die nieuwe medicijnmoleculen identificeren - exponentieel sneller zou werken?

Computerwetenschappers van de Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS) hebben een volledig nieuw soort algoritme ontwikkeld, een die de berekening exponentieel versnelt door het aantal parallelle stappen dat nodig is om tot een oplossing te komen drastisch te verminderen.

De onderzoekers zullen hun nieuwe aanpak presenteren op twee aankomende conferenties:het ACM Symposium on Theory of Computing (STOC), 25-29 juni en Internationale Conferentie over Machine Learning (ICML), 10 -15 juli.

Veel zogenaamde optimalisatieproblemen, problemen die uit alle mogelijke oplossingen de beste oplossing vinden, zoals het in kaart brengen van de snelste route van punt A naar punt B, vertrouwen op sequentiële algoritmen die niet zijn veranderd sinds ze voor het eerst werden beschreven in de jaren zeventig. Deze algoritmen lossen een probleem op door een sequentieel stapsgewijs proces te volgen. Het aantal stappen is evenredig met de grootte van de gegevens. Maar dit heeft geleid tot een computationeel knelpunt, wat resulteert in vragen en onderzoeksgebieden die gewoon te rekenkundig duur zijn om te verkennen.

"Deze optimalisatieproblemen hebben een afnemende opbrengsteigenschap, " zei Yaron Singer, Universitair docent computerwetenschappen bij SEAS en senior auteur van het onderzoek. "Naarmate een algoritme vordert, de relatieve winst van elke stap wordt kleiner en kleiner."

Singer en zijn collega vroegen:wat als, in plaats van honderden of duizenden kleine stappen te nemen om tot een oplossing te komen, een algoritme maar een paar sprongen kan maken?

"Dit algoritme en deze algemene benadering stellen ons in staat om de berekening voor een enorm grote klasse van problemen op veel verschillende gebieden drastisch te versnellen, inclusief computervisie, informatie ophalen, netwerk analyse, computationele biologie, veiling ontwerp, en vele anderen, "zei Singer. "We kunnen nu berekeningen uitvoeren in slechts een paar seconden die voorheen weken of maanden in beslag zouden nemen."

"Dit nieuwe algoritmische werk, en de bijbehorende analyse, opent de deuren naar nieuwe grootschalige parallellisatiestrategieën met veel grotere versnellingen dan ooit tevoren, " zei Jeff Bilmes, Professor bij de afdeling Elektrotechniek aan de Universiteit van Washington, die niet bij het onderzoek betrokken was. "Deze vaardigheden zullen bijvoorbeeld, waardoor real-world samenvattingsprocessen op ongekende schaal kunnen worden ontwikkeld."

traditioneel, algoritmen voor optimalisatieproblemen verkleinen de zoekruimte voor de beste oplossing stap voor stap. In tegenstelling tot, dit nieuwe algoritme bemonstert parallel verschillende richtingen. Op basis van dat monster het algoritme negeert aanwijzingen met een lage waarde uit zijn zoekruimte en kiest de meest waardevolle richtingen om naar een oplossing te gaan.

Neem dit speelgoedvoorbeeld:

Je bent in de stemming om een ​​film te kijken die lijkt op The Avengers. Een traditioneel aanbevelingsalgoritme zou in elke stap achtereenvolgens een enkele film toevoegen die vergelijkbare kenmerken heeft als die van The Avengers. In tegenstelling tot, het nieuwe algoritme samplet willekeurig een groep films, het weggooien van degenen die te veel verschillen van The Avengers. Wat overblijft is een reeks films die divers zijn (per slot van rekening je wilt geen tien Batman-films) maar vergelijkbaar met The Avengers. Het algoritme blijft bij elke stap batches toevoegen totdat het genoeg films heeft om aan te bevelen.

Dit proces van adaptieve bemonstering is essentieel voor het vermogen van het algoritme om bij elke stap de juiste beslissing te nemen.

"Traditionele algoritmen voor deze klasse van problemen voegen gretig gegevens toe aan de oplossing, terwijl ze bij elke stap de volledige gegevensset in overweging nemen, " zei Eric Balkanski, afgestudeerde student bij SEAS en co-auteur van het onderzoek. “De kracht van ons algoritme is dat we naast het toevoegen van data, het snoeit ook selectief gegevens die in toekomstige stappen zullen worden genegeerd."

Bij experimenten, Singer en Balkanski toonden aan dat hun algoritme een dataset kon doorzoeken met 1 miljoen beoordelingen van 6, 000 gebruikers op 4, 000 films en beveelt een gepersonaliseerde en diverse verzameling films aan voor een individuele gebruiker, 20 keer sneller dan de allernieuwste.

De onderzoekers testten het algoritme ook op een taxidispatchprobleem, waar er een bepaald aantal taxi's is en het doel is om de beste locaties te kiezen om het maximale aantal potentiële klanten te dekken. Met behulp van een dataset van twee miljoen taxiritten van de taxi- en limousinecommissie in New York City, het adaptive-sampling-algoritme vond oplossingen 6 keer sneller.

"Deze kloof zou nog aanzienlijk toenemen bij toepassingen op grotere schaal, zoals het clusteren van biologische gegevens, gesponsorde zoekveilingen, of sociale media-analyse, ' zei Balkanski.

Natuurlijk, het potentieel van het algoritme gaat veel verder dan filmaanbevelingen en optimalisaties van taxiverzending. Het kan worden toegepast op:

• het ontwerpen van klinische proeven voor geneesmiddelen voor de behandeling van de ziekte van Alzheimer, multiple sclerose, zwaarlijvigheid, suikerziekte, hepatitis C, HIV en meer
• evolutionaire biologie om goede representatieve subsets van verschillende verzamelingen genen te vinden uit grote datasets van genen van verschillende soorten
• ontwerpen van sensorarrays voor medische beeldvorming
• detectie van interacties tussen geneesmiddelen via online gezondheidsforums

Dit proces van actief leren is essentieel voor het vermogen van het algoritme om bij elke stap de juiste beslissing te nemen en lost het probleem van afnemende meeropbrengsten op.

"Dit onderzoek is een echte doorbraak voor grootschalige discrete optimalisatie, " zei Andreas Krause, hoogleraar computerwetenschappen aan de ETH Zürich, die niet bij het onderzoek betrokken was. "Een van de grootste uitdagingen bij machine learning is het vinden van goede, representatieve subsets van gegevens uit grote verzamelingen afbeeldingen of video's om machine learning-modellen te trainen. Dit onderzoek zou die subsets snel kunnen identificeren en een substantiële praktische impact hebben op deze grootschalige problemen met het samenvatten van gegevens."

Het Singer-Balkanski-model en varianten van het in de paper ontwikkelde algoritme kunnen ook worden gebruikt om de nauwkeurigheid van een machine learning-model sneller te beoordelen, zei Vahab Mirrokni, een hoofdwetenschapper bij Google Research, die niet bij het onderzoek betrokken was.

"In sommige gevallen, we hebben een black-box toegang tot de modelnauwkeurigheidsfunctie die tijdrovend is om te berekenen, "zei Mirrokni. "Tegelijkertijd, rekenmodelnauwkeurigheid voor veel functie-instellingen kan parallel worden gedaan. Dit adaptieve optimalisatieraamwerk is een geweldig model voor deze belangrijke instellingen en de inzichten van de algoritmische technieken die in dit raamwerk zijn ontwikkeld, kunnen een grote impact hebben op dit belangrijke gebied van machine learning-onderzoek."

Singer en Balkanski blijven met praktijkmensen werken aan de implementatie van het algoritme.