揭示了在线学习中哪些情况可被计算机实现，打破理论与实践的鸿沟。
Computable universal online learning
- 提出可计算的通用在线学习框架，要求学习策略能编成程序执行。
- 证明即使假设类简单，通用在线学习也不一定可计算。
- 给出无监督和正确学习的精确可计算条件，适合理论研究者参考。
理解学习何时可能，是机器学习理论的根本任务。然而，现有许多刻画将学习视为抽象数学对象，忽视了一个关键问题：学习能否被实现为计算机程序？本文针对通用在线学习（universal online learning）这一在线二分类的理论模型展开研究。该模型不预先固定假设类，而是由对手（模拟自然）在保持局部一致性前提下动态调整。要求学习者在有限错误次数内完成学习，且策略必须可编程实现。我们证明：通用在线学习并不蕴含可计算的通用在线学习，即使假设类从可计算性角度看相对简单。随后，我们研究了无监督变体，并给出了可计算通用在线学习的精确刻画。还分析了正确学习的变体，明确了其可实现的精确条件。整体结果为在线二分类理论及归纳推理问题提供了更贴近现实的视角。
原文摘要 · Abstract (English)
Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as a mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal online learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC'21). In this model, there is no hypothesis fixed in advance; instead, Adversary -- playing the role of Nature -- can change their mind as long as local consistency with the given class of hypotheses is maintained. We require Learner to achieve a finite number of mistakes while using a strategy that can be implemented as a computer program. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from a computability-theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant of proper universal online learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。