论文标题
稀疏的随机最短路径与tsallis差异正则化路由
Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization
论文作者
论文摘要
这项工作详细阐述了（1）设计最佳随机路由策略，以达到目标节点t的最佳随机注释t，从加权的有向图G上的源注释s和（2）定义节点之间定义距离的距离，在最低成本（基于最佳运动）和通勤成本（基于随机的g上）（根据g上的随机步行），根据该温度的速度（根据该温度的随机步行）（根据该温度的随机步行）（根据该温度的随机步行） [2,99,124]）根据tsallis差异正则化而不是kullback-leibler差异。这种变化的主要结果是，当t减小时，所得的路由策略（本地过渡概率）变得更稀疏，因此，当t趋向于0时，诱导g趋向于g趋向于g时，t趋向于0。在节点群集上进行实验比较时，对节点群集和半纯净的分类任务的结果表明，基于预期的成本，以衍生的量表来实现差异。因此，稀疏的RSP是图表上运动的有前途的运动模型，以最佳方式平衡稀疏的剥削和探索。
This work elaborates on the important problem of (1) designing optimal randomized routing policies for reaching a target node t from a source note s on a weighted directed graph G and (2) defining distance measures between nodes interpolating between the least cost (based on optimal movements) and the commute-cost (based on a random walk on G), depending on a temperature parameter T. To this end, the randomized shortest path formalism (RSP, [2,99,124]) is rephrased in terms of Tsallis divergence regularization, instead of Kullback-Leibler divergence. The main consequence of this change is that the resulting routing policy (local transition probabilities) becomes sparser when T decreases, therefore inducing a sparse random walk on G converging to the least-cost directed acyclic graph when T tends to 0. Experimental comparisons on node clustering and semi-supervised classification tasks show that the derived dissimilarity measures based on expected routing costs provide state-of-the-art results. The sparse RSP is therefore a promising model of movements on a graph, balancing sparse exploitation and exploration in an optimal way.
