Resumo Técnico: Busca de Modelo de Desconto para Otimização de Diversidade de Qualidade em Espaços de Medida de Alta Dimensão

Definição do Problema

A otimização de Diversidade de Qualidade (DQ) visa descobrir uma coleção de soluções que maximizam uma função objetivo $f$ enquanto cobrem simultaneamente uma gama diversificada de saídas definida por uma função de medida vetorial, especificada pelo usuário, $m$. A imagem de $m$ constitui o espaço de medida $S$. Uma limitação crítica nos algoritmos de DQ contemporâneos, particularmente nos métodos mais avançados como Adaptação de Matriz de Covariância MAP-Annealing (CMA-MAE), é a sua incapacidade de escalar efetivamente para espaços de medida de alta dimensão.

Em espaços de alta dimensão, os algoritmos sofrem de distorção, um fenômeno onde grandes volumes do espaço de soluções mapeiam para pequenas regiões do espaço de medida. O CMA-MAE aborda o objetivo de DQ maximizando a "melhoria do arquivo", definida como $\Delta(\theta) = f(\theta) - f_A(m(\theta))$, onde $f_A$ é uma função de desconto. O CMA-MAE representa $f_A$ como um histograma discreto (uma tesselação de células). Em configurações de alta dimensão, a distorção faz com que muitas soluções distintas caiam na mesma célula do histograma, atribuindo-lhes valores de desconto idênticos. Consequentemente, o algoritmo não consegue distinguir entre soluções com medidas semelhantes, levando a sinais de melhoria imprecisos e estagnação da busca. Além disso, projetar funções de medida de baixa dimensão para domínios complexos (por exemplo, especificar "onde um caminhante está localizado") é frequentemente tedioso e contra-intuitivo.

Metodologia: Busca de Modelo de Desconto (DMS)

Para abordar essas limitações, os autores propõem a Busca de Modelo de Desconto (DMS). Em vez de usar um histograma discreto, o DMS emprega uma rede neural para aprender uma representação suave e contínua da função de desconto $f_A$.

Componentes Principais

1. Modelo de Desconto ($\hat{f}_A$): Uma rede neural parametrizada por $\psi$ que recebe valores de medida $s = m(\theta)$ como entrada e produz um valor de desconto escalar. A arquitetura é flexível: Perceptrons Multicamada (MLPs) são usados para medidas vetoriais de baixa dimensão, enquanto Redes Convolucionais ou Transformadores são adequados para dados de alta dimensão, como imagens.
2. Arquivo e Emissores: O DMS mantém um arquivo no estilo MAP-Elites que armazena as melhores soluções encontradas. Utiliza emissores baseados em CMA-ES que amostram soluções de uma distribuição Gaussiana. Diferentemente do CMA-MAE, o arquivo não armazena valores de desconto discretos; em vez disso, o modelo de desconto é consultado para calcular os valores de melhoria $\Delta_i = f(\theta_i) - \hat{f}_A(m(\theta_i))$.
3. Treinamento do Modelo de Desconto: O modelo é treinado para aproximar a regra de atualização de limiar usada no CMA-MAE. O conjunto de dados de treinamento $D_A$ consiste em duas fontes:
   • Amostras dos Emissores: Para cada solução amostrada $\theta$, o valor de desconto alvo $t_A$ é atualizado com base em se a função objetivo da solução $f(\theta)$ excede a previsão atual do modelo $\hat{f}_A(s)$. Se $f(\theta) > \hat{f}_A(s)$, o alvo é uma combinação linear da função objetivo e do desconto atual, controlada por uma taxa de aprendizado do arquivo $\alpha$.
   • Pontos Vazios: Para evitar que o modelo atribua valores arbitrariamente altos a regiões inexploradas do espaço de medida, o algoritmo amostra os centros de células do arquivo não ocupadas e lhes atribui um valor alvo de $f_{min}$ (o mínimo da função objetivo). Isso "segura" o modelo em áreas inexploradas, garantindo que os emissores sejam guiados a explorar novas regiões.

Insight Teórico

Ao substituir o histograma discreto por uma função contínua, o DMS pode atribuir valores de desconto distintos a soluções, mesmo quando elas mapeiam para medidas semelhantes em um espaço de alta dimensão. Isso permite que o algoritmo mantenha um gradiente de sinais de melhoria, prevenindo a estagnação e permitindo a exploração contínua muito depois de métodos baseados em histograma falharem.

