Laufende Diplom-, Master- und Bachelorarbeiten

Im folgenden finden Sie einen Überblick über laufende Diplom-, Master- und Bachelorarbeiten im Fachgebiet Knowledge Engineering (Prof. J. Fürnkranz). Es gibt auch eine Liste aktueller Themen, bereits abgeschlossene Arbeiten finden Sie hier.

Laufende Arbeiten

Legende

Themen im Detail

Ermittlung von Sudoku Schwierigkeitsstufen

Ansprechpartner: JF

Sudoku Puzzles kommen in unterschiedlichen Schwierigkeitsstufen, wobei allerdings weder die Skalen noch die Vergabe-Richtlinien der Schwierigkeitsstufen normiert sind. Im Web findet man zahlreiche Hinweise, wie man die Schwierigkeitsstufen ermitteln kann, beginnend von einfachen aber oft täuschenden Heuristiken wie der Anzahl der vorgegebenen Zahlen bis hin zu komplexen Massen wie die Komplexität der einzusetzenden Lösungstechniken. Aufgabe dieser Arbeit ist es, ein System zu entwerfen, welches mit Hilfe von Methoden des Präferenz-Lernens den Schwierigkeitsgrad eines gegebenen Puzzles vohersagt. Insbesondere müssen die folgenden Aufgaben gelöst werden:

• Recherche und Überblick über bestehende Techniken zur Ermittlung des Schwerigkeitsgrads eines Puzzles
• Auffinden geeigneter Mengen von Sudoku-Puzzles mit Schwierigkeitsgraden für Trainings-Zwecke
• Implementieren oder Auffinden eines Constraint-basierten Lösers
• Definition von Merkmalen zur Charakterisierung eines Problems, wobei sowohl flache Merkmale (solche die sich unmittelbar aus Betrachtung des Puzzles ergeben) als auch tiefe Charakteristike (solche die sich man nur durch Analyse des Lösungsprozesses erhalten kann) berücksichtigt werden sollen
• Einsatz von vorhandenen Techniken des Präferenz-Lernens zum Trainieren eines Lerners zur Vorhersage des Schwierigkeitsgrads aus den extrahierten Merkmalen eines Puzzles.

Vergleich verschiedener Ranking-Verfahren in Sport-Turnieren

Ansprechpartner: JF

In Sport-Wettkämpfen werden unterschiedlichste Verfahren eingesetzt um aus einer Vielzahl von paarweisen Vergleichen (z.B. Fußball-Spiele, Tennis-Spiele) eine Rangliste aller beteiligten Spieler oder Teams zu erstellen. Dabei treten verschiedenste Probleme auf, die gelöst werden müssen, wie z.B., daß verschiedene Spieler eine unterschiedliche Anzahl von Spielen spielen, oder daß nicht jeder Spieler gegen jeden anderen Spieler antreten kann.

Aufgabe dieser Arbeit ist es, einerseits eine Bestandaufnahme der in verschiedenen Sportarten verwendeten Verfahren zu machen, die dazugehörigen wissenschaftliche Literatur aufzuarbeiten, und ausgewälte Verfahren anhand von simulierten oder echten Daten miteinander zu vergleichen.

Literatur:

• Stephen Gordon and Michel Truchon. Social choice, optimal inference and figure skating. Social Choice and Welfare, 30(2):265-284, 2008.
• Adriana Birlutiu and Tom Heskes. Expectation propagation for rating players in sports competitions. In Proceedings of the 11th European Symposium on Principles of Knowledge Discovery in Databases (PKDD-07), pages 374-381, Warsaw, Poland, 2007. Springer-Verlag.

Evaluierung der Vorhersagegenauigkeit verschiedener Fragebögen zur Hautkrebs-Erkennung

Ansprechpartner: FJ & JF

• Thema

In dieser Arbeit soll ein Vergleich verschiedener Fragebögen zur Früherkennung von Hautkrebs  durchgeführt werden. Da Hautkrebs weltweit auf dem Vormarsch ist, gewinnt eine Früherkennung immer mehr an Bedeutung. Hierfür sind aber möglichst stichhaltige Fragebögen unumgänglich. Nicht nur die manuelle Auswertung, sondern insbesondere die automatische Analyse steht in direkter Abhängigkeit zur Güte des Fragebogens. Aus diesem Grund ist ein Vergleich verschiedener Fragebögen ein erster Schritt in Richtung zu einem universellen Fragebogen, der klare, einfach verständliche Fragen enthält.

• Aufgabenstellung

Im Rahmen einer vorherigen Arbeit [1] wurde bereits ein deutscher Fragebogen analysiert. Diese Arbeit soll nun auf 3 englische Fragebögen erweitert werden. Ein Tool zur Konvertierung des deutschen Fragebogens ist bereits vorhanden, dieses müsste aber auf die englischen Bögen adaptiert werden.

