当前位置: 首页 > news >正文

最优传输问题和Sinkhorn

最优传输问题

假设有M堆土,每堆土的大小是ama_mam,有N个坑,每个坑的大小是bnb_nbn,把单位土从土堆m运送到坑n的代价是c(m,n)c(m,n)c(m,n),如何找到一种运输方法填满坑,并且代价最小,这就是最优传输问题(optimal transport (OT) problem)。

假设有两个概率分布,类似上面的情况,如何以最小的成本将一种概率分布转换为另一种概率分布,这也是最优传输问题。这个最小的成本可以作为度量两个概率分布的距离,被称为Wasserstein距离,或者推土机距离(Earth Mover’s Distance(EMD))。

在离散的情况下,假设r,c\mathbf r, \mathbf cr,c是两个概率向量,也就是所有元素求和为1的向量。1d\mathbf 1_d1d是维度为ddd所有元素为1的向量。
运输多面体(transport polytope )U(r,c)U(\mathbf r,\mathbf c)U(r,c)被定义为:
U(r,c):={P∈R+d×d∣P1d=r,P⊤1d=c}U(\mathbf r,\mathbf c) := \{ \mathbf P \in \mathbb R^{d \times d}_+ | \mathbf P \mathbf 1_d = \mathbf r, \mathbf P^\top \mathbf 1_d = \mathbf c\} U(r,c):={PR+d×dP1d=r,P1d=c}
给定一个费用矩阵M∈Rd×d\mathbf M \in \mathbb R^{d \times d}MRd×dr\mathbf rrc\mathbf cc的最优传输距离被定义为:
dM(r,c):=min⁡P∈U(r,c)<P,M>=∑i=1d∑j=1dPijMijd_{\mathbf M}(\mathbf r, \mathbf c) := \min_{\mathbf P \in U(\mathbf r,\mathbf c)}<\mathbf P, \mathbf M> = \sum_{i=1}^d \sum_{j=1}^d \mathbf{P}_{ij} \mathbf{M}_{ij} dM(r,c):=PU(r,c)min<P,M>=i=1dj=1dPijMij对于一般的矩阵M\mathbf MM,目前提出的最佳算法在最坏情况下的复杂度是 O(d3log⁡d)O(d^3 \log d)O(d3logd)。在实践中复杂度也被证明是超立方的。

Sinkhorn距离

为上面的最优传输问题加上熵正则化:
dMλ(r,c)=min⁡P∈U(r,c)∑i,jPijMij−1λh(P)h(P)=−∑i,jPijlog⁡Pijd_\mathbf{M}^\lambda(\mathbf{r}, \mathbf{c}) = \min_{\mathbf P\in U(\mathbf{r}, \mathbf{c})}\, \sum_{i,j} \mathbf P_{ij} \mathbf M_{ij} - \frac{1}{\lambda}h(\mathbf P)\\ h(\mathbf P) = -\sum_{i,j}\mathbf P_{ij}\log \mathbf P_{ij} dMλ(r,c)=PU(r,c)mini,jPijMijλ1h(P)h(P)=i,jPijlogPij dMλ(r,c)d_\mathbf{M}^\lambda(\mathbf{r}, \mathbf{c})dMλ(r,c)被称为dual-Sinkhorn divergence,h(P)h(\mathbf P)h(P)是香浓熵(Shannon entropy)。
λ→0\lambda\rightarrow0λ0时,上面问题的解是Pij=ricj\mathbf P_{ij}=\mathbf r_i \mathbf c_jPij=ricj;当λ→∞\lambda\rightarrow\inftyλ时,回到了原始的最优输运问题。
香浓熵要求分配更加均匀, 参数λ\lambdaλ权衡了按花费分配和平分。

加上熵正则的最优传输问题变得更好计算了,因为解变得平滑。
Sinkhorn定理被用来寻找熵正则化最优输运问题的解。

参考资料

Wiki Sinkhorn’s theorem
Notes on Optimal Transport
http://alexhwilliams.info/itsneuronalblog/2020/10/09/optimal-transport/
https://zipjiang.github.io/2020/11/23/sinkhorn’s-theorem-,-sinkhorn-algorithm-and-applications.html

相关文章:

最优传输问题和Sinkhorn

