允许预测多个标签，只要其中之一正确即可，提升学习鲁棒性。
Ambiguous Online Learning
- 允许多标签预测，只要一个正确且无可预见错误
- 错误次数分为三类：常数、根号N或线性增长，无中间态
- 适用于推荐系统与动态系统，对算法容错性强
我们提出一种新的在线学习范式，称为“模糊在线学习”。在此设定中，学习者可输出多个预测标签，只要至少一个正确且无“可预见错误”即视为成功。所谓“可预见错误”指该标签不被真实假设所允许，而真实假设来自一个多值假设类。此设定在多值动力系统、推荐算法和无损压缩中自然出现，也与“苹果品尝”问题密切相关。我们证明，在此框架下，任何假设类的最优错误界至多差一个对数因子，只能是Theta(1)、Theta(sqrt(N))或N三种形式之一。
原文摘要 · Abstract (English)
We propose a new variant of online learning that we call "ambiguous online learning". In this setting, the learner is allowed to produce multiple predicted labels. Such an "ambiguous prediction" is considered correct when at least one of the labels is correct, and none of the labels are "predictably wrong". The definition of "predictably wrong" comes from a hypothesis class in which hypotheses are also multi-valued. Thus, a prediction is "predictably wrong" if it's not allowed by the (unknown) true hypothesis. In particular, this setting is natural in the context of multivalued dynamical systems, recommendation algorithms and lossless compression. It is also strongly related to so-called "apple tasting". We show that in this setting, there is a trichotomy of mistake bounds: up to logarithmic factors, any hypothesis class has an optimal mistake bound of either Theta(1), Theta(sqrt(N)) or N.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。