کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427385 686499 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Learning parities in the mistake-bound model
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Learning parities in the mistake-bound model
چکیده انگلیسی

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(n1−1k). This is the first polynomial-time algorithm to learn ω(1)ω(1)-parities in the mistake-bound model with mistake bound o(n)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˜(nk/2) time algorithm from Klivans and Servedio (2004) [1] that PAC-learns k  -parities with sample complexity O(klogn) can be extended to the mistake-bound model.

Research highlights
► Parities of o(logn) variables can be learned with sublinear mistake bound.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 1, 15 December 2010, Pages 16–21
نویسندگان
, , ,