paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Learning first-order definable concepts over structures of small degree

在小度数结构上学习一阶可定义概念
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 该论文属于逻辑与PAC学习理论，研究在小度数背景结构上一阶可定义概念的可学习性，与用户关注的LLM/Agent、静态分析、浮点程序分析和贝叶斯程序分析均无直接关系；仅因涉及逻辑与机器学习的交叉而略有边缘关联。引用 27 inbox
Martin Grohe, Martin Ritzert
逻辑与自动机机器学习与程序语言
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话：证明在度数至多多对数的背景结构上，一阶公式定义的概念可在多对数时间内PAC学习。

论文研究一种声明式机器学习框架：概念与假设均由背景结构上某逻辑的公式定义。核心问题是，当背景结构的度数至多为多对数级时，一阶可定义概念能否被高效学习。作者证明，此类概念可在多对数时间内以 PAC 意义学习，即存在学习算法在多对数时间内返回近似正确的假设。该结果把逻辑可定义性与计算学习理论中的可学习性联系起来，给出了基于背景结构度数的可学习性边界，并为在稀疏或小度数结构上进行声明式学习提供了理论保证。

问题
在声明式逻辑学习框架中，背景结构度数很小时，一阶公式定义的概念是否可在 PAC 模型下高效学习。
方法
将概念与假设表示为背景结构上的一阶逻辑公式，并设计/分析针对多对数度数结构的 PAC 学习算法，使其运行时间为多对数级。
评估
以理论证明为主，证明该算法能在多对数时间内 PAC 学习一阶可定义概念，提供可学习性保证而非实验评估。
原文摘要（Abstract）

We consider a declarative framework for machine learning where concepts and hypotheses are defined by formulas of a logic over some “background structure”. We show that within this framework, concepts defined by first-order formulas over a background structure of at most polylogarithmic degree can be learned in polylogarithmic time in the “probably approximately correct” learning sense.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@inproceedings{GroheR17,
  title = {Learning first-order definable concepts over structures of small degree},
  author = {Martin Grohe and Martin Ritzert},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005080}
}