Resumo Técnico: Modelos de Ordem Parcial Hierárquicos para Classificação

Definição do Problema

A agregação de rankings visa combinar listas ordenadas de diversas fontes em uma estrutura de consenso. Modelos paramétricos clássicos, como Mallows e Plackett–Luce, assumem que as preferências se concentram em torno de um ou mais rankings de consenso completos (ordens totais). No entanto, em muitas aplicações, a suposição de que a verdadeira estrutura de preferência é uma ordem total é injustificada; os avaliadores podem considerar certos itens como incomparáveis. Além disso, os dados de preferência frequentemente exibem estruturas de grupo (por exemplo, diferentes avaliadores, cenários distintos ou segmentos de séries temporais) que os modelos existentes têm dificuldade em acomodar enquanto preservam estruturas de ordem parcial.

Embora trabalhos recentes tenham relaxado a suposição de ordem total para permitir ordens parciais (posets), e outros trabalhos tenham introduzido extensões hierárquicas para ordens totais, há uma falta de um framework unificado que combine agrupamento hierárquico com consenso de ordem parcial. Modelos hierárquicos existentes para ordens parciais (ex: Arcagni et al., 2022) dependem de estimativas de ponto baseadas em perda em vez de inferência Bayesiana generativa.

Metodologia

O artigo introduz os modelos de Ordem Parcial Hierárquica (HPO) e sua extensão de agrupamento não supervisionado (HCPO).

1. O Framework HPO

O modelo HPO é projetado para dados de ordem de ranking que vêm em grupos rotulados (ex: $A$ avaliadores). Ele é estruturado como uma árvore com um nó raiz representando uma ordem parcial "global" e nós folha representando ordens parciais específicas de cada avaliador.

• Construção de Variáveis Latentes: O modelo parametriza ordens parciais usando variáveis latentes contínuas. Para cada item $j$ no universo de escolhas, existe um vetor de pesos de preferência $U_j \in \mathbb{R}^K$. Uma ordem parcial é formada pela interseção de $K$ ordens completas derivadas desses pesos.
• Processo Generativo:
  • Nível Global: Um peso latente global $U^{(0)}$ é extraído de uma distribuição normal multivariada com uma estrutura de correlação controlada por $\rho$.
  • Nível Local: Para cada avaliador $a$, pesos latentes $U^{(a)}$ são extraídos condicionalmente de $U^{(0)}$ via uma distribuição normal multivariada com o parâmetro de correlação $\tau$. Este parâmetro $\tau \in (0, 1]$ controla o "encolhimento" (shrinkage) dos posets específicos do avaliador em direção ao poset global.
  • Mapeamento para Posets: Os pesos latentes são transformados via uma construção Gumbel (usando a função inversa da CDF da distribuição Gumbel aplicada à CDF normal) para gerar escores de preferência $\eta$. A ordem parcial $h^{(a)}$ é definida pela interseção das ordens derivadas desses escores.
• Modelos de Observação: O artigo propõe três verossimilhanças para observar um ranking $y$ dado um poset $h$:
  1. Sem ruído (Noise-free): Amostragem uniforme de extensões lineares (computacionalmente caro para $M$ grandes).
  2. Salto de fila (Queue-jumping): Um modelo de seleção repetida onde, com probabilidade $p$, um item é escolhido aleatoriamente (ruído), e caso contrário, é escolhido com base nas restrições do poset.
  3. Salto de fila ponderado (Weighted Queue-jumping): Uma extensão onde as escolhas aleatórias são enviesadas pelos escores latentes $\eta$, tornando os erros menos prováveis para itens com grandes lacunas de preferência.
  4. Softmax de Fronteira (Frontier-softmax): Um modelo de utilidade onde itens são escolhidos a partir da "fronteira" (elementos maximais) da subordem restante, ponderados pelo número de itens que eles dominam. É computacionalmente eficiente ($O(M)$ por passo) e adequado para grandes conjuntos de dados.

2. O Framework HCPO

Quando os rótulos de grupo são desconhecidos, o artigo estende o HPO para modelos de Agrupamento Hierárquico de Ordem Parcial (HCPO).

• Agrupamento (Clustering): Um prior de processo Pitman-Yor é colocado sobre a partição das listas (ou avaliadores) em $G$ grupos latentes.
• Inferência: O número de grupos $G$ e as atribuições de cluster são inferidos conjuntamente com a hierarquia do poset usando MCMC (Markov Chain Monte Carlo).
• Agrupamento de Avaliador vs. Lista: O modelo pode agrupar listas individuais ou avaliadores inteiros (movendo todas as listas de um avaliador juntas).

3. Inferência Bayesiana

