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

Resumo Técnico: Sobre a Estrutura Espectral e Equivalência Objetiva de Discriminantes de Fisher Multirrotulados Ortogonais

Enunciação do Problema
A Análise Discriminante Linear (LDA) é uma técnica fundamental para redução de dimensão supervisionada, tradicionalmente formulada para classificação de rótulo único. No cenário de rótulo único, o posto da matriz de dispersão entre classes $S_b$ é limitado por $C-1$ (onde $C$ é o número de classes), e os autovetores padrão são $S_w$-conjugados, mas não necessariamente ortogonais no sentido euclidiano. Duas extensões distintas evoluíram independentemente: LDA Ortogonal (que impõe ortogonalidade euclidiana via restrições de Stiefel) e LDA Multirrotulada (que redefine as matrizes de dispersão para lidar com amostras com múltiplos rótulos simultâneos).

Este artigo aborda a lacuna teórica na análise da combinação dessas duas extensões: Análise Discriminante Linear com matrizes de dispersão multirrotuladas simultâneas e restrições de ortogonalidade de Stiefel. Especificamente, investiga-se a formulação:
$$\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)}$$
onde $\text{St}(d,r)$ é a variedade de Stiefel ($W^\top W = I_r$). Os autores observam que, embora existam métodos anteriores (por exemplo, kaLDA, MDDM, frameworks de regressão), nenhum fornece uma análise unificada da estrutura algébrica (posto, equivalência objetiva) ou garantias estatísticas (taxas de amostra finita, optimalidade minimax) para esta formulação específica de razão de Fisher sob condições multirrotuladas.

Metodologia e Framework
Os autores estabelecem um framework teórico unificado baseado em um modelo linear de efeito de rótulo, onde as características são geradas como $x_i = \mu + \sum_{\ell} y_{i\ell}\alpha_\ell + \epsilon_i$. Os componentes metodológicos chave incluem:

1. Análise Algébrica: O artigo deriva o posto da matriz de dispersão entre classes multirrotulada $S_b^{\text{ML}}$ usando uma fatoração matricial $S_b^{\text{ML}} = MM^\top$, onde $M = \tilde{X}^\top Y D_n^{-1/2}$. Isso permite uma caracterização precisa da dimensionalidade discriminante efetiva.
2. Particionamento de Variância: É estabelecida uma identidade de particionamento de variância multirrotulada, mostrando que a dispersão total $S_t^{\text{ML}}$ é uma versão ponderada pela cardinalidade da dispersão total padrão, onde cada amostra contribui $k_i$ vezes (onde $k_i$ é o número de rótulos).
3. Equivalência Objetiva: Os autores analisam os quatro objetivos padrão de Fisher (Razão de Rastros, Rastros de Razão, Razão de Determinantes, Diferença de Rastros) sob duas restrições: ortogonalidade $S_t^{\text{ML}}$ ($W^\top S_t^{\text{ML}} W = I$) e ortogonalidade de Stiefel ($W^\top W = I$).
4. Garantias Estatísticas: Sob suposições de ruído sub-Gaussiano, o artigo emprega desigualdades de concentração matricial (Bernstein Matricial, Hanson–Wright) e teoria de perturbação (teorema $\sin \Theta$ de Davis–Kahan) para derivar limites de amostra finita sobre o erro de estimação de subespaço. Estabelece-se ainda limites inferiores minimax usando a desigualdade de Fano e argumentos de empacotamento em Grassmanniana.

Contribuições e Resultados Chave

• Caracterização de Posto: O artigo prova que $\text{posto}(S_b^{\text{ML}}) = \text{posto}(\tilde{X}^\top Y) \le \min(d, n-1, \text{posto}(Y))$. Crucialmente, ao contrário do limite de rótulo único de $C-1$, o cenário multirrotulado pode alcançar um posto de $L$ (o número de rótulos) se a estrutura de co-ocorrência de rótulos permitir (isto é, se o vetor de todos os uns não estiver no espaço coluna de $Y$). Isso implica que o cenário multirrotulado pode fornecer direções discriminantes estritamente maiores do que o caso de rótulo único.
• Equivalência e Divergência Objetiva:
  • Sob a restrição de ortogonalidade $S_t^{\text{ML}}$, todos os quatro objetivos de Fisher são provados ser equivalentes, compartilhando a mesma solução ótima (os principais autovetores generalizados de $(S_b^{\text{ML}}, S_t^{\text{ML}})$).
  • Sob a restrição de Stiefel ($W^\top W = I$), a equivalência não é garantida. O artigo identifica que a divergência surge das cardinalidades variáveis de rótulos ($k_i$) e da não comutatividade de $S_b^{\text{ML}}$ e a dispersão total $S_t$. O objetivo de diferença de rastros é mostrado como uma perturbação do caso de rótulo único, com o erro limitado pela norma espectral do resíduo $R = S_t^{\text{ML}} - S_t$.
• Preservação de Distância de Rótulos: É estabelecido um limite determinístico bilateral relacionando a distância projetada quadrática esperada entre amostras à distância de Hamming entre seus vetores de rótulos. A restrição de ortogonalidade é mostrada como controlando o termo de ruído neste limite, fornecendo uma base teórica para o uso de características projetadas em classificação multirrotulada baseada em distância.
• Garantias Estatísticas:
  • Limites de Amostra Finita: O artigo deriva um limite superior sobre o erro de estimação de subespaço de $O(k_{\max} \sqrt{d \log d / n} / \text{gap}_r)$, onde $k_{\max}$ é a cardinalidade máxima de rótulos. Isso destaca que a estimação multirrotulada é mais intensiva em amostras devido ao reponderamento das matrizes de dispersão.
  • Optimalidade Minimax: É estabelecido um limite inferior correspondente de $\Omega(\sigma^2 d / (n \cdot \text{gap}_r))$. Os autores observam que, embora as taxas coincidam em $n$ e $d$, o fator $k_{\max}$ no limite superior permanece uma questão em aberto quanto à sua precisão.
  • Robustez e Regularização: O framework é mostrado como robusto a interações de rótulos em pares, e a regularização de Tikhonov é provada como preservando a estrutura espectral e propriedades de posto em regimes de alta dimensão ($d \gg n$).

Significância e Alegações
O artigo alega preencher uma lacuna teórica específica ao fornecer a primeira análise unificada de discriminantes de Fisher multirrotulados ortogonais. Sua significância reside em:

1. Insight Algébrico: Demonstrar que o cenário multirrotulado altera fundamentalmente as propriedades de posto da LDA, potencialmente gerando subespaços discriminantes de dimensão superior aos anteriormente compreendidos.
2. Clarificação Objetiva: Resolver as condições sob as quais diferentes objetivos de Fisher são equivalentes ou divergentes no contexto multirrotulado, distinguindo especificamente entre ortogonalidade $S_t$ e restrições de Stiefel.
3. Rigor Estatístico: Estabelecer taxas quase minimax ótimas para estimação de subespaço em cenários multirrotulados, quantificando explicitamente o custo da cardinalidade de rótulos ($k_{\max}$) na dificuldade de estimação.

Os autores enfatizam que seus resultados são verificados numericamente em dados sintéticos gerados a partir do modelo linear de efeito de rótulo para servir como um "teste de sanidade" para os teoremas. Eles afirmam explicitamente que a avaliação em conjuntos de dados multirrotulados do mundo real é adiada para trabalhos futuros voltados a venues orientados a aplicações, mantendo um escopo modesto focado em fundamentos teóricos em vez de benchmarking empírico.