Resumo Técnico: Rankings de Bradley-Terry para Sistemas de Recomendação Através de Taxonomias de Conjuntos de Dados

Declaração do Problema

O ranking de algoritmos de recomendação é um desafio complexo porque o desempenho do modelo é altamente sensível às características do conjunto de dados, incluindo esparsidade, estrutura sequencial e escala. Consequentemente, um único algoritmo pode se destacar em um subconjunto específico de conjuntos de dados enquanto apresenta desempenho inferior em outros. Essa variabilidade torna difícil para os profissionais selecionarem o método mais adequado para uma tarefa específica sem incorrer nos altos custos de uma comparação direta e exaustiva.

Os métodos de avaliação tradicionais frequentemente dependem da agregação ingênua de métricas de desempenho (por exemplo, a média do NDCG entre benchmarks). Os autores argumentam que tais abordagens podem gerar rankings enganosos ou instáveis porque não levam em conta a força variável dos oponentes em diferentes conjuntos de dados e não fornecem uma maneira fundamentada de lidar com dados ausentes ou contextos específicos de cada conjunto de dados. Há uma necessidade crítica de uma metodologia que permita a comparação e seleção de algoritmos de forma justa e consciente do conjunto de dados.

Metodologia

O artigo propõe uma estrutura de ranking baseada em dados fundamentada no modelo de Bradley-Terry (BT) e suas extensões. A abordagem central trata a avaliação de algoritmos de recomendação como um torneio onde os algoritmos "competem" em vários conjuntos de dados.

1. Estrutura de Comparação Pareada

Em vez de agregar pontuações brutas de métricas, os autores constroem uma tabela de torneio $W$, onde $W_{ij}$ representa o número de conjuntos de dados nos quais o algoritmo $i$ supera o algoritmo $j$.

• Tratamento de Empates: Se as métricas de desempenho de dois algoritmos em um conjunto de dados caírem dentro de intervalos de confiança sobrepostos (definidos como $métrica \pm std$), a comparação é tratada como um empate. Os autores adicionam 0,5 tanto a $W_{ij}$ quanto a $W_{ji}$ nesses casos.
• Estimativa: Os autores avaliam três métodos de estimativa:
  • Zermelo Clássico (MLE): Maximização iterativa da verossimilhança.
  • BT Bayesiano: Utiliza Metropolis-Hastings para amostrar parâmetros, fornecendo intervalos de confiança e quantificação de incerteza.
  • Centralidade de Rank (Método Espectral): Modela comparações como um passeio aleatório em um grafo para estimar medidas estacionárias.
  • Nota: Nos dados de benchmark completos, todos os três métodos convergiram para rankings idênticos. A abordagem Bayesiana foi selecionada por sua capacidade de fornecer intervalos de confiança.

2. Métricas de Validação

Para avaliar a qualidade e a robustez dos rankings, os autores introduzem a métrica de "tripletos transitivos".

• Um triplet $(i, j, k)$ é transitivo se $i \succ j$, $j \succ k$ e $i \succ k$.
• A métrica calcula a razão de tripletos transitivos em todos os conjuntos de dados. Uma razão mais alta indica um ranking mais consistente e estável.
• Esta métrica é especificamente desenhada para avaliar a robustez contra dados ausentes, uma limitação das medidas padrão de correlação de rank, como o $\tau$ de Kendall.

3. Extensões Conscientes do Conjunto de Dados

Para abordar a limitação de que um ranking global pode não se aplicar a conjuntos de dados não vistos, o artigo estende a estrutura:

• BT Ajustado por Covariáveis: Incorpora características do conjunto de dados (covariáveis) como densidade, razão usuário-item e sequencialidade ao modelo. A probabilidade de $i$ vencer $j$ é modelada como uma função das forças dos algoritmos e das covariáveis do conjunto de dados: $P(i \succ j | x) = \sigma(\beta_{i0} - \beta_{j0} + \langle x, \beta_i \rangle - \langle x, \beta_j \rangle)$. A regularização L1 é usada para evitar o sobreajuste (overfitting).
• Árvores de Bradley-Terry: Uma abordagem não paramétrica que particiona recursivamente os conjuntos de dados com base em covariáveis (ex: sequencialidade) para identificar grupos com escalonamentos de preferência homogêneos.

Configuração Experimental

