Kategorien
Uncategorized

Warum ich keine Angst vor KIs habe

Mir ist bewusst, dass ich mich mit diesem Beitrag auf ziemlich dünnes Eis begebe, denn bekanntlich kann man mit nichts so sehr daneben liegen wie mit dem Versuch, in die Zukunft zu schauen. Aber nachdem ich letzte Woche angemerkt habe, dass ich keine übermäßige Angst vor Künstlichen Intelligenzen habe, finde ich, dass ich dafür eine Erklärung schuldig bin. Diese Erklärung ist aber wirklich eher eine (hoffentlich nicht völlig unqualifizierte) persönliche Meinung als eine unumstößliche Wahrheit.

Zwei Arten von KIs

Zunächst einmal ist es wichtig zu verstehen, dass mit „Künstliche Intelligenz“ zwei sehr unterschiedliche Dinge bezeichnet werden. Das Klischee eines Computers, der einem Menschen kognitiv ebenbürtig oder sogar überlegen ist, wird als Starke KI bezeichnet. Solche KIs existieren derzeit noch nicht, und wie es aussieht, wird das auch noch eine Zeitlang so bleiben.

Relevanter für die Gegenwart ist die Schwache KI, mit der ein Verfahren bezeichnet wird, das nur ein eng begrenztes Problem lösen kann – beispielsweise Schach zu spielen, Gesichtsdaten auszuwerten oder ein Auto zu steuern. Im Unterschied zu einem klassischen Algorithmus muss die KI dabei selbständig lernen und in der Lage sein, mit Unsicherheiten umzugehen. Solche schwachen KIs haben in den vergangenen Jahren bedeutende Fortschritte erlebt, und wir sehen ihr Wirken an immer mehr Stellen im Alltag.

Starke KI (1): Energieverbrauch

Die meisten Informatiker kennen das Moore’sche Gesetz, nach dem sich die Anzahl der Transistoren, die auf eine bestimmte Fläche passen, alle zwei Jahre verdoppelt. Dieses Gesetz bestimmte seit den 1960er Jahren die Entwicklung immer besserer Chips, aber es ist absehbar, dass es in nicht allzu ferner Zukunft zum Erliegen kommen wird. Für die Entwicklung von KIs wäre das aber grundsätzlich kein Problem, schließlich könnte man einfach größere Chips bauen, um die gewünschte Leistungsfähigkeit zu erreichen.

Relevanter ist daher in der Praxis eher der Energieverbrauch des Chips. Ein Beispiel: Der berühmte IBM-PC aus dem Jahr 1981 verwendete als CPU einen Prozessor namens Intel 8088. Dieser hatte 29.000 Transistoren und eine Leistungsaufnahme von 1 Watt. Ein moderner Prozessor (aus dem Jahr 2020) hat dagegen rund 10 Milliarden Transistoren – wäre die Leistungsaufnahme in gleichem Ausmaß gestiegen wie die Anzahl der Transistoren, dann würde solch ein Prozessor über 300 Kilowatt verbrauchen und könnte mit seiner Abwärme 25 Einfamilienhäuser beheizen.

Es ist also wichtig, dass sich nicht nur die Rechenleistung erhöht, sondern dass gleichzeitig auch der Energieverbrauch sinkt. Das war lange Zeit der Fall, und diese Beziehung wurde ein halbes Jahrhundert lang durch das Koomey’sche Gesetz beschrieben: Der Energieverbrauch bei gleicher Rechenleistung fiel alle anderthalb Jahre um die Hälfte.

Dem Anschein nach kommt aber diese Faustregel, die über 50 Jahre lang gültig war, allmählich zum Stillstand. Bei vielen Chips sieht man bereits eine Verlangsamung auf eine Halbierung der Leistungsaufnahme alle zweieinhalb Jahre. Vor allem aber nähern wir uns allmählich einer harten Grenze: in spätestens 25 Jahren muss das Koomey’sche Gesetz einfach deshalb zum Stillstand kommen, weil die Gesetze der Physik keine weitere Steigerung mehr zulassen.

Das ist deshalb wichtig, weil es bedeutet, dass das Ziel, eine starke KI zu bauen, nicht erreicht werden kann, indem man einfach nur auf immer leistungsfähigere Rechner setzt. Tatsächlich funktioniert das menschliche Gehirn ja auch ganz anders als ein Computerchip. Man wird daher wohl ganz andere Hardware benötigen als bisher, und es ist noch völlig unklar, in welchem Umfang diese Umstellung gelingt.

Starke KI (2): Soll und Ist

Derweil können wir aber einen Blick werfen auf das, was derzeit technisch möglich ist. Und dabei deutet eben vieles darauf hin, dass die künstlichen Intelligenzen, die derzeit gebaut und in den Medien diskutiert werden, noch meilenweit von einer starken KI entfernt sind.

  • Die alljährlichen Gewinner des Loebner Prize für den „most human computer“ (eine Art Turing-Test, bei dem es darum geht, so menschlich wie möglich zu kommunizieren) zeichnen sich eben nicht durch intelligente Konversation aus, sondern dadurch, dass sie versuchen, den Partner so lange über ihre Ahnungslosigkeit hinwegzutäuschen, bis das Zeitlimit erreicht ist.
  • Manche dieser Programme „lernen“ auch einfach massenhaft menschliche Kommunikationen auswendig und wählen jeweils eine geeignete Antwort aus – eine Strategie, die so ähnlich auch von der KI IBM Watson angewandt wurde, um beim Jeopardy-Spiel gegen die amtierenden Champions zu gewinnen.
  • Der Computer AlphaGo, der durch seinen überragenden Sieg gegen den besten Go-Spieler der Welt berühmt wurde, ist dem Menschen nur in einem sehr schmalen Bereich überlegen: dem Spielen eines Spiels mit festen Regeln, die sich auf weniger als 3 Seiten beschreiben lassen.

Solche und ähnliche Erfolge künstlicher Intelligenzen sagen leider sehr wenig darüber aus, wie weit der Weg zu einer starken KI ist – sie sind auf enge Themengebiete beschränkt und durchgehend nicht in der Lage, abstrakt zu denken oder gar ein neues Problem zu lösen, was aber gerade das Hauptkriterium menschenähnlicher Kognition wäre.

Schwache KI

Ich vermute daher, dass die Singularität noch lange auf sich warten lässt und wir es auf absehbare Zeit vor allem mit schwachen KIs zu tun haben werden: Computersystemen, die in der Lage sind, ein klar abgegrenztes Problem zu lösen. In diesem Bereich sehen wir tatsächlich seit einigen Jahren große Fortschritte. KIs erkennen Gesichter, fälschen Videos, steuern Autos, komponieren Musik, zeichnen Bilder oder suchen in gewaltigen Datenmengen nach Mustern. Dabei wissen sie zwar nicht, was sie tun, aber die Ergebnisse sind beeindruckend.

Interessanterweise stellt sich dabei heraus, dass gerade solche menschliche Tätigkeiten, die jahrelang als „intelligent“ angesehen und entsprechend teuer bezahlt wurden (ärztliche Analyse, die Suche nach passenden Rechtstexten, das Schreiben von Computerprogrammen etc.) für KIs vergleichsweise gut zu bewältigen sind, und viele Experten gehen davon aus, dass hier in der Zukunft viele Arbeitsplätze wegfallen werden. Das gleiche gilt sicherlich auch für die gewaltige Anzahl von Arbeitsplätzen, bei denen es eben um den Umgang mit Daten in allen Formen geht (beispielsweise in Buchhaltung, Verwaltung etc.).

Große Schwierigkeiten haben KIs dagegen immer noch mit vielem, was für Menschen selbstverständlich ist: Bewegung, Sinneswahrnehmung, Empathie, Kommunikation, Sozialverhalten und vor allem das Handeln in komplexen Umgebungen. Es zeichnet sich ab, dass in der näheren Zukunft eine Zweiteilung von Aufgaben eintreten wird: Jene, die leicht von Computern übernommen werden können, und solche, die weiter dem Menschen vorbehalten bleiben.

Das eigentliche Problem

Das Problem ist also nicht so sehr, dass die KIs in den Bereich dessen eindringen würden, was wir als zutiefst menschlich empfinden. Sie werden vielmehr vor allem solche Tätigkeiten übernehmen, die nur vergleichsweise wenigen von uns wirklich liegen, sondern von den meisten schon zu Schulzeiten als unangenehm und langweilig empfunden wurden. Natürlich wird das Vordringen der KIs zu Veränderungen führen (und nicht alle werden diese Veränderungen mögen), aber die Welt wird davon nicht untergehen.

