A scalable version of MADD for big-data classification

Resumo Técnico: Uma Versão Escalável de MADD para Classificação de Big-Data

Definição do Problema
Classificadores baseados em distância, particularmente aqueles que dependem da distância euclidiana, são fundamentais para o aprendizado de máquina moderno. No entanto, em cenários de alta dimensionalidade e baixa amostragem (HDLSS), a distância euclidiana sofre de "concentração de distância", onde as distâncias entre pontos da mesma classe tornam-se maiores do que as distâncias entre pontos de classes diferentes. Isso viola as estruturas de vizinhança e leva ao surgimento de "hubs", degradando severamente o desempenho do classificador.

Para abordar isso, Pal et al. (2016) introduziram a Diferença de Distância Absoluta da Média (MADD), uma semimétrica orientada por dados que contorna com sucesso esses problemas de alta dimensão ao manter estruturas de vizinhança corretas baseadas em diferenças de localização e escala. Apesar de suas vantagens teóricas, a MADD enfrenta um gargalo crítico: sua complexidade computacional. Calcular a MADD entre dois pontos requer $O(nd)$ operações (onde $n$ é o tamanho da amostra de treinamento e $d$ é a dimensionalidade), e classificar um único ponto de teste via uma abordagem de Vizinho Mais Próximo (NN) requer $O(n^2d)$ operações. Como demonstrado no artigo, essa escala quadrática torna a MADD computacionalmente proibitiva para grandes conjuntos de dados com $n$ elevado, mesmo em hardware moderno.

Metodologia
Os autores propõem uma versão escalável da MADD, denominada MADDsc, que reduz significativamente a complexidade computacional enquanto retém as vantagens estatísticas da métrica original. A metodologia consiste em três componentes principais:

1. Seleção de Conjunto Representativo via Processos de Ponto Determinantal (DPP):
   Em vez de calcular distâncias contra todo o conjunto de treinamento, a MADDsc redefine a métrica usando um subconjunto pequeno e representativo de observações, $X^* \subset X$. Os autores argumentam que as propriedades de separação teórica da MADD são preservadas se o conjunto representativo capturar a diversidade dos dados originais.

   • Para selecionar este conjunto, os autores utilizam Processos de Ponto Determinantal (DPP). Ao contrário da amostragem aleatória simples, que pode perder estruturas intrínsecas dos dados (especialmente em distribuições multimodais), os DPPs introduzem um efeito de "repulsão". Ao construir uma matriz de similaridade $L$ usando um kernel radial gaussiano, os DPPs selecionam um subconjunto de pontos que são diversos e espalhados pelo nuvem de dados, garantindo que o conjunto representativo capture o panorama da amostra de treinamento completa.
   • O custo computacional é reduzido de $O(n^2d)$ para $O(knd)$, onde $k$ é o tamanho do conjunto representativo ($k \ll n$).

2. Validação Cruzada Incremental para Seleção de Hiperparâmetro:
   O tamanho do conjunto representativo ($k$) é um hiperparâmetro crucial. A validação cruzada padrão exigiria a seleção repetida de amostras de DPP e o recálculo de distâncias para cada dobra (fold) e candidato a $k$, anulando os ganhos de velocidade.

   • Os autores propõem uma técnica de validação cruzada incremental. Ao modificar o algoritmo de amostragem de DPP para garantir que os subconjuntos selecionados sejam aninhados (ou seja, $X^*(k_t) \subseteq X^*(k_{t+1})$), os valores de MADDsc podem ser computados incrementalmente. Isso permite que o algoritmo atualize a métrica à medida que $k$ aumenta sem recomputar toda a matriz de distância, reduzindo drasticamente o overhead computacional da seleção de modelo.

3. Características de Fourier Aleatórias (RFF) para Grandes Conjuntos de Dados:
   Para conjuntos de dados extremamente grandes onde até a construção da matriz de similaridade $n \times n$ para o DPP é inviável (devido a custos de memória ou decomposição de autovalores), os autores integram Características de Fourier Aleatórias (RFF).

   • Baseado no teorema de Bochner, o kernel gaussiano é aproximado via uma expectativa de Monte Carlo. A matriz de similaridade $L$ é aproximada por $R R^T$, onde $R$ é uma matriz de mapeamento de características de baixa dimensão ($n \times 2D$).
   • Isso permite que a decomposição de autovalores necessária para a amostragem de DPP seja realizada em uma matriz muito menor de $2D \times 2D$ (ou via SVD de $R$), reduzindo tanto o tempo quanto a complexidade de memória. Esta abordagem é formalizada como NN-MADDsc com RFF.

O framework também é estendido para gMADDsc, uma versão escalável da MADD generalizada (gMADD), que lida com casos onde as populações diferem além dos dois primeiros momentos (localização e escala).

Resultados Principais
Estudos de simulação extensos e análises de dados reais em conjuntos de dados de Séries Temporais UCR demonstram a eficácia dos métodos propostos:

• Desempenho vs. MADD Original: Em simulações através de várias distribuições (localização, escala, mistura e cauda pesada), a NN-MADDsc atinge taxas de classificação incorreta quase idênticas à NN-MADD original (diferenças tipicamente $\le 1\%$).
• Eficiência Computacional:
  • A NN-MADDsc é significativamente mais rápida que a NN-MADD. Para um tamanho de treinamento de $n=16.384$, a NN-MADD levou mais de 6,5 horas, enquanto a NN-MADDsc completou em uma fração desse tempo.
  • A estratégia de validação cruzada incremental reduz ainda mais o tempo de execução em comparação com a validação cruzada padrão, cortando o tempo de computação em quase metade para $n=4096$.
  • A abordagem baseada em RFF oferece a aceleração mais dramática. Para $n=25.000$, o método baseado em RFF completou em menos de 25 minutos, enquanto a NN-MADDsc padrão levou mais de 15 horas, e a NN-MADD original falhou devido a restrições de memória.
• Comparação com Outros Classificadores: A NN-MADDsc consistentemente supera ou iguala classificadores de última geração (incluindo Random Forest, SVMs e GLMNET) em configurações de alta dimensão, particularmente quando as distribuições dos dados diferem em forma ou escala. Em benchmarks de séries temporais do mundo real, ela alcançou as menores taxas de erro em vários conjuntos de dados (ex: Synthetic Control Chart, Two Patterns).
• Garantias Teóricas: O artigo estabelece que, sob regimes de alta dimensão e alto número de amostras (HDHSS), as decisões de classificação da NN-MADDsc convergem para as da NN-MADD com probabilidade tendendo a 1, desde que o tamanho do conjunto representativo cresça apropriadamente em relação ao logaritmo do tamanho da amostra.

Significância e Alegações
O artigo afirma ampliar o escopo da MADD, tornando-a aplicável a cenários de big-data caracterizados tanto por alta dimensionalidade quanto por grandes contagens de observações. A principal contribuição é o desacoplamento da robustez estatística da MADD de sua complexidade computacional quadrática. Ao utilizar DPPs para amostragem de preservação de diversidade e RFFs para aproximação de kernel, os autores fornecem uma solução prática e escalável que mantém os benefícios teóricos da MADD em espaços de alta dimensão. O trabalho não pretende substituir todos os classificadores, mas posiciona a MADDsc como uma alternativa superior para classificação baseada em distância em regimes onde a distância euclidiana falha e a MADD tradicional é computacionalmente intratável.