Diplom-, Master-, Bachelor- oder Studienarbeiten

Im Fachgebiet Knowledge Engineering (Prof. J. Fürnkranz) werden zur Zeit folgende Themen für studentische Arbeiten angeboten. Die meisten Themen eignen sich sowohl für Diplom- und Master-Arbeiten, als auch für Studien- oder Bachelor-Arbeiten, wobei bei letzteren natürlich eine etwas weniger tiefe Behandlung des Themas erwartet wird, bzw. Themen eventuell auch zu zweit behandelt werden können.

Die Themen-Liste ist keineswegs vollständig und Sie sind auch herzlich eingeladen, selbst Themen vorzuschlagen. Am Fachgebiet findet auch regelmäßig ein Ober-Seminar statt, in dem laufende oder gerade fertig gestellte Arbeiten vorgestellt werden.

Antworten auf häufig gestellte Fragen zu Abschlußarbeiten finden Sie in unserer FAQ.

All theses can be written in English (in fact, this is strongly encouraged). English descriptions of individual topics are available upon request.

Maschinelles Lernen und Data Mining

Erweiterung und Evaluierung des modularen Perceptron-Frameworks Perceptrovement

Ansprechpartner: ELM

Der Perzeptron-Algorithmus ahmt eine neuronalen Zelle nach und ist einer der bekanntesten und ältesten Vertreter der linearen Klassifizierer. Obwohl der Algorithmus sehr simpel ist und schon in den 60er Jahren entwickelt wurde, erfreut er sich in letzter Zeit großer Beliebtheit wegen der Einfachheit und Schnelligkeit und da festgestellt wurde, daß lineare Klassifizierer für viele Aufgaben wie z.B. Text-Klassifizierung vollkommen ausreichend sind.

Die kürzlich in der Literatur vorgeschlagenen Erweiterungen behandeln verschiedene Themen wie verallgemeinernde Modelle, Toleranz gegenüber Rauschen, inkrementelles Lernen, Minimierung der Anzahl der Support-Vektoren, der Epochen etc. Viele der genannten Techniken wurden im Rahmen einer Bachelor-Arbeit am Fachgebiet implementiert. Das in Java geschriebene Framework Perceptrovement steht unter www.ke.tu-darmstadt.de/resources zur freien Verfügung. Mit dem stark modularen Framework ist es möglich, bestimmte Verbesserungen, Techniken und Fähigkeiten des Perceptron-Algorithmus auszuwählen, hinzuzuschalten und zu kombinieren. Dadurch ergibt sich jedoch eine große Zahl an möglichen Parameterkombinationen, die eine geeignete Wahl für eine bestimme Problemstellung erschwert.

Je nach gewünschtem Umfang der Arbeit (Praktikum, Bachelor- oder Masterarbeit) und persönlichem Interesse sind folgende Ziele zu verfolgen:

  • Erweiterung des bestehenden Frameworks
  • extensive Evaluation der verschiedenen Erweiterungen, Kombinationen und Parameter
  • Entwicklung einer Strategie, um (möglicherweise automatisch) eine geeignete Parameterauswahl für ein bestimmtes Klassifikationsproblem zu treffen

Referenzen:

  • Tobias Krönke. Verbesserungen des Perzeptron-Algorithmus, Bachelor's Thesis, 2011.
  • Roni Khardon, Gabriel Wachman. Noise Tolerant Variants of the Perceptron Algorithm, Journal of Machine Learning Research, Vol. 8, pp. 227-248, 2007.
  • Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, Yoram Singer. Online Passive-Aggressive Algorithms, Journal of Machine Learning Research Vol. 7, pp. 551-585, 2006.

Exploration Services on Data-Cube Sets

Ansprechpartner: LorenzWeizsäcker

Engineers from different fields such as machine learning or material research, as well as businesspeople in aquision, sales, or finance deal with large data cubes with many dimension that contain, for example, experimental result, or sales figures. The task of the bachelor thesis is to build a lean but extensible service framework for effective exploration of single data cubes as well as of multiple cubes in a joint manner.

The initial motivation is that the resulting framework supplements a given workflow framework for machine learning experiments which represents one possible source of data cubes. The modeling of the meta data should be sufficient for that case but might further be designed to fit other engineering or monetary settings making it suitable for business intelligence.

