Game Theory: Distributed Solving (Master)

One of the grand challenges of Artificial Intelligence research is to solve games by proving perfect strategies. Recent success have been reported for 2 person limit Texas hold'em poker (Science journal, 2015) and checkers (Science journal, 2007). (Weakly) solving a game means to know which party can win (and how) from the starting position. Those solutions partially have applications in economy, but are also done for the sheer joy of solving those hard games.

The aim of this master thesis is to design a distributed game solver, which can run on a cluster of processing nodes. Once this is done, it should be applied to a game of choice (Skat, Chess and Go are the current candidates). Depending on the game of choice, a detailed solving strategy will be designed to allow taking the particularities of each game into account (e.g. for Skat a mixed strategy Nash equilibrium needs to be computed). Access to very large computational resources will be provided such that it is likely that more complex (fragments of) games can be solved.

What we expect:

• the master thesis is mostly suitable for excellent students who aim at a scientific career and are motivated by achieving unprecedented results
• motivation to read a book on game theory basics (approx. 1–2 weeks effort)
• motivation to obtain basics on distributed computing (e.g. AMQP)
• programming knowledge in at least one of these languages: C++, Java, Python

What we offer:

• comprehensive supervision
• very significant computational resources
• support & collaboration in follow-up publications

if you are interested in this topic, please contact: Jens Lehmann – lehmann@informatik.uni-leipzig.de

Erweiterung des LinkedGeoData-Browsers (Masterarbeit)

Das LinkedGeoData-Projekt (LGD) umfasst die Konvertierung von OpenStreetMap Datensätzen nach RDF, sowie das Verlinken mit anderen Wissensbasen.
Desweiteren erlaubt der LGD-Browser die visuelle Darstellung der Daten auf einer Karte.

Ziel der Arbeit ist das Überarbeiten des Browsers gemä­ß der im Rahmen der Arbeit noch näher zu spezifizierenden Anwendungsfälle. Dabei liegt der primäre Fokus auf der Performanz der im Hintergrund ablaufenden Anfragen an die Datenquellen. Für die Anwendungsfälle sollen daher verschiedene Datenrepräsentationen und Anfragestrategien erarbeitet und bewertet werden. Die Ergebnisse sollen in eine Anpassung des Browsers an die Anwendungsfälle einflie­ßen, wofür eine passende Architektur zu konzipieren und umzusetzen ist. Sofern es die Zeit erlaubt, wäre es möglich, den überarbeiteten Browser noch in einem Usability-testing zu unterziehen.

Aufgabenstellung

• Konzeption von Anwendungszenarien für den Browser
• Evaluation verschiedener Repräsentationen von Geodaten und entsprechender Querystrategien in Bezug auf Performanz
• Konzeption einer geeigneten Architektur des Browsers
• Implementierung, dabei ggf. Anpassung der GUI
• Eventuell Usability-testing

Vorraussetzungen

• Kenntnisse in PHP und Java-Script
• Kenntnisse in Java und Semantic Web-Technologien vorteilhaft aber nicht Bedingung

Wir bieten

• Umfassende Betreuung durch am Thema stark interessierte Mitarbeiter
• Mitarbeit an Publikationen (falls gewünscht)

Bei Interesse können Sie sich an Claus Stadler und Jens Lehmann wenden.

Geo-Spiel: Interlinking

Das LinkedGeoData-Projekt (LGD) umfasst die Konvertierung von OpenStreetMap Datensätzen nach RDF, sowie das Verlinken mit anderen Wissensbasen. Desweiteren erlaubt der LGD-Browser die visuelle Darstellung der Daten auf einer Karte.

Analog wurde in der AKSW-Gruppe mit VeriLinks ein Spiel-Framework entwickelt, dessen Kernidee es ist Spieler im Hintergrund Verknüpfungen (Links) zwischen Wissensbasen validieren zu lassen. Mehrere Spieler können dabei um Punkte / Geld spielen, während sie wertvolles Feedback zu den Links liefern.

