Learning noisy perceptrons by a perceptron in polynomial time
Learning noisy perceptrons by a perceptron in polynomial time
复制标题
通过感知器在多项式时间内学习噪声感知器
DOI：
10.1109/sfcs.1997.646140
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
E. Cohen
中科院分区：
文献类型：
--
作者：
E. Cohen
从标记的示例中学习感知器（线性阈值功能）是机器学习中的重要问题。我们考虑标签受到随机分类噪声的问题。已知该问题是通过由多项式数量线性阈值组成的假设来学习的（由于A. Blum，A。Frieze，R。Kannan和S. Vempala（1996））。是否可以在多项式时间中找到一个自身的假设（单个阈值函数）的问题。我们表明，确实，嘈杂的感知源是PAC可以学习的，这是一个感知的假设。
Learning perceptrons (linear threshold functions) from labeled examples is an important problem in machine learning. We consider the problem where labels are subjected to random classification noise. The problem was known to be PAC learnable via a hypothesis that consists of a polynomial number of linear thresholds (due to A. Blum, A. Frieze, R. Kannan, and S. Vempala (1996)). The question of whether a hypothesis that is itself a perceptron (a single threshold function) can be found in polynomial time was open. We show that indeed, noisy perceptrons are PAC learnable with a hypothesis that is a perceptron.