Performance-Driven QUBO for Recommender Systems on Quantum Annealers

1. Formulação do Problema

Os sistemas de recomendação frequentemente sofrem com a "maldição da dimensionalidade" devido ao vasto número de características dos itens, levando a redundância, aumento dos custos de armazenamento e redução da eficiência de recuperação. Embora a seleção de características seja crítica, os métodos tradicionais frequentemente falham em otimizar explicitamente o desempenho final da recomendação (por exemplo, métricas de classificação como nDCG).

As abordagens existentes de Recozimento Quântico (QA) para seleção de características, que formulam o problema como Otimização Binária Quadrática sem Restrições (QUBO), enfrentam duas limitações principais:

1. Objetivos Desalinhados: Os métodos atuais baseados em QUBO (por exemplo, MIQUBO, CoQUBO) constroem a matriz de coeficientes $Q$ com base em dependências estatísticas (informação mútua, correlação) ou saídas de modelos, em vez do impacto direto na métrica de desempenho da recomendação.
2. Instabilidade: O desempenho dos recozidores quânticos em hardware real (era NISQ) é sensível ao tamanho do problema, contagem de amostras e dificuldade do problema, levando a resultados inconsistentes.

Os autores levantam três questões de pesquisa principais:

• Como a instabilidade dos recozidores quânticos afeta o desempenho do sistema de recomendação?
• Quão eficazes são os recozidores quânticos para seleção de características neste domínio?
• Os métodos baseados em QUBO em hardware quântico podem igualar ou superar as bases de seleção de características clássicas?

2. Metodologia: PDQUBO

Os autores propõem o PDQUBO (Otimização Binária Quadrática sem Restrições Orientada a Desempenho), um novo quadro que alinha o objetivo de otimização QUBO diretamente com o desempenho de recomendação a jusante, utilizando análise contrafactual.

Fluxo de Trabalho Principal

1. Treinamento do Modelo Base: Um modelo de recomendação ($G_\Theta$) é treinado no conjunto completo de características $F$.
2. Análise Contrafactual: O método avalia o impacto das características criando "instâncias contrafactuais". Ele mascara sistematicamente (remove) características individuais ($f_i$) e pares de características ($f_i, f_j$) da entrada e mede a mudança na métrica de avaliação (por exemplo, nDCG).
   • $E_i$: Queda de desempenho quando $f_i$ é removida.
   • $E_{ij}$: Queda de desempenho quando ambas $f_i$ e $f_j$ são removidas.
   • Nota: Um $E$ positivo indica que a característica é importante (o desempenho cai quando removida); um $E$ negativo sugere que a característica é redundante ou prejudicial.
3. Formulação QUBO: Os valores contrafactuais são usados para construir a matriz de coeficientes QUBO $Q$:
   • Elementos diagonais ($Q_{ii}$): Definidos como $-E_i$ (representando a importância individual da característica).
   • Elementos fora da diagonal ($Q_{ij}$): Definidos como $-E_{ij}$ (representando interações de pares de características).
   • A função objetivo minimiza a energia $Y = x^T Q x$, onde $x$ é um vetor binário indicando a seleção de características. Minimizar $Y$ corresponde a selecionar características que maximizam o desempenho da recomendação.
4. Otimização: O problema QUBO construído é resolvido usando solucionadores clássicos (Recozimento Simulado, Busca Tabu) ou Recozidores Quânticos (D-Wave).
5. Retreinamento: O subconjunto de características selecionado é usado para retreinar o modelo base para avaliação final.

Distinções Principais

• Agnóstico ao Modelo: O PDQUBO funciona com qualquer modelo base (KNN, MLP, NCF) e qualquer métrica.
• Consciente de Interação: Diferentemente dos métodos de "filtro" que tratam características independentemente, o PDQUBO modela explicitamente interações de pares por meio dos termos quadráticos em $Q$.

3. Principais Contribuições

1. Quadro PDQUBO: Uma nova formulação QUBO que liga explicitamente a seleção de características ao desempenho da recomendação via análise contrafactual, garantindo que a direção da otimização seja orientada pelo desempenho e não por dependências estatísticas.
2. Análise Abrangente de Estabilidade: Uma investigação detalhada sobre a instabilidade dos recozidores quânticos do mundo real, analisando como a qualidade da solução varia com:
   • Tamanho do problema (número de características).
   • Tamanho da amostra (número de execuções de recozimento).
   • Dificuldade do problema (espalhamento dos dados).
