Neuer Algorithmus verkürzt die Rechenzeit um Größenordnungen

• Ein neuer Algorithmus beschleunigt die Berechnung exponentiell, indem er die Anzahl der zur Lösung eines Problems erforderlichen Iterationen drastisch verringert.
• Es ist weitaus leistungsfähiger als herkömmliche (sequentielle) Algorithmen bei großen Datensätzen, wie z. B. Social-Media-Analysen und Clustering genetischer Daten. 

Tausende von Optimierungsproblemen (Problem, aus allen möglichen Lösungen die beste Lösung zu finden), wie die Zuweisung von Mitteln zu Aktien, um das Risiko von Renditen zu minimieren, oder die Zuweisung von Mitarbeitern zu verfügbaren Büros, um den Arbeitsablauf und die Mitarbeiterstatistik zu maximieren, basieren stark auf sequentiellen Algorithmen.

Das grundlegende Arbeitsmuster dieser Algorithmen wurde seit ihrer Einführung in den frühen 1970er Jahren nicht verändert (verbessert). Sie lösen jedes bestimmte Problem nacheinander in „n“ Schritten.

Die Anzahl der Schritte hängt von der Größe des Problems ab (das dem Algorithmus bestimmte Werte als Eingabe liefert). Diese Art von Methode führt normalerweise zu einem rechnerischen Engpass. Der relative Gewinn aus jeder Iteration wird mit fortschreitendem Algorithmus immer kleiner.

Was wäre, wenn ein Algorithmus ein paar Sprünge machen könnte, anstatt Tausende kleiner Schritte zu unternehmen, um das Problem zu lösen? Was wäre, wenn wir dafür sorgen könnten, dass eine große Menge der heute weit verbreiteten Algorithmen exponentiell schneller arbeitet? Wir sprechen über die Algorithmen, die uns helfen, neue Medikamente zu entdecken und den Verkehr zu vermeiden.

Um dies zu ermöglichen, haben Forscher der Harvard University einen neuen Algorithmustyp entwickelt, den sie „Breakthrough“ nennen und der die Berechnung exponentiell beschleunigt, indem er die Anzahl der zur Lösung eines Problems erforderlichen Iterationen drastisch verringert.

Es beschleunigt die Berechnung einer Vielzahl von Problemen in verschiedenen Bereichen, z. B. Informationsextraktion, Auktionsdesign, maschinelles Sehen, Computerbiologie, Netzwerkanalyse und mehr.

Den Entwicklern zufolge ist es in der Lage, große Berechnungen in wenigen Sekunden durchzuführen, die früher Tage oder Wochen gedauert hätten. Dies könnte die Türen zu neuen groß angelegten Parallelisierungsansätzen öffnen und die Entwicklung praktischer Zusammenfassungsprozesse in außergewöhnlichem Maßstab ermöglichen.

Wie funktioniert es?

Sequentielle Algorithmen funktionieren, indem sie die Anzahl der möglichen Lösungen Schritt für Schritt eingrenzen. Der neue Algorithmus hingegen tastet parallel verschiedene Richtungen ab, eliminiert dann weniger relevante Richtungen und wählt die günstigsten (hochwertigen) Richtungen aus, um zur Lösung zu gelangen. Es verwirft selektiv Werte, die in zukünftigen Iterationen ignoriert werden.

Durchbruchsalgorithmus verwendet adaptives Sampling | Mit freundlicher Genehmigung von Forschern

Genauer gesagt erfordert der Algorithmus O (log n) aufeinanderfolgende Schritte und erreicht eine Annäherung, die beliebig nahe bei 1/3 liegt. Wenn die Parallelisierung aktiviert ist, erreichen die Algorithmen eine Näherung mit konstantem Faktor exponentiell schneller als jede bestehende Methode zur submodularen Maximierung.

Referenz:Harvard SEAS | Harvard Publications

Wenn die Aufgabe beispielsweise darin besteht, Filme zu empfehlen, die Star Wars ähneln, würde ein herkömmlicher Algorithmus bei jedem Schritt einen Film hinzufügen, der ähnliche Attribute (Action, Abenteuer, Fantasy) wie Star Wars aufweist.

Der neu entwickelte Algorithmus hingegen wählt zufällig eine Reihe von Filmen aus und schneidet diejenigen heraus, die überhaupt nicht zu Star Wars passen. Dies ergibt eine vielfältige Sammlung von Filmen (natürlich möchten Sie nicht, dass 10 Superman-Filme in Ihrer Empfehlung enthalten sind), die Star Wars ähneln.

Der Algorithmus fügt in jedem Schritt so lange verschiedene Filme hinzu, bis genügend Elemente zum Empfehlen vorhanden sind. Der Schlüssel, um bei jedem einzelnen Schritt wertvolle Entscheidungen zu treffen, liegt im adaptiven Sampling-Prozess.

Anzahl der Schritte, die ein sequenzieller (schwarz) und bahnbrechender (rot) Algorithmus zur Lösung eines Problems unternimmt

Tests und Anwendungen

Die Forscher testeten ihren adaptiven Sampling-Algorithmus anhand eines großen Datensatzes mit einer Million Bewertungen für 4.000 Filme von 6.000 Benutzern. Es empfahl erfolgreich personalisierte und vielfältige Filme für eine Person, und zwar 20-mal schneller als herkömmliche Algorithmen.

Sie wandten diesen Algorithmus auch auf ein Taxi-Versandproblem an – wählen Sie die besten Standorte aus, um die maximale Anzahl von Kunden mit begrenzten Taxis zu bedienen. Bei 2 Millionen Taxifahrten arbeitete der Algorithmus sechsmal schneller als der Stand der Technik.

Es kann bei großen Datensätzen, wie Social-Media-Analysen oder der Clusterung genetischer Daten, weitaus bessere Ergebnisse liefern.  Darüber hinaus könnte der Algorithmus für die Entwicklung klinischer Studien für mehrere Krankheiten, Sensorarrays für die medizinische Bildgebung und die Erkennung von Wechselwirkungen zwischen Medikamenten eingesetzt werden.

Lesen Sie:Der neue Algorithmus für selbstfahrende Fahrzeuge kann aggressiv die Spur wechseln

Heutzutage ist es zu einer herausfordernden Aufgabe geworden, aus Millionen von Bildern/Videos eine effektive Teilmenge von Daten zu finden, um Deep-Learning-Netzwerke zu trainieren. Diese Studie könnte dazu beitragen, wertvolle Teilmengen schnell zu extrahieren und erhebliche Auswirkungen auf Probleme bei der Datenzusammenfassung in großem Maßstab zu haben.