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

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...