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

چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 159, Issue 5, 6 March 2011, Pages 259–271
نویسندگان
Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan,