Künstliche Intelligenz – ganz klein angefangen

Christoph Pöppe

Am tiefsten Punkt des Meeresgrundes liegt ein Schatz, den es zu finden gilt – möglichst schnell, denn die Konkurrenz ist schon unterwegs. Mit meinem Schiff kann ich übers Meer fahren, an Punkten meiner Wahl ein Lot werfen und damit die Tiefe des Meeres an dieser Stelle bestimmen. Es ist unmöglich, so tief zu tauchen, dass man einen Überblick über die Gegend bekommt. Was ist ein gutes Verfahren, um an den Schatz zu kommen?

Das klingt nach einem klassischen Problem der numerischen Mathematik. Es gibt eine Funktion (die Höhe des Meeresgrundes in Abhängigkeit vom Ort auf der Oberfläche), deren Minimum ist gesucht, ich kann die Funktion zwar auswerten, das heißt an jeder Stelle ihren Wert bestimmen, aber das ist jedes Mal Aufwand, also möchte ich mir mit möglichst wenigen Auswertungen ein ausreichend klares Bild machen und vor allem mit möglichst wenig Aufwand das Minimum finden.

Für das Folgende denken wir uns die Meeresoberfläche und entsprechend den Meeresgrund eindimensional. Das vereinfacht das Nachdenken etwas, ohne dass allzu viel Wesentliches dabei verloren ginge.

Es ist auf jeden Fall eine gute Idee, ein Lot mit Tangentenfunktion zu verwenden. Das heißt, eine Funktionsauswertung misst nicht nur, wie tief der Boden liegt, sondern auch, wie steil er nach der einen oder der anderen Seite abfällt. Wenn zum Beispiel die beiden ersten Messungen so aussehen:

dann liegt es nahe zu vermuten, dass die tiefste Stelle zwischen den beiden liegt. Denn von links nach rechts geht’s bergab, und von rechts nach links ebenso, also muss dazwischen ein Minimum liegen. Und in diesem Fall stimmt es sogar:

Aber das muss nicht immer so sein. Vielleicht haben wir statt der absolut tiefsten Stelle nur eine kleine Mulde entdeckt; zwei solche lokalen Minima sind auch im Bild oben zu sehen. Wir müssen also einerseits ein einmal eingekreistes Minimum immer enger eingrenzen, bis wir den Schatz „mit bloßem Auge“ sehen können (was immer das in der abstrakten Situation heißen mag), andererseits uns im Rest des Meeres umschauen, ob es nicht irgendwo noch tiefer geht. Für Letzteres haben wir wenig Anhaltspunkte; wahrscheinlich ist per Zufall herumzustochern so gut wie jede andere Strategie, oder sogar besser. In dem Online-Spiel „Gradient Descent“ oder leibhaftig in der kürzlich eröffneten Ausstellung „I AM A. I.“, zu der das Spiel gehört, können Sie Ihre eigenen Fähigkeiten zur Schatzsuche erproben und vervollkommnen, mit oder ohne Gegenspieler.

So ziemlich alle Optimierungsprobleme – für die das genannte Online-Spiel nur ein radikal vereinfachtes Beispiel ist – haben dieses Dilemma, in jedem Moment zwischen zwei Strategien entscheiden zu müssen:

– Bin ich einem Minimum auf der Spur und versuche, ihm immer näher zu kommen? Dann werde ich meinen Suchpunkt ein bisschen in der Richtung verändern, in der ich das Minimum erwarte, hoffen, dass der Wert der Zielfunktion – in unserem Beispiel der Meeresboden – dadurch niedriger wird als zuvor, und wenn diese Hoffnung enttäuscht wird, diesen Schritt verwerfen und in eine andere Richtung weiterwandern. Diese Strategie heißt bei den Optimierern „gierig“ („greedy“): Nimm, was du kriegen kannst, und zwar sofort, und lass dich nicht auf eine vorübergehende Verschlechterung ein in der Hoffnung, hinter dem Hügel doch noch ein tieferes Tal zu finden.

– Oder fürchte ich, dass ich in einem lokalen Minimum feststecken könnte, und bin deswegen bereit, große Schritte zu machen und dabei auch Verschlechterungen in Kauf zu nehmen? Nennen wir diese Strategie, die die ganze Vielfalt der Möglichkeiten zu erkunden versucht, „explorativ“.

