🤖 machine learning

Efficient Coreset Selection via K-Nearest Neighbor Graphs

Este artículo presenta KNNG-CS, un método de selección de co-sets ligero que aprovecha los grafos de K-vecinos más cercanos para identificar eficientemente subconjuntos de datos representativos con costos de tiempo y memoria significativamente reducidos, manteniendo una precisión comparable a los enfoques de aproximación de gradiente existentes.

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

Publicado 2026-08-18

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

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

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Los modelos de aprendizaje automático son los motores detrás de muchas herramientas modernas, desde el reconocimiento de rostros en fotos hasta la predicción de tendencias en el mercado de valores. Para aprender a realizar estas tareas, estos modelos deben ser alimentados con cantidades masivas de datos. Imagine intentar enseñar a un estudiante dándole cada uno de los libros de una biblioteca; eventualmente aprendería, pero el proceso sería increíblemente lento y agotador. En el mundo de la inteligencia artificial, esta es la realidad de entrenar con enormes conjuntos de datos. Requiere una potencia de cómputo y una memoria enormes, lo que a menudo lo hace demasiado costoso o lento para muchas aplicaciones prácticas. Para resolver esto, los científicos utilizan una técnica llamada selección de coreset. El objetivo es simple: en lugar de usar la biblioteca completa, encontrar un subconjunto pequeño y perfecto de libros que contenga todas las lecciones esenciales. Si puede entrenar el modelo con esta muestra diminuta y representativa, este aprenderá tan bien como si hubiera leído todo, pero en una fracción del tiempo y con mucha menos memoria.

Durante años, las mejores formas de encontrar estos subconjuntos pequeños y perfectos han dependido de un método que es computacionalmente pesado. Estos enfoques existentes intentan medir la distancia entre cada uno de los puntos de datos y cada uno de los demás puntos de datos para ver cuáles son más similares. Es como intentar encontrar al mejor representante de una multitud haciendo que cada persona mida su distancia con respecto a todas las demás personas en la sala. Si bien esto funciona, crea una cantidad masiva de datos que es difícil de almacenar y procesar, especialmente cuando el conjunto de datos crece. Los investigadores de la Universidad de Xidian y sus colaboradores se dieron cuenta de que este enfoque de "medir todo" era ineficiente. Observaron que los representantes más útiles en un conjunto de datos son usualmente aquellos que se encuentran en medio de grupos densos de elementos similares, en lugar de aquellos que están aislados. Una muestra que está cerca de muchas otras es probablemente representativa de un patrón común, mientras que una muestra aislada tiene menos probabilidades de ser un buen sustituto para un grupo grande.

Para abordar esto, el equipo desarrolló un nuevo método llamado KNNG-CS. En lugar de obligar a cada elemento a medir su distancia con todos los demás elementos, construyeron un mapa que solo conecta cada elemento con sus diez vecinos más cercanos. Esto crea una red dispersa, o un grafo, que captura las relaciones locales entre los puntos de datos sin la carga abrumadora de calcular cada conexión posible. Una vez construido este mapa, los investigadores asignaron una puntuación a cada elemento basada en cuántos otros elementos lo señalaban como vecino y qué tan cerca estaban esos vecinos. Los elementos que fueron elegidos frecuentemente como un vecino cercano por muchos otros recibieron una puntuación alta, marcándolos como representantes altamente importantes. El algoritmo luego seleccionó de forma codiciosa los elementos con mayor puntuación para formar el subconjunto pequeño final. A medida que cada elemento de alta puntuación era elegido, el algoritmo lo eliminaba junto con sus vecinos del grupo, asegurando que el grupo seleccionado cubriera todo el conjunto de datos de manera eficiente y sin redundancia.

Los resultados de este nuevo enfoque fueron sorprendentes cuando se probaron en cuatro conjuntos de datos del mundo real, que iban desde tipos de cobertura forestal hasta calificaciones de películas y deudas de tarjetas de crédito. El nuevo método produjo un conjunto de entrenamiento pequeño que permitió al modelo de aprendizaje automático lograr una precisión comparable a la de los mejores métodos existentes. Sin embargo, la diferencia en eficiencia fue dramática. El nuevo método funcionó entre 2.3 y 41.2 veces más rápido que las técnicas líderes anteriores. Aún más impresionante fue la reducción en el uso de memoria. Mientras que los métodos antiguos requerían almacenar tablas masivas de distancias que podían consumir gigabytes de memoria, el nuevo enfoque utilizó solo el 0.3% al 7.5% de esa memoria. En términos prácticos, esto significa que tareas que antes requerían servidores costosos y de alta gama ahora podrían realizarse en máquinas mucho más pequeñas y accesibles. Los investigadores encontraron que incluso con un subconjunto de datos muy pequeño, el modelo aprendía eficazmente, convergiendo a una solución estable mucho más rápido que si hubiera sido entrenado con el conjunto de datos completo.

