Thomas Endres & Samuel Hopstock 26. Februar 2019

Machine Learning on Source Code

Wenn wir darin intuitiv Muster erkennen können, ist es wahrscheinlich, dass ein künstliches System diese auch finden kann. © Adobe: monsitj / stock.adobe.com / 246289655 — © Adobe: monsitj

Künstliche Intelligenz in Form von maschinellem Lernen ist heutzutage in sehr vielen Bereichen unseres Lebens präsent. Sehr verbreitet ist Machine Learning bei der Erkennung und Klassifizierung von Bildern und der Analyse natürlicher Sprache. Der Einsatz von Machine Learning ist überall dort sinnvoll, wo Aufgaben wiederholt durchgeführt werden und werden müssen. Durch die Wiederholung ergibt sich eine große Anzahl an Beispielen, mit denen wir unser Machine-Learning-Modell trainieren können. Wenn wir darin intuitiv Muster erkennen können, ist es wahrscheinlich, dass ein künstliches System diese auch finden kann. Ein spannendes Anwendungsgebiet ist etwa die Analyse von Source Code: Hier können wir als Menschen Muster erkennen, die Auswirkungen auf das Verhalten des Programms haben. Folglich scheint Machine Learning hier ebenfalls ein vielversprechender Ansatz zu sein.

In diesem Text möchten wir uns hauptsächlich anhand eines konkreten Beispiels mit der Anwendung von Machine Learning auf Source Code befassen: Der Vorhersage von Testergebnissen. In vielen Softwareentwicklungsprozessen existiert eine große Anzahl an Test Cases. Die Ausführung dieser Test Cases nimmt üblicherweise viel Zeit in Anspruch. Daher überlegen sich die Entwickler dieser Projekte, wie häufig und gründlich man neue Codeänderungen testen möchte. Eine gängige Praxis ist es, nur eine kleinere Auswahl sogenannter Smoke-Tests bei jeder Änderung laufen zu lassen. Diese wählen die Entwickler so, dass sie die wichtigsten Funktionen der Software überprüfen. Häufig wird nur einmal pro Tag, beim Nightly-Build, die vollständige Test-Suite ausgeführt.

Ein schwieriges Problem bei der Auswahl der richtigen Smoke-Tests ist allerdings, diejenigen Tests zu wählen, die gravierende Fehler schnell finden. Menschen haben eine Intuition dafür, welche Art von Codeänderungen Auswirkungen auf welche Tests haben könnten. Als Entwickler möchte ich aber nicht bei jeder Änderung selbst die wichtigsten Tests aussuchen. Daher wäre ein automatisiertes System zur Erkennung der relevanten Testfälle hier hilfreich. In Gebieten, in denen Menschen mit genug Erfahrung und Daten relevante Vorhersagen treffen können, findet sich wie gesagt häufig auch ein vielversprechender Ansatz im Bereich des Machine Learning.

Die Analyse von Source Code spielt im Bereich des Machine Learning derzeit noch keine so große Rolle wie die von Bildern oder natürlicher Sprache. Deshalb gibt es noch keine wirklich etablierten Standardverfahren, wie man Source Code als Datenquelle für Vorhersagen nutzen kann. Man könnte diesen natürlich als normalen englischsprachigen Text behandeln. Allerdings verliert man dann den ganz eigenen semantischen Kontext zwischen den einzelnen Anweisungen sowie viele weitere semantische Informationen.

Man muss also andere Ansätze für Machine Learning auf Source Code finden. Dabei sind wir auf einige zentrale Fragestellungen gestoßen, auf die wir in diesem Artikel eingehen wollen:

Welche Eingabe- und Ausgabedaten können wir für das Modell verwenden und woher bekommen wir einen Trainingsdatensatz ausreichender Größe?
Wie können wir diese Daten mathematisch als Vektoren darstellen, damit wir überhaupt Machine-Learning-Algorithmen anwenden können?
Welche Modelle können zum Training verwendet werden und welche Stolperfallen gibt es, die wir beachten müssen?
Wie könnte eine Machine-Learning-Komponente in den Arbeitsfluss eines Programmierers eingebaut werden?

Trainingsdaten

