Following [21, 23], the present work investigates a new relative entropy-regularized algorithm for solving the optimal transport on a graph problem within the randomized shortest paths formalism. More precisely, a unit flow is injected into a set of input nodes and collected from a set of output nodes while minimizing the expected transportation cost together with a paths relative entropy regularization term, providing a randomized routing policy. The main advantage of this new formulation is the fact that it can easily accommodate edge flow capacity constraints which commonly occur in real-world problems. The resulting optimal routing policy, i.e., the probability distribution of following an edge in each node, is Markovian and is computed by constraining the input and output flows to the prescribed marginal probabilities thanks to a variant of the algorithm developed in [8]. In addition, experimental comparisons with other recently developed techniques show that the distance measure between nodes derived from the introduced model provides competitive results on semi-supervised classification tasks.


翻译:在 [21, 23] 之后,本项工作调查了一种新的相对正正正常规算法,用以在随机最短路径的形式主义范围内解决图形问题的最佳传输。更准确地说,单位流被注入一组输入节点,从一组输出节点中收集,同时尽量减少预期的运输成本,同时提供一个路径相对加密正规化的术语,提供随机化的路线政策。这一新公式的主要优点是,它能够很容易地适应现实世界问题中常见的边缘流动能力限制。由此产生的最佳路线政策,即每个节点边缘的概率分布是Markovian,其计算方法是将输入和输出流限制在[8] 所开发的算法变异的规定的边际概率。此外,与其他最近开发的技术的实验性比较表明,从采用的模式中得出的节点之间的距离测量方法在半超强分类任务上提供了竞争性的结果。

0
下载
关闭预览

相关内容

深度学习理论,55页ppt,Preetum Nakkiran (UCSD)
专知会员服务
32+阅读 · 2021年10月27日
【Google-Marco Cuturi】最优传输,339页ppt,Optimal Transport
专知会员服务
47+阅读 · 2021年10月26日
【UAI2021教程】贝叶斯最优学习,65页ppt
专知会员服务
64+阅读 · 2021年8月7日
专知会员服务
45+阅读 · 2021年7月26日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年11月10日
Arxiv
0+阅读 · 2021年11月9日
Arxiv
20+阅读 · 2021年2月28日
Arxiv
5+阅读 · 2021年1月7日
Arxiv
3+阅读 · 2018年1月10日
VIP会员
相关VIP内容
深度学习理论,55页ppt,Preetum Nakkiran (UCSD)
专知会员服务
32+阅读 · 2021年10月27日
【Google-Marco Cuturi】最优传输,339页ppt,Optimal Transport
专知会员服务
47+阅读 · 2021年10月26日
【UAI2021教程】贝叶斯最优学习,65页ppt
专知会员服务
64+阅读 · 2021年8月7日
专知会员服务
45+阅读 · 2021年7月26日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员