【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 3：算法实现

论文：Multi-Head Encoding for Extreme Label Classification
作者：Daojun Liang, Haixia Zhang, Dongfeng Yuan and Minggao Zhang
单位：山东大学
代码：https://github.com/Anoise/MHE

论文地址：Online，ArXiv，GItHub

背景动机参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 1
基础知识参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 2
算法实现参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 3
表示能力参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 4
实验结果参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 5
无需预处理见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 6

请各位同学给我点赞，激励我创作更好、更多、更优质的内容！^_^

关注微信公众号，获取更多资讯

1 三种多头编码（MHE）实现

现在，我们考虑具体化的算法实现，以使MHE适用于各种XLC任务。具体地说，将MHP应用于xsl以实现多头并行加速。在XMLC中使用MHC来防止多个类别之间的混淆，在模型预训练中使用MHS来有效地提取特征，因为该任务不需要分类器。然后，我们提供了一种策略来确定头像的数量和长度。

图 3 ： XLC 任务的三个基于 MHE 的训练和测试流程。红色虚线框表示的部分是为了便于理解，实际中并不需要。

1.1 多头乘积（MHP）

根据推论1，输出可以分解为头部的乘积，这为使用MHP代替普通分类器来训练模型铺平了道路。
如3-a所示，在训练过程中，需要将全局标签$Y_i$分配给每个头部，进行局部损失计算。因此，我们首先对$Y_i$执行OHE，然后根据头部的长度将其重塑为$H$阶张量${\mathcal{Y}}_i^{1,...,H}$。最后，将${\mathcal{Y}}_i^{1,...,H}$分解为每个头部上的本地标签 { Y i h } h = 1 H \{Y_i^h\}_{h=1}^H {Yih​}h=1H​。由于one-hot编码$Y_i$的分解仅取决于头部的数量和顺序，因此可以递归地计算为

其中$j$和$k$为分类头的索引。
在测试期间，必须从局部预测中恢复全局预测。如图3-a所示，我们首先对每个头部执行${\mathbb{I}}_{\Lambda }$，以获得局部预测的标签。然后，通过对每个头部执行乘积并对最终输出应用Argmax来获得全局预测${\tilde{Y}}_i$。为了加快这一过程，根据定理1，我们从局部预测和后续正面的长度计算${\tilde{Y}}_i$，为
$${\tilde{Y}}_i=\sum _{k=1}^{H-1}\Lambda ({\mathbf{O}}^k)\prod _{j=k+1}^H|{\mathbf{O}}^j|+\Lambda ({\mathbf{O}}^H).(11)$$
MHP的算法伪代码见附录E-1。它可以用于许多xsl任务，如图像分类、人脸识别等。

1.2 多头级联（MHC）

对于XMLC，每个示例${\mathbf{X}}_i$对应于多个标签 Y ˉ i ∈ { 0 , 1 } C \bar{\bm{Y}}_i \in \{0,1\}^{C} Yˉi​∈{0,1}C，因此分类器的输出需要执行多热编码和Top- $K$选择，如${\tilde{Y}}_i=\text{Top-}K(\bar{\mathbf{O}})$。在XMLC中不能直接采用MHP。这是因为MHP中的每个头只预测一个标签。如果用于多标签预测，则在计算局部预测的乘积时将导致不匹配。为了解决多标签场景下MHP的不匹配问题，提出了MHC，它将多个头部级联用于模型训练和测试。

如图3-b所示，在训练过程中，MHC的标签分解过程与MHP相同。在测试期间，选择输出的顶级$K$激活。然后，通过预定义的候选集${\mathbb{C}}^1$获得该头部的局部预测，并采用该候选集表示后续头部的标签集，方便检索，减少计算量。$h$\text{-}头的最终输出${\tilde{\mathbf{O}}}^h$由嵌入的${\tilde{\mathbf{Y}}}^{h-1}$和当前输出${\mathbf{O}}^h$的乘积得到。然后，根据${\tilde{\mathbf{O}}}^h$的前$K$激活项，从${\mathbb{C}}^h$中选择${\tilde{\mathbf{Y}}}^h$。重复此过程，直到获得${\tilde{\mathbf{Y}}}^H$的标签为

其中$i_h={\prod }_{j=1}^h|{\mathbf{O}}^j|$, ${\mathbb{E}}^h$为$h$\text{-}头的嵌入层，${\mathbb{C}}_{[1,...,i_{h+1}]}^{(i_h,|{\mathbf{O}}^{h+1}|)}$为元素为$1$ ～ $i_{h+1}$，形状为$(i_h,|{\mathbf{O}}^{h+1}|)$的索引矩阵。由公式12可知，MHC是一种由粗到精的分层预测方法，它依次从前一个头部中选择Top- $K$候选标签。请注意，MHC仅依赖于Eq. 10进行标签分解，不需要HLT或标签聚类等预处理技术。MHC的算法伪代码见附录E-2。

1.3 多头采样（MHS）

