Resumo Técnico: BEACON

Formulação do Problema

O artigo aborda o desafio da Busca de Novidade (Novelty Search - NS) no contexto de sistemas de caixa-preta caros e ruidosos, comuns na química, ciência dos materiais e design molecular. Diferente da otimização tradicional, que busca um único ótimo escalar, o objetivo aqui é descobrir um conjunto diversificado de comportamentos (resultados) alcançáveis dentro de um orçamento limitado de avaliações.

Formalmente, o problema envolve uma função de caixa-preta multivariada $f: \mathcal{X} \to \mathcal{O}$, onde $\mathcal{X} \subset \mathbb{R}^d$ é o espaço de entrada e $\mathcal{O} \subset \mathbb{R}^n$ é o espaço de resultados (comportamento). O objetivo é maximizar a alcançabilidade (reachability), definida como a fração de regiões de comportamento distintas descobertas dentro de uma partição finita do espaço de resultados.

Os métodos de NS existentes, frequentemente baseados em meta-heurísticas como algoritmos evolucionários, são tipicamente ineficientes em termos de amostragem. Eles têm dificuldade em cenários onde cada avaliação de função (por exemplo, uma simulação ou experimento físico) é custosa. Além disso, a Otimização Bayesiana (BO) padrão é mal adequada porque colapsa os resultados em uma única função de utilidade, podendo negligenciar comportamentos intermediários ou raros que são cientificamente valiosos.

Metodologia: BEACON

Os autores propõem o BEACON (Bayesian Exploration Algorithm for outCOme Novelty), uma estratégia de eficiência de amostragem inspirada nos princípios da Otimização Bayesiana, mas adaptada para a busca de novidade.

Componentes Principais

1. Surrogate de Processo Gaussiano Multivariado (MOGP):
   Em vez de modelar um objetivo escalar, o BEACON coloca um modelo substituto probabilístico diretamente no mapeamento entrada-resultado $f$. O framework utiliza MOGPs para modelar a função multivariada completa. Na maioria dos experimentos, os autores utilizam modelos de GP de saídas independentes (ajustando um GP escalar por coordenada de saída) para manter a simplicidade, embora o framework suporte saídas correlacionadas e kernels cientes da química (ex: Tanimoto-fragprint) para domínios específicos.

2. Função de Aquisição Baseada em Thompson Sampling:
   O BEACON introduz uma nova função de aquisição que pontua candidatos de entrada com base na distância de seus resultados plausíveis de um arquivo (archive) de resultados observados anteriormente, que foi filtrado por ruído.

   • Denoising (Redução de Ruído): As observações brutas são substituídas pelas previsões da média posterior ($\mu_D$) para mitigar os efeitos do ruído de observação.
   • Quantificação de Incerteza: O algoritmo extrai uma função amostral $g(x)$ da posterior do MOGP (usando Thompson sampling).
   • Pontuação: A pontuação de novidade $\alpha_{NS}$ para um candidato $x$ é a distância média entre o resultado amostrado $g(x)$ e os $k$ vizinhos mais próximos no arquivo filtrado:
     $$\alpha_{NS}(x | g, D) = \frac{1}{k} \sum_{i=1}^{k} \text{dist}(g(x), \mu_D(x_i^*))$$
   • Otimização: Esta função de aquisição é otimizada usando métodos baseados em gradiente (ex: L-BFGS-B) com múltiplos reinícios. O uso de relaxações diferenciáveis para a operação de ordenação no cálculo do $k$-vizinho mais próximo permite a maximização eficiente via gradiente.

3. Extensões:

   • Escalabilidade para Alta Dimensionalidade: Para espaços de entrada de alta dimensão, o BEACON integra priors SAAS (Sparse Axis-Aligned Subspace) para induzir esparsidade nas escalas de comprimento do GP, ou utiliza surrogates cientes da química (ex: kernels moleculares) para entradas discretas estruturadas.
   • Restrições Guiadas pelo Usuário (UG-BEACON): O framework permite que usuários definam partições do espaço de resultados para excluir regiões já exploradas ou focar esforços de busca em regimes de interesse específicos.

Principais Contribuições

O artigo delineia quatro contribuições primárias:

1. Desenvolvimento de Algoritmo: Introdução do BEACON, um novo algoritmo de NS projetado especificamente para sistemas de caixa-preta caros e ruidosos que melhora a alcançabilidade do espaço de comportamento com avaliações limitadas.
2. Nova Estratégia de Aquisição: Uma função de aquisição baseada em Thompson sampling que opera em um espaço de resultados contínuo. Ela considera a incerteza preditiva e o ruído observacional sem exigir a otimização direta sobre uma partição de comportamento fixa e discretizada.
3. Escalabilidade: Extensões para configurações de alta dimensão via priors que induzem esparsidade e modelagem de surrogate específica do domínio (ex: grafos moleculares).
4. Validação Empírica: Demonstração da eficácia do algoritmo através de benchmarks sintéticos, descoberta de materiais (Metal-Organic Frameworks), descoberta de propriedades moleculares e tarefas de aprendizado por reforço.

Resultados

Os autores avaliaram o BEACON contra diversos baselines, incluindo busca de novidade evolucionária (NS-EA), busca de distância para área explorada (NS-DEA), amostragem de variância máxima e busca aleatória.

• Benchmarks Sintéticos: Nas funções Ackley, Rosenbrock e Styblinski-Tang, o BEACON alcançou consistentemente a maior alcançabilidade, particularmente em espaços de entrada de maior dimensão (até 12 dimensões). Também superou os baselines em um problema multivariado sintético com uma distribuição de cauda longa, cobrindo efetivamente regiões de baixa densidade que outros métodos perderam.
• Descoberta de Materiais: Em tarefas envolvendo absorção de Hidrogênio, absorção de Nitrogênio e absorção conjunta de CO2/CH4 em Metal-Organic Frameworks (MOFs), o BEACON alcançou a cobertura total do espaço de comportamento discretizado dentro do orçamento de avaliação, superando os baselines aplicáveis.
• Descoberta Molecular: Para solubilidade em água, ESOL (solubilidade aquosa com entradas de 2.133 dimensões) e tarefas de LogD, o BEMA demonstrou cobertura superior. O uso de kernels específicos da tarefa (Tanimoto-fragprint) e priors SAAS foi crítico para o desempenho em espaços moleculares de alta dimensão.
• Paisagens Deceptivas: Em uma tarefa de navegação de labirinto de aprendizado por reforço com uma paisagem de recompensa deceptiva, o BEACON foi o único método a resolver consistentemente a tarefa em todas as réplicas, enquanto métodos orientados por recompensa (como Expected Improvement) e outros baselines de novidade falharam em escapar de armadilhas locais.
• Descoberta Guiada pelo Usuário: Em tarefas com restrições (descoberta de dígitos MNIST e design de materiais absorventes de óleo), o UG-BEACON incorporou com sucesso as preferências do usuário para descobrir comportamentos alvo mais rapidamente do que as versões não restritas.

Significância e Alegações

O artigo afirma que o BEACON torna a exploração orientada pela novidade prática para domínios onde as abordagens evolucionárias tradicionais são muito ineficientes em termos de amostragem. Ao alavancar a modelagem de surrogate Bayesiana, o BEACON pode direcionar as avaliações para regiões inexploradas do espaço de resultados, contabilizando rigorosamente a incerteza do modelo e o ruído.

Os autores posicionam o BEACON como uma ferramenta para cenários de descoberta de baixos dados, onde o objetivo científico é a cobertura ampla de propriedades alcançáveis, em vez de um único ótimo. Eles sugerem que esta abordagem é particularmente valiosa para fluxos de trabalho de experimentação autônoma em química e ciência dos materiais, onde descobrir fenômenos previamente não vistos é tão crítico quanto otimizar alvos conhecidos.

O artigo reconhece limitações em relação a espaços de resultados "bruscos" (ex: mudanças de fase) onde o modelo de surrogate pode suavizar excessivamente saltos abruptos, observando que a descoberta nesses casos ainda pode depender de exploração ampla ou amostragem por chance se não houver uma estrutura aprendível. No entanto, argumentam que o framework é flexível o suficiente para incorporar estratégias híbridas (ex: inicialização de preenchimento de espaço) para mitigar esses problemas.