🤖 machine learning

Efficient Coreset Selection via K-Nearest Neighbor Graphs

Este artigo apresenta o KNNG-CS, um método de seleção de coreset leve que aproveita grafos de K-vizinhos mais próximos para identificar eficientemente subconjuntos de dados representativos com custos de tempo e memória significativamente reduzidos, mantendo uma precisão comparável às abordagens de aproximação de gradiente existentes.

Autores originais: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Publicado 2026-08-18

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Modelos de aprendizado de máquina são os motores por trás de muitas ferramentas modernas, desde o reconhecimento de rostos em fotos até a previsão de tendências do mercado de ações. Para aprender a realizar essas tarefas, esses modelos precisam ser alimentados com quantidades massivas de dados. Imagine tentar ensinar um estudante dando a ele todos os livros de uma biblioteca; ele eventualmente aprenderia, mas o processo seria incrivelmente lento e exaustivo. No mundo da inteligência artificial, esta é a realidade do treinamento em enormes conjuntos de dados. Isso requer um poder computacional e memória enormes, tornando-o frequentemente caro ou lento para muitas aplicações práticas. Para resolver isso, cientistas utilizam uma técnica chamada seleção de coreset. O objetivo é simples: em vez de usar a biblioteca inteira, encontrar um subconjunto pequeno e perfeito de livros que contenha todas as lições essenciais. Se você puder treinar o modelo com essa amostra minúscula e representativa, ele aprenderá tão bem quanto se tivesse lido tudo, mas em uma fração do tempo e com muito menos memória.

Por anos, as melhores formas de encontrar esses subconjuntos pequenos e perfeitos basearam-se em um método que é computacionalmente pesado. Essas abordagens existentes tentam medir a distância entre cada ponto de dado e cada outro ponto de dado para ver quais são mais semelhantes. É como tentar encontrar o melhor representante para uma multidão fazendo com que cada pessoa meça sua distância de todas as outras pessoas na sala. Embora isso funcione, cria uma quantidade massiva de dados que é difícil de armazenar e processar, especialmente quando o conjunto de dados cresce. Os pesquisadores da Universidade de Xidian e seus colaboradores perceberam que essa abordagem de "medir tudo" era ineficiente. Eles observaram que os representantes mais úteis em um conjunto de dados são geralmente aqueles que se situam no meio de grupos densos de itens semelhantes, em vez daqueles que estão isolados. Uma amostra que está próxima de muitas outras provavelmente representa um padrão comum, enquanto uma amostra isolada tem menos probabilidade de ser um bom substituto para um grande grupo.

Para enfrentar isso, a equipe desenvolveu um novo método chamado KNNG-CS. Em vez de forçar cada item a medir sua distância para todos os outros itens, eles construíram um mapa que conecta apenas cada item aos seus dez vizinhos mais próximos. Isso cria uma rede esparsa, ou um grafo, que captura as relações locais entre os pontos de dados sem o fardo esmagador de calcular todas as conexões possíveis. Uma vez construído esse mapa, os pesquisadores atribuíram uma pontuação a cada item com base em quantos outros itens o apontavam como um vizinho e quão próximos esses vizinhos estavam. Itens que foram frequentemente escolhidos como um vizinho próximo por muitos outros receberam uma pontuação alta, marcando-os como representantes altamente importantes. O algoritmo então selecionou avidamente os itens de maior pontuação para formar o subconjunto final. À medida que cada item de alta pontuação era escolhido, o algoritmo removia este e seus vizinhos do grupo, garantindo que o grupo selecionado cobrisse todo o conjunto de dados de forma eficiente e sem redundância.

Os resultados desta nova abordagem foram impressionantes quando testados em quatro conjuntos de dados do mundo real, variando de tipos de cobertura florestal a classificações de filmes e inadimplência de cartões de crédito. O novo método produziu um conjunto de treinamento pequeno que permitiu ao modelo de aprendizado de máquina alcançar uma precisão comparável aos melhores métodos existentes. No entanto, a diferença de eficiência foi dramática. O novo método rodou entre 2,3 e 41,2 vezes mais rápido do que as técnicas líderes anteriores. Ainda mais impressionante foi a redução no uso de memória. Enquanto os métodos antigos exigiam o armazenamento de tabelas massivas de distâncias que poderiam consumir gigabytes de memória, a nova abordagem utilizou apenas 0,3% a 7,5% dessa memória. Em termos práticos, isso significa que tarefas que anteriormente exigiam servidores caros e de alto desempenho agora podem ser realizadas em máquinas muito menores e mais acessíveis. Os pesquisadores descobriram que, mesmo com um subconjunto de dados muito pequeno, o modelo aprendeu efetivamente, convergindo para uma solução estável muito mais rápido do que se tivesse sido treinado no conjunto de dados completo.

