标签 Entropy Regularization 下的文章

最优传输问题

考虑这么一个问题，假设佬友 A、B 分别有 100 刀、400 刀 api，佬友 C、D 分别有 200 刀、300 刀的 api 需求，那么怎么生成一个合理的分配方案

我们可以很容易列出这么一个表格

供给 \ 需求	C(200)	D(300)
A(100)
B(400)

由于供给需求平衡，分配方案是非常多的，比如使用对角线定 1 法，立马就能像填字游戏一样给出一个结果：

对角线定 1：

供给 \ 需求 C(200) D(300)

A(100) 100
B(400)
填充空格：

供给 \ 需求 C(200) D(300)

A(100) 100 0
B(400) 100 300

供给 \ 需求	C(200)	D(300)
A(100)	100
B(400)

供给 \ 需求	C(200)	D(300)
A(100)	100	0
B(400)	100	300

非常好，我们已经得到一个可行方案了。把上述问题归纳抽象成数学语言，就是一个最优传输 ( Optimal Transport) 问题：

在给定源分布、目标分布和运输代价矩阵的情况下，求一个非负矩阵，使得它的行和、列和分别等于给定分布，并且总运输成本最小。

已知供给 \mu $μ$ 、需求 \nu $ν$ 、以及每条路的单位成本 C_{ij} $C_{i j}$ 。
目标运输矩阵 \Pi $Π$ :

\Pi_{ij} \geq 0 $Π_{i j} \geq 0$
行和 = 供给: \Pi 1 = \mu $Π 1 = μ$
列和 = 需求: \Pi^{\top} 1 = \nu $Π^{⊤} 1 = ν$

目标：总成本最小

\min_{\Pi \in \mathcal{U}(\mu,\nu)} \langle C, \Pi \rangle = \sum_{i,j} C_{ij}\Pi_{ij}

min Π \in U (μ, ν) ⟨ C, Π ⟩ = \sum i, j C_{i j} Π_{i j}

数学语言	与引入问题的对应
源分布	供给端（100,400）
目标分布	需求端（200,300）
传输代价	未显式体现，默认都是单位代价
非负矩阵	传输非负性，不能从需求端分配资源给供给端

听起来这个问题也不难嘛，填填空也就把方案做出来了，那么这个分配方式有什么问题吗？

规模复杂性：如果供给方和需求方数量增加，问题也将复杂起来，由于要求传输非负性，定 1 法可能导致其他位置计算出现负数而需要进行调整
成本敏感性：给定供给方和需求方之间的传输代价，问题复杂度也立马上升
解的稀疏性：定 1 法容易产生大量 0 元素，在应对分布改变和成本改变时不稳定，比如某个供给方断供，其对应的需求方将立刻卡脖子

为了不把鸡蛋放在一个篮子里（解的稀疏性）和解决其他问题，我们需要把分配方式软化，比如这样的分配方式就被认为比之前的方案更加 “软”：

供给 \ 需求	C(200)	D(300)
A(100)	50	50
B(400)	150	250

那么，怎么数学化地计算这种软化方案呢，数学家引入了一种叫熵正则项，用来惩罚传输方案里的极端项，就是让你不要把鸡蛋放在一个篮子里：就算你供给量少，也要拆开卖，万一买家跑了你也不至于全亏损；就算你需求少，也分开买，卖家不稳定了你还有缓冲。于是熵正则最优传输的目标变成:

\min_{\Pi \in \mathcal{U}(\mu, \nu)} \langle C, \Pi \rangle - \varepsilon H(\Pi)

min Π \in U (μ, ν) ⟨ C, Π ⟩ - ε H (Π)

其中，

H(\Pi) = - \sum_{i,j} \Pi_{ij} \log \Pi_{ij}

H (Π) = - \sum i, j Π_{i j} log Π_{i j}

而 \varepsilon $ε$ 代表了分散程度，该值如果取 0，则问题等价于原始的最优传输问题，该值增大，传输方案越软。
增加熵正则项后，目标函数就从线性变成了强凸性的。在给定 \varepsilon $ε$ 的情况下，熵正则最优传输问题的最优解是唯一的，且具有一个非常优雅的结构:

\Pi^* = \mathrm{diag}(u) K \mathrm{diag}(v), K_{ij} = \exp(-C_{ij}/\varepsilon)

