Lernen und Vergessen

Das Lösen bestimmter schwieriger Probleme auf dem Computer erfordert Lernen und Vergessen. Lernen bedeutet hier, neue Einsichten über ein schwieriges Problem herzuleiten. Vergessen, einen Teil dieser Einsichten wieder zu verwerfen.

Beispiel: Automobilproduktportfolio

Ein Beispiel für ein derartiges Problem ist das Erstellen von technischen Produkten aus einem Baukasten. Ein Automobilhersteller weiß genau, welche Teile er für den Bau eines bestimmten Autos benötigt. Typischerweise sind das mehrere tausend. Angefangen bei der kleinsten Schraube bis hin zum fertigen Motor und Chassis gibt es einen Plan, wie die Teile zusammenpassen. Diese Teile zu verwalten stellt ein einfaches Problem für den Computer dar: Wenn an unserem Auto eine Reparatur notwendig wird, kann der Händler in Sekunden feststellen, ob er ein für die Reparatur benötigtes Teil auf Lager hat.

Ein schwieriges Problem ist die Frage, ob der Automobilhersteller mit seinen aktuellen Teilen ein Auto bauen kann, das bestimmte Eigenschaften hat, beispielsweise nur 6 l Kraftstoff auf 100 km verbraucht und eine Höchstgeschwindigkeit von 200 km/h erreicht. Um diese Frage mit einem Computer zu beantworten, reicht es nicht aus, einen Plan für ein konkretes Auto zu haben. Vielmehr muss es ein Regelwerk darüber geben, wie vorhandene Teile und Komponenten zusammengefügt werden können. Statt eines Plans "für Auto x wird Motor z eingebaut" bedarf es einer Regel "Motor z passt in jedes Auto, das ein Volumen von 0,5 m³, eine Breite von 1,10 m und eine Länge von 0,6 m im Motorraum bereitstellt.“ Eine solche Modellierung beschreibt nicht nur die Auswahl der aktuell gebauten Autos, sondern alle Varianten des Autos, die produziert werden könnten. Führende Automobilhersteller pflegen bereits solche Modellierungen ihres Produktportfolios, wenn auch nicht bis zu dem Detail von technischen Zusammenhängen. Aber warum ist das Problem schwierig?

Bereits das aktuell gebaute Portfolio eines Automobilherstellers umfasst zu viele Autos, als dass man diese einfach bezüglich obiger Eigenschaften testen könnte. Ein konkretes Auto könnte 5 verschiedene Chassis (Coupe, Cabriolet usw.), 10 verschiedene Motoren, 5 verschiedene Getriebe, 15 verschiedene Farben, 10 verschiedene Polster, 10 verschiedene Räder etc. haben. Das sind über 3 Millionen verschiedene mögliche Autos, ohne die Betrachtung weiterer Ausstattungsmöglichkeiten. Alle diese Autos auf obige Eigenschaften zu testen, würde schon zu lange dauern. Nun könnte man annehmen, dass die Farbe eines Autos nichts mit den obigen Fahreigenschaften zu tun hat und daher irrelevant ist. Aber zum einen beschreibt genau dies das Lernen der Einsicht "Farbe ist irrelevant" und zum anderen stimmt dieser Schluss in der Praxis oft nicht, da Farben bei Autos aus Marketinggründen fast immer mit anderen Komponenten, wie einem bestimmten Chassis, verknüpft sind.

Lernen

Eine Aufzählung aller Varianten funktioniert also nicht. Aktuelle Verfahren lösen das Problem, indem sie aus den bekannten Regeln neue Einsichten lernen. Für unser Beispiel könnte dies bedeuten: "Kein Motor erfüllt die Verbrauchsvorgabe von 6 l pro 100 km in Kombination mit der großen HiFi-Anlage" etc.

Die Akkumulation solcher Einsichten erlaubt es, den Variantenraum so einzuschränken, dass eine Antwort auf die ursprüngliche Frage in akzeptabler Zeit berechnet werden kann. Die Antwort könnte beispielsweise "nein" sein. Die Antwort "nein" ist aber wenig zufriedenstellend, weil sie das "warum" nicht erklärt. Das explizite Lernen von Einsichten unterstützt auch die Generierung von Erklärungen. Eine Antwort könnte sein: "Der Luftwiderstand aller Fahrzeuge ist so hoch, dass entweder nicht die Verbrauchs- oder die Höchstgeschwindigkeitsvorgabe erfüllt werden.“

Vergessen

Die Herausforderung von Computerprogrammen, die nach dem Prinzip „Lernen durch Generierung neuer Einsichten“ funktionieren, ist die schiere Anzahl der generierten Einsichten. Moderne Programme generieren zwischen 1000 und 100.000 neue Einsichten pro Sekunde. Zu viele, um alle verarbeiten zu können, zumal die neuen Einsichten wiederum weitere Einsichten generieren. Daher müssen Einsichten vergessen werden können. Zudem sind nicht alle Einsichten nützlich, so hat die Einsicht "eine Anhängerkupplung ist nicht mit einem Heckfahrradträger kombinierbar" vermutlich nichts mit dem Ausgangsproblem zu tun.

Das Trennen von nützlichen von nutzlosen Einsichten ist nicht einfach, es ist beweisbar genau so schwierig wie das eigentliche Problem. Hier haben sich zwei Techniken etabliert. Zum einen können alle Einsichten vergessen werden, für die es eine allgemeinere gibt, so wird "Motor x mit 3,4 l Hubraum erfüllt nicht die Verbrauchsanforderungen" durch "alle Motoren mit mehr als 3 l Hubraum erfüllen nicht die Verbrauchsanforderungen" subsumiert. Anhand dieser Technik lassen sich etwa ein Drittel aller unnötigen Einsichten eliminieren. Weitere werden dann heuristisch eliminiert, indem beispielsweise der Abstand zwischen einer Einsicht zu einer Vorgabe gemessen wird. Wenn etwa eine Einsicht zur Anhängerkupplung nicht in wenigen Schritten über das Regelwerk mit dem Verbrauch in Verbindung gebracht werden kann, dann wird sie erst einmal als nutzlos gelöscht.

Forschung

Wir arbeiten daran, Regelwerke, die arithmetische und logische Zusammenhänge kombinieren, praktisch anwendbar zu machen. Im Allgemeinen ist diese Klasse von Regelwerken unentscheidbar, es gibt also Regelwerke und Probleme, die sich beweisbar nicht lösen lassen. Regelwerke aus der Praxis sind üblicherweise leichter zu lösen, aber auch für diese müssen spezifische Verfahren entwickelt werden, um dann auch für komplexere Probleme, wie die Modellierung eines Automobilprodukt-Portfolios inklusive technischer Zusammenhänge, Lösungen in akzeptabler Zeit zu berechnen. Die Hauptanwendungen dieser Techniken sind der Nachweis von Eigenschaften von Computersystemen selbst. Dank dieser Techniken ist heute etwa der Intel Pentium Bug von 1994 so nicht mehr möglich. Dieser Hardware-Fehler führte bei Gleitkomma-Divisionen mit bestimmten, relativ wenigen Wertepaaren zu ungenauen Ergebnissen.

Literaturhinweise