最优传输问题
考虑这么一个问题，假设佬友 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 |
非常好，我们已经得到一个可行方案了。把上述问题归纳抽象成数学语言，就是一个最优传输 ( Optimal Transport) 问题：
在给定源分布、目标分布和运输代价矩阵的情况下，求一个非负矩阵，使得它的行和、列和分别等于给定分布，并且总运输成本最小。
已知供给 \muμ、需求 \nuν 、以及每条路的单位成本 C_{ij}Cij。
目标运输矩阵 \PiΠ:
- \Pi_{ij} \geq 0Πij≥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Π∈U(μ,ν)⟨C,Π⟩=∑i,jCijΠij
| 数学语言 | 与引入问题的对应 |
|---|
| 源分布 | 供给端（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Π∈U(μ,ν)⟨C,Π⟩−εH(Π)
其中，
H(\Pi) = - \sum_{i,j} \Pi_{ij} \log \Pi_{ij}
H(Π)=−∑i,jΠijlogΠij
而 \varepsilonε 代表了分散程度，该值如果取 0，则问题等价于原始的最优传输问题，该值增大，传输方案越软。
增加熵正则项后，目标函数就从线性变成了强凸性的。在给定 \varepsilonε 的情况下，熵正则最优传输问题的最优解是唯一的，且具有一个非常优雅的结构:
\Pi^* = \mathrm{diag}(u) K \mathrm{diag}(v), K_{ij} = \exp(-C_{ij}/\varepsilon)
Π∗=diag(u)Kdiag(v),Kij=exp(−Cij/ε)
计算出缩放系数 uu、vv 就能给出最优解了，这里有个简单的 Sinkhorn 算法，通过交替地更新这两个缩放系数，让边际约束满足:
u \leftarrow \mu /(K v), \quad v \leftarrow \nu /(K^{\top} u)
u←μ/(Kv),v←ν/(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=[1e−1e−11]=[]
第 1 轮迭代后的方案 X^{(1)}X(1)
X^{(1)} \approx \begin{bmatrix} 80.92193504 & 25.26714252 \\ 119.07806496 & 274.73285748 \end{bmatrix}
X(1)≈[]
此时行和误差约为 6.1891：
- 行和 \approx (106.18907756, 393.81092244)≈(,)
- 列和 = (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≈ (100.00034024, 399.99965976) (已经非常接近供给)
・列和 = (200, 300)
双随机矩阵
解决了熵正则最优问题，我们再来看看这个传输矩阵，如果我们把供给、需求归一化，那么原先的传输矩阵就变成了一个 “分配比例” 矩阵，每个格子不再代表具体分配的额度，而是分配比例。失去量纲让它变得更加通用了，从一个具体的 “分配方案” 变成了一个 “通用的分配规则”。
如果进一步把供给端和需求端设置为均匀分布（都是 1），那么这种 “分配比例” 矩阵会具备如下特点：
具备这些特点的矩阵，取名叫 “双随机矩阵”，因为它每行每列都像是一个随机概率分布。可以把双随机矩阵看成一个软路由表，它规定了供给和需求之间的分配比例，又可以通过软化系数 \varepsilonε 避免极端分配情况（即不把鸡蛋放在一个篮子里）和快速调整（可学习性）。
容易观察到，它具备乘法封闭性：
任意两个 nxn 双随机矩阵相乘，结果仍然是双随机矩阵。
相当于可以累积这种路由表，而保持供给、需求的分配方案不崩溃 —— 你叠多少层 “软分配”，整体仍然是一个合法的软分配，不会出现 “某个需求方越分越多、某个供给方越分越空” 的诡异情况。如果需要对一个分布进行信息重分配，那双随机矩阵是一个非常好的选择。
诶，既需要避免累积导致模式崩溃，又期望促进不同分布之间进行信息分配，还有良好的可学习性性质，那不正是神经网络中常见的需求吗？这也正是 DeepSeek mHC 引入双随机矩阵（论文里的故事叫 “流形约束”）的重要原因。啊这鸡汤真是太好喝了，哦不是， 这矩阵真是太美妙了。
- 字节的 HC 尝试引入 Mapping 来丰富跨层连接多样性，mHC 则通过双随机矩阵约束改良了 HC 的训练不稳定性（谱范数为 1，累乘封闭性）
（除引入双随机矩阵外，mHC 也做了很多扎实的优化工作，这里就不再赘述和解读了，仅从最优传输角度提供一种浅浅解读）
📌 转载信息
原作者：
zhong_little
转载时间：
2026/1/3 14:54:58
