We study a variant of online multiclass classification where the learner predicts a single label but receives a \textit{set of labels} as feedback. In this model, the learner is penalized for not outputting a label contained in the revealed set. We show that unlike online multiclass learning with single-label feedback, deterministic and randomized online learnability are \textit{not equivalent} even in the realizable setting with set-valued feedback. Accordingly, we give two new combinatorial dimensions, named the Set Littlestone and Measure Shattering dimension, that tightly characterize deterministic and randomized online learnability respectively in the realizable setting. In addition, we show that the Measure Shattering dimension tightly characterizes online learnability in the agnostic setting. Finally, we show that practical learning settings like online multilabel ranking and online multilabel classification are specific instances of our general online learning framework.

本文研究一种在线多类分类变体，在这种模型中，学习器预测一个单一标签，但接收一个标签的集合作为反馈，我们证明在这种情况下，确定性和随机化的在线可学习性不等价，并且给出两个新的组合维度，称为集合维度和度量破灭维度，分别紧密描述了实现情况下的确定性和随机化的在线可学习性，此外，我们还展示了度量破碎维度紧密描述了模糊情况下的在线可学习性，最后，我们展示了在线多标签排名和在线多标签分类是我们提出的在线学习框架的具体实例。

带集合值反馈的在线学习