1. Arbeitspapier: Was ist ein Algorithmus?
Dieses Arbeitspapier behandelt die Frage danach, was Algorithmen sind und inwieweit sie als neutral oder objektiv betrachtet werden können. Es streift auch die Frage danach, welche Arten von Fehlern auftreten können, wenn Fragen algorithmisch gelöst werden und basierend auf den berechneten Lösungen Entscheidungen getroffen werden – entweder automatisch oder durch Menschen.
Alle verlinkten Begriffe werden in der Begriffsklärung (kursiv fett gesetzte Worte) weiter unten erläutert. Das Arbeitspapier schließt mit dem Verweis auf weiterführende Literatur.
Was sind Algorithmen?
Algorithmen erlauben es, mathematische Probleme zu lösen. Wer auf dem Standpunkt steht, dass sie nicht mehr tun als genau dieses, der behauptet oft auch, dass Algorithmen an sich weder gut noch böse sind, sondern dass die Verantwortung für ihre Anwendung bei denen liegt, die sie verwenden. Oft sind Algorithmen aber direkt mit Aktuatoren verknüpft, die sie ansteuern – basierend auf dem Ergebnis ihrer Berechnung. So kann beispielsweise ein Auto die Bremsung einleiten, basierend auf Daten aus seinen Sensoren und den daraus resultierenden Berechnungen.
Hier wird in den deutschen Medien häufig vom Algorithmus als dem Handelnden in einer solchen Situation gesprochen. Die eigentlich Handelnden sind aber die Designer und Designerinnen des Algorithmus, die ihre Ideen für die Lösung des Problems genutzt haben. Ihre Handlungsanweisung wird potenziell millionenfach ausgeführt, ohne dass ihre physische Anwesenheit erforderlich ist und ohne die Begrenzung menschlicher Kapazitäten bezüglich Zeit, Gehirnleistung, Konzentration oder fehlerfreier Berechnungen. Es handelt sich also um eingefrorene Handlungsanweisungen, basierend auf den Ideen einiger Individuen, die unabhängig von Zeit und Raum millionen- oder gar milliardenfach ausgeführt werden. In vielen Fällen gibt es hier entsprechend eine Verantwortung der Designer und Designerinnen eines Algorithmus für dessen Handeln (s. Abbildung 1 zu den Verantwortlichkeiten).
Auf der anderen Seite werden – insbesondere im sogenannten Data Mining – Algorithmen von Anwendern ausgesucht, um eine spezifische Frage zu beantworten. Hier kommt den Designern und Implementierern eines Algorithmus nur die Verantwortung für das korrekte Design des Algorithmus und die korrekte Implementierung zu. Ein Algorithmus ist falsch designt, wenn er beispielsweise:
- das Problem nicht löst, sondern Lösungen berechnet, die der Spezifikation durch das mathematische Problem nicht entsprechen;
- der Algorithmus die Berechnung nicht beendet;
- für einige Eingaben das falsche Ergebnis produziert.
Eine Implementierung kann ebenso fehlerhaft sein und selbst dann, wenn sie auf einem an sich korrekten Algorithmus basieren, die eben genannten Fehlverhalten verursachen.
Die Entscheidung, dass eine bestimmte Frage durch ein bestimmtes mathematisches Problem zu lösen ist, ist ein Teil der Modellierung der Frage, um sie algorithmisch beantworten zu können. Die Modellierung beinhaltet auch die Entscheidung, wie eine Lösung am Ende bezüglich der gestellten Frage zu interpretieren ist (s. Abbildung 2). Aus den verschiedensten Gründen wird dabei nicht jedes Problem direkt als sein eigenes mathematisches Problem formuliert, sondern oft wird auf ein schon bekanntes und gelöstes Problem zurückgegriffen.
Gründe dafür können sein:
- Implementierte Algorithmen in bewährten Softwarepaketen sind meistens schon oft verwendet worden und daher kann man davon ausgehen, dass sie korrekt implementiert wurden.
- Auch wenn die Frage abstrahiert werden muss, um auf ein bekanntes, mathematisches Problem abgebildet werden zu können, kann es sein, dass eine stärker spezifische Modellierung gar nicht mehr lösbar wäre.
Bei der Formulierung als mathematisches Problem, insbesondere, wenn dieses nicht spezifisch für die Frage formuliert worden ist, müssen gewisse Modellierungsentscheidungen getroffen werden. Am Beispiel des Kürzesten-Wege-Problems muss zum Beispiel genau festgelegt werden, welche Art von Daten genutzt werden kann (aktuelle Verkehrsdichte, Kapazitäten der Straßen, Länge der Straßen, aktuelle Baustellen) und wie optimiert werden soll: denkbar ist die Minimierung der Gesamtlänge oder die Minimierung der erwarteten Fahrtzeit. Weitere Optimierungskriterien können sein: möglichst schöne Strecke, möglichst wenig Abbiegungen oder Vermeiden von Autobahnen etc.
Bei dieser Modellierungen können viele Fehler passieren, die am Ende eine sinnvolle Interpretation der Ergebnisse in Bezug auf die eigentlich gestellte Frage nicht zulassen. Da aber immer ein Wert berechnet wird – auch wenn die zugrundeliegende Modellierung inhaltlich falsch ist – kommt es hier zu einer scheinbaren Objektivität des berechneten Ergebnisses, solange man davon ausgehen kann, dass der Computer rein rechnerisch keinen Fehler macht. Bei Fragen, die eine starke Modellierungsleistung benötigen, um algorithmisch lösbar zu sein, kommen also viele subjektive Modellierungsentscheidungen dazu.
Auch in diesem Fall ist es immer noch richtig, dass der Computer ganz „objektiv“, ohne Ansehen der Person, seine Berechnung macht. Trotzdem ist das Ergebnis nur scheinbar objektiv oder neutral im landläufigen Sinne, da es die Interpretation des Ergebnisses definitiv nicht ist.
Eine besondere Klasse von Algorithmen sind „lernende Algorithmen“ aus dem Forschungsgebiet der künstlichen Intelligenz (Artificial Intelligence), die im Data Mining eingesetzt werden. Der Begriff des „lernenden“ Algorithmus ist irreführend, da der Algorithmus selbst sich nicht verändert. Er baut aber – basierend auf bekannten Daten – eine Entscheidungsstruktur auf. Da diese Entscheidungsstruktur von den ihr vorgelegten Daten beeinflusst wird, von ihnen „lernt“, spricht man oft von lernenden Algorithmen. Informatiker sprechen vom „Training“ eines Algorithmus. In einem zweiten Schritt werden dann neue, unbekannte Daten mit Hilfe der Entscheidungsstruktur klassifiziert und eine Entscheidung getroffen. Zu dieser Klasse gehören Bilderkennungsalgorithmen, die beispielsweise zuerst lernen, wie eine Schraube aussieht und dann in einem zweiten Schritt mit Hilfe des Gelernten in Form einer Entscheidungsstruktur Objekte in „Schraube“ und „Nicht-Schraube“ unterteilen.
Solche Algorithmen machen immer Fehler – wir unterscheiden zwei verschiedene Arten von Fehlentscheidungen durch Algorithmen:
- Sie erkennen Dinge als Schrauben, die keine sind; solche Fehlentscheidungen werden „falsch positiv“ genannte.
- Sie erkennen Schrauben nicht, die welche sind. Solche Fehlentscheidungen nennt man „falsch negativ“.
Oftmals kann in der Trainingsphase eingestellt werden, was wichtiger ist – der Algorithmus kann dann entweder sehr spezifisch sein, und Nicht-Schrauben nie als Schrauben kategorisieren, oder er ist sensitiv und findet alle Schrauben. Meistens wird aber die Anzahl der falsch positiven Entscheidungen höher, wenn die Anzahl der falsch negativen möglichst klein gehalten werden soll, und umgekehrt. Damit kann also nicht beides gleichzeitig optimiert werden. Sie gehören damit zur Klasse der Optimierungsalgorithmen, wobei sie Heuristiken sind, die auch Lösungen akzeptieren, die nicht optimal sind (100% korrekte Entscheidungen).
Auch die Entscheidung, ob ein Algorithmus lieber sensitiv oder spezifisch sein soll, ist subjektiv und wird oft von einem kleinen Team von Entwicklern entschieden, die meist keine Ausbildung in Psychologie, Wirtschaftswissenschaften, Politik, Soziologie oder Geschichte haben. Trotzdem entscheiden Algorithmen über so sensible Fragen wie die, ob jemand kreditwürdig ist, zum Bewerbungsgespräch aufgefordert wird oder die Frage nach der Wahrscheinlichkeit, dass jemand ein Terrorist ist.
Begriffsklärung (alphabetische Sortierung)
Algorithmus: Ein Algorithmus löst ein mathematisches Problem, d.h., er beschreibt einen für den Computer korrekt interpretierbaren Lösungsweg, der für jede durch das mathematische Problem definierte mögliche Eingabe die korrekte Lösung in endlicher Zeit berechnet. Warum in endlicher Zeit? Weil Lösungswege denkbar sind, bei denen man unendlich lange auf die Lösung warten muss. Dazu gehört der folgende Sortieralgorithmus: Bringe die Dinge in eine zufällige Reihenfolge und prüfe für jedes Paar von Dingen, die in der Reihenfolge direkt nebeneinander stehen, ob diese richtig herum stehen. Wenn dies der Fall ist, gib die Reihenfolge aus – diese ist sortiert. Da aber jedes Mal eine zufällige Reihenfolge gewählt wird, gibt es keine Garantie, dass jemals eine korrekte Lösung ausgegeben wird. Hier handelt es sich nicht um einen Algorithmus. Auch die berühmte Analogie zu einem Kochrezept funktioniert in den allermeisten Fällen nicht, da viele Begriffe benutzt werden, die in dieser Form nicht direkt von einem Computer interpretiert werden können, z.B. „Nudeln bissfest kochen“ oder „eine Prise Salz zugeben“. Diese Angaben müssten in eine Form gebracht werden, die für den Kochroboter sensorisch erfasst werden können (z.B. benötigter Druck um Nudel zu zerteilen) oder in genaue Mengen übersetzt werden(„1 g Salz“).
Aktuatoren: Geräte, die die digitale Entscheidung in die physische Welt übertragen und die dazugehörige Tat ausführen. Dazu gehören zum Beispiel die Bremssysteme eines fahrerlosen Wagens, aber auch der Auslöser einer Waffe in einer Drohne.
Data Mining: Als Data Mining bezeichnet man die Suche nach Mustern in meist großen Datenmengen. Oftmals wird das Muster selbst vorgegeben, z.B. wird nach zwei Ereignissen gesucht, die häufig miteinander auftreten. Ein berühmtes Beispiel ist die Entdeckung des US-Händlers Target, dass Schwangere oft Produkte kaufen, die in ihrer Häufung so ungewöhnlich sind, dass sie dadurch zu einem gewissen Prozentsatz identifizierbar sind.
Heuristik: Eine Heuristik versucht eine Lösung für ein Optimierungsproblem zu finden, ohne zu garantieren, dass es die optimale Lösung ist. Heuristiken werden dann verwendet, wenn es zwar grundsätzlich möglich ist, die optimale Lösung zu finden, dies aber zu lange dauern wird. Wir Menschen benutzen beispielsweise eine Heuristik, um die kürzeste Route von A nach B auf einer Landkarte zu finden: Wir suchen nach dem augenscheinlich kürzesten Weg zu einer Autobahn, dann nach dem augenscheinlich kürzesten Weg über die Autobahnen in die Nähe von B und dann nach dem augenscheinlich kürzesten Weg von der Autobahn zum Zielort. Das Verfahren garantiert keine kürzeste Route (weder in der Gesamtdistanz noch Gesamtfahrzeit), ist aber meistens auch nicht allzu weit davon entfernt.
Implementierung: Die Implementierung eines Algorithmus beschreibt die Übersetzung der Handlungsanweisungen in eine konkrete Programmiersprache, so dass der Computer nach Ausführen des dabei entstehenden Codes das zugehörige mathematische Problem für jede Eingabe lösen kann.
Kürzeste-Wege-Problem: Das „Kürzeste-Wege-Problem“ definiert als Eingabemenge zum Beispiel einen Straßenplan mit allen möglichen Verbindungen, einen Startpunkt und ein Ziel. Als Resultat gewünscht ist die kürzeste Route, basierend auf dem Straßenplan. Dabei muss konkret benannt sein, wie „kürzest“ zu interpretieren sei, z.B. basierend auf der Strecke oder basierend auf der erwarteten Ankunftszeit, mit oder ohne Berücksichtigung der aktuellen Verkehrslage.
Mathematisches Problem: Ein mathematisches „Problem“ definiert, welches gewünschte Resultat basierend auf den eingegebenen Daten berechnet werden soll. Dazu gibt das Problem auch an, für welche Art von Eingabedaten das zuverlässig berechnet werden können soll. Beispiele: das „Kürzeste-Wege-Problem“ oder das „Sortierproblem“. Oftmals werden die Eingabe und die gewünschte Ausgabe mit den einleitenden Worten Gegeben und Gesucht beschrieben. Wie man am untenstehenden Sortierproblem sehen kann, ist es möglich, dass verschiedene Ausgaben die gewünschte Eigenschaft haben. Außerdem kann ein und dasselbe Problem durch verschiedene Algorithmen gelöst werden, d.h. es wird genau dieselbe Lösung berechnet, wenn diese eindeutig bestimmt ist. Gibt es mehrere Lösungen, die die Anforderungen erfüllen, kann jeder Algorithmus eine andere davon berechnen.
Modellierung: Während viele mathematische Probleme sich so anhören, als seien sie direkte Abbilder der in der Realität zu beantwortenden Fragen, gibt es immer einen mehr oder weniger großen Modellierungsfreiraum – Beispiele dafür geben wir unter den Schlagworten Kürzeste-Wege-Problem und Sortier-Problem. Andere Fragen bieten deutlich mehr Spielraum bei der Auswahl des mathematischen Problems, das eigentlich zu lösen ist. Ein Beispiel hierfür ist die Frage nach der zentralen, wichtigsten Person in einer sozialen Struktur, z.B. einer Firma. Hier gibt es Dutzende von Ansätzen, die die Frage zum Beispiel danach beantworten, wieviele Untergebene jemand hat, wie sehr er oder sie die Kommunikation von anderen kontrollieren kann, oder wie zentral und wichtig seine direkten Bekannten sind. Jede dieser Interpretationen der Frage wird durch ein anderes mathematisches Problem repräsentiert.
Optimierungsproblem: Als wichtige Spezialklasse der mathematischen Probleme gibt es die Gruppe der Optimierungsprobleme. Diese bekommen eine Menge von Eingaben und definieren eine Menge von grundsätzlichen Lösungen. Auf dieser Menge definieren sie zusätzlich für jede mögliche Lösung eine Kostenfunktion (oder eine Gewinnfunktion). Gesucht wird dann nach der Lösung mit den geringsten Kosten (oder dem höchsten Gewinn). Das Kürzeste-Wege-Problem kann man als Optimierungsproblem repräsentieren, wenn man grundsätzlich alle Routen von Startpunkt zu Ziel als mögliche Lösungen definiert plus einer Kostenfunktion, die dann entweder der Gesamtlänge oder Gesamtfahrzeit entspricht.
Sortierproblem: Gegeben eine Menge von Dingen und eine Eigenschaft, so dass man für jedes Paar bestimmen kann, ob in einer nach der Eigenschaft sortierten Reihenfolge das eine vor dem anderen kommt oder umgekehrt, oder ob beide an derselben Stelle stehen sollte. Beispiel: Gegeben eine Menge von Büchern, die nach dem Nachnamen ihres Erstautoren sortiert werden sollen, kann man für je zwei Bücher bestimmen, welches vor dem anderem einsortiert werden muss. Stammen beide von Autoren mit demselben Nachnamen, dann ist bei dieser Variante egal, welche zuerst einsortiert wird – jede Lösung, die alle anderen Paare korrekt einsortiert, ist eine mögliche Ausgabe. Natürlich kann das Sortierproblem so variiert werden, dass bei gleichem Nachnamen noch nach dem Vornamen entschieden wird, und, wenn dieser auch gleich ist, nach dem Erstpublikationsjahr unterschieden werden soll.
Weiterführende Literatur
Christoph Drösser: Total berechenbar?: Wenn Algorithmen für uns entscheiden, Hanser Verlag, 2016
Drösser beschreibt einige grundlegende Algorithmen, z.B. Kürzeste-Wege-Algorithmen, Sortieralgorithmen, Verschlüsselungsalgorithmen und Matching-Algorithmen, die für eine ideale Paarung von Dingen nach angegebenen Kriterien sorgen. Link zum Buch beim Verlag
Sebastian Stiller: Planet der Algorithmen: Ein Reiseführer, Albrecht Knaus Verlag München, 2015
Stiller beschreibt noch allgemeiner als Drösser, was Algorithmen sind, führt Beispiele auf und führt dann etwas tiefer in die Informatik ein. Insbesondere geht er darauf ein, in welche Klassen Algorithmen einsortiert werden in Abhängigkeit davon, wie lange sie für die Lösung eines Problems brauchen. Link zum Buch beim Verlag