Ich selbst mache mir eher über einen anderen Punkt Gedanken, nämlich über die blinde Technikgläubigkeit, mit der die Ergebnisse der KIs übernommen werden. Zur Erinnerung: Die meisten (schwachen) KIs, die derzeit im Einsatz sind und aus großen Datenmengen Handlungsempfehlungen ableiten, haben eines gemeinsam: Wir wissen nicht wirklich, nach welchen Kriterien sie ihre Entscheidungen treffen (sie wissen es auch selbst nicht und können es uns nicht erklären). Wenn nun aber diese Vorschläge unreflektiert übernommen werden, „weil der Computer es ja so berechnet hat“ (und der menschliche Entscheider mit den Datenmengen ohnehin vollkommen überfordert ist), dann weiß genau genommen niemand mehr, warum Entscheidungen so gefällt wurden, und es fühlt sich auch niemand mehr dafür verantwortlich. Gerade der Frage nach der Verantwortung kommt aber eine entscheidende Rolle zu, und sie wurde auch beispielsweise im Zusammenhang mit selbstfahrenden Autos intensiv diskutiert. Da reichten die (wenig praktikablen) Vorschläge von „der Fahrzeughalter muss eben doch die ganze Zeit aufpassen und im Zweifel eingreifen“ bis zu „die Firma, die die Fahrzeug-KI herstellt, muss für eventuelle Schäden haften“. Bei typischen Data-Mining-Anwendungen scheint eine solche Diskussion aber völlig zu fehlen, obwohl entsprechende Systeme schon längst im praktischen Einsatz sind. Hier nutzen Entscheider den Verweis auf die Entscheidung der KIs oft sogar als Beleg dafür, dass sie ja besonders gewissenhaft gearbeitet haben. So müssen wir damit rechnen, dass künftig beispielsweise Anträge auf einen Kredit (oder eine Wohnung oder eine Krankenversicherung oder eine Bewährung…) abgelehnt werden, ohne dass man auch nur eine Begründung dafür bekommen kann, denn schließlich weiß ja niemand, warum die KI so und nicht anders entschieden hat. Das ist problematisch und wird sicherlich noch Gerichte, Politik und Gesellschaft beschäftigen.

Vor diesem Hintergrund wird es noch wichtiger als bisher sein, einen kritischen Umgang mit Medien und Daten in allen Formen zu bewahren. Wir müssen uns angewöhnen, skeptisch zu bleiben bei allem, was eine Künstliche Intelligenz berechnet oder was uns (als Text, Foto oder Video) als „Beweis“ serviert wird. Das – und nicht der Kampf gegen eine vorläufig noch fiktive übermächtige KI – wird meiner Meinung nach darüber entscheiden, in was für einer Gesellschaft wir künftig leben.

Und um auf meine ursprüngliche These zurückzukommen: Nein, ich habe keine Angst vor KIs. Ich mache mir eher Sorgen über die Art, wie wir damit umgehen…

Kategorien
Uncategorized

Warum KIs keine Algorithmen sind

Ganz zu Beginn dieses Blogs habe ich ja darauf hingewiesen, dass es hier nicht darum geht, Körner meiner überlegenen Weisheit fallen zu lassen (die ich übrigens gar nicht besitze), sondern vielmehr Schritte meiner eigenen Reise zu einem besseren Verständnis des Themas „algorithmisches Denken“ zu dokumentieren. Dazu gehört auch, dass man ab und zu feststellt, dass etwas, was man früher verstanden zu haben glaubte, doch komplizierter ist. Und dass man mögliche Fehler nachträglich korrigiert – nicht heimlich, still und leise, sondern ausdrücklich.

Und um einen solchen Fehler in einem früheren Posting soll es heute gehen.

Algorithmus und Heuristik, die Zweite

Anfang des Jahres habe ich einen Beitrag zum Thema Algorithmus und Heuristik geschrieben. Dabei bin ich etwas vorschnell zu dem Schluss gekommen, dass eine Heuristik ein spezieller Fall eines Algorithmus ist, was ich an dieser Stelle korrigieren möchte.

Das Problem wird deutlich, wenn man sich überlegt, wie die Heuristiken funktionieren, mit denen das menschliche Gehirn arbeitet. Bei der Definition eines Algorithmus hatten wir nämlich gefordert, dass es sich um „eine schrittweise Handlungsanweisung, wobei die Schritte so eindeutig definiert sein müssen, dass keine Missverständnisse aufkommen können“ handeln muss. Und genau so funktioniert unser Gehirn natürlich nicht.

Zwar wissen wir noch längst nicht alles über die Funktionsweise unseres Denkapparats, aber es scheint doch gesichert, dass er weder mit Einzelschritten arbeitet noch, dass sein Vorgehen eindeutig definiert (im Sinne von: wiederholbar) ist. Vielmehr handelt es sich um eine Verkettung von zahlreichen elektrischen Signalen, die parallel erfolgen und von variabler Stärke sind. Der Versuch, das Vorgehen des Gehirns in einen Schritt-für-Schritt-Algorithmus zu übersetzen, scheint damit aussichtslos.

Künstliche Intelligenz

Interessanterweise gilt das Gleiche auch für die Künstlichen Intelligenzen (kurz KIs genannt), die man in Anlehnung an natürliche Gehirne entwickelt hat. Wir wissen zwar, wie man sie baut und für ein bestimmtes Problem trainiert, aber wir wissen nicht wirklich, wie sie vorgehen, um ein konkretes Problem zu lösen.

So war der Rechner AlphaGo zwar 2016 in der Lage, den weltbesten Go-Spieler wiederholt zu besiegen, aber selbst seine Erbauer können nicht genau sagen, wie er dabei vorgegangen ist. Und das liegt nicht daran, dass wir zu dumm wären, sein Vorgehen zu verstehen, sondern dass sein Vorgehen eben kein vollständig algorithmisches ist. Seine Spielstrategie ist vielmehr in einem Suchbaum sowie in der Anordnung seiner Knoten (seinen „Neuronen“) und der Gewichtung der Kanten dazwischen (seinen „Synapsen“) codiert. Teile seines Vorgehens können zwar als Algorithmus beschrieben werden, aber eine vollständige Wiedergabe ist so nicht möglich, und man könnte daraus auch kein Rezept ableiten, anhand dessen menschliche Go-Spieler ihr Spiel verbessern können.

KIs sind keine Algorithmen

Das Interessante daran ist, dass eine KI (jedenfalls eine, die wie die meisten aktuellen Programme auf dem Deep-Learning-Ansatz basiert) genauso wenig ein Algorithmus ist wie die Vorgehensweise des menschlichen Gehirns. Die von KI-kritischen Kommentatoren immer wieder vorgetragene Sorge vor den bösen „Algorithmen“ ist somit sachlich falsch.

Das mag nach Haarspalterei klingen, ist aber in Wirklichkeit von großer Tragweite, gerade wenn man sich Sorgen über die Entwicklung immer mächtigerer KIs macht. Wenn es sich nämlich um Algorithmen handeln würde, könnte man sie analysieren, von ihnen lernen und sie auch abschalten, bevor sie zu mächtig werden. Das Problem ist aber gerade, dass man das nicht kann: Wenn eine KI ein Problem erfolgreich löst, wissen wir also gerade nicht, wie sie das angestellt hat (oder wozu sie sonst noch in der Lage ist).

Wenn ich zu den Leuten gehören würde, die Angst vor der Entwicklung der KIs haben (was nicht der Fall ist, mehr dazu in einem der nächsten Beiträge), dann würde mir diese Art von Heuristik viel mehr Sorgen machen als ein mächtiger Algorithmus…

Kategorien
Uncategorized

Wer will wirklich Probleme lösen?

Einmal wie immer, bitte!

Bisher bin ich ja stillschweigend davon ausgegangen, dass es ein menschliches Bedürfnis ist, Probleme lösen zu können. Nun bin ich kein Psychologe, aber zumindest die Beobachtungen aus dem Hochschulalltag deuten darauf hin, dass diese Annahme keinesfalls für alle zutrifft.

Als Dozenten erleben wir immer wieder, dass sich viele Studierende nichts sehnlicher wünschen, als Aufgaben nach einem festen Strickmuster, die man auf die immer gleiche Weise lösen kann. Nun kann man ihnen das ja nicht verdenken – das ist schließlich der sichere Weg, gute Noten zu bekommen. Was mich aber nachdenklich stimmt ist, dass dieser Wunsch keinesfalls auf die Prüfungen beschränkt zu sein scheint, sondern daher rührt, dass die Fähigkeit zum Lösen neuer Probleme häufig gar nicht vorhanden ist und auch nicht angestrebt wird.

Die universelle Problemlösungsheuristik

