Preview

PDF, English Download (1MB) | Terms of use

Abstract

A quarter of a century after the world-wide web was born, we have grown accustomed to having easy access to a wealth of data sets and open-source software. The value of these resources is restricted if they are not properly integrated and maintained. A lot of this work boils down to matching; finding existing records about entities and enriching them with information from a new data source. In the realm of code this means integrating new code snippets into a code base while avoiding duplication.

In this thesis, we address two different such matching problems. First, we leverage the diverse and mature set of string similarity measures in an iterative semisupervised learning approach to string matching. It is designed to query a user to make a sequence of decisions on specific cases of string matching. We show that we can find almost optimal solutions after only a small amount of such input. The low labelling complexity of our algorithm is due to addressing the cold start problem that is inherent to Active Learning; by ranking queries by variance before the arrival of enough supervision information, and by a self-regulating mechanism that counteracts initial biases.

Second, we address the matching of code fragments for deduplication. Programming code is not only a tool, but also a resource that itself demands maintenance. Code duplication is a frequent problem arising especially from modern development practice. There are many reasons to detect and address code duplicates, for example to keep a clean and maintainable codebase. In such more complex data structures, string similarity measures are inadequate. In their stead, we study a modern supervised Metric Learning approach to model code similarity with Neural Networks. We find that in such a model representing the elementary tokens with a pretrained word embedding is the most important ingredient. Our results show both qualitatively (by visualization) that relatedness is modelled well by the embeddings and quantitatively (by ablation) that the encoded information is useful for the downstream matching task.

As a non-technical contribution, we unify the common challenges arising in supervised learning approaches to Record Matching, Code Clone Detection and generic Metric Learning tasks. We give a novel account to string similarity measures from a psychological standpoint and point out and document one longstanding naming conflict in string similarity measures. Finally, we point out the overlap of latest research in Code Clone Detection with the field of Natural Language Processing.

Translation of abstract (German)

Ein Vierteljahrhundert nachdem das World-Wide Web eingeführt wurde, haben wir uns sehr daran gewöhnt, einfachen Zugang zu einer riesigen Menge an Daten und Open-Source Software zu haben. Der Wert dieser Resourcen ist allerdings dadurch bedingt, dass sie ordentlich integriert und gewartet werden. Ein Großteil solcher Arbeit läuft auf Matching hinaus: Das Auffinden von existierenden Datensätzen, um sie mit weiterer Information aus neuen Datensätzen anzureichern; das Integrieren von Code in eine bestehende Code-Basis, ohne gleichzeitig Duplikation einzuführen.

In dieser Arbeit gehen wir zwei verschiedene solcher Matching-Probleme an. Erstens machen wir Gebrauch von der vielfältigen und ausgereiften Menge an String-Ähnlichkeitsmaßen um in einem iterativen, halb-überwachten Lernansatz das String-Matching-Problem zu lösen. Er ist so angelegt, dass der User eine Sequenz an Einzelfällen des String-Matchings entscheiden muss. Wir zeigen dass mit einer nur sehr kleinen Menge an Entscheidungen fast optimale Lösungen gefunden werden können. Der geringe Annotationsaufwand unseres Algorithmus kommt daher, dass wir das Cold-Start-Problem, das dem Active Learning innewohnt, auf zweierlei Arten behandeln. Einerseits durch das Ordnen der Instanzen nach ihrer Rang-Varianz, solange noch nicht genug überwachte Information vorliegt, und andererseits durch einen selbstregulierenden Mechanismus, der anfänglichen Verzerrungen des Komitees entgegenwirkt.

Zweitens widmen wir uns dem Matching von Code-Fragmenten für die Deduplikation. Programmiercode ist nicht nur ein Werkzeug, sondern stellt selbst eine Resource dar, die der Wartung bedarf. Code-Duplikation ist ein häufig auftretendes Problem, das besonders im Zusammenhang moderner Entwicklungspraxis entsteht. Es gibt viele Gründe, Code-Duplikate aufzudecken und zu beheben; zum Beispiel das Bewahren einer sauberen und wartbaren Code-Basis. Für solche komplexeren Datenstrukturen wie Code sind String-Ähnlichkeitsmaße inadäquat. Stattdessen untersuchen wir einen modernen Ansatz des überwachten Metric-Learning, um Code-Ähnlichkeit mit Neuronalen Netzen zu modellieren. Ein Ergebnis ist, dass das Repräsentieren der elementaren Code-Tokens durch vortrainierte Embeddings die wichtigste Zutat in einem solchen Modell ist. Unsere Auswertung ergibt sowohl qualitativ, durch Visualisierung, dass thematische Verbundenheit gut durch diese Embeddings modelliert wird, und quantitativ, durch Ablation, dass die kodierte Information nützlich für das nachgelagerte Matching ist.

Als nicht-technischen Beitrag geben wir einen einheitlichen Zugang zu gemeinsamen Herausforderungen, die beim überwachten Lernen von Record Matching, Code Clone Detection und allgemeinen Metric-Learning-Anwendungen auftreten. Wir geben einen neuen Zugang zu String-Ähnlichkeitsmaßen vom Standpunkt der Wahrnehmungspsychologie, zeigen einen lange bestehenden Namenskonflikt von String-Ähnlichkeitsmaßen auf und dokumentieren ihn. Schließlich geben wir einen Überblick über die Schnittmenge der neuesten Forschung in Code Clone Detection mit dem Gebiet des Natural Language Processing.