最优传输问题和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):={P∈R+d×d∣P1d=r,P⊤1d=c}
给定一个费用矩阵M∈Rd×d\mathbf M \in \mathbb R^{d \times d}M∈Rd×d,r\mathbf rr到c\mathbf cc的最优传输距离被定义为:
dM(r,c):=minP∈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):=P∈U(r,c)min<P,M>=i=1∑dj=1∑dPijMij对于一般的矩阵M\mathbf MM,目前提出的最佳算法在最坏情况下的复杂度是 O(d3logd)O(d^3 \log d)O(d3logd)。在实践中复杂度也被证明是超立方的。
Sinkhorn距离
为上面的最优传输问题加上熵正则化:
dMλ(r,c)=minP∈U(r,c)∑i,jPijMij−1λh(P)h(P)=−∑i,jPijlogPijd_\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)=P∈U(r,c)mini,j∑PijMij−λ1h(P)h(P)=−i,j∑PijlogPij 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堆土,每堆土的大小是ama_mam,有N个坑,每个坑的大小是bnb_nbn,把单位土从土堆m运送到坑n的代价是c(m,n)c(m,n)c(m,n),如何找到一种运输方法填满坑,并且代价最小,这就是…...

Netty核心组件EventLoop源码解析
源码解析目标 分析最核心组件EventLoop在Netty运行过程中所参与的事情,以及具体实现 源码解析 依然用netty包example下Echo目录下的案例代码,单我们写一个NettyServer时候,第一句话就是 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 定义:(global regular expression) 命令用于查…...

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

开源电子书工具Calibre 6.3 发布
Calibre 开源项目是 Calibre 官方出的电子书管理工具。它可以查看,转换,编辑和分类所有主流格式的电子书。Calibre 是个跨平台软件,可以在 Linux、Windows 和 macOS 上运行。Calibre 6.3 正式发布,此次更新内容如下:新…...
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适配器就是接口,对容器、迭代器、算法进行包装,但其实质还是…...
防抖和节流
防抖和节流的区别?防抖:触发高频事件后n 秒内 函数只会执行一次,如果n秒内 高频事件在在次触发,则会重新计算节流:高频事件触发,但在n 秒内 只会执行一次,所以节流会稀释函数的执行频率下面就是…...
vue3 微信扫码登录及获取个人信息实现的三种方法
一、流程: 微信提供的扫码方式有两种,分别是: 跳转二维码扫描页面 内嵌式二维码根据文档我们可以知道关于扫码授权的模式整体流程为: 1. 第三方发起微信授权登录请求,微信用户允许授权第三方应用后,微信会拉起应用或重定向到第三方网站&…...

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

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

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

数据结构-考研难点代码突破(C++实现树型查找 - B树插入与遍历,B+树基本概念)
数据结构(C)[B树(B-树)插入与中序遍历,效率分析]、B树、B*树、B树系列应用 文章目录1. B树B树的插入与删除流程2. B树(MySQL)3. B树与B树对比4. C实现B树插入,中序遍历1. B树 B树类…...

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

基于Java+SpringBoot+Vue前后端分离书店购书系统设计与实现
博主介绍:✌全网粉丝3W,全栈开发工程师,从事多年软件开发,在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战✌ 博主作品:《微服务实战》专栏是本人的实战经验总结,《Spring家族及…...
Android:截屏/视频截图
需求描述 实现截取Android应用当前界面的功能,需包含界面中视频(此博客的参考代码以存储在设备本地的视频为例,未检验在线视频的情况)当前的播放帧截图。 调研准备 首先应用需要获取设备存储的读写权限,需要在Andro…...

leecode-C语言实现-28. 找出字符串中第一个匹配项的下标
一、题目给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。示例 1:输入:haystack …...

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

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

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

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

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
TCP/IP 网络编程 | 服务端 客户端的封装
设计模式 文章目录 设计模式一、socket.h 接口(interface)二、socket.cpp 实现(implementation)三、server.cpp 使用封装(main 函数)四、client.cpp 使用封装(main 函数)五、退出方法…...

在Zenodo下载文件 用到googlecolab googledrive
方法:Figshare/Zenodo上的数据/文件下载不下来?尝试利用Google Colab :https://zhuanlan.zhihu.com/p/1898503078782674027 参考: 通过Colab&谷歌云下载Figshare数据,超级实用!!࿰…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验
2024年初,人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目(一款融合大型语言模型能力的云端AI编程IDE)时,技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力,TRAE在WayToAGI等…...