 | From the Series از مجموعه : -
Produced by تهيه كننده : Microsoft Research
Date تاريخ : 2006-02-06
Towards Agnostically Learning Halfspacesdownload دانلود ,ويدئو و اسلايد Video & Slide , از گروه Computer Sience & Engineering كامپيوتر و مهندسی كتابخانه اينترنتي دانش گستران جوان You Research Description توضيح : A longstanding open problem in computational learning theory is that of learning halfspaces in the agnostic model of Kearns, Schapire and Sellie (which model can also be viewed as learning with adversarial noise). In this problem, there is an arbitrary and unknown joint distribution over n-dimensional vectors X and their 0-1 labels Y. The goal is to design an algorithm that provably learns to predict the labels of future examples with error at most (opt + eps), where opt is the error of the best halfspace predictor for the distribution, for any eps > 0, using runtime and a number of samples of this distribution that is polynomial in n and 1/eps.
We make progress on this problem by giving a simple learning algorithm that learns such functions for a very general class of distributions on n-dimensional vectors X (including any log-concave distribution) in time polynomial in the dimension n (but exponential in 1/eps). Note that our distributional assumptions are only on X, and thus the algorithm tolerates worst-case noise. The simple randomized algorithm generalizes Fourier learning and is also related to 'support vector machines with a polynomial kernel.
Joint work with Adam Klivans, Yishay Mansour and Rocco Servedio.
Related Links لينك‌های مرتبط : -
Towards Agnostically Learning Halfspacesdownload دانلود ,ويدئو و اسلايد Video & Slide , از گروه Computer Sience & Engineering كامپيوتر و مهندسی كتابخانه اينترنتي دانش گستران جوان You Research Speaker(s) اجرا : Adam Tauman Kalai, assistant professor, Toyota Technological Institute in Chicago
Runtime مدت زمان : 01:12:50
Video Size حجم ويدئو : 148 MB
Number of Slides تعداد اسلايد‌ها : 63 (4 MB)
Towards Agnostically Learning Halfspacesdownload دانلود ,ويدئو و اسلايد Video & Slide , از گروه Computer Sience & Engineering كامپيوتر و مهندسی كتابخانه اينترنتي دانش گستران جوان You Research
|
