Improving FMQA via Initial Training Data Design Considering Marginal Bit Coverage in One-Hot Encoding

Este artigo propõe aprimorar o algoritmo de Máquinas de Fatoração com Recozimento de Otimização Quadrática (FMQA) projetando dados de treinamento iniciais usando os métodos de amostragem de hipercubo latino e de Sobol' para garantir a cobertura completa de bits marginais na codificação one-hot, melhorando assim o desempenho de otimização em problemas de variáveis inteiras e contínuas discretizadas.

O essencial

Imagine que você está tentando encontrar a forma perfeita para a asa de um avião movido a energia humana. Você quer que ele voe o mais rápido possível, mas a física envolvida é tão complexa que você não consegue escrever uma fórmula simples para prever a velocidade. Em vez disso, você precisa construir um modelo virtual, testá-lo, ver quão rápido ele vai e, em seguida, tentar novamente. Este é um problema de "caixa preta": você insere um projeto e uma velocidade sai, mas você não conhece a receita secreta no interior.

Para resolver isso, os pesquisadores usam um programa de computador inteligente chamado FMQA. Pense no FMQA como uma equipe de detetives em duas etapas:

1. O Substituto (O Estudante): Um modelo de aprendizado de máquina que tenta adivinhar a resposta com base em testes passados.
2. O Buscador (O Caçador): Um computador especializado (uma "máquina de Ising") que usa as suposições do estudante para caçar a melhor forma possível de asa.

O Problema: Os Bits "Silenciosos"

Para fazer o computador entender a forma da asa, os pesquisadores traduzem as variáveis de projeto contínuas (como "comprimento da asa") em uma sequência de interruptores binários (0s e 1s) usando um método chamado codificação one-hot.

Imagine que você tem 32 interruptores para o "comprimento da asa". Para dizer que o comprimento é "médio", você liga exatamente um desses 32 interruptores para "LIGADO" (1) e deixa os outros 31 "DESLIGADOS" (0).

O artigo identifica uma falha na forma como eles geralmente iniciam esse processo. Eles tipicamente escolhem as formas de asa iniciais rolando dados (amostragem aleatória).

• O Problema: Se você rolar os dados apenas 32 vezes para começar, há uma alta probabilidade (cerca de 36%) de que alguns desses 32 interruptores nunca sejam ligados para "LIGADO" durante a fase inicial.
• A Consequência: O "Estudante" (o modelo de aprendizado de máquina) aprende olhando para os interruptores que estavam ligados. Se um interruptor nunca esteve ligado, o Estudante nunca aprende como aquela configuração específica afeta a velocidade. É como um professor tentando avaliar um aluno que nunca levantou a mão; o professor não tem dados sobre a capacidade daquele aluno.
• O Resultado: O "mapa" do computador do problema tem pontos cegos. Quando o "Caçador" vai procurar a melhor solução, ele pode ignorar áreas boas porque o mapa diz: "Não temos ideia do que acontece aqui".

A Solução: A Estratégia de "Amostragem Justa"

Os autores propõem uma nova maneira de escolher as formas de asa iniciais. Em vez de apenas rolar dados, eles usam duas ferramentas matemáticas chamadas Amostragem Hipercúbica Latina (LHS) e a sequência de Sobol'.

Pense nessas ferramentas como um inspetor de justiça.

• Em vez de esperar que a sorte ligue cada interruptor, o inspetor garante que cada um dos 32 interruptores seja ligado para "LIGADO" pelo menos uma vez durante os 32 testes iniciais.
• Isso garante que o "Estudante" receba uma lição direta sobre cada configuração possível antes que a busca real comece. Nenhum interruptor fica no escuro.

Os Resultados: Asas Melhores, Mais Rápidas

Os pesquisadores testaram isso em duas versões do problema da asa de avião: uma com 17 variáveis de projeto e uma mais difícil com 32 variáveis.