Kernidee dieser Arbeit ist es beide Komponenten zu vereinigen: Der Spieler startet (analog zu Spielen wie Parallel Kingdom) auf einer Karte, z.B. dem Ort an dem er sich gerade befindet. Auf diesem Kartenausschnitt werden Elemente aus Linked Geo Data angezeigt, z.B. bestimmte Häuser, Restaurants, Sehenswürdigkeiten, Pubs usw. Gleichzeitig sollen Objekte aus anderen Wissensbasen angzeigt werden, z.B. Bilder aus Flickr. Ziel ist es die Objekte zuzuordnen, d.h. einem Linked Geo Data- Objekt ein Objekt aus einer anderen Wissensbasen zuzuordnen. Zum Beispiel kann der Spieler entscheiden, ob ein bestimmtes Bild tatsächlich zu einer Sehenswürdigkeit gehört. Wenn ein Spieler mit seiner Entscheidung mit anderen Spielern übereinstimmt, so erhalten diese Spieler Punkte. Die Punkte können dann genutzt werden um bestimmte Fähigkeiten zu erlernen, Territorium zu beanspruchen usw. Der Arbeit ist an der Stelle keine Grenze gesetzt.

Ihre Aufgabe ist:

• Entwickeln eines Online-Spiels nach der oben beschriebenen Idee
• Einarbeitung in Semantic Web Technologien wie RDF

Folgende Voraussetzungen und Fähigkeiten sind für die Bearbeitung der Arbeit notwendig:

• Studium der Informatik oder vergleichbarer Studiengänge
• Javascript-Kenntnisse
• Interesse an Webprogrammierung
• Interesse an Semantic Web

Entsprechendes Wissen kann ggf. auch während der Arbeit vermittelt bzw. erarbeitet werden. Die Arbeit kann als Bachelor-/Master- bzw. Diplomarbeit belegt werden.

Wir bieten eine umfangreiche Betreuung, sowie Hilfe bei der Einarbeitung in das Thema. Die Arbeit ermöglicht Resultate aus einem aktuellen Forschungsgebiet mit guter Zukunftsperspektive in die Praxis umzusetzen.

Sollten wir Ihr Interesse geweckt haben, wenden Sie Sich bitte an: Claus Stadler – cstadler@informatik.uni-leipzig.de Jens Lehmann – lehmann@informatik.uni-leipzig.de

Distributed Researcher Network