Vermutlich jeder, der an einer Hochschule unterrichtet, kann bestätigen, dass die universelle Problemlösungsheuristik unserer Tage „Frag Google!“ heißt. Und tatsächlich kann man die Frage stellen, wo denn das Problem dabei sein soll, diese Heuristik auf so viele Probleme wie möglich anzuwenden. Löst sie das Problem etwa nicht? Ist sie etwa nicht effizienter als selbst stundenlang darüber zu brüten? Wo wäre denn die Menschheit, wenn jeder immer wieder versuchen würde, das Rad neu zu erfinden? Eben.

Da ist nur das klitzekleine Problem, dass man früher oder später an den Punkt kommt, an dem man neue Probleme lösen muss. Und wenn dann die einzige Heuristik, die man zur Problemlösung gelernt hat, darin besteht, nach einer existierenden Lösung für bekannte Probleme zu suchen, dann ist die eigene Toolbox an dieser Stelle eben leer.

Dummerweise deutet viel darauf hin, dass wir dank immer leistungsfähiger werdender Computer und der Fortschritte in der Künstlichen Intelligenz künftig immer weniger Menschen brauchen werden, die bekannte Probleme mit bekannten Methoden bearbeiten. Das wird voraussichtlich schon in nicht allzu ferner Zukunft zu einer Aufgabe der Maschinen werden.

Gerade wenn es um die Abgrenzung zwischen künstlicher und menschlicher Intelligenz geht, wird immer wieder gern darauf verwiesen, dass der Mensch doch ein universeller Problemlöser sei, kreativ, intuitiv und vielseitig und somit den Maschinen himmelhoch überlegen. Ich halte es für wahrscheinlich, dass wir schon bald den Beweis antreten müssen, dass dem wirklich so ist – mit Standardlösungen aus dem Internet wird das aber nicht möglich sein.

Lernziel „Problemlösungskompetenz“

In dem Zusammenhang stelle ich mir immer häufiger die Frage, inwieweit es uns in Schule und Hochschule gelingt, junge Menschen darin auszubilden, solche neuen Probleme zu lösen. In vielen Fächern hat man als Außenstehender den Eindruck, dass das Vermitteln von Wissen und das Anwenden bereits bekannter Vorgehensweisen im Mittelpunkt stehen. Das Entwickeln neuer Lösungen wird dagegen eher der Forschung zugeordnet und bleibt einem kleinen Kreis von Auserwählten vorbehalten.

Dabei sagen die Lehrpläne meist etwas ganz anderes. Sie verwenden für die Definition der Lernziele häufig die Bloomsche Taxonomie, die die zu vermittelnden Kompetenzen in sechs Stufen einteilt:

  1. Kennen (Wissen)
  2. Verstehen
  3. Anwenden
  4. Analysieren
  5. Zusammenführen (Synthese)
  6. Beurteilen (Evaluation)

Das Entwickeln neuer Lösungen fällt dabei in Stufe 5 und 6: Synthese und Evaluation. Diese Fähigkeiten werden ab einem bestimmten Punkt in so gut wie allen Lehrplänen gefordert. Nichtsdestotrotz trifft man im Alltag erstaunlich viele Menschen, deren Kompetenz trotz Bildungsabschlüssen wie Abitur, Bachelor oder sogar Master kaum über Stufe 1 hinausgehen. Offenbar werden die weitergehenden Kompetenzen oft gar nicht eingefordert, sonst wäre die Prüfungsstrategie „Bulimielernen“ nicht so häufig von Erfolg gekrönt.

Die Frage ist nun, was Ursache und was Wirkung ist. Sind die meisten Menschen schlicht nicht (oder nur unter großen Schwierigkeiten) in der Lage, Problemlösungskompetenz zu entwickeln? Und kapitulieren die Bildungsanstalten vor dieser Tatsache, indem sie auch denen, die es nicht weiter als bis zur Stufe 3 geschafft haben, trotzdem einen Abschluss geben, um nicht von eifrigen Sparpolitikern wegen schlechter Absolventenzahlen geschlossen zu werden? Oder erzieht die Art, wie Kompetenzen vermittelt und abgeprüft werden, Schüler und Studierende überhaupt erst dazu, sich eher auf Stufe 1-3 der Bloomschen Taxonomie zu konzentrieren?

Was tun?

Wie ich bereits im Beitrag über Intuition geschrieben habe, neige ich häufig dazu, die Wahrheit in der Mitte zu sehen. Einerseits halte ich das Disney-Paradigma, dass man alles werden kann, wenn man es nur genug will, für gefährlichen Unsinn. Wir können nicht alles werden, und wir können schon gar nicht durch entsprechende Schulung aus jedem alles machen. Worin wir gut sind, hängt immer ab von Einsatz und Veranlagung. Andererseits gibt es durchaus Indizien dafür, dass das Bildungssystem sehr wohl einen Einfluss auf die Problemlösungskompetenz hat. So zeigt ein Blick in unsere internationalen Master-Studiengänge, dass sich so mancher Absolvent ausländischer Universitäten noch deutlich schwerer tut mit dem selbständigen Problemlösen, und das liegt sicherlich nicht an der Intelligenz, sondern an der Art, wie mancherorts noch immer Wissen vermittelt wird.

Zugleich bezweifle ich, dass wir uns bereits entspannt zurücklehnen und mit dem Status Quo zufrieden sein dürfen. Solange die verbreitetste Veranstaltungsform an Schulen und Hochschulen noch immer der Frontalunterricht ist und die verbreitetste Prüfungsform die 60-Minuten-Prüfung, müssen wir uns nicht wundern, wenn die Studierenden auf Auswendiglernen und das Bearbeiten von kurzen Übungsaufgaben setzen, um die Stoffmengen zu bewältigen. Problemlösungskompetenz entwickeln sie auf diese Weise nicht.

Wenn es uns ernst ist damit, junge Menschen zu Problemlösern auszubilden, müssen wir so manches alte Paradigma hinterfragen: Ist eine große Stoffmenge in Zeiten des Internets wirklich wichtiger als der sichere Umgang mit Methoden? Erlernt man diese, indem man zweimal pro Woche 90 Minuten andächtig den Worten eines Dozenten lauscht und dann daheim ein paar Übungsaufgaben rechnet? Und welche Anreize setzt eine Klausur, von der man weiß, dass keine Teilaufgabe eine Bearbeitungsdauer von mehr als 15 Minuten haben wird?

Es ist einfach, von der Höhe des Professorenpults herab über die Jugend von heute zu klagen. Aber es ist etwas ganz anderes, jungen Menschen Wege aufzuzeigen, wie sie mehr werden können als reine Wissensreproduzierer. Wenn es uns ernst ist mit der Problemlösungskompetenz, werden wir mehr ändern müssen als nur ein paar Lernziele.

Kategorien
Uncategorized

Meta-Algorithmik

Die Meta-Frage der Algorithmik

Von Algorithmen ist derzeit viel die Rede, und in keinem Informatik-Lehrplan darf ein Kurs „Algorithmen und Datenstrukturen“ fehlen. Algorithmik ist die Lehre von den Algorithmen, aber sie umfasst mehr, als in einem klassischen Algorithmen-Buch steht. Ziegenbald schreibt dazu im Handbuch der Mathematikdidaktik (Springer, 2015):

Computer werden mit Programmen bzw. Algorithmen „gefüttert“, und dementsprechend ist in diesem Zeitraum viel Literatur zum Thema Algorithmen entstanden, weniger dagegen zur Algorithmik. Der Begriff der Algorithmik ist der umfassendere, denn neben der rein inhaltlichen Seite, eben den Algorithmen (auf der „Objektebene“), umfasst er (auf der „Metaebene“) alles, was das Arbeiten mit Algorithmen betrifft, also insbesondere auch die Methode des algorithmischen Problemlösens. Er signalisiert, dass es beim Arbeiten mit Algorithmen auch um eine bestimmte methodologische und philosophische Grundeinstellung geht, die in einem engen Zusammenhang mit der konstruktivistischen Seite der Mathematik steht.

Tatsächlich habe ich in meinem Büro ziemlich viele Bücher stehen, die Titel wie „Algorithmen und Datenstrukturen“ oder „Algorithmen in Java/Python/C/…“ tragen. Die meisten davon erklären, wie Algorithmen für typische Probleme funktionieren. Einige wenige erklären sogar die dahinterliegenden Designprinzipien für Algorithmen. Aber ich kenne tatsächlich nur ein einziges, das die Frage beantwortet, die sich meiner Meinung nach jeder Algorithmiker irgendwann stellen müsste:

„Wie sieht ein Algorithmus (oder eine Heuristik) aus, mit dessen Hilfe man einen geeigneten Algorithmus für ein gegebenes Problem findet?“

Ein Algorithmus, der Algorithmen findet

