Learning linear threshold functions in the presence of classification noise
Learning linear threshold functions in the presence of classification noise
复制标题
DOI：
10.1145/180139.181176
复制
发表时间：
1994-07
期刊：
影响因子：
4.6
通讯作者：
T. Bylander
中科院分区：
文献类型：
--
作者：
T. Bylander
我证明了线性阈值函数在存在分类噪声的情况下是多项式可学习的，即，多项式n，1/ε，1/δ和1/，其中n是布尔属性的数量，ε和δ是通常的精度和置信度参数，并指示任何示例与目标超平面的最小距离，假设该距离低于示例与任何超平面的平均距离。这一结果是通过修改Perceptron算法实现的-对于每次更新，将误分类示例的样本的加权平均值和校正向量添加到当前权重向量。对于加权多数算法也显示了类似的修改。校正向量只是归一化示例的平均值。在布尔阈值函数的特殊情况下，修改的感知器算法在O（n4ε −2ln（n/（δε）个示例上执行O（n2ε−2）次迭代。这改进了先前的分类噪声结果的Angluin和Laird到一个更大的概念类具有类似数量的例子，但与多个迭代的例子。
I show that the linear threshold functions are polynomially learnable in the presence of classification noise, i.e., polynomial in n, 1/ε, 1/δ, and 1/, where n is the number of Boolean attributes, ε and δ are the usual accuracy and confidence parameters, and indicates the minimum distance of any example from the target hyperplane, which is assumed to be lower than the average distance of the examples from any hyperplane. This result is achieved by modifying the Perceptron algorithm—for each update, a weighted average of a sample of misclassified examples and a correction vector is added to the current weight vector. Similar modifications are shown for the Weighted Majority algorithm. The correction vector is simply the mean of the normalized examples. In the special case of Boolean threshold functions, the modified Perceptron algorithm performs O (n2ε−2 ) iterations over O(n4ε −2ln(n/(δε))) examples. This improves on the previous classification-noise result of Angluin and Laird to a much larger concept class with a similar number of examples, but with multiple iterations over the examples.