Optimal Top-$k$ Identification from Pairwise Comparisons

Resumo Técnico: Identificação Ótima de Top-$k$ a partir de Comparações Pareadas

Formulação do Problema
Este artigo aborda o problema de aprendizado ativo de identificação de top-$k$ de confiança fixa a partir de comparações pareadas ruidosas. O cenário envolve $n$ itens com utilidades latentes desconhecidas $\theta = (\theta_1, \dots, \theta_n)$. Um algoritmo seleciona sequencialmente pares de itens $(i, j)$ para comparar, observa os resultados e deve parar para retornar o conjunto dos $k$ melhores itens, denotado por $S^*(\theta)$, com uma probabilidade de erro de no máximo $\delta$. O objetivo é projetar um procedimento $\delta$-correto que minimize o número esperado de comparações (complexidade de amostragem).

Os autores assumem um modelo de utilidade latente onde os resultados das comparações seguem uma família exponencial de um parâmetro. Especificamente, para um par $(i, j)$, a distribuição do resultado depende do parâmetro natural $\eta_{ij}(\theta) = \theta_i - \theta_j$. Este arcabouço acomoda tanto resultados binários (ex: modelo de Bradley-Terry) quanto resultados cardinais (ex: diferenças gaussianas). O problema assume um hiato positivo entre o $k$-ésimo e o $(k+1)$-ésimo melhores itens ($\theta_{(k)} > \theta_{(k+1)}$).

Metodologia e Design do Algoritmo
A solução proposta é um algoritmo online e adaptativo (Algoritmo 1) que alcança otimalidade assintótica conforme $\delta \to 0$. A metodologia baseia-se no arcabouço Track-and-Stop (Rastrear-e-Parar), que envolve o rastreamento de uma alocação de comparações "oráculo" ótima e a interrupção assim que a confiança estatística for suficiente.

1. Caracterização do Problema Oráculo:
   Os autores caracterizam o limite inferior informacional sobre a complexidade de amostragem, que é governado por um problema de oráculo max-min. Eles mostram que distinguir o parâmetro verdadeiro $\theta$ de qualquer alternativa $\theta'$ (onde o conjunto top-$k$ difere) requer considerar apenas pares de fronteira — pares $(u, v)$ onde $u$ está no verdadeiro conjunto top-$k$ e $v$ não está.
   O problema do oráculo é formulado como um jogo de ponto de sela de dois jogadores:

   • Designer (Primal): Aloca pesos de comparação $w$ sobre todos os pares.
   • Adversário (Dual): Seleciona uma distribuição $q$ sobre os $k(n-k)$ pares de fronteira para "visar" a alternativa mais difícil.
     O equilíbrio $(w^*, q^*)$ deste jogo define a estratégia de amostragem assintoticamente ótima e a taxa de informação ótima $\Gamma^*(\theta)$.

2. Aprendizado Primal-Dual Online:
   Como o verdadeiro $\theta$ é desconhecido, o algoritmo aprende o ponto de sela online. Em cada rodada $t$:

   • Estimação: Ele computa a Estimativa de Máxima Verossimilhança (MLE) $\hat{\theta}_t$ e o conjunto de fronteira induzido $\hat{B}_t$.
   • Rastreamento: Mantém iterados primais $w_t$ (pesos de alocação) e iterados duais $q_t$ (pesos sobre pares de fronteira).
   • Atualizações: Em vez de resolver o problema max-min completo em cada etapa, o algoritmo realiza um único passo de atualização FTRL (Follow-The-Regularized-Leader) entrópico por rodada usando gradientes estocásticos.
   • Estimação de Gradiente: Para garantir eficiência computacional, o algoritmo amostra um único par de fronteira $I_t$ uniformemente de $\hat{B}_t$ para construir estimativas de gradiente não viesadas para as projeções de divergência KL, evitando o custo de $O(n^2)$ de computar projeções para todos os pares de fronteira.
   • Amostragem: O próximo par a ser comparado é selecionado via C-tracking, que garante que as proporções de amostragem empíricas rastreiem a média móvel dos pesos aprendidos enquanto mantém a exploração via um esquema de mistura (mixing schedule).

