研究如何在计算约束下学习可计算函数，突破传统学习框架的局限。
Learning Algorithms in the Limit
- 引入时间约束与策略轨迹观测，扩展经典归纳推理框架
- 证明在时间限制下可学习一般递归函数，而原框架无法做到
- 揭示策略轨迹学习与有限状态转换器的深层联系，适合理论计算方向研究者
本文研究在极限条件下学习可计算函数的问题，将Gold的归纳推理框架扩展至包含计算观测与受限输入源。除传统的输入-输出观测外，引入时间约束观测和策略轨迹观测，以研究在更现实约束下对一般递归函数的可学习性。尽管传统输入输出观测不足以在极限下学习一般递归函数，但通过施加计算复杂度约束或补充近似时间约束观测，可突破这一学习障碍。进一步构建了关于计算智能体观测的正式框架，表明从策略轨迹中学习可计算函数等价于从输入输出中学习有理函数，从而揭示其与有限状态转换器推断的深刻关联。另一方面，我们证明即使在策略轨迹观测下，线性时间可计算函数类也不存在可计算或多项式质量的特征集。
原文摘要 · Abstract (English)
This paper studies the problem of learning computable functions in the limit by extending Gold's inductive inference framework to incorporate \textit{computational observations} and \textit{restricted input sources}. Complimentary to the traditional Input-Output Observations, we introduce Time-Bound Observations, and Policy-Trajectory Observations to study the learnability of general recursive functions under more realistic constraints. While input-output observations do not suffice for learning the class of general recursive functions in the limit, we overcome this learning barrier by imposing computational complexity constraints or supplementing with approximate time-bound observations. Further, we build a formal framework around observations of \textit{computational agents} and show that learning computable functions from policy trajectories reduces to learning rational functions from input and output, thereby revealing interesting connections to finite-state transducer inference. On the negative side, we show that computable or polynomial-mass characteristic sets cannot exist for the class of linear-time computable functions even for policy-trajectory observations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。