Π^{*} = d i a g (u) K d i a g (v), K_{i j} = exp (- C_{i j} / ε)

计算出缩放系数 u $u$ 、v $v$ 就能给出最优解了，这里有个简单的 Sinkhorn 算法，通过交替地更新这两个缩放系数，让边际约束满足:

u \leftarrow \mu /(K v), \quad v \leftarrow \nu /(K^{\top} u)

u \leftarrow μ / (K v), v \leftarrow ν / (K^{⊤} u)

由于该问题变成强凸性，所以上述过程收敛很快（线性收敛），而且迭代过程只涉及逐行逐列的元素归一化（可规模化并行计算），是一个非常实用的方案。

以前述引入问题为例

取 \varepsilon=1 $ε = 1$ , 计算 K 矩阵：

K = \begin{bmatrix} 1 & e^{-1} \\ e^{-1} & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0.36787944 \\ 0.36787944 & 1 \end{bmatrix}

K = [\begin{matrix} 1 & e^{- 1} e^{- 1} & 1 \end{matrix}] = []

第 1 轮迭代后的方案 X^{(1)} $X^{(1)}$

X^{(1)} \approx \begin{bmatrix} 80.92193504 & 25.26714252 \\ 119.07806496 & 274.73285748 \end{bmatrix}

X^{(1)} \approx []

此时行和误差约为 6.1891：

行和 \approx (106.18907756, 393.81092244) $\approx (,)$
列和 = (200, 300) $= (200, 300)$

第 6 轮迭代后的方案 X^{(6)} $X^{(6)}$

X^{(6)} \approx \begin{bmatrix}
76.70375289 & 23.29658735 \\
123.29624711 & 276.70341265
\end{bmatrix}

X^{(6)} \approx []

・行和 \approx $\approx$ (100.00034024, 399.99965976) (已经非常接近供给)
・列和 = (200, 300)

双随机矩阵

解决了熵正则最优问题，我们再来看看这个传输矩阵，如果我们把供给、需求归一化，那么原先的传输矩阵就变成了一个 “分配比例” 矩阵，每个格子不再代表具体分配的额度，而是分配比例。失去量纲让它变得更加通用了，从一个具体的 “分配方案” 变成了一个 “通用的分配规则”。

如果进一步把供给端和需求端设置为均匀分布（都是 1），那么这种 “分配比例” 矩阵会具备如下特点：

所有元素非负
各行元素之和为 1
各列元素之和为 1

具备这些特点的矩阵，取名叫 “双随机矩阵”，因为它每行每列都像是一个随机概率分布。可以把双随机矩阵看成一个软路由表，它规定了供给和需求之间的分配比例，又可以通过软化系数 \varepsilon $ε$ 避免极端分配情况（即不把鸡蛋放在一个篮子里）和快速调整（可学习性）。

容易观察到，它具备乘法封闭性：

任意两个 nxn 双随机矩阵相乘，结果仍然是双随机矩阵。

相当于可以累积这种路由表，而保持供给、需求的分配方案不崩溃 —— 你叠多少层 “软分配”，整体仍然是一个合法的软分配，不会出现 “某个需求方越分越多、某个供给方越分越空” 的诡异情况。如果需要对一个分布进行信息重分配，那双随机矩阵是一个非常好的选择。

诶，既需要避免累积导致模式崩溃，又期望促进不同分布之间进行信息分配，还有良好的可学习性性质，那不正是神经网络中常见的需求吗？这也正是 DeepSeek mHC 引入双随机矩阵（论文里的故事叫 “流形约束”）的重要原因。~~啊这鸡汤真是太好喝了，哦不是，~~ 这矩阵真是太美妙了。

字节的 HC 尝试引入 Mapping 来丰富跨层连接多样性，mHC 则通过双随机矩阵约束改良了 HC 的训练不稳定性（谱范数为 1，累乘封闭性）

（除引入双随机矩阵外，mHC 也做了很多扎实的优化工作，这里就不再赘述和解读了，仅从最优传输角度提供一种浅浅解读）

📌 转载信息

来源：
https://linux.do/t/topic/1400097

原作者：
zhong_little

转载时间：
2026/1/3 14:54:58