Der Einstiegspunkt für diese Arbeit wird das Ende der vorherigen Arbeit sein. Als erstes sollte man sich mit dem Thema vertraut machen. Dann sollten die gleichen Vorverarbeitungsschritte wie zuvor auf die neuen Fragebögen angewendet werden. Ein Hauptaugenmerk liegt auf der Analyse welcher Fragebogen die höchste Vorhersagegenauigkeit hat. Daran anschließend soll herausgefunden werden aus welchen Gründen sich bestimmte Fragebögen oder auch einzelne Fragen besser zur Vorhersage von Hautkrebs eignen als andere.

Eine weitere Idee ist, einen universellen Fragebogen in Englisch zu erstellen, der dann als Grundlage für andere Fragebögen genutzt werden kann. Eine Zusammenarbeit mit Sprachwissenschaftlern ist im weiteren Verlauf der Kooperation angestrebt, um beispielweise die Art der Fragen zu analsysieren, sowie dabei behilflich zu sein schlechte Fragen zu verbessern. Anhand des universellen Fragebogens sollten sich individuelle Bögen leicht erstellen lassen.

• Vorkenntnisse

Grundkenntnisse und gute praktische Erfahrungen in maschinellem Lernen (wie sie z.B. in der Vorlesung Maschinelles Lernen: Symbolische Ansätze vermittelt werden).

• Betreuung

Diese Arbeit wird in Kooperation mit der Qualitätsgemeinschaft südhessischer Dermatologen e.V. angeboten. Dessen Vorsitzender Dr. med. Matthias Herbst wird der Ansprechpartner auf ärztlicher Seite sein, mit dem insbesondere bei medizinischen Fragen eng zusammengearbeitet werden sollte.

• Literatur

[1] Daniel Fischer – Maschinelles Lernen zur Hautkrebs-Vorhersage. Bachelor Thesis. KE Group. 2011.

Trainieren eines Poker-Computerspielers

Bisher galt im Computerpoker die Auffassung, daß die erfolgsversprechendsten Algorithmen auf Simulation und Durchsuchen des Spielbaums basieren würden. So waren Monte-Carlo und UCT-Suche, die zufällig sehr viele Pfade im Spielbaum berechnen, und in jüngerer Zeit die Berechnung von pseudo Nash-optimaler Spieler durch Simulation, auch im Rahmen unser alljährigen TUD Computer Poker Challenge die Verfahren, die verwendet werden sollten.
Maschinelles Lernen und somit aus Erfahrung lernende Algorithmen kamen, wenn überhaupt, nur zur Gegnermodellierung und zur Begrenzung des Suchbaums zum Einsatz.

Bei der letzten 2011 AAAI Computer Poker Competition konnte ein Bot, der auf fall-basierten Verfahren aufbaut, gute bis sehr gute Ergebnisse erzielen. Er machte sich dabei die mittlerweile im großen Umfang verfügbaren Spieldaten zu Nutze und lernte, die Spielweise und das Verhalten eines bestimmten Spielers nachzuahmen. Das zum Einsatz kommende Lernverfahren basiert im Grunde auf dem simplen Durchsuchen einer Datenmenge nach gleichen oder ähnlichen Datenpunkten.

Ziel der Arbeit ist es, ein Pokerbot nach Vorbild des erwähnten Bots zu entwickeln und in ein vorhandenes Framework zu integrieren. Es soll dabei allerdings möglich sein, aus verschiedenen Lernverfahren zu wählen und somit auch Modell-basierte Verfahren, die den Stand der Forschung darstellten, zu verwenden. Dies ist bei dem erwähnten Bot nicht möglich. Die Verwendung von verschiedenen Lernverfahren und verschiedener Spieldatensätze soll experimentell evaluiert werden.

Referenzen:

• Jonathan Rubin, Ian Watson. (2011). Successful Performance via Decision Generalisation in No Limit Texas Hold'em. In Case-Based Reasoning. Research and Development, 19th International Conference on Case-Based Reasoning, ICCBR 2011.

Vorhersage von Bahnpreisen

Gemeinsame Arbeit mit dem FG Algorithmik, Ansprechpartner: FJ

Die Arbeitsgruppe Algorithmik arbeitet an einem multikriteriellen Fahrplanauskunftssystem für Bahnverbindungen. Das System sucht nicht nur die schnellste Verbindung zwischen zwei Bahnhöfen, sondern auch umstiegsarme, bequeme und günstigse Verbindungen. Die Verbindungssuche verwendet einen generalisierten Dijkstra Algorithmus der mit multiplen Kantengewichten umgehen kann.

Ein kritisches Bottleneck bei der Berechnung von Verbindungen sind die Preise. Im Gegensatz zu linearen Kriterien wie Fahrtzeit oder Anzahl der Umstiege ergeben sich Preise nicht einfach als Summe der Kantengewichte, sondern werden mit Hilfe eines Relationensystems berechnet, welches über eine Blackboxkomponente in das System eingebunden ist.

