双随机矩阵
双随机矩阵（Doubly Stochastic Matrix）笔记
配套笔记：
sinkhorn-knopp理解.md— Sinkhorn-Knopp 算法的目标就是"任意正矩阵 → 双随机矩阵"，是这份笔记的应用层。涉及代码：
dinov3/loss/dino_clstoken_loss.py:42-70— DINO 损失里把 teacher logits 缩到"列和=1、行和均匀"的目标分布dinov3/loss/ibot_patch_loss.py:20-58— iBOT patch 损失里的版本
1. 一句话定义
$$ A \in \mathbb{R}^{n \times m}_+,\quad A\mathbf{1} = \mathbf{1},\quad A^\top \mathbf{1} = \mathbf{1} $$双随机矩阵 = 一个 $n \times n$（或 $n \times m$）的非负矩阵，每一行求和为 1，每一列求和也为 1。 它是"行随机"和"列随机"的合集，本质上代表"概率分布之上的概率转移"。
记号约定（也是 DINO 代码里用的）：
- $A\mathbf{1} = \mathbf{1}$：每行和=1（row-stochastic）
- $A^\top \mathbf{1} = \mathbf{1}$：每列和=1（column-stochastic）
注意"行/列"的方向：在 DINO 论文里常说"列和=1"是因为他们把矩阵写成"行=样本、列=原型"（$B \times K$），所以"每列=1"= 每样本=概率分布。在 Sinkhorn-Knopp 笔记里
Q.t()之后变成 $[K, B]$，此时"每行=1"指每原型。方向不同只是约定不同，本质都是双随机。
2. 对比：三种随机矩阵
| 名称 | 约束 | 物理/概率意义 | 代表 |
|---|---|---|---|
| 一般（非负）矩阵 | $A \ge 0$ | 任意"权重矩阵" | 邻接矩阵、注意力权重 |
| 行随机矩阵（row-stochastic） | $A \ge 0$，$A\mathbf{1} = \mathbf{1}$ | 右乘概率向量 = 新的概率分布 | Markov 链转移矩阵（标准用法） |
| 列随机矩阵（column-stochastic） | $A \ge 0$，$A^\top \mathbf{1} = \mathbf{1}$ | 左乘概率向量 = 新的概率分布 | 反向 Markov、对偶问题 |
| 双随机矩阵（doubly stochastic） | $A \ge 0$，两者都满足 | 概率分布与自身做"对称"映射 | OT 耦合、prototype 软分配 |
行随机矩阵的物理意义最容易懂：把"状态 $i$“转移成"状态 $j$“的概率，于是右乘一个状态分布向量 $\pi$ 仍然得到合法的分布 $\pi' = A^\top \pi$。双随机矩阵的额外约束”$A^\top \mathbf{1} = \mathbf{1}$“意味着：均匀分布 $\mathbf{1}/n$ 也是稳态（下面 §4.3 详述）。
3. 核心定理与直觉
3.1 几何直觉：Birkhoff-von Neumann 定理（“模糊的置换矩阵”）
定理（Birkhoff 1946, von Neumann 1953）：任意双随机矩阵都可以写成若干置换矩阵（permutation matrix）的凸组合：
$$ > A = \sum_{k} \theta_k P_k,\quad \theta_k \ge 0,\ \sum_k \theta_k = 1 > $$其中每个 $P_k$ 都是"每行每列恰好一个 1、其余 0"的矩阵。
物理意义：
- 置换矩阵 = “确定性"的元素重排（把位置 $i$ 映射到位置 $P(i)$）
- 双随机矩阵 = “概率性"或"软"的元素重排（$a_{ij}$ = “把 $i$ 处的质量按比例分到 $j$ 处"的概率）
- 凸组合系数 $\theta_k$ 告诉你"在所有可能的硬匹配方案中，各选哪个”
这个定理非常关键——它把”连续的、双随机的、可微的“对象和”离散的、不可微的、组合的“对象用凸包联系起来。这是为什么 DINO 训练时能"软对齐"到一组 prototype（双随机），推理/离散化时再投回"硬聚类”（置换）。
3.2 信息论直觉：Majorization 与熵增
双随机矩阵乘以一个向量 $\mathbf{x}$ 得到 $\mathbf{y} = A\mathbf{x}$，会发生什么？
定理（Hardy-Littlewood-Pólya）：$\mathbf{y} = A\mathbf{x}$，$A$ 双随机 ⟹ $\mathbf{y} \prec \mathbf{x}$（称 $\mathbf{y}$ 被 $\mathbf{x}$ 控制（majorized））。
等价描述（按降序排列 $\mathbf{x}^\downarrow, \mathbf{y}^\downarrow$）：
$$ \sum_{i=1}^{k} y^\downarrow_i \le \sum_{i=1}^{k} x^\downarrow_i,\quad k = 1, \dots, n $$且总和不严格增加（因为 $A$ 行和=1）。这意味着：
- 大的分量被"挤小”、小的分量被"填大”
- 分布变得更均匀
- Shannon 熵不减：$H(A\mathbf{x}) \ge H(\mathbf{x})$（在 $A$ 全正且不可分解时严格 >）
直观例子：
$$ \mathbf{x} = \begin{pmatrix} 1 \\ 0 \end{pmatrix},\quad A = \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix} \Rightarrow A\mathbf{x} = \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix} $$一个极端集中的分布被"打散"成均匀分布——这就是双随机矩阵的熵增效应。
3.3 Markov 链直觉：均匀分布是唯一稳态
设 $A$ 是双随机矩阵，看 $A$ 当 Markov 链转移矩阵：
- 任意分布 $\pi$ 演化一步：$\pi' = A^\top \pi$
- 想找稳态 $\pi^*$：$A^\top \pi^* = \pi^*$
- 直接验：$\pi^* = \mathbf{1}/n$（均匀分布），因为 $A^\top \mathbf{1} = \mathbf{1}$
- 如果 $A$ 是不可约 aperiod的，$\pi^* = \mathbf{1}/n$ 是唯一稳态
物理意义：在双随机转移下，不管初始分布是什么，长期都会"熵增"到完全均匀的稳态——双随机矩阵是最公平、最混乱的随机游走。
DINO 直接用了这条直觉：
- 矩阵 $P$（teacher 目标）被强制成"列和=1”——这正是双随机（行=1） + 全局 $B$ 倍缩放
- “行和均匀” ⟺ “每 prototype 的边际分配概率相同” ⟺ 避免 prototype collapse
- 即使 teacher 训练初期输出极不均匀，Sinkhorn 投影每步都把分布往"最均匀"方向拉，最终在稳态附近对齐
4. 数学性质
4.1 Sinkhorn 缩放定理（与 SK 笔记的 §3.2 呼应）
定理（Sinkhorn 1964）：设 $M \in \mathbb{R}^{n \times m}_+$，且 $M$ 的支撑图（$\{(i,j): M_{ij} > 0\}$）含一个完美匹配（即零模式有完美匹配）。当且仅当这个条件满足，存在对角正定矩阵 $D_1 \in \mathbb{R}^{n \times n}$、$D_2 \in \mathbb{R}^{m \times m}$，使 $D_1 M D_2$ 是双随机的。
而且 $D_1, D_2$ 唯一（差一个标量倍数）。
应用到 DINO：
- $M = \exp(Z/\tau)$：严格正（无零元素）
- → 完美匹配条件自动满足
- → $D_1, D_2$ 存在且唯一
- → Sinkhorn-Knopp 迭代就是在数值上求 $D_1, D_2$
4.2 Birkhoff 多面体（Birkhoff polytope）
所有 $n \times n$ 双随机矩阵的集合 $\Omega_n$ 是个凸多面体：
- 顶点：所有 $n!$ 个置换矩阵（由 Birkhoff 定理）
- 内部：所有"严格正且不可分解"的双随机矩阵
- 维数：$(n-1)^2$
这给出了"双随机 = 置换的凸包"的几何图像。任何投影、任何最优传输问题，目标约束集都是这个多面体。
4.3 对偶与谱性质
- $A$ 双随机 $\Rightarrow$ 1 是 $A$ 的特征值（对应右/左特征向量 $\mathbf{1}$）
- 其它特征值的模 $\le 1$
- 谱半径 $\rho(A) = 1$，且 $A$ 的第二特征值 $\lambda_2$ 决定 Markov 链收敛速度（$\sim \lambda_2^t$）
4.4 基本不等式
| 不等式 | 形式 | 含义 |
|---|---|---|
| Hölder | $\langle A, B\rangle \le \sum_i r_i c_i$ | 双随机矩阵的 Frobenius 内积被行的"匹配列和"控制 |
| Birkhoff–von Neumann | $A = \sum \theta_k P_k$ | 任意双随机 = 置换凸组合 |
| Schur-Horn | $A$ 双随机 ⟹ $\mathrm{diag}(A)$ 在 $\Omega_n$ 顶点可达 | 任何"对角线和=1"向量都能被某个置换实现 |
5. 在 DINOv3 中的角色：与 Sinkhorn-Knopp 的关系
DINOv3 的 teacher 输出 $P \in \mathbb{R}^{B \times K}$ 满足（dino_clstoken_loss.py:42-70）：
注意：这不是严格"列和=1"的双随机矩阵，而是"列和=1 + 行和均匀"。但数学本质相同——把 $P$ 乘上 $K/B$ 就得到严格双随机（$B \times K$ 维度上的）：
$$ \tilde P = \frac{K}{B} P,\quad \tilde P \mathbf{1} = \frac{K}{B}\mathbf{1},\quad \tilde P^\top \mathbf{1} = \mathbf{1} $$为什么 DINO 要选这个"缩放版"？因为：
- $P$ 直接当 student 交叉熵的 target，需要是合法的概率分布 → $P\mathbf{1} = \mathbf{1}$（每行=1）
- 要避免 prototype collapse → $P^\top \mathbf{1}$ 必须均匀（每列= $B/K$）
- 这两个要求在 $B \neq K$ 时不能同时严格满足"列和=1"的双随机
- 折中：$P$ 在 $K$ 列上按 $B/K$ 缩放——是双随机矩阵 $\tilde P$ 的 $\frac{B}{K}$ 倍
5.1 为什么 Sinkhorn-Knopp 能"打到"这个目标？
回顾：$Q = \exp(Z/\tau) \in \mathbb{R}^{B \times K}_+$（严格正）。
Sinkhorn 定理保证存在唯一的 $D_1, D_2$：
$$ \tilde Q = D_1 Q D_2 \in \mathbb{R}^{B \times K},\quad \tilde Q \mathbf{1} = \frac{K}{B}\mathbf{1},\ \tilde Q^\top \mathbf{1} = \mathbf{1} $$即 $\tilde Q$ 是双随机。乘 $B/K$ 还原后就是 DINO 的目标 $P$。
5.2 双随机约束给 DINO 带来什么？
| 性质 | 公式 | DINO 实际效果 |
|---|---|---|
| 行和=1 | $\sum_j P_{ij} = 1$ | 合法概率分布，可作 cross-entropy target |
| 列和均匀 | $\sum_i P_{ij} = B/K$ | 每 prototype 的边际分配概率相同，防 collapse |
| Birkhoff 凸包 | $P = \sum \theta_k P_k$ | 软分配是"硬聚类的凸组合"——$P$ 训练收敛后，再做硬分配是凸优化 |
| 熵增 | $H(PZ) \ge H(Z)$ | Sinkhorn 把 teacher 的"尖峰分布"自动平滑化，让 student 学到稳定信号 |
| 唯一稳态 | $\pi^* = \mathbf{1}/K$ | 长期 teacher 目标稳定在均匀分配附近，不漂移 |
最后两条（DINO 直接受益）是单随机矩阵做不到的——这正是 DINOv2+ 改用 Sinkhorn-Knopp 替代 DINOv1 的 softmax-center 的根本原因（见 sinkhorn-knopp理解.md §7）。
6. 其它机器学习中的双随机矩阵
6.1 最优传输（Optimal Transport, OT）
经典 OT 问题：把分布 $\mathbf{a}$ 传输到 $\mathbf{b}$，最小化 $\langle C, P \rangle$，约束是 $P \ge 0$、$P\mathbf{1} = \mathbf{a}$、$P^\top \mathbf{1} = \mathbf{b}$。当 $\mathbf{a} = \mathbf{b} = \mathbf{1}/n$（等概率），约束就退化为双随机约束。
熵正则 OT（Cuturi 2013）：
$$ P^\star = \arg\min_{P \in \Omega} \langle C, P \rangle - \varepsilon H(P) $$的最优解必有形式 $P^\star_{ij} = u_i K_{ij} v_j$（$K_{ij} = e^{-C_{ij}/\varepsilon}$），其中 $\mathbf{u}, \mathbf{v}$ 由 Sinkhorn 迭代给出——这正是 Sinkhorn-Knopp 算法的"再发现"路径。
6.2 注意力机制
标准 attention 的权重矩阵是行随机（行=1，列不一定）。如果用 Sinkhorn 把 attention 矩阵额外约束成双随机，就得到：
- 列也归一化 → 不同 query 之间互斥（不让一个 key 被多 query 抢）
- 论文：Sparse Attention via Balancing 等
6.3 图匹配 / 线性分配
要在两个大小相同的图之间找节点对应（1-to-1 匹配）：
- 理想解：置换矩阵（$n!$ 种，离散不可微）
- 连续松弛：双随机矩阵的 Birkhoff 多面体（连续可微）
- 优化完成后：匈牙利算法 / Sinkhorn 投回置换矩阵
DINO 的"prototype 软分配"本质是同一种松弛——区别只是 DINO 不需要"1-to-1 硬匹配"（多 sample 可共享 prototype），所以最后停在双随机（带 $B/K$ 缩放）就够了。
6.4 谱聚类 / 归一化切割
Normalized Cut 的连续松弛等价于求一个归一化 Laplacian 的特征向量。双随机归一化（Sinkhorn-Knopp on 相似度矩阵）则是更稳定的变体。
7. 易混点 & 常见错误
“双随机"vs"对称双随机”：
- 双随机：$A\mathbf{1} = \mathbf{1}$，$A^\top \mathbf{1} = \mathbf{1}$
- 对称双随机：上面 + $A = A^\top$（额外要求）
- DINO 用的不是对称的（$B \neq K$ 都不可能是方阵）
“列和=1"的方向依赖：
- 在 $B \times K$ 矩阵（行=样本，列=原型）上，“列和=1” 实际上意味着"每样本=1”
- 实际读 DINO 论文/代码时，要确认是哪个维度——很多新手被"列和=1"误导
双随机 ≠ 联合分布归一化：
- 把矩阵 $\sum$ 总和归一到 1，是"全局单随机"
- 双随机要求每行每列分别归一到 1（约束更强）
Sinkhorn 收敛的隐藏条件：
- 输入矩阵 $Q$ 的支撑图必须含完美匹配（全零行/列 → 除零爆）
- DINO 里 $Q = \exp(Z/\tau)$ 严格正，永远满足
- 但如果用 ReLU、thresholding 等操作破坏了正定性，Sinkhorn 就会出问题
$B = K$ 时双随机 = 严格双随机：
- 此时 $B/K = 1$，无需缩放
- DINO 默认 $B \ll K$（batch ~256，prototype 65536+），所以缩放很关键
DINOv1 vs DINOv2 的差异：
- v1 用 EMA center + softmax（不是双随机）——靠"减均值"来去偏
- v2+ 用 Sinkhorn-Knopp（是双随机）——靠"投影到多面体"来去偏
- 两种都"防 collapse"，但机制不同
8. 一句话总结
双随机矩阵是"置换矩阵的连续凸包"——把离散的硬匹配松弛成连续的概率分配，约束"行和=列和=1"使其像"最公平"的最优传输耦合 / 最混乱的 Markov 稳态。 在 DINOv3 中，Sinkhorn-Knopp 迭代把 teacher 的 logits 强制投影到"行=1、列均匀"的目标分布，本质上是把任意正矩阵变换成"带 $B/K$ 缩放的双随机矩阵"，这给 SSL 提供了合法概率目标 + 防 prototype collapse + 熵平滑三重保证，是 DINO 损失鲁棒收敛的几何基石。