SPR-001：用递归路径替代稠密矩阵
问题
Transformer 的输出层做了这件事：
hidden (256 维)
│
× Output 矩阵 O ∈ ℝ^{256 × 32000} ← 8.2M 个浮点参数
│
→ 32000 维 logits
│
softmax → argmax → 下一个词
每一步都在问全部 32000 个词：“是不是你？” 不管 context 已经强烈缩小了候选范围（比如前文是 “the cat sat on the…"，下一个词几乎肯定是名词/介词），O 矩阵还是老老实实把 32000 维全算一遍。
能不能不这么做？
方案：SPR（语义前缀路由）
用一棵语义判定树替代 Output 矩阵。
● ( hidden 向量 )
/ \
判定: 动词? 名词?
/ \
... ...
/ \ / \
cat grep 猫 狗
(命令) (搜索) (动物) (动物)
每个内部节点是一个极小的线性门：
$$P(\text{左}) = \sigma( \mathbf{h} \cdot \mathbf{w}_{\text{node}} + b )$$$$P(\text{右}) = 1 - P(\text{左})$$- 每个节点只有 d+1 个参数（d=256 时仅 257 个浮点数）
- 整棵树 512 个内部节点 = 512×257 ≈ 131K 参数
- vs Output 矩阵的 8.2M —— 减少 60 倍
查 max 天然快： 从根开始，每个节点问 “左还是右”，log₂V 步走到叶子 → 拿到预测词。不需要算 32000 维 softmax。
词的不同用法天然对应不同路径：
cat 可以出现在两条路径上——
- 动词路径（Linux 命令）→ 左子树
- 名词路径（动物）→ 右子树
传统 embedding 把这两个 cat 塞进同一个 256 维向量里（混淆）。SPR 把不同语义的同一个 token 放在了树的不同位置，路径不同，表示不同。
树拓扑从哪里来？
三种方案，复杂度递进：
| 方案 | 树结构 | 学习内容 | 复杂度 |
|---|---|---|---|
| 静态 | 预先用词聚类（Brown clustering / WordNet）建树 | 仅边权 W | 低 |
| 半动态 | 固定结构，词可以移动到不同叶子 | 边权 + 词→叶映射 | 中 |
| 全动态 | 树拓扑本身随训练改变 | 边权 + 结构 | 高 |
最激进的方案——启动时树全是 0，每次梯度更新同时改变边权和子节点分配。这等于把 embedding 学习变成了树拓扑的动态重组。
训练
每个 token 有一条目标路径（根→目标词所在叶子）。交叉熵损失：
$$L = -\sum_{\text{路径上的节点}} \log P(\text{正确的方向} \mid \mathbf{h})$$链式求导照样沿着树往下传，每一步只更新当前节点的 w 和 b。叶子节点上的词不需要跟其他 31999 个词比——只跟同一个父节点下的兄弟比。
与现有方案的关系
| Output 矩阵 | Hierarchical Softmax | SPR | |
|---|---|---|---|
| 结构 | 稠密 32000×256 | 固定二叉树（词频建） | 可学习的语义判定树 |
| 查找 | O(V) | O(log V) | O(log V) |
| 参数 | 8.2M | ~8.2M | ~131K |
| 结构学习 | 不需要 | 不需要 | 可以学 |
| 多义词 | 混淆在同一向量 | 混淆在同一叶子 | 天然分开 |
下一步
- 静态版本实现：用词聚类建树 + 线性门节点 → 测 WMT14 BLEU
- 动态叶分配：每个词可以在多个叶子间重新分配
- 与 T1 基线（d256/3L, BLEU=3.58）对比
如果 131K 参数的树能达到 32000×256 稠密矩阵的效果——那就证明了不是参数多有用，而是参数的组织方式有用。
May the Code be with us.
License: GPLv3