最优传输问题与Sinkhorn算法

这篇具有很好参考价值的文章主要介绍了最优传输问题与Sinkhorn算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 引言

最近看到一篇特征匹配相关的论文,思想是将特征匹配问题转化为最优传输问题求解,于是我去学习了一下最优传输问题。
本文主要是对博文 Notes on Optimal Transport 的学习做一个记录总结,该博文写的不错,推荐阅读。

2 例子:分甜点

文章作者以一个简单的甜点分配例子引入了最优传输问题。
向量 r = [ 3 , 3 , 3 , 4 , 2 , 2 , 2 , 1 ] ⊤ \mathbf{r}=[3, 3, 3, 4, 2, 2, 2, 1]^{\top} r=[3,3,3,4,2,2,2,1] 表示 n = 8 n=8 n=8 个人需要的甜点数:
最优传输问题与Sinkhorn算法
向量 c = [ 4 , 2 , 6 , 4 , 4 ] ⊤ \mathbf{c}=[4, 2, 6, 4, 4]^{\top} c=[4,2,6,4,4] 表示 m = 5 m=5 m=5 种甜点的数量:
最优传输问题与Sinkhorn算法

矩阵 M ∈ R 5 × 8 \mathbf{M}\in \mathbb{R}^{5\times 8} MR5×8 表示每个人对各种甜点的偏好,尺度区间 [ − 2 , 2 ] [-2, 2] [2,2],-2表示非常不喜欢,2表示非常喜欢:
最优传输问题与Sinkhorn算法

我们的目标,就是要根据甜点的数量,同时考虑每个人的需求和偏好,将所有甜点合理地分配到每个人手中。

3 最优传输问题

最优运输问题的目标就是以最小的成本将一个概率分布转换为另一个概率分布。上面的分甜点的目标,用最优传输问题的定义来说,就是将概率分布 c \mathbf{c} c 以最小的成本转换到概率分布 r \mathbf{r} r
这就需要我们求得一个分配方案,由矩阵 P ∈ R n × m P\in \mathbb{R}^{n\times m} PRn×m 表示,存储每个人分得的每个甜点的情况。

根据现实条件,这个分配矩阵 P P P 显然具有以下约束:

  1. 分配的甜点数量不能为负数;
  2. 每个人的需求都要满足,即 P P P 的行和服从分布 r \mathbf{r} r
  3. 每种甜点要全部分完,即 P P P 的列和服从分布 c \mathbf{c} c

于是在分布 r \mathbf{r} r c \mathbf{c} c 约束下, P P P 的解空间可以做如下定义:
U ( r , c ) = { P ∈ R > 0 n × m ∣ P 1 m = r , P ⊤ 1 n = c } (1) U(\mathbf{r}, \mathbf{c})=\left\{P \in \mathbb{R}_{>0}^{n \times m} \mid P \mathbf{1}_{m}=\mathbf{r}, P^{\top} \mathbf{1}_{n}=\mathbf{c}\right\} \tag 1 U(r,c)={PR>0n×mP1m=r,P1n=c}(1)
PS:这是博文的原公式,这里我有个疑问,为什么 P P P 的元素要求严格大于0,而不是大于等于0?希望有同学能够解答我的疑惑(感谢)

如前面所述,我们希望最小化转换成本,可以简单地反转偏好矩阵 M \mathbf{M} M 的符号,就可以得到成本矩阵(cost matrix)。于是就有了最优传输问题的公式化表示:
d M ( r , c ) = min ⁡ P ∈ U ( r , c ) ∑ i , j P i j M i j (2) d_{M}(\mathbf{r}, \mathbf{c})=\min _{P \in U(\mathbf{r}, \mathbf{c})} \sum_{i, j} P_{i j} M_{i j} \tag 2 dM(r,c)=PU(r,c)mini,jPijMij(2)

标量 d M d_{M} dM 也被称为推土机距离(earth mover distance),因为它可以解释为至少移动多少“泥土”(成本)才能将一个土堆(分布)变成另一个土堆(分布)。

4 Sinkhorn算法

4.1 Sinkhorn距离

Sinkhorn距离是对推土机距离的一种改进,在其基础上引入了熵正则化项:
d M λ ( r , c ) = min ⁡ P ∈ U ( r , c ) ∑ i , j P i j M i j − 1 λ h ( P ) (3) d_{M}^{\lambda}(\mathbf{r}, \mathbf{c})=\min _{P \in U(\mathbf{r}, \mathbf{c})} \sum_{i, j} P_{i j} M_{i j}-\frac{1}{\lambda} h(P) \tag 3 dMλ(r,c)=PU(r,c)mini,jPijMijλ1h(P)(3)
其中 h ( P ) = − ∑ P i j log ⁡ P i j h(P)=-\sum{P_{ij}\log{P_{ij}}} h(P)=PijlogPij 称作 P P P 的信息熵(information entropy), P P P 分布越均匀,信息熵越大。

