Conjunto básico

En geometría computacional y algoritmos de aproximación , un coreset es un subconjunto pequeño, posiblemente ponderado, de un conjunto de puntos de entrada que preserva aproximadamente el valor de un problema de optimización específico. Resolver el problema en el coreset produce una solución cuyo costo es demostrablemente cercano a la solución óptima para el conjunto de datos completo. Los coresets se utilizan ampliamente en optimización geométrica, análisis de clústeres , flujos de datos y aprendizaje automático a gran escala para reducir la complejidad computacional manteniendo garantías teóricas. ^{[ 1 ] [ 2 ]}

Muchos problemas de optimización geométrica admiten conjuntos básicos cuyo tamaño está acotado por una función del parámetro de aproximación ε y la dimensión, pero que son independientes del tamaño de entrada. Cuando dicho conjunto básico puede construirse en tiempo lineal o casi lineal, se obtiene un esquema de aproximación en tiempo polinomial (PTAS) o un algoritmo de aproximación eficiente.

El concepto de coresets surgió a finales de la década de 1990 y principios de la de 2000 en el campo de la geometría computacional, como parte de un esfuerzo más amplio por desarrollar esquemas de aproximación para problemas geométricos de alta dimensión. Los primeros trabajos vincularon los coresets con las aproximaciones ε y las redes ε en espacios de rango y la teoría de la dimensión VC . Investigaciones posteriores extendieron el marco a la agrupación, los modelos de transmisión y la computación distribuida. Con el tiempo, los coresets se convirtieron en una herramienta fundamental en el análisis de datos a gran escala, particularmente para problemas de agrupación y regresión, donde el cálculo exacto en conjuntos de datos masivos es computacionalmente inviable.

Sea P un conjunto finito de puntos y sea f(P, x) el costo de una solución candidata x para un problema de optimización definido en P. Por ejemplo, en el agrupamiento k-means, x puede representar un conjunto de k centros y f(P, x) la suma de las distancias al cuadrado desde los puntos en P hasta su centro más cercano.

Un ε-coreset (fuerte) para P con respecto a f es un subconjunto (posiblemente ponderado) S ⊆ P tal que para todas las soluciones candidatas x,

${\displaystyle (1-\epsilon )\,f(P,x)\leq f(S,x)\leq (1+\epsilon )\,f(P,x),}$

donde ε > 0 es un parámetro de aproximación definido por el usuario.

En muchas construcciones, S está equipado con pesos w(p) de modo que

${\displaystyle f(S,x)=\sum _{p\in S}w(p)\,c(p,x),}$

donde c(p, x) es la contribución del punto p al costo.

Algunos textos distinguen entre:

• Coresets fuertes : La garantía de aproximación se cumple uniformemente para todas las soluciones candidatas x.
• Conjuntos básicos débiles : La garantía solo se cumple para soluciones cercanas al óptimo.

Los conjuntos básicos se construyen normalmente utilizando una o más de las siguientes técnicas:

• Muestreo por importancia : Los puntos se muestrean con una probabilidad proporcional a su sensibilidad (su máxima influencia relativa en la función objetivo).
• Muestreo aleatorio y aproximaciones ε : Se utilizan técnicas de la teoría VC para garantizar la convergencia uniforme .
• Particionamiento geométrico : El espacio se divide y se seleccionan puntos representativos de cada región.
• Marcos de fusión y reducción : Se utilizan en entornos de transmisión y distribución para mantener conjuntos de datos básicos a lo largo del tiempo.

Para muchos problemas, el tamaño del conjunto básico es O(g(ε, d)), donde d es la dimensión y el límite no depende del tamaño de entrada n.

En los modelos de transmisión de datos, los puntos de datos llegan secuencialmente y el almacenamiento es limitado. Las técnicas de fusión y reducción mantienen un conjunto de datos reducido cuyo tamaño depende únicamente de ε y de los parámetros del problema. De manera similar, en los sistemas distribuidos, los conjuntos de datos componibles permiten que cada máquina calcule un conjunto de datos local, que luego se puede combinar de forma centralizada, preservando las garantías de aproximación.

Los conjuntos básicos están relacionados con:

• Aproximaciones ε y redes ε en espacios de rango
• Técnicas de dibujo aleatorio
• Reducción de dimensionalidad
• Algoritmos sublineales y de transmisión