• Conjuntos de Dados: 89 conjuntos de dados diversos do benchmark APS e fontes adicionais, pré-processados com um esquema de filtragem de 5-core.
• Algoritmos: 14 algoritmos variando de heurísticas triviais (Random, PopRandom) a variantes de vizinhança (variantes de KNN), fatoração de matriz (ALS, BPR, PureSVD), baseados em grafos (LightGCN, UltraGCN) e modelos sequenciais (SASRec, GASATF).
• Protocolo: Divisão temporal global (90/5/5) com otimização de hiperparâmetros via Optuna. As métricas foram calculadas sobre a média de 10 sementes aleatórias para estabelecer intervalos de confiança.

Principais Resultados

1. Superioridade sobre Baselines de Agregação

Os rankings baseados em BT demonstraram estabilidade e consistência significativamente maiores em comparação com métodos simples de agregação (Média e Soma de métricas).

• Tripletos Transitivos: Os modelos BT alcançaram uma razão maior de tripletos transitivos (ex: 0,631 com empates em todos os conjuntos de dados) comparado a Média (0,613) e Soma (0,613).
• Robustez a Dados Ausentes: À medida que a proporção de comparações pareadas ausentes aumentava, a razão de tripletos transitivos para os rankings de Média e Soma caía rapidamente. Em contraste, os rankings BT e Plackett-Luce (PL) permaneceram estáveis, mantendo uma alta razão de tripletos transitivos mesmo com lacunas significativas de dados.

2. Desempenho Dependente de Contexto

Os experimentos revelaram que nenhum algoritmo é universalmente ótimo; os rankings mudam drasticamente com base na taxonomia do conjunto de dados:

• Sequencialidade: Modelos sequenciais (SASRec, GASATF) dominam conjuntos de dados sequenciais (ranks 1 e 2), mas caem significativamente (ranks 10 e 11) em dados não sequenciais. Por outro lado, modelos tradicionais como ALS e UltraGCN apresentam melhor desempenho em dados não sequenciais.
• Comprimento do Histórico: Em conjuntos de dados com históricos de usuários longos, Seq-KNN e GASATF lideram. Em conjuntos de dados com histórico curto, o LightGCN torna-se o melhor performer.
• Esparsidade: GASATF e User-KNN mostram um desempenho relativo melhorado em conjuntos de dados esparsos em comparação com os densos.

3. Capacidade Preditiva para Conjuntos de Dados Não Vistos

Os autores avaliaram a capacidade de prever rankings em conjuntos de dados de teste (holdout) sem executar os modelos:

• Modelos Ajustados por Covariáveis: O modelo BT ajustado por covariáveis e as árvores BT superaram a agregação simples e o modelo BT global na previsão do algoritmo Top-1 (Top-1 hits: 0,28 para Cov. BT vs. 0,24 para o BT global).
• Suficiência da Seleção de Baselines: Apesar da maior precisão dos modelos de covariáveis na classificação precisa, os autores descobriram que o ranking BT global (sem covariáveis) é suficiente para selecionar um conjunto forte de 5 baselines (sobreposição Top-5 ~3,32), o que é comparável ao desempenho de modelos mais complexos.

Significância e Alegações

O artigo afirma fornecer uma metodologia fundamentada e baseada em dados para uma comparação justa de algoritmos que vai além da agregação ingênua de métricas. Suas principais contribuições são:

1. Uma Estrutura de Ranking Robusta: Demonstrando que os rankings baseados em BT são mais estáveis e consistentes, particularmente na presença de dados ausentes, do que os métodos tradicionais de agregação.
2. Seleção Dependente de Conjunto de Dados: Estabelecendo que o desempenho do algoritmo é altamente dependente do contexto. A estrutura proposta permite que os profissionais entendam quais algoritmos são adequados para taxonomias específicas de conjuntos de dados (ex: esparso vs. denso, sequencial vs. não sequencial).
3. Utilidade Preditiva: Mostrando que, embora os modelos ajustados por covariáveis ofereçam previsões de ranking mais precisas para conjuntos de dados não vistos, um ranking BT global é frequentemente suficiente para identificar um conjunto forte de algoritmos de baseline, reduzindo o custo computacional de uma avaliação exaustiva.
4. Reprodutibilidade: Os autores fornecem um repositório aberto contendo implementações de 14 algoritmos, uma estrutura de otimização de hiperparâmetros e resultados para 89 conjuntos de dados, facilitando a pesquisa reprodutível em sistemas de recomendação.

O trabalho conclui que a abordagem proposta oferece uma base mais confiável e interpretável para a comparação de algoritmos em sistemas de recomendação, abordando os desafios da heterogeneidade dos conjuntos de dados e da instabilidade de avaliação.