Human-Centered Algorithm Engineering

Das HumAlgo-Projekt setzt sich zum Ziel, eine völlig neuartige Herangehensweise an die Algorithmik, ein zentrales Forschungsgebiet der Informatik, zu entwickeln und zu etablieren. Unter Algorithmik versteht man das Teilgebiet in der theoretischen Informatik, das sich unter Verwendung formaler, mathematischer Methoden mit der Entwicklung und der Analyse von Algorithmen beschäftigt, wie sie letztlich im Kern aller Software aus unserer zunehmend digitalisierten Welt nicht mehr wegzudenken sind. Kritisch wurde in der Vergangenheit zunehmend gesehen, dass die Algorithmentheorie oft nur einen geringen Bezug zur Praxis hat. Um dem entgegenzuwirken ergänzt die Methodik des Algorithm Engineerings seit einiger Zeit sehr erfolgreich formalen Entwurf und Analyse von Algorithmen durch Implementierungsaspekte und experimentelle Evaluation. Nun lassen sich aber gerade komplexe Aufgaben, die man mittels Softwareunterstützung lösen möchte, oft nicht uneingeschränkt in eine formale, algorithmische Problemstellung überführen, die direkt im Sinne des Algorithm Engineering gelöst werden kann. Beispiele hierfür stammen aus den Bereichen der Visualisierung von Netzwerken oder Landkarten, in denen ästhetische und subjektive Kriterien die Qualität bestimmen und professionelle Grafikdesigner meist deutlich bessere Lösungen finden als herkömmliche Computerprogramme, denen menschliche Kreativität und übergeordnete kognitive Fähigkeiten fehlen. Speziell für solche Fragestellungen, bei denen Menschen an der Größe der Datenmengen scheitern und Computer an den zu eingeschränkten Modellen, soll nun in diesem Projekt die Methodik des Algorithm Engineering durch die Integration von menschlicher Expertise und Kreativität in algorithmische Lösungsprozesse ergänzt werden. Dadurch lassen sich, so die Hypothese, interaktive Mensch-Maschine-Algorithmen entwickeln, die zu effizienteren, qualitativ besseren und vom Anwender nachvollziehbareren Lösungen führen. Dazu werden zusätzlich zur formalen Problemmodellierung auch Anforderungen und Bedürfnisse der Anwender von Beginn an im Algorithmenentwurf berücksichtigt und die entwickelten Algorithmen und Lösungen gemeinsam mit Domänenexperten evaluiert und mit vollautomatischen sowie manuellen Lösungen verglichen. Ziel ist es, anhand von ausgewählten Anwendungsbeispielen zu neuartigen, interaktiven Lösungsverfahren zu gelangen, die die Rechenkraft von Computern und die formale Arbeitsweise von Algorithmen mit der Kreativität und Erfahrung von Menschen verbinden. Weiterhin sollen die so gewonnenen Erkenntnisse auch in die Entwicklung der theoretischen Grundlagen des sogenannten Human-centered Algorithm Engineering einfließen und dadurch eine neue Methodik für eine ganze Reihe von algorithmischen Fragestellungen etabliert werden, deren erfolgreiche Lösung nach einer Kombination von Mensch und Maschine verlangt.

Effiziente Algorithmen bilden die Grundlage eines weiten Spektrums an intelligenten Systemen und Softwareanwendungen in unserer modernen und digitalisierten Welt. Während vollständig automatisierte Systeme in vielen Anwendungen ausreichend sind, gibt es umgekehrt auch viele wichtige und relevante Fälle, in denen Menschen mit Computersystemen interagieren müssen oder sollten, um hochqualitative Lösungen zu finden, die möglichst gut eine spezifische Fragestellung erfüllen. Dies gilt insbesondere dann, wenn es kein eindeutiges und formal definierbares Optimierungsziel gibt, sondern nur eine diverse Sammlung von weichen Kriterien, die die Lösungsqualität in einer weniger exakten Art und Weise charakterisieren. Die letztendliche Auswahl der bestgeeignetsten Lösung liegt dann oft im menschlichen Ermessen und umfasst auch subjektive Präferenzen. Das FWF Einzelprojekt "Human-centered Algorithm Engineering" beschäftigte sich mit der Untersuchung algorithmischer Probleme mit eben solchen Eigenschaften. Das Projektteam hatte als Ziel, spezifische Algorithmen zur interaktiven, gemeinsamen Optimierung durch Mensch und Maschine zu entwickeln und zu implementieren. Die zentrale wissenschaftliche Herausforderung dabei war es, zu erforschen wie sich die mathematische Genauigkeit formaler Algorithmen und die hohe Rechenkraft moderner Hardware mit den kreativen Fähigkeiten des menschlichen Denkens möglichst effektiv und effizient verknüpfen lassen. Im Projekt fokussierten wir uns auf zwei wichtige Forschungsfelder, in denen wir dieses neue algorithmische Paradigma zur Anwendung bringen wollten: Netzwerkvisualisierung und algorithmische Kartografie. Beide Felder haben gemeinsam, dass sie visuelle, geometrische Repräsentationen komplexer Daten untersuchen, mit dem Ziel einerseits einer hohen Lesbarkeit und andererseits einer ästhetischen Darstellung. Beides sind Kriterien, die schwierig exakt zu quantifizieren sind und daher oft einem hohen Grad an subjektiver Einschätzung durch menschliche Experten unterliegen. In den verschiedenen Forschungsergebnissen aus diesem Projekt untersuchten wir interaktive Algorithmen sowohl aus einer theoretischen Perspektive, als auch aus einer praktisch motivierten Perspektive im Sinne des Algorithm Engineering Konzepts. In den theoretischeren Betrachtungen erforschten wir beispielsweise verschiedene dynamische Optimierungsalgorithmen, die eine Lösung Schritt für Schritt durch immer genauer angegebene (hypothetische) Zusatzanforderungen der Nutzer:innen an deren Wunschvorstellungen anpassen und dabei insbesondere die visuelle Stabilität der Zwischenlösungen mitberücksichtigen. Diese Algorithmen sind dabei so entworfen, dass sie konsistente lokale Aktualisierungen der Lösungen berechnen und dabei deutlich weniger Rechenzeit benötigen, als wenn die Lösungen komplett neu berechnet werden müssten. In den praktischeren Betrachtungen implementierten wir eine ganze Reihe von verschiedenen interaktiven Algorithmen und untersuchten deren Leistungsfähigkeit sowohl durch quantitative Simulationsexperimente als auch in empirischen Nutzer:innenstudien. Die konkreten Anwendungsthemen reichten dabei von der Visualisierung biologischer Netzwerke zu semantischen Wortwolken in der Textvisualisierung und von der Beschriftung von Elementen in Landkarten hin zu abstrakten und schematischen Kartendarstellungen. Insgesamt führte das Projekt zu zwei erfolgreichen Dissertationen und 39 begutachteten Veröffentlichungen, die in internationalen wissenschaftlichen Zeitschriften und Konferenzen vorgestellt wurden.