Sampling on Random Subspaces under Limited Data in the Context of Exploratory Landscape Analysis

Resumo Técnico: Amostragem em Subespaços Aleatórios sob Dados Limitados em Análise Exploratória de Paisagem

Definição do Problema
A Análise Exploratória de Paisagem (ELA) é uma metodologia baseada em dados utilizada para caracterizar problemas de otimização de caixa-preta, transformando vetores de decisão amostrados e valores de objetivo em características numéricas estruturadas. Esses descritores suportam tarefas subsequentes, como seleção de algoritmos, configuração e classificação de problemas. No entanto, a confiabilidade das características de ELA depende fortemente do tamanho da amostra. Em cenários de recursos restritos — comuns em otimização de alta dimensão ou aplicações do mundo real dispendiosas, onde as avaliações de função são custosas — os designs de preenchimento de espaço padrão (ex: Amostragem de Hipercubo Latino) frequentemente falham. Quando o orçamento de amostragem é limitado, esses designs resultam em uma cobertura esparsa do espaço de decisão, levando a uma alta variância e instabilidade nas estimativas das características, particularmente para aquelas que dependem de estruturas geométricas locais ou relações de vizinhança.

Metodologia
Para abordar o compromisso entre representatividade global e densidade de amostragem local, os autores propõem uma estratégia de amostragem baseada em embeddings lineares aleatórios. Em vez de distribuir um orçamento fixo uniformemente por todo o espaço ambiente de $D$ dimensões, o orçamento é realocado para subespaços afins de baixa dimensão e orientados aleatoriamente.

O estudo avalia quatro configurações específicas de amostragem em um cenário de 20 dimensões ($D=20$) usando o conjunto de testes BBOB sem ruído:

1. Full/ELAA: Amostragem uniforme no espaço ambiente total; características computadas no espaço ambiente.
2. Sliced/ELAA (Múltiplos Embeddings): O orçamento é dividido entre $K$ embeddings aleatórios de dimensão $d$. As amostras são geradas em cada subespaço, mapeadas de volta para o espaço ambiente, e as características são computadas sobre a união desses pontos.
3. All_in/ELAA (Embedding Único, Avaliação no Ambiente): Todo o orçamento é alocado a um único embedding aleatório. Os pontos são mapeados para o espaço ambiente para avaliação, e as características são computadas no espaço ambiente.
4. All_in/ELAR (Embedding Único, Avaliação Reduzida): Todo o orçamento é alocado a um único embedding aleatório. Os pontos são avaliados no espaço ambiente, mas as características são computadas diretamente dentro do subespaço reduzido de dimensão $d$.

As matrizes de embedding são geradas usando distribuições normais padrão, com normalização de coluna opcional para preservar as distâncias euclidianas. Para lidar com restrições de contorno, as amostras geradas no espaço de embedding são mapeadas para o espaço ambiente e limitadas ao domínio viável. O estudo utiliza razões de compressão ($r = d/D$) de 0,1, 0,25 e 0,5.

Principais Contribuições

• Proposta de uma Nova Estratégia de Amostragem: Os autores introduzem um método que realoca um orçamento de avaliação fixo para subespaços de baixa dimensão gerados aleatoriamente para aumentar a densidade de amostragem efetiva, evitando as distorções artificiais associadas à projeção de pontos pré-amostrados.
• Análise Empírica de Estabilidade: O artigo realiza uma comparação abrangente da estabilidade de características entre a amostragem de espaço total e a amostragem baseada em embedding entre seis conjuntos de características clássicas de ELA (incluindo ela_distr, ela_level, ela_meta, nbc, disp e ic) e 24 funções BBOB.
• Análise de Razões de Compressão: O estudo investiga o impacto de variar as razões de compressão, destacando o compromisso entre o aumento da densidade de amostragem e a perda de informação.
• Protocolo de Avaliação: Os autores avaliam a confiabilidade dessas estratégias medindo a distância de Wasserstein-1 entre as distribuições de características obtidas sob orçamentos limitados e uma distribuição de referência de alta fidelidade (2000 amostras).

Resultados
Os resultados experimentais, agregados sobre 40 sementes aleatórias por configuração, revelam que a eficácia da estratégia de amostragem é altamente dependente da classe específica de característica e da paisagem do problema subjacente:

• Dependência de Características:
  • Características de metamodelo (ela_meta): A amostragem de espaço total (Full/ELAA) geralmente supera os métodos de subespaço, pois estas características dependem de cobertura global para ajustar modelos lineares.
  • Dispersão (disp) e Conteúdo de Informação (ic): A amostragem baseada em embedding, particularmente com uma razão de compressão moderada ($r=0,5$), frequentemente iguala ou supera a amostragem de espaço total, sugerindo que estas características são robustas à amostragem localizada.
  • Características de nível de contorno (ela_level): Estratégias envolvendo um único embedding com computação de característica no espaço reduzido (All_in/ELAR) alcançam consistentemente os rankings superiores.
• Impacto da Razão de Compressão: A compressão agressiva (ex: $r=0,1$) degrada sistematicamente o desempenho na maioria dos conjuntos de características, indicando que reter um nível moderado de informação da paisagem é necessário. Uma razão de $r=0,5$ fornece o melhor compromisso geral.
• Desempenho Geral: A estratégia Sliced/ELAA com $r=0,5$ atinge o melhor ranking de consenso, performando consistentemente bem tanto em agregações de características quanto de funções. No entanto, nenhum método é estatisticamente superior em todos os cenários.

Significância e Alegações
O artigo conclui que, sob orçamentos de avaliação limitados, a prática padrão de amostragem uniforme em espaço total é frequentemente subótima para caracterizar paisagens de problemas. Os autores alegam que a amostragem estruturada em subespaços constitui uma alternativa promissora que pode melhorar a estabilidade de subconjuntos específicos de características de ELA.

A significância deste trabalho reside em mudar a perspectiva da amostragem de um passo passivo de coleta de dados para uma escolha de design ativa. Ao demonstrar que concentrar amostras dentro de subespaços informativos pode gerar descritores mais confiáveis do que distribuí-las esparsamente pelo espaço total, os autores fornecem um mecanismo prático para aumentar a caracterização de paisagens em cenários de otimização com recursos restritos. O estudo reconhece limitações, observando que a abordagem é atualmente validada em benchmarks de 20 dimensões e que características que dependem de estrutura global ainda podem enfrentar dificuldades sob amostragem localizada. Sugere-se que trabalhos futuros explorem benchmarks com baixa dimensionalidade intrínseca e avaliem o impacto destas estratégias em tarefas de seleção de algoritmos subsequentes.