On the Spectral Structure and Objective Equivalence of Orthogonal Multilabel Fisher Discriminants

技术摘要：关于正交多标签 Fisher 判别分析的谱结构与目标等价性

问题陈述
线性判别分析（LDA）是监督降维的基础技术，传统上 formulated 用于单标签分类。在单标签设定中，类间散度矩阵 $S_b$ 的秩受限于 $C-1$（其中 $C$ 为类别数），且标准特征向量是 $S_w$-共轭的，但不一定是欧几里得正交的。两种不同的扩展已独立发展：正交 LDA（通过 Stiefel 约束强制欧几里得正交性）和多标签 LDA（重新定义散度矩阵以处理具有多个同时标签的样本）。

本文探讨了将这两种扩展相结合的理论空白：即具有同时多标签散度矩阵和 Stiefel 正交约束的线性判别分析。具体而言，它研究了如下公式：
$$\max_{W \in \text{St}(d,r)} \frac{\text{tr}(W^\top S_b^{\text{ML}} W)}{\text{tr}(W^\top S_w^{\text{ML}} W)}$$
其中 $\text{St}(d,r)$ 是 Stiefel 流形（$W^\top W = I_r$）。作者指出，虽然已有先前的方法（例如 kaLDA、MDDM、回归框架），但没有任何方法针对多标签条件下的这种特定 Fisher 比率公式提供代数结构（秩、目标等价性）的统一分析，或统计保证（有限样本速率、极小极大最优性）。

方法论与框架
作者建立了一个基于线性标签效应模型的统一理论框架，其中特征生成形式为 $x_i = \mu + \sum_{\ell} y_{i\ell}\alpha_\ell + \epsilon_i$。关键的方法论组成部分包括：

1. 代数分析：本文利用矩阵分解 $S_b^{\text{ML}} = MM^\top$（其中 $M = \tilde{X}^\top Y D_n^{-1/2}$）推导了多标签类间散度矩阵 $S_b^{\text{ML}}$ 的秩。这使得能够精确表征有效判别维数。
2. 方差划分：建立了一个多标签方差划分恒等式，表明总散度 $S_t^{\text{ML}}$ 是标准总散度的基数加权版本，其中每个样本贡献 $k_i$ 次（$k_i$ 为标签数量）。
3. 目标等价性：作者在两种约束下分析了四种标准 Fisher 目标（迹比率、比率迹、行列式比率、迹差）：$S_t^{\text{ML}}$-正交性（$W^\top S_t^{\text{ML}} W = I$）和 Stiefel 正交性（$W^\top W = I$）。
4. 统计保证：在次高斯噪声假设下，本文利用矩阵集中不等式（矩阵 Bernstein、Hanson–Wright）和摄动理论（Davis–Kahan $\sin \Theta$ 定理）推导了子空间估计误差的有限样本界。此外，利用 Fano 不等式和 Grassmannian 打包论证建立了极小极大下界。

主要贡献与结果

• 秩表征：本文证明了 $\text{rank}(S_b^{\text{ML}}) = \text{rank}(\tilde{X}^\top Y) \le \min(d, n-1, \text{rank}(Y))$。至关重要的是，不同于 $C-1$ 的单标签界限，如果标签共现结构允许（即全 1 向量不在 $Y$ 的列空间中），多标签设定可以达到 $L$（标签数量）的秩。这意味着多标签设定可以提供比单标签情况严格更多的判别方向。
• 目标等价性与发散：
  • 在 $S_t^{\text{ML}}$-正交性约束下，所有四种 Fisher 目标被证明是等价的，共享相同的最优解（$(S_b^{\text{ML}}, S_t^{\text{ML}})$ 的前 $r$ 个广义特征向量）。
  • 在 Stiefel 约束（$W^\top W = I$）下，等价性无法保证。本文指出，发散源于变量标签基数（$k_i$）以及 $S_b^{\text{ML}}$ 与总散度 $S_t$ 的非交换性。迹差目标被证明是单标签情况的摄动，其误差由残差 $R = S_t^{\text{ML}} - S_t$ 的谱范数界定。
• 标签距离保持：建立了一个确定性双边界，将样本间的期望平方投影距离与其标签向量间的汉明距离联系起来。正交性约束被证明控制了该界中的噪声项，为在基于距离的多标签分类中使用投影特征提供了理论基础。
• 统计保证：
  • 有限样本界：本文推导了子空间估计误差的上界，为 $O(k_{\max} \sqrt{d \log d / n} / \text{gap}_r)$，其中 $k_{\max}$ 是最大标签基数。这突显了由于散度矩阵的重新加权，多标签估计需要更多的样本。
  • 极小极大最优性：建立了匹配的 $\Omega(\sigma^2 d / (n \cdot \text{gap}_r))$ 下界。作者指出，虽然速率在 $n$ 和 $d$ 上匹配，但上界中的 $k_{\max}$ 因子关于其紧致性仍是一个未决问题。
  • 鲁棒性与正则化：该框架被证明对成对标签交互具有鲁棒性，并且证明了 Tikhonov 正则化在高维情形（$d \gg n$）下保留了谱结构和秩属性。

意义与主张
本文声称通过提供正交多标签 Fisher 判别分析的首次统一分析，填补了特定的理论空白。其意义在于：

1. 代数洞察：证明多标签设定从根本上改变了 LDA 的秩属性，可能产生比先前理解的更高维的判别子空间。
2. 目标澄清：解决了多标签背景下不同 Fisher 目标等价或发散的条件，特别是区分了 $S_t$-正交性和 Stiefel 约束。
3. 统计严谨性：建立了多标签设定中子空间估计的近极小极大最优速率，明确量化了标签基数（$k_{\max}$）对估计难度的成本。

作者强调，其结果是在基于线性标签效应模型生成的合成数据上通过数值验证的，旨在作为定理的“合理性检查”。他们明确表示，在真实世界多标签数据集上的评估将推迟到未来针对应用型场所的工作，保持适度的范围，专注于理论基础而非经验基准测试。