图 书 馆
图形学习的可扩展算法Scalable algorithms for learning on graphs |
|
| 课程网址: | http://videolectures.net/icml2010_cesa_bianchi_salg/ |
| 主讲教师: | Nicolò Cesa-Bianchi |
| 开课单位: | 米兰大学 |
| 开课时间: | 2010-07-20 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Networked data are found in a variety of domains: Web, social networks, biological networks, and many others. In learning tasks, networked data are often represented as a weighted graph whose edge weights reflect the similarity between incident nodes. In this talk, we consider the problem of classifying the nodes of an arbitrary given graph in the game-theoretic mistake bound model. We characterize the optimal predictive performance in terms of the cutsize of the graph's random spanning tree, and describe a randomized prediction algorithm achieving the optimal performance while running in expected time sublinear in the graph size (on most graphs). These results are then extended to the active learning model, where training labels are obtained by querying nodes selected by the algorithm. We describe a fast query placement strategy that, in the special case of trees, achieves the optimal number of mistakes when classifying the non-queried nodes. Joint work with: Claudio Gentile, Fabio Vitale and Giovanni Zappella. |
| 关 键 词: | 网络数据; 加权图; 随机生成树 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-04-25：cwx |
| 阅读次数: | 29 |