最优传输问题 假设有M堆土&#xff0c;每堆土的大小是ama_mam​&#xff0c;有N个坑&#xff0c;每个坑的大小是bnb_nbn​&#xff0c;把单位土从土堆m运送到坑n的代价是c(m,n)c(m,n)c(m,n)&#xff0c;如何找到一种运输方法填满坑&#xff0c;并且代价最小&#xff0c;这就是…...

Netty核心组件EventLoop源码解析

源码解析目标 分析最核心组件EventLoop在Netty运行过程中所参与的事情&#xff0c;以及具体实现 源码解析 依然用netty包example下Echo目录下的案例代码&#xff0c;单我们写一个NettyServer时候&#xff0c;第一句话就是 EventLoopGroup bossGroup new NioEventLoopGroup(…...

排障命令-汇总

目录 日志查询 1. grep 2. zgrep cpu 1. top 内存 1. free tcp相关 1. netstat 2. ulimit 3. lsof jvm常用 1. jps 2. jinfo 3. jstack 4. jmap 5. jstat 进制转换 1. 十进制转16进制 日志查询 1. grep 定义&#xff1a;(global regular expression) 命令用于查…...

python+pytest接口自动化(4)-requests发送get请求

python中用于请求http接口的有自带的urllib和第三方库requests&#xff0c;但 urllib 写法稍微有点繁琐&#xff0c;所以在进行接口自动化测试过程中&#xff0c;一般使用更为简洁且功能强大的 requests 库。下面我们使用 requests 库发送get请求。requests库简介requests 库中…...

开源电子书工具Calibre 6.3 发布

Calibre 开源项目是 Calibre 官方出的电子书管理工具。它可以查看&#xff0c;转换&#xff0c;编辑和分类所有主流格式的电子书。Calibre 是个跨平台软件&#xff0c;可以在 Linux、Windows 和 macOS 上运行。Calibre 6.3 正式发布&#xff0c;此次更新内容如下&#xff1a;新…...

C++ STL:适配器 Adapter

文章目录1、容器适配器1.1、stack1.2、queue1.3、priority_queue2、迭代器适配器2.1、插入迭代器2.2、反向迭代器2.3、流迭代器3、函数适配器3.1、* bindbind 使用方法bind 简化原理3.2、mem_fn适配器就是接口&#xff0c;对容器、迭代器、算法进行包装&#xff0c;但其实质还是…...

防抖和节流

防抖和节流的区别&#xff1f;防抖&#xff1a;触发高频事件后n 秒内 函数只会执行一次&#xff0c;如果n秒内 高频事件在在次触发&#xff0c;则会重新计算节流&#xff1a;高频事件触发&#xff0c;但在n 秒内 只会执行一次&#xff0c;所以节流会稀释函数的执行频率下面就是…...

vue3 微信扫码登录及获取个人信息实现的三种方法

一、流程&#xff1a; 微信提供的扫码方式有两种,分别是: 跳转二维码扫描页面 内嵌式二维码根据文档我们可以知道关于扫码授权的模式整体流程为: 1. 第三方发起微信授权登录请求&#xff0c;微信用户允许授权第三方应用后&#xff0c;微信会拉起应用或重定向到第三方网站&…...

Java8 新特性强大的Stream API

一、Stream API 说明 Java8中有两大最为重要的改变。第一个是 Lambda 表达式&#xff1b;另外一个则是 Stream API。 Stream API ( java.util.stream) 把真正的函数式编程风格引入到Java中。这是目前为止对Java类库最好的补充&#xff0c;因为Stream API可以极大提供Ja…...

day22_IO

今日内容 上课同步视频:CuteN饕餮的个人空间_哔哩哔哩_bilibili 同步笔记沐沐霸的博客_CSDN博客-Java2301 零、 复习昨日 一、作业 二、缓冲流 三、字符流 四、缓冲字符流 五、匿名内部类 零、 复习昨日 File: 通过路径代表一个文件或目录 方法: 创建型,查找类,判断类,其他 IO …...

第三十八章 linux-并发解决方法二(信号量)

第三十八章 linux-并发解决方法二&#xff08;信号量&#xff09; 文章目录第三十八章 linux-并发解决方法二&#xff08;信号量&#xff09;信号量的定义DOWN操作UP操作相对于自旋锁&#xff0c;信号量的最大特点是允许调用它的线程进入睡眠状态这意味着试图获得某一信号的进程…...

数据结构-考研难点代码突破(C++实现树型查找 - B树插入与遍历,B+树基本概念)

