Learning Definable Relations in Graphs

Kontakt

Martin Ritzert

Telefon

work
+49 241 80 21706

E-Mail

E-Mail
  Software Urheberrecht: Martin Braun

Ich betrachte Klassifikationsprobleme über einfachen Strukturen bei denen die Hypothese, also der vom Lernalgorithmus zurückgegebene Classifier, aus einer logischen Formel und einer beschränkten Anzahl an Konstanten besteht. Ich betrachte insbesondere Formeln in Logik erster Stufe sowie Formeln der Logik MSO über einfachen Strukturen wie zum Beispiel geordneten Wörtern, Bäumen sowie Strukturen mit beschränktem Grad.

Das Ziel ist es Lernalgorithmen zu finden, die polynomiell im Trainingsset sind, aber deren Abhängigkeit von der Hintergrundstruktur höchstens sublinear ist, vorzugsweise logarithmisch oder sogar unabhängig von der Größe der Struktur.

Falls solche Algorithmen nicht existieren versuche ich stattdessen den nicht-sublinearen Anteil auszulagern und betrachte Algorithmen, die zuerst in linearer (oder polynomieller) Zeit eine Indexstruktur aufbauen und danach mit Hilfe der Indexstruktur in polylogarithmischer Zeit eine konsistente Hypothese finden.