研究如何在无限结构中用逻辑类函数精确或近似拟合数据样本。
How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
- 基于逻辑定义的函数类在可判定结构中拟合问题的复杂性分析
- 提出通过自然查询语言判断样本是否可拟合的新方法
- 适用于逻辑推理、形式验证等需要精确建模的领域
我们研究拟合问题（又称训练问题），即给定有限输入输出样本，判断是否存在某个特定函数类中的函数能恰好或近似地在这些输入上产生对应输出。重点关注在常见可判定结构（如实数有序域和Presburger算术）中，由逻辑定义的函数类的计算与描述复杂性，也涵盖通过组合或模型论性质定义的更广泛类。我们厘清了这些拟合问题的复杂性，特别关注能否利用自然查询语言对样本进行查询，以判断样本是否可拟合。
原文摘要 · Abstract (English)
We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures, like the real ordered field and Presburger arithmetic, and also for broader classes defined via combinatorial or model-theoretic properties. We isolate the complexity of these fitting problems, with particular attention to cases where we can use queries in a natural query language over the sample to determine whether a sample is fittable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。