Resumo Técnico: Aprendizado com Múltiplas Respostas Corretas – Limites de Arrependimento sob Diferentes Modelos de Feedback

1. Definição do Problema e Motivação

Este trabalho aborda o problema do aprendizado online com múltiplas respostas corretas, um cenário onde uma única instância de entrada $x$ admite um conjunto de rótulos válidos $S \subseteq \mathcal{Y}$ em vez de um único rótulo alvo. Esta formulação é motivada por tarefas modernas, como geração de linguagem (onde um prompt possui muitas conclusões aceitáveis), resposta a perguntas aberta, geração de diálogo e sistemas de recomendação.

O estudo foca no paradigma de aprendizado online, procedendo em rodadas $t \in [T]$. Em cada rodada, um adversário apresenta uma instância $x_t$ e um conjunto de rótulos aceitáveis $S_t$. O aprendiz prevê um rótulo $\hat{y}_t$ e incorre em uma perda de 1 se $\hat{y}_t \notin S_t$. O artigo analisa este problema sob três modelos de feedback distintos:

1. Erro-desconhecido (Mistake-unknown): O aprendiz recebe apenas um único rótulo válido $y_t \in S_t$ (escolhido pelo adversário), mas não sabe se sua previsão estava correta.
2. Erro-conhecido (Mistake-known): O aprendiz recebe um único rótulo válido $y_t \in S_t$ e um indicador binário revelando se sua previsão $\hat{y}_t$ foi um erro.
3. Valor-de-conjunto (Set-valued): O aprendiz tem acesso ao conjunto completo de rótulos válidos $S_t$.

A análise abrange tanto o cenário realizável (onde existe uma hipótese $h^* \in \mathcal{H}$ tal que $h^*(x_t) = S_t$ para todo $t$) quanto o cenário agnóstico (onde o aprendiz compete contra a melhor hipótese em $\mathcal{H}$ minimizando a perda cumulativa).

2. Metodologia e Caracterizações Combinatórias

Os autores introduzem novas dimensões combinatórias para caracterizar a aprendibilidade de classes de hipóteses multilabel sob cada modelo de feedback. Estas dimensões são definidas via argumentos de fragmentação de árvores (tree-shattering) adaptados à informação específica disponível em cada modelo.

Dimensões Combinatórias

• Dimensão de Littlestone de Valor-de-Conjunto ($LD_{set}$): Definida em uma árvore de valor de conjunto onde os nós são rotulados com subconjuntos de $\mathcal{Y}$. Uma árvore é fragmentada (shattered) se, para cada caminho de previsões, existir uma hipótese consistente com os conjuntos revelados $S_t$, mas que cometa um erro no rótulo previsto.
• Dimensão de Littlestone de Erro-Conhecido ($LD_{known}$): Definida em uma árvore multilabel onde os nós são rotulados com rótulos únicos. A fragmentação exige consistência com o rótulo único revelado $y_t$ e um erro na previsão.
• Dimensão de Littlestone de Erro-Desconhecido ($LD_{unknown}$): Definida usando uma função de "deslocamento de erro" (mistake offset). Uma árvore é $d$-fragmentada se o número cumulativo de erros ao longo de qualquer caminho, mais um deslocamento para a hipótese, exceder $d$. Isso contabiliza a falta de feedback imediato sobre a correção.

Algoritmos

Para o cenário realizável, os autores propõem Algoritmos Ótimos Padrão (SOA) para cada modelo de feedback. Esses algoritmos mantêm um espaço de versões de hipóteses consistentes e selecionam previsões que minimizam a pior dimensão de caso do espaço de versões restante.

• SOA para Erro-Desconhecido: Mantém um espaço de versões e uma função de deslocamento, prevendo o rótulo que minimiza o máximo $LD_{unknown}$ das subclasses resultantes.
• SOA para Erro-Conhecido: Prevê para minimizar o máximo $LD_{known}$ das subclasses formadas pelo bit de erro.
• SOA para Valor-de-Conjunto: Prevê para minimizar o máximo $LD_{set}$ das subclasses formadas pelo conjunto revelado $S_t$.

