图 书 馆
对数凹分布下线性分选器的主动和被动学习Active and passive learning of linear separators under log-concave distributions |
|
| 课程网址: | http://videolectures.net/colt2013_balcan_learning/ |
| 主讲教师: | Maria-Florina Balcan |
| 开课单位: | 乔治亚理工学院 |
| 开课时间: | 2013-08-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We prove that active learning provides an exponential improvement over PAC (passive) learning of homogeneous linear separators under nearly log-concave distributions. Building on this, we provide a computationally efficient PAC algorithm with optimal (up to a constant factor) sample complexity for such problems. This resolves an open question of (Long, 1995, 2003; Bshouty et al., 2009) concerning the sample complexity of efficient PAC algorithms under the uniform distribution in the unit ball. Moreover, it provides the first bound for a polynomial-time PAC algorithm that is tight for an interesting infinite class of hypothesis functions under a general class of data-distributions, providing significant progress towards a long standing open question of (Ehrenfeucht et al., 1989; Blumer et al., 1989). We also provide new bounds for active and passive learning in the case that the data might not be linearly separable, both in the agnostic case and and under the Tsybakov low-noise condition. To derive our results, we provide new structural results for (nearly) log-concave distributions, which might be of independent interest as well. |
| 关 键 词: | 对数凹分布; 线性分选器; 最有的样本复杂度; 算法; 线性计算 |
| 课程来源: | 视频讲座网公开课 |
| 最后编审: | 2019-05-26：cwx |
| 阅读次数: | 65 |