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.

      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:

        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

        Heuristiken für Model Trees

        Ansprechpartner: FJ & CW

        Aus Gründen wie beispielsweise Interpretierbarkeit oder geringere Modellgrößen werden symbolische Lernverfahren wie Entscheidungsbäume oder Regellerner auch zum Lernen sog. Regressionsproblemen verwendet. Bei diesen muss nicht ein nominaler Klassenwert vorhergesagt werden sondern eine numerische Klasse (also eine Funktion gelernt werden). Im Gegensatz zu statistischen Verfahren ist es symbolischen Algorithmen nicht möglich eine kontinuierliche Funktion zu lernen, sondern die Vorhersage setzt sich aus einzelnen Werten zusammen, bildet also eine Treppenfunktion. In der Literatur gibt es bereits Verfahren, die beide Welten vereinen, indem ein Baum oder eine Regelmenge gelernt werden mit dem Unterschied, dass nun in den Blättern bzw. Heads der Regeln keine einzelnen Werte mehr stehen, sondern wieder ein lineares Modell (Bäume werden dann Model Trees genannt). Der wohl populärste Regellernalgorithmus ist M5Rules bei welchem Regeln sukzessive aus einem Model-Tree gelernt werden. Als Heuristik zum Aufspalten der Daten in Regionen in denen ein lineares Modell möglichst gut anpassbar ist wird die SDR genommen, die Reduktion in der Standardabweichung gegeben der aktuelle Split.
        In dieser Arbeit soll ein anderes Maß hierfür implementiert werden welches direkt die Apassbarkeit eines linearen Modells misst. So soll in einem ersten Ansatz für jeden möglichen Split der Fehler eines auf die entsprechenden Teilbäume angepassten linearen Modells verwendet werden und im weiteren Verlauf der Arbeit bessere bzw. effizientere Heuristiken gefunden werden.

            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:

                  Kontakt
                  small ke-icon

                  Knowledge Engineering Group

                  Fachbereich Informatik
                  TU Darmstadt

                  S2|02 D203
                  Hochschulstrasse 10

                  D-64289 Darmstadt

                  Sekretariat:
                  Telefon-Symbol +49 6151 16-21811
                  Fax-Symbol +49 6151 16-21812
                  E-Mail-Symbol info@ke.tu-darmstadt.de

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