We have developed a workflow framework for machine learning experiments, peewit, which produces data cubes that fulfill simple meta-data model and are called v-cubes. The exploration code should allow comfortable analysis for those specific v-cubes but constitution of an improved cube model can also be part of the thesis. As minimal demand on the framework we define the following services for v-cubes based on the current model.

  • readable graphical presentation of up to six dimensions
  • clear textual presentation of meta-data and content for any number of dimensions
  • simple one sheet specification of the representation
  • intelligent listing of accessible cubes trough meta-data analysis
  • joint presentation of multiple fitting cubes/sources

In addition the candidate can cover simple data cube operations that are less relevant for machine learning experiments but often provided by OLAP in the business context. In this case it is eligible to revisit the current cube model such that it synchronously fits to numerical, measurement, and monetary data while remaining lean and comprehensible.

Maschinelles Lernen in der Disposition

Gemeinsame Arbeit mit dem FB 13, FG Bahnsysteme und Bahntechnik, Ansprechpartner: FJ & Anselmo Stelzer

Themenbeschreibung

Um die betriebliche/verkehrliche Disposition des Bahnbetriebs zu automatisieren sind relevante Kriterien (Attribute) zu ermitteln, anhand deren ein Algorithmus des maschinellen Lernens ein Modell ableiten kann, mit welchem dann ein Entscheidungsvorschlag für neue Situationen ermittelt werden kann. Dabei ist zunächst zu erfassen, welche Attribute prinzipiell für die Verfahren des maschinellen Lernens tauglich sind. In einem weiteren Schritt ist zu ermitteln, wie diese Attribute erzeugt werden können. Aus den Ergebnissen wird eine Datenbank aufgebaut, die als Lernbasis dient.

Aufgabenbeschreibung

Zu den Aufgaben im Rahmen der Arbeit zählen:

  • Bestimmung von relevanten Attributen
  • (algorithmische) Herleitungsmöglichkeit der Attribute
  • Evaluierung der Attribute für die Tauglichkeit im maschinellen Lernen

Grundlagen/Anforderungsprofil

  • Analytische Fähigkeiten
  • Bahnbetriebliches Interesse, wobei Vorkenntnisse nicht zwangsläufig erforderlich sind
  • Interesse an maschinellem Lernen

Beginn: Nach Vereinbarung
Dauer: 2 bis 6 Monate (je nach Studiengang, Prüfungsordnung bzw. Vollzeit/ Teilzeit)

Divide-and-Conquer-Lernen von SPARQL-Abfragen

Ansprechpartner: FJ

Linked Open Data ist eine globale Wissenssammlung, die für Maschinen und Menschen nutzbar ist. Hier finden sich zum Beispiel Daten über Länder, Städte, und berühmte Persönlichkeiten, aber auch spezielleres Wissen aus unterschiedlichen Domänen.

Die Abfrage-Sprache für Linked Open Data heißt SPARQL (analog zu SQL für Datenbanken). Mit einer SPARQL-Abfrage lässt sich eine bestimmte Information oder eine Menge von Objekten aus Linked Open Data abfragen. Solche Abfragen können auch genutzt werden, um neue Klassen von Objekten zu beschreiben - zum Beispiel die Klasse "Eltern" als die Abfrage aller Personen, die mindestens ein Kind haben.

In Ihrer Arbeit untersuchen Sie, wie sich Divide-and-Conquer-Lernverfahren anwenden lassen, um SPARQL-Abfragen für bestimmte Klassen von Objekten zu lernen. Dabei liegt der Fokus einerseits auf der Entwicklung eines Divide-and-Conquer-Algorithmus für SPARQL-Abfragen, andererseits auch auf einer laufzeiteffizienten Implementierung.

Nutzung bahnbezogener Sensordaten zur Vorhersage von Wartungszyklen

Ansprechpartner: FJ & Dr. Immanuel Schweizer

Thema:
Seit einiger Zeit werden auf den Lokomotiven der deutschen Bahn Sensordaten aufgezeichnet. Pro Monat sind dies in etwa 3000 Einträge pro Lokomotive. Es werden einerseits Daten über die Aktionen des Lokführers und andererseits Daten von verschiedenen Sensoren wie zum Beispiel Temperatur von Motoren, Geschwindigkeit, etc. aufgezeichnet. Diese sind sogar bereits mit GPS-Informationen verknüpft.
Ein momentan laufendes Projekt von DB Schenker beschäftigt sich damit, diese Daten effektiv zu nutzen und zum Beispiel interessante Zusammenhänge in diesen Daten zu finden um Vorhersagen zu treffen. Bisher gibt es aber kein automatisiertes System mit welchem man solche Zusammenhänge aus den Daten lernen könnte, sondern die Muster werden zumeist manuell von Experten gespeichert.

