IQ-Test für KI: Die ARC Challenge

ARC IQ-Test für KI|ARC IQ Test für KI|Automat zur Generierung valider Bildverarbeitungsalgorithmen|Ablauf - IQ Test für KI|ARC IQ-Test für KI|||
© ML2R

Künstliche Intelligenzen, wie man sie aus Science-Fiction Filmen kennt, sind meist Generelle Künstliche Intelligenzen. Sie sind in der Lage jedwede Aufgabe durch eine Kombination von gesammeltem Wissen und logischem Denken zu lösen, auch und besonders dann, wenn die Aufgabe noch nie vorher gelöst wurde. Eine solche Künstliche Intelligenz zu entwickeln wird daher vermehrt als Heiliger Gral der KI bezeichnet.

Aktuell werden Verfahren des Maschinellen Lernens benutzt, um speziell definierte Aufgaben aus einer Sammlung von Beispielen zu lernen. Beispiele hierfür sind die Gesichtserkennung auf Bildern oder das Übersetzen von Text zwischen zwei Sprachen. Sobald das Verfahren trainiert wurde, beherrscht es, anders als Menschen, im Allgemeinen allerdings nicht die Abstraktionsleistung verwandte Probleme zu lösen. So kann ein Modell zur Gesichtserkennung nicht ohne weiteres eine Person mit einer Mund-Nasen-Bedeckung identifizieren, solange es nicht auf solchen Beispielen trainiert wurde.

In seinem Artikel On the Measure of Intelligence beschreibt François Chollet die Notwendigkeit für einen Benchmark, welcher akkurat die generelle Intelligenz von KI quantifizieren kann. Dies käme einem IQ-Test für KI gleich. Als Resultat seiner Überlegungen veröffentlichte er den Abstraction and Reasoning Corpus.

Der Abstraction and Reasoning Corpus

Der Abstraction and Reasoning Corpus (ARC) besteht aus vielen verschiedenen Aufgaben in Form von Bilddaten. Jedes Bild besteht aus einem rechteckigen Gitter beliebiger Größe (zwischen 1×1 und 30×30 Pixel), dessen Zellen mit einer von neun Farben gefüllt ist. Aus zwei bis vier Trainingsbeispielen mit Lösung soll die KI die Logik der jeweiligen Aufgabe erlernen, um sie dann auf ein bis zwei weitere Beispielbilder ohne vorgegebene Lösungen anzuwenden. Typische Aufgaben benötigen ein Verständnis von Geometrie und logischem Denken. So müssen beispielsweise Formen einer speziellen Farbe verschoben, ausgeschnitten, dupliziert oder fortgeführt werden (siehe nachstehende Abbildung). Solche Aufgaben sind typischerweise für Menschen leicht und schnell verständlich.

example task 1 - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)
© ML2R
Eine Beispielaufgabe aus dem ARC. Es soll aus jedem Bild der oberen Reihe die Form mit der kleinsten Fläche ausgeschnitten werden. Der KI werden die ersten drei Paare zum Training zur Verfügung gestellt. Anhand des letzten Bildes wird evaluiert, ob die KI die Logik der Aufgabe gelernt hat.

Die Schwierigkeit bei diesem Datensatz besteht zum einen darin, dass es sehr viele verschiedene Aufgaben mit grundlegend verschiedener Logik gibt. Um die 400 Aufgaben werden im Trainingsdatensatz bereitgestellt, welche alle von dem gleichen Ansatz gelöst werden müssen. Eine zusätzliche Schwierigkeit entsteht dadurch, dass sich nicht nur die Bildgrößen zwischen den Aufgaben verändern können, sondern auch innerhalb der Aufgabe verschiedene Größen auftreten können. Teilweise ist sogar die Ausgabegröße nicht gleich der Eingabegröße, wenn beispielsweise bestimmte Formen aus der Eingabe ausgeschnitten werden sollen. Viele maschinelle Lernverfahren erwarten allerdings feste Ein- und Ausgabedimensionen der Daten.

Um den Datensatz zu testen, veranstaltete François Chollet eine öffentliche Challenge auf der Data Science Plattform Kaggle. Registrierte Gruppen erhielten den Datensatz und konnten berechnete Lösungen zur Evaluation an Kaggle schicken. Auf einer öffentlichen Rangliste wurde daraufhin die Anzahl der korrekt gelösten Aufgaben jedes Teams aufgeführt. Mit unserem im Nachfolgenden beschriebenen Ansatz erreichten wir zum Abschluss der Challenge eine Platzierung unter den besten 30 von über 900 teilnehmenden Gruppen.

