کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419483 683823 2011 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Learning random monotone DNF
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Learning random monotone DNF
چکیده انگلیسی

We give an algorithm that with high probability properly learns random monotone DNF with t(n)t(n) terms of length ≈logt(n)≈logt(n) under the uniform distribution on the Boolean cube {0,1}n{0,1}n. For any function t(n)≤poly(n) the algorithm runs in time poly(n,1/ϵ) and with high probability outputs an ϵϵ-accurate monotone DNF hypothesis. This is the first algorithm that can learn monotone DNF of arbitrary polynomial size in a reasonable average-case model of learning from random examples only. Our approach relies on the discovery and application of new Fourier properties of monotone functions which may be of independent interest.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 5, 6 March 2011, Pages 259–271
نویسندگان
, , , ,