Aufgabenstellung:
In dieser Arbeit sollen daher Auswertungen dieser Offline Wartungslogs vorgenommen werden. Hierfür sollte anhand einer repräsentativen Anwendung wie beispielsweise der Vorhersage des Ausfalls eines einzelnen Motors ein Modell entwickelt werden. Die Sensormessungen sollten daher mit Schadens- bzw. Wartungsergeinissen verknüpft werden. Außerdem sollte versucht werden Kernereignisse zu identifizieren, die für einen Ausfall verantwortlich sind. Die Daten stehen gefiltert in Excel zu Verfügung und müssen entsprechend konvertiert werden.
Wir erwarten als Ergebnis ein erstes Modell zur Vorhersage einer Wartung welches im Rahmen der Arbeit ebenfalls bereits evaluiert werden sollte um zum Beispiel fehlende Sensorwerte oder mangelnde Datenqualität zu identifizieren.

Rahmenbedingungen:

  • die Arbeit wird als externe Arbeit am Standort DB Schenker Mainz (DB Schenker Rail GmbH, Rheinstraße 2, 55116 Mainz) durchgeführt
  • eine Aufwandsentschädigung ist möglich
  • die Arbeit kann als Bachelor-, Master- oder Studienarbeit durchgeführt werden
  • es handelt sich um eine Kooperation mit DB Schenker (Ansprechpartner: Dr. Dirk Schlebeck), der DB Systel (Ansprechpartner: Dirk Rammelt), dem Fachgebiet Telekooperation (Ansprechpartner: Dr. Immanuel Schweizer) und dem Fachgebiet Knowledge Enigneering (Ansprechpartner: Dr. Frederik Janssen)

Regel-Lernen

Optimizing the AUC with Rule Learning

Ansprechpartner: JF

Die Fläche unter ROC-Kurve (AUC) ist ein wichtiges Performanz-Maß, das angibt, wie gut ein Lerner positive von negativen Beispielen trennen kann. Im Bereich Regel-Lernen wurden verschiedene Verfahren zum Lernen von Regel-Mengen, die die AUC maximieren, vorgeschlagen. Im Rahmen dieser Arbeit sollen diese Verfahren untereinander, sowie mit einem neuen einfachen Verfahren verglichen werden.

Literatur:

ROC Analyse von Weighted Covering

Ansprechpartner: JF

Scholz (2006) hat eine auf einer ROC-Analyse basierende Variante von Boosting vorgestellt, die eine theoretisch fundierte Methode bietet, um Weighted Covering für Regel-Lerner zu implementieren. Aufgabe dieser Arbeit ist es, die Diplomarbeit von Ruppert (2006) unter Berücksichtigung dieser neuen Erkenntnisse fortzuführen. Besonderer Schwerpunkt soll auch auf der Evaluierung von Regelmengen verschiedener Mächtigkeit bzw. auf der Analyse, ob deren Redundanz gewinnbringend zu einer Performanz-Steigerung eingesetzt werden kann, liegen.

Literatur:

Überblick und Implementierung von Algorithmen zur Klassifikation mittels Assoziationsregeln

Ansprechpartner: JF

In der jüngeren Literatur findet sich eine Anzahl von Algorithmen, die Assoziations-Regel-Lern-Algorithmen einsetzen, um Klassifikationsregeln zu lernen. Aufgabe dieser Diplomarbeit, ist einerseits eine Aufarbeitung der Literatur auf diesem Gebiet (Startpunkte in der Literatur-Liste unten), andererseits eine Implementierung eines prototypischen Algorithmus in einer bereits vorhandenen Regel-Lern-Umgebung.

Literatur:

  • Branko Kavsek, Nada Lavrac, Viktor Jovanoski: APRIORI-SD: Adapting Association Rule Learning to Subgroup Discovery. Proceedings Intelligent Data Analysis 2003: 230-241
  • Bing Liu, Wynne Hsu, Yiming Ma: Integrating Classification and Association Rule Mining. Proceedings SIGKDD 1998: 80-86
  • Wenmin Li, Jiawei Han, Jian Pei: CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules. Proceedings of the IEEE Conference on Data Mining, 2001: 369-376
  • Xiaoxin Yin, Jiawei Han: CPAR: Classification based on Predictive Association Rules. Proceedings SIAM Conference on Data Mining, 2003