熵正则化参数 λ \lambda λ 负责调整信息熵的影响程度, λ \lambda λ 越大,信息熵的影响越小,最终结果受成本矩阵的影响更大,即更多地考虑每个人的喜好;反之,最终结果则更倾向于均匀分配,每种甜点将平均分配给每个人。

4.2 算法流程

新增的熵正则化项似乎让问题更加难以优化,但Sinkhorn算法提供了一种简单且有效的方法应对这一问题,Sinkhorn算法认为,最优分配矩阵 P λ ∗ P^*_\lambda Pλ 的元素应该具有如下形式:
( P λ ∗ ) i j = α i β j e − λ M i j (4) (P^*_\lambda)_{ij}=\alpha_i \beta_j e^{-\lambda M_{ij}} \tag 4 (Pλ)ij=αiβjeλMij(4)
其中正是 α 1 , . . . , α n \alpha_1,...,\alpha_n α1,...,αn β 1 , . . . , β n \beta_1,...,\beta_n β1,...,βn 使得 P ∗ P^* P 满足分配矩阵的三个约束。如何推导出这一形式可以参考SuperGlue中的最优传输算法详解一文。

具体流程如下:

给定: 代价矩阵 M M M, 分布 r \mathbf{r} r, 分布 c \mathbf{c} c, 熵正则化参数 λ \lambda λ
初始化: 分配矩阵 P λ = e − λ M P_\lambda=e^{-\lambda M} Pλ=eλM
重复:

  1. 缩放行,使得 P P P 的行和逼近分布 r \mathbf{r} r
  2. 缩放列,使得 P P P 的列和逼近分布 c \mathbf{c} c

直到: 收敛

4.3 代码实验

以下是Sinkhorn代码实现:

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt


r = np.array([3, 3, 3, 4, 2, 2, 2, 1])
c = np.array([4, 2, 6, 4, 4])
M = np.array(
    [[2, 2, 1, 0, 0], 
    [0, -2, -2, -2, -2], 
    [1, 2, 2, 2, -1], 
    [2, 1, 0, 1, -1],
    [0.5, 2, 2, 1, 0], 
    [0, 1, 1, 1, -1], 
    [-2, 2, 2, 1, 1], 
    [2, 1, 2, 1, -1]],
    dtype=float) 
M = -M # 将M变号,从偏好转为代价

def compute_optimal_transport(M, r, c, lam, eplison=1e-8):
    """
    Computes the optimal transport matrix and Slinkhorn distance using the
    Sinkhorn-Knopp algorithm

    Inputs:
        - M : cost matrix (n x m)
        - r : vector of marginals (n, )
        - c : vector of marginals (m, )
        - lam : strength of the entropic regularization
        - epsilon : convergence parameter

    Outputs:
        - P : optimal transport matrix (n x m)
        - dist : Sinkhorn distance
    """
    n, m = M.shape  # 8, 5
    P = np.exp(-lam * M) # (8, 5)
    P /= P.sum()  # 归一化
    u = np.zeros(n) # (8, )
    # normalize this matrix
    while np.max(np.abs(u - P.sum(1))) > eplison: # 这里是用行和判断收敛
        # 对行和列进行缩放,使用到了numpy的广播机制,不了解广播机制的同学可以去百度一下
        u = P.sum(1) # 行和 (8, )
        P *= (r / u).reshape((-1, 1)) # 缩放行元素,使行和逼近r
        v = P.sum(0) # 列和 (5, )
        P *= (c / v).reshape((1, -1)) # 缩放列元素,使列和逼近c
    return P, np.sum(P * M) # 返回分配矩阵和Sinkhorn距离

我们来看看在不同 λ \lambda λ 下,得到的分配矩阵有什么特点:

lam = 0.1

P, d = compute_optimal_transport(M,
        r,
        c, lam=lam)

partition = pd.DataFrame(P, index=np.arange(1, 9), columns=np.arange(1, 6))
ax = partition.plot(kind='bar', stacked=True)
print('Sinkhorn distance: {}'.format(d))
ax.set_ylabel('portions')
ax.set_title('Optimal distribution ($\lambda={}$)'.format(lam))

最优传输问题与Sinkhorn算法

可以看到每个人分配得到的甜点基本上都符合初始甜点的分布比例 c = [ 4 , 2 , 6 , 4 , 4 ] ⊤ \mathbf{c}=[4, 2, 6, 4, 4]^{\top} c=[4,2,6,4,4]

