Neuer Algorithmus reduziert Berechnungszeit um Größenordnungen

Ein neuer Algorithmus beschleunigt Berechnungen exponentiell, indem er die Anzahl der Iterationen zur Problemlösung drastisch verringert. Er übertrifft konventionelle (sequenzielle) Algorithmen bei großen Datensätzen – wie Social-Media-Analytik und Clustering genetischer Daten – bei weitem.

Das Problem sequenzieller Algorithmen

Tausende Optimierungsprobleme – wie Kapitalallokation zur Risikominimierung oder Mitarbeiterzuweisung zur Workflow-Maximierung – basieren auf sequenziellen Algorithmen. Ihr Grundmuster hat sich seit den frühen 1970ern nicht verändert: Sie lösen Probleme sequenziell in "n" Schritten.

Die Schrittzahl hängt von der Problemgröße ab. Diese Methode führt oft zu rechnerischen Engpässen. Der relative Gewinn pro Iteration wird immer kleiner.

Was, wenn ein Algorithmus statt tausender kleiner Schritte wenige große Sprünge machen könnte? Was, wenn wir heutige Standardalgorithmen exponentiell schneller machen könnten? Algorithmen, die uns bei Medikamentenentwicklung und Verkehrsvermeidung helfen.

Forscher von Harvard haben einen neuen Algorithmus entwickelt – "Breakthrough" –, der Berechnungen exponentiell beschleunigt, indem er die benötigten Iterationen drastisch reduziert.

Er beschleunigt Berechnungen für diverse Probleme across verschiedenen Bereichen: Informationsextraktion, Auktionsdesign, Machine Vision, Computational Biology, Netzwerkanalyse und mehr.

Laut Entwicklern bewältigt er Großberechnungen in Sekunden, die zuvor Tage oder Wochen dauerten. Dies könnte neue großskalige Parallelisierungsansätze ermöglichen und praktische Zusammenfassungsprozesse in außergewöhnlichem Maßstab erlauben.

Funktionsweise

Sequenzielle Algorithmen verengen die Menge machbarer Lösungen Schritt für Schritt. Der neue Algorithmus sampelt parallel verschiedene Richtungen, eliminiert weniger relevante und wählt die günstigsten (hochwertigen) Richtungen zur Lösung. Er verwirft Werte, die in zukünftigen Iterationen ignoriert würden.

Der Breakthrough-Algorithmus nutzt adaptives Sampling. Er benötigt O(log n) sequenzielle Schritte und erreicht eine Annäherung beliebig nahe an 1/3. Bei Parallelisierung erreicht er eine konstante Faktor-Approximation exponentiell schneller als jede existierende Methode für submodulare Maximierung.

Beispiel: Bei Filmempfehlungen ähnlich zu "Star Wars" würde ein konventioneller Algorithmus pro Schritt einen Film mit ähnlichen Attributen (Action, Abenteuer, Fantasy) hinzufügen.

Der neue Algorithmus sampelt zufällig eine Filmmenge, entfernt völlig unpassende. Das ergibt eine diverse Sammlung (keine 10 Superman-Filme), die Star Wars ähnelt. Er fügt in jedem Schritt Vielfalt hinzu, bis genug Empfehlungen vorliegen. Der Schlüssel: adaptiver Sampling-Prozess.

Tests und Anwendungen

Getestet auf einem Datensatz mit 1 Million Bewertungen zu 4.000 Filmen von 6.000 Nutzern: 20-mal schnellere personalisierte, diverse Empfehlungen als konventionelle Algorithmen.

Angewandt auf Taxi-Dispatch-Problem – optimale Standorte für maximale Kundenbedienung mit begrenztem Taxibestand. Bei 2 Millionen Taxifahrten: 6-mal schneller als State-of-the-Art.

Der Algorithmus liefert weit bessere Ergebnisse bei großen Datensätzen: Social-Media-Analytik, Clustering genetischer Daten. Weitere Anwendungen: Klinische Studien für Mehrfacherkrankungen, Sensormatrizen für medizinische Bildgebung, Erkennung von Arzneimittelinteraktionen.

Heute ist das Extrahieren effektiver Datenteilmengen aus Millionen Bilder/Videos für Deep-Learning-Training eine Herausforderung. Diese Studie könnte wertvolle Teilmengen rascher extrahieren und massive Datenzusammenfassungsprobleme signifikant beeinflussen.