Este trabalho demonstra que, ao focar em relações locais em vez de comparações globais, é possível simplificar drasticamente o processo de preparação de dados para o aprendizado de máquina. O estudo confirma que você não precisa calcular todas as distâncias possíveis para encontrar os pontos de dados mais importantes; um mapa local inteligente é suficiente. Ao utilizar essa estratégia baseada em grafos, os pesquisadores mostraram que um treinamento de modelo de alta qualidade pode ser alcançado com uma fração do tempo e dos recursos anteriormente considerados necessários. Isso abre as portas para processos de treinamento mais eficientes, permitindo que modelos complexos sejam desenvolvidos e implantados em ambientes onde o poder computacional é limitado, sem sacrificar a qualidade do resultado final.

Resumo Técnico: Seleção de Coreset Eficiente via Grafos de K-Vizinhos Mais Próximos

Declaração do Problema

A seleção de coreset visa reduzir os custos computacionais e de memória do treinamento de modelos de aprendizado de máquina, substituindo um grande conjunto de treinamento por um subconjunto pequeno e representativo. O artigo foca na seleção de coreset baseada em aproximação de gradiente (GA). Neste framework, o objetivo é selecionar um subconjunto $C$ de tamanho $M$ de um conjunto de treinamento $T$ tal que os gradientes do conjunto completo sejam bem aproximados pelo subconjunto. Este problema é reduzido matematicamente à minimização do erro de representatividade no espaço de características (Eq. 1), onde cada ponto de dado é representado por seu vizinho mais próximo no coreset selecionado.

Métodos existentes baseados em GA, como CRAIG e FastCore, dependem de estratégias de seleção gananciosas (greedy). No entanto, eles enfrentam problemas significativos de escalabilidade:

CRAIG pré-computa uma matriz de distância densa de pares, exigindo $O(n^2)$ de espaço e $O(n^2d)$ de tempo, o que se torna proibitivo em grandes conjuntos de dados.
FastCore substitui as distâncias item-item por limites superiores de item-cluster para economizar espaço, mas frequentemente requer um número massivo de clusters (centenas a dezenas de milhares) para manter a precisão, levando a um overhead considerável no cálculo e armazenamento de grandes matrizes de limites.

Os autores observam que a representatividade no espaço de características é inerentemente local: uma amostra que serve como um vizinho próximo para muitas outras amostras é provavelmente representativa de uma região local densa com baixo erro de aproximação. Métodos existentes falham em explorar essa localidade de forma eficiente porque dependem de estruturas densas em vez de relações de vizinhança esparsas.

Metodologia: KNNG-CS

O artigo propõe o KNNG-CS, um método de seleção de coreset leve baseado em um Grafo de K-Vizinhos Mais Próximos (KNNG). O método opera em três estágios principais:

1. Construção de KNNG Aproximado

Em vez de calcular todas as distâncias de pares, o método constrói um KNNG aproximado $G=(V, E)$ sobre os vetores de características. Cada nó $x_i$ conecta-se aos seus $K$ vizinhos mais próximos.

Eficiência: Usando métodos aproximados de última geração (ex: KGraph), o tempo de construção é $O(n^{1.14}d)$ , e a complexidade de espaço é linear, $O(nK)$, onde $K$ é uma constante pequena (definida como 10 nos experimentos). Isso evita o requisito de espaço quadrático das matrizes densas.

2. Pontuação de Nós Sensível à Distância

A inovação central é uma função de pontuação que estima a importância de cada nó (item de dado) com base em sua estrutura de vizinhança local dentro do KNNG.

Grau de Entrada (In-Degree): Um nó com um alto grau de entrada (muitos nós apontam para ele como um vizinho próximo) é um forte candidato à representatividade.
Sensibilidade à Distância: O grau de entrada por si só é insuficiente. O método incorpora as distâncias das arestas convertendo-as em probabilidades usando uma função softmax (Eq. 2).
Fórmula de Pontuação: A pontuação de importância $P_i$ para um nó $v_i$ é a soma das probabilidades softmax de todas as arestas de entrada (Eq. 3):
$P_i = \sum_{v_j \in N_{in}^G(v_i)} p_{ji}$
onde $p_{ji}$ representa o peso de proximidade normalizado do vizinho $v_j$ para $v_i$ . Isso permite que o método distinga entre nós com graus de entrada iguais, mas com diferentes proximidades em relação aos seus vizinhos.