Lösungsansatz mittels grammatikalischer Evolution

Zunächst verfolgen wir den Ansatz, Operationen auf Gitterbildern als domänenspezifische Sprache zu definieren. Zusätzlich zu den Bildern definieren wir hierbei ein Schichtobjekt, welches aus einer Liste von mehreren Bildern besteht. Dieser Ansatz findet sich auch häufig in Bildverarbeitungssoftware, wie Adobe Photoshop oder GIMP, wieder. Die Grammatik der domänenspezifischen Sprache besteht aus vier verschiedenen Operationstypen:

  • T (Bild -> Bild): Operationen, welche ein Bild direkt verarbeiten und ein Bild zurückgeben (zuschneiden, rotieren, spiegeln etc.)
  • S (Bild -> Schichten): Operationen, welche ein Bild in mehrere Schichten aufteilen (duplizieren, in Farbkanäle aufteilen etc.)
  • L (Schichten -> Schichten): Analog zu T, allerdings für Schichtobjekte (sortieren der Schichten nach vorgegebenen Kriterien, filtern etc.)
  • J (Schichten -> Bild): Invers zu S (Vereinigung der Schichten zu einem Bild etc.)
lwda automata - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)
© ML2R
Automat zur Generierung valider Bildverarbeitungsalgorithmen. X beschreibt hierbei ein einzelnes Bild, während X ein Schichtobjekt darstellt. Es wird festgelegt, dass sowohl Start- als auch Endzustand wieder ein Bild sein müssen, wodurch jeder generierte Ausdruck zu einem validen Bild führt.

Mithilfe eines evolutionären Algorithmus generieren wir aus der definierten Grammatik Syntaxbäume und mutieren, rekombinieren und selektieren diese anhand ihrer Güte auf den Beispieldaten. Dieser Ansatz wird für jede Aufgabe im Datensatz wiederholt. Wir nehmen an, dass ein korrekter Syntaxbaum gefunden wurde, sobald er alle Beispieldaten korrekt löst. Wir lösen dann damit die verbleibenden Aufgaben ohne Lösung. Sollte innerhalb eines gewissen Zeitfensters kein Syntaxbaum alle Beispielaufgaben lösen, wird die Aufgabe übersprungen.

lwda ablauf - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)
© ML2R
Generierte Lösung unseres Ansatzes zu der obig genannten Beispielaufgabe. Zunächst wird die Farbe “c1” (schwarz) aus dem Bild entfernt. Danach wird das Bild anhand der vorhandenen Farben in einzelne Schichten aufgeteilt und absteigend nach Fläche der einzelnen Farben sortiert. Mit “top” wird die oberste Schicht dann ausgewählt und zugeschnitten.

Mit diesem Ansatz ist es uns gelungen 3% der geheimen Testaufgaben zu lösen, aus denen die öffentliche Rangliste erstellt wird. Auch wenn dies niedrig erscheint, so erreichten wir Platz 28 von über 900 Gruppen. Dies verdeutlicht, wie schwierig es ist für den ARC eine gute Lösung zu finden. Denn: Durch die starke Diversität der Aufgaben ist es schwierig eine einheitliche Menge an vorgegebenen Funktionen zu definieren, aus denen Ausdrücke für verschiedenste Aufgaben generiert werden können. Jede weitere Funktion führt zudem zu mehr Komplexität und vergrößert den Suchraum. Auch wenn die ARC Challenge einen interessanten Einblick in die Möglichkeiten von Genereller Künstlicher Intelligenz gibt, so zeigt sie doch ebenso deutlich, wie weit diese noch in der Zukunft liegt.

Weitere Informationen im zugehörigen Paper:
Solving Abstract Reasoning Tasks with Grammatical Evolution Raphael Fischer, Matthias Jakobs, Sascha Mücke, Katharina Morik. Lernen, Wissen, Daten, Analyse (LWDA), 2020, PDF.

Matthias Jakobs

Matthias Jakobs beschäftigt sich in seiner Forschung intensiv mit vertrauenswürdigem maschinellen Lernen. Derzeit arbeitet er an verschiedenen Problemen, darunter die Bereitstellung von Garantien für Erklärungsmethoden, die auf Shapley-Werten basieren, sowohl in der Theorie als auch in der praktischen Anwendung. Zudem untersucht er die Kombination von Erklärbarkeitsmodellen mit Bayesschen Neuronalen Netzen (BNN). Sein besonderes Interesse gilt der Beleuchtung des Entscheidungsfindungsprozesses von Black-Box-Modellen. Ziel ist es, sowohl Nutzern als auch Experten mehr […]

Weitere Blogartikel