Das Buch, das besagte löbliche Ausnahme bildet, ist The Algorithm Design Manual (Springer, 2008) von Steven S. Skiena, das in seinem Mittelteil tatsächlich ein (wenn auch kleines) Kapitel namens „How to Design Algorithms“ enthält. Dieses Kapitel gibt tatsächlich eine Schritt-für-Schritt-Anleitung zum Finden von Algorithmen. Dieser ist zwar vergleichsweise oberflächlich und alles andere als einfach anzuwenden, aber es ist immerhin ein Versuch.

Was man häufiger findet, sind Sammlungen von Techniken, die beim Entwickeln von Algorithmen helfen. Ein berühmtes Beispiel ist Polyas 1945 erschienenes (und seither immer wieder aufgelegtes) Buch How to Solve It. Ihm geht es zwar in erster Linie um das Lösen mathematischer Probleme, aber seine Ideensammlung umfasst von Analogy bis Working Backwards viele Techniken, die auch auf andere Diszplinen (und insbesondere auf die Algorithmik) übertragbar sind. Eines aber leistet auch sie nicht: Sie bringt diese Techniken nicht in eine Reihenfolge, sondern überlässt es der Intuition des Lesers, die richtige Technik oder die richtige Kombination von Techniken für den jeweiligen Anlass auszuwählen.

Es erstaunt mich, dass Algorithmiker nicht entschlossener darüber nachdenken, wie sie eigentlich einen Algorithmus finden. Skiena selbst schreibt:

Problem-solving is not a science, but part art and part skill.

Dieser Satz weckt in mir unangenehme Erinnerungen, weil er in meinem angestammten Forschungsgebiet, der Kryptografie, fast genauso verwendet wird. Scheinbar beginnen wir immer dann, wenn wir ein Problemfeld nicht wirklich durchdrungen haben, von einer Kunstform zu reden. Wahrscheinlich haben die Menschen früherer Jahrhunderte das gleiche über die Medizin oder die Landwirtschaft gesagt.

Einerseits spricht daraus ein gesundes Vertrauen in die menschliche Intuition. Selbst eine so exakte Wissenschaft wie die Mathematik wird an den meisten Universitäten gelehrt, indem man die Studierenden mit zahlreichen Beispielen konfrontiert und darauf setzt, dass das Gehirn schon irgendwann selbst herausfinden wird, wie es beim Lösen neuer Probleme vorzugehen hat.

Bin ich zu naiv, wenn ich mir wünsche, dass wir wenigstens versuchen sollten, erste Schritte in die Richtung einer Meta-Algorithmik zu machen? Es muss ja nicht gleich perfekt sein, aber können wir unseren Studierenden nicht erklären: „Wenn ich vor einem neuen Problem stehe, dann mache ich zuerst dies, dann versuche ich das?“ Müssen wir uns wirklich damit abfinden, dass Algorithmik eine Kunstform ist, die am Ende eben den Inspirierten vorbehalten ist? Besteht nicht doch die Hoffnung, dass wir Heuristiken zum Finden von Problemlösungen beschreiben können, die vielleicht nicht gleich optimal sind, aber nachvollziehbar und vielleicht sogar vergleichbar? Und wäre nicht das der erste Schritt hin zu einer echten Wissenschaft des Denkens?

Kategorien
Uncategorized

Wenn sich Theorie verselbständigt

Letzte Woche habe ich ja bereits über Richard Feynman gesprochen. Er war als ausgesprochen fähiger Problemlöser bekannt, so dass sich die Frage stellt, wie er dabei vorging.

Er selbst betonte immer wieder, dass er nur denken könne, wenn er eine Anwendung oder konkrete Anschauung vor Augen habe. Mit anderen Worten gelang ihm das überraschend seltene Kunststück, die Theorie zu beherrschen, darüber aber die Praxis nicht aus dem Blick zu verlieren.

Tatsächlich habe ich den Eindruck, dass eine Theorie häufig von Leuten entwickelt wird, die sehr genau wissen, wozu sie dient und wie sie angewandt werden kann. Dann aber neigt sie irgendwie dazu, sich zu verselbständigen: Den nächsten Generationen wird nur noch die Theorie beigebracht, die Anwendung wird dann leicht als „trivial“ abgetan. Und dabei geht viel Verständnis verloren, im Extremfall bis zu dem Punkt, an dem die Theorie so lange weiterentwickelt wird, bis sie für die Praxis nicht mehr anwendbar ist. Benjamin Brewster hat dieses Phänomen, das wir sicher alle schon erlebt haben, 1882 mit diesen Worten beschrieben: „In theory, there is not difference between theory and practice. In practice, there is.“

Im Folgenden will ich das Problem einmal am Beispiel der Entropie erklären, und vielleicht es wird der eine oder andere, der ein Studium der Informatik hinter sich hat, sogar wiedererkennen.

Was ist Entropie?

Als Claude Shannon 1948 mit einem einzigen Paper das neue Forschungsgebiet der Informationstheorie aus der Taufe hob, führte er auch den Begriff der (Informations-)Entropie ein. Es handelt sich um ein Maß für die Ungewissheit über den Inhalt einer Nachricht. Gemessen wird sie in Bit, und je größer sie ist, desto weniger kann man vor dem Lesen der Nachricht über ihren Inhalt aussagen.

Ein klassisches Lehrbuchbeispiel ist das Werfen einer Münze (die „Nachricht“ ist das Ergebnis des Münzwurfs). Handelt es sich um eine faire Münze, so beträgt die Entropie genau 1 Bit. Weiß ich dagegen, dass die Münze manipuliert ist (sagen wir, sie zeigt in 3 von 4 Fällen „Kopf“), dann ist die Entropie niedriger (konkret etwa 0,8 Bit), weil ich eine Ahnung habe, wie die Nachricht aussehen wird. Im Extremfall fällt die Entropie vollends auf 0, nämlich immer dann, wenn ich schon vorher sicher weiß, was herauskommt.

Nun wird die Entropie nicht umsonst in Bit gemessen, denn der Informationsgehalt einer Nachricht sagt zugleich etwas darüber aus, wie kompakt man sie darstellen kann. Um den Ausgang unseres fairen Münzwurfs zu speichern, benötige ich eben mindestens 1 Bit, und wenn ich vier faire Münzwürfe hintereinander ausführe, muss ich mindestens 4 Bit zur Verfügung haben, um das Ergebnis zu speichern. Ich kann zwar jederzeit auch mehr Bits verwenden, aber weniger sind ausgeschlossen.

Beispiel: Nehmen wir an, es wird „Zahl, Zahl, Kopf, Zahl“ geworfen. Wenn wir uns zuvor geeinigt haben, dass „Zahl = 1“ und „Kopf = 0“ codiert wird, dann reicht es, dass ich das Ergebnis als 1101 abspeichere. Ich könnte es aber auch beispielsweise als Textstring „Zahl, Zahl, Kopf, Zahl, Kopf“ abspeichern – der String besteht aus 22 Zeichen, und da einfache Zeichen meist mit 8 Bit codiert werden, werden 22*8=176 Bit abgespeichert. Falsch ist das nicht, aber eben viel mehr, als streng genommen nötig gewesen wäre.

In Vorlesungen wird beim Thema Entropie gerne mit dem Beispiel der natürlichen Sprache gearbeitet. Wenn wir die Entropie der Buchstaben der deutschen Sprache anhand ihrer Häufigkeit ausrechnen (ein „E“ ist extrem häufig, ein „R“ kommt immer noch ziemlich oft vor, ein „Q“ dagegen ist sehr selten usw.), dann stellt sich heraus, dass sie ca. 4 Bit beträgt. Ein Buchstabe kann also in ca. 4 Bit codiert werden.

Verlust des Anwendungsbezugs

Und jetzt passiert es. In dem Moment, in dem diese 4 Bit im Raum stehen, verirrt sich so mancher im Labyrinth der Theoreme und verliert die Praxis aus dem Blick. Eine typische Argumentationskette, die man explizit oder implizit auf Webseiten und sogar in Lehrbüchern findet, sieht dann so aus:

  • Die Entropie eines deutschen Buchstabens beträgt 4 Bit.
  • Wenn man eine Nachricht aus n Elementen zusammensetzt, die alle die Entropie 4 Bit haben, dann hat die Gesamtnachricht die Entropie 4n Bit.
  • Somit hat eine Nachricht in deutscher Sprache, die aus n Zeichen besteht, eine Entropie von 4n Bit.

Dass das so nicht stimmt, kann man leicht herausfinden, indem man einen deutschen Text von einem beliebigen Kompressionsprogramm (wie z.B. ZIP) verlustfrei komprimieren lässt, und siehe da: Eine Nachricht mit n Zeichen lässt sich in ungefähr 3,25n Bit speichern – wenn die obige Aussage stimmen würde, müsste die Kompression aber mindestens 4n Bit benötigen!

Jetzt kann man natürlich fragen, wo hier etwas schiefgegangen ist.