3. Resultados Principais

Aprendizado Online Realizável

O artigo fornece uma caracterização completa do limite de erros ótimo para qualquer classe multilabel $\mathcal{H}$ no cenário realizável:

• Erro-desconhecido: O limite de erros ótimo é $\min(LD_{unknown}(\mathcal{H}), T)$.
• Erro-conhecido: O limite de erros ótimo é $\min(LD_{known}(\mathcal{H}), T)$.
• Valor-de-conjunto: O limite de erros ótimo é $\min(LD_{set}(\mathcal{H}), T)$.

Estes resultados generalizam trabalhos anteriores sobre classes finitas para classes de hipóteses arbitrárias (possivelmente infinitas). Os autores provam que $LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$, o que ocorre se, e somente se, a interseção de todos os conjuntos de rótulos das hipóteses para qualquer instância for não vazia.

Aprendizado Online Agnóstico (Limites de Arrependimento/Regret)

Uma contribuição significativa é a demonstração de que as taxas de arrependimento variam drasticamente entre os modelos de feedback no cenário agnóstico, contrastando com o aprendizado de rótulo único, onde o arrependimento é tipicamente $\tilde{\Theta}(\sqrt{T})$.

1. Erro-desconhecido: Os autores mostram que o arrependimento pode crescer linearmente em $T$ ($\Omega(T)$), mesmo para classes de hipóteses simples com $LD_{unknown}=1$. Isso implica que a aprendibilidade realizável (caracterizada por $LD_{unknown}$) não garante arrependimento sublinear no cenário agnóstico para este modelo de feedback.
2. Erro-conhecido: O artigo estabelece um limite superior de arrependimento sublinear de $O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T})$. Isso é alcançado reduzindo o problema a bandidos não estocásticos com conselhos de especialistas, utilizando um conjunto de especialistas baseados em SOA.
3. Valor-de-conjunto:
   • Para classes específicas (ex: a classe de exemplo $H_3$), o arrependimento é constante ($O(1)$).
   • Para classes gerais, o arrependimento é limitado por $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$. Notavelmente, este limite é independente do tamanho do espaço de rótulos $|\mathcal{Y}|$, permitendo que se aplique a espaços de rótulos infinitos.

Implicações para Aprendizado em Lote (Batch Learning)

As dimensões combinatórias e os limites online derivados implicam limites de complexidade de amostra para os correspondentes problemas de aprendizado em lote. Os autores fornecem os primeiros limites superiores conhecidos para aprendizado em lote sob o modelo de feedback de conjunto completo e melhoram os limites existentes para o caso de resposta única, passando de classes finitas para infinitas.

4. Significância e Alegações

O artigo afirma fornecer a primeira caracterização combinatória completa do aprendizado multilabel online realizável sob três distintos modelos de feedback. Sua principal significância teórica reside na separação entre a aprendibilidade realizável e agnóstica no cenário de erro-desconhecido, onde a dimensão de Littlestone padrão falha em capturar limites de arrependimento significativos.

Além disso, o trabalho destaca uma estrutura rica no aprendizado multilabel agnóstico:

• O modelo de feedback altera fundamentalmente as taxas de arrependimento alcançáveis (de linear para constante).
• O modelo de feedback de valor-de-conjunto permite arrependimento constante em classes específicas e limites independentes da dimensão para classes gerais, um fenômeno não observado no aprendizado de rótulo único.
• Os resultados sugerem que caracterizar o aprendizado multilabel agnóstico requer objetos combinatórios além daqueles suficientes para a aprendibilidade realizável.

Os autores explicitamente observam que suas definições de arrependimento diferem de trabalhos anteriores (ex: Joshi et al. [JLB+25] e Raman et al. [RST24]) para melhor alinhar-se à tarefa de predição subjacente de minimizar o erro contra o verdadeiro conjunto de rótulos aceitáveis, em vez de competir contra uma hipótese que meramente contém um rótulo específico revelado.