Prediction algorithm runtimes

Kann man die Laufzeit von Algorithmen vorhersagen?

Ein Interview mit Katharina Brennig

Katharina Brennig befindet sich derzeit im 4. Semester ihres Masterstudiengangs MIS (Management Information Systems) an der Universität Paderborn und hat bereits einen Bachelorabschluss in International Business Studies. Sie ist seit 2018 Werkstudentin bei der OPTANO GmbH und hat sich zu einem unverzichtbaren Mitglied des OPTANO-Teams entwickelt. Unter anderem hat sie technische Dokumentationen für Kundenprojekte verfasst. Inspiriert durch ihre Arbeit bei OPTANO schrieb sie eine erfolgreiche Studienarbeit als Teil ihres Masterstudiums mit dem Titel „Vorhersage der Laufzeit von Optimierungsalgorithmen: Sind Computerlernverfahren geeignet, um die Laufzeit von Optimierungsalgorithmen vorherzusagen?“

Wir wollten mehr über Katharinas Arbeit erfahren und insbesondere herausfinden, inwieweit OPTANO von ihren Ergebnissen profitieren kann:

Katharina Brennig

Hallo Katharina! Vorab möchte ich dich fragen, woher du die Idee für das Thema deiner Studienarbeit hattest?

Nun, ich wollte an einem Projekt arbeiten, welches praxisorientiert ist; eines, von dem ich wusste, dass es dem Unternehmen einen Mehrwert bringen kann. Deshalb habe ich mich dazu entschieden, meine Studienarbeit in Zusammenarbeit mit OPTANO zu schreiben. Ich habe verschiedene Optionen mit meinem Mentor diskutiert. Letztendlich haben wir uns auf ein Thema geeinigt, das sich auf ein Projekt bezog, für das ich bereits die technische Dokumentation geschrieben hatte. Ich wollte auf jeden Fall etwas Neues machen. Ich wollte an einem Projekt arbeiten, von dem ich wusste, dass ich hierdurch einiges dazulernen kann und welches neue Erkenntnisse hervorbringt – in diesem Fall: herauszufinden, ob Computerlernverfahren dazu geeignet sind, die Laufzeit von Optimierungsalgorithmen vorherzusagen.

Warum ist es wichtig, die Laufzeit von Optimierungsalgorithmen vorhersagen zu können?

Wenn es darum geht, ein bestimmtes Problem zu lösen, weisen Algorithmen trotz identischer Instanzen und Datengröße oft extrem lange und unterschiedliche Laufzeiten auf. Aus diesem Grund ist es oft schwierig, die Dauer vorherzusagen, die ein Algorithmus zur Lösung eines Problems benötigt. Außerdem ist es nicht einfach, genau zu bestimmen, durch welche Faktoren die unterschiedlichen Laufzeiten verursacht werden. Daher kann es ein großer Vorteil sein, die Laufzeit eines Optimierungsalgorithmus vorherzusagen.

Und warum ist dies insbesondere für OPTANO von Bedeutung?

Zurzeit ist eine Laufzeitabschätzung für ein Optimierungsproblem im Allgemeinen, trotz aller durchgeführten Studien, nicht möglich. Dies gilt auch für die OPTANO Plattform. Deshalb ist es interessant, über die Implementierung eines Modells in die OPTANO Plattform nachzudenken, welches Informationen über die vorhergesagte Laufzeit eines Optimierungsjobs liefern kann. Auf diese Weise könnte der Benutzer entscheiden, ob eine Optimierung gestartet werden soll oder nicht. Darüber hinaus ist es für die Anwendung von Interesse, insbesondere wenn es darum geht, mehrere Optimierungsjobs auf mehrere Server zu verteilen. Die Möglichkeit, die Laufzeit vorherzusagen, kann beispielsweise auch die Frage beantworten, ob es notwendig ist, einen zweiten Server zu starten, damit eine Optimierung ausgeführt werden kann, oder ob es sich lohnt zu warten, bis der erste Server den Optimierungsjob abgeschlossen hat, um anschließend einen zweiten Optimierungsjob auf dem ersten Server auszuführen.