Este trabajo demuestra que, al enfocarse en las relaciones locales en lugar de las comparaciones globales, es posible simplificar drásticamente el proceso de preparación de datos para el aprendizaje automático. El estudio confirma que no es necesario calcular cada distancia posible para encontrar los puntos de datos más importantes; un mapa local inteligente es suficiente. Al utilizar esta estrategia basada en grafos, los investigadores han demostrado que se puede lograr un entrenamiento de modelos de alta calidad con una fracción del tiempo y los recursos que antes se consideraban necesarios. Esto abre la puerta a procesos de entrenamiento más eficientes, permitiendo que modelos complejos sean desarrollados y desplegados en entornos donde la potencia de cómputo es limitada, sin sacrificar la calidad del resultado final.

Resumen Técnico: Selección de Coresets Eficiente mediante Grafos de K-Vecinos Más Cercanos

Planteamiento del Problema

La selección de coresets tiene como objetivo reducir los costes computacionales y de memoria del entrenamiento de modelos de aprendizaje automático, reemplazando un gran conjunto de entrenamiento con un subconjunto pequeño y representativo. El artículo se centra en la selección de coreset basada en la aproximación de gradientes (GA). En este marco, el objetivo es seleccionar un subconjunto $C$ de tamaño $M$ de un conjunto de entrenamiento $T$ tal que los gradientes del conjunto completo sean bien aproximados por el subconjunto. Este problema se reduce matemáticamente a minimizar el error de representatividad en el espacio de características (Ec. 1), donde cada punto de datos es representado por su vecino más cercano en el coreset seleccionado.

Los métodos existentes basados en GA, como CRAIG y FastCore, dependen de estrategias de selección codiciosas (greedy). Sin embargo, enfrentan problemas significativos de escalabilidad:

CRAIG precalcula una matriz de distancias de pares densa, lo que requiere $O(n^2)$ de espacio y $O(n^2d)$ de tiempo, lo cual resulta prohibitivo en conjuntos de datos grandes.
FastCore reemplaza las distancias entre elementos con límites superiores de elemento-clúster para ahorrar espacio, pero a menudo requiere un número masivo de clústeres (cientos a decenas de miles) para mantener la precisión, lo que genera una sobrecarga considerable en el cálculo y almacenamiento de grandes matrices de límites.

Los autores observan que la representatividad en el espacio de características es inherentemente local: una muestra que sirve como un vecino cercano para muchas otras muestras es probablemente un representante de una región local densa con un error de aproximación bajo. Los métodos existentes no logran explotar esta localidad de manera eficiente porque dependen de estructuras densas en lugar de relaciones de vecindad dispersas (sparse).

Metodología: KNNG-CS

El artículo propone KNNG-CS, un método de selección de coreset ligero basado en un Grafo de K-Vecinos Más Cercanos (KNNG). El método opera en tres etapas principales:

1. Construcción Aproximada del KNNG

En lugar de calcular todas las distancias de pares, el método construye un KNNG aproximado $G=(V, E)$ sobre los vectores de características. Cada nodo $x_i$ se conecta a sus $K$ vecinos más cercanos.

Eficiencia: Utilizando métodos aproximados de vanguardia (por ejemplo, KGraph), el tiempo de construcción es $O(n^{1.14}d)$ , y la complejidad de espacio es lineal, $O(nK)$, donde $K$ es una constante pequeña (establecida en 10 en los experimentos). Esto evita el requisito de espacio cuadrático de las matrices densas.

2. Puntuación de Nodos Sensible a la Distancia

La innovación central es una función de puntuación que estima la importancia de cada nodo (elemento de datos) basándose en su estructura de vecindad local dentro del KNNG.

Grado de Entrada (In-Degree): Un nodo con un alto grado de entrada (muchos nodos apuntan a él como un vecino cercano) es un fuerte candidato para la representatividad.
Sensibilidad a la Distancia: El grado de entrada por sí solo es insuficiente. El método incorpora las distancias de las aristas convirtiéndolas en probabilidades mediante una función softmax (Ec. 2).
Fórmula de Puntuación: La puntuación de importancia $P_i$ para un nodo $v_i$ es la suma de las probabilidades softmax de todas las aristas entrantes (Ec. 3):
$P_i = \sum_{v_j \in N_{in}^G(v_i)} p_{ji}$
donde $p_{ji}$ representa el peso de cercanía normalizado desde el vecino $v_j$ hacia $v_i$ . Esto permite al método distinguir entre nodos con iguales grados de entrada pero con diferentes proximidades a sus vecinos.

