【顶刊TPAMI 2025】多头编码（MHE）之极限分类 Part 4：MHE表示能力

论文：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的表示能力

正如推论1所证明的那样，MHE的本质是一种通过多个一阶头的乘积逼近高阶极值标签的低秩逼近方法。
因此：MHE在分类问题中是否保证足够健壮的性能？

为了回答上述问题，我们将MHE推广到更一般的低秩近似问题，从Frobenius-norm度量扩展到交叉熵。如图4-a所示，如果有$G$组具有MHE的多头，每组多头形成一个$H$阶张量。然后，将所有这些张量相加，得到最终的输出
$$\begin{gathered} {\mathbb{I}}_{Y_i}\approx \sigma (\tilde{\mathbf{O}})=\sigma (\sum _g^G{\mathbf{O}}_g^1\otimes {\mathbf{O}}_g^2\otimes \cdots \otimes {\mathbf{O}}_g^H)(16a) \\ =\sigma (\sum _g^G({\mathcal{W}}_g^{1}F)\otimes ({\mathcal{W}}_g^{2}F)\otimes \cdots \otimes ({\mathcal{W}}_g^{G}F)),(16b) \end{gathered}$$其中$g$为组的索引。实际上，等式\ref{eq9_}是张量的CP分解，$G$是张量的秩。这将张量分解成一个分量秩一张量的和。从理论上讲，其他张量分解方法也可以用来近似$\mathbf{O}$，当它被视为一个矢量化的高阶张量。

分类器的低秩逼近能力。(a)使用MHE的$G$组多头分类器（G-MHE）。(b)在原点分类器上增加瓶颈层，实现$\mathcal{W}$的低秩特性。

2 基于Frobenius-范数的低秩逼近

等式16说明了输出$\tilde{\mathbf{O}}$的低秩近似本质上是为了限制其权重的秩。因此，我们研究低秩权重对分类器性能的影响。为了约束$\mathcal{W}$的rank，在特征层$\mathbf{F}$和输出层$\mathbf{O}$之间增加一个线性瓶颈层${\mathbf{O}}_b$，如图4-b所示。设$\mathbf{F}$和${\mathbf{O}}_b$之间的权值为${\mathcal{W}}_1$, ${\mathbf{O}}_b$和$\mathbf{O}$之间的权值为${\mathcal{W}}_2$，有
$$\begin{gathered} \mathbf{O}={\mathcal{W}}_2{\mathcal{W}}_1\mathbf{F}+\mathbf{B}=\tilde{\mathcal{W}}\mathbf{F}+\mathbf{B},（17） \\ s.t.R(\tilde{\mathcal{W}})=r\le min(|\mathbf{F}|,|{\mathbf{O}}_b|), \end{gathered}$$其中$\tilde{\mathcal{W}}={\mathcal{W}}_2{\mathcal{W}}_1$, $R(\cdot )$是矩阵的秩。如果$\tilde{\mathcal{W}}$被frobenius范数损失优化，有
$$minL=\frac{1}{2}||{\mathbb{I}}_{Y_i}-\mathbf{O}|{|}_F^2=||{\mathbb{I}}_{Y_i}-\tilde{\mathcal{W}}\mathbf{F}|{|}_F^2.(18)$$等式18是一个低秩近似问题，它使${\mathbb{I}}_{Y_i}$和$\mathbf{O}$的所有元素尽可能接近。它产生了一个低秩近似$\underset{R(\tilde{\mathcal{W}})\le r}{\mathrm{Argmin}}||\mathcal{W}-\tilde{\mathcal{W}}|{|}_F^2$。更进一步，我们有了下面的定理。

Theorem 2: 假设$\mathcal{F}$为满行秩，用frobenius范数作为损失函数对式17中的线性神经网络进行训练，不会产生虚假的局部极小值，并且每个退化的鞍点$\mathcal{W}$要么是全局极小值，要么是二阶鞍点。

定理2的证明在附录B中给出。该定理说明方程17的任何局部最优解${\tilde{\mathcal{W}}}^{\ast }$都是全局最优解，即通过任意${\tilde{\mathcal{W}}}^{\ast }$都可以得到${\mathbb{I}}_{Y_i}$的最优逼近。值得注意的是，定理2中指定的完整行秩条件在XLC任务中很容易得到满足。这是因为特征的长度比类别的数量要小得多，例如$|\mathcal{F}{\mathcal{F}}^T|=|\mathcal{F}|,s.t.|F|\ll C$。

