Learning Aggregate Queries Described by Extensions of First-order Logic on Weighted Structures

• Applicant: Professorin Dr. Nicole Schweikardt
• Subject Area: Theoretical Computer Science
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 541000908

In the logical framework introduced by Grohe and Turan (2004) for Boolean classification problems, the instances to classify are tuples from a logical structure, and Boolean classifiers are described by parametric models based on logical formulas. This is a specific scenario for supervised passive learning, where classifiers should be learned based on labelled examples. Exact-learning results and PAC-learning results within this scenario have been obtained for Boolean classification problems described by formulas of first-order logic (FO) and certain extensions of first-order logic that allow counting (FOC_1) as well as aggregation of weights associated with tuples present in the structure (FOWA_1). This project wants to extend the state-of-the-art in three dimensions. (A): Existing results in this scenario focus on Boolean classification. We want to obtain learnability results beyond Boolean classification. I.e., we want to solve multiclass classification problems where the task is to assign inputs to an arbitrary, possibly infinite number of classes. To represent such classifiers, we want to use aggregate queries specified by extensions of first-order logic with counting-terms or weight-aggregation-terms (including terms of FOC_1 and FOWA_1). (B): The logics FOC_1 and FOWA_1 are significantly more expressive than FO, but they still lack the ability to express certain natural conditions (for example, "all edges incident with vertex x have the same weight"). We want to design and study logics that are more expressive than FOC_1 and FOWA_1, but that still yield locality results that enable efficient learnability algorithms. (C): The existing learnability results for FOC_1 and FOWA_1 only apply to classes of structures of small degree. We want to achieve comparable results for more general classes of sparse structures, including classes of bounded treewidth, classes of bounded expansion, and nowhere dense classes.

• DFG Programme: Research Grants