仅需一个线性序，就能在ZFC中刻画任意二值假设类的一致归纳推理！
An Order-Theoretic Characterization of Consistent Inductive Inference
📖 AI 总结
本文研究归纳推理中一致性的刻画问题：在目标假设固定但未知的情况下，学习器何时能在任意无限标注序列上只犯有限次预测错误？作者在ZFC框架下，对任意二值假设类给出了这一致性形式的完整刻画，且不要求统一的错误上界。核心工具是在有限可实现轨迹上构造一个线性序，每条轨迹选取其最小子轨迹，该序须满足两个条件：冲突轨迹选取不同子轨迹，且在固定目标的轨迹上良基。这些条件可诱导出一个学习器，使其在每次犯错时所依据的证据严格递减；反过来，任一一致学习器也可通过规范错误记录与Kleene–Brouwer序导出这样的序。该结果为用有限证据表示一致预测提供了表示定理，回答了Lu（2024）提出的问题。
🔑 关键词速览
| 一致归纳推理 (Consistent Inductive Inference) | 学习者在每个由目标假设标记的无限序列上只犯有限多次预测错误的性质。 |
| ZFC | Zermelo-Fraenkel集合论加上选择公理，是数学中常用的公理系统。 |
| 二值假设类 (Binary Hypothesis Class) | 由将实例映射到{0,1}的假设组成的集合，用于二分类学习问题。 |
| 良基序 (Well-founded Order) | 不存在无限递减序列的偏序关系，确保归纳定义和递归的有效性。 |
| Kleene–Brouwer序 | 一种定义在有限序列上的偏序，用于比较序列在字典序下的先后关系。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