Damit kann man einerseits den Fehler in der Argumentation meinen. Haben Sie ihn gefunden? Falls nicht, kommt hier die Auflösung: Das entscheidende Problem ist, dass die Buchstaben einer deutschen Nachricht etwas miteinander zu tun haben – im Gegensatz zu den Münzwürfen sind sie nicht unabhängig voneinander. Somit ergibt sich die Gesamtentropie nicht als Summe der Einzelentropien.

Statt nach dem mathematischen Grund für den Fehler könnte man aber auch fragen, warum man überhaupt den Realitätsbezug aus dem Blick verloren hat. Denn mit ein paar einfachen Beispielen hätte man ja sofort sehen können, dass hier etwas nicht stimmt. Wenn wir beispielsweise nur zwei mögliche Nachrichten aus 40 Zeichen betrachten (sagen wir mal, „Der geplante Angriff morgen findet statt“ und „Der geplante Angriff morgen ist abgesagt“), dann ist ja ziemlich klar, dass wir dafür keine 40*4=160 Bit für eine komprimierte Codierung benötigen – ein einfaches „Angriff = 1“ und „Absage = 0“ hätte auch gereicht. Die Nachricht enthält also nur ein einziges Bit an Information!

Wo kamen wir nochmal her?

Was hier geschieht, ist ein Beispiel für ein Problem, das ich bereits letzte Woche erwähnt habe und auf das ich noch öfter zurückkommen werde: Wenn man sich mit einem Thema unter einer bestimmten Brille beschäftigt (hier: der Brille der Informationstheorie) und dabei die menschliche Erfahrungswelt aus dem Blick verliert, dann stehen die Chancen gut, dass man irgendwann einen Fehler macht und dies nicht einmal bemerkt. Es fehlt schlicht das Korrektiv, das uns sagt: „Das war jetzt ist ja alles schön und gut, aber es kann nicht stimmen, weil es nämlich ein offensichtliches Gegenbeispiel gibt!“

Es scheint erstaunlich schwer zu sein, sich diesem Sog der Theorie zu entziehen. Oft beginnen wir ja sogar mit einer konkreten Fragestellung, verlieren diese dann aber aus dem Blick und glauben dann irgendwann das, was wir in der Theorie gelernt haben, ohne es wieder vor den Spiegel der Anwendung zu halten und zu prüfen, ob es eigentlich passt. Das geht mir selbst so, und ich weiß aus Erfahrung, dass es der überwiegenden Mehrheit meiner Studierenden nicht anders geht: Wenn ich eine Theorie auf der Tafel nur überzeugend genug hinschreibe, geht eben kaum jemand nach Hause und macht mal einen einfachen Test (so wie oben mit dem ZIP-Programm), um zu prüfen, ob das eigentlich stimmen kann. Und das, obwohl die meisten meiner Studierenden sofort bestätigen würden, dass sie sich für die Anwendung viel mehr interessieren als für die Theorie.

Dabei haben wir als Informatiker oft eine einzigartige Möglichkeit, solche Theorien zu überprüfen: Wir können sie nämlich ausprobieren! Es gibt nur wenig, was man in unserem Fach glauben oder der Theorie überlassen muss – spätestens, wenn die theoretischen Überlegungen abgeschlossen sind, können wir die Ergebnisse in die Praxis tragen und nachschauen, ob sie auch das tun, was sie tun sollten! Und die Chancen stehen gut, dass wir auf diese Weise beides verbessern: sowohl unser Verständnis der Theorie als auch unsere Fähigkeiten in der Praxis.

Kategorien
Uncategorized

Lernen von den Großen: Richard Feynman

Der Feynman-Algorithmus

Der Physiker Murray Gell-Man beschrieb einmal die Problemlösungsstrategie des Nobelpreisträgers Richard Feynman wie folgt („The Feynman Algorithm“):

  1. Write down the problem.
  2. Think real hard.
  3. Write down the solution.

Das Problem an diesem Algorithmus war natürlich, dass er so nur von Richard Feyman anwendbar war – für den Rest der Welt blieb damit nur noch der Non-Feynman-Algorithmus:

  1. Write down the problem.
  2. Ask Feynman.
  3. Copy the solution.

Leider ist Richard Feynman aber im Jahr 1988 verstorben, so dass keiner der beiden Algorithmen mehr anwendbar ist. Wir müssen uns also wohl doch wieder eigene Gedanken machen, wie wir Probleme lösen können.

Natürlich war der Feynman-Algorithmus ohnehin nicht ernst gemeint. Gell-Man wollte damit lediglich betonen, dass für die Außenwelt oft nicht nachvollziehbar war, wie Feynman auf seine Problemlösungen kam – also das, was wir für gewöhnlich als „Genie“ bezeichnen. Aber genau genommen geht es uns ja allen so, dass wir oft gar nicht wissen, wo die Ideen herkommen, die plötzlich in unserem Kopf auftauchen.

Ironischerweise wusste gerade Richard Feynman recht gut, wie er vorging, um Probleme zu lösen. Ein Punkt war ihm dabei so wichtig, dass er in Büchern und Vorträgen immer wieder darauf verwies: Man sollte die Dinge, über die man nachdenkt, wirklich verstanden haben. Nur so bilden sie das Fundament, auf dem neues Wissen entstehen kann.

Die Sache mit dem Verstehen

Feynman war immer wieder erstaunt, wieviel die Menschen in seinem Umfeld zu wissen glaubten, ohne es verstanden zu haben.

In seinem autobiographisch-anekdotischen Buch „Surely You’re Joking, Mr. Feynman“ beschreibt er beispielsweise, wie unter den Studenten seines MIT-Kurses zum technischem Zeichnen eine Diskussion aufkam, wie wohl die Kurven eines Kurvenlineals ermittelt worden wären (für diejenigen, die so etwas gar nicht mehr kennen: ein Kurvenlineal wurde früher, als technische und mathematische Zeichnungen noch von Hand erstellt wurden, verwendet, um einigermaßen glatte Kurven hinzukriegen, und sah aus wie auf dem untenstehenden Bild). Feynman, der berüchtigt dafür war, seiner Umwelt gerne auf den Arm zu nehmen, erklärte: Das Lineal ist so geformt, dass der niedrigste Punkte jeder Kurve – ganz egal wie man es dreht – immer eine Horizontale ist. Seine Kommilitonen prüften diese Aussage nach, und siehe da – sie war korrekt!

(Drehungen eines Kurvenlineals)

Feynman selbst war einigermaßen erschüttert darüber, dass sich erfahrene Physikstudenten mit dieser Erklärung abspeisen ließen, denn in Wahrheit gilt diese Aussage schlicht für jede Kurve. Wenn man die gleiche Frage im Kontext einer Analysis-Vorlesung gestellt hätte, wäre jedem klar gewesen, dass die Steigung im tiefsten Punkte einer (stetigen und differenzierbaren) Kurve immer Null ist, ja dass das sogar die mathematische Definition eines lokalen Tiefpunkts ist! Aber sobald die gleiche Aussage in einem anderen Kontext und in abgewandelter Formulierung getroffen wird, wirkt sie auf die meisten Menschen (auch wenn sie sehr intelligent sind) neu und wird nicht wiedererkannt.

Der tiefste Punkte jeder Kurve hat eine horizontale Tangente!

Tatsächlich reden wir uns gerne ein, dass uns so etwas natürlich nicht passieren würde. Aber als ich anfing, darüber nachzudenken, warum sowohl meine Studenten als auch ich häufig nicht sahen, dass das, was wir über den Computer lernten, auch im Alltag anwendbar war, wurde mir klar, dass es sich um genau das gleiche Phänomen handelte: Wir erwerben Wissen meist für einen bestimmten Anwendungszusammenhang, und sobald wir uns in einem anderen Kontext bewegen, erkennen wir nicht mehr, dass es hier genauso relevant wäre.

Der Erklärtest

Woran also erkennt man, ob man ein Konzept wirklich verstanden hat? Man sollte es selbst herleiten können, wenn man es vergessen hat. Man sollte es auch auf ungewohnte Situationen anwenden können. Und man sollte – das war der von Feynman selbst vorgeschlagene Lackmus-Test – es auch einem Laien erklären können.

Ganz allgemein war Feynman der Meinung, dass das Lehren die beste Methode ist, ein Thema wirklich zu verstehen. Für mich selbst trifft das sicherlich zu, und es funktioniert umso besser, je mehr die Zuhörer wirklich etwas lernen wollen und sich auch trauen, Fragen zu stellen. Denn gerade diese Fragen decken häufig auf, wo man etwas noch nicht richtig verstanden hat – wer bereit ist, sich selbst zu verbessern, kann diese Gelegenheiten nutzen, um sein Wissen zu verbessern.

