A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization

Resumo Técnico: Um Framework Unificado para Entropy Search e Expected Improvement em Otimização Bayesiana

Declaração do Problema
A Otimização Bayesiana (BO) é uma técnica padrão para otimizar funções de caixa-preta caras, dependendo de funções de aquisição (AFs) para equilibrar exploração e exploração. Existem dois paradigmas dominantes:

1. Expected Improvement (EI): Uma AF baseada em heurística que maximiza a melhoria esperada sobre o melhor valor observado atual. É computacionalmente eficiente e amplamente utilizada, mas é frequentemente vista como fundamentalmente distinta de métodos baseados em teoria da informação.
2. AFs Baseadas em Teoria da Informação (por exemplo, Max-value Entropy Search - MES): Esses métodos visam reduzir a incerteza sobre a localização ou o valor do ótimo global usando medidas baseadas em entropia. Embora fundamentados teoricamente, são frequentemente considerados distintos do EI devido a filosofias subjacentes diferentes.

A perspectiva predominante na comunidade de BO trata o EI e as AFs baseadas em teoria da informação como metodologias separadas. Este artigo desafia essa visão, argumentando que existe uma conexão teórica mais profunda entre eles que não havia sido reconhecida anteriormente.

Metodologia: Variational Entropy Search (VES)
Os autores introduzem o Variational Entropy Search (VES), um framework teórico unificado que interpreta o EI como uma aproximação de inferência variacional da Entropy Search de Valor Máximo (MES) baseada em teoria da informação.

• Unificação Teórica: O framework estabelece um limite inferior para a função de aquisição MES usando o limite de Barber-Agakov (BA). Ao definir uma família variacional $Q$ para aproximar a densidade condicional $p(y^* | D_t, y_x)$ (onde $y^*$ é o valor do máximo global), os autores derivam um Limite Inferior de Entropy Search (ESLBO).
• Recuperação do EI: Quando a família variacional $Q$ é restrita a distribuições exponenciais, a maximização do ESLBO produz uma solução idêntica ao Expected Improvement (EI) padrão. Isso prova que o EI é um caso especial do MES sob uma aproximação variacional específica.
• VES-Gamma: Reconhecendo que a distribuição exponencial é muito rígida para capturar a verdadeira estrutura de $p(y^* | D_t, y_x)$ (que é frequentemente não monotônica), os autores propõem o VES-Gamma. Esta nova AF usa uma distribuição Gamma como a família variacional. A distribuição Gamma generaliza a distribuição exponencial, permitindo uma aproximação mais flexível que captura melhor a forma da densidade.
• Otimização: O algoritmo VES-Gamma emprega uma abordagem no estilo Expectation-Maximization (EM). Ele iterativamente:
  1. Estima os parâmetros ($k, \beta$) da distribuição Gamma que maximizam o ESLBO para um ponto candidato fixo $x$.
  2. Atualiza o ponto candidato $x$ para maximizar o ESLBO dados os parâmetros atuais.
     Os parâmetros $k$ e $\beta$ são determinados automaticamente por meio de análise de derivadas e regularização, equilibrando dinamicamente os componentes da função objetivo.

Principais Contribuições

1. Framework Unificado: A introdução do framework VES, que demonstra que o EI é uma aproximação variacional do MES, unificando assim dois paradigmas de função de aquisição anteriormente distintos.
2. Nova Função de Aquisição: A proposta do VES-Gamma, uma AF que herda as forças de desempenho do EI enquanto incorpora princípios baseados em teoria da informação através de uma aproximação variacional Gamma mais flexível.
3. Avaliação Abrangente: Avaliações empíricas extensas em benchmarks sintéticos de baixa e alta dimensão, amostras de Processos Gaussianos (GP) e problemas do mundo real.

Resultados
O artigo avalia o VES-Gamma contra o EI, MES e outros métodos do estado da arte (como UCB e LogEI) em diversos benchmarks:

• Benchmarks Sintéticos: Em funções como Branin, Levy, Hartmann e Griewank, o VES-Gamma desempenha consistentemente de forma competitiva. Ele alcança o melhor desempenho no Branin e Hartmann, enquanto iguala ou supera ligeiramente o EI no Levy e Griewank.
• Amostras de GP: Em experimentos com priores de GP de 100 dimensões, o VES-Gamma supera significativamente tanto o EI quanto o MES para escalas de comprimento menores ($\ell = 0.05, 0.1, 0.25$), onde o EI e o MES tendem a convergir para soluções subótimas.
• Benchmarks do Mundo Real: Em problemas de alta dimensão (60D Rover, 124D Mopta08, 180D Lasso-DNA, 388D SVM), o VES-Gamma demonstra desempenho robusto. Ele supera significativamente todos os outros métodos no benchmark SVM e classifica-se entre os melhores desempenhos no Mopta08 e Lasso-DNA.
• Validação Teórica: Um teste de Kolmogorov-Smirnov confirma a equivalência empírica entre VES-Exp (a variante exponencial) e EI, com taxas de aprovação superiores a 90% em diversos benchmarks.

Significado e Afirmações
O artigo afirma que o framework VES fornece uma nova percepção teórica: a função de aquisição mais popular (EI) não é fundamentalmente distinta de métodos baseados em teoria da informação, mas sim uma aproximação variacional específica deles.

Ao unir essas perspectivas, os autores apresentam o VES-Gamma como uma função de aquisição robusta e versátil que equilibra efetivamente as forças do EI (desempenho e simplicidade) e do MES (redução de incerteza). Os resultados sugerem que o VES-Gamma é um forte candidato para diversos problemas de otimização, particularmente em configurações de alta dimensão onde métodos tradicionais podem ter dificuldades. Os autores observam que, embora o VES-Gamma incorra em um custo computacional mais alto por iteração do que o EI ou MES, isso é frequentemente insignificante em comparação com o custo de avaliar funções de caixa-preta caras em aplicações do mundo real. Trabalhos futuros são identificados como a exploração de distribuições variacionais alternativas e a extensão do framework para cenários ruidosos.