Resumo Técnico: Subamostragem para Aprendizado Supervisionado em Espaços de Hilbert de Núcleos Reproduzíveis

Declaração do Problema

Na era do big data, o custo computacional e o consumo de energia associados ao treinamento de modelos de aprendizado estatístico em conjuntos de dados massivos tornaram-se gargalos críticos. Embora existam várias técnicas de redução de dados (ex: sketching, coresets, otimização estocástica), muitas são ou independentes da tarefa ou dependem de probabilidades intratáveis para uma seleção ótima. Especificamente, no aprendizado supervisionado não paramétrico onde as hipóteses residem em um Espaço de Hilbert de Núcleos Reproduzíveis (RKHS), os métodos existentes frequentemente falham em fornecer um esquema de subamostragem dependente dos dados que seja ótimo para minimizar a variância assintótica do estimador. Os métodos de kernel tipicamente escalam mal ($O(n^2)$ ou $O(nm)$) com o tamanho original do conjunto de dados $n$, e embora a subamostragem reduza isso para $O(s^2)$ (onde $s \ll n$), a subamostragem uniforme padrão ignora o valor informacional de pontos de dados individuais, levando a uma precisão de estimação subótima.

Metodologia

Os autores propõem um framework para Minimização de Risco Subamostrado (SRM) em RKHSs, utilizando um esquema de reponderação de Horvitz-Thompson para garantir a estimação não enviesada do risco empírico. A metodologia central envolve:

1. Framework Teórico:

   • Configuração: Aprendizado supervisionado não paramétrico (classificação e regressão) com uma função de perda $\ell$ convexa e duas vezes diferenciável e uma penalidade de ridge. O estimador minimiza um risco empírico regularizado.
   • Estratégias de Subamostragem: O artigo analisa duas estratégias:
     • Subamostragem Multinomial (com reposição): Pontos são extraídos independentemente com probabilidades de inclusão $\pi_{n,i}$.
     • Subamostragem de Poisson (sem reposição): Pontos são incluídos independentemente com probabilidade $s_n \pi_{n,i}$.
   • Análise Assintótica: Usando ferramentas de espaços de probabilidade funcionais e teoria de martingales, os autores estabelecem a normalidade assintótica do estimador SRM. Eles derivam o operador de covariância assintótica $\Sigma^*$, que depende das probabilidades de inclusão $\pi_{n,i}$.

