Learning Concepts Described by Weight Aggregation Logic
Learning Concepts Described by Weight Aggregation Logic
复制标题
学习权重聚合逻辑描述的概念
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Nicole Schweikardt
中科院分区：
文献类型：
--
作者：
Steffen van Bergerem;Nicole Schweikardt
我们考虑加权结构，它通过将权重（即来自特定组或环的元素）分配给结构中存在的元组来扩展普通关系结构。我们引入一阶逻辑的扩展，允许聚合元组的权重，比较这些聚合，并使用它们来构建更复杂的公式。我们提供的局部属性的片段，这个逻辑包括Feferman-Vaught分解和一个Gaifman正常形式的片段称为FOW 1，以及一个本地化定理的一个更大的片段称为FOWA 1。这个片段可以表达来自各种机器学习场景的概念。使用的局部性，我们表明，在FOWA 1中定义的概念在加权背景结构的最多polylogarithmic度是不可知的PAC学习的polylogarithmic时间后，伪线性时间预处理。
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.
用于计算一阶逻辑扩展的盖夫曼范式
DOI：
10.4230/lipics.icalp.2018.133
发表时间：
2018
期刊：
影响因子：
--
作者：
Dietrich Kuske;Nicole Schweikardt
通讯作者：
Nicole Schweikardt
DOI：
10.1109/lics.2017.8005133
发表时间：
2017-03
期刊：
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
影响因子：
--
作者：
D. Kuske;Nicole Schweikardt
通讯作者：
D. Kuske;Nicole Schweikardt