Resumo Técnico: Valoração de Dados Baseada em Banzhaf Eficiente para Classificação por $k$ Vizinhos Mais Próximos

Declaração do Problema

A valoração de dados, a tarefa de quantificar a contribuição de pontos de dados individuais para o desempenho do modelo, é um desafio fundamental no aprendizado de máquina. Embora abordagens baseadas na teoria dos jogos, como o valor de Banzhaf, ofereçam estruturas principiais para uma valoração justa, elas sofrem de complexidade computacional exponencial. Especificamente, o cálculo de valores exatos de Banzhaf requer a avaliação da função de valor sobre todos os subconjuntos possíveis do conjunto de dados, uma tarefa provada ser #P-difícil em geral. Esse ônus computacional torna o cálculo exato inviável para conjuntos de dados do mundo real contendo milhares ou milhões de amostras, forçando a maioria dos trabalhos existentes a depender de métodos de aproximação que trocam precisão por eficiência.

Este artigo aborda o desafio específico de calcular valores exatos de Banzhaf para classificadores de $k$ vizinhos mais próximos ($k$NN). Os autores visam preencher a lacuna entre os fundamentos teóricos da teoria dos jogos cooperativos e as demandas práticas do aprendizado de máquina do mundo real, desenvolvendo algoritmos que exploram as propriedades únicas de localidade do $k$NN para alcançar melhorias computacionais significativas sem recorrer a aproximações.

Metodologia

O artigo propõe um conjunto de algoritmos de programação dinâmica (PD) adaptados ao cenário de classificação $k$NN, juntamente com métodos eficientes de estimativa de Monte Carlo.

1. Dificuldade Teórica

Os autores primeiro estabelecem a dificuldade teórica do problema. Eles provam que calcular valores de Banzhaf para o modelo de classificação $k$NN é #P-difícil. Isso é demonstrado por meio de uma redução do problema do Jogo da Maioria Ponderada (Weighted-Majority-Game - WMG), um problema clássico #P-difícil na teoria dos jogos cooperativos. Esse resultado implica que, sob suposições padrão de complexidade, nenhum algoritmo de tempo polinomial estritamente forte existe para o caso geral.

2. Estruturas de Programação Dinâmica

Apesar do resultado de dificuldade, os autores exploram a propriedade de localidade do $k$NN (onde apenas os $k$ vizinhos mais próximos influenciam a previsão) para desenvolver algoritmos exatos com complexidades de tempo melhoradas.

• PD Padrão para $k$NN Ponderado:
  Os autores apresentam inicialmente um algoritmo de PD com complexidade de tempo de $O(W n^4)$, onde $n$ é o número de pontos de dados e $W$ é a soma máxima dos pesos dos $k$ primeiros. Essa abordagem define uma função de estado $f_i(w, s, m)$ representando o número de subconjuntos de tamanho $s$ com uma soma de pesos específica $w$ e um $m$-ésimo ponto mais próximo específico.

• PD Aprimorado para $k$NN Ponderado:
  Para reduzir a complexidade, os autores introduzem técnicas inovadoras:

  • Pré-cálculo de Soma Parcial: Para o caso em que o tamanho do subconjunto $s \le k$, eles pré-calculam somas parciais para acelerar a relação de recorrência, reduzindo a contribuição de complexidade desse termo.
  • Recorrência de Coeficientes Binomiais: Para $s > k$, eles exploram relações de recorrência de coeficientes binomiais para calcular a soma de estados de forma eficiente.
  • Resultado: Essas otimizações produzem um algoritmo com complexidade de tempo de $O(W k n^2)$.

• PD Especializado para $k$NN Não Ponderado:
  Para o caso não ponderado (onde todos os pesos são 1), os autores propõem um algoritmo especializado que alcança complexidade de tempo de $O(n k^2)$.

  • Redesenho do Espaço de Estados: Eles reduzem o espaço de estados eliminando a necessidade de rastrear a identidade específica do $m$-ésimo ponto mais próximo.
  • Agregação Forward e Backward: Eles utilizam funções forward ($f_i$) e backward ($b_i$), juntamente com funções backward assinadas ($b^+_i, b^-_i$) para lidar com sinais de rótulos.
  • Resultado: Como $k$ é tipicamente uma constante pequena, este algoritmo executa em tempo quase linear em relação ao número de pontos de dados.

3. Estimativa de Monte Carlo

Reconhecendo que até mesmo a complexidade quadrática pode ser proibitiva para conjuntos de dados massivos, o artigo oferece dois métodos eficientes baseados em amostragem:

• Amostragem Baseada em Coalizões: Otimizada mantendo apenas os $k+1$ principais jogadores em uma lista ordenada, reduzindo a complexidade para $O(m n \log k)$ para $m$ amostras.
• Amostragem Baseada em Permutação: Adapta a formulação de permutação dos valores de Banzhaf por meio de um esquema de reponderação, alcançando também complexidade de $O(m n \log k)$.