1. O "Método Antigo" (Aleatório): Mesmo após executar 200 testes, cerca de 36% dos interruptores nunca foram ligados nos dados iniciais. O desempenho do computador era aceitável, mas tinha pontos cegos.
2. O "Novo Método" (LHS e Sobol'): Cada interruptor foi ligado pelo menos uma vez desde o início.
   • O Resultado: Os novos métodos encontraram formas de asa que voaram mais rápido do que o antigo método aleatório.
   • A Diferença: A melhoria foi pequena para o problema mais simples, mas tornou-se muito mais óbvia para o problema mais difícil, de 32 variáveis. É como se os pontos cegos no mapa importassem mais quando o terreno ficava mais complexo.

A Conclusão

O artigo não afirma que isso faz o computador voar o avião em si, nem afirma que isso resolve todos os problemas de otimização. Ele simplesmente mostra que como você começa importa.

Ao usar uma estratégia de "amostragem justa" para garantir que cada opção possível tenha a chance de ser vista nos dados iniciais de treinamento, o computador aprende um mapa melhor do problema. Isso permite que ele encontre melhores soluções mais rápido, especialmente quando o problema se torna complicado. É um lembrete de que, na otimização, você não precisa apenas de um mecanismo de busca inteligente; você precisa de uma maneira inteligente de iniciar a jornada.

Resumo técnico

Resumo Técnico: Melhoria do FMQA via Projeto de Dados Iniciais de Treinamento Considerando a Cobertura Marginal de Bits em Codificação One-Hot

Declaração do Problema
A Máquina de Fatoração com Recozimento de Otimização Quadrática (FMQA) é um método de otimização de caixa preta (BBO) que combina um modelo substituto de Máquina de Fatoração (FM) com uma Máquina de Ising para busca. Quando a FMQA é aplicada a variáveis inteiras ou contínuas discretizadas usando codificação one-hot, surge uma questão crítica com a amostragem inicial aleatória uniforme. Neste cenário, muitas variáveis binárias (bits) no conjunto de dados inicial de treinamento podem nunca assumir o valor "1". Como o gradiente da saída da FM em relação aos parâmetros associados a um bit específico é proporcional ao valor desse bit, os parâmetros correspondentes a bits que permanecem "0" em todo o conjunto de dados inicial não recebem atualizações diretas de gradiente a partir das respostas observadas. Consequentemente, esses parâmetros evoluem exclusivamente com base na inicialização e no decaimento de pesos, introduzindo viés nos coeficientes estimados da Otimização Binária Não Constrained Quadrática (QUBO). Esse viés pode degradar a qualidade da busca de solução realizada pela Máquina de Ising, particularmente em problemas de dimensões mais elevadas.

Metodologia
Os autores propõem uma modificação ao framework FMQA focada no projeto dos dados iniciais de treinamento. O objetivo central é alcançar cobertura marginal completa de bits, garantindo que toda variável binária obtida via codificação one-hot assuma o valor "1" pelo menos uma vez no conjunto de dados inicial.

Para realizar isso, os autores introduzem dois métodos de geração de dados iniciais baseados em técnicas de amostragem de preenchimento de espaço:

1. LHS-FMQA: Utiliza Amostragem Hipercúbica Latina (LHS).
2. Sobol'-FMQA: Utiliza a sequência de Sobol' (uma sequência determinística de baixa discrepância).

Ambos os métodos são configurados de modo que o número de amostras iniciais ($N_0$) seja igual ao número de valores discretos por variável ($M$). Sob a codificação one-hot, onde cada variável original é representada por $M$ bits binários, definir $N_0 = M$ permite que essas estratégias de amostragem garantam que cada valor discreto seja selecionado pelo menos uma vez. Através do mapa de decodificação, isso assegura que cada bit binário correspondente assuma o valor "1" pelo menos uma vez. Isso garante que todos os parâmetros da FM recebam atualizações diretas de gradiente derivadas do conjunto de dados durante a fase inicial de treinamento, mitigando o viés causado por bits "nunca ativos".

Principais Contribuições

• Identificação de um Mecanismo de Viés: O artigo identifica formalmente que a amostragem aleatória uniforme na FMQA codificada one-hot leva a bits "nunca ativos", fazendo com que parâmetros específicos da FM não sejam informados pelas respostas observadas da caixa preta.
• Estratégia de Inicialização Proposta: Os autores propõem e implementam projetos de dados iniciais de treinamento usando sequências LHS e Sobol' especificamente para impor a cobertura marginal de bits ($N_0 = M$).
• Validação Empírica: Os métodos são avaliados no benchmark de otimização da forma da asa de Aeronaves de Propulsão Humana (HPA) (HPA103), um problema de engenharia complexo com restrições implícitas e sem informação de gradiente analítico. Os experimentos foram conduzidos em duas escalas de problema: 17 variáveis de projeto (HPA103-1) e 32 variáveis de projeto (HPA103-2).

Resultados
Experimentos numéricos comparando os métodos propostos (LHS-FMQA e Sobol'-FMQA) contra uma linha de base Conv-FMQA (inicialização aleatória uniforme) e outros otimizadores (GP-BO, NSGA-II, Busca Aleatória) produziram os seguintes resultados:

• Melhoria de Desempenho: Ambos os métodos propostos alcançaram velocidades médias finais de cruzeiro numericamente superiores à linha de base Conv-FMQA.
• Dependência da Dimensionalidade: A vantagem dos métodos propostos foi mais pronunciada no problema de dimensão mais elevada (HPA103-2, 32 variáveis). A melhoria na velocidade final de cruzeiro sobre a linha de base aumentou de aproximadamente +0,135 m/s (LHS) e +0,192 m/s (Sobol') no problema de 17 variáveis para +0,333 m/s e +0,352 m/s, respectivamente, no problema de 32 variáveis.
• Confirmação do Mecanismo: A análise das distribuições de uso de bits confirmou que, enquanto a Conv-FMQA manteve aproximadamente 36% de bits "nunca ativos" mesmo após o orçamento total de avaliação, os métodos propostos alcançaram 0% de bits "nunca ativos".
• Comparação com Outros Otimizadores: Os métodos propostos performaram de forma comparável ou superior ao GP-BO e ao NSGA-II. Notavelmente, a melhoria sobre a Conv-FMQA foi impulsionada pelo processo de otimização após a fase de amostragem inicial (maior "ganho"), e não simplesmente por começar a partir de melhores valores iniciais.

Significado e Alegações
O artigo alega que melhorar a cobertura marginal de bits nos dados iniciais de treinamento é um fator crucial para aprimorar o desempenho da FMQA. Ao garantir que toda variável binária seja ativa pelo menos uma vez, os métodos propostos impedem que os coeficientes QUBO sejam determinados exclusivamente pela inicialização e pelo decaimento de pesos em direções específicas. Isso permite que a Máquina de Ising realize uma busca informada através de todas as dimensões de projeto.

Os autores observam modestamente que, embora seus resultados apoiem a hipótese de que a cobertura marginal reduz o viés, o estudo atual não isola completamente o efeito da cobertura marginal das propriedades de preenchimento de espaço das sequências LHS e Sobol'. Eles reconhecem que os métodos propostos alcançam simultaneamente ambas as propriedades. Além disso, observam que os métodos garantem a cobertura marginal, mas não a cobertura de pares de bits (interações entre bits). O estudo conclui que essas estratégias de inicialização são particularmente eficazes para problemas de dimensões mais elevadas, onde o número absoluto de bits potencialmente inativos na amostragem aleatória seria substancial. Sugere-se trabalho futuro para desacoplar a cobertura marginal das propriedades de preenchimento de espaço e investigar estratégias de cobertura de pares.