论文标题
通过体重聚集逻辑描述的学习概念
Learning Concepts Described by Weight Aggregation Logic
论文作者
论文摘要
我们考虑加权结构，这些结构通过分配权重，即从特定组或环的元素到结构中存在的元素来扩展普通的关系结构。我们介绍了一阶逻辑的扩展，该扩展可以汇总元组的权重，比较此类骨料并使用它们来构建更复杂的公式。我们提供了该逻辑片段的局部性特性，包括Feferman-grought分解和称为FOW1的片段的Gaifman正常形式，以及一个称为FOWA1的较大片段的局部定理。该片段可以从各种机器学习方案中表达概念。使用局部性属性，我们表明在Fowa1中可以在高加权背景结构中定义的概念，最多是多数粒子度的概念，在伪线性时间预处理后，在pseogarogarithmic的时间内不可或缺。
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.
