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(走完路径的耗费)最小。这个问题的解，转化成一个玻尔兹曼分布（还有相关的“配分函数”）！

学机器学习的可能对这个玻尔兹曼分布不熟悉，但是问问搞统计物理的人，根本就是小儿科嘛！

顺水推舟，作者推出了根据“配分函数”计算两节点的协方差的公式，并且给出了计算分配函数的方法。于是问题解决了！

这个协方差，可以在用来计算两点间的相关，而这相关这可以作为定义在一个有向图上的核，用来做半监督分析之用。

亮点：

1. 两点的相似性，用是否在一条路径上来衡量，我想到过了，可惜没有具体地定义出如何来计算；
2. 学科间的融会贯通，最内在的东西，是思想方法的贯通，而不是表面上一个学科做工具，一个学科做应用。可惜这样的合作实在太难了，我觉得只有一个人同时学了这两个学科才有可能在自己的大脑中融合，两个不同学科的人合作，太难了！

可能的改进之处：

1. 是否能将这个核应用于相似度学习？正如白所做的那样？ 

2. 还有几点没搞清楚：（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.

并没有任何统计物理相关的，估计也是作者自己兴趣比较广泛吧？