Weiterentwicklung und Optimierung einer Regel-Lern Umgebung

Ansprechpartner: FJ & JF

Am Fachgebiet wurde in einer Diplomarbeit ein modulares Regel-Lern-Framework (das SeCo-Framework) implementiert, welches seitdem stetig weiterentwickelt wurde. Auch momentan wird an verschiedenen Erweiterungen des Frameworks gearbeitet. In dieser Arbeit geht es darum einerseits einige weitere Funktionalitäten einzubauen und andererseits das vorhandene Framework zu optimieren, da das momentane Zusammenspiel der einzelnen Komponenten nicht effizient implementiert ist.

Es gibt eine Reihe von Erweiterungen, die entweder bereits in anderen Umgebungen implementiert sind (zum Beispiel in einem Vorgänger-Framework, was aber ähnliche Strukturen hat) und nun im SeCo-Framework adaptiert werden müssen oder die noch niregnds implemetiert sind. Zu diesen Erweiterungen zählen unter anderem:

  • Implementierung einer effizienten erschöpfenden Suche
  • Multi-Objective Heuristiken
  • Regression
  • Adaptierung einer vorhandenen GUI für interaktives Regellernen
  • Implementierung eines Wrappers zu weka

Ein weiterer wichtiger Punkt ist die Effizienz des Frameworks. Hier soll jede Komponenten genau untersucht werden und gegebenenfalls optimiert werden.

Literatur:

Rule-based Clustering

Ansprechpartner: JF & FJ

In dieser Arbeit soll ein Clustering Algorithmus entworfen werden, der die Cluster mit Regeln erklärt. Es gibt bereits einige Arbeiten, in denen basierend auf bereits existierenden Algorithmen Erweiterungen entworfen wurden, mit denen Cluster gefunden werden können. So ist der Algorithmus CLUSTER/2 entstanden, der auf der Separate-and-conquer Strategie beruht und eine Adaptierung des AQ-Algorithmus ist.
Die Aufgabe dieser Arbeit ist auch eine Literatursuche durchzuführen und eine Zusammenfassung über andere regelbasierte Clustering-Algorithmen zu geben.
Am Fachgebiet gibt es bereits einen allgemeinen Separate-and-conquer Algorithmus, der dann in dieser Arbeit auf Clustering-Funktionalität erweitert werden soll. Als Suchstrategie soll hierbei ein einfaches Hill-Climbing verwendet werden. Während des Ablaufs des Algorithmus soll ein Cluster der alle Instanzen abdeckt soweit verfeinert werden bis ein Stopping Criterion greift. Dann werden die Instanzen im gefundenen Cluster aus der Datenmenge entfernt und der nächste Cluster wird gefunden. So erklärt jede Regel genau einen Cluster. Die zentrale Aufgabe der Arbeit wird sein den Algorithmus zu adaptieren. Im Besonderen müssen die Heuristiken, die das Verfeinern einer einzelnen Regel steuern, angepasst werden. Als Startpunkt kann hierfür der Trade-Off zwischen intra-class similarity (die Gleichheit der Instanzen innerhalb eines Clusters) und inter-class dissimilarity (die Unterschiedlichkeit verschiedener Cluster) dienen. Basierend auf diesem Trade-Off sollen dann die Heuristiken weiter analysiert werden und insbesondere ein optimaler Trade-Off dieser beiden Ziele gefunden werden.

Literatur:

  • R.S. Michalski. Pattern recognition and rule-guided inference. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2:349–361, 1980.
  • R.S. Michalski.  On the quasi-minimal solution of the covering problem. Proceedings 5th International Symposium on Information Processing, volume A3 (Switching Circuits), pages 125–128, Bled, Yugoslavia, 1969.
  • R.S. Michalski and R.E. Stepp. Learning from observation: Conceptual clustering. Machine Learning: An Artificial Intelligence Approach. Tioga, Palo Alto, CA, 1983.

Entwurf, Implementierung und Evaluierung eines vertikalen Beispiel-Speichers für einen Regel-Lerner

Ansprechpartner: JF

