On learning from noisy and incomplete examples
On learning from noisy and incomplete examples
复制标题
从嘈杂和不完整的例子中学习
DOI：
10.1145/225298.225341
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
R. Gennaro
中科院分区：
文献类型：
--
作者：
Scott E. Decatur;R. Gennaro
当用于学习的数据（属性和标签）损坏或不完整时，我们研究PAC模型中的可学习性。为了证明我们的主要结果，我们在统计查询（SQ）学习算法上定义了一个新的复杂度度量。SQ算法的视图是该算法中所有查询中查询所依赖的输入比特数的最大值。我们证明了类的受限视图SQ算法是属性噪声和覆盖（或缺失）属性模型中可学习性的一般充分条件，我们进一步表明，由于所讨论的算法是统计的，它们也可以同时容忍分类噪声。这些结果成立的类，因此可以同时使用属性噪声和分类噪声来学习，包括k-DNF， k-term-DNF通过DNF表示，与少数相关变量的连接，以及均匀分布，决策列表。这些噪声模型是第一个所有训练数据、属性和标签都可能被随机过程破坏的PAC模型。先前的研究表明，如果属性噪声率是已知的，那么k-DNF类是可学习的。我们表明，当确切的噪声率不为时，我们所有的属性噪声可学习性结果，无论是有或没有分类噪声，都是成立的。作者得到了NDSEG奖学金和NSF拨款CCR-92-00884的支持。作者邮箱：sed@das。hsrvard。作者获得了美国国家科学基金会（NSF） 9121466 CCR基金的资助，并获得了意大利Consiglio Nazionale delle Ricerche的研究生奖学金。作者邮箱：rosario@theory。lcs。麻省理工学院。edu允许免费制作全部或部分材料的数字/硬拷贝。d只要副本不是为了盈利或商业利益而制作或分发，ACM版权（scvcr）通知。如果学习器对噪声率有一个多项式的良好近似值，就会出现发表的标题和发表的日期，并给出已知的通知。此外，我们还表明，当每个属性都有不同的噪声率而不是单一的噪声率时，结果也成立。我们的随机覆盖学习的结果不需要学习者被告知覆盖率的近似值，而且在每个属性具有不同覆盖率的设置中也是成立的。最后，我们给出了在存在属性噪声或覆盖的情况下学习所需的样例数量的下界。
We investigate learnability in the PAC model when the data used for learning, attributes and labels, is either corrupted or incomplete. In order to prove our main results, we define a new complexity measure on statistical query (SQ) learning algorithms. The view of an SQ algorithm is the maximum over all queries in the algorithm, of the number of input bits on which the query depends. We show that a restricted view SQ algorithm for a class is a general sufficient condition for learnability in both the models of attribute noise and covered (or missing) attributes, We further show that since the algorithms in question are statistical, they can also simultaneously tolerate classification noise. Classes for which these results hold, and can therefore be learned with simultaneous attribute noise and classification noise, include k-DNF, k-term-DNF by DNF representations, conjunctions with few relevant variables, and over the uniform distribution, decision lists. These noise models are the first PAC models in which all training data, attributes and labels, may be corrupted by a random process. Previous researchers had shown that the class of k-DNF is learnable with attribute noise if the attribute noise rate is known exactly. We show that all of our attribute noise learnability results, either with or without classification noise, also hold when the exact noise rate is not *Author was supported by an NDSEG Fellowship and by NSF Grant CCR-92-00884. Author’s email address: sed@das. hsrvard. edu ‘Author was supported by NSF Grant 9121466 CCR and a graduate fellowship from the Consiglio Nazionale delle Ricerche, Italy. Author’s email address: rosario@theory. lcs .mit . edu Permission to make digital/hard copies of all or part of this material withmt fee is grantc.d provided that the copies are not made or distributed for profit or commercial advantage, the ACM copyright(scrvcr notice. the title of the publication and its date appear, and notice is given known, provided that the learner instead has a polynomially good approximation of the noise rate. In addition, we show that the results also hold when there is not one single noise rate, but a distinct noise rate for each attribute. Our results for learning with random covering do not require the learner to be told even an approximation of the covering rate and in addition hold in the setting with distinct covering rates for each attribute. Finally, we give lower bounds on the number of examples required for learning in the presence of attribute noise or covering.