||
The Sum-over-Paths Covariance Kernel: A Novel Covariance Measure between Nodes of a Directed Graph
Mantrach, Amin; Yen, Luh; Callut, Jerome; Francoisse, Kevin; Shimbo, Masashi; Saerens, Marco;
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume: 32 , Issue: 6
Digital Object Identifier: 10.1109/TPAMI.2009.78
Publication Year: 2010 , Page(s): 1112 - 1126
IEEE Journals
Abstract | Full Text: PDF (2167 KB)
如何衡量一个有向图上的两个节点的相关性?这是机器学习里的一个重要问题,可以应用在诸如半监督分类等问题上。
作者在这里别出心裁,提出了一个新颖的想法:如果两个节点越经常在同一个路径上出现,则他们相关性越大!
这点是和传统的方法的根本不同,不是直接衡量两点多距离什么的,而是看他们是不是在同一路径出现:一句话,两只蚂蚱像不像,看他们是不是在同一跟绳上!
关键问题是:这里的路径如何定义?
作者又说了:当然,路径越短,走完路径话费代价越小,当然就越好了。为此,作者决定在每个路径上定义一个概率分布:路径越长,概率越小,路径越短,概率越大。从而,变成一个求概率分布的问题P:
求一个P使得:P(路径)×E(走完路径的耗费)最小。这个问题的解,转化成一个玻尔兹曼分布(还有相关的“配分函数”)!
学机器学习的可能对这个玻尔兹曼分布不熟悉,但是问问搞统计物理的人,根本就是小儿科嘛!
顺水推舟,作者推出了根据“配分函数”计算两节点的协方差的公式,并且给出了计算分配函数的方法。于是问题解决了!
这个协方差,可以在用来计算两点间的相关,而这相关这可以作为定义在一个有向图上的核,用来做半监督分析之用。
亮点:
可能的改进之处:
是否能将这个核应用于相似度学习?正如白所做的那样?
还有几点没搞清楚:(12)和(16)为啥要这么计算?
奇怪的是,作者的教育经历:
Currently, I am completing a Ph.D. at the IRIDIA laboratory (the artificial intelligence laboratory, Université Libre de Bruxelles (ULB), Belgium).
I received the B.Sc. degree in computer science, and the M.Sc. degree in bioinformatics in 2004, all from the Université Libre de Bruxelles (ULB), Belgium.
并没有任何统计物理相关的,估计也是作者自己兴趣比较广泛吧?
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-25 06:56
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社