Für das Training eines überwachten Machine-Learning-Modells müssen wir Trainingsdaten bereitstellen. Die Basis dieser Trainingsdaten ist immer ein Projekt, das aus einer bestimmten Menge an Code besteht. Zusätzlich existiert für unser Beispiel der Vorhersage von Testfehlschlägen eine Sammlung von Tests, die die aktuelle Funktionalität überwacht. Ein einzelnes Element in unseren Trainingsdaten besteht aus einem Satz von Änderungen an der Codebasis. Auf dem Stand vor und nach der Änderung werden die Tests ausgeführt und diese Testergebnisse bilden den Ausgabeteil des Datensatzes.
Glücklicherweise gibt es eine gute Quelle, die solche einzelnen Änderungssets sammelt: Ein Versionskontrollsystem wie beispielsweise Git. Indem man durch alle Commits iteriert, die Codeänderungen festhält und auf dem jeweiligen Stand die Test-Suite ausführt, lässt sich hier einfach und automatisiert eine gute Sammlung an Trainingsdaten aufbauen.

Als Nutzer eines lernenden Systems möchten wir so viele Beispieldaten wie nur möglich zum Lernen bereitstellen. Manchmal ist das aber nicht einfach machbar, etwa wenn unsere Versionskontrolle bisher noch nicht viele Commits beinhaltet. Selbst die größten Git-Repositories besitzen vielleicht einige tausend Commits, aber nicht so viele Elemente wie sie in gängigen Machine-Learning-Datensätzen enthalten sind.

In diesem Fall verwendet man häufig eine Technik namens "Data Augmentation", die automatisierte Vergrößerung des Trainingsdatensatzes. Bei Bildern wendet man zum Beispiel zufällige Rotationen oder vergleichbare Manipulationen auf den Daten an. Analog dazu haben wir den sogenannten MonkeyRunner entwickelt, der eine ähnliche Vergrößerung des Datensatzes auch auf Source Code ermöglicht.

MonkeyRunner: Automatisierte Codeänderungen

Der MonkeyRunner verhält sich wie ein sprichwörtlicher Affe, der im Source Code für Unordnung sorgt. Er sucht sich einige Dateien im Projekt aus, die er verändern will. Dann ist das Ziel, den Code so zu mutieren, dass zwar die Funktionalität verändert wird, die geänderte Klasse aber immer noch kompilierenden und ausführbaren Java-Code beinhaltet.

Dafür haben wir auf die Bibliothek "JavaParser" zurückgegriffen. Diese extrahiert aus einem Java-Programm den zugehörigen Abstract Syntax Tree (AST). Dessen Darstellung gruppiert die einzelnen Zeichen und Wörter im Code in dessen semantische Programmbausteine (Tokens) und ordnet sie als Baum an. Diese Programmdarstellung wird auch in Compilern verwendet, um aus dem Code die eigentliche Struktur zu ermitteln. Ein darin verwendetes Token ist beispielsweise ein Ausdruck, in dem einer Variable ein Wert zugewiesen wird (im Java-Compiler "AssignExpression" genannt). Ein weiteres Beispiel wäre ein Ausdruck, der eine Schleife beschreibt.

Im AST verändert der MonkeyRunner nun die Parameter einiger Tokens. Beispielsweise werden Additionen zu Subtraktionen, die Werte von Konstanten verändern sich und logische Operatoren werden vertauscht. Im Anschluss an diese Manipulationen kann der JavaParser den veränderten AST wieder als Java-Code abspeichern. Dass das zu ändernde Programm in seiner AST- und nicht der Textdarstellung verändert wird, macht die Entwicklung eines solchen MonkeyRunners modular. Um eine neue Art von Modifikation zu implementieren, müssen wir nicht auf die korrekte Textform des Codes achten. Stattdessen reicht es, betroffene Tokens im Syntaxbaum zu bearbeiten.

Sobald der MonkeyRunner einen Datensatz erzeugen soll, nimmt er zunächst einige zufällige Änderungen am Code vor. Auf dieser Codebasis werden dann die Testfälle ausgeführt und die Ergebnisse festgehalten. Unserer Erfahrung nach reichen kleine Änderungen aus, um einige Tests fehlschlagen zu lassen, die vorher noch erfolgreich waren.

Nachdem auf diese Art einige Trainingsdatensätze gesammelt wurden – einerseits aus der Versionskontrolle, zusätzlich noch mit dem MonkeyRunner vervielfältigt – sind wir bereit für den nächsten Schritt: Wie kann ich diese Daten mathematisch darstellen, damit sie für Machine Learning geeignet sind?

Vektordarstellungen für Code-Änderungen

Machine Learning ist in seiner Basis letztlich nichts anderes als die Anwendung verschiedener mathematischer Algorithmen zum Zwecke der Klassifikation oder Regression. Für diese benötigt man folglich auch eine mathematische Darstellung aller Daten, mit denen die Algorithmen arbeiten sollen. Bei fast allen gängigen Techniken im KI-Bereich arbeitet man daher mit Vektoren und Matrizen.

