最优传输OT

POUF-UDA in Pretrain models Optimal Transport（最优传输）是一种数学理论，研究如何高效地将一个分布（或资源）转换为另一个分布的问题，同时最小化传输的“成本”。其核心思想起源于 Gaspard Monge 提出的经典问题：如何以最小的成本将一堆泥土移动到一个特定的地方，给定泥土的起始分布和目标分布。

假设有两个概率分布 $P$ 和 $Q$：

• $P$ 是源分布，定义在空间 $\mathcal{X}$ 上。
• $Q$ 是目标分布，定义在空间 $\mathcal{Y}$ 上。
• $c(x,y)$ 是从点 $x\in \mathcal{X}$ 移动到点 $y\in \mathcal{Y}$ 的成本函数（例如欧氏距离或其他度量）。

Monge 公式
Monge 提出的问题写为：

$$\underset{T:T_{\#}P=Q}{\min }{\int }_{\mathcal{X}}c(x,T(x))P(x)dx,$$

其中 $T:\mathcal{X}\to \mathcal{Y}$ 是映射函数，$T_{\#}P=Q$ 表示通过映射 $T$ 后，源分布 $P$ 被转换为目标分布 $Q$。

Kantorovich 松弛
Monge 的问题因严格要求映射 $T$ 可行，可能不总是有解。Kantorovich 提出了松弛版本，允许概率质量分布在多个目标点之间分配，定义为：

$$\underset{\pi \in \Pi (P,Q)}{\min }{\int }_{\mathcal{X}\times \mathcal{Y}}c(x,y)\pi (x,y)dxdy,$$

其中 $\pi (x,y)$ 是联合分布，称为传输计划，$\Pi (P,Q)$ 是满足边缘分布为 $P$ 和 $Q$ 的联合分布集合：

$${\int }_{\mathcal{Y}}\pi (x,y)dy=P(x),{\int }_{\mathcal{X}}\pi (x,y)dx=Q(y).$$

关键概念

• 传输成本 $c(x,y)$ 衡量从点 $x$ 到点 $y$ 的代价，通常选择为欧氏距离的幂： $$c(x,y)=\Vert x-y{\Vert }^p.$$
• Wasserstein 距离 衡量两个概率分布之间的距离，为 OT 问题的解： $$W_p(P,Q)={\left(\underset{\pi \in \Pi (P,Q)}{\min }{\int }_{\mathcal{X}\times \mathcal{Y}}\Vert x-y{\Vert }^p\pi (x,y)dxdy\right)}^{1/p}.$$ 常见的 Wasserstein 距离包括 $W_1$（Earth Mover’s Distance）和 $W_2$，后者常用于图像处理和生成对抗网络。

Entropic Regularization（熵正则化）
为了降低计算复杂度，可以引入熵正则化：

$$\underset{\pi \in \Pi (P,Q)}{\min }{\int }_{\mathcal{X}\times \mathcal{Y}}c(x,y)\pi (x,y)dxdy+\epsilon {\int }_{\mathcal{X}\times \mathcal{Y}}\pi (x,y)\log \pi (x,y)dxdy,$$

使解更加平滑，可通过 Sinkhorn-Knopp 算法快速求解。

应用领域

• 机器学习：
  • 域适配：最小化源域和目标域分布之间的 Wasserstein 距离。
  • GAN：Wasserstein GAN 用 $W_1$ 距离替代 JS 散度，改善训练稳定性。
  • 特征匹配：用于分布对齐和聚类。
• 图像处理：
  • 颜色迁移：调整图像的颜色分布。
  • 图像配准：对齐图像像素分布。
• 物理与经济：
  • 资源分配问题：描述从供应分布到需求分布的最优分配。

实际例子

Given two discrete distributions $P$ and $Q$ as defined in POUF-UDA in Pretrain models, the Optimal Transport (OT) between them is expressed as:

$$\text{OT}(P,Q):=\underset{T\in \Pi (u,v)}{\min }\text{Tr}(T^{\top }C),\text{\hspace{1em}(3)}$$

where:

• $T\in {\mathbb{R}}_{+}^{K\times N}$ is a doubly stochastic transport matrix, meaning it satisfies the marginal constraints: $$\Pi (u,v)=\{T\mid T{1}_N=u,T^{\top }{1}_K=v\}.$$
• $T_{ij}$ represents the transport probability between $x_i$ and $y_j$.
• $C\in {\mathbb{R}}_{+}^{K\times N}$ is the transport cost matrix, with entries $C_{ki}=c(w_k,f_i)$ denoting the cost of transporting mass from $w_k$ to $f_i$.
• $\text{Tr}(\cdot )$ is the matrix trace operator, representing the sum of the diagonal elements of the matrix.

满足边际分布在最优传输问题和概率分布对齐中是一个核心约束条件，确保传输方案保持输入和输出分布的总量一致性。以下是详细解析：

1. 什么是“满足边际分布”？
   在最优传输（Optimal Transport, OT）中，边际分布约束是指传输矩阵 $T$ 必须满足预定义的边际分布 $u$ 和 $v$，即：

$$T{1}_N=u,T^{\top }{1}_K=v$$

• $T{1}_N=u$：
  $T$ 的行总和等于 $u$，表示分布 $P$ 中的每个点 $w_k$ 的总传输量与其权重 $u_k$ 相等，直观上，分布 $P$ 的质量不能“凭空消失”，也不能“额外生成”。
• $T^{\top }{1}_K=v$：
  $T$ 的列总和等于 $v$，表示分布 $Q$ 中的每个点 $f_i$ 的总接收量与其权重 $v_i$ 相等，直观上，分布 $Q$ 的质量只能从 $P$ 的传输中获得。

边际分布：

• $u$：$P$ 的边际分布，表示每个文本原型 $w_k$ 的权重。
• $v$：$Q$ 的边际分布，表示每个目标样本 $f_i$ 的权重。

通过边际分布约束，确保传输矩阵 $T$ 的行为严格符合输入分布 $P$ 和输出分布 $Q$ 的特性。

2. 边际分布约束的意义

• (1) 确保质量守恒：
  边际分布约束确保输入分布 $P$ 的总质量与输出分布 $Q$ 的总质量一致，避免“凭空生成”或“丢失”质量的现象。例如在物流运输中，这意味着运输的总货物量必须等于原始供应量，且接收方接收的总量必须等于需求量。
• (2) 确保分布匹配：
  边际分布约束使传输方案严格对齐输入和输出分布，统计上保证 $T$ 矩阵能够保留 $P$ 和 $Q$ 的分布关系。
• (3) 提供优化问题的可行性：
  定义所有可能传输方案的集合 $\Pi (u,v)$，缩小优化问题的范围，使得解更稳定和有意义。
• (4) 建模模态对齐问题：
  在多模态学习中，边际分布约束将文本模态和图像模态的分布联系起来。例如，文本原型的分布权重能够准确传输到目标图像的嵌入分布。

3. 边际分布约束的目的

• (1) 实现模态对齐：
  在多模态嵌入中，文本模态的分布和图像模态的分布需要对齐，边际分布约束通过控制传输矩阵 $T$ 确保权重分布上的合理性。
• (2) 保证模型稳定性：
  确保传输方案 $T$ 遵循合理的质量流动规则，避免解发散或不稳定。
• (3) 限制传输成本：
  限定传输方案 $T$ 的总传输量（由边际分布 $u$ 和 $v$ 决定），间接限制总传输成本的上界，从而提升优化效率。

4. 应用示例
   假设 $P$ 和 $Q$ 分别是文本嵌入和图像嵌入的分布：

• 边际分布的定义：
  $u_k=\frac{1}{K}$，表示每个文本原型的权重相等；$v_i=\frac{1}{N}$，表示每个图像样本的权重相等。
• 传输矩阵的约束：
  $T$ 的行和对应文本原型的权重 $u$；$T$ 的列和对应目标图像样本的权重 $v$。
• 效果：
  确保文本嵌入和图像嵌入的权重对齐，从而实现跨模态分布的对齐。

5. 总结
   满足边际分布的约束是最优传输问题的核心条件，具有以下意义：

• 确保输入和输出分布的质量守恒，避免不合理的分布调整。
• 提供合理的分布对齐基础，保证传输矩阵 $T$ 的结果具有物理和统计意义。
• 限制优化问题范围，提高解的稳定性和效率。
• 在多模态学习和概率分布对齐中，边际分布约束是实现模态对齐和分布匹配的重要工具。