A inferência é realizada via MCMC. A distribuição posterior é sobre os parâmetros de correlação ($\rho, \tau$), as matrizes de pesos latentes ($U$), os coefs de regressão ($\beta$) e a partição ($C$). A dimensão do espaço latente $K$ também pode ser inferida usando MCMC de salto reversível (reversible jump MCMC).

Principais Contribuições

1. Modelos HPO e HCPO: A introdução de um framework Bayesiano generativo para dados de ranking agrupados que explicitamente modela estruturas de consenso de ordem parcial, estendendo o modelo Plackett–Luce para o domínio de posets.
2. Propriedades Teóricas:
   • Prova de que os modelos Plackett–Luce e suas variantes hierárquicas são casos especiais de HPO (quando $K=1$).
   • Demonstração de que o modelo é marginalmente consistente, garantindo que o prior sobre subordens seja consistente com o prior sobre o universo completo.
   • Prova de que o modelo pode representar qualquer hierarquia de posets, desde que $K \ge \lfloor M/2 \rfloor$.
3. Novos Modelos de Observação: O desenvolvimento das verossimilhanças Weighted Queue-jumping e Frontier-softmax, que permitem ruído e eficiência computacional enquanto mantêm uma interpretação generativa.
4. Agrupamento Não Supervisionado: A extensão para HCPO para descobrir estruturas de agrupamento latentes em dados de ranking não rotulados.

Resultados Experimentais

O artigo avalia os modelos em dados sintéticos e do mundo real:

• Dados Sintéticos (HPO): Em configurações com grupos rotulados, o HPO recupera com sucesso a hierarquia latente de posets. A precisão da recuperação é impulsionada principalmente pelo comprimento das listas observadas (tamanho do conjunto de escolha) e pela força de acoplamento ($\tau$). A verossimilhança Frontier-softmax oferece ganhos significativos de velocidade computacional (escalando linearmente com o comprimento da lista) em comparação com métodos exatos de extensão linear, que sofrem timeout para $M \ge 50$.
• Dados Sintéticos (HCPO): Em ambientes não rotulados, o HCPO recupera com precisão tanto a estrutura de agrupamento latente quanto os posets específicos de cada cluster. O benefício do agrupamento é mais pronunciado quando o acoplamento entre os grupos é fraco (alta heterogeneidade).
• Traços de Provisionamento de Nuvem (Agentes de LLM): Aplicado a traços de execução de agentes de LLM (Aliyun Cloud-IaC-6). O modelo HPO, tratando diferentes cenários como grupos, superou baselines de ordem total independentes na recuperação das estruturas de dependência subjacentes (estruturas de workflow). O agrupamento hierárquico melhorou a recuperação de restrições de precedência, particularmente em cenários com dados esparsos.
• Dados de Preferência Humana (Som 3D): Aplicado a dados de preferência acústica pareada onde ouvintes exibiram padrões cíclicos (violando ordens totais). O modelo HCPO superou significativamente os baselines de ordem total (misturas de Plackett–Luce e Mallows) em ajuste preditivo (WAIC). Crucialmente, os resumos do HCPO revelaram estruturas interpretáveis onde os clusters continham camadas superiores amplas de itens incomparáveis, uma característica que modelos de ordem total não conseguem representar sem forçar rankings estritos arbitrários.

Significância e Alegações

O artigo afirma que os frameworks propostos HPO e HCPO fornecem uma maneira fundamentada de lidar com dados de ranking agrupados onde as preferências podem ser incompletas ou incomparáveis.

• Interpretabilidade Estrutural: Os modelos permitem a recuperação de estruturas de ordem parcial que refletem incomparabilidades genuínas, evitando artefatos introduzidos ao forçar os dados em ordens totais.
• Compartilhamento de Informação: A estrutura hierárquica permite o compartilhamento de informações (encolhimento/shrinkage) de forma fundamentada entre grupos, melhorando a estimativa em regimes de poucos dados enquanto preserva as nuances específicas de cada grupo.
• Viabilidade Computacional: A verossimilhança Frontier-softmax permite a aplicação destes modelos a conjuntos de itens maiores, onde a contagem exata de extensões lineares é intratável.
• Generalidade: O framework absorve os modelos hierárquicos Plackett–Luce existentes e estende-os para o domínio da ordem parcial, oferecendo uma abordagem unificada tanto para dados de ranking agrupados rotulados quanto não rotulados.

Os autores enfatizam que sua abordagem é superior aos métodos baseados em perda para ordens parciais ao fornecer uma distribuição posterior Bayesiana completa, permit o quantificação de incerteza e comparação de modelos fundamentada via WAIC.