Für Bilder ist diese Darstellung einfach zu finden: Ein Digitalfoto ist nichts anderes als eine Matrix aus Zahlen, die die Farben der einzelnen Pixel beschreibt. Mit einer solchen Matrix lassen sich sofort weitere Berechnungen durchführen. Aber wie funktioniert das bei Source Code, beziehungsweise bei Änderungen am Code? Da es hier bisher keine etablierte Standardverfahren gibt, haben wir uns in mehreren Schritten überlegt, wie eine geeignete Vektordarstellung aussehen könnte.

Einfaches Referenzmodell

Als ersten Schritt stellen wir eine Repräsentation vor, die Änderungen an einem Softwareprojekt so einfach wie möglich widerspiegelt. Wir arbeiten oft im Java-Umfeld, daher konzentrieren wir uns auf diesen Spezialfall. Die Mechanik lässt sich aber auf praktisch jede Programmiersprache erweitern. Ein übliches Java-Projekt ist in einzelnen Klassen organisiert. Dabei hat, vereinfacht gesagt, jede Klasse ihre eigene Datei. Wenn wir nun am Projekt eine Änderung vornehmen, bearbeiten wir also eine gewisse Menge dieser Klassen. Unsere erste Vektordarstellung dieser Änderung besteht darin, festzuhalten, welche Klassen geändert wurden und welche nicht. Dazu erstellt man einen Vektor, der so viele Dimensionen hat, wie es Klassen im Projekt gibt. Die Einträge geänderter Klassen werden auf 1 gesetzt, die der nicht veränderten Klassen auf 0. Damit haben wir einen sinnvollen Vektor und könnten sofort mit dem Machine Learning beginnen.

Leider gibt es aber noch einige Probleme bei diesem Ansatz:

Was machen wir, wenn neue Klassen hinzugefügt oder bestehende gelöscht werden? Viele Machine-Learning-Modelle benötigen eine fixe Anzahl an Dimensionen für die Ein- und Ausgabevektoren. Also können wir nicht so einfach neue Dimensionen an den Vektor anfügen.
Wir wissen mit Hilfe dieses Vektors nicht, was genau geändert wurde. Eine Klasse, die nur neue Kommentare beinhaltet, besitzt genauso den Status "geändert" wie eine andere, die komplett umgeschrieben wurde. Letztere hat aber auf Ergebnisse der Tests erhebliche Auswirkungen, während die neuen Kommentare diese überhaupt nicht beeinflussen.
Wir müssen also unser Vektormodell noch weiter verfeinern. Vor allem muss in diesem mehr Information über den Inhalt der Änderungen enthalten sein.

Änderungskontext aus dem Abstract Syntax Tree

In der nächsten betrachteten Vektordarstellung wollen wir auch wissen, was sich zwischen zwei Versionen einer Datei im Source Code geändert hat, und diese Unterschiede als Vektor darstellen. Ein Ansatz dafür ist, je einen Vektor für diese beiden Versionen der Klasse zu finden und diese voneinander abzuziehen. Die wichtigste Frage ist also, wie die Vektoren für den Inhalt kompletter Dateien berechnet werden sollen. Um das herauszufinden sehen wir uns den Inhalt der Source-Code-Datei etwas genauer an. Es handelt sich dabei im Grunde um nichts anderes als Text. Dieser Text hat zwar eine etwas andere semantische Struktur als natürliche Sprache. Im Gebiet des Natural Language Processing existieren jedoch bereits Methoden, einen kompletten Text als Summe von Einzelvektoren darzustellen. Davon können wir uns für unsere Anwendung auf Source Code inspirieren lassen.

Das Grundprinzip unserer Methodik ist relativ einfach: Wenn wir einen Vektor für einen Text erstellen wollen, zerteilen wir diesen zunächst in seine Einzelbausteine (also Wörter). Für jedes in der Grammatik vorkommende Wort bilden wir im nächsten Schritt einen Vektor. Um schließlich einen Vektor für den gesamten Text zu bekommen, werden diese einzelnen Vektoren einfach aufaddiert. Den Unterschied zwischen zwei Texten erhält man dann, indem man ihre Vektoren voneinander subtrahiert. Anschaulich gesehen sind in diesem Änderungsvektor dann Informationen über genau die Wörter enthalten, in denen sich die beiden Texte unterscheiden.

