Stage-dependent integer-binary encoding in factorization-machine black-box optimization

Resumo Técnico: Codificação inteiro-binária dependente de estágio em otimização de caixa-preta com máquinas de fatoração

Enunciado do Problema
A otimização de caixa-preta (BBO) aborda problemas onde as funções objetivo carecem de formas analíticas explícitas e são caras para serem avaliadas. O Factorization Machine with Quadratic-optimization Annealing (FMQA) é uma abordagem proeminente de BBO que constrói um modelo substituto utilizando uma Máquina de Fatoração (FM) e o otimiza por meio de uma máquina de Ising. Um componente crítico do FMQA é a conversão de variáveis inteiras ou contínuas em variáveis binárias via codificação inteiro-binária (ex: one-hot, domain-wall ou codificação binária) para formular o problema como um modelo de Otimização Binária Quadrática Não Restrita (QUBO).

O FMQA convencional emprega um único método de codificação inteiro-binária durante ambas as etapas de construção do modelo substituto (aprendizado de máquina) e de busca de solução (otimização da máquina de Ising). No entanto, pesquisas anteriores sugerem um compromisso (trade-off): a codificação domain-wall frequentemente produz um desempenho de busca de solução superior em máquinas de Ising, enquanto a codificação one-hot tem sido observada como produtora de valores de função objetivo mais baixos no processo de otimização global do FMQA. Essa discrepância implica que a codificação ideal para aprender o panorama (landscape) do substituto pode diferir da codificação ideal para buscar esse panorama. Métodos convencionais, ao fixar uma única codificação, podem falhar em explorar plenamente as capacidades distintas da FM e da máquina de Ising.

Metodologia
Os autores propõem um framework FMQA dependente de estágio que utiliza diferentes métodos de codificação inteiro-binária para as etapas de aprendizado de máquina e de busca de solução. O núcleo desta abordagem envolve:

1. Estratégia de Codificação Dupla: O framework treina o modelo substituto FM usando uma codificação adequada para o aprendizado (especificamente a codificação one-hot na variante "OhDw" proposta) e, em seguida, converte o modelo substituto resultante em uma codificação diferente adequada para a busca (especificamente a codificação domain-wall) antes da otimização pela máquina de Ising.
2. Conversão de Matriz QUBO: Para permitir essa alternância, os autores derivaram fórmulas de conversão matemática entre as matrizes QUBO de codificações one-hot e domain-wall. Essas fórmulas garantem que o panorama da função objetivo do substituto seja preservado sobre estados inteiros viáveis até uma constante aditiva.
   • A conversão de one-hot para domain-wall envolve a transformação de termos diagonais e fora da diagonal da matriz QUBO $Q^{(oh)}$ para $Q^{(dw)}$ usando relações de somatório específicas (Eqs. 18–20).
   • A conversão inversa (domain-wall para one-hot) também é derivada (Eqs. 22–24).
   • A complexidade computacional para essas conversões mútuas é estabelecida como $O(N^2q^2)$, onde $N$ é a dimensão de entrada e $q$ é o número de níveis de discretização.
3. Fluxo de Trabalho Algorítmico:
   • Etapa de Aprendizado: Uma FM é treinada em dados de entrada-saída codificados usando codificação one-hot.
   • Conversão: O modelo substituto treinado (representado como uma matriz QUBO) é convertido de codificação one-hot para domain-wall.
   • Etapa de Busca: O QUBO convertido, aumentado com restrições de codificação domain-wall, é otimizado usando uma máquina de Ising (Fixstars Amplify Annealing Engine) para encontrar soluções candidatas.
   • Avaliação: As soluções são decodificadas, avaliadas contra a verdadeira função de caixa-preta e adicionadas ao conjunto de dados de treinamento para a próxima iteração.

Principais Contribuições

1. Proposta de Framework: Introdução de um framework FMQA que desacopla a escolha de codificação entre as etapas de aprendizado e de busca, em vez de fixar uma única codificação durante todo o processo.
2. Derivação Teórica: Derivação de fórmulas de conversão mútua entre matrizes QUBO one-hot e domain-wall que preservam o panorama da função objetivo do substituto sobre estados viáveis, permitindo a troca de codificações sem perder a fidelidade do modelo aprendido.
3. Decomposição Empírica: Uma decomposição numérica dos efeitos da codificação inteiro-binária em contribuições da etapa de aprendizado de máquina e da etapa de busca de solução, avaliando-as separadamente para entender seus distintos impactos no desempenho.

Resultados Experimentais
O método proposto foi avaliado na função Rastrigin, um problema de teste multimodal, com dimensões de entrada $N \in \{2, 5\}$ e níveis de discretização $q \in \{61, 301\}$. O desempenho do método "OhDw" proposto (one-hot para aprendizado, domain-wall para busca) foi comparado contra variantes de codificação única convencional (Oh, Dw, Bi) e Otimização Bayesiana (BO).

• Dominância da Codificação da Etapa de Aprendizado: Em todas as condições, a codificação usada na etapa de aprendizado foi o fator dominante que governou o desempenho da otimização. Métodos que empregam codificação one-hot para o aprendizado (Oh e OhDw) alcançaram consistentemente erros residuais menores do que aqueles que usam codificação domain-wall ou binária para o aprendizado.
• Benefícios Dependentes de Estágio: O benefício de mudar para a codificação domain-wall para a etapa de busca foi dependente da condição:
  • Para $N=5$ e $q=301$ (discretização mais fina, espaço de busca maior), o método OhDw alcançou erros residuais menores e soluções mais próximas do ótimo global em comparação ao método Oh (apenas one-hot).
  • Para $N=5$ e $q=61$, o método Oh superou ligeiramente o OhDw.
  • Para $N=2$, não foi observada diferença significativa de desempenho entre Oh e OhDw.
• Estabilidade de Busca: A análise da etapa de busca de solução indicou que a codificação domain-wall permite transições mais estáveis entre estados viáveis na máquina de Ising, enquanto a codificação one-hot exige a passagem por estados que violam restrições, potencialmente reduzindo a estabilidade da busca.

Significância e Alegações
O artigo alega que a escolha da codificação inteiro-binária não é meramente uma escolha de representação, mas um elemento de design que serve papéis distintos nas etapas de aprendizado e de busca de solução do FMQA. O principal achado é que a codificação one-hot na etapa de aprendizado é o principal motor do desempenho da otimização, provavelmente devido à sua capacidade superior de construir um modelo substituto preciso. No entanto, o estudo demonstra que empregar codificações dependentes de estágio — especificamente combinando one-hot para aprendizado com domain-wall para busca — pode proporcionar melhorias adicionais, particularmente em cenários com maiores dimensões de entrada e discretização mais fina, onde o espaço de busca é mais complexo.

Os autores concluem que, embora o método OhDw mostre promessa, sua generalidade requer validação adicional em uma variedade mais ampla de funções de teste e problemas de otimização de design do mundo real. Adicionalmente, a análise sistemática da sensibilidade aos coeficientes de penalidade e às diferenças de densidade de QUBO permanece como uma direção para trabalhos futuros.