Allmählich werden Sie ein Gefühl dafür entwickeln, in welchem Verhältnis man die beiden Strategien einsetzt und wohin genau man in der konkreten Situation stochert: ein Lernprozess! Und das ist ein Beispiel für einen Lernprozess, den auch eine Maschine vollziehen kann. Typischerweise handelt es sich dabei um ein neuronales Netz; das ist ein Gerät, das dem Netz der Nerven in unserem Gehirn nachempfunden ist, allerdings in einer sehr groben Weise. Die klugen Gedanken, die wir uns machen, zum Beispiel „wenn es links abwärts geht und rechts davon aufwärts, dann muss dazwischen ein Minimum liegen“, sind in einem neuronalen Netz nicht einprogrammiert (wohl aber in dem „Bot“, dem Computerprogramm, das man sich in dem Online-Spiel als Gegenspieler dazuschalten kann). Das Netz lernt die entsprechenden Prinzipien, und zwar aus Erfahrung: indem es sehr viel mehr Situationen durchprobiert als unsereins. Darin ist es auch noch viel schneller als wir, weil es sich über jede einzelne Situation nicht entfernt so viele Gedanken macht. Am Ende erledigt das Netz die Schatzsuche um ein Vielfaches besser als jeder Mensch; aber auf unsere Ideen kommt es nicht, noch nicht einmal in irgendeinem übertragenen Sinn.

Das ist die große Schwäche der neuronalen Netze: Sie können sehr viele Aufgaben grandios bewältigen, aber niemals erklären, wie sie es eigentlich gemacht haben. In jedem übertragenen Sinn: Alles, was das Netz gelernt hat, steckt in einer – meistens sehr großen – Ansammlung von Zahlen, den „synaptischen Gewichten“. Die kann man problemlos aus dem Netz auslesen. Aber daraus etwas zu erschließen ist schwierig bis unmöglich. Wenn eine Bank ein solches Netz, an vergangenen Erfahrungen geschult, zur Einschätzung der Kreditwürdigkeit nutzt und ein Kunde fragt, warum sein Kreditantrag abgelehnt wurde, dann hat die Bank ein Problem.

Die Kunst, zwischen den beiden Strategien „gierig“ und „explorativ“ geschickt zu wechseln, mussten die Optimierer schon beherrschen, bevor die neuronalen Netze für derartige Aufgaben zur Verfügung standen. Und zwar auch bei richtig großen Problemen.

Der Klassiker unter ihnen ist das „Problem des Handlungsreisenden“, in der älteren Literatur zitiert als „travelling salesman problem“ (TSP), neuerdings gegendert als „travelling salesperson problem“. Der oder die Handlungsreisende muss, sagen wir, 20 vorgegebene Städte besuchen, darf aber deren Reihenfolge frei wählen und möchte den Weg mit der kürzesten Gesamtlänge finden. So viele Staubsaugervertreter*innen gibt es gar nicht mehr, dass deren Reiseplanung größere gedankliche Anstrengungen rechtfertigen würde; aber das TSP ist das, was man ein „benchmark problem“ nennt: Jeder, der ein neues Optimierungsverfahren erfunden hat, muss vorzeigen, wie gut es ein TSP löst, und dadurch wird es mit den Vorgängerverfahren vergleichbar. Und viele kombinatorische Optimierungsprobleme sind dem TSP so ähnlich, dass sich ein Lösungsverfahren für das benchmark problem leicht auf sie übertragen lässt: Tourenplanung für Lastwagen, Zuweisung von Aufgaben an verschiedene Maschinen, Fahrpläne für das U-Bahn-Netz, Stundenpläne für Schulen …

Kombinatorische Optimierungsprobleme unterscheiden sich von dem Schatzsuche-Spiel nicht nur in der schieren Größe, sondern auch noch in anderer Hinsicht. Man sucht den tiefsten Punkt in einem Raum mit sehr vielen Dimensionen. Und der Meeresgrund ist alles andere als glatt. Um genau zu sein, es gibt ihn gar nicht so richtig. Will sagen: Es gibt keine reellen Koordinaten, an denen man wackeln kann, um sich auf dem Meeresgrund zu bewegen. Beim TSP gibt es ohnehin nur endlich viele denkbare Lösungen – alle Reihenfolgen der abzuklappernden Städte –; da ist mit Begriffen wie Tangenten und Minimumssuche nach dem Schulverfahren sowieso nichts zu machen. Immerhin: Es gibt kleine Änderungen, die haben auch kleine Wirkungen, sozusagen eine zarte Andeutung von Stetigkeit. Wenn man die nicht hätte, bliebe einem sowieso nichts übrig, als blind in der Lösungsmenge herumzustochern.