2. Esquema de Subamostragem Ótimo:

   • Os autores definem L-otimalidade como a minimização do traço do operador de covariância assintótica (pré-condicionado pelo inverso da Hessiana do risco verdadeiro) $\ell$.
   • Eles derivam uma expressão de forma fechada para a função de interesse absoluto L-ótima $\psi^*$, que dita as probabilidades de inclusão ótimas:
     $$\psi^*(z) = |\ell'(h_0(x), y)| \sqrt{k(x, x)}$$
     onde $h_0$ é o verdadeiro minimizador do risco regularizado, $\ell'$ é a derivada da perda, e $k$ é o kernel.
   • Isso implica que pontos de dados com alto erro de predição (grande $|\ell'|$) ou alta autossimilaridade de kernel devem ser amostrados com maior probabilidade.

3. Implementação Prática (Estimador Piloto):

   • Como $h_0$ é desconhecido, os autores propõem uma abordagem de plug-in:
     1. Computar um estimador piloto $\hat{h}_{k_n}$ em um pequeno subconjunto dos dados ($k_n \ll s_n$).
     2. Estimar as probabilidades ótimas usando $\hat{h}_{k_n}$.
     3. Suavizar as probabilidades estimadas para garantir que satisfaçam as premissas técnicas (especificamente, que não convirjam para zero muito rapidamente) usando um hiperparâmetro $\alpha \in (0, 1]$:
        $$\tilde{\pi}_{n,i}^\alpha = (1-\alpha)\tilde{\pi}_{n,i} + \frac{\alpha}{n}$$
     4. Para subamostragem de Poisson, aplicar uma truncagem pós-hoc para garantir que as probabilidades permaneçam válidas ($\leq 1/s_n$).
   • Garantias teóricas (consistência e normalidade assintótica) são fornecidas para este estimador $\alpha$-piloto.

Principais Contribuições

• Normalidade Assintótica em RKHS: O artigo estabelece a normalidade assintótica de estimadores subamostrados em RKHSs de dimensão infinita, distinguindo-se de resultados paramétricos ao empregar técnicas de espaço de probabilidade aleatória funcional e teoria de martingales.
• Derivação de Esquema Ótimo: Fornece a primeira derivação de um esquema de subamostragem ótimo especificamente para métodos de kernel não paramétricos, mostrando que a probabilidade de inclusão ótima é proporcional à magnitude do gradiente da perda ponderada pelo diagonal do kernel.
• Comparação de Estratégias: Os autores analisam os trade-offs entre subamostragem Multinomial e de Poisson, demonstrando que a escolha ótima depende da razão limite $c = \lim s_n/n$. Notavelmente, devido à presença de regularização de ridge, as duas estratégias não possuem eficiências assintóticas idênticas quando $c=0$, divergindo de achados em configurações paramétricas.
• Algoritmo Prático Robusto: A proposta de um algoritmo "piloto" de dois estágios que combina um estimador piloto com suavização e truncagem torna o esquema teoricamente ótimo implementável na prática, mantendo garantias estatísticas.

Resultados

Experimentos numéricos foram conduzidos em conjuntos de dados sintéticos (classificação e regressão) e um conjunto de dados do mundo real (UCI Covertype), comparando o SRM $\alpha$-piloto proposto contra:

• Subamostragem uniforme (baseline).
• Método Nyström.
• Random Fourier Features (RFF).
• Kernel sketching.

Achados:

• Parâmetro de Suavização: Um parâmetro de suavização $\alpha$ entre 0,1 e 0,4 produz o melhor erro de generalização, equilibrando os benefícios da subamostragem ótima com a estabilidade da amostragem uniforme.
• Regime de Grandes Dados: Para grandes conjuntos de dados, o SRM proposto supera significativamente a subamostragem uniforme em termos do trade-off entre erro de generalização e tempo de computação (CPU).
• Comparação com Aproximações: No conjunto de dados real Covertype, o método SRM foi mais eficiente que Nyström, RFF e sketching. Em tarefas sintéticas de baixa dimensão, as aproximações de kernel (Nyström, RFF) foram mais rápidas, sugerindo que subamostragem e aproximação de kernel são técnicas complementares.
• Abordagem Híbrida: Combinar subamostragem com o método Nyström melhorou ainda mais o desempenho, indicando a compatibilidade do método com técnicas existentes de aproximação de kernel.

Significância e Alegações

O artigo afirma fornecer um método teoricamente fundamentado e praticamente viável para reduzir a carga computacional do aprendizado baseado em kernel sem sacrificar a eficiência estatística. Ao derivar um esquema de subamostragem ótimo baseado no traço da covariância assintótica, os autores oferecem uma maneira de extrair indivíduos "informativos" de grandes conjuntos de dados.

Os autores enquadram seu trabalho de forma modesta como um passo em direção a um aprendizado mais eficiente energeticamente, observando que, embora o método reduza o tamanho do problema de otimização de $O(n^2)$ para $O(s^2)$, ele depende de um estimador piloto. Eles reconhecem que a teoria é atualmente baseada em riscos regularizados e que estender para configurações não regularizadas ou desenvolver procedimentos online de múltiplos estágios são direções potenciais para pesquisas futuras. O trabalho se distingue ao abordar os desafios específicos da configuração não paramétrica de RKHS, que as teorias de subamostragem paramétrica existentes não cobrem totalmente.