对于模型预训练任务，训练完成后丢弃香草分类器，只采用模型提取的特征$\mathbf{F}$对下游任务进行微调。因此，需要训练分类器中权值的所有参数来提取更多的判别特征，但是训练权值的所有参数计算开销很大。因此，提出MHS通过选择地面真值标签所在的头部来更新模型参数。

如图3-c所示，MHS将原始分类器平均分为$H$组，使$\mathbf{O}={\sum }_h^H|{\mathbf{O}}^h|$。训练时，选择标签$Y_i$所在的头部进行模型训练，称为正头部。当然，我们也可以随机选择几个负头像一起训练模型，从而使模型具有更多的负样本信息。${\mathbf{O}}^h$的MHS正演过程可表示为
O h = O h ∪ { O j } = W h F ∪ { W j } F , ( 13 a ) Y h = Y h ∪ { 0 } = Y [ ∣ O h − 1 ∣ : ∣ O h ∣ ] ∪ { 0 } , ( 13 b ) \bm{O}^h = \bm{O}^h \cup \{\bm{O}^j\} = \mathcal{W}^h\bm{F} \cup \{\mathcal{W}^j\}\bm{F}, \qquad \quad \ \ \ \ (13a) \\ \bm{Y}^h = \bm{Y}^h \cup \{0\} = \bm{Y}[|\bm{O}^{h-1}|:|\bm{O}^{h}|] \cup \{\bm{0}\}, \qquad (13b) Oh=Oh∪{Oj}=WhF∪{Wj}F,    (13a)Yh=Yh∪{0}=Y[∣Oh−1∣:∣Oh∣]∪{0},(13b)
其中 { O j } \{\bm{O}^j\} {Oj}和 { W j } \{\mathcal{W}^j\} {Wj}分别表示负头的输出和权重集，$\cup$表示串联操作。等式13-b表示用$0$ s填充${\mathbf{Y}}^h$以对齐${\mathbf{O}}^h$的长度，其中$|{\mathbf{O}}^h|=0$表示$h=0$。

式13中的方法可以表示为MHS- $S$，其中$S$为所选头像的个数。我们的实验表明MHS- $1$（仅正样本）在模型预训练上取得了很好的效果。对于$S=2$， MHS近似或优于香草分类器。为了加快MHS的速度，在同一批次中选择含有其他样品标签的头作为阴性头。MHS的算法伪代码见附录E-3。

1.4 标签分解策略

到目前为止，我们已经介绍了三种MHE算法，其实现取决于头的数量和长度。因此，在本小节中，我们引入误差积累和混淆度的概念来衡量头部数量和长度对基于mhe的算法性能的影响。

头的数量： 带$H$头的MHE的近似过程可表示为
$$\mathbf{O}\approx {\mathbf{O}}^1\otimes {\tilde{\mathbf{O}}}^2\approx {\mathbf{O}}^1\otimes \underset{\approx {\tilde{\mathbf{O}}}^2}{\underbrace{{\mathbf{O}}^2\otimes \widetilde{{\mathbf{O}}^3}}}\approx {\mathbf{O}}^1\otimes {\mathbf{O}}^2\otimes \underset{\approx {\tilde{\mathbf{O}}}^{H-1}}{\underbrace{\cdots \otimes {\mathbf{O}}^H}}.(14)$$
如等式14所示，增加一个头部相当于又累积了一个时间误差。虽然增加头的数量会显著减少分类器的参数和计算量，但也会导致更大的累积误差。因此，在计算资源和运行速度允许的情况下，应尽量减少分类头的数量。

头的长度：混淆度是当采用MHE来近似原始标签空间时由共享组件引起的不匹配的度量。它与近似误差成正比，如下所示
$$D=\underset{\pi ({\mathbf{O}}^1,\cdots ,{\mathbf{O}}^H)}{\max }\left(\prod _{h=2}^H\frac{{\prod }_{k=h}^H|{\mathbf{O}}^k|}{|{\mathbf{O}}^{k-1}|}\right),(H\ge 2),(15)$$
其中$\pi$是正面的排列策略。希望$D$的值尽可能小。由于$\pi$依赖于具体的分解过程，我们详细分析了MHE不同算法的混淆程度。因此，

• 对于MHP，由于磁头是平行的，需要组合，因此混淆程度与磁头的排列无关。也就是说，等式15中的$max$可以在头的长度按升序排列时删除。因此，我们得出结论，MHP中每个头部的长度应尽可能一致，以最小化$D$，即$|{\mathbf{O}}^h|\approx \sqrt[H]{C}$。
• 对于MHC，由于头部是顺序级联的，我们可以选择一个更好的策略$\pi$最小化$D$。显然，当$\pi$按降序排列（$|{\mathbf{O}}^1|\ge \cdots \ge {\mathbf{O}}^H$）时，$D$是最小的。
• 对于MHS，这些多个磁头是相互关联的，需要组合（与$max$操作无关）。也就是说，我们可以选择与MHC相同的策略来最小化D。

背景动机参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 1
基础知识参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 2
算法实现参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 3
表示能力参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 4
实验结果参见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 5
无需预处理见 【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 6