Does Dimensionality Reduction via Random Projections Preserve Landscape Features?

Resumo Técnico: Redução de Dimensionalidade via Projeções Aleatórias e Análise Exploratória de Paisagem

1. Problema e Motivação

A Análise Exploratória de Paisagem (ELA - Exploratory Landscape Analysis) é um framework fundamental para caracterizar problemas de otimização de caixa-preta, extraindo características numéricas (features) de pontos amostrados para guiar a seleção e configuração de algoritmos. No entanto, a aplicação da ELA em problemas de alta dimensionalidade enfrenta três barreiras principais:

1. Efeitos de Esparsidade: A necessidade de amostras exponencialmente maiores para cobrir o espaço de busca.
2. Custo Computacional: O cálculo de certas classes de características (como mapas de células ou níveis) torna-se proibitivo em dimensões elevadas.
3. Variância Estocástica: As estimativas de características tornam-se instáveis com amostras limitadas.

Uma estratégia proposta para mitigar isso é a redução de dimensionalidade, projetando os pontos amostrados em um espaço de menor dimensão antes de calcular as características da ELA. O problema central investigado neste trabalho é: as características calculadas no espaço reduzido ainda refletem as propriedades intrínsecas da paisagem original, ou são distorcidas pela projeção?

2. Metodologia

Os autores investigaram a robustez das características da ELA sob a técnica de Embebedimentos Gaussianos Aleatórios (RGEs - Random Gaussian Embeddings). Diferente de métodos como PCA (que dependem dos dados), as RGEs utilizam projeções lineares aleatórias independentes da função objetivo.

• Configuração Experimental:
  • Benchmarks: Coleção de problemas BBOB (24 funções sem ruído) do framework COCO.
  • Dimensões: Dimensão original $D=20$.
  • Amostragem: Dois orçamentos de avaliação: limitado ($10 \cdot D = 200$ pontos) e abundante ($100 \cdot D = 2000$ pontos).
  • Redução de Dimensionalidade: Projeção para dimensões $d \in \{2, 5, 10\}$, resultando em taxas de compressão $r \in \{0.1, 0.25, 0.5\}$.
  • Repetição: 40 realizações independentes de matrizes de projeção aleatória para cada configuração, permitindo a análise da variabilidade induzida pela projeção.
• Métricas de Avaliação:
  • Definição de um deslocamento relativo de característica ($\delta$) para medir a diferença entre a característica calculada no espaço projetado e a referência no espaço original.
  • Análise de viés (bias) e variância das distribuições das características após a projeção.
  • Verificação de quais características são invariantes (não mudam) ou robustas (mudam pouco) à projeção.

3. Contribuições Principais

1. Investigação Sistemática: Primeiro estudo a analisar sistematicamente o impacto de múltiplas projeções aleatórias sobre um amplo conjunto de características da ELA (8 conjuntos de características, totalizando 54 features).
2. Identificação de Robustez vs. Informatividade: Demonstração de que a robustez (estabilidade numérica) não garante informatividade. Características podem ser estáveis na projeção, mas refletir artefatos da projeção em vez da paisagem original.
3. Análise de Distorção Topológica: Evidência de que projeções aleatórias podem induzir multimodalidade espúria e alterar a estrutura de vizinhança, distorcendo características baseadas em vizinhança local e geometria de níveis.
4. Guia Prático: Identificação de um subconjunto de características que permanecem estáveis sob redução de dimensionalidade, oferecendo diretrizes para o uso de ELA em cenários de alta dimensão com orçamento limitado.

4. Resultados Chave

• Distorção Geométrica e Topológica:

  • A projeção aleatória comprime e distorce a geometria do espaço de busca. Pontos distintos no espaço original podem colapsar em coordenadas idênticas no espaço projetado, enquanto a função objetivo varia ao longo dessas fibras.
  • Isso viola a suposição de cobertura uniforme e isotrópica do espaço, levando a agrupamentos artificiais (clustering) que são interpretados erroneamente como multimodalidade ou rugosidade da paisagem.

• Comportamento das Características:

  • Robustas/Invariantes: Características baseadas apenas nos valores de aptidão (fitness) (ex: ela_distr, fitness_distance.fitness_mean) são invariantes, pois não dependem da posição espacial dos pontos. Algumas características de meta-modelo (interceptos) e PCA também mostraram baixa sensibilidade.
  • Sensíveis: Características que dependem de relações de vizinhança (ex: nbc - nearest-better clustering) e informação de conteúdo (ex: ic) são altamente sensíveis. A projeção altera as distâncias relativas e a ordem dos vizinhos, distorcendo drasticamente esses valores.
  • Efeito de Tamanho de Amostra: A variância dos estimadores aumenta significativamente com a redução da amostra, mas a distorção sistemática (viés) é causada principalmente pela própria projeção, não apenas pelo tamanho da amostra.

• Convergência Enganosa:

  • O estudo identificou um fenômeno de "convergência consistente à projeção". Algumas características (como ela_level) parecem estabilizar em valores específicos no espaço projetado, mas esses valores não correspondem às propriedades intrínsecas da função original. Elas refletem a estrutura induzida pela projeção, não a função.

5. Significado e Conclusões

O trabalho conclui que a redução de dimensionalidade via projeções aleatórias não preserva fielmente as características da paisagem para a maioria das métricas da ELA.

• Implicações: O uso de características calculadas em espaços projetados para tarefas downstream (como seleção automática de algoritmos ou configuração) pode levar a decisões subótimas, pois as características podem estar capturando artefatos da projeção (como falsa multimodalidade) em vez da dificuldade real do problema.
• Recomendação: Embora um subconjunto de características (principalmente estatísticas de fitness e dispersão global) seja robusto, a maioria das características topológicas e de vizinhança deve ser evitada ou interpretada com extrema cautela em espaços projetados.
• Futuro: Os autores sugerem que a simples projeção aleatória não é uma solução mágica para a "maldição da dimensionalidade" na ELA. Trabalhos futuros devem investigar embebedimentos estruturados ou baseados em conhecimento a priori para preservar melhor as propriedades do problema.

Em suma, o artigo alerta que a redução de dimensionalidade introduz um "preço a pagar" em termos de fidelidade da paisagem, e que a estabilidade de uma característica sob projeção não é sinônimo de sua validade para descrever o problema original.