Induktive Regel-Lerner zu Lernen von Klassifikations-Regeln gehen im allgemeinen von einer horizontal abgespeicherten Datenbank aus, d.h., der Speicher wird als ein Array von Beispielen organisiert, wobei jedes Beispiel eine Menge von Features hat. Im Bereich des Assoziationslernen finden sich in letzter Zeit jedoch vermehrt Ansätze, die von einem vertikalen Speicher ausgehen, d.h., es wird ein Array von Coverage-Vektoren abgespeichert, wobei jeder dieser Vektoren für ein bestimmtes Feature angibt, welche Beispiele es abdeckt. Solche Lösungen finden sich z.B. in den Assoziationsregel-Lernern Eclat und FP-Growth.

Aufgabe dieser Arbeit ist das Umsetzen eines ähnlichen Ansatzes für Klassifikations-Regel-Lerner. Ein Regel-Lerner, der auf dem horizontalen Datenbank-Design von Weka basiert, existiert bereits am Fachgebiet. Dieser müßte auf die neuen, im Rahmen der Diplomarbeit zu entwerfenden vertikalen Datenstrukturen angepaßt werden. Ein abschließender Vergleich zwischen beiden Varianten ist es ebenfalls durchzuführen.

Multilabel Rule Learning

Ansprechpartner: FJ & ELM

Oftmals wird Regel-Lernen nur zum Lernen einer einzelnen Klasse eingesetzt. Multilabel-Klassifikation basiert hingegen auf der Annahme, dass ein Beispiel zu mehreren Klassen gehören kann. So kann beispielweise ein Zeitungsartikel sowohl über Sport als auch über Politik sein. Bisher gibt es so gut wie keine Verfahren, die eine Menge von Regeln lernen, die dann zur Multilabel Klassifikation eingesetzt werden können. Dies ist erstaunlich, das Regel-Lernverfahren den großen Vorteil haben, dass sie ein interpretierbares Modell liefern, sehr gut erforscht sind und außerdem eine extrem schnelle Klassifikation bieten.

Ein naheliegender Ansatz für dieses Problem ist die sog. Binary Relevance bei welcher man jede der Klassen des Labelvektors einzeln lernt und erst später eine Kombination findet, um eine echte Multilabel Klassifikation vorzunehmen. Dabei ist das größte Problem, dass man Abhängigkeiten der Klassen nicht berücksichtigt. Wenn also Klasse B beispielsweise immer dann vorkommt wenn auch Klasse A vorhanden ist, wird man dies bei der Binary Relevance Methode nicht feststellen, bzw. ausnutzen können.

Es gibt verschiedene Ideen, wie man einen am Fachgebiet vorhandenen Regel-Lerner auf Multilabel Klassifikation erweitern könnte. In dieser Arbeit sollen einige dieser Ansätze implementiert werden und dann sowohl gegeneinander als auch gegen Binary Relevance bzw. gegebenenfalls andere Algorithmen getestet werden.

Literatur:

  • Fadi A. Thabtah, Peter I. Cowling and Yonghong Peng. Multiple labels associative classification. In: Knowledge and Information Systems, vol. 9 (1): pp. 109–129, 2006. doi: 10.1007/s10115-005-0213-x. http://selab.iecs.fcu.edu.tw/course/95/dp2/dpclass/16.pdf
  • Adriano Veloso, Wagner Meira, Marcos Gonçalves and Mohammed Zaki. Multi-label Lazy Associative Classification. In: Knowledge Discovery in Databases: PKDD 2007, 11th European Conference on Principles and Practice of Knowledge Discovery in Databases, vol. 4702 of Lecture Notes in Computer Science, pp. 605–612. Springer, 2007. ISBN 978-3-540-74975-2. doi:10.1007/978-3-540-74976-9_64. http://www.dcc.ufmg.br/~adrianov/papers/PKDD07/Veloso-pkdd07.pdf
  • Jesse Read, Albert Bifet, Geoff Holmes and Bernhard Pfahringer. Efficient multi-label classification for evolving data streams. Tech. rep., University of Waikato, Department of Computer Science, 2010. http://www.cs.waikato.ac.nz/pubs/wp/2010/uow-cs-wp-2010-04.pdf

Präferenz-Lernen

Ordered Classifier Chains

Ansprechpartner: JF