Feynman selbst ging so weit zu behaupten, dass man ein Konzept nur dann wirklich verstanden habe, wenn man es einem Kind erklären könne – ohne Fachbegriffe, mit Bildern, Beispielen und Analogien.

Nun gibt es natürlich Kinder mit sehr unterschiedlichen Voraussetzungen, und Feynman selbst (der sich als Elfjähriger während er Wirtschaftskrise ein Zubrot verdiente, indem er Radios reparierte oder Zaubershows mit Chemikalien aufführte) war sicherlich nicht wirklich repräsentativ. Aber dem Grundprinzip würde ich zustimmen: Vieles von dem, was wir zu wissen glauben, sind schlicht auswendig gelernte Fakten (oder gar Begriffe), an die wir eher glauben als dass wir sie wirklich überprüft und verstanden hätten.

Ein einfaches Beispiel: Viele Menschen glauben, dass der Schatten, den die Erde auf den Mond wirft, für die Mondphasen verantwortlich ist. Aber Hand aufs Herz – wer hat das schon wirklich persönlich nachgeprüft und könnte es einem Kind erklären? Und was ist, wenn das Kind anfängt, Fragen zu stellen („Aber wenn sich der Mond bewegt und die Erde und die Sonne, wieso haben wir dann die ganze Nacht lang die gleiche Mondphase?“)? Eben. Dann merken wir ganz schnell, ob wir das Thema wirklich verstanden haben oder ob wir eigentlich nur nachplappern, was wir von anderen gehört haben.

Kategorien
Uncategorized

Kognitionswissenschaft

Bereits in der Einführung habe ich ja geschrieben, dass ich in den letzten anderthalb Jahren viel darüber gelernt habe, was ich alles nicht weiß. Heute will ich einmal von einem Forschungsgebiet berichtet, von dem ich nicht einmal wusste, dass es existiert: der Kognitionswissenschaft nämlich.

(Und ja, alle die sich seit Jahren damit beschäftigen: Lacht nur. Aber fragt euch danach vielleicht auch mal, warum euer Thema – zumindest in Europa – nicht bekannter ist.)

Also: Ich bin bis vor kurzem davon ausgegangen, dass die Kognition des Menschen etwas ist, womit sich die Psychologie beschäftigt, genauer (ta-dah!): die Kognitionspsychologie. Hier beschäftigt man sich mit der Frage, wie das menschliche Denken organisiert ist: wie funktionieren Wahrnehmung und Aufmerksamkeit, wie speichert unser Gehirn Informationen, wie lernt es, wie löst es Probleme, produziert Ideen, trifft Entscheidungen oder trifft Schlussfolgerungen?

Nun neigt man als Informatiker natürlich bei all dem dazu, Vergleiche mit einem Computer anzustellen. Man sucht überall Gemeinsamkeiten und Unterschiede zwischen dem Gehirn und den Rechnern, die es sich ausgedacht hat. Tatsächlich hatten Leute wie Alan Turing, die die ersten Computermodelle erdacht haben, bevor man überhaupt Computer bauen konnte, genau das im Sinn: Sie wollten ein Modell dessen entwerfen, wozu menschliches Denken in der Lage ist und wozu nicht.

Was ist nun Kognitionswissenschaft?

Und letztlich ist genau das auch der Ausgangsgedanke der Kognitionswissenschaft. Im Gegensatz zur Kognitionspsychologie richtet sie den Blick nicht ausschließlich auf den Menschen, sondern auf alle Arten von denkenden oder informationsverarbeitenden Systemen. Natürlich hofft sie, dabei auch etwas über das menschliche Denken zu lernen, aber sie will auch umgekehrt das, was wir über menschliches Denken gelernt haben, auf künstliche Systeme übertragen.

Die Kognitionswissenschaft ist somit inhärent interdiszplinär. Instinktiv denkt man dabei an eine Kreuzung aus Kognitionswissenschaft und Informatik (insb. Künstliche Intelligenz), aber in den gängigen Darstellungen des Themas werden noch mehr Disziplinen genannt, die gerne in Form eines Heptagramms dargestellt werden.

Ursprünglich lag der Kognitionswissenschaft tatsächlich das sogenannte „Computermodell des Geistes“ zugrunde, nach dem man versuchte, das menschliche Gehirn als eine Art Computer zu modellieren. Dieses Modell gilt jedoch aufgrund heutiger Erkenntnis über die Funktionsweise des Gehirns als widerlegt. Stattdessen sucht man inzwischen nach Unterschieden, Gemeinsamkeiten und passenden Abstraktionen, die allen Arten von Kognition (natürlich wie künstlich) gerecht werden.

Verbindung zum Algorithmischen Denken

Eines der Probleme der Kognitionswissenschaft ist es, dass sie als Feld so gewaltig (und so unsauber gegen benachbarte Disziplinen abgegrenzt) ist, dass es niemand mehr überblickt. Wer sich davon überzeugen will, der kann einmal einen Blick in die Proceedings der Jahrestagung der Cognitive Science Society werfen, der stolze 3642 Seiten umfasst. Ich selbst habe jedenfalls noch nie einen derart riesigen Tagungsband mit derart vielen verschiedenen Themen gesehen. Die meisten Wissenschaftler sind daher nach wie vor nur in einem Teilbereich der Disziplin unterwegs und halten bestenfalls oberflächlich Kontakt zu den anderen Disziplinen.

Und so würde auch ich sie nutzen wollen. Tatsächlich hat die Kognitionswissenschaft manche Ergebnisse hervorgebracht, die hier tatsächlich relevant sind – so beispielsweise die bereits erwähnte Erkenntnis, dass sich biologische Gehirne eben nicht wie Computer verhalten. Zugleich gibt es Modelle, die sowohl biologische als auch technische Kognition als informationsarbeitende Systeme beschreiben, und die sind für die Zwecke meines Projekts natürlich nützlich. Hilfreich finde ich auch, dass man überall dort, wo man eine Verbindung zwischen zwei der oben genannten Disziplinen sucht (beispielsweise zwischen der Philosophie des Geistes und der Informatik / Künstlichen Intelligenz), in der Kognitionswissenschaft fündig wird.

Andererseits fehlt der Kognitionswissenschaft (soweit ich das am Anfang meiner Reise überblicke jedenfalls) eine wichtige Komponente dessen, was mich im Rahmen meines Projektes interessiert. Sie versteht sich nämlich in erster Linie als deskriptive Disziplin, die beschreibt, wie kognitive Systeme Informationen verarbeiten. Letztlich will sie in erster Linie verstehen, wie Kognition funktioniert. Sie scheint dagegen weniger daran interessiert, sich präskriptiv zu betätigen.

Letzteres ist aber gerade ein Ziel des algorithmischen Denkens: Es geht darum, analog zur Entscheidungstheorie nicht nur zu beschreiben, wie wir typischerweise an eine Aufgabenstellung (sei es nun das Treffen einer Entscheidung, das Lösen eines Problems oder das Schaffen kreativer Werke) herangehen, sondern auch, wie wir es tun sollten. Somit reiht sich die Kognitionswissenschaft ein in die lange Reihe von Disziplinen, die zu diesem Ziel beitragen können, ohne es jedoch als Hauptfokus zu haben.

Kategorien
Uncategorized

Algorithmus und Heuristik

In diesem Blog wird viel von Algorithmen und Heuristiken die Rede sein. Dabei zeigt ein Blick in die Literatur, dass nicht alle unter diesen Begriffen das Gleiche verstehen. Wie so häufig entwickelt man zwar schnell ein Gefühl dafür, was gemeint ist, die formalen Definitionen unterscheiden sich aber teilweise in wichtigen Punkten. Daher versuche ich mich hier gleich zu Beginn an einer Klarstellung, was ich im Rahmen dieses Blogs mit diesen Begriffen meine.

Zunächst einmal geht es immer darum, ein Problem zu lösen. Ein solches Problem kann dabei darin bestehen, eine Schachpartie zu gewinnen, eine Rechenaufgabe zu lösen, den Blumenladen in der Innenstadt zu finden oder mit den mir gegebenen Mitteln stinkend reich zu werden. Immer soll dabei eine Ausgangssituation in eine Zielsituation verwandelt werden oder zumindest in etwas, was diesem Ziel möglichst nahe kommt.

Algorithmus und Heuristik sind nun Vorgehensweisen, mit denen ein solches Problem mehr oder weniger gut gelöst wird. Ein Algorithmus ist dabei eine schrittweise Handlungsanweisung, wobei die Schritte so eindeutig definiert sein müssen, dass keine Missverständnisse aufkommen können. So ist die Handlungsanweisung „Beschwöre einen Djinn und bitte ihn um eine Tonne Gold“ kein Algorithmus für das Problem „Wie werde ich stinkend reich?“, weil der Schritt „Beschwöre einen Djinn“ nicht gut genug definiert ist.

