提出在图上计算概率测度加权平均的新方法,解决传统方法失效问题。
Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs
- 利用动态最优传输的黎曼结构,在图上定义测度的加权平均
- 通过内蕴梯度下降合成测度,数值实验验证了有效性
- 适合处理图结构数据的信号分析与机器学习任务
最优传输问题定义了概率测度间的几何关系,从而引出测度加权平均(重心)的概念,在机器学习与计算机视觉中作为信号处理工具。本文针对支持在图上的测度,提出一种重心编码模型。由于经典最优传输几何在图结构下退化,本研究利用动态最优传输问题诱导的单纯形黎曼结构,近似其指数映射及逆映射,基于已有计算作用最小路径的方法,数值逼近离散空间上测度间的传输距离。采用内蕴梯度下降合成重心,通过近似当前迭代点与参考测度之间的测地线,计算方差泛函梯度,并通过连续性方程离散化推进迭代。通过求解目标测度与参考测度间测地线构成的二次规划问题,实现对测度的分析。将该方法与基于静态最优传输熵正则化、用图距离函数编码图结构的方法进行对比,数值实验验证了本文方法的有效性,结论表明:在概率单纯形上的内蕴梯度下降为图上测度的合成与分析提供了连贯框架。
原文摘要 · Abstract (English)
The optimal transportation problem defines a geometry of probability measures which leads to a definition for weighted averages (barycenters) of measures, finding application in the machine learning and computer vision communities as a signal processing tool. Here, we implement a barycentric coding model for measures which are supported on a graph, a context in which the classical optimal transport geometry becomes degenerate, by leveraging a Riemannian structure on the simplex induced by a dynamic formulation of the optimal transport problem. We approximate the exponential mapping associated to the Riemannian structure, as well as its inverse, by utilizing past approaches which compute action minimizing curves in order to numerically approximate transport distances for measures supported on discrete spaces. Intrinsic gradient descent is then used to synthesize barycenters, wherein gradients of a variance functional are computed by approximating geodesic curves between the current iterate and the reference measures; iterates are then pushed forward via a discretization of the continuity equation. Analysis of measures with respect to given dictionary of references is performed by solving a quadratic program formed by computing geodesics between target and reference measures. We compare our novel approach to one based on entropic regularization of the static formulation of the optimal transport problem where the graph structure is encoded via graph distance functions, we present numerical experiments validating our approach, and we conclude that intrinsic gradient descent on the probability simplex provides a coherent framework for the synthesis and analysis of measures supported on graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。