当前位置: 首页 > 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运…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

ABAP设计模式之---“Tell, Don’t Ask原则”

“Tell, Don’t Ask”是一种重要的面向对象编程设计原则&#xff0c;它强调的是对象之间如何有效地交流和协作。 1. 什么是 Tell, Don’t Ask 原则&#xff1f; 这个原则的核心思想是&#xff1a; “告诉一个对象该做什么&#xff0c;而不是询问一个对象的状态再对它作出决策。…...