论文标题
列表可学习性的特征
A Characterization of List Learnability
论文作者
论文摘要
学习理论的经典结果表明，二进制假设类别的PAC可学习性和VC维度的有限性。将其扩展到多类设置是一个开放的问题，该问题是在最近的突破性结果中解决的，该结果通过Daniely和Shalev-Shwartz前面提出的DS维度来表征多类PAC可学习性。在这项工作中，我们考虑列表PAC学习的目标是输出$ K $预测的列表。列表学习算法已经在以前的几个设置中开发了，而且列表学习在最新的多类可学习性表征中起着重要作用。在这项工作中，我们问：什么时候可以$ k $清单学习假设课？我们完全表征了$ k $清单的可学习性，从我们称为$ k $ -ds维度的DS维度的概括方面。概括了多类可学习性的最新表征，我们表明假设类是$ k $清单的可学习，并且仅当$ k $ -ds维度是有限的时。
A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz. In this work we consider list PAC learning where the goal is to output a list of $k$ predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to $k$-list learn a hypothesis class? We completely characterize $k$-list learnability in terms of a generalization of DS dimension that we call the $k$-DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is $k$-list learnable if and only if the $k$-DS dimension is finite.