Um dieses Problem zu lösen, habe ich angefangen mich mit dem Thema des maschinellen Lernens zu beschäftigen und versucht herauszufinden, ob Computerlernverfahren dazu geeignet sind, die Laufzeit von Optimierungsalgorithmen vorherzusagen.

Kannst du uns mehr über maschinelles Lernen erzählen? Was genau ist es und wie funktioniert es im Allgemeinen?

 In den letzten Jahren hat sich das Konzept des maschinellen Lernens zu einer der beliebtesten Technologien im Bereich der künstlichen Intelligenz entwickelt. Das allgemeine Ziel besteht also darin, Wissen aus vorhandenen Datenbeständen und Beispielen abzuleiten, indem aus historischen Daten gelernt wird, um die Performance einer bestimmten Aufgabe zu verbessern. Das Ziel des maschinellen Lernens besteht also darin, Vorhersagen für neue Daten zu treffen, und nicht darin, Daten zu reproduzieren. Dabei werden Methoden des maschinellen Lernens entwickelt, um automatisch Strukturen in den Daten zu erkennen und unter Anwendung von statistischen Verfahren gleichartige Anwendungsfälle zu lösen.

In der Regel wird eine Reihe von Features als Input für das Modell verwendet. Diese Features beschreiben Merkmale und werden verwendet, um die Beziehung zwischen den Input Features und dem zugehörigen Output zu lernen.  Durch Training extrahiert der Algorithmus aus den Beziehungen der Features untereinander eine Struktur, die für die vorliegende Problemstellung nützlich ist. Nach Abschluss des Trainings können die neu erworbenen Informationen verallgemeinert und die gefundenen Muster auf neue Problemstellungen oder zur Vorhersage zukünftiger Daten ähnlichen Typs angewendet werden. In diesem Zusammenhang sollte erwähnt werden, dass es verschiedene Computerlernverfahren gibt, wie überwachte und unüberwachte Verfahren. Ich habe mich hierbei auf die Methoden des überwachten Lernens konzentriert, bei denen versucht wird, Ereignisse in der Zukunft auf der Grundlage von Erfahrungen aus der Vergangenheit vorherzusagen.

Did you know…?

  • Im Jahr 2018 sparte Netflix durch den Einsatz von Computerlernverfahren für personalisierte Empfehlungen von TV-Shows und Filmen für Abonnenten $1 Milliarde ein.
  • PWC prognostiziert, dass bis zum Jahr 2030 etwa 38% aller Arbeitsplätze in den USA durch künstliche Intelligenz und Automatisierung ersetzt werden könnten.
  • Maschinelles Lernen spielt im alltäglichen Leben bereits jetzt eine große Rolle. Dies reicht vom Filtern von Spam-E-Mails und dem Empfehlen von Freunden in sozialen Netzwerken bis hin zum Empfehlen von personalisierten Fernsehsendungen und Filmen auf Plattformen wie Netflix.

Wie bist du mit deiner Studienarbeit weiter vorgegangen?

Ich habe mich an dem Konzept der sogenannten Empirical Performance Modelle orientiert, die eine zunehmend wichtige Rolle spielen, wenn es um die Vorhersage der Laufzeit von Algorithmen geht, und die bereits in anderen Studien, die sich mit diesem Problem befassen, evaluiert und verwendet wurden. Bei diesen Modellen handelt es sich um statistische Modelle, die die Leistung eines Algorithmus in Abhängigkeit von seinen Eingaben beschreiben. Sie geben Aufschluss darüber, welche Faktoren für die Leistung eines Algorithmus verantwortlich sind.

Das Verfahren dieser Modelle beginnt mit der Auswahl eines Algorithmus und endet mit dem Training einer Methode des maschinellen Lernens. Da der Optimierungsalgorithmus und das gegebene Projekt bereits ausgewählt waren, habe ich evaluiert, welche Features für die Erstellung von Vorhersagen wichtig sein könnten. Bei der Suche nach relevanten Features habe ich versucht, mich von bestehenden Studien abzugrenzen und Features zu evaluieren, die bereits vor Beginn der Optimierung bekannt waren, wie zum Beispiel die Eigenschaften der Daten, die zur Erstellung der Matrix für die Berechnung der optimalen Lösung verwendet werden. Nach der Auswahl der relevanten Features zog ich mehrere von ML.NET bereitgestellte Machine Learning Algorithmen in Betracht. Während des Trainings der verschiedenen Modelle habe ich auch Feature Selection Verfahren angewendet, um nicht informative Features zu eliminieren. Dies führte zu einer weiteren Verbesserung einiger Verfahren. Auf diese Weise habe ich mich auf die drei Verfahren konzentriert, dessen Performance am besten war, bis keine weitere Verbesserung mehr möglich war.

