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.

Featured Theses

Multilabel Rule Learning

Ansprechpartner: FJ & ELM

Diese Arbeit setzt auf bisherigen Arbeiten zu diesem Themenbereich auf. Daher arbeiten Sie an einem aktuellen Forschungsthema. Zusätzlich zu den Credit Points winkt also eine Mit-Autorenschaft bei den weiteren geplanten Veröffentlichungen.

Thema:
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:

 

Machine Learning

Top-Down induction of classifier trees.

Ansprechpartner: JF

Classifier Trees sind eine Möglichkeit, Multi-Klassen-Probleme in eine hierarchische Struktur abzubilden, wobei jeder Knoten eine Entscheidung zwischen den Nachfolge-Knoten trifft. Ein konventioneller Multi-Klassen-Klassifizierer entspricht einem einfachen Baum, der nur aus der Wurzel und je einem Blatt für jede der Klassen besteht. Komplexere Bäume nehmen eine sukzessive Verfeinerung vor, indem sie z.B. zuerst einen Klassifizierer verwenden, um zu entscheiden, ob ein Beispiel den Klassen A/B bzw. C/D angehört, und dann je einen Klassifizierer für die weitergehende Entscheidung zwischen A und B bzw. C und D trainieren.

Aufgabe dieser Arbeit ist es, ein bereits definiertes Verfahren in der Data Mining Umgebung Weka zu implementieren und mit anderen Multi-Klassen-Klassifikationsverfahren experimentell zu vergleichen.

    Data Mining

    Outlier Detection in Satellite Data

    Ansprechpartner: JF

    An important and tedious task in the monitoring of satellite data is to recognize abnormal behavior of the satellite from the sensor information that is transmitted from the satellite to the ground. For this task, time series of up to 40,000 parameters of different degrees of relevance have to be manually screened by ground staff. A domain expert usually looks at about 50 of them in order to recognize potential outliers. In addition, known and unknown external events may cause abnormal behavior the sensors (e.g.,Was the satellite in the sun or in the earth shadow?Was some on-board equipment like the camera turned on?). While such outliers do not constitute abnormal behavior, they are nevertheless interesting to detect, in particular if a suitable explanation can be found.

    The main task of this thesis is to develop automated support for this task via data mining and machine learning algorithms, in particular with outlier detection and subgroup discovery techniques. The work will be conducted in cooperation with Solenix, a proficient startup company targeting the space industry, in particular the European Space Agency ESA/ESOC.

    Prerequisites

    Ideally, a student working on this thesis should bring

    • Basic knowledge in machine learning and data mining (at least one course in these areas)
    • Practical experience with data mining tools such as Weka or RapidMiner
    • Good communication skills (English) that facilitate working in the intersection between TU Darmstadt and the Solenix company

    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)

      Competitions im Data Mining

      Im Bereich des Data Mining gibt es eine Vielzahl an Wettbewerben, Competitions und Challenges. Ein jährlicher Wettbewerb, an dem die Knowledge Engineering Group regelmäßig teilnimmt, ist der  Data Mining Cup. Dabei werden besonders Vorhersageprobleme aus dem Feld der Recommender Systeme gestellt. Ein weiterer Wettbewerb, diesmal aus dem Bereich der Künstlichen Intelligenz, ist die Computer Poker Competition. Die Teilnahmen fanden jeweils im Rahmen eines Praktikums statt.

      Wir möchten Studierenden die Möglichkeit geben, auch an weiteren interessanten Wettbewerben im Bereich des Data Mining und der Künstlichen Intelligenz teilnehmen zu können. Dies wird im Normalfall im Rahmen einer Studienarbeit stattfinden, aber je nach Aufwand und Vor- und Nacharbeit ist auch eine Bachelor- oder Masterarbeit oder ein Projektpraktikum denkbar.

      Im Folgenden stellen wir eine kleine Liste laufender bzw. abgeschlossener (soweit aktualisiert) Wettbewerbe statt:

      Weitere Möglichkeiten, um sich über aktuelle Wettbewerbe zu informieren, bieten:

      Divide-and-Conquer-Lernen von SPARQL-Abfragen

      Ansprechpartner: FJ

      Diese Arbeit wird zusammen mit Heiko Paulheim, Uni Mannheim, betreut.

      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.

        Regel-Lernen

        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 nirgends 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.

        Lernen von symbolischen Beschreibungen von Neuronalen Netzen durch Regeln

        Ansprechpartner: FJ & ELM & JF

        Neuronale Netze zeigen eine gute Perfomanz in Bezug auf die Genauigkeit. Ein großes Problem ist aber, dass man sie nicht gut interpretieren kann. Man ist zwar in der Lage, die Gewichte der Eingänge an jedem Neuron zu deuten, jedoch müssen diese nicht unbedingt ausschlaggebend sein, da es zumeist eine Reihe von Hidden Layern im Netzwerk gibt und die Netzwerke üblicherweise voll verdrahtet sind. Daher ist eine Idee neuronale Netze mit Regelmengen zu beschreiben, welche dann besser interpretierbar sind.
        Diese Arbeit ist flexibel, kann also je nach Art im Umfang angepasst werden (Bachelorarbeit, Masterarbeit, Diplomarbeit, Forschungsprojekt, Studienarbeit etc.). Im Groben gibt es momentan vier Ideen, derartige Beschreibungen zu erstellen:

        1. Die Zielvariable im Trainingsdatensatz wird mit der Ausgabe des Netzes ersetzt. Dann wird wie gewohnt eine Regelmenge gelernt. Nun schaut man sich für jedes Beispiel an, welche Neuronen und welche Regeln für dieses feuern, um so eine "Karte" des Netzes zu erstellen (welche Regeln decken welche Regionen im Netz ab).
        2. Man legt die Klasse eines Beispiels am Ausgang des Netzes an und schaut sich an welche Eingänge für die derartige Ausgabe verantwortlich sind (Backpropagation). Da nicht nur ein Eingangssignal (Trainingsbeispiel) für den angelegten Zielwert in Frage kommt, muss man beispielsweise simulieren (Monte Carlo o.Ä.) um so z.B. Intervalle für die jeweiligen Features am Eingang zu erhalten. Basierend auf diesen Distributionen kann man nun versuchen, eine Regelmenge zu lernen, die diese widerspiegelt.
        3. Beim sog. Deep Learning von Neuronalen Netzen wird davon ausgegangen, dass Neuronen in den Hidden Layern versteckte Features darstellen. Nun kann man versuchen, jeden Layer mit einer Regelmenge zu beschreiben, also für den Inputlayer hätte man x -> h_1, für den ersten Hidden Layer dann h_1 -> h_2 bis man beim n-ten Hiddenlayer bei h_n -> y angelangt ist. Man erhält so für jeden Zwischenlayer eine symbolische Repräsentation.
        4. Bei ungeordneten Regelmengen ist die Frage, wie man die Vorhersagen der einzelnen Regeln aggregiert. Eine Möglichkeit anstelle von Standardverfahren wie Voting wäre die Aggregation zu lernen, indem man als Eingabe des Neuronalen Netzes die Regeln verwendet (Signal: gefeuert oder nicht). Das Netz würde nun lernen, welche Klasse abhängig vom Feuern welcher Regeln vorhergesagt wird. Dies könnte man dann als Aggregation verwenden.

        Literatur

          Präferenz-Lernen

          Ordered Classifier Chains

          Ansprechpartner: JF, Ulf Brefeld

          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 gemeinsam mit Prof. Brefeld betreuten Arbeit ist einerseits, verschiedene einfache Techniken zur Klassenanordnung zu implementieren, empirisch miteinander zu vergleichen und ggf. auch theoretisch zu analysieren, andererseits einen vorgegebenen, auf Markov Random Fields basierenden Ansatz zu implementieren und mit einfachen Benchmarks zu vergleichen.

          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

            Automatische Schwierigkeitsanpassung in einem Serious Game

            Ansprechpartner: JF

            In vielen Spielen ist es wichtig, dass die Schwierigkeitsstufe automatisch angepasst wird, sodass der Spieler das Spiel weder als zu einfach noch als zu schwierig empfindet. Bei Serious Games, also bei Spielen, mit denen ein "ernsthafter" Zweck dahintersteht, spielt dieser Aspekt eine besondere Rolle, da z.B. bei Health Games der Spieler nach seiner jeweiligen Fitness gefordert werden soll aber auch nicht überfordert werden darf.

            Aufgabe dieser Arbeit ist es, in einem vorhandenen Serious Game Verfahren des maschinellen Lernens einzusetzen, um aus den Aktionen des Spielers auf sein Spiel-Niveau zu schließen, und dann einen entsprechenden Level einzustellen. Diese Arbeit wird gemeinsam mit Stefan Göbel (Serious Games Gruppe KOM) und Ulf Brefeld (KMA) angeboten.

            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:

            Pseudo-Nash-optimaler Computerspieler für 3-Spieler-Limit-Poker

            Ansprechpartner: ELM

            Eine Nash-optimale Spielweise bedeutet grob gesprochen, daß diese verlustminimierend ist. Die exakte Bestimmung einer solchen Strategie ist zwar prinzipiell möglich, jedoch für ein Spiel wie 2-Player (2P) Heads-Up Limit (noch) nicht vollständig lösbar, zumindest nicht in akzeptabler Zeit. Es ist jedoch möglich durch ein Verfahrens namens Counterfactual Regret Minimization (CRM) relativ effizient eine gute approximative Lösung zu berechnen. Diese Strategie wird auch von den momentan stärksten Pokerbots eingesetzt. Die Berechnung der pseudo Nash-optimalen Lösung beschränkt sich momentan leider auf 2P Spiele.

            Im Rahmen der TUD Computer Poker Challenge im SS 11 wurde erstmals damit experimentiert, einen 2P CRM-Spieler für die 3-Spieler (3P) Variante des Spiels zu verwenden in dem z.B. bestimmte Spielzustände eines 2P-Spiels auf ein 3P-Spiel abgebildet werden. Dieses Verfahren wurde auch genauer im Rahmen einer Bachelor-Arbeit untersucht. Die Erkenntnis ist, daß sich die Abbildungen in bestimmten Situationen durchaus verwenden lassen, aber leider nicht in allen.

            Ziel dieser Arbeit ist es deshalb, den CFR-Algorithmus selbst so anzupassen, daß dieser direkt (teilweise) auf 3P-Spiele anwendbar ist.

            Für die Implementierung steht sowohl unser Poker Framework zur Verfügung, das die grundlegende Logik eines Pokerspielers implementiert und leicht Experimente ermöglicht, als auch die Implementierung des CFR-Algorithmus und der Source-Code vergangener Bots aus dem Praktikum.

            Referenzen:

            • Martin Zinkevich, Michael Johanson, Michael Bowling, Carmelo Piccione: Regret Minimizationin Games with Incomplete Information, NIPS, 2007
            • Nick Abou Risk, Duane Szafron: Using Counterfactual Regret Minimization to Create Competitive Multiplayer Poker Agents, AAMAS, 2010
            • Peter Glöckner: Abbildung eines 2-Spieler Computerspielers auf 3-Spieler-Limit-Poker, 2013

                Studiendekanat

                Studienarbeit "Weiterentwicklung einer Software für das Management im Ausland erbrachter Leistungen (MAL)"

                Im Studiendekanat des Fachbereichs Informatik wurde bereits eine Software zum Management im Ausland erbrachter Leistungen implementiert (MAL). Es gibt jedoch eine Reihe von Features, die in der bisherigen Version noch nicht vorhanden sind. Ein Teil dieser soll in einer variablen Studienarbeit mit entweder 6 CP oder 9 CP nun implementiert werden. Die momentane Version der Software basiert auf einer mit Hibernate erstellten Datenbank und ist in Java mit Web Services implementiert.

                Aufgabe(n):
                Langfristig plant das Studiendekanat eine Software mit der alle Aspekte eines Auslandsaufenthalts abgedeckt und automatisiert bearbeitet werden können. Demnach sollte man folgende Punkte mit der Software erledigen können (wobei die aktuelle Version Punkt 1 bereits umfasst):

                1. Datenbank: umfasst alle Länderbereiche, Partneruniversitäten, Kurse dieser sowie deren Anerkennung mit Ausschlüssen der Veranstaltungen des Fachbereichs
                2. Automatische Dokumenterstellung (Nebenvereinbarung zum Learning Agreement, ...)
                3. Erstellung von Views auf die Datenbank
                4. Statusabfragen und –updates für jeden Studierenden der ins Ausland gehen möchte
                5. Kryptografische Absicherung aller sicherheitsrelevanten Aspekte
                6. Automatische Eingaben von neuen Kursen (Parsen verschiedenster Dokumenttypen)
                7. Erstellung automatischer Tests für alle Funktionalitäten

                Ablauf:

                • Einarbeitung in bestehende Software (Ecplise oder beliebige andere Umgebung)
                  • währenddessen: Bearbeitung kleiner Aufgaben; Fehlerbehebung
                • Je nach Umfang: einen oder mehrere Teilaspekte möglichst gekapselt programmieren (Web-Service Architektur sollte dies vereinfachen)

                Vorkenntnisse:

                • Exzellente Java-Kenntnisse sowie Erfahrungen mit Entwicklung von Web-Services
                • Kenntnisse der Abläufe eines Auslandsaufenthalts (nicht zwingend notwendig)

                Betreuung:
                Die Studienarbeit wird in enger Zusammenarbeit mit dem Studiendekanat Informatik und hier mit dem Ansprechpartner Frederik Janssen sowie dem Hiwi für Auslandsangelegenheiten durchgeführt. Die Laufzeit ist variabel, es ist also möglich auch in den Semesterferien zu arbeiten oder für die Lernphase die Arbeit kurzzeitig auszusetzen. Aussagekräftige Anfragen bitte per Mail.

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