Für den Wechsel zwischen gierigen und explorativen Strategien gibt es ein eingeführtes und sehr erfolgreiches Verfahren namens „simulated annealing“ („simuliertes Tempern“). Die Bezeichnung ist aus der Technik der Stahlherstellung entlehnt: Um das Material besonders hart und zäh zu machen, unterwirft man es mehreren Zyklen aus Erhitzung und Abkühlung. Erhitzen bringt die Atome zum Zappeln und weicht deren Bindungen etwas auf; Abkühlen gibt ihnen die Gelegenheit, neue und hoffentlich stabilere Bindungen zu knüpfen. Beim Optimieren ist Erhitzen die explorative Phase; der Prozess, der in dem abstrakten Raum der Möglichkeiten nach der optimalen Stelle sucht, bekommt sehr viel Bewegungsenergie und springt entsprechend wild in der Gegend herum. Beim Abkühlen kollert er allmählich an die tiefste Stelle, die aus seiner gegenwärtigen Position erreichbar ist.

Noch merkwürdiger ist der Sintflut-Algorithmus. Für sein Verständnis muss man bei der Zielfunktion das Vorzeichen umdrehen. Man sucht also nicht die tiefste Stelle im Meer, sondern den höchsten Berggipfel – was vom mathematischen Standpunkt aus ein völlig belangloser Wechsel der Perspektive ist. Am Anfang nimmt der Sintflut-Algorithmus jede Verschlechterung ohne Weiteres in Kauf. Der Prozess wandert also vollkommen ziellos durch die Landschaft. Aber dann wird diese Landschaft geflutet, und man darf überallhin gehen, nur nicht ins Wasser. Erstaunlicherweise landet man dabei in der Regel nicht auf irgendeinem mickrigen Hügel, sondern meistens auf einem Gipfel akzeptabler Höhe, nur knapp unter dem Mount Everest.

Oder der Bomben-Algorithmus, interessant für Probleme wie zum Beispiel die Aufteilung von Paketen mit verschiedenen Zielen auf verschiedene Lastwagen, wo es bereits ein erheblicher Aufwand ist, überhaupt eine „zulässige Lösung“ zu finden, also eine nicht unbedingt optimale, aber wenigstens praktikable Aufteilung. Kaum hat man eine solche zulässige Lösung gefunden, wirft man eine Bombe, das heißt man zerstört gezielt einen Teil der Lösung und baut sie dann wieder auf, nach einem gierigen Verfahren. Die Ergebnisse sind besser, als man von einem derart brutalen Vorgehen erwarten würde.

Alle diese Verfahren sind ausgiebig an echten Problemen erprobt worden. Erhebliche menschliche Intelligenz wurde aufgewandt, um die Details der Verfahren so zu gestalten, dass man in möglichst kurzer Zeit zu möglichst guten Lösungen kommt. Kann künstliche Intelligenz es der menschlichen an dieser Stelle gleichtun oder sie sogar übertreffen?

Das sieht zumindest im Moment eher durchwachsen aus. Vor etwa 20 Jahren blieben die Resultate noch in enttäuschender Weise hinter den hohen Erwartungen zurück. Die tiefen neuronalen Netze, die in jüngerer Zeit so spektakuläre Erfolge eingefahren haben, kamen erst danach. Aber auch sie haben in der kombinatorischen Optimierung nicht ohne Weiteres den Durchbruch gebracht. Das scheint erst neuerdings mit den grafischen neuronalen Netzen zu gelingen. Und auch die haben noch unter einem Standardproblem ihrer Art zu leiden: Sie brauchen sehr viele Trainingsdaten. Man muss also zunächst unter entsprechend hohem Aufwand eine große Zahl von Beispielproblemen gelöst haben und dem Netz als Trainingsmaterial vorlegen, damit dieses wenigstens ungefähr weiß, wo’s langgeht. Dann bringt es immerhin gute Lösungen zu Problemen vom selben Typ. Das ist für die Großspedition, die täglich ihre Lastwagenflotte aufs neue auf den Weg schicken muss, sogar attraktiv.

Auf das neuronale Netz, das vollkommen eigenständig neue Strategien entwickelt, wie das beim Go-Spiel gelungen ist, werden wir wohl noch ein Weilchen warten müssen.

The post Künstliche Intelligenz – ganz klein angefangen originally appeared on the HLFF SciLogs blog.