图 书 馆
一种用于链接分类的快速主动学习算法A Fast Active Learning Algorithm for Link Classification |
|
| 课程网址: | http://videolectures.net/machine_zappella_learning_algorithm/ |
| 主讲教师: | Giovanni Zappella |
| 开课单位: | 米兰大学 |
| 开课时间: | 2013-08-06 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We present a very efficient active learning algorithm for link classification in signed networks. Our algorithm is motivated by a stochastic model in which edge labels are obtained through perturbations of an initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to within a constant factor) number of mistakes on any graph G = (V;E) such that |E| = \Omega(|V|^3/2) by querying O(|V|^3/2) edge labels. More generally, we show an algorithm that achieves optimality to within a factor of O(k) by querying at most order of |V| + (|V|/k)^3/2 edge labels. The running time of this algorithm is at most of order |E| + |V| log |V|. |
| 关 键 词: | 主动学习算法; 符号网络; 链接分类; 常数因子 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-03-27：chenxin |
| 阅读次数: | 52 |