Local Regularization Does Not Characterize Multiclass PAC Learnability

Resumo Técnico: A Regularização Local Não Caracteriza a Aprendizabilidade PAC Multiclasse

Enunciado do Problema
Uma questão central na teoria do aprendizado estatístico é identificar princípios algorítmicos simples que caracterizem a aprendizabilidade de classes de hipóteses. Na classificação binária, a Minimização do Risco Empírico (ERM) caracteriza a aprendizabilidade PAC. No entanto, o cenário multiclasse é mais complexo; o aprendizado próprio pode falhar para classes aprendíveis, e os aprendizes otimizados frequentemente dependem de estruturas dependentes da amostra, em vez de ordenações fixas de hipóteses.

Asilis et al. propuseram a regularização local como uma potencial generalização do ERM para o cenário multiclasse. Um regularizador local atribui um escore fixo $\psi(h, x)$ para cada hipótese $h$ em cada ponto de teste $x$, independentemente da amostra de treinamento. Um aprendiz induzido por tal regularizador prevê o rótulo da hipótese com o menor escore entre aquelas consistentes com a amostra observada. Embora Jafar, Asilis e Dughmi tenham demonstrado anteriormente que a regularização local falha em caracterizar a aprendizabilidade no modelo transdutivo (onde um ponto específico retido é testado), permanecia uma questão em aberto se esse princípio caracteriza a aprendizabilidade PAC, onde o ponto retido pode carregar uma massa populacional negligenciável e a amostragem repetida poderia, teoricamente, revelá-lo.

Metodologia e Construção
O artigo constrói um contraexemplo usando uma classe de hipóteses enumerável baseada em torneios (grafos completos direcionados).

• Classe de Hipóteses ($H$): Para um inteiro $q \ge 3$, as hipóteses correspondem às arestas de um grafo completo $K_q$. Uma hipótese $h_{q,e}$ prevê a "cabeça" (vértice alvo) da aresta $e$ dentro de uma instância de torneio $\tau$.
• Espaço de Instâncias: Instâncias são pares $(q, \tau)$, onde $\tau$ é um torneio sobre $q$ vértices.
• Distribuições Difíceis: Os autores definem uma família de distribuições "difíceis" $D_{e,v}$ para uma aresta alvo $e=\{u,v\}$ e um ponto final $v$. Estas distribuições são uniformes sobre torneios onde a aresta $e$ é orientada para $v$. Consequentemente, todos os rótulos observados na amostra de treinamento são idênticos: $(q, v)$.
• O Mecanismo de Falha:
  1. Filtragem: A amostra de treinamento (todos os rótulos iguais a $v$) filtra o espaço da versão, retendo apenas as hipóteses correspondentes a arestas incidentes a $v$ que estão orientadas para $v$ nos torneios amostrados.
  2. Ranking Fixo: O regularizador local $\psi$ impõe uma ordenação total estrita sobre as arestas incidentes a $v$ no ponto de teste antes da amostra ser observada.
  3. Inversões Cíclicas: A dificuldade central surge dos triângulos cíclicos no torneio. Mesmo que a amostra de treinamento remova muitos competidores, a ordenação fixa das arestas restantes pode ser "invertida" em relação ao alvo real devido à estrutura cíclica. Especificamente, se uma aresta de saída (que não deveria ser o alvo) sobreviver ao processo de filtragem e aparecer antes da aresta de entrada alvo na classificação fixa do regularizador, o aprendiz comete um erro.

Principais Contribuições e Resultados

1. Existência de um Contraexemplo: O artigo prova a existência de uma classe de hipóteses multiclasse enumerável $H$ que é aprendível via PAC, mas não é aprendível por qualquer regularizador local.

   • Aprendizabilidade: A classe é aprendível via PAC com uma complexidade de amostra de $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$. Um aprendiz explícito tem sucesso ao identificar a aresta alvo assim que ambos os rótulos dos pontos finais aparecem na amostra.
   • Limite de Dimensão: A classe possui uma dimensão Daniely–Shalev-Shwartz (DS) de no máximo 2. Isso é estabelecido mostrando que a imagem de cada hipótese contém no máximo dois rótulos, impedindo a formação de um pseudo-cubo de 3 dimensões.

2. Teorema de Impossibilidade: Para qualquer regularizador local $\psi$, existe um aprendiz induzido $A_\psi$ que falha em aprender $H$ via PAC.

   • Modo de Falha: Para qualquer regularizador fixo, os autores mostram que, para tamanhos de amostra $n$ arbitrariamente grandes, existem distribuições realizáveis onde a probabilidade de erro excede uma constante $\delta_0 = \frac{1}{192e}$.
   • Limites Quantitativos: A probabilidade de erro é limitada longe de zero ($\varepsilon_0 = \frac{1}{96e}$) porque o número esperado de "inversões" (arestas de saída classificadas antes de arestas de entrada) na estrutura do torneio permanece significativo. A prova utiliza o fato de que um torneio aleatório contém $\Theta(q^3)$ triângulos cíclicos, garantindo que, para qualquer ordenação estrita de arestas, uma fração constante de incidências alvo resultará em erro de previsão.

Significância e Alegações
O artigo conclui que a regularização local não caracteriza a aprendizabilidade PAC multiclasse realizável.

• Distinção de Resultados Transdutivos: Diferente do limite inferior transdutivo de Jafar et al., que se baseia em um único ponto retido com potencialmente negligível massa, esta construção distribui o erro através de uma população de torneios. A falha persiste mesmo quando os tamanhos de amostra crescem arbitrariamente, impedindo o aprendiz de "aprender" a estrutura oculta através de amostragem repetida.
• Limitação de Escores Fixos: O resultado destaca uma rigidez fundamental na regularização local: como a classificação das hipóteses em um ponto de teste é fixa antes de observar a amostra, o aprendiz não pode adaptar a ordenação relativa dos competidores sobreviventes com base na estrutura específica dos dados de treinamento. No cenário de torneio, essa incapacidade de reordenar leva a um erro populacional constante, apesar de a classe possuir baixa dimensão DS e ser eficientemente aprendível por outros meios.
• Escopo: O resultado aplica-se especificamente a regularizadores onde os escores são fixos independentemente da amostra. Não aborda frameworks não supervisionados onde a regra de regularização pode depender da amostra não rotulada.

Em resumo, o artigo fornece uma resposta negativa definitiva à questão de se a regularização local caracteriza a aprendizabilidade PAC multiclasse, demonstrando que mesmo para classes com baixa dimensão combinatória (dim-DS $\le 2$) e complexidade de amostra ótima, regularizadores de escore fixo podem falhar no aprendizado.