Does Dimensionality Reduction via Random Projections Preserve Landscape Features?

1. Problema y Contexto

El Análisis Exploratorio del Paisaje (ELA, por sus siglas en inglés) es un marco fundamental para caracterizar problemas de optimización de caja negra mediante la extracción de características numéricas a partir de muestras de puntos y sus valores objetivo. Estas características se utilizan para tareas posteriores como la selección automática de algoritmos y la configuración de hiperparámetros.

Sin embargo, el ELA enfrenta limitaciones críticas en escenarios de alta dimensionalidad:

• Efectos de escasez: Se requieren tamaños de muestra enormes para obtener estimaciones estables, lo cual es prohibitivo cuando las evaluaciones de la función son costosas.
• Costo computacional: Ciertas clases de características (como las basadas en mapeo de celdas o modelos meta) se vuelven computacionalmente inviables a medida que crece la dimensión del problema.
• Incertidumbre: No está claro si aplicar técnicas de reducción de dimensionalidad (como proyecciones aleatorias) antes de calcular las características del ELA preserva las propiedades intrínsecas del paisaje original o si introduce distorsiones que invalidan los resultados.

El trabajo se centra en investigar la robustez de las características del ELA bajo Proyecciones Gaussianas Aleatorias (RGEs), una técnica que proyecta puntos de un espacio de alta dimensión ($D$) a uno de baja dimensión ($d$) mediante una matriz aleatoria, sin depender de los datos específicos (a diferencia de PCA).

2. Metodología

Los autores diseñaron un experimento riguroso utilizando la colección de problemas BBOB (Black-Box Optimization Benchmarking) de la plataforma COCO, que incluye 24 funciones sin ruido en un espacio de búsqueda continuo.

• Configuración Experimental:

  • Dimensión: $D = 20$.
  • Instancias: 15 instancias por cada una de las 24 funciones (total 360 instancias).
  • Muestreo: Se generaron diseños de muestreo mediante Latin Hypercube Sampling (LHS) con dos presupuestos de evaluación: limitado ($S = 10 \cdot D = 200$) y abundante ($S = 100 \cdot D = 2000$).
  • Reducción de Dimensionalidad: Se aplicaron RGEs para proyectar los datos a dimensiones reducidas $d \in \{2, 5, 10\}$, correspondientes a ratios de compresión $r \in \{0.1, 0.25, 0.5\}$. Se utilizaron 40 realizaciones independientes de las matrices de proyección para cada configuración.
  • Características Analizadas: Se evaluaron 8 conjuntos de características del ELA (totalizando 60 características individuales), incluyendo distribuciones, niveles, modelos meta, agrupamiento de vecinos, dispersión, contenido de información, correlación distancia-fitness y PCA.

• Métrica de Evaluación:
  Se definió un desplazamiento relativo de la característica ($\delta$) para cuantificar la diferencia entre las características calculadas en el espacio proyectado y las del espacio original (referencia). Esto permite medir tanto el sesgo inducido por la proyección como la variabilidad de la estimación.

3. Contribuciones Clave

1. Evaluación Sistemática de RGEs en ELA: Es el primer estudio que analiza exhaustivamente cómo las proyecciones gaussianas aleatorias afectan a la amplia gama de características del ELA, no solo a un subconjunto específico.
2. Análisis de Robustez y Estabilidad: Se identificaron qué características son estables (robustas) frente a la proyección y cuáles son altamente sensibles, considerando diferentes presupuestos de muestreo y grados de compresión.
3. Distinción entre Robustez e Informatividad: El trabajo demuestra que una característica puede ser "robusta" (poca variación bajo proyección) pero no necesariamente "informativa" (puede reflejar artefactos de la proyección en lugar de propiedades intrínsecas del problema).
4. Identificación de Sesgos Estructurales: Se revela cómo la proyección altera la topología del paisaje, creando multimodalidad espuria y distorsionando las relaciones de vecindad, lo que afecta directamente a características basadas en la geometría local.

4. Resultados Principales

Los hallazgos del estudio son mixtos y advierten sobre el uso indiscriminado de la reducción de dimensionalidad en ELA:

• Características Robustas: Un subconjunto de características permanece relativamente estable. Estas incluyen:

  • Estadísticas puramente basadas en los valores de fitness (ej. fitness_distance.fitness_mean, fitness_distance.fitness_std).
  • Medidas de dispersión global (ej. disp.ratio).
  • Algunos coeficientes de modelos meta (ej. el intercepto de la regresión lineal simple, debido a que los diseños LHS están centrados cerca de cero).
  • Descriptores derivados de PCA que capturan propiedades geométricas gruesas.

• Características Sensibles: La mayoría de las características, especialmente aquellas que dependen de la estructura de vecindad o la geometría local, sufren distorsiones significativas:

  • Características de Nivel (ela_level): Muestran una alta variabilidad y dependencia del paisaje específico, ya que la proyección altera la conectividad de los subniveles.
  • Agrupamiento de Vecinos Mejores (nbc) y Contenido de Información (ic): Son altamente sensibles. La proyección induce una "densificación" artificial de puntos y colapsa coordenadas distintas, distorsionando las relaciones de vecindad y las secuencias simbólicas de las caminatas aleatorias. Esto genera falsos indicadores de multimodalidad o rugosidad.

• Fenómenos de Distorsión:

  • Convergencia Consistente con la Proyección: Algunas características convergen a valores estables en el espacio reducido, pero estos valores no coinciden con los del espacio original. Esto sugiere que la característica está midiendo una propiedad del proceso de proyección y no del problema original.
  • Desplazamiento Inducido por Proyección: En otras características (como ic.eps_s), la reducción de dimensión aumenta sistemáticamente el valor estimado debido al aumento de la densidad efectiva de puntos en el espacio reducido, independientemente del tamaño de la muestra.

• Impacto del Tamaño de Muestra: Aunque un mayor presupuesto de muestreo reduce la varianza de la estimación, no elimina el sesgo sistemático introducido por la proyección. La distorsión geométrica es inherente al método de reducción de dimensionalidad.

5. Significado y Conclusiones

El estudio concluye que la reducción de dimensionalidad mediante proyecciones aleatorias no preserva fielmente las características del paisaje necesarias para el ELA en la mayoría de los casos.

• Advertencia para Aplicaciones Prácticas: Utilizar características del ELA calculadas en espacios proyectados para tareas de selección o configuración de algoritmos puede llevar a decisiones subóptimas o erróneas, ya que las características pueden reflejar artefactos de la proyección (como multimodalidad falsa) en lugar de la dificultad real del problema.
• Selección de Características: Si se debe utilizar reducción de dimensionalidad, se recomienda restringirse estrictamente al subconjunto de características que han demostrado ser robustas (principalmente estadísticas de fitness y dispersión global), evitando características basadas en topología local o vecindad.
• Futuro: Los autores sugieren que la combinación de muestreo limitado y proyecciones aleatorias no mitiga completamente los desafíos del ELA en alta dimensión. Se proponen futuras investigaciones sobre el uso de incrustaciones estructuradas o a priori (basadas en conocimiento del dominio) en lugar de proyecciones puramente aleatorias, para mejorar la asignación de presupuestos de muestreo y la fiabilidad de la caracterización del paisaje.

En resumen, el trabajo actúa como una advertencia crítica: la reducción de dimensionalidad es una herramienta poderosa para la optimización, pero no es una herramienta inocua para el análisis de características del paisaje, ya que altera fundamentalmente la información geométrica y topológica que el ELA intenta capturar.