Wie können wir dieses Verfahren auf Source Code anwenden? Der einfachste Ansatz wäre, den Code als normalen englischen Text zu behandeln und die Vektoren seiner einzelnen Wörter zu addieren. Allerdings haben wir bei Code einen ganz anderen Blick auf die semantische Struktur: Wenn man wissen will, welchen Zweck ein Stück Source Code besitzt, ist die Sicht auf seinen Syntaxbaum viel sinnvoller. Hier haben wir nun keine einzelnen Wörter, sondern Tokens als kleinste Einheit. Der Java-Compiler kennt 86 verschiedene Tokens. Also müssen wir, um beliebigen Java-Code als Vektor darstellen zu können, Vektoren für jeden dieser 86 Bausteine finden.

Vektordarstellung einzelner Tokens

Die Güte der Vektorisierung der Tokens ist entscheidend für die Güte zukünftiger Vorhersagen. Sind die einzelnen Wort- bzw. Tokenvektoren nicht aussagekräftig genug, hilft diese Information nicht weiter und ein Lernalgorithmus kann hieraus keine Informationen gewinnen.

Sehen wir uns auch hier wieder Methoden aus dem Natural Language Processing an. Diese Verfahren lassen sich unverändert auf Code anwenden, da es hier nur darum geht, den kleinsten Einheiten eines Textes Vektoren zuzuweisen. Ob diese Einzelbausteine Wörter sind oder etwas abstraktere Tokens eines Syntaxbaumes, ist dafür nicht relevant.

Ein klassisches Verfahren ist das so genannte One-Hot Encoding. Darunter versteht man einen Vektor, der genau so viele Dimensionen besitzt wie es Wörter oder Tokens in der Sprache gibt. In unserem Fall mit Java wäre dieser Vektor also 86 Dimensionen lang. Im Vektor eines bestimmten Tokens sind fast alle Einträge auf den Wert 0 gesetzt. Nur ein einziger belegt den Wert 1. Die Position der 1 ist für jeden Token einzigartig und wird über seinen Rang im Wörterbuch der Sprache festgelegt. Beispielsweise kann man die Tokens alphabetisch sortieren. Das erste Token erhält die 1 an der ersten Vektorposition, das folgende Token an zweiter Stelle, usw. Das One-Hot Encoding ist ein sehr einfacher Weg, Wörter beziehungsweise Tokens einer Sprache als Vektor darzustellen. Außerdem hat es den großen Vorteil, dass im Vektor eines gesamten Textes exakt abgelesen werden kann, welche Wörter darin enthalten sind: Steht an erster Stelle die Zahl 3, so gibt es vom ersten Wort im Wörterbuch genau drei Vorkommnisse im Text.

Der Nachteil dieses Verfahrens wird sichtbar, wenn man sich einmal die Anzahl der Wörter einer natürlichen Sprache ansieht. Hier haben wir es leicht mit mehreren Millionen Wörtern zu tun, also würde auch unser Vektor einige Millionen Dimensionen besitzen. Deswegen wurde für natürliche Sprachen eine andere Lösung gefunden, die mit einer ausreichend kleinen Zahl fixer Vektordimensionen arbeitet und auch für Tokens aus dem AST vielversprechend wirkt: Das sogenannte word2vec.

Wortvektoren mit Hilfe von Machine Learning finden

Bei word2vec wird ein Ansatz aus dem Bereich Machine Learning verwendet, um Vektoren für eine spätere Anwendung im Machine Learning zu finden. Das klingt zunächst etwas skurril, die Idee dahinter ist aber sehr interessant.

Wenn wir word2vec anwenden, wollen wir, wie beim One-Hot Encoding auch, Vektoren für alle Wörter oder Tokens unserer Sprache finden. Das verantwortliche neuronale Netz wird aber nicht direkt darauf trainiert, sondern es soll zunächst eine andere Aufgabe lösen. Nehmen wir als Beispiel den Satz "Dieser rote Apfel schmeckt gut." Wir zeigen dem word2vec-Netz die Begriffe "Dieser", "rote", "schmeckt" sowie "gut" und erwarten, dass es vorhersagt, dass das fehlende Wort in der Mitte "Apfel" ist. Wenn man ihm dafür viele verschiedene Beispiele zeigt, etwa reihenweise Wikipedia-Artikel, wird es diese Lückentexte irgendwann sehr zielsicher ausfüllen können. Das ist bereits sehr beeindruckend, aber nicht das, was wir eigentlich wollen.