试着调大 λ \lambda λ
最优传输问题与Sinkhorn算法
可以看到最终的分配向每个人的偏好靠拢了。文章来源地址https://www.toymoban.com/news/detail-434851.html

到了这里,关于最优传输问题与Sinkhorn算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 基于 ARM SoC 的视频传输系统设计(10-01-01)引言

    新芯设计:专注,积累,探索,挑战   对于 《基于 SoC 的卷积神经网络车牌识别系统设计》 这个极具竞争的项目而言,其主要是 通过 CPU 软核 IP 在纯 FPGA 平台上构建一个 AI SoC 卷积神经网络车牌识别系统,其中,缩放、填充层、卷积层、ReLU、池化层、全连接层 IP 都是 V

    2024年01月25日
    浏览(35)
  • 【算法设计与分析】分治法(最近点对问题)

    目录 实验目的 实验内容与结果 蛮力法求解 分治法求解 实验总结 (1)掌握分治法思想。 (2)学会最近点对问题求解方法。 算法过程: 遍历n个点与剩余n-1个点之间的距离,在计算点对距离时不断更新最短距离的值,遍历完所有点对后即可求得最短点对距离。 伪代码: 复

    2024年02月08日
    浏览(46)
  • 最优化:建模、算法与理论(典型优化问题

    4.1.1 基本形式和应用背景 再次说明一下,其实这本书很多的内容之前肯定大家都学过,但是我觉得这本书和我们之前学的东西的出发角度不一样,他更偏向数学,也多一个角度让我们去理解 线性规划问题的一般形式如下: min ⁡ x ∈ R n c T x s . t . A x = b G x ≤ e (4.1.1) min_{x{

    2024年02月09日
    浏览(250)
  • 分治法解二维的最近对问题,算法分析与代码实现,蛮力法与分治法解决二维的最近对问题的区别

    🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨,经典算法的解析✨都在这儿,欢迎大家前往订阅本专题,获取更多详细信息哦🎏🎏🎏 🪔本系列专栏 -  数据结构与算法_勾栏听曲_0 🍻欢迎大家  🏹  点赞👍  评论📨  收藏⭐️ 📌个人主

    2024年02月04日
    浏览(40)
  • 计算机算法分析与设计(14)---贪心算法(会场安排问题和最优服务次序问题)

     假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 数据输入: 第 1 1 1 行中有一个整数 n n n ,表示有 n n n 个待安排的活动。接下来的 n n n 行中,每行有 2 2 2 个正整数,分别表示 n n n 个待安排的活动的开始时间和结束

    2024年02月02日
    浏览(43)
  • 深度学习求解稀疏最优控制问题的并行化算法

    问题改编自论文An FE-Inexact Heterogeneous ADMM for Elliptic Optimal Control Problems with L1-Control Cost { min ⁡ y ( μ ) , u ( μ )

    2024年02月07日
    浏览(44)
  • 【算法设计与分析】C++独立任务最优调度问题

    一、问题描述:   用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有aibi,而对于某些j,j≠i,有ajbj。既不能将一个作业分开由2台机器处理,也没有一台机器能同

    2024年02月11日
    浏览(41)
  • 小米妙享中心加载失败电脑能发现手机,手机能发现电脑,无法打开镜像画面,无法打开最近文件,能够看到但是无法打开,无法流转应用,无法共享屏幕

            本人是小米笔记本PRO14锐龙版WIN11系统,手机是小米14pro,电脑刚买来的时候都是可以正常在电脑投屏的,最近投屏总是失败报错,查了很久才解决这个问题可以正常投屏,所以发出来跟大家分享一下,以作参考。         首先要保证电脑上安装了小米妙享的最新

    2024年02月04日
    浏览(167)
  • Java使用遗传算法,寻找十滴水问题的最优解

    近期某手游出了个活动,经确认发现本质为十滴水游戏。 简单说一下规则,棋盘大小通常为6x6,在游戏开始时,棋盘随机有若干水珠,其大小范围为1-4。点击棋盘内的一格,会消耗玩家持有的1个小水滴,同时使得该单元格的水珠大小+1。如果水珠大小超过4,则水珠发生爆炸

    2024年02月20日
    浏览(42)
  • 【计算机算法】【图论】【最优匹配与点云对准问题】最(极)大团算法

    团与最大团的定义 图顶点集的子集满足任意两个顶点相邻,称该子集是该图的一个团。图的所有团中顶点最多的,即最大的一个或多个,称为图的最大团或极大团。 图的最大团的实际应用问题 CVPR2023最佳论文之一用最大团算法实现鲁棒的点云对准,有效解决外点问题。顾名

    2024年03月15日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包