3 基于CE的低秩近似

更进一步，如果用softmax将等式17中低秩近似的损失从Frobenius-范数推广到交叉熵（CE），我们将得到一个更好的${\mathbb{I}}_{Y_i}$近似。这是因为方程\ref{eq10_}中的frobenius -范数度量对于分类问题过于严格，即Frobenius -范数损失倾向于近似所有元素，而CE损失倾向于选择最大的元素。因此，需要将等式17中的低秩近似推广到CE损失，CE损失是分类问题中常用但研究较少的方法。

与等式17中使用的Frobenius -范数不同，对输出的非线性操作会影响其表示能力。这是因为Softmax（训练）和不可微Argmax（测试）可以近似为
$$\Lambda ({\mathbf{O}}_i)=\underset{ϵ\to 0}{\lim }\Lambda ({\sigma }_{ϵ}({\mathbf{O}}_i))=\underset{ϵ\to 0}{\lim }\Lambda \left(\frac{e^{\frac{{\mathbf{O}}_i}{ϵ}}}{{\sum }_j{e}^{\frac{{\mathbf{O}}_i}{ϵ}}}\right),(19)$$其中$ϵ$为Softmax的温度。由公式19可知，测试中使用的Argmax操作实际上与训练中使用的Softmax和CE操作是一致的。即Eq. 19相当于CE和Softmax， Softmax使元素之间的间隙变大，CE选择最大的元素。因此，我们将低秩近似问题从Frobenius -范数损失推广到CE损失。

Theorem 3: 当$\mathcal{F}$可分离时，使用CE以softmax作为损失函数训练方程17中的两层线性网络，只要满足$R([\genfrac{}{}{0ex}{}{\tilde{\mathcal{W}}}{\mathbf{B}}])>1$，就可以恢复与vanilla分类器$\mathcal{O}=\mathcal{W}\mathcal{F}$相同的精度。

定理3的证明在附录C中给出。定理\ref{th3}表明，当偏差$\mathbf{B}$存在时，$R(\tilde{\mathcal{W}})$的最小值可以等于$1$，这意味着OHE和MHE之间的性能差距相当小。同时，定理3也说明了当深度神经网络对数据进行过拟合时，其泛化与标签的语义信息无关。这意味着标签预处理技术，如HLT和标签聚类，是不必要的，因为低秩近似仍然独立于标签定位。

为了验证这个定理，我们生成$N\times N$高斯随机样本，其中$N=100$和$|{\mathbf{O}}_b|=1$。如图5-a所示，训练精度和$R(\sigma (\mathbf{O}))$不随时代的增加而增加。然而，在图5-b中，$R(\sigma (\mathbf{O}))$与训练精度呈正相关，并且随着epoch的增加接近$100\%$。然后，为了验证Softmax对CE的选择性，我们使用ResNet-18 在CIFAR-100 上进行了实验，并将$|{\mathbf{O}}_b|$设置为不同的长度。结果如图5-c所示。我们发现，当$|{\mathbf{O}}_b|$设置适当时，可以很好地保证模型的测试精度。实验部分进一步证实了这一说法。

图5：不同损失函数和$R(\tilde{W})$的实验。（a, b）两层线性网络在高斯分布随机样本上的性能。 (c ) ResNet-18在CIFAR-100数据集上的性能。

此外，当使用CE和Softmax对方程17中的模型进行训练时，低秩矩阵$\tilde{\mathcal{W}}$的逼近误差可以通过以下定理进行分析。

Theorem 4: 设${\mathcal{W}}^{\ast }$为方程17中模型的局部最小值，和$\Delta =\tilde{\mathcal{W}}-{\mathcal{W}}^{\ast }$，使用CE和softmax作为损失函数训练方程17中的双层线性网络，有
$$E\le \sum _j^C|e^{{\Delta }_j}-1|,(20)$$其中$E$是$\sigma (\mathcal{O})$到$\sigma ({\mathcal{O}}^{\ast })$的近似误差。

定理4的证明在附录D中给出。定理4表明，近似误差$E$与类数$C$和$\tilde{\mathcal{W}}$的秩有关。它说明了一个重要的结论：当${\Delta }_j>0$, $E$呈指数下降时，当${\Delta }_j\to 0$, $E$呈线性下降时。这与深度学习方法一致，在训练开始时损失急剧下降。

背景动机参见 【顶刊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