一句话：证明多对数度结构上 FOCN(P) 可定义概念可亚线性学习，而无界度下即使一阶公式也不存在亚线性学习算法。
本文研究关系背景结构上的分类学习问题，其中待学习假设由带计数量词的一阶逻辑 FOCN(P) 定义。目标是在远小于背景结构规模的时间内完成学习。作者针对多对数度（polylogarithmic degree）结构，给出可在亚线性时间内学习 FOCN(P) 公式所定义概念的算法；作为对比，证明当结构度无界时，即使对纯一阶公式也不存在亚线性学习算法。结果刻画了结构度对逻辑可定义概念可学习性的影响，并给出亚线性学习与下界。
We study classification problems over relational background structures for hypotheses that are defined using logics with counting. The aim of this paper is to find learning algorithms running in time sublinear in the size of the background structure. We show that hypotheses defined by FOCN(P)formulas over structures of polylogarithmic degree can be learned in sublinear time. Furthermore, we prove that for structures of unbounded degree there is no sublinear learning algorithm for first-order formulas.
DOI 原文 ·
@inproceedings{paperbot4991,
title = {Learning Concepts Definable in First-Order Logic with Counting},
author = {Steffen van Bergerem},
booktitle = {LICS},
year = {2019},
doi = {10.1109/lics.2019.8785811}
}