提出新学习框架，解决无限标签在线分类的可学习性问题。
Universal Multiclass Transductive Online Learning
- 引入LCLL树结构与无差异性，刻画可学习性条件。
- 可学习类的错误率最优仅两种：有界或对数增长。
- 适用于实时分类、大规模标签场景，适合理论研究者。
我们研究具有可能无界标签空间的通用归纳在线分类问题。该设定下，学习者事先知晓实例序列（无标签）。若存在学习算法，在任意可实现序列上其错误次数随预测次数的增长为次线性，则称概念类可学习。本文刻画了该设置下的可学习性，证明可学习类仅有两种最优错误率：有界或对数增长。提出新的组合结构——层级受限的利特尔顿-利特尔顿（LCLL）树，结合无差异性，完整刻画可学习性。还将结果扩展至广义情形及仅知实例生成随机过程的情况。
原文摘要 · Abstract (English)
We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class $\mathcal{H}$ is learnable if there is a learning algorithm $\mathcal{A}$, such that for every realizable sequence, the number of mistakes made by $\mathcal{A}$ grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called ``Level-Constrained-Littlestone-Littlestone (LCLL) tree'', which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。