Lernen von Ontologien und Anfragen aus Beispieldaten

• Antragsteller: Professor Dr. Jean Christoph Jung; Professor Dr. Carsten Lutz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 555349010

Das Ziel dieses Projekt ist, unser Verständnis des folgenden grundlegenden Problems zu vertiefen: Gegeben eine Menge von beschrifteten Datenbeispielen, finde einen passenden logischen Ausdruck. Hierbei passt ein Ausdruck phi(x) zu einem positiven Beispiel (D,a,+), welches aus einer Datenbank D und einem ausgezeichneten Tupel a von Individuen aus D besteht, wenn phi(a) in D erfüllt ist, und zu einem negativen Beispiel (D,a,−), wenn phi(a) in D nicht erfüllt ist. Probleme dieser Art, sogenannte Fitting Probleme, haben eine lange Geschichte in mehreren Teilbereichen der Informatik. Zum Beispiel stehen sie im Bereich Datenbanken im Mittelpunkt des klassischen Query-by-Example Paradigmas; im Bereich des maschinellen Lernens ist das zentrale Konsistenzproblem von dieser Natur; im Bereich Wissensrepräsentation und -verarbeitung werden passende logische Ausdrücke als als sogenannte referring expressions (eindeutige Beschreibungen von Individuen) sowie als Unterstützung für Benutzer beim Schreiben von Konzepten und Ontologien verwendet. Im vorgeschlagenen Projekt werden wir unser Wissen über Fitting Probleme und Algorithmen dafür erweitern. Der Schwerpunkt wird hauptsächlich auf Datenbank-Anfragen und Ontologien als logische Ausdrücke liegen. Genauer gesagt sind unsere Hauptziele wie folgt: (A) Wir werden praktisch relevante Szenarien untersuchen, die bisher wenig Beachtung gefunden haben, wie zum Beispiel die kürzlich standardisierten Graphanfragesprachen SQL/PGQ und GQL sowie Ontologien, die in Beschreibungslogiken und als existenzielle Regeln formuliert sind. (B) Wir werden transparente modelltheoretische Charakterisierungen für die Existenz einer Anfrage oder Ontologie, die zu einer gegebenen Menge von Beispielen passt, geben. Basierend auf diesen Charakterisierungen werden wir die Berechnungskomplexität des Existenzproblems bestimmen und Algorithmen zur Konstruktion einer passenden Anfrage/Ontologie entwickeln. (C) Wir werden Variationen des reinen Existenzproblems untersuchen. Die wichtigsten Varianten sind größenbeschränkte bzw. kleinste passende Ausdrücke, der extremale Fall, in dem wir zusätzlich fordern, dass der passende Ausdruck ein logisch stärkster/schwächster ist, und Angluin's exaktes Lernen, in dem der Lern-Algorithmus zusätzliche Fragen an ein Orakel stellen darf um den Lernprozess zu erleichtern.

• DFG-Verfahren: Sachbeihilfen