Haben die Ergebnisse deiner Studienarbeit neue Erkenntnisse/Ideen für OPTANO hervorgebracht?

Ja, sie führten zu neuen Erkenntnissen bei der Untersuchung der Laufzeitvorhersage von Optimierungsalgorithmen für OPTANO. Basierend auf dem Projekt und den Daten war es möglich, die Laufzeit des im Projekt verwendeten Optimierungsalgorithmus grob vorherzusagen.  Um ganz sicher zu sein, dass der Einsatz von Methoden des maschinellen Lernens ein geeigneter Ansatz für das Problem ist, habe ich Tests mit anderen, trivialeren Methoden durchgeführt. Dabei stellte ich jedoch fest, dass die Verwendung trivialer Methoden nicht ausreicht, um die Laufzeit eines Optimierungsalgorithmus adäquat vorherzusagen, und dass durch den Einsatz von Verfahren des maschinellen Lernens präzisere Vorhersagen möglich sind.

Wird deine Arbeit also für künftige OPTANO Projekte nützlich sein?

 Das an dieser Stelle erworbene Wissen kann in Zukunft auch auf andere OPTANO Projekte angewendet werden.  Da jedoch jedes Projekt individuell ist und unterschiedliche Einflussfaktoren hat, müssen die Features für andere Projekte neu spezifiziert und der Machine-Learning-Algorithmus neu trainiert werden. Man könnte also sagen, dass jedes Empirical Performance Modell für ein bestimmtes Problem spezifisch ist. Deshalb habe ich einen Leitfaden für andere Projekte erstellt, der adaptiert werden kann, um die Auswahl relevanter und nicht relevanter Features zu erleichtern. Es ist wichtig zu wissen, dass es ausreichend Daten vorhanden sein sollten, auf Basis derer der Maschinen-Learning-Algorithmus lernen kann.

Was hast Du persönlich von deiner Arbeit an dem Projekt mitgenommen, abgesehen natürlich von dem spezifischen Wissen über das Thema?

 Nun, ich stand vor einer großen Herausforderung, nämlich der, dass ich lernen musste, wie man programmiert, etwas, mit dem ich überhaupt nicht wirklich vertraut war. Zuerst war ich von all dem völlig überwältigt, aber es wurde viel einfacher, als ich mich erst einmal zurechtfand. Das hat meinem Selbstvertrauen definitiv einen großen Schwung gegeben, da ich jetzt weiß, dass ich eine Herausforderung allein bewältigen kann. Allerdings muss ich hinzufügen, dass das OPTANO Team immer da war, wenn ich Unterstützung brauchte. Und obwohl ich mich zuvor generell für das Thema Machine Learning interessierte, hätte ich nicht gedacht, dass es so spannend sein würde, wie es sich letztendlich herausstellte.

Katharina, vielen Dank für das Gespräch und viel Erfolg in deinem weiteren Masterstudium.

„Katharinas Studienarbeit ist sehr beeindruckend und hat sich bereits in unseren OPTANO Projekten bewährt. Projekte wie dieses bedeuten, dass OPTANO enger mit der Universität zusammenarbeiten kann, und sie unterstreichen unseren Wunsch, dass OPTANO bei Optimierungsfragen an vorderster Front mitwirkt. Dies ist übrigens tatsächlich das erste Mal, dass wir von Anfang an den Einsatz von Open Source für ein Projekt in Betracht gezogen haben. Außerdem wollten wir uns durch die Anwendung der MIT-Lizenz profilieren, die den Benutzern umfangreiche Rechte einräumt“

Jens Peter KempkesGeschäftsführer bei OPTANO

Autorin: Alisa Temme

Haben Sie Interesse am OPTANO Algorithm Tuner?
Dann lesen Sie unser Interview mit den Entwicklern des Tuners.

Auch interessant…