Contribuições Principais

1. Busca de Modelo de Desconto (DMS): Um algoritmo de DQ inovador que utiliza um modelo de desconto suave e contínuo para guiar a exploração em espaços de medida distorcidos e de alta dimensão.
2. Diversidade de Qualidade com Conjuntos de Dados de Medidas (QDDM): Os autores introduzem uma nova configuração onde os usuários especificam medidas desejadas por meio de um conjunto de dados (por exemplo, uma coleção de imagens) em vez de projetar manualmente uma função de medida. Isso trata o espaço de alta dimensão do conjunto de dados (por exemplo, o espaço de imagens) como o espaço de medida.
3. Novos Domínios: Dois domínios QDDM são propostos e avaliados:
   • Arranjo de Triângulos (TA): Arranjar triângulos para corresponder a imagens do MNIST ou Fashion MNIST.
   • Iluminação de Espaço Latente (LSI) (Caminhante): Gerar imagens de rostos de caminhantes em paisagens diversas usando StyleGAN3, onde o espaço de medida é o espaço de imagens de paisagens.
4. Validação Empírica: Benchmarks extensivos mostrando que o DMS supera o CMA-MAE, DDS e variantes do MAP-Elites em benchmarks padrão e nos novos domínios QDDM.

Resultados Experimentais

Os autores avaliaram o DMS em 9 benchmarks padrão (incluindo Projeção Linear e Repertório de Braço) e 3 domínios QDDM.

• Domínios de Benchmark: O DMS superou significativamente todas as linhas de base na Pontuação de DQ (soma das funções objetivo no arquivo) e na Cobertura (porcentagem de células do arquivo preenchidas) na maioria das configurações de alta dimensão (por exemplo, benchmarks LP de 10D, 20D, 50D). Notavelmente, no benchmark LP (Esfera) de 10D, a cobertura do CMA-MAE caiu para 6,95%, enquanto o DMS alcançou 89,21%.
• Domínios QDDM:
  • Em TA (F-MNIST), o DMS superou significativamente todas as linhas de base em ambas as métricas.
  • Em TA (MNIST), o DMS igualou o CMA-MAE em cobertura, mas superou significativamente as variantes do MAP-Elites na Pontuação de DQ. Os autores observam que o DMS não superou significativamente o CMA-MAE na Pontuação de DQ aqui, especulando que o ruído introduzido pela aproximação da rede neural pode prejudicar a otimização de função objetivo de alta precisão em tarefas de baixa distorção.
  • Em LSI (Caminhante), o DMS superou significativamente o CMA-MAE, alcançando uma Pontuação de DQ de 214,91 comparada a 14,61, e uma cobertura de 3,77% (377 imagens únicas de caminhantes). Os autores observam que as variantes do MAP-Elites alcançaram alta cobertura, mas com grandes pontuações de DQ negativas devido à geração de imagens fora da distribuição de treinamento do gerador.
• Custo Computacional: O DMS incorre em um custo computacional maior que o CMA-MAE devido ao treinamento do modelo de desconto, particularmente em benchmarks de baixa dimensão. No entanto, em domínios QDDM onde a geração de imagens é o gargalo, a sobrecarga é menos perceptível.

Significado e Alegações

O artigo afirma que o DMS oferece dois benefícios principais:

1. Melhoria de Desempenho: O DMS aprimora o desempenho nas aplicações atuais de DQ ao superar os efeitos de distorção que afligem espaços de medida de alta dimensão, superando algoritmos de caixa-preta mais avançados.
2. Acessibilidade e Novas Aplicações: Ao introduzir a configuração QDDM, o DMS torna a DQ mais acessível. Ele alivia a necessidade de funções de medida manuais e projetadas à mão, permitindo que os usuários especifiquem objetivos de diversidade simplesmente fornecendo um conjunto de dados. Isso permite a especificação de medidas complexas e de alta dimensão (como estilos visuais ou localizações semânticas) que são difíceis de representar com vetores de baixa dimensão.

Os autores concluem que, dada a onipresença de conjuntos de dados em aprendizado de máquina, enquadrar problemas como QDDM e resolvê-los com DMS é uma direção promissora. Eles reconhecem limitações, incluindo a sobrecarga computacional do treinamento do modelo e o potencial de ruído de aproximação afetar a otimização fina, sugerindo trabalho futuro em arquiteturas de modelo mais avançadas e alvos de treinamento alternativos.