Nieuw algoritme verkort de rekentijd met ordes van grootte

• Een nieuw algoritme versnelt de berekeningen exponentieel door het aantal iteraties dat nodig is om een probleem op te lossen drastisch te verminderen.
• Het presteert veel beter dan conventionele (sequentiële) algoritmen op grootschalige datasets, zoals analyse van sociale media en het clusteren van genetische gegevens. 

Duizenden optimalisatieproblemen (probleem van het vinden van de beste oplossing uit alle haalbare oplossingen), zoals het toewijzen van geld aan aandelen om het risico op rendement te minimaliseren, of het toewijzen van werknemers aan beschikbare kantoren om de workflow en werknemersstatisticus te maximaliseren, zijn sterk afhankelijk van sequentiële algoritmen.

Het basiswerkpatroon van deze algoritmen is niet gewijzigd (verbeterd) sinds ze begin jaren zeventig voor het eerst werden ingevoerd. Ze lossen elk specifiek probleem opeenvolgend op in “n” aantal stappen.

Het aantal stappen hangt af van de grootte van het probleem (dat bepaalde waarden aan het algoritme als invoer levert). Dit soort methoden resulteert meestal in een computationeel knelpunt. De relatieve winst van elke iteratie wordt steeds kleiner naarmate het algoritme vordert.

Wat als een algoritme een paar sprongen zou kunnen maken, in plaats van duizenden kleine stappen te nemen om het probleem op te lossen? Wat als we een groot aantal hedendaagse, veelgebruikte algoritmen exponentieel sneller zouden kunnen laten werken? We hebben het over de algoritmen die ons helpen nieuwe medicijnen te ontdekken en verkeer te vermijden.

Om dit mogelijk te maken hebben onderzoekers van de Harvard University een nieuw type algoritme bedacht, wat zij ‘Breakthrough’ noemen, dat de berekeningen exponentieel versnelt door het aantal iteraties dat nodig is om een probleem op te lossen drastisch te verminderen.

Het versnelt de berekening voor een breed scala aan problemen op verschillende gebieden, zoals informatie-extractie, veilingontwerp, machine vision, computationele biologie, netwerkanalyse en meer.

Volgens de ontwikkelaars is het in staat om binnen enkele seconden grote berekeningen uit te voeren die voorheen dagen of weken zouden duren. Dit zou de deuren kunnen openen voor nieuwe grootschalige parallellisatiebenaderingen, waardoor praktische samenvattingsprocessen op uitzonderlijke schaal kunnen worden gebouwd.

Hoe het werkt?

Opeenvolgende algoritmen werken door het aantal haalbare oplossingen stap voor stap te beperken. Terwijl het nieuwe algoritme parallel verschillende richtingen bemonstert, vervolgens minder relevante richtingen elimineert en de meest gunstige (hoogwaardige) richtingen selecteert om tot de oplossing te komen. Het verwijdert selectief waarden die in toekomstige iteraties zullen worden genegeerd.

Baanbrekend algoritme maakt gebruik van adaptieve bemonstering | Met dank aan onderzoekers

Meer specifiek vereist het algoritme O (log n) opeenvolgende stappen en bereikt het een benadering die willekeurig dicht bij 1/3 ligt. Wanneer parallellisatie wordt ingeschakeld, bereiken de algoritmen exponentieel sneller een benadering van constante factoren dan welke bestaande methode voor submodulaire maximalisatie dan ook.

Referentie:Harvard SEAS | Harvard-publicaties

Als het bijvoorbeeld de taak is om films aan te bevelen die vergelijkbaar zijn met Star Wars, zou een conventioneel algoritme bij elke stap één film toevoegen met vergelijkbare kenmerken (actie, avontuur, fantasie) als die van Star Wars.

Het nieuw ontwikkelde algoritme daarentegen bemonstert willekeurig een reeks films en verwijdert de films die helemaal niet overeenkomen met Star Wars. Dit levert een gevarieerde verzameling films op (uiteraard wil je geen 10 Superman-films in je aanbeveling) die vergelijkbaar zijn met Star Wars.

Het algoritme blijft bij elke stap verschillende films toevoegen totdat er voldoende items zijn om aan te bevelen. De sleutel om bij elke stap waardevolle beslissingen te nemen ligt in het adaptieve bemonsteringsproces.

Aantal stappen dat door een sequentieel (zwart) en baanbrekend (rood) algoritme is gezet om een probleem op te lossen

Testen en toepassingen

Onderzoekers testten hun adaptieve bemonsteringsalgoritme op een grote dataset met 1 miljoen beoordelingen voor 4.000 films van 6.000 gebruikers. Het heeft met succes gepersonaliseerde en gevarieerde films aanbevolen voor een persoon, 20 keer sneller dan conventionele algoritmen.

Ze hebben dit algoritme ook toegepast op een taxiprobleem:kies de beste locaties om het maximale aantal klanten te bedienen met een beperkt aantal taxi's. Voor 2 miljoen taxiritten werkte het algoritme 6 keer sneller dan de state-of-the-art.

Het kan veel betere resultaten opleveren op grootschalige datasets, zoals analyse van sociale media of het clusteren van genetische gegevens.  Daarnaast zou het algoritme kunnen worden toegepast voor het ontwikkelen van klinische onderzoeken voor meerdere ziekten, sensorarrays voor medische beeldvorming en het detecteren van interactie tussen medicijnen.

Lezen:Zoeken naar nieuw zelfrijdend voertuigalgoritme kan agressief van rijstrook veranderen

Tegenwoordig is het vinden van een effectieve subset van gegevens uit miljoenen afbeeldingen/video’s om deep learning-netwerken te trainen een uitdagende taak geworden. Dit onderzoek zou kunnen helpen om snel waardevolle subsets te extraheren en een aanzienlijke impact te hebben op grootschalige problemen bij het samenvatten van gegevens.