3. Seleção Gananciosa com Remoção de Redundância

O processo de seleção é um algoritmo ganancioso de passagem única:

Calcular a pontuação de importância $P_i$ para todos os nós.
Selecionar o nó com a maior pontuação e adicioná-lo ao coreset $C$ .
Remoção de Redundância: Remover imediatamente o nó selecionado e todos os seus vizinhos de entrada (in-neighbors) do grafo. A lógica é que, se um nó é selecionado, seus vizinhos de entrada (que o consideram um vizinho próximo) serão representados por ele e não precisam ser selecionados eles mesmos.
Repetir até que $M$ itens sejam selecionados.

Esta abordagem evita a recomputação repetida do benefício, um grande gargalo nos métodos gananciosos tradicionais.

Principais Contribuições

Algoritmo KNNG-CS: Um método de seleção de coreset escalável, baseado em GA, que utiliza um Grafo de K-Vizinhos Mais Próximos esparso para evitar estruturas de distância densas e caras.
Mecanismo de Pontuação Inovador: Uma função de pontuação de vizinhos de entrada sensível à distância que estima a representatividade local diretamente do KNNG sem armazenar distâncias de pares densas.
Ganhos de Eficiência: Validação empírica demonstrando que o método reduz significativamente o tempo de seleção e o uso de memória, mantendo uma qualidade de coreset comparável aos métodos de última geração.

Resultados Experimentais

Os autores avaliaram o KNNG-CS em quatro conjuntos de dados do mundo real: CovType, IMDB, Brazil e Card. Eles compararam seu método com Amostragem Aleatória (Random sampling), CRAIG e FastCore.

Eficácia (Acurácia): O KNNG-CS alcançou acurácia de teste comparável ao CRAIG e FastCore, e significativamente melhor que a Amostragem Aleatória. Embora o CRAIG tenha mostrado uma acurácia ligeiramente superior em alguns conjuntos de dados (IMDB, Card, Brazil) devido ao uso de distâncias exatas, o KNNG-CS manteve um desempenho competitivo.
Eficiência (Tempo): O KNNG-CS demonstrou acelerações substanciais:
- 2.3× a 41.2× mais rápido que o CRAIG.
- 2.3× a 4.9× mais rápido que o FastCore.
- A aceleração é atribuída à construção eficiente do KNNG e à estratégia de seleção gananciosa de passagem única que evita cálculos de matrizes.
Uso de Memória: O KNNG-CS reduziu drasticamente o consumo de memória de pico:
- Requer apenas 0.3% a 3.4% da memória de pico usada pelo CRAIG.
- Requer apenas 4.1% a 7.5% da memória de pico usada pelo FastCore.
- Isso ocorre porque o KNNG-CS armazena apenas $O(nK)$ arestas, enquanto os concorrentes armazenam matrizes de distância $O(n^2)$ ou grandes matrizes de limites item-cluster.
Convergência: O treinamento no coreset selecionado convergiu muito mais rápido (em termos de iterações) do que o treinamento no conjunto de dados completo, com o tamanho do coreset $M=0.01n$ proporcionando um bom equilíbrio entre eficiência e eficácia.

Significância e Alegações

O artigo afirma que o KNNG-CS oferece uma solução prática para a seleção de coreset em larga escala ao mudar de estruturas de distância globais e densas para estruturas de vizinhança locais e esparsas. Ao alavancar a localidade inerente dos espaços de características, o método alcança:

Complexidade de armazenamento linear ($O(nK)$) em comparação com a complexidade quadrática ( $O(n^2)$ ) dos métodos anteriores de última geração.
Reduções significativas tanto nos custos de tempo quanto de memória sem sacrificar a qualidade do subconjunto selecionado.
Um processo de seleção leve que requer apenas uma passagem de seleção gananciosa após a construção do grafo, eliminando a necessidade de cálculos de distância repetidos.

Os autores concluem que esta abordagem permite a seleção eficiente de coreset para grandes conjuntos de dados onde os métodos tradicionais de aproximação de gradiente são computacionalmente ou memorialmente proibitivos.