|
在对数凹面密度下学习半空间：多项式近似和矩量匹配
Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching |
|
| |
| 课程网址: |
http://videolectures.net/colt2013_meka_matching/
|
| 主讲教师: |
Raghu Meka
|
| 开课单位: |
阿姆斯特丹大学
|
| 开课时间: |
2013-08-09
|
| 课程语种: |
英语
|
| 中文简介: |
我们给出了第一个多项式时间算法，用于相对于任何对数凹面分布（对于任何恒定精度参数）非常地学习恒定数量的半空间的任何函数。即使PAC学习两个半空间的交叉，也不知道这个结果。我们给出了两个非常不同的结果证明。第一个开发了对数凹面测量的多项式近似理论，并构造了低度L1多项式逼近器，以获得足够平滑的函数。第二种方法使用与经典矩问题相关的技术来获得夹心多项式。两种方法都明显偏离已知的基于傅立叶的方法，其中基本上所有先前的工作都要求基础分布具有一些产品结构。此外，我们表明，在平滑分析设置中，上述结果适用于具有亚指数尾部的分布，这是机器学习中许多自然且经过充分研究的分布所满足的属性。
|
| 课程简介: |
We give the first polynomial-time algorithm for agnostically learning any function of a constant number of halfspaces with respect to any log-concave distribution (for any constant accuracy parameter). This result was not known even for the case of PAC learning the intersection of two halfspaces. We give two very different proofs of this result. The first develops a theory of polynomial approximation for log-concave measures and constructs a low-degree L1 polynomial approximator for sufficiently smooth functions. The second uses techniques related to the classical moment problem to obtain sandwiching polynomials. Both approaches deviate significantly from known Fourier-based methods, where essentially all previous work required the underlying distribution to have some product structure. Additionally, we show that in the smoothed-analysis setting, the above results hold with respect to distributions that have sub-exponential tails, a property satisfied by many natural and well-studied distributions in machine learning.
|
| 关 键 词: |
对数凹面; 傅立叶的方法; 多项式近似理论
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2019-03-10：mmx
|
| 阅读次数: |
99
|
|
图 书 馆