Learning Concepts Described by Weight Aggregation Logic
This work provides a theoretical framework for learning concepts in weighted relational structures, with potential applications in machine learning scenarios, though it appears incremental in extending existing logic-based methods.
The authors introduced an extension of first-order logic for weighted structures that aggregates and compares weights, and showed that concepts definable in a specific fragment (FOWA1) over structures with polylogarithmic degree are agnostically PAC-learnable in polylogarithmic time after pseudo-linear preprocessing.
We consider weighted structures, which extend ordinary relational structures by assigning weights, i.e. elements from a particular group or ring, to tuples present in the structure. We introduce an extension of first-order logic that allows to aggregate weights of tuples, compare such aggregates, and use them to build more complex formulas. We provide locality properties of fragments of this logic including Feferman-Vaught decompositions and a Gaifman normal form for a fragment called FOW1, as well as a localisation theorem for a larger fragment called FOWA1. This fragment can express concepts from various machine learning scenarios. Using the locality properties, we show that concepts definable in FOWA1 over a weighted background structure of at most polylogarithmic degree are agnostically PAC-learnable in polylogarithmic time after pseudo-linear time preprocessing.