图 书 馆
一种高效的基于图的主动学习算法及其在非参数分类中的应用An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification |
|
| 课程网址: | https://videolectures.net/videos/colt2015_dasarathy_nonparametric... |
| 主讲教师: | Gautam Dasarathy |
| 开课单位: | 信息不详。欢迎您在右侧留言补充。 |
| 开课时间: | 2015-08-20 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | This paper investigates the problem of active learning for binary label prediction on a graph. We introduce a simple and label-efficient algorithm called $S^2$ for this task. At each step, $S^2$ selects the vertex to be labeled based on the structure of the graph and all previously gathered labels. Specifically, $S^2$ queries for the label of the vertex that bisects the {\em shortest shortest} path between any pair of oppositely labeled vertices. We present a theoretical estimate of the number of queries $S^2$ needs in terms of a novel parametrization of the complexity of binary functions on graphs. We also present experimental results demonstrating the performance of $S^2$ on both real and synthetic data. While other graph-based active learning algorithms have shown promise in practice, our algorithm is the first with both good performance and theoretical guarantees. Finally, we demonstrate the implications of the $S^2$ algorithm to the theory of nonparametric active learning. In particular, we show that $S^2$ achieves near minimax optimal excess risk for an important class of nonparametric classification problems. |
| 关 键 词: | 最短路径; 主动学习理论：非参数分类 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2025-04-20：zsp |
| 最后编审: | 2025-04-20：zsp |
| 阅读次数: | 4 |