数据结构&#xff08;C&#xff09;[B树&#xff08;B-树&#xff09;插入与中序遍历&#xff0c;效率分析]、B树、B*树、B树系列应用 文章目录1. B树B树的插入与删除流程2. B树&#xff08;MySQL&#xff09;3. B树与B树对比4. C实现B树插入&#xff0c;中序遍历1. B树 B树类…...

Python可视化界面编程入门

Python可视化界面编程入门具体实现代码如所示&#xff1a; &#xff08;1&#xff09;普通可视化界面编程代码入门&#xff1a; import sys from PyQt5.QtWidgets import QWidget,QApplication #导入两个类来进行程序界面编程if __name__"__main__":#创建一个Appl…...

基于Java+SpringBoot+Vue前后端分离书店购书系统设计与实现

博主介绍&#xff1a;✌全网粉丝3W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战✌ 博主作品&#xff1a;《微服务实战》专栏是本人的实战经验总结&#xff0c;《Spring家族及…...

Android:截屏/视频截图

需求描述 实现截取Android应用当前界面的功能&#xff0c;需包含界面中视频&#xff08;此博客的参考代码以存储在设备本地的视频为例&#xff0c;未检验在线视频的情况&#xff09;当前的播放帧截图。 调研准备 首先应用需要获取设备存储的读写权限&#xff0c;需要在Andro…...

leecode-C语言实现-28. 找出字符串中第一个匹配项的下标

一、题目给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack 的一部分&#xff0c;则返回 -1 。示例 1&#xff1a;输入&#xff1a;haystack …...

使用 Postman 实现 API 自动化测试

目录&#xff1a;导读 背景介绍 名词解析 使用说明 执行 API 测试 集成 CI 实现 API 自动化测试 写在最后 背景介绍 相信大部分开发人员和测试人员对 postman 都十分熟悉&#xff0c;对于开发人员和测试人员而言&#xff0c;使用 postman 来编写和保存测试用例会是一种比…...

k8s环境jenkins发布vue项目指定nodejs版本

k8s环境jenkins发布vue项目指定nodejs版本1、背景2、分析3、解决方法3.1、 找到配置镜像位置3.2、 制作新镜像3.3、 推送镜像到私有仓库3.4、 修改配置文件1、背景 发布一个前端项目&#xff0c;它需要nodejs 16.9.0版本支持&#xff0c;而kubesphere 3.2.0集成的jenkins 的镜…...

我应该把毕业设计做到什么程度才能过关?

本篇博客包含了狗哥多年职业生涯对于软件项目的一丢丢理解&#xff0c;也讲述了对于大学生毕业设计的一些理解。如果你还是懵懵懂懂就要离开学校了&#xff0c;被老师告知不得不做出一套毕业设计的时候&#xff0c;希望你可以看到这篇博客&#xff0c;让你有点头绪&#xff0c;…...

力扣-合作过至少三次的演员和导演

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目&#xff1a;1050. 合作过至少三次的演员和导演二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...

Python爬虫(四):PyQuery 框架

PyQuery 框架详解与对比 BeautifulSoup 第一部分&#xff1a;PyQuery 框架介绍 1. PyQuery 是什么&#xff1f; PyQuery 是一个 Python 的 HTML/XML 解析库&#xff0c;它采用了 jQuery 的语法风格&#xff0c;让开发者能够用类似前端 jQuery 的方式处理文档解析。它的核心特…...

记一次spark在docker本地启动报错

1&#xff0c;背景 在docker中部署spark服务和调用spark服务的微服务&#xff0c;微服务之间通过fegin调用 2&#xff0c;问题&#xff0c;docker容器中服务器来后&#xff0c;注册中心都有&#xff0c;调用服务也正常&#xff0c;但是调用spark启动任务后报错&#xff0c;报错…...

python打卡day47

昨天代码中注意力热图的部分顺移至今天 知识点回顾&#xff1a; 热力图 作业&#xff1a;对比不同卷积层热图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import D…...

timestamp时间戳转换工具

作为一名程序员&#xff0c;一款高效的 在线转换工具 &#xff08;在线时间戳转换 计算器 字节单位转换 json格式化&#xff09;必不可少&#xff01;https://jsons.top 排查问题时非常痛的点: 经常在秒级、毫秒级、字符串格式的时间单位来回转换&#xff0c;于是决定手撸一个…...