Das word2vec-Netz hat allerdings nebenbei bereits die Arbeit der Vektorisierung des Wortes erledigt: Während es sich darum gekümmert hat, aus einem Kontext ein fehlendes Wort zu finden, musste es die in neuronalen Netzen vorhandene innere Vektorschicht, das sogenannte Hidden Layer, anpassen. Am Anfang werden hier zufällige Werte in dessen Feature-Aktivierungen erzeugt. Durch das Training wird der Vektor der Aktivierungen im Hidden Layer aber so verändert, dass die Vorhersagen präziser werden. Nach dem Training kann dann zurückgerechnet werden, welche Aktivierungen im Hidden Layer verursacht wurden, wenn das word2vec-Netz ein bestimmtes Wort vorhersagt. Dieser Vektor an Aktivierungswerten kann dann für jedes Wort in der Sprache gemacht werden und wir bekommen so alle benötigten Vektoren. Die so berechneten Vektoren besitzen eine wesentlich geringere Zahl an Dimensionen, als beim One-Hot Encoding, trennen die Wörter aber ähnlich scharf voneinander.

Für das Training benötigen wir bei word2vec verschiedene Beispiele dafür, in welchem Kontext ein Wort vorkommt. Wenn wir dieses Verfahren auch auf Source Code anwenden wollen, müssen wir folglich Beispiele für Kontexte finden, in denen einzelne Tokens verwendet werden. Glücklicherweise ist dies eine relativ einfache Aufgabe, da auch Tokens im Syntaxbaum eine Art Kontext besitzen: Sie haben einen Vater-Token und auch möglicherweise mehrere Kindknoten. Diese Tokens in der näheren Umgebung werden dann als Input für das word2vec-Netz verwendet. Die Beispiele, auf denen trainiert werden kann, sind dabei beliebige Java-Dateien. Nach dem Training kann für jeden der 86 Tokens ein Vektor zurückgerechnet werden, genau wie bei der Variante für natürliche Sprache.

Abb. 1: Koordinatensystem zur Visualisierung und Überprüfung. © TNG Technology Consulting GmbH

Eine Eigenschaft und ein Gütekriterium von Vektoren, die durch word2vec erzeugt werden, ist Folgendes: Wenn Wörter oft in einem ähnlichen Kontext verwendet werden, sind auch ihre Vektoren ähnlich zueinander. Das führt dazu, dass sich diese Wörter räumlich nah sind, wenn ihre Vektoren in ein Koordinatensystem eingetragen werden. Um zu überprüfen, ob der word2vec-Ansatz auch für Java-Code funktioniert, haben wir daher die Vektoren der einzelnen Tokens in einem Koordinatensystem visualisiert und überprüft, ob "ähnliche" Tokens nahe beieinander liegen.

Da wir es hier mit eigentlich 7-dimensionalen Daten zu tun haben, wurde Abb. 1 mit dem sogenannten t-SNE Verfahren auf 2 Dimensionen reduziert. t-SNE achtet darauf, dass Cluster, die in 7D existieren, auch in 2D erhalten bleiben. Sehen wir uns diese Grafik etwas genauer an, so entdecken wir Familien von Tokens, deren Vektoren sich ähneln. Etwa finden wir rechts unten die Return- und Throw-Statements nahe zueinander. Im linken oberen Quadranten existiert dagegen ein Cluster von verschiedenen Tokens, die sich alle in typischem Programmcode in der Nähe von Variablenzuweisungen befinden (Unary/Binary Expression, usw.). Alles in allem scheint das word2vec-Verfahren also auch eine gute Vektorisierung für Code zu liefern. Die von uns mit word2vec generierten Tokenvektoren für Java finden sich übrigens auch in Tensorflow Projector [1]. Dort können unter anderem die Cluster von Abb. 1 in einer interaktiven 3D-Ansicht visualisiert werden.

Leider können word2vec und der MonkeyRunner in dieser einfachen Form noch nicht problemlos im Zusammenspiel verwendet werden. Der MonkeyRunner verändert beispielsweise Additionen zu Subtraktionen oder ändert den Wert von Konstanten. Dabei bleibt aber die Struktur des Syntaxbaumes gleich, es werden keine neuen Tokens eingefügt oder andere entfernt. Das Tool verändert lediglich bestimmte Parameter der Tokens – etwa die konkrete Operation einer Binary Expression oder den Wert einer Variablen. Da word2vec die Vektorisierung dann aber auf Token-Ebene durchführt und eventuelle Parameter dabei nicht beachtet, erhält eine Addition den gleichen Vektor wie eine Subtraktion. Aus diesem Grund wird word2vec einer Datei nach einer Veränderung durch den MonkeyRunner den gleichen Vektor zuweisen wie bereits zuvor. Der Unterschied wird nicht erkannt und wir können auf dieser Basis natürlich kein Machine-Learning-Modell trainieren.