Semantic Web Technologien erlauben den globalen Austausch von Informationen. Insbesondere sind in den letzten Jahren Ideen entwickelt wurden um Daten dezentral verwalten zu können, wie z.B. hier beschrieben. In dieser Arbeit sollen verteilte Semantic Web Technologien am Anwendungsszenario von Forscherwebseiten (wie z.B. http://jens-lehmann.org ) realisiert werden. Die meisten Forscher verwalten in irgendeiner Form Publikationen, Präsentationen, Ereignisse usw. Um den Verwaltungsaufwand dafür zu reduzieren ist eine Kombination aus verschiedenen Datenquellen notwendig: 1.) Information die aus zentralen Quellen kommen, z.B. Publikationen aus Google Scholar. 2.) Informationen die aus dem Netzwerk des Forschers kommen, z.B. kann ein Ko-Autor eines Artikels bereits Informationen hinterlegt haben (z.B. Thema des Artikels oder die Zuordnung zu einem Projekt), die man selbst wiederverwenden möchte. 3.) Selbst erstellte Informationen. Mit Techniken des verteilten semantischen Webs lassen sich diese Szenarien realisieren. Die prinzipielle Protokoll- und Toolunterstützung existiert bereits, z.B. im OntoWiki Tool. Ziel der Arbeit ist die Anpassung auf den konkreten Anwendungsfall der Erstellung von Forscherwebseiten, d.h. insbesondere a) Synchronisationsdienste mit z.B. Google Scholar und b) die Entwicklung eines Front-Ends (d.h. der eigentlichen Forscherwebseite) unter Nutzung der im Backend gesammelten Daten. Solch ein System bietet Vorteile gegenüber existierenden Möglichkeiten für einen Wissenschaftler eine eigene Webseite zu erstellen:

• Vorteile gegenüber normalen traditionellen Webseiten:
  • weniger Verwaltungsaufwand, da z.B. nur ein Autor eine Publikation eintragen muss
  • viel mehr Möglichkeiten beim browsen/filtern/visualisieren
  • bessere Wiederverwendung der Daten z.B. können sie dann leichter den Seiten von Arbeitsgruppe oder Projekt eingeblendet werden
• Vorteile gegenüber arbeitsgruppen-/projektspezifischen Seiten:
  • viele Forscher wechseln mehrfach die Arbeitsgruppe während ihrer Karriere – statt dann woanders neu anzufangen (ev. mit einem anderen System) kann man einfach existierende Daten behalten
• Vorteile gegenüber zentralen Diensten wie Google Scholar, MS Academic Search:
  • man hat selbst die Kontrolle über seine Daten
  • höhere Qualität
  • man bestimmt selbst was man präsentiert (z.B. nicht nur Publikationen sondern auch Präsentationen, Informationen zu eingeworbenem Funding usw.)
  • man kann die eigenen Daten beliebig anreichern z.B. nach verschiedenen Themen / Projekten gruppieren oder eigene Kurzzusammenfassungen schreiben (siehe z.B. http://korrekt.org)

Ihre Aufgabe ist:

• Entwickeln von Synchronisationsdiensten z.B. Google Scholar, Bibsonomy, MS Academic Search, DBLP
• Anpassung des Onto Wiki- Systems z.B. spezielle Eingabe-Templates
• Entwicklung eines leichtgewichtigen, flexiblen Front-Ends für Forscherwebseiten

Folgende Voraussetzungen und Fähigkeiten sind für die Bearbeitung der Arbeit notwendig:

• Studium der Informatik oder vergleichbarer Studiengänge
• Javascript-Kenntnisse
• PHP-Kenntnisse
• Interesse an Webprogrammierung
• Interesse an Semantic Web

Entsprechendes Wissen kann ggf. auch während der Arbeit vermittelt bzw. erarbeitet werden. Die Arbeit kann als Bachelor-/Master- bzw. Diplomarbeit belegt werden.

Wir bieten eine umfangreiche Betreuung, sowie Hilfe bei der Einarbeitung in das Thema. Die Arbeit ermöglicht Resultate aus einem aktuellen Forschungsgebiet mit guter Zukunftsperspektive in die Praxis umzusetzen.

Sollten wir Ihr Interesse geweckt haben, wenden Sie Sich bitte an: Sebastian Tramp – tramp@informatik.uni-leipzig.de Jens Lehmann – lehmann@informatik.uni-leipzig.de

Games with a Purpose: Interlinking

Games with a Purpose ist eine Forschungsrichtung, bei der Spaß an Spielen verknüpft wird mit häufig arbeitsintensiven Aufgaben, die durch das Spiel im Hintergrund erledigt werden. Eine solche Aufgabe ist das verknüpfen von Wissen aus unterschiedlichen Wissensbasen («Interlinking»). In dem Bereich wurden viele Verfahren entwickelt, deren Evaluation sich allerdings nur schwierig automatisieren lässt. Innerhalb des LATC-Projekts wurde deshalb eine grundlegende Spielidee entwickelt, die das Bewerten von Verknüpfungen erlaubt. Dabei können 2 oder mehr Spieler miteinander um Punkte / Geld spielen, während sie wertvolles Feedback für die Interlinking-Algorithmen im Hintergrund liefern. Ziel der Arbeit ist die Verfeinerung der Spielidee und deren Implementierung in einem Onlinespiel mit möglichst hohem Suchtfaktor. :-)

Ihre Aufgabe ist:

• Entwickeln eines einfachen Online-Spiels
• Einarbeitung in Semantic Web Technologien wie RDF

Folgende Voraussetzungen und Fähigkeiten sind für die Bearbeitung der Arbeit notwendig:

• Studium der Informatik oder vergleichbarer Studiengänge
• Interesse an Webprogrammierung
• Interesse an Semantic Web

Entsprechendes Wissen kann ggf. auch während der Arbeit vermittelt bzw. erarbeitet werden. Die Arbeit kann als Bachelor-/Master- bzw. Diplomarbeit belegt werden.

Wir bieten eine umfangreiche Betreuung, sowie Hilfe bei der Einarbeitung in das Thema. Die Arbeit ermöglicht Resultate aus einem aktuellen Forschungsgebiet mit guter Zukunftsperspektive in die Praxis umzusetzen.

Sollten wir Ihr Interesse geweckt haben, wenden Sie Sich bitte an: Jens Lehmann – lehmann@informatik.uni-leipzig.de

Browsen, Suchen und Navigieren in DBpedia mit Hilfe maschinellen Lernens

Anfang des Jahres wurde das sehr erfolgreiche DBpedia-Projekt gegründet. Ziel dieses Projektes ist es Informationen aus Wikipedia extrahieren und sie mit anderen Wissensbasen zu verbinden. Wikipedia ist eine der am häufigst besuchten Seiten weltweit (Position 8 im Oktober 2008 laut http://alexa.com) auf der von Menschen eine riesige Menge an Wissen zusammengetragen wird. Eine Herausforderung bei dieser Menge von innerhalb des DBpedia-Projektes extrahierten Informationen ist Navigationsmöglichkeiten innerhalb der DBpedia-Daten anzubieten. Dafür wurde in einer Vorarbeit der DBpedia Navigator entwickelt, der das OWL-Lernsystem DL-Learner verwendet. Ziel der Arbeit ist es dieses Werkzeug zu einem Endnutzer DBpedia-Viewer weiterzuentwickeln und dabei Machine Learning Methoden für die Generierung von Navigationsvorschlägen (auf Basis der zuletzt angeschauten Instanzen) zu verwenden.

Ihre Aufgabe ist:

• Verbesserung der generierten Navigationsvorschläge: ein existierender neuer OWL-Lernalgorithmus soll auf diesen Anwendungsfall angepasst werden
• Erweiterung des DBpedia Navigator User Interfaces: verbessertes Ranking der Suchergebnisse, nutzerfreundliche Klassenhierarchie-Anzeige, verbesserte Anzeige der Instanzdaten mit Templates
• Integration von anderen Wissensbasen, die mit DBpedia verknüpft sind z.B. Geonames

Kenntnisse:

• Java- und PHP-Kenntnisse
• Interesse an Semantic Web, Machine Learning
• Studium der Informatik oder vergleichbarer Studiengänge

Wir bieten:

• eine umfangreiche Betreuung
• Teamarbeit in der Forschungsgruppe AKSW
• Mitarbeit an interessanten und erfolgreichen Projekten mit Potential die Nutzung von DBpedia/Wikipedia zu verbessern

Sollten wir Ihr Interesse geweckt haben, wenden Sie Sich bitte an: Jens Lehmann – lehmann@informatik.uni-leipzig.de

Anwendung von Ontologielernverfahren im medizinischen Bereich

Die Ontologiesprache OWL ist einer der Grundbausteine des Semantic Web und wird bereits in großem Umfang im biologischen und medizinischen Bereich eingesetzt. Das automatische Lernen in Ontologien aus Instanzdaten erlaubt dabei neue interessante Anwendungen im medizinischen Bereich, z.B. können anhand von Daten zu Patientenuntersuchungen neue Erkenntnisse über Krankheiten gewonnen werden. Bei dieser Arbeit ermöglichen wir die Zusammenarbeit mit dem Institut für Medizinische Informatik, Statistik und Epidemiologie (IMISE).

Ihre Aufgabe ist:

• Einarbeitung in Lernverfahren für OWL-Ontologien und das Open Source Tool DL-Learner
• Erarbeitung eines oder mehrerer konkreter Anwendungsszenarien
• Evaluation existierender Lernverfahren an diesen Anwendungsszenarien

Folgende Voraussetzungen und Fähigkeiten sind für die Bearbeitung der Arbeit notwendig:

• Studium der Informatik oder vergleichbarer Studiengänge
• Interesse an Semantic Web, insbesondere OWL 
• Machine Learning (anwendungsorientiert)

Entsprechendes Wissen kann ggf. auch während der Arbeit vermittelt bzw. erarbeitet werden. Allgemeines medizinisches Interesse ist ebenfalls günstig, aber nicht notwendig.

Wir bieten eine umfangreiche Betreuung, sowie Hilfe bei der Einarbeitung in das Thema. Die Arbeit ermöglicht Resultate aus einem aktuellen Forschungsgebiet mit guter Zukunftsperspektive in die Praxis umzusetzen. Bei erfolgreicher Umsetzung kann die Arbeit signifikante wissenschaftliche Resultate liefern.

Sollten wir Ihr Interesse geweckt haben, wenden Sie Sich bitte an: Patrick Westphal – patrick.westphal@informatik.uni-leipzig.de