Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

Resumo Técnico: Núcleos de Bernstein–Schur via Modulação Esboçada e Randomização Radial

1. Enunciado do Problema

Métodos de núcleo (ex: SVMs, Regressão de Ridge de Núcleo, Processos Gaussianos e camadas de atenção de Transformers) dependem da matriz Gram $N \times N$ $K_{ij} = k(x_i, x_j)$. Escalar esses métodos para grandes conjuntos de dados ($N > 10^5$) é dificultado pelos custos de armazenamento $O(N^2)$ e de fatoração $O(N^3)$. Mapas de características aleatórias (random feature maps), que aproximam $k(x, w) \approx z(x)^\top z(w)$ com um $z$ de baixa dimensão, oferecem uma alternativa $O(NM)$.

No entanto, as construções de características aleatórias existentes são estruturalmente limitadas:

• Características de Fourier Aleatórias (RFF) aplicam-se a núcleos invariantes por translação via teorema de Bochner.
• Esboços Polinomiais (ex: TensorSketch) aplicam-se a núcleos de produto escalar.
• Métodos Nyström dependem de decaimento espectral rápido e são dependentes dos dados.

O artigo aborda o núcleo $\mathcal{T}$-enviesado:
$$k_{\mathcal{T},b}(w, x) = \frac{(w^\top x + b)^2}{\|w - x\|^2 + \varepsilon}, \quad b \ge 0, \varepsilon > 0$$
Este núcleo acopla alinhamento (produto escalar ao quadrado no numerador) e proximidade (inverso da distância ao quadrado no denominador). Crucialmente, ele não é nem invariante por translação, nem um núcleo de produto escalar (exceto na esfera unitária, onde a distância e o produto escalar são bijetivos). Consequentemente, RFF padrão e esboço polinomial não podem ser aplicados diretamente ao núcleo completo, forçando o retorno à intratável matriz Gram $O(N^2)$ para o cálculo exato.

2. Metodologia: Características Aleatórias de Bernstein–Schur

Os autores propõem o RAY (Random Approximation of the $\mathcal{T}$-kernel), uma construção de característica aleatória para uma classe mais ampla de núcleos de Bernstein–Schur. Estes são definidos como o produto de Schur (produto elemento a elemento) de um núcleo de características finitas e um núcleo invariante por translação completamente monótona.

A metodologia decompõe o núcleo $\mathcal{T}$ em dois fatores tratáveis:

1. Modulação Polinomial: $p_b(w, x) = (w^\top x + b)^2$. Este possui um mapa de características finito e exato $p_b(x) \in \mathbb{R}^{d^2+d+1}$.
2. Fator Radial: $h_\varepsilon(w, x) = (\|w - x\|^2 + \varepsilon)^{-1}$. Este é completamente monótono em $\|w-x\|^2$ e admite uma representação de Bernstein–Widder como uma mistura de núcleos Gaussianos sobre um único parâmetro de escala $t \sim \text{Exp}(\varepsilon)$.

As Etapas de Construção:

1. Fatoração: Expressar $k_{\mathcal{T},b} = p_b \cdot h_\varepsilon$.
2. Amostragem Radial: Amostrar o parâmetro de escala $t_j \sim \text{Exp}(\varepsilon)$.
3. RFF Gaussiana: Para cada $t_j$, aplicar Características de Fourier Aleatórias ao núcleo Gaussiano resultante $e^{-t_j \|x-w\|^2}$.
4. Esboço de Modulação: Em vez de usar a característica polinomial exata $O(d^2)$ $p_b(x)$, aplicar um TensorSketch (grau-2) para comprimir a modulação em dimensão $m$.
5. Produto Tensorial: O mapa de características final $z(x)$ é a concatenação do produto tensorial da modulação esboçada e das RFFs radiais.

A dimensão de característica resultante é $D \times m$, onde $D$ é o número de extrações radiais e $m$ é o tamanho do esboço. Esta dimensão é isenta do piso $O(d^2)$ associado à característica polinomial exata.

3. Principais Contribuições

O artigo apresenta as seguintes contribuições teóricas e empíricas:

