Realizable Bayes-Consistency for General Metric Losses

Resumo Técnico: Consistência Bayesiana Realizável para Perdas Métricas Gerais

1. Declaração do Problema

Este artigo aborda o problema da consistência Bayesiana universal forte no cenário realizável para aprendizado com perdas métricas gerais. O cenário envolve:

• Um espaço de instâncias $(X, \rho)$ e um espaço de rótulos $(Y, \ell)$, onde $\ell$ é uma métrica que pode ser ilimitada.
• Uma classe de hipóteses $\mathcal{H} \subseteq Y^X$.
• Uma distribuição geradora de dados $\bar{\mu}$ em $X \times Y$ que é realizável por $\mathcal{H}$, significando que o risco ótimo é zero ($\inf_{h \in \mathcal{H}} R_{\bar{\mu}}(h) = 0$).

O objetivo é determinar condições necessárias e suficientes sobre $\mathcal{H}$ tais que exista uma regra de aprendizado livre de distribuição cujo risco convirja para zero quase certamente para toda distribuição realizável $\bar{\mu}$.

Os autores destacam uma distinção crítica entre perdas limitadas e ilimitadas. Em cenários limitados, controlar a probabilidade de erro é sinônimo de controlar o risco. Em cenários métricos ilimitados, um aprendiz pode cometer erros em eventos com probabilidade decrescente, contudo a magnitude desses erros pode crescer tão rapidamente que o risco esperado permanece infinito ou falha em convergir para zero. O artigo busca caracterizar quando tais "falhas catastróficas de eventos raros" são evitáveis.

2. Metodologia e Estrutura Teórica

O artigo emprega uma abordagem combinatória enraizada na teoria de jogos infinitos e obstruções em árvores, estendendo frameworks previamente desenvolvidos para classificação 0-1 e regressão limitada.

Definições Chave:

• Árvore de Littlestone Infinita Não-Decrescente $(\gamma_k)$: Uma árvore binária completa onde os nós internos na profundidade $k$ são instâncias $x_{k,i}$, e as arestas de saída são rotuladas com $y_{k,i,1}, y_{k,i,2} \in Y$ tais que a distância métrica $\ell(y_{k,i,1}, y_{k,i,2}) \ge \gamma_k$. A sequência $(\gamma_k)$ é não-decrescente e diverge para infinito ($\gamma_k \to \infty$). A árvore é "realizável" se todo caminho finito da raiz à folha for consistente com alguma hipótese em $\mathcal{H}$.
• Suposição de Realizabilidade: Os autores assumem uma condição de "parametrização compacta" (Lema 4.3): $\mathcal{H}$ é parametrizado por um espaço compacto $\Theta$ com um mapa de avaliação contínuo. Sob essa suposição leve, a realizabilidade de prefixos finitos implica que todo caminho infinito é realizado por uma única hipótese.

Arquitetura da Prova:
O resultado principal é estabelecido via um limite inferior (necessidade) e um limite superior (suficiência).

• Limite Inferior (Impossibilidade): Se $\mathcal{H}$ contém uma árvore de Littlestone infinita não-decrescente $(\gamma_k)$, os autores constroem uma distribuição realizável onde o adversário esconde uma sequência de escolhas de rótulos cada vez mais separadas atrás de massas de probabilidade decrescentes rapidamente. Usando um argumento de Borel-Cantelli, eles mostram que para qualquer algoritmo de aprendizado, o risco esperado é infinito para todo tamanho de amostra $n$. O aprendiz é forçado a adivinhar entre rótulos separados por $\gamma_k$ em nós não vistos, levando a um risco divergente.
• Limite Superior (Algoritmo Construtivo): Se tal árvore não existe, os autores constroem uma regra de aprendizado livre de distribuição. A prova procede em quatro etapas:
  1. Codificação Teórica de Jogos: A ausência da obstrução da árvore implica que o aprendiz possui uma estratégia vencedora em um jogo específico de Gale-Stewart infinito contra um adversário.
  2. Estabilização: Ao simular este jogo em uma amostra i.i.d., o processo estabiliza quase certamente após um número finito de rodadas. Isso produz, para cada $x$, um conjunto de rótulos "admissíveis" $H_K(x)$ com diâmetro limitado.
  3. Particionamento: O espaço de instâncias $X$ é particionado em células enumeráveis baseadas em um subconjunto denso de $Y$. Dentro de cada célula, o conjunto de rótulos admissíveis possui diâmetro limitado.
  4. Redução: O problema é reduzido a subproblemas enumeráveis com perdas limitadas. Os autores aplicam o algoritmo existente MedNet (Tsir Cohen & Kontorovich, 2022), que é fortemente universalmente consistente de Bayes para perdas métricas limitadas, a cada célula e agregam os resultados.

3. Contribuições Principais

1. Caracterização Precisa: O artigo fornece uma condição necessária e suficiente para a consistência Bayesiana universal forte realizável sob perdas métricas gerais (possivelmente ilimitadas). A condição é a não existência de uma árvore de Littlestone infinita não-decrescente $(\gamma_k)$ na classe de hipóteses.
2. Resolução de um Problema Aberto: Este trabalho resolve o caso realizável de um problema aberto proposto por Tsir Cohen & Kontorovich (2022). Demonstra que condições naturais do tipo finitude, como a finitude do risco de Bayes ($R^* < \infty$) ou a condição "limitada na esperança" (BIE) no espaço de rótulos, são insuficientes para garantir consistência no cenário ilimitado.
3. Regra de Aprendizado Construtiva: Na ausência da obstrução da árvore, o artigo apresenta uma regra de aprendizado explícita (baseada no algoritmo MedNet e estabilização teórica de jogos) que alcança consistência Bayesiana universal forte.
4. Construção de Contraexemplo: Os autores fornecem um contraexemplo concreto (Seção 3) mostrando que mesmo quando $R^* < \infty$, nenhum aprendiz consistente livre de distribuição existe se a classe de hipóteses admitir a estrutura específica de árvore com lacuna ilimitada.

4. Resultados e Significado

O teorema central (Teorema 4.5) afirma que para espaços de Polish $(X, \rho)$ e $(Y, \ell)$ e uma classe de hipóteses $\mathcal{H}$ satisfazendo condições leves de mensurabilidade e compacidade, os seguintes são equivalentes:

1. Existe uma regra de aprendizado livre de distribuição que é fortemente universalmente consistente de Bayes para toda distribuição realizável.
2. $\mathcal{H}$ não contém uma árvore de Littlestone infinita não-decrescente $(\gamma_k)$ com $\gamma_k \to \infty$.

Significado:
O artigo esclarece que a dificuldade de aprendizado com perdas métricas ilimitadas não é meramente uma questão de integrabilidade ou condições de momento na distribuição. Em vez disso, a obstrução é combinatória e intrínseca à classe de hipóteses. A escala da ambiguidade (a lacuna entre rótulos) pode crescer sem limites ao longo da profundidade de uma árvore, criando um cenário onde eventos raros dominam o risco. Isso estende o framework clássico da árvore de Littlestone (usado para perda 0-1) e as árvores de Littlestone escaladas (usadas para regressão limitada) para o cenário métrico geral ilimitado, apontando a interação precisa entre magnitudes de perda ilimitadas e realizabilidade.

Os autores notam que estender essa caracterização para o cenário agnóstico (onde a distribuição não é necessariamente realizável) permanece uma direção aberta, citando barreiras discutidas em seu Apêndice.