3. Validação Empírica: Experimentos extensivos em conjuntos de dados do mundo real (conjuntos de dados CLEF 2024 QuantumCLEF, KuaiRec, KuaiRand, Avazu, Criteo) demonstrando que o PDQUBO supera as bases QUBO existentes e compete com métodos de seleção de características clássicos de última geração.
4. Insights de Escalabilidade: Análise do custo computacional e uma estratégia proposta de poda em dois estágios para mitigar a complexidade $O(|F|^2)$ de construir a matriz QUBO completa, embora o artigo conclua que a formulação quadrática completa é necessária para desempenho ótimo.

4. Resultados Experimentais

Os autores avaliaram o PDQUBO contra bases (CQFS, MIQUBO, CoQUBO, QUBO-Boosting) e métodos clássicos (Lasso, GBDT, Importância por Permutação) em vários conjuntos de dados e modelos.

• Desempenho vs. Bases:

  • O PDQUBO consistentemente alcançou as pontuações melhor ou segunda melhor nDCG@10 na maioria das configurações nos conjuntos de dados 150_ICM e 500_ICM.
  • Em tarefas de previsão de CTR (Avazu, Criteo), o PDQUBO-Híbrido (usando um solucionador quântico-clássico híbrido) alcançou as maiores pontuações AUC, superando tanto as bases clássicas quanto outras variantes QUBO.
  • O PDQUBO superou significativamente outros métodos QUBO (como MIQUBO), provando que a construção orientada pelo desempenho é superior à construção de dependência estatística.

• Descobertas sobre Estabilidade:

  • Tamanho do Problema: Os resultados do Recozimento Quântico (QA) tornam-se instáveis à medida que o número de características aumenta além da capacidade de qubits lógicos do hardware, enquanto os solucionadores clássicos (SA, TS) permanecem estáveis.
  • Tamanho da Amostra: Aumentar o número de amostras de QA reduz significativamente a variância de energia e melhora o desempenho a jusante, destacando a necessidade de amostragem suficiente em dispositivos NISQ.
  • Dificuldade: O QA tende a mostrar ganhos de desempenho maiores, mas mais voláteis, em conjuntos de dados esparsos (difíceis).

• Necessidade de Termos Quadráticos:

  • Experimentos comparando "Indiv" (apenas diagonal) vs. "All" (matriz completa) mostraram que incluir interações de pares ($Q_{ij}$) é crucial. A abordagem "All" produziu resultados significativamente melhores, confirmando que as interações entre características são vitais para uma seleção eficaz neste contexto.

• Eficiência:

  • Embora a complexidade de tempo dos solucionadores clássicos cresça exponencialmente com o tamanho do problema, o tempo de recozimento quântico permanece relativamente constante (limitado pelo acesso ao hardware e tempo de amostragem), oferecendo uma vantagem potencial de velocidade para problemas em grande escala uma vez que as restrições de hardware sejam superadas.

5. Significado e Direções Futuras

• Ponte da Lacuna: Este trabalho conecta com sucesso a lacuna entre a otimização quântica teórica e a implantação prática de sistemas de recomendação, garantindo que o objetivo de otimização vise diretamente a métrica de negócios (qualidade da recomendação).
• Viabilidade Prática: Os resultados sugerem que, mesmo com as limitações atuais do hardware NISQ, abordagens híbridas quântico-clássicas podem fornecer seleção de características competitiva ou superior em comparação com métodos clássicos maduros.
• Trabalho Futuro: Os autores sugerem estender o PDQUBO para modelar interações de características de ordem superior (além de pares) e explorar algoritmos quânticos variacionais em computadores quânticos baseados em portas para lidar com estruturas de características em grande escala e mais complexas.

Em conclusão, o PDQUBO representa um passo significativo para frente na aplicação da computação quântica a desafios reais de recomendação, demonstrando que formulações QUBO baseadas em contrafactuais e orientadas por desempenho podem aproveitar efetivamente os recozidores quânticos para seleção de características de alta qualidade.