• Uma Nova Classe de Núcleos (Bernstein–Schur): Os autores definem uma classe de núcleos formados pelo produto de um núcleo de características finitas e um núcleo radial completamente monótona. Eles fornecem um estimador de característica aleatória unificado para toda esta classe, não apenas para o núcleo $\mathcal{T}$.
• Análise de Viés e Variância:
  • Provou que o estimador é não viesado ($E[z(x)^\top z(w)] = k(x, w)$).
  • Derivou uma fórmula de variância exata para o estimador "plano" (uma frequência por escala), mostrando que ela escala com $(R^2 + b)^4 / (D\varepsilon^2)$.
  • Provou que usar uma frequência por escala ($D'=1$) é otimizado em termos de variância dentro do orçamento hierárquico.
• Garantias de Norma de Operador:
  • Estabeleceu um limite de norma de operador de Bernstein-matriz esperado para a aproximação da matriz Gram. Diferente dos limites brutos por elemento que escalam com $N$, este limite depende da dimensão intrínseca e dos autovalores superiores das matrizes Gram do núcleo e da modulação.
  • Provou a estabilidade espectral relativa determinística para Regressão de Ridge de Núcleo (KRR) sob esta aproximação.
• Estimador Duplamente Randomizado (RAY):
  • Introduziu o esboço da fator de modulação. A análise teórica mostra que condicionar no esboço preserva a garantia de norma de operador de dimensão intrínseca, adicionando apenas um termo de erro aditivo ajustável controlado pelo tamanho do esboço $m$.
  • Demonstrou que esta abordagem remove a barreira da dimensão de característica $O(d^2)$, tornando o método escalável para altas dimensões.
• Decomposição de Erro: Forneceu uma decomposição de erro de modulação–radial mostrando que o ruído radial é modulado pelo fator de alinhamento, enquanto o erro de modulação é localizado pela proximidade radial. Isso explica por que o produto permanece eficaz mesmo quando a modulação é comprimida.

4. Resultados Experimentais

Os experimentos foram conduzidos principalmente em regimes fora da esfera (esferas limitadas com normas variadas), onde o núcleo $\mathcal{T}$ é genuinamente um núcleo de não-produto escalar.

• Desempenho Fora da Esfera: Em uma bola limitada com normas variadas, o RAY mantém uma taxa de convergência de $O(1/\sqrt{D})$ independentemente da dimensão $d$. Em contraste, os métodos Nyström uniformes e k-means degradam significativamente conforme $d$ aumenta, mesmo com contagens de marcos (landmarks) correspondentes.
• Comparação de Custo Equivalente: Quando comparado em custos de representação equivalentes, métodos Nyström adaptativos (que são dependentes de dados) podem ser mais precisos que o RAY em $N$ moderados. No entanto, o RAY oferece características não dependentes de dados, não viesadas e em streaming, o que o Nyström não pode oferecer.
• Preferência de Alvo Acoplado: Em testes controlados com alvos sintéticos exigindo tanto alinhamento quanto proximidade, o núcleo $\mathcal{T}$ (aproximado pelo RAY) superou núcleos que modelam apenas um fator (Gaussian, IMQ ou Polinomial isoladamente). Isso valida o viés indutivo do núcleo.
• Atenção de Tempo Linear: O RAY foi aplicado como uma primitiva de atenção de tempo linear. Ele aproximou com sucesso a $\mathcal{T}$-atenção exata, com o erro mediano diminuindo conforme a dimensão de característica $M$ aumentava, mantendo memória $O(NM)$ e permitindo decodificação causal e em streaming (impossível para métodos baseados em landmarks).
• Treinamento de Larga Escala: No dataset HIGGS (11 milhões de exemplos), o RAY permitiu o treinamento primal em um cenário de streaming onde a matriz Gram é impossível de armazenar, superando os limites de modulação exata com orçamentos equivalentes.

5. Significância e Alegações

O artigo alega significância em três áreas principais:

1. Preenchimento de Lacunas Estruturais: Fornece a primeira construção de características aleatórias para núcleos que não são nem invariantes por translação nem de produto escalar, fatorando-os em componentes que são passíveis de aplicação de ferramentas padrão (esboço e RFF).
2. Escalabilidade sem Dependência de Dados: Oferece uma alternativa em streaming e independente de dados para métodos Nyström para núcleos não estacionários, evitando simultaneamente a matriz Gram $O(N^2)$ e a barreira da dimensão de característica $O(d^2)$.
3. Rigor Teórico: A análise vai além de simples limites por elemento para fornecer garantias de norma de operador controladas pelas dimensões intrínsecas, oferecendo uma compreensão mais matizada do erro de aproximação para núcleos estruturados.

Os autores observam modestamente que, embora o RAY seja altamente eficaz para configurações de streaming e larga escala, métodos Nyström adaptativos ainda podem ser superiores para problemas de $N$ moderado e orçamento fixo, onde a dependência de dados é aceitável. O método requer entradas de norma limitada para garantir estabilidade, e a constante de variância é maior do que a do RFF padrão devido ao fator polinomial.