Contribuições Principais

1. Prova de Dificuldade: O artigo prova que calcular valores de Banzhaf para classificadores $k$NN é #P-difícil.
2. Primeira PD Exata para $k$NN Ponderado: Apresenta o primeiro algoritmo de programação dinâmica para calcular valores exatos de Banzhaf em classificadores $k$NN ponderados com complexidade de tempo pseudo-polinomial.
3. Algoritmo Ponderado Otimizado: Melhora significativamente a complexidade de tempo do algoritmo ponderado para $O(W k n^2)$ através de técnicas algorítmicas inovadoras envolvendo somas parciais e recorrências binomiais.
4. Algoritmo Não Ponderado Quase Linear: Introduz um algoritmo especializado para $k$NN não ponderado com complexidade de tempo $O(n k^2)$, representando o primeiro algoritmo de tempo quase linear para calcular valores baseados em teoria dos jogos com rótulos duros para $k$NN.
5. Amostragem Eficiente: Fornece métodos de Monte Carlo baseados em coalizões e permutações otimizados que exploram a localidade do $k$NN para estimativa aproximada mais rápida.

Resultados Experimentais

Os autores conduziram experimentos extensivos em 12 conjuntos de dados do mundo real (variando de 5.404 a 1.000.000 de pontos de dados) e dados sintéticos.

• Eficiência Computacional:

  • O algoritmo de força bruta falhou em completar dentro de 10 horas para conjuntos de dados tão pequenos quanto 30 pontos.
  • O algoritmo de PD não ponderado (bv-uw) demonstrou escalabilidade quase linear, lidando com conjuntos de dados de até $10^6$ pontos dentro do orçamento de tempo.
  • A PD ponderada aprimorada (bv-fast) escalou até $10^4$ pontos, superando as linhas de base existentes de Shapley com rótulos duros (sv, sv-uw), que não conseguiram completar execuções para $n \ge 10^4$.
  • Métodos de Monte Carlo ofereceram acelerações de até 25$\times$ sobre a PD ponderada ao aceitar um desvio de aproximadamente 0,02.

• Aplicações Práticas:

  • Remoção de Pontos: A remoção de pontos de dados com os maiores valores de Banzhaf causou uma queda mais acentuada na precisão do modelo em comparação com outros métodos (como LOO ou Funções de Influência), indicando que esses pontos eram críticos para o desempenho.
  • Seleção de Dados: A seleção de pontos com os maiores valores melhorou incrementalmente a precisão do modelo mais rapidamente do que a seleção aleatória ou outras linhas de base.
  • Detecção de Rótulos Incorretos: O estudo destacou uma compensação entre tipos de valoração. Os valores de Shapley com rótulos suaves foram melhores na detecção de rótulos aleatoriamente invertidos (alta pontuação $F_1$). No entanto, valores de Banzhaf com rótulos duros foram superiores na identificação de pontos decisivos de baixa qualidade cuja correção melhorou significativamente o desempenho do modelo. Valores com rótulos duros foram mais robustos ao ruído e mais adequados para limpeza de dados onde o objetivo é corrigir pontos que realmente alteram as previsões.

Significado e Alegações

O artigo alega fornecer os algoritmos mais rápidos para valoração de Banzhaf com rótulos duros em $k$NN, superando até mesmo a eficiência de suas contrapartes de Shapley com rótulos duros. O significado reside em tornar a valoração de dados baseada em teoria dos jogos exata computacionalmente viável para conjuntos de dados em grande escala, uma tarefa anteriormente limitada a aproximações.

Os autores enfatizam que, embora o valor de Banzhaf não satisfaça o axioma de eficiência (a soma dos valores é igual ao valor total) sem normalização, ele oferece vantagens práticas distintas:

• Esparsidade: Produz valores mais esparsos, destacando um conjunto concentrado de pontos influentes, o que é benéfico para interpretabilidade baseada em exemplos.
• Robustez: É mais robusto ao ruído e a pontos de dados duplicados em comparação com os valores de Shapley, que podem ser excessivamente sensíveis a subconjuntos extremos.
• Praticidade: Os algoritmos desenvolvidos permitem a aplicação de valoração de dados rigorosa em cenários como aquisição de dados, limpeza e aprendizado colaborativo, onde entender a ordem relativa da importância dos pontos de dados é crucial.

O artigo conclui que, embora a estrutura não se estenda diretamente à regressão $k$NN devido a termos de normalização não decomponíveis, ela preenhe com sucesso a lacuna entre a teoria dos jogos cooperativos e aplicações práticas de aprendizado de máquina para tarefas de classificação.