Leider ist die Verwendung der Blackboxkomponente viel zu langsam, um sie im Algorithmus nach jeder Kante neu anzufragen; für die Suche wird daher eine schnelle und möglichst exakte Schätzung des Preises benötigt.

Als Lösungsmöglichkeiten sehen wir

1. die Blackbox mit Methoden des maschinellen Lernens zu lernen und nachzubauen und
2. eine Methode zu entwickeln, mit der man Preise möglichst exakt auf die Kanten eines Hilfsgraphen verteilen kann um Preise analog den anderen Kriterien zu behandeln.

Gegeben sind:

Auskunftssystem: zum Erzeugen von beliebig vielen Verbindungen

Verbindung: inkl. verwendeter Strecke

Preis-Blackbox: IN: Verbindung, OUT: Verbindung + Preis

Beiden Verfahren sollen implementiert und evaluiert sowie gegen das bestehende Legacy-System getestet werden.

Von Vorteil sind Kenntnisse im Maschinellen Lernen (Vorlesung „Maschinelles Lernen – Symbolische Ansätze”, „DKE” oder auch „Künstliche Intelligenz”). Diese sind aber nicht notwendig, müssten sich dann aber angeeignet werden.

Die Arbeit wird vom FG Algorithmik sowie dem FG Knowledge Engineering betreut, wobei erstere für Fragen bezüglich des Fahrplanauskunftssystems verantwortlich sind und das FG Knowledge Engineering für Fragen bezüglich des maschinellen Lernens zur Verfügung steht.

Vergleich von SVM und Regel- und Entscheidungsbaum-Lernern

Ansprechpartner: JF

Support-Vector Maschinen zeigen generell eine gute Performanz, wenn ihre Parameter an die Daten angepaßt werden, was auch durchaus üblich ist. Entscheidungsbaum-Lerner (wie C4.5) bzw. Regel-Lerner (wie Ripper) werden oft in ihrer Standard-Konfiguration, ohne entsprechende Anpassung der Parameter verwendet. Ziel dieser Bachelor-Arbeit ist eine breite empirische Studie, die bereits vorhandene Implementierungen von SVMs und Regel-Lerner vergleicht, wobei für beide Systeme die Parameter gründlich optimiert werden sollen.

Regellernen zur Verbesserung der Studiensituation in den Anfangssemestern des Informatikstudiums

Ansprechpartner: FJ & Sabine General & Tim Neubacher

Thema: In dieser Arbeit soll basierend auf ausgewerteten Fragebögen einiger vorangegangener Semester ein Regellernsystem geschaffen werden, welches einerseits interessante Regeln lernt und andererseits über eine akzeptable Genauigkeit bei der Klassifikation von Studierenden verfügt. Die Hauptaufgabe des Systems ist es eine Einteilung von Studierenden, die bestimmte Kriterien erfüllen, vorzunehmen. Hierbei soll geprüft werden inwiefern ein Studierender einen gesonderten Beratungstermin benötigt oder nicht.
Aufgabenstellung: Im Rahmen einer vorherigen Arbeit [1] wurden bereits Daten des Sommersemesters 2011 und des Wintersemesters 2011/12 analysiert und es wurde geprüft wie man die Fragebögen, die im moodle System verfügbar sind, entsprechend in ein maschinenlesbares Format (.arff) konvertieren kann. Erste Auswertungen mit verschiedenen Methoden des maschinellen Lernens sind ebenfalls bereits durchgeführt. Die Hauptaufgabe dieser Arbeit liegt demnach in einem breitflächigen Vergleich verschiedener Methoden (sowohl statistischer als auch symbolischer). Darüber hinaus soll über Feintuning verschiedener Regellerner versucht werden interessantere sowie genauere Regeln als bisher zu finden.
Das Ziel der Arbeit ist ein System zu schaffen mit welchem eine Vorauswahl von Studierenden machbar ist, da diese Arbeit momentan noch manuell durchgeführt werden muss.
Vorkenntnisse: Grundkenntnisse und gute praktische Erfahrungen in maschinellem Lernen (wie sie z.B. in der Vorlesung Maschinelles Lernen: Symbolische Ansätze vermittelt werden)
Betreuung: Diese Arbeit wird in Kooperation mit dem FG Knowledge Engineering (Bereich Maschinelles Lernen), dem Mentorensystem Informatik (Bereich Fragebögen) sowie der Fachstudienberatung (Bereich Beratungsgespräche) angeboten und zu gleichen Teilen betreut.
Ansprechpartner:
Frederik Janssen, FG Knowledge Engineering & Fachstudienberatung
Sabine General, Mentorensystem Informatik
Tim Neubacher, Fachstudienberatung
Literatur:
[1] Maxi Neubacher – Verbesserung und Weiterentwicklung der Abläufe im Mentorensystem (geleitet von der Hochschuldidaktischen Arbeitsstelle) des Fachbereichs Informatik der TU Darmstadt – Klassifizierung von Studierenden mit schlechtem Prüfungserfolg im ersten Semester, Praktikum, 09.02.2012.