Ein klassisches Beispiel für einen Algorithmus ist dagegen ein Kochrezept, mit dem wir eine Ausgangssituation (einen Stapel Zutaten) in eine Zielsituation (ein schmackhaftes Essen) verwandeln, wobei wir eine Reihe wohldefinierter Anweisungen (eine Zwiebel fein würfeln, 5 Minuten in heißer Butter dünsten,…) abarbeiten. Aber auch die Anweisungsfolge, mit der uns das Navi an unser Ziel bringt („In 200 Metern links abbiegen!“), oder die Rechenvorschrift, mit der wir zwei ganze Zahlen multiplizieren, sind Algorithmen.

Algorithmen müssen übrigens keinesfalls immer deterministisch sein, d.h. bei gleicher Ausgangssituation die gleiche Folge von Schritten ausführen und somit zum gleichen Ergebnis kommen. Es gibt nämlich auch randomisierte Algorithmen, bei denen Ablauf und Ergebnis vom Zufall beeinflusst werden. Ein einfaches Beispiel ist eine Partie „Schere, Stein, Papier“: wenn man dieses Spiel immer nach dem gleichen Verfahren gegen einen intelligenten Gegner spielt, wird dieser früher oder später hinter unseren Algorithmus kommen und dieses Wissen dann gegen uns verwenden. Aber auch in der Mathematik gibt es überraschenderweise Probleme, die sich leichter lösen lassen, wenn man dabei den Zufall mitspielen lässt.

Was aber sind nun Heuristiken? Im Grunde handelt es sich ebenfalls um Algorithmen, allerdings mit den folgenden Besonderheiten:

  • Sie sind ohne großen Aufwand (Zeit, Energieverbrauch,… ) durchführbar.
  • Sie führen auch bei gleicher Ausgangssituation nicht zwingend zum gleichen Ergebnis.
  • Das Ergebnis ist nicht notwendigerweise perfekt.

Manche Heuristiken können sogar dann ausgeführt werden, wenn die Ausgangssituation gar nicht vollständig bekannt ist, andere ignorieren ganz bewusst Teile dessen, was sie eigentlich wissen könnten, um so schneller zu Ergebnissen zu gelangen. Wenn wir beispielsweise einem Auto ausweichen müssen, wäre es wenig sinnvoll, bei unserer Reaktion auch die Farben der Blumen am Straßenrand oder den Redeschwall unseres Beifahrers mit einzubeziehen. Um so schnell wie möglich handeln zu können, beschränken wir uns auf die beiden Autos und einige wenige Hindernisse, mit denen wir absolut nicht kollidieren wollen. Alles andere wird ausgeblendet – ob zu Recht oder zu Unrecht, merken wir dann erst hinterher.

In der Informatik verwendet man Heuristiken, wenn ein Problem zu schwierig ist, um exakt gelöst zu werden. Das menschliche Gehirn dagegen verwendet Heuristiken für so gut wie alle Probleme. Die genaue Vorgehensweise ist uns dabei für gewöhnlich nicht bewusst, weshalb manche Forscher argumentieren, dass es sich bei Heuristiken gar nicht um Algorithmen handelt – schließlich können wir häufig nicht Schritt für Schritt angeben, wie wir es geschafft haben, das Problem zu lösen. Andererseits gelingt es der Kognitionspsychologie immer wieder, explizite Beschreibungen für solche unbewussten Heuristiken zu finden, und dabei handelt es sich (bisher jedenfalls) dann eben doch um ein Vorgehen, das man als (randomisierten) Algorithmus beschreiben kann.

Aus diesem Grund werde ich im Folgenden unter einer Heuristik stets eine Art „Quick-and-Dirty“-Algorithmus verstehen: effizient, unter Umständen etwas händewedelnd, meist aber mit passablen Ergebnissen. Wenn dagegen Algorithmen gemeint sind, die immer die gleiche Schrittfolge ausführen und dabei zum optimalen Ergebnis kommen, dann werde ich diese ausdrücklich als klassische Algorithmen bezeichnen.

Zwei Arten von Algorithmen

P.S.: Und ja, mir ist bewusst, dass es noch zahlreiche weitere Möglichkeiten gibt, Algorithmen zu unterteilen und dass es allein zwischen den Extrempunkten „klassischer Algorithmus“ und „Heuristik“ noch viele Zwischenstufen gibt. Aber solange wir hier (noch) nicht in die Feinheiten der theoretischen Informatik eintauchen, lasse ich diese vorerst noch außen vor.

Nachtrag (8.3.2021): Inzwischen habe ich zu dem Thema einen neuen Beitrag geschrieben, in dem die Aussage, dass Heuristiken ein Spezialfall eines Algorithmus sind, korrigiert wird.

Kategorien
Uncategorized

Intuition – zwischen den Extremen

Bauchentscheidungen

In den letzten Wochen habe ich das Buch „Bauchentscheidungen“ des international anerkannten Psychologen Gerd Gigerenzer gelesen. Das (populärwissenschaftlich geschriebene) Buch ist 2007 unter dem Titel „Gut Feelings“ erschienen und hat sich seither sehr erfolgreich verkauft, so dass ich mich gefreut hatte, endlich Zeit dafür zu haben.

Beim Lesen beschlich mich aber zunehmend der Eindruck, dass die Dinge hier der „Message“ zuliebe doch recht einseitig dargestellt werden. Schon der deutsche Untertitel („Die Intelligenz des Unbewussten und die Macht der Intuition“) lässt erahnen, dass Gigerenzer die menschliche Intuition in einem ziemlich positiven Licht sieht. Damit grenzt er sich ganz ausdrücklich von den Arbeiten der bekannten Psychologen Daniel Kahneman und Amos Tversky ab, die in ihrer Forschung immer wieder Beispiele dafür geliefert haben, wie die menschliche Intuition völlig danebenliegen kann.

Der gemeinsame Feind: Der Erwartungsnutzenmaximierer

Als Informatiker stelle ich mir hier die (für Geisteswissenschaftler vielleicht gar nicht nachvollziehbare) Frage, wie angesehene Forscher zu derart unterschiedlichen Einschätzungen gelangen können. Denn die Alltagsbeobachtung sagt ja, dass beides richtig ist: In vielen Situationen kommen wir mit unserer Intuition ziemlich weit, in bestimmten Situationen dagegen versagt unser Bauchgefühl völlig.

Es sagt eine Menge aus über die lange in der Wirtschaftstheorie gepredigten Glaubenssätze, dass diese einfache Alltagsbeobachtung jahrzehntelang geleugnet wurde und dass man stattdessen ohne jede Evidenz behauptete, im Inneren jedes Menschen würden komplexe Optimierungsalgorithmen ablaufen, die uns zu „Erwartungsnutzenmaximierern“ machen. Jeder Mensch, so die These, würde aus den vorhandenen Informationen die für ihn und seine Ziele bestmöglichen Entscheidungen ableiten.

Nun zeigen sowohl die Ergebnisse Gigerenzers als auch die Ergebnisse von Kahneman und Tversky, dass dem überhaupt nicht so ist und dass Intuition ganz anders funktioniert. Allerdings nähern sie sich dem Problem von entgegengesetzten Seiten: Während Gigerenzer zu zeigen versucht, dass Intuition den formalen Algorithmen der klassischen Entscheidungslehre sogar überlegen sein kann, suchen Kahneman und Tversky nach Beispielen, bei denen das Gegenteil der Fall ist.

Extrempositionen

Ein Stückweit ärgert es mich, wenn ausgerechnet in Büchern, die eine große Leserschaft erreichen wollen, solche Extrempositionen bezogen werden. Denn natürlich glaubt weder Gigerenzer, dass die menschliche Intuition immer zu überlegenen Ergebnissen führt, noch sind Kahneman und Tversky davon überzeugt, dass sie immer daneben liegt. Die Wahrheit ist komplizierter, sie hat viel damit zu tun, wer welche Testfragen stellt und mit welcher Absicht.

Diese Situation kennen wir auch aus dem Alltag. Wenn ich möchte, dass mein Gegenüber meinen Test besteht, stelle ich eben einfache Fragen. Und so fragt Gigerenzer danach, welche von zwei Städten wohl größer ist – eine Frage, die deshalb auch mit Halbwissen vergleichsweise gut zu beantworten ist, weil die Antwort mit der Bekanntheit der Stadt korreliert ist. Daraus, dass Menschen diese Frage oft auch dann richtig beantworten, wenn sie die Größe der Stadt gar nicht kennen, folgert er, dass die Intuition (hier konkret: die sogenannte Rekognitionsheuristik) ein mächtiges Werkzeug ist. Doch was wäre, wenn man den gleichen Teilnehmern stattdessen die Frage gestellt hätte, welche der Städte älter ist oder welche südlicher liegt? Hier ist die Korrelation mit der Bekanntheit deutlich weniger ausgeprägt, und ich vermute daher, dass die Ergebnisse nicht annähernd so gut gewesen wären.

