Nieuw algoritme vermindert berekeningstijd met orde van grootte

Een nieuw algoritme versnelt berekening exponentieel door het aantal benodigde iteraties om een probleem op te lossen drastisch te verminderen. Het presteert veel beter dan conventionele (sequentiele) algoritmen op grootschalige datasets, zoals social media-analyses en het clusteren van genetische data.

Het probleem met sequentiële algoritmes

Duizenden optimalisatieproblemen (problemen van het vinden van de beste oplossing uit alle haalbare oplossingen) – zoals fondsen toewijzen aan aandelen om risico op rendement te minimaliseren, of werknemers toewijzen aan beschikbare kantoren om werkstroom en werknemerstevredenheid te maximaliseren – zijn zwaar afhankelijk van sequentiële algoritmes.

Het basische werkpatroon van deze algoritmes is niet veranderd (verbeterd) sinds ze in de vroege jaren '70 voor het eerst werden ingesteld. Ze lossen elk specifiek probleem sequentieel 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). Deze methode leidt meestal tot een rekenkundige knelpunt. De relatieve winst per iteratie wordt steeds kleiner naarmate het algoritme vordert.

Wat als een algoritme een paar sprongen kan maken, in plaats van duizenden kleine stappen om het probleem op te lossen? Wat als we de vandaag wijd gebruikte algoritmes exponentieel sneller kunnen maken? We praten over algoritmes die ons helpen nieuwe geneesmiddelen te ontdekken en verkeersdrukte te vermijden.

Om dit mogelijk te maken, hebben onderzoekers van Harvard Universiteit een nieuw type algoritme bedacht, wat ze "Breakthrough" noemen, dat berekening exponentieel versnelt door het aantal benodigde iteraties drastisch te verminderen.

Het versnelt berekening voor een breed scala aan problemen over verschillende domeinen, zoals informatie-uitwinning, veilingontwerp, machinevisie, computationele biologie, netwerkanalyse, en meer.

Volgens de ontwikkelaars is het in staat om grote berekeningen in enkele seconden uit te voeren die eerder dagen of weken zouden hebben gekost. Dit kan de deuren openen voor nieuwe grootschalige paralleliseringsbenaderingen, waardoor praktische samenvattingsprocessen op uitzonderlijke schaal gebouwd kunnen worden.

Hoe het werkt

Sequentiële algoritmes werken door het aantal haalbare oplossingen stap voor stap in te perken. Waarbij het nieuwe algoritme parallel verschillende richtingen bemonstert, en dan minder relevante richtingen elimineert en de meest gunstige (hoog-gewardeerde) richtingen selecteert om de oplossing te bereiken. Het verwijdert selectief waarden die in toekomstige iteraties genegeerd zullen worden.

Het Breakthrough-algoritme gebruikt adaptieve bemonstering. Meer specifiek vereist het algoritme O(log n) sequentiële stappen en bereikt een benadering willekeurig dicht bij 1/3. Bij inschakeling van parallelisatie bereikt het algoritme een constante factor benadering exponentieel sneller dan elke bestaande methode voor submodulaire maximalisatie.

Bijvoorbeeld, als de taak is om films aan te bevelen die lijken op Star Wars, zou een conventioneel algoritme op elke stap één film toevoegen die vergelijkbare attributen (actie, avontuur, fantasie) heeft met Star Wars.

Het nieuwe algoritme bemonstert daarentegen willekeurig een set films, en snoeit degene die helemaal niet overeenkomen met Star Wars. Dit geeft een diverse collectie films (natuurlijk wil je geen 10 Superman-films in je aanbevelingen) die lijken op Star Wars.

Het algoritme blijft in elke stap een verscheidenheid aan films toevoegen tot het voldoende items heeft om aan te bevelen. De sleutel om waardevolle beslissingen te nemen op elke stap ligt in het adaptieve bemonsteringsproces.

Testen en toepassingen

Onderzoekers testten hun adaptieve-bemonsteringsalgoritme op een grote dataset met 1 miljoen beoordelingen van 4.000 films door 6.000 gebruikers. Het bevoelde succesvol gepersonaliseerde en diverse films voor een persoon 20 keer sneller dan conventionele algoritmes.

Ze pasten dit algoritme ook toe op een taxidispatch-probleem – de beste locaties kiezen om het maximum aantal klanten te bedienen met beperkte 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 social media-analyses of het clusteren van genetische data. Daarnaast kan het algoritme toegepast worden voor het ontwikkelen van klinische studies voor meerdere ziekten, sensorarrays voor medische imaging, en het detecteren van interacties tussen geneesmiddelen.

Tegenwoordig is het vinden van een effectieve subset van data uit miljoenen afbeeldingen/video's om diep leer-netwerken te trainen een uitdagende taak. Deze studie kan helpen waardevolle subsets snel te extraheren en een significante impact hebben op massale datasamenvattingsproblemen.