Classifier Chains (Read et al. 2011) sind eine Technik zum Lernen von Multilabel Klassifizierern, die in jüngster Zeit stark an Popularität gewonnen hat, obwohl sie auch einige Unzulänglichkeiten aufweisen (Dembczynksi et al. 2012). Eine davon ist, dass sie von einer beliebigen Anordnung der Klassen ausgeht, was zwar in der Theorie keinen Unterschied macht, aber in der Praxis wesentlich ist. Aufgabe dieser Arbeit ist es, verschiedene einfache Techniken zur Klassenanordnung empirisch miteinander zu vergleichen und ggf. auch theoretisch zu analysieren.

Literatur:

  • Jesse Read, Bernhard Pfahringer, Geoff Holmes, Eibe Frank: Classifier chains for multi-label classification. Machine Learning 85(3): 333-359 (2011).
  • Krzysztof Dembczynski, Willem Waegeman, Eyke Hüllermeier: An Analysis of Chaining in Multi-Label Classification. Proceedings ECAI 2012: 294-299.

Semi-Supervised Pairwise Classification

Ansprechpartner: JF

Paarweise Klassifikation ist eine Methode, ein Multi-Klassenproblem auf eine Menge von paarweisen Vergleichen zu reduzieren, von denen jeder durch einen binären Klassifizierer realisiert werden kann. Die binären Klassifizierer werden dabei jeweils nur an den Beispielen der Klassen trainiert, die sie letztendlich klassifizieren sollen.

Aufgabe dieser Bachelor-Arbeit ist es, das Verfahren dahingehend zu erweitern, dass die binären Klassifizierer auch alle anderen Beispiele (allerdings ohne Labels) verwenden können. Nach der Integration der Verfahren in eine bestehende Bibliothek ist das Verfahren anhand einiger Testdatensets zu evaluaieren.

Pairwise Object Ranking in Information Retrieval

Ansprechpartner: JF

Das LETOR Benchmark Dataset for Learning to Rank stellt eine Menge von Datensets für Object-Ranking zur Verfügung, sowie Testresultate für eine Menge von bekannten Ranking-Algorithmen. Aufgabe dieser Arbeit ist es, einen paarweisen Ansatz auf diesen Problemen zu testen. Dieser Ansatz trainiert einen konventionellen binären Lernalgorithmus für jedes Paar von Trainings-Objekten. Dessen paarweise Vorhersagen für eine Menge von Test-Objekten werden dann kombiniert. Abhängig von der Methodik, ergeben sich dadurch verschiedene Reihungen für die Menge von Test-Objekten. Die Qualität dieser Reihungen soll evaluiert werden, sowie die Laufzeit des Verfahrens mit alternativen Verfahren verglichen werden.

Literatur:

  • William W. Cohen, Rob Schapire, Yoram Singer (1999): Learning to Order Things, Journal of Artificial Intelligence Research (JAIR) 10: 243-270 (1999).

Unifying Pairwise Object and Label Ranking

Ansprechpartner: JF

Object Ranking ist die Aufgabe, eine Menge von Objekten, die durch Merkmale beschrieben sind, in eine Reihung zu bringen. Label Ranking ist dagegen die Aufgabe, für eine Menge von Objekten abhängig von einem Kontext in eine Reihung zu bringen. Hier wird der Kontext durch Merkmale beschrieben, die zugeordneten Objekte jedoch nur durch einen Identifier, i.e., durch ein Label.

Aufgabe dieser Diplomarbeit ist es, ein Szenario zur Unifikation beider Ansätze zu implementieren, zu testen und ggf. auch weiterzuentwickeln. Die Grundidee hierbei ist es, ein Prädikat p(c,o1,o2) zu lernen, welches angibt, das im Kontext c das Objekt c1 dem Objekt c2 vorgezogen wird. Zum Lernen diese Prädikats kann auf bestehende Lernalgorithmen zurückgegriffen werden. Die Evaluierung soll einen Vergleich mit Label Ranking und Object Ranking beinhalten und soll sowohl auf reellen Daten (z.B. dem Sushi-Datensatz) als auch auf zu erstellenden künstlichen Daten erfolgen.

Predicting Partial Orders

Ansprechpartner: JF

Präferenz-Lern-Algorithmen zum Lernen aus Label-Präferenzen sagen für einen neuen Datenpunkt eine totale Ordnung aller möglichen Präferenzen voraus. Durch eine Reduktion auf eine Multilabel-Klassifikationsproblem läßt sich jedoch auch eine partielle Ordnung vorhersagen. Aufgabe dieser Diplomarbeit ist die Implementierung und das Testen dieser Methode, insbesondere für den Spezialfall von Klassifikationsdaten.