3. Selección Codiciosa con Eliminación de Redundancia

El proceso de selección es un algoritmo codicioso de una sola pasada:

Calcular la puntuación de importancia $P_i$ para todos los nodos.
Seleccionar el nodo con la puntuación más alta y añadirlo al coreset $C$ .
Eliminación de Redundancia: Eliminar inmediatamente el nodo seleccionado y todos sus vecinos de entrada del grafo. La lógica es que si un nodo es seleccionado, sus vecinos de entrada (que lo consideran un vecino cercano) serán representados por este y no necesitan ser seleccionados ellos mismos.
Repetir hasta que se seleccionen $M$ elementos.

Este enfoque evita la recomputación repetida del beneficio, un cuello de botella importante en los métodos codiciosos tradicionales.

Contribuciones Clave

Algoritmo KNNG-CS: Un método de selección de coreset escalable basado en GA que utiliza un Grafo de K-Vecinos Más Cercanos disperso para evitar estructuras de distancia densas y costosas.
Mecanismo de Puntuación Novedoso: Una función de puntuación de vecinos entrantes sensible a la distancia que estima la representatividad local directamente desde el KNNG sin almacenar distancias de pares densas.
Ganancias de Eficiencia: Validación empírica que demuestra que el método reduce significativamente el tiempo de selección y el uso de memoria, manteniendo una calidad de coreset comparable a los métodos de vanguardia.

Resultados Experimentales

Los autores evaluaron KNNG-CS en cuatro conjuntos de datos del mundo real: CovType, IMDB, Brazil y Card. Compararon su método contra el muestreo aleatorio (Random sampling), CRAIG y FastCore.

Efectividad (Precisión): KNNG-CS logró una precisión de prueba comparable a la de CRAIG y FastCore, y significativamente mejor que el muestreo aleatorio. Aunque CRAIG mostró una precisión ligeramente superior en algunos conjuntos de datos (IMDB, Card, Brazil) debido a su uso de distancias exactas, KNNG-CS mantuvo un rendimiento competitivo.
Eficiencia (Tiempo): KNNG-CS demostró aceleraciones sustanciales:
- De 2.3× a 41.2× más rápido que CRAIG.
- De 2.3× a 4.9× más rápido que FastCore.
  La aceleración se atribuye a la construcción eficiente del KNNG y a la estrategia de selección codiciosa de una sola pasada que evita cálculos matriciales.
Uso de Memoria: KNNG-CS redujo drásticamente el consumo de memoria pico:
- Requirió solo el 0.3% al 3.4% de la memoria pico utilizada por CRAIG.
- Requirió solo el 4.1% al 7.5% de la memoria pico utilizada por FastCore.
  Esto se debe a que KNNG-CS almacena solo $O(nK)$ aristas, mientras que sus competidores almacenan matrices de distancias $O(n^2)$ o grandes matrices de límites de ítem-clúster.
Convergencia: El entrenamiento sobre el coreset seleccionado convergió mucho más rápido (en términos de iteraciones) que el entrenamiento sobre el conjunto de datos completo, siendo el tamaño del coreset $M=0.01n$ un buen equilibrio entre eficiencia y efectividad.

Significado y Reivindicaciones

El artículo afirma que KNNG-CS ofrece una solución práctica para la selección de coresets a gran escala al cambiar de estructuras de distancia globales y densas a estructuras de vecindad locales y dispersas. Al aprovechar la localidad inherente de los espacios de características, el método logra:

Complejidad de almacenamiento lineal ($O(nK)$) en comparación con la complejidad cuadrática ( $O(n^2)$ ) de los métodos anteriores de vanguardia.
Reducciones significativas tanto en costes de tiempo como de memoria sin sacrificar la calidad del subconjunto seleccionado.
Un proceso de selección ligero que requiere solo una pasada de selección codiciosa tras la construcción del grafo, eliminando la necesidad de cálculos de distancia repetidos.

Los autores concluyen que este enfoque permite una selección de coreset eficiente para conjuntos de datos grandes donde los métodos tradicionales de aproximación de gradientes son computacional o memóricamente prohibitivos.