3. Regra de Parada:
   O algoritmo emprega uma regra de parada baseada em um argumento de martingala de razão de verossimilhança. Ele computa uma estatística $Z_{ij}(t)$ para cada par de fronteira, representando a razão de log-verossimilhança entre a MLE atual e a alternativa mais confusa que inverte a ordem daquele par. O algoritmo para quando o mínimo dessas estatísticas através de todos os pares de fronteira excede um limiar $\beta(t, \delta)$ derivado de limites de concentração autonormalizados.

Principais Contribuições

• Otimalidade Assintótica: O artigo estabelece o primeiro algoritmo assintoticamente ótimo para identificação de top-$k$ a partir de comparações pareadas sob modelos de utilidade latente. A complexidade de amostragem esperada do procedimento proposto iguala o limite inferior informacional conforme $\delta \to 0$.
• Caracterização Estrutural: Os autores caracterizam a estrutura do limite inferior ao reduzir o conjunto de alternativas para parâmetros que invertem pares de fronteira. Essa redução permite que o problema do oráculo seja formulado como um problema de ponto de sela tratável.
• Procedimento Computacionalmente Eficiente: Ao formular o problema como um jogo e usar atualizações primal-dual estocásticas, o algoritmo evita a complexidade combinatória de encontrar a "alternativa mais confusa" em cada etapa. Isso torna o método escalável para valores de $n$ moderadamente grandes.
• Generalização: O arcabouço aplica-se tanto a resultados de comparação binários quanto cardinais sob suposições gerais de família exponencial.

Resultos e Desempenho
Os autores avaliam o algoritmo em três instâncias sintéticas:

1. Utilidades Aleatórias: Utilidades desenhadas uniformemente e centradas.
2. Utilidades Espaçadas Uniformemente: Utilidades com um intervalo fixo.
3. Matriz de Preferência SST: Resultados gerados a partir de uma matriz que satisfaz a Transitividade Estocástica Forte (SST), mas não é necessariamente induzida por utilidades latentes (erro de especificação do modelo).

Em simulações com $\delta = 0.01$, o algoritmo proposto supera consistentemente as linhas de base existentes (SEEEKS, SEEKS-v2 e Active Ranking) através de variações no número de itens $n$ e tamanhos de top-$k$.

• No cenário de Utilidades Aleatórias, o algoritmo demonstra desempenho superior conforme $n$ e $k$ aumentam.
• No cenário de Espaçamento Uniforme, o tempo de parada do algoritmo rastreia de perto um benchmark oráculo que conhece o verdadeiro $\theta$, confirmando desempenho próximo do ótimo mesmo para $\delta$ moderado.
• Sob erro de especificação SST, o algoritmo permanece competitivo, embora o limiar de parada possa ser frouxo para $\delta$ moderado devido ao crescimento da norma $\|\hat{\theta}_t\|_2^2$.

Significância e Alegações
O artigo afirma que, embora procedimentos assintoticamente ótimos existam para várias variações de exploração pura, um algoritmo assintoticamente ótimo para identificação de top-$k$ a partir de comparações pareadas sob modelos de utilidade latente não havia sido estabelecido antes deste trabalho. A significância reside em preencher essa lacuna fornecendo um procedimento que:

1. Iguala o limite inferior informacional exatamente (incluindo constantes multiplicativas) conforme $\delta \to 0$.
2. É computacionalmente eficiente, escalando para tamanhos de problemas práticos via aprendizado online do ponto de sela.
3. Lida com feedback binário e cardinal dentro de um arcabouço unificado.

Os autores observam modestamente que uma fraqueza da abordagem atual é o limiar de parada em $\delta$ moderado, que às vezes pode levar a um desempenho subótimo em comparação com as linhas de base em regimes específicos (ex: quando a norma da utilidade é grande). Eles sugerem que trabalhos futuros poderiam focar na construção de limiares de parada mais estreitos para $\delta$ moderado, preservando a otimalidade assintótica.