Word Sense Alignment anhand von Präferenzen-Lernen

Ansprechpartner: ELM

Sense Alignment bezeichnet grob gesprochen das Zuordnen von Bedeutungen eines Wortes von einem Wörterbuch zu der semantisch zutreffenden Bedeutung eines Wortes in einem anderen Wörterbuch. So ist die Zuordnung von "Kiefer (Föhre)" aus openthesaurus.de zu "Kiefer (Botanik)" aus wiktionary.org sicherlich korrekt, während "Kiefer (Föhre)" zu "Kiefer (Knochen)" eine falsche Zuordnung darstellt. Im UKP Lab werden derzeit Verfahren erforscht, die anhand von semantischen Ähnlichkeiten zwischen den Beschreibungen automatisch Sprachresourcen wie wiktionary und WordNet miteinander verbinden. Aktuell wird hierfür semi-statisch ab einem bestimmten Wert der Ähnlichkeit zwischen zwei Bedeutungen die Zuordnung durchgeführt.

Das Ziel dieser Arbeit ist es, Techniken aus dem Präferenzlernen anzuwenden, um dieses Problem zu lösen. So kann man die Zuordnung von "Kiefer (Föhre)" zu "Kiefer (Botanik)" und nicht "Kiefer (Knochen)" natürlicherweise als Präferenz modellieren. In Zusammenarbeit mit UKP soll untersucht werden, welches Präferenzmodell zu verwenden ist und wie es im Vergleich zur statischen Methode abschneidet.

Referenzen:
  • Christian M. Meyer and Iryna Gurevych: What Psycholinguists Know About Chemistry: Aligning Wiktionary and WordNet for Increased Domain Coverage, in: Proceedings of the 5th International Joint Conference on Natural Language Processing, (to appear), November 2011. Chiang Mai, Thailand.

Game Playing

Wissensgewinn aus Spiel-Datenbanken

Ansprechpartner: JF

Zu einer stetig wachsenden Anzahl von Spielen gibt es wertvolle Informationen in Datenbanken. Zum einen wurden viele Spiele bereits durch vollständige Enumeration gelöst, d.h. man weiss für jede mögliche Stellung (und damit auch für die Ausgangsstellung), ob die Stellung gewonnen oder verloren ist bzw. wie viele Züge man bis zum Gewinn benötigt. Zum anderen werden immer mehr Spiele zwischen menschlichen Gegnern aufgezeichnet und in Datenbanken gespeichert.

Derartige Datenbanken sind ein Parade-Beispiel für die Aufgabe von Data Mining: In den Daten steckt alle Information, die notwendig ist, um das Spiel perfekt (im Falle von vollständigen Datenbanken) oder sehr gut zu spielen (im Falle von Partiensammlungen von guten Spielern). Dennoch ist es angesichts der Fülle der Daten menschlichen Experten zumeist unmöglich, aus dieser Information explizites, formalisierbares Wissen zu gewinnen.

Eine Diplomarbeit zu diesem Thema hätte die Aufgabe, aus einer relativ kleinen Datenbank (z.B. das König-Turm-König Endspiel im Schach) Wissen über das Spiel zu gewinnen, das in einer wohldefinierten Aufgabe zu einer Performanz-Steigerung führt. Solche Aufgaben können z.B. sein: einfache Konzepte zu lernen, mit deren Hilfe ein Programm seine Spielstärke verbessern kann, unter Verwendung häufig auftretender Muster eine bessere Komprimierung der Datenbank zu erreichen, etc. Das Hauptproblem, das dabei zu lösen sein wird, ist, geeignetes Hintergrundwissen zu definieren, mit deren Hilfe sinnvolle Konzepte repräsentiert werden können, sowie Data Mining Methoden so zu adaptieren, das sie dieses Wissen effizient nutzen können.

UCT*

Ansprechpartner: JF

UCT ist ein Algorithmus, der klassische Spielbaum-Suche mit einer stochastischen Monte-Carlo Suche kombiniert. B* ist ein auf A* basiserendes Such-Verfahren, dessen Grundidee es ist, den möglichen Wertebereich einer Variante durch eine obere und untere Schranke einzuschränken.

Aufgabe dieser Master-Arbeit ist es, eine intervall-basierte Version des UCT-Algorithmus zu entwickeln und zu testen. Die ''ProveBest'' and ''DisproveRest'' Strategien  von B* sollen dabei für Monte-Carlo-Suche angepaßt werden. Dadurch läßt sich eine dynamisches Abbruch-Kriterium für die Monte-Carlo Iterationen realisieren.

