کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439297 690500 2007 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On PAC learning algorithms for rich Boolean function classes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On PAC learning algorithms for rich Boolean function classes
چکیده انگلیسی

We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying previously known results, we use existing techniques to give the first known subexponential-time algorithms for PAC learning two natural and expressive classes of Boolean functions: sparse polynomial threshold functions over the Boolean cube {0,1}n and sparse polynomials over {0,1}n.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 384, Issue 1, 24 September 2007, Pages 66-76