论文标题
列出属性噪声的学习
List Learning with Attribute Noise
论文作者
论文摘要
我们介绍并研究具有属性噪声的列表学习模型。 Shackelford和Volper（Colt 1988）引入了具有属性噪声的学习，作为PAC学习的一种变体，其中该算法可以访问嘈杂的例子和未腐败的标签，其目标是恢复准确的假设。斯隆（Colt 1988）和高盛和斯隆（Goldman and Sloan）（Algorithmica 1995）在这种模型中发现了学习的信息理论限制，这阻碍了进一步的进步。在本文中，我们将模型扩展到列表学习的模型，从编码理论中的列表编码模型中汲取灵感，以及其在学习背景下研究的最新变体。从积极的一面来看，我们表明，稀疏的结合可以有效地列出有关基础真相分布的一些假设。负面的一面，我们的结果表明，即使在列表学习模型中，无论使用哪种表示，都无法对平等和大多数的有效学习。
We introduce and study the model of list learning with attribute noise. Learning with attribute noise was introduced by Shackelford and Volper (COLT 1988) as a variant of PAC learning, in which the algorithm has access to noisy examples and uncorrupted labels, and the goal is to recover an accurate hypothesis. Sloan (COLT 1988) and Goldman and Sloan (Algorithmica 1995) discovered information-theoretic limits to learning in this model, which have impeded further progress. In this article we extend the model to that of list learning, drawing inspiration from the list-decoding model in coding theory, and its recent variant studied in the context of learning. On the positive side, we show that sparse conjunctions can be efficiently list learned under some assumptions on the underlying ground-truth distribution. On the negative side, our results show that even in the list-learning model, efficient learning of parities and majorities is not possible regardless of the representation used.