Es gibt mehrere Lösungsansätze für dieses Problem. Zum einen können wir den MonkeyRunner so anpassen, dass er komplexere Änderungen erzeugt. Automatisiert sinnvolle und tiefgreifende Änderungen zu erzeugen ist aber keine leichte Aufgabe. Zum anderen können wir auch word2vec anpassen. Wir können hier einzelne Java-Tokens in mehrere verschiedene Klassen aufteilen. Beispielsweise lässt sich das Token der Binary Expression in Addition, Subtraktion, Multiplikation etc. aufspalten. Schwieriger wird es aber etwa bei Variablen, die unendlich viele Werte annehmen können.

Outputvektoren für Machine Learning auf Code

Beim Machine Learning benötigt man nicht nur Eingabedaten, sondern auch Ausgabedaten, die als sogenannte Output-Vektoren vorliegen. Diese Vektoren beschreiben die Klasse eines Datensatzes oder eine Menge von vorhergesagten Parameterwerten.

In unserer Beispiel-Anwendung wollten wir Auswirkungen von Code-Änderungen auf Testergebnisse vorhersagen. Dafür lässt sich ein Outputvektor verwenden, der für jeden Test im Projekt eine eigene Dimension besitzt. Dann können wir bei jeder Codeänderung eintragen, welche Tests fehlschlagen und welche erfolgreich sind. Fehlgeschlagene Tests werden beispielsweise mit einer Eins markiert, erfolgreiche Tests mit einer Null.

Aus unseren Eingabedaten lassen sich aber auch andere Vorhersagen treffen, etwa die Auswirkung auf bestimmte Qualitätsmetriken. Solange eine Eigenschaft des untersuchten Projekts als Zahl oder Vektor dargestellt werden kann, ist es möglich, diesen Wert in den Ausgabedaten eines Machine-Learning-Modells zu verwenden.

Speziell bei der Vorhersage von Testergebnissen stoßen wir aber auf ein Problem, das schon bei der simplen Repräsentation der Eingabevektoren auftrat: Viele Algorithmen im Bereich des Machine Learnings benötigen eine fixe Dimension für die Ein- und Ausgabedaten. Wie behandeln wir dann den Fall, dass neue Testfälle zum Projekt hinzugefügt werden? Glücklicherweise haben wir es bei den Ausgabevektoren leichter als bei den Vektoren für Codeänderungen. Hier ist es in solch einem Fall üblich, pro Dimension im Outputvektor (also pro Testfall im Projekt) ein eigenes Modell zu trainieren. Am Ende wird die Vorhersage der Testergebnisse durch ein Ensemble vieler Machine-Learning-Modelle getätigt, wobei sich jedes auf ein spezielles Testergebnis konzentriert.

Machine-Learning-Modelle

An dieser Stelle wollen wir nun auf die konkreten Modelle eingehen, die wir zur Analyse von Source Code benutzen können. Wir zeigen dabei zunächst die allgemeine Funktionsweise zweier Modelle auf und beschreiben Probleme, die man bei ihrer Verwendung beachten sollte.

Support Vector Machines

Die ersten Modelle, die wir zur Code-Analyse benutzt haben, waren Support Vector Machines oder kurz SVMs. Eine SVM nimmt einen Input-Vektor und versucht, ihn in eine von zwei Kategorien einzuordnen: Gehört die Eingabe zu der Kategorie, die dieses Modell betrachtet (1) oder nicht (0)? Zum Beispiel kann die SVM bei einem Software-Test die vorliegenden Eingabedaten in erfolgreiche (1) und fehlschlagende (0) Testergebnisse aufteilen.

Abb. 2: Koordinatensystem mit Input-Vektoren. © TNG Technology Consulting GmbH

Um diese Entscheidung zu treffen, wird eine Support Vector Machine anhand von Beispieldaten trainiert: Jedem der Input-Vektoren wird zunächst eine Eins oder eine Null zugeordnet. Bildlich veranschaulicht werden diese Einsen und Nullen dann so in ein Koordinatensystem eingetragen, dass ihre Input-Vektoren als Koordinaten benutzt werden. Für zweidimensionale Input-Vektoren zeigen wir das in Abb. 2 beispielhaft. Hier befindet sich an Position (1,2) eine (1), da der Datensatz mit Input-Vektor (1,2) zur Kategorie 1 zugeordnet wurde.

