Learning parities in the mistake-bound model

作     者：Buhrman, Harry Garcia-Soriano, David Matsliah, Arie 

作者机构：CWI Amsterdam Amsterdam Netherlands 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2010年第111卷第1期

页      面：16-21页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：On-line algorithms Parities Mistake-bound Attribute-efficient learning 

摘      要：We study the problem of learning parity functions that depend on at most k variables (k-parities) attribute-efficiently in the mistake-bound model. We design a simple, deterministic, polynomial-time algorithm for learning k-parities with mistake bound O(n(1-1/k)). This is the first polynomial-time algorithm to learn omega(1)-parities in the mistake-bound model with mistake bound o(n). Using the standard conversion techniques from the mistake-bound model to the PAC model, our algorithm can also be used for learning k-parities in the PAC model. In particular, this implies a slight improvement over the results of Klivans and Servedio (2004) [1] for learning k-parities in the PAC model. We also show that the (O) over tilde (n(k/2)) time algorithm from Klivans and Servedio (2004) [1] that PAC-learns k-parities with sample complexity O(k log n) can be extended to the mistake-bound model. (c) 2010 Elsevier B.V. All rights reserved.