Learning parities in the mistake-bound model |
| |
Authors: | Harry Buhrman Arie Matsliah |
| |
Affiliation: | CWI Amsterdam, Netherlands |
| |
Abstract: | 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 . This is the first polynomial-time algorithm to learn ω(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 time algorithm from Klivans and Servedio (2004) [1] that PAC-learns k-parities with sample complexity can be extended to the mistake-bound model. |
| |
Keywords: | On-line algorithms Parities Mistake-bound Attribute-efficient learning |
本文献已被 ScienceDirect 等数据库收录! |