Schließlich versucht die SVM, die in der Abb. blau eingezeichnete Entscheidungsfunktion zu finden: Die SVM erstellt die Funktion so, dass sie die beiden Kategorien 1 und 0 in den Trainingsdaten gut voneinander trennt. Eine Vorhersage bei unbekannten Daten überprüft dann lediglich, auf welcher Seite der Entscheidungsfunktion sich die Datensätze befinden.

In ihrer Grundform kann eine Support Vector Machines nur zwischen zwei Kategorien unterscheiden. Wenn wir aber beispielsweise die Ergebnisse einer Reihe von Software-Tests vorhersagen möchten, reicht uns das nicht aus. Es gibt allerdings auch eine Möglichkeit, hier trotzdem SVMs zu verwenden: Für jeden einzelnen Test wird eine separate SVM trainiert, um dessen Ergebnis vorherzusagen. Um eine komplette Vorhersage für den Datensatz zu treffen, werden dann die Ergebnisse aller einzelnen SVMs gesammelt und zu einem Ausgabe-Vektor konkateniert.

Neuronale Netze

Eine sehr vielseitige andere Modellfamilie stellen die neuronalen Netze dar. Sie sind angelehnt an die Funktionsweise eines Nervensystems und die Vorhersage-Algorithmen basieren auf sehr einfachen mathematischen Berechnungen [2].

Abb. 3: Text und Quelle Glosser.ca [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)] — Abb. 3: Text und Quelle Glosser.ca [CC BY-SA 3.0]

Wie auch bei anderen Machine-Learning-Verfahren benötigen wir bei neuronalen Netzen Trainingsdaten, die aus Eingabe- und Ausgabe-Vektoren bestehen. Für das Netz selbst gibt es eine Vielzahl von Architekturmöglichkeiten, aber wir beschränken uns hier auf ein einfaches Netz mit einer versteckten Vektorschicht, dem sogenannten Hidden Layer. Jede Schicht von Neuronen kann als einzelner Vektor gesehen werden, wobei die erste Schicht für den Input-Vektor und die letzte Schicht für den Output-Vektor eines Datensatzes verwendet wird.

Der Input-Vektor eines Datensatzes wird also in die erste Vektorschicht des Netzes eingetragen. Im Folgenden müssen wir dann die Werte der weiteren Schichten berechnen, bis wir bei der letzten Schicht angekommen sind. Deren Vektor ist der vorhergesagte Output-Vektor des Datensatzes.

Wie werden nun die Werte innerhalb der verschiedenen Schichten berechnet? Die Neuronen der Input-Schicht sind, wie in der oberen Grafik durch Pfeile dargestellt, mit den Neuronen des Hidden Layer verbunden. Um nun den Wert eines Neurons im Hidden Layer zu berechnen, werden die Werte aller eingehenden Verbindungen addiert. Dabei hat jede einzelne Verbindung ein bestimmtes Gewicht, das im Laufe des Trainings festgelegt wurde. Mit diesem Gewicht wird der Wert des eingehenden Neurons vor der Addition multipliziert. Zum Schluss addieren wir auf den Wert des versteckten Neurons noch einen konstanten Wert, den sogenannten Bias, auf. In dieser Art werden die Werte aller Neuronen des Hidden Layer ermittelt. Sobald das geschehen wird, können in genau der gleichen Weise die Werte der nächsten Vektorschicht berechnet werden, bis zum Schluss der Output-Vektor bestimmt wurde.

Die Gewichte der einzelnen Verbindungen sowie die Bias-Werte der Neuronen werden vor dem Training zufällig initialisiert, da zu diesem Zeitpunkt die optimalen Werte noch nicht bekannt sind. Die Input-Vektoren der Trainingsdaten benutzen wir dann nacheinander als Eingabe für das Netz und vergleichen den vorhergesagten Output-Vektor mit dem korrekten Ergebnis. Anhand der Höhe der Abweichung (auch Kosten genannt) verändern die Trainings-Algorithmen dann die Gewichte und Bias-Werte Schritt für Schritt. So wird das Ergebnis mit jedem Durchlauf der Trainingsdaten genauer – so zumindest das Ziel.

Problem: Overfitting

