Online Learning-to-Defer with Varying Experts

Formulação do Problema
A Aprendizagem para Adiar (Learning-to-Defer, L2D) é um framework projetado para integrar modelos preditivos com especialistas externos (humanos ou automatizados) a fim de aumentar a confiabilidade do sistema, roteando entradas incertas ou de alto risco para agentes mais competentes. Embora a pesquisa existente em L2D opere principalmente em configurações em lote com pools fixos de especialistas e supervisão total (observando todas as previsões dos especialistas durante o treinamento), implementações no mundo real enfrentam desafios significativos: os dados chegam sequencialmente, a disponibilidade dos especialistas flutua (por exemplo, devido a turnos ou restrições de recursos) e a confiabilidade dos especialistas pode mudar ao longo do tempo. Além disso, sistemas práticos frequentemente operam sob feedback de bandit, onde o aprendiz observa apenas o resultado da ação escolhida (previsão ou consulta específica a um especialista) em vez da verdade fundamental ou do desempenho de todos os especialistas disponíveis. Este artigo aborda a lacuna entre as suposições clássicas de L2D e essas realidades dinâmicas e online, introduzindo o primeiro framework online de L2D para classificação multiclasse com feedback de bandit e um pool de especialistas que varia dinamicamente.

Metodologia
Os autores propõem um framework geral onde, em cada rodada $t$, uma entrada aumentada $(x_t, A_t)$ é revelada, consistindo em um vetor de características $x_t$ e um conjunto de especialistas disponíveis $A_t$. O aprendiz deve decidir se prevê um rótulo de classe ou se adia para um dos especialistas disponíveis em $A_t$. A interação segue um cenário semi-adversarial: as entradas podem ser escolhidas adversarialmente, mas os rótulos são extraídos de uma distribuição fixa (embora desconhecida) condicional à entrada.

As contribuições metodológicas centrais incluem:

1. Perda Real de Adiamento e Surrogata: Os autores definem uma perda real de adiamento $\ell_{def}$ que considera custos de classificação incorreta e custos de consulta a especialistas. Como essa perda é não diferenciável, eles introduzem uma perda surrogata convexa $\Phi_{def}$ que estende surrogatas baseadas em pontuação padrão (como a perda de hinge com restrição) para o cenário online com especialistas variáveis. Essa surrogata é projetada para não ser afetada pelas pontuações de especialistas indisponíveis.
2. Limites de Consistência-H para Aprendizado Online: Um passo teórico significativo é a extensão dos limites de consistência-H do aprendizado em lote para o cenário online. Os autores provam que minimizar o arrependimento de adiamento surrogato no framework online garante um arrependimento de adiamento real limitado, desde que a surrogata subjacente admita um limite de consistência-H em relação à perda zero-um.
3. Projeto do Algoritmo: O algoritmo proposto (Algoritmo 1) utiliza Descida de Gradiente Online (OGD) com gradientes projetados. Para lidar com a restrição de que a soma das pontuações para rótulos disponíveis deve ser zero (necessária para a perda de hinge com restrição), o algoritmo projeta a matriz de pesos em um subespaço viável $K_{A_t}$ específico para o conjunto atual de especialistas disponíveis. Essa projeção preserva as previsões da hipótese no conjunto de rótulos disponíveis. O algoritmo incorpora uma taxa de exploração $\gamma_t$ para lidar com o feedback de bandit, estimando a função de perda com base no resultado observado da ação amostrada.

Principais Contribuições
O artigo reivindica quatro contribuições primárias:

1. Primeiro Framework Online de L2D: Introduz o primeiro framework para Aprendizagem para Adiar online sob feedback de bandit, onde tanto a distribuição de dados quanto o pool de especialistas podem variar ao longo do tempo.
2. Extensão Teórica: Estende a noção de limites de consistência-H para o cenário online, uma propriedade anteriormente limitada a análises de aprendizado em lote.
3. Garantias de Arrependimento: O algoritmo proposto alcança um limite de arrependimento de $O((n + n_e)T^{2/3})$ no caso geral, onde $n$ é o número de classes e $n_e$ é o número de especialistas distintos observados. Sob uma suposição de baixo ruído (quase realizável), isso melhora para $O((n + n_e)\sqrt{T})$.
4. Validação Empírica: A abordagem é validada em conjuntos de dados sintéticos e do mundo real (Reuters4 e CIFAR10H), demonstrando sua capacidade de se adaptar à disponibilidade variável de especialistas e à expertise em mudança.

Resultados
Os experimentos foram conduzidos sob três regimes de complexidade crescente: (1) disponibilidade e expertise fixas, (2) disponibilidade em mudança com expertise fixa e (3) configurações totalmente dinâmicas com disponibilidade e expertise em mudança.

• Dados Sintéticos: O algoritmo aprendeu com sucesso a fronteira ótima entre prever e adiar, roteando consistentemente as entradas para os especialistas disponíveis mais competentes. Manteve baixa perda de adiamento e alta precisão mesmo quando as regiões de competência dos especialistas mudaram ao longo do tempo.
• Dados do Mundo Real (Reuters4): No cenário mais desafiador (disponibilidade e expertise em mudança), o método rastreou efetivamente as regiões de competência móvel dos especialistas. Adiou com alta frequência para especialistas atualmente competentes, preservando calibração estável e alcançando precisão na tarefa comparável às linhas de base de expertise fixa.
• CIFAR10H: Usando um preditor WideResNet e especialistas anotados por humanos, o método superou uma linha de base baseada em confiança que adiava uniformemente ao acaso. A política aprendida alcançou menor perda de adiamento e maior precisão, indicando que aprendeu a rotear exemplos para os especialistas mais adequados em vez de adiar indiscriminadamente.

Significado
O artigo posiciona-se como um passo fundamental para tornar os sistemas de Aprendizagem para Adiar viáveis para ambientes do mundo real e não estacionários. Ao ir além da suposição de pools de especialistas fixos e supervisão total, os autores demonstram que métodos consistentes baseados em surrogatas podem ser tornados robustos a ambientes adversariais e à confiabilidade variável dos especialistas. O estabelecimento teórico da consistência-H no cenário online fornece uma garantia rigorosa de que minimizar a perda surrogata leva à minimização do arrependimento real de adiamento, preenchendo uma lacuna crítica entre as garantias teóricas de L2D e os requisitos práticos de dados em fluxo e sistemas de especialistas dinâmicos.