Literatur:

  • Hans J. Berliner, Chris McConnell: B Probability Based Search. Artificial Intelligence 86(1): 97-156 (1996)
  • Hans J. Berliner: The B* Tree Search Algorithm: A Best-First Proof Procedure. Artificial Intelligence 12(1): 23-40 (1979)
  • G.M.J-B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik, and B. Bouzy. Progressive strategies for Monte-Carlo Tree Search. New Mathematics and Natural Computation 4(3), 2008.

Monte-Carlo Schach

Ansprechpartner: JF

Monte-Carlo Suche funktioniert sehr gut in Spielen wie Go, aber sehr schlecht in Schach (Ramanujan et al. 2010). In dieser Arbeit soll untersucht werden, inwieweit sich das Verhalten verbessern läßt, indem man in die Monte-Carlo Suche systematisch intelligente Züge (z.B. Schlage-Züge wie bei einer Ruhe-Suche oder Züge, die von einer Heuristik gut bewertet werden) einstreut.

Literatur:

Künstliche Intelligenz in kommerziellen Computer-Spielen

Ansprechpartner: JF

Die kommerzielle Spiele-Industrie beginnt gerade Methoden der Künstlichen Intelligenz zu entdecken, um den Unterhaltungswert ihrer Spiele zu steigern. Die Expertise für die KI-Methoden ist bei uns vorhanden, die Expertise für die Spielanwendung müßten Sie mitbringen. Wenn Sie eine Idee für ein diesbezügliches Projekt haben, können wir gerne darüber sprechen, ob sich dieses für eine Master- oder Bachelor-Arbeit eignet.

Materialien:

Reinforcement Learning

Hyper-Parameter Optimization for Reinforcement Learning

Ansprechpartner: C.Wirth

Themenbeschreibung:

Wie in den meisten Bereichen des Machine Learning, ist auch im Reinforcement Learning die Parametrisierung von Algorithmen ein gewichtiges Problem. Mit einer falschen Parametrisierung können selbst viel versprechende Ansätze unbefriedigende Ergebnisse liefern. Daher ist es wichtig eine effiziente und zuverlässige Methode zur Bestimmung dieser Hyperparameter zur Verfügung zu haben. Der wisschenschaftliche Standard hierbei ist aber noch immer die so genannte Grid-Search. Hierzu werden die Parameter regulär Unterteil und in jeder möglichen Kombination getestet. Dieses Verfahren findet zwar mit einer hohen Wahrscheinlichkeit eine gute Parametrisierung, ist aber sehr zeitaufwendig. Zudem ist es möglich, das die beste Parametrisierung nicht gefunden werden kann, da sie nicht Teil der vorgegebenen Unterteilung ist. Es wurden bereits diverse, effizientere Verfahren vorgestellt, wie z.B. evolutionäre Algorithmen, aber diese sind noch immer nicht in der Reinforcement Learning Gemeinschaft akzeptiert. Die Vorteile dieser Methoden müssten unabhängig von der Anwendungsdomäne evaluiert werden, da es ansonsten möglich ist, dass diese neueren Methoden nur in bestimmten Fällen zu bevorzugen sind. Eine komplett unabhängige Evaluierung ist natürlich nicht möglich, daher besteht Bedarf an einer weit gefächerten Auswertung über viele Domänen und Algorithmen.

Aufgabenbeschreibung:

Die Details der Aufgabe können nach Absprache variiert werden. Wahrscheinliche Elemente wären:

  • Implementation verschiedener Probleme und Algorithmen
  • Recherche bezüglich neuer Parameter-Optimierungsverfahren
  • Implementation neuer Parameter-Optimierungsverfahren

Grundlagen/Anforderungsprofil:

Primär relevant ist ein Interesse an wissenschaftlichen Vorgehensweisen und dem Durchführen von Experimenten im großen Maßstab. Kenntnisse in Java und Software Engineering sind von Vorteil. Bei einem zufriedenstellende Ablauf der Auswertungen, werden die Ergebnisse in eine wisschenaftliche Publikation aufgenommen, was mit einer entsprechenden Koautorenschaft einhergeht.

A A A | Drucken | Impressum | Sitemap | Suche | Mobile Version
zum Seitenanfangzum Seitenanfang