So aber wird der Eindruck erweckt, als könne es auf die Frage „wie intelligent ist die menschliche Intuition“ nur eine Antwort geben. Und das ist in einem solch komplexen Thema eine gefährliche Vereinfachung.

Die Folgen der Übertreibung

Die Probleme, die sich aus dem Argumentieren mit Extremen ergeben, kennen wir aus dem politischen Alltag seit Jahren – die Mitte, der Ausgleich, der Kompromiss gehen darüber immer mehr verloren. Und leider treffen wir auch in der Politik den Typ des Wissenschaftlers an, der nur seinen eigenen Standpunkt, sein eigenes Modell, seine eigene Prognose gelten lässt. Typischerweise entstammen diese Wissenschaftler einer Disziplin, in der eindeutige Wahrheiten gar nicht beweisbar sind, was aber durch umso bessere rhetorische Schulung oder größere Überzeugung ausgeglichen wird. Argumentiert wird mit Extremen; gemäßigte, vermittelnde oder gar zweifelnde Standpunkte wirken langweilig, passen nicht in einen Tweet und verkaufen sich weder in den Abendnachrichten noch als Buch.

Dem Vertrauen der Allgemeinheit in die Wissenschaft hat dies nicht gutgetan. Wenn (um ein aktuelles Beispiel zu nennen) die einen Wissenschaftler mit fast schon religiöser Hingabe einen harten, monatelangen Lockdown zur Bekämpfung der Corona-Pandemie fordern, während die anderen mit genau der gleichen Überzeugung jede Form von Lockdown als nutzlosen und gefährlichen Unfug zur Bekämpfung eines maßlos übertriebenen Problems bezeichnen, fragt sich der sprichwörtliche Mann auf der Straße natürlich, wieso er irgendwelches Vertrauen in diese Wissenschaftler haben sollte. Und dieser Zweifel an den Wissenschaft, ihren Methoden und Erkenntnissen wird in den letzten Jahren ja auch immer deutlicher ausgesprochen…

Die wahren Fragen

Was also kann die Wissenschaft tun? Bei aller Freude am Diskurs ist es wichtig, sich daran erinnern, dass Extrempositionen so gut wie nie die Wahrheit sind, sondern dass komplexe Sachverhalte es erfordern, dass man alle Seiten gleichermaßen beleuchtet.

Bei den oben genannten Autoren finden sich zwischen den Zeilen (und vor allem in ihren Forschungsarbeiten) natürlich auch genau diese Grautöne, die echte Wissenschaft auszeichnen. Und wir erkennen auch die Fragen wieder, die ein Algorithmiker instinktiv gestellt hätte:

  • Wie schwer ist das zu lösende Problem überhaupt?
  • Wie eindeutig ist die Aufgabenstellung definiert?
  • Wie vollständig sind die Informationen, über die die Person verfügt?
  • Wie wichtig ist die Qualität der Lösung?
  • Wieviel Zeit hat die Person zur Verfügung?
  • Welche Ressourcen (Denkleistung etc.) hat die Person zur Verfügung?
  • Hat die Person Erfahrung mit vergleichbaren Situationen?
  • Spielt der Zufall eine Rolle, und falls ja: sind die Wahrscheinlichkeiten bekannt?
  • Gibt es einen intelligenten Gegenspieler?

Anhand dieser Fragen wird hoffentlich deutlich, wie viele verschiedene Anforderungen es an eine gute Intuition gibt und auf wie viele Arten man ihre Qualität beurteilen kann. Ich wage – auch aus der Erfahrung der Informatik in diesem Bereich – zu behaupten, dass die Forschung hier noch ganz am Anfang steht. Jeder Schritt dabei ist wertvoll, aber er sollte nicht vorschnell als Teil einer universellen Wahrheit wie „vertrauen Sie ruhig öfter ihrem Bauchgefühl“ verkauft werden.

Kategorien
Uncategorized

Rezension: Algorithms to Live By

Ich möchte gleich zu Beginn ein Buch besprechen, das einen riesigen Beitrag dazu geleistet hat, dass mir der Zusammenhang zwischen „Computer-Algorithmen“ und „Alltags-Algorithmen“ klar geworden ist. Es handelt sich um das Buch „Algorithms to Live By“ (deutsch: Algorithmen für den Alltag) von Brian Christian und Tom Griffiths.

B. Christian, T. Griffiths: Algorithms to Live By. Henry Holt, 2016

In dem Buch zeigen die Autoren anhand zahlreicher Beispiele auf, wie Algorithmen, die ich aus der Informatik seit Jahren kannte, auch im Alltag ganz selbstverständlich zum Einsatz kommen. Und ich muss zugeben, dass ich an manchen Stellen schlicht fassungslos war, dass mir das nicht einmal aufgefallen war, obwohl mir sowohl Algorithmus als auch Alltagssituation durchaus vertraut waren. Umgekehrt werden auch Alltagssituationen besprochen, die wir alle kennen, und mit Algorithmen verknüpft, die vielleicht weniger bekannt sind, die aber nichtsdestotrotz entweder sinnvoll sind oder zumindest ein neues Licht auf unsere tatsächlichen Entscheidungen werfen.

Wer einen ersten Eindruck von den Ideen bekommen will, die in „Algorithms to Live By“ diskutiert werden, dem sei Tom Griffiths‘ TED-Talk von 2017 empfohlen, den man auf Youtube finden kann. Für alle anderen möchte ich hier ein paar Beispiele auflisten:

  • Der Explore-Exploit-Tradeoff zeigt, wie sich das Verhältnis zwischen „Neues ausprobieren“ und „Erprobtes genießen“ im Laufe der Zeit verschiebt und auch, dass sich das tatsächliche Verhalten von Menschen meist erstaunlich nah an der Idealkurve liegt. Ich selbst habe auch gelernt, dass ich nahezu zum mathematisch perfekten Zeitpunkt geheiratet habe…
  • Das Kapitel über das Sortieren im Alltag (Sie sortieren im Alltag gar nicht? Dachte ich auch…) hat mich gleich mehrfach überrascht und mich zu einer Reihe von Überlegungen angeregt, von denen in künftigen Blogeinträgen noch die Rede sein wird.
  • Speicherhierarchien hielt ich ebenfalls für etwas, was nur in Computern vorkommt. Wieder falsch gedacht…
  • Im Kapitel über Netzwerke gab es gleich mehrere Fundstücke, die mir sehr zu denken gegeben haben. So habe ich da gelernt, warum wir genauso wie Computer darauf achten müssen, unsere Eingangspuffer (physisch ebenso wie geistig) nicht zu überlasten, und ich habe verstanden, was mit Messies wirklich passiert. Aber auch die Exponential-Backoff-Strategie fand ich erhellend und die Erkenntnis, dass sie im Umgang mit anderen Menschen sinnvoller sein kann als das gängige „Ich rufe ihn zweimal an, dann kann er mir den Buckel runterrutschen“.
  • Vielleicht das größte Aha-Erlebnis aber hatte ich im Kapitel über Spieltheorie. Mir war gar nicht bewusst, welche Rolle Emotionen bei spieltheoretischen Dilemmata spielen, aber wenn man es einmal gesehen hat, macht es absolut Sinn. Und es zeichnet ein ziemlich hässliches Bild davon, wie weit das derzeit so verbreitete individualistische Weltbild an der evolutionären Wirklichkeit vorbeigeht…

Tatsächlich könnte ich hier noch stundenlang weiterschreiben, denn eigentlich habe ich alle paar Seiten etwas gefunden, was mich weitergebracht oder zumindest zum Nachdenken angeregt hat. Vor allem zeigt das Buch Zusammenhänge auf zwischen zwei Disziplinen, die ich bisher immer isoliert betrachtet habe. Dadurch hat es schon jetzt die Art verändert, wie ich Algorithmik (oder sogar Informatik insgesamt) unterrichte, und es hat mich zu einer Reihe von Forschungsideen inspiriert. Ja, allein dass ich jetzt diese Zusammenfassung schreibe, führt mich in Versuchung, das Buch erneut durchzulesen und dabei diesmal auch den Endnoten und Quellen im Anhang stärkere Bedeutung beizumessen.

Zusammenfassend kann ich nur jedem – egal ob er sich nun für Informatik interessiert oder „nur“ dafür, wie wir Menschen ticken – empfehlen, einen Blick in dieses Buch zu werfen. Ich selbst jedenfalls würde es jederzeit in der Liste der 10 Bücher führen, die ich auf eine einsame Insel mitnehmen würde. Und in Anbetracht der doch ziemlich vielen Bücher, die ich besitze, will das etwas heißen!