通过约束满足问题判断神经符号任务是否可学习，给出误差边界。
A Learnability Analysis on Neuro-Symbolic Learning
- 用派生约束满足问题判定任务可学习性
- 可学习任务的误差受假设空间聚类特性限制
- 揭示解集分歧度与渐近误差的关系，适合算法设计者
本文分析了混合系统中神经符号（NeSy）任务的可学习性。我们证明，若对应的派生约束满足问题（DCSP）有唯一解，则该任务可学习；否则不可学习。对于可学习任务，利用假设空间的聚类性质建立了误差界。此外，我们分析了通用NeSy任务的渐近误差，发现期望误差随解集间的分歧程度而增长。研究结果为判定可学习性提供了理论依据，并为新算法设计提供洞见。
原文摘要 · Abstract (English)
This paper analyzes the learnability of neuro-symbolic (NeSy) tasks within hybrid systems. We show that the learnability of NeSy tasks can be characterized by their derived constraint satisfaction problems (DCSPs). Specifically, a task is learnable if the corresponding DCSP has a unique solution; otherwise, it is unlearnable. For learnable tasks, we establish error bounds by exploiting the clustering property of the hypothesis space. Additionally, we analyze the asymptotic error for general NeSy tasks, showing that the expected error scales with the disagreement among solutions. Our results offer a principled approach to determining learnability and provide insights into the design of new algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。