Erweiterungen der Logik erster Stufe auf gewichteten Strukturen zum Beschreiben und Lernen von Aggregat-Anfragen

• Antragstellerin: Professorin Dr. Nicole Schweikardt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 541000908

In dem von Grohe und Turan (2004) eingeführten Logik-basierten Framework für Boolesche Klassifikationsprobleme sind die zu klassifizierenden Eingaben Tupel aus einer relationalen Struktur, und Boolesche Klassifikatoren werden durch parametrisierte logische Formeln repräsentiert. Dies ist ein spezifisches Szenario des überwachten passiven Lernens, bei dem Klassifikatoren an Hand von bewerteten Trainingsbeispielen gelernt werden sollen. Für dieses Szenario wurden Resultate zum exakten Lernen und zum PAC-Lernen von Booleschen Klassifikatoren erzielt, die durch Formeln der Logik erster Stufe (FO) beschrieben werden können. Diese Ergebnisse wurden auf bestimmte Erweiterungen der Logik erster Stufe verallgemeinert, die das Zählen (FOC_1) und das Aggregieren von Gewichten erlauben, die Tupeln der Struktur zugeordnet sind (FOWA_1). Dieses Projekt soll den Stand der Forschung in drei Dimensionen erweitern. (A): Die bisherigen Resultate in diesem Szenario beschränken sich auf Boolesche Klassifikationsprobleme. Wir wollen Lernbarkeits-Resultate jenseits von Boolescher Klassifikation erzielen und dazu Klassifikationsprobleme untersuchen, bei denen jedem Eingabetupel eine Klasse aus einer beliebigen, potentiell unendlichen Menge von Klassen zugeordnet werden soll. Um solche Klassifikatoren zu repräsentieren, wollen wir Aggregat-Anfragen verwenden, die durch Erweiterungen der Logik erster Stufe mit Zähltermen und Gewichts-Aggregations-Termen beschrieben werden (darunter auch Terme der Logiken FOC_1 und FOWA_1). (B): Die Logiken FOC_1 and FOWA_1 haben zwar eine deutlich größere Ausdrucksstärke als FO, aber es gibt dennoch bestimmte natürliche Eigenschaften, die nicht in diesen Logiken ausgedrückt werden können (zum Beispiel: "alle mit dem Knoten x inzidenten Kanten haben das gleiche Gewicht"). Wir wollen Logiken konzipieren und untersuchen, die eine größere Ausdrucksstärke als FOC_1 und FOWA_1 haben, aber trotzdem noch Lokalitätseigenschaften besitzen, die effiziente Lernbarkeits-Algorithmen erlauben. (C): Die existierenden Lernbarkeits-Resultate für FOC_1 und FOWA_1 sind nur für Klassen von Strukturen von kleinem Grad verfügbar. Wir wollen vergleichbare Resultate für allgemeinere Klassen von "dünn besetzten" Strukturen erzielen, darunter Klassen von beschränkter Baumweite, Klassen von beschränkter Expansion (bounded expansion) und nirgends-dichte Klassen (nowhere dense classes).

• DFG-Verfahren: Sachbeihilfen