Ein häufiges Problem bei der Verwendung von Machine Learning – speziell mit neuronalen Netzen – ist das Phänomen des "Overfitting". Damit bezeichnet man die Tendenz eines Machine-Learning-Modells, statt allgemeinen Mustern in den Trainingsdaten vielmehr ungewollte Details zu erkennen. Overfitting tritt vor allem dann auf, wenn wir das Modell auf zu wenigen bzw. zu wenig verschiedenen Datensätzen trainieren. Ein Beispiel hierfür ist unser erster Versuch, ein neuronales Netz zur Vorhersage der Ergebnisse von Software-Tests zu verwenden: Das Modell hatte sich hier gemerkt, welcher der Tests am häufigsten fehlschlägt. Damit lernte das System einfach, dass dieser Test immer fehlschlagen würde, egal um welche Code-Änderung es sich handelt.

Auf der Suche nach einer Lösung für dieses Problem gibt es im Grunde zwei verschiedene Ansätze:

Die erste Lösung wäre, einfach mehr Daten zum Trainieren zu verwenden. Außerdem muss sichergestellt sein, dass von einer Kategorie nicht deutlich mehr Daten vorliegen als von anderen. Das ist aber nicht immer so leicht möglich: Um Overfitting zu vermeiden gibt es eine Faustregel, die besagt, dass man ca. 10 Datensätze pro veränderlichem Parameter im Modell benötigt. Wenn man von einem neuronalen Netz ausgeht, bei dem jedes einzelne Gewicht und jeder Bias ein solcher Parameter ist, kommt man hier schnell zu mehreren zehn- bis hunderttausenden Parametern. Folglich bräuchten wir auch 100.000 bis 1 Mio. Datensätze für das Training. In unserem Fall mussten wir eine große Anzahl an verschiedenen Code-Änderungen erzeugen, was selbst automatisiert lange dauert. Mehr als ca. 20.000 Datensätze waren hier nicht sehr realistisch.

Daher kommt hier der zweite Ansatz ins Spiel: Wir benötigen ein Modell mit weniger Parametern. Und hier werden die zuerst genannten Support Vector Machines sowie weitere statistische Verfahren interessant. Hier hat man es nicht mit zu vielen Parametern zu tun und kann somit auch mit einer geringeren Datenmenge gute Vorhersagen erreichen. Deswegen lautet unsere Empfehlung: Bei Machine-Learning-Problemen, die noch keine sehr etablierten Standardmodelle haben, sollte man zunächst versuchen, einfache Modelle mit weniger Parametern zu trainieren. Erst wenn man hier zu einem Punkt gelangt, an dem man gute Performance bei Vorhersagen erreicht hat, kann man sich auch komplexeren Modellen zuwenden.

Fazit

Um Machine Learning erfolgreich anwenden zu können, sind die Beschaffung von Trainingsdaten und deren Umwandlung in eine Vektorform von zentraler Bedeutung. In diesem Artikel haben wir uns näher damit befasst, wie verschiedene Ansätze im Bereich des Machine Learning Aufgaben bei der Analyse von Source Code lösen können.

Für die Generierung von Trainingsdaten schlagen wir einen zweigeteilten Weg vor: Wir benutzen einerseits natürliche Daten in Form von Code-Änderungen, die durch Entwickler durchgeführt wurden und in der Versionsverwaltung gespeichert sind. Andererseits kommt unser MonkeyRunner-Tool zum Einsatz, um anschließend diesen natürlichen Datensatz automatisiert zu vergrößern.

Unser Ansatz, aus diesen Codeänderungen dann Vektoren zu generieren, basiert auf dem word2vec-Verfahren des Natural Language Processing. Dabei werden zunächst den einzelnen Bausteinen des Source Codes, den sogenannten Tokens, Vektoren zugewiesen. Diese werden summiert und so zu einer Vektordarstellung des gesamten Codes verarbeitet.

Mit diesen Strategien wird eine Ausgangssituation für ein Machine-Learning-System geschaffen, das durch Analyse des Source Codes den Entwickler unterstützen kann. Als Beispiel haben wir die Vorhersage von Testergebnissen vorgeschlagen, allerdings können wir auch viele andere Zusammenhänge betrachten. Unsere Pipeline zur Trainingsdatengenerierung und eine sinnvolle Vektordarstellung von Code als Eingabedaten bilden hier eine Art Grundstein für weitere Entwicklungen.

Auch die Wahl des eigentlichen Machine-Learning-Modells, das beim Training und der Vorhersage eingesetzt wird, ist von diesem Fundament unabhängig. Je nach vorhandener Datenmenge kann etwa ein neuronales Netz verwendet werden oder auch einfachere statistische Modelle wie zum Beispiel Support Vector Machines.

Quellen