Programmieren und KI: Künstliche Intelligenz in der Softwareentwicklung
Seite 3: Praktisch und schnell: Code aus Beispielen
Eine intuitive Art, das gewünschte Verhalten eines Programms festzulegen, ist die Angabe von Beispielen. Microsoft-Anwender kennen diese Form der Spezifikation durch das Flash-Fill-Feature (Blitzvorschau) in Excel. Gibt man in Excel Daten ein, die ein bestimmtes Muster aufweisen, etwa die Trennung vollständiger Namen in Vor- und Nachnamen, dann kann Excel dieses Muster erkennen und eine Tabelle automatisch vervollständigen.
Hinter den Kulissen verwendet Excel eine Programmiersprache für String-Transformationen mit Operationen für reguläre Ausdrücke, Fallunterscheidungen, Schleifen und Ähnliches. Für das automatische Vervollständigen der Tabelle in der folgenden Abbildung generiert Excel ein Programm in dieser Sprache, das aus der ersten Spalte, in der die vollständigen Namen aufgelistet sind, eine zweite Spalte mit den Nachnamen erzeugt. Die vollständigen Namen können dabei entweder in der Form "Vorname Nachname" oder in der Form "Nachname, Vorname" angegeben sein.
Das Programm extrahiert dazu aus einem gegebenen String das Wort vor dem Komma oder – falls der String kein Komma enthält – das letzte Wort im String. Das Flash-Fill-Feature erzeugt dieses Programm in weniger als 0,1 Sekunden aus den vom Nutzer vorgegebenen Beispielen. Der Codegenerierungsalgorithmus berechnet dazu zunächst für jede Beispielzeile eine Menge von Programmen, deren Ergebnis diesem Beispiel entspricht. Wenn ein Programm darunter ist, das in allen Beispielen funktioniert, dann ist dieses Programm die gesuchte Lösung. Andernfalls werden die Beispiele in verschiedene Klassen partitioniert, die jeweils eine gemeinsame Lösung haben. Hier im Beispiel haben "Anna-Maria Schmidt" und "Julia Richards" dieselbe Lösung (das letzte Wort), "Brinkmann, Klaus" dagegen eine andere (das Wort vor dem Komma). Die verschiedenen Klassen werden dann mithilfe einer Fallunterscheidung kombiniert.
Das Prinzip hinter Flash Fill ist die Syntax-Guided Synthesis (SyGuS). Beim Einsatz von SyGuS besteht der zentrale Schritt darin, die Menge aller möglichen Programme mithilfe einer domänenspezifischen Sprache (DSL) zu formalisieren. Frameworks wie PROSE von Microsoft berechnen dann aus den gegebenen Beispielen ein möglichst einfaches, in der DSL ausgedrücktes Programm, das sich auf den Beispielen richtig verhält.
Anschließend lässt sich das Programm auf neuen Daten ausführen. SyGuS ist in vielen Anwendungen einsetzbar: bei der Analyse von Logfiles, beim Extrahieren von Daten aus PDF-Dokumenten und beim Codieren von Datenbankabfragen als SQL-Abfragen. SyGuS spielt seine Stärken immer dann aus, wenn es sich um einen überschaubaren und kompakt als DSL beschreibbaren Aufgabenbereich handelt.
