图 书 馆
已知图和未知图的网络数据的在线相似度预测Online Similarity Prediction of Networked Data from Known and Unknown Graphs |
|
| 课程网址: | http://videolectures.net/colt2013_herbster_graphs/ |
| 主讲教师: | Mark Herbster |
| 开课单位: | 伦敦大学学院 |
| 开课时间: | 2013-08-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We consider online similarity prediction problems over networked data. We begin by relating this task to the more standard class prediction problem, showing that, given an arbitrary algorithm for class prediction, we can construct an algorithm for similarity prediction with “nearly” the same mistake bound, and vice versa. After noticing that this general construction is computationally infeasible, we target our study to feasible similarity prediction algorithms on networked data. We initially assume that the network structure is known to the learner. Here we observe that Matrix Winnow (Warmuth, 2007) has a near-optimal mistake guarantee, at the price of cubic prediction time per round. This motivates our effort for an efficient implementation of a Perceptron-like algorithm with a weaker mistake guarantee but with only poly-logarithmic prediction time. Our focus then turns to the challenging case of networks whose structure is initially unknown to the learner. In this novel setting, where the network structure is only incrementally revealed, we obtain a mistake-bounded algorithm with a quadratic prediction time per round. |
| 关 键 词: | 网络数据; 在线相似度预测; 类预测; 预测算法; 网络结构; 最优化 |
| 课程来源: | 视频讲座网公开课 |
| 最后编审: | 2019-05-26：cwx |
| 阅读次数: | 29 |