Strategic PAC Learnability via Geometric Definability

Resumo Técnico: Aprendibilidade PAC Estratégica via Definibilidade Geométrica

Declaração do Problema
A classificação estratégica aborda cenários de aprendizado onde indivíduos modificam suas características a um custo para influenciar a decisão de um classificador. Uma questão fundamental neste campo é se a aprendibilidade de uma classe de hipóteses subjacente $\mathcal{H}$ é preservada quando os indivíduos agem estrategicamente. Especificamente, a classe de hipóteses estratégica induzida $\mathcal{H}^N$ (onde $N$ representa a relação de vizinhança induzida pelo custo) permanece PAC-aprendível, e como sua complexidade de amostra se relaciona com a complexidade de $\mathcal{H}$ e a estrutura de custos?

Trabalhos anteriores estabeleceram resultados positivos para configurações específicas, como classificador lineares com custos de norma ou classes fechadas sob escalonamento de entrada. No entanto, a relação geral entre simplicidade combinatória (por exemplo, baixa dimensão VC) e aprendibilidade estratégica permaneceu sem resolução. O artigo investiga se estruturas de custos "simples" e classes de hipóteses são suficientes para garantir que o comportamento estratégico não torne um problema de aprendizado intratável.

Metodologia e Estrutura
Os autores empregam uma abordagem dual: demonstrar o fracasso da aprendibilidade em configurações combinatórias gerais e restaurá-la através de suposições de definibilidade geométrica enraizadas na teoria dos modelos.

1. Resultado Negativo (Simplicidade Combinatória é Insuficiente):
   O artigo constrói um contraexemplo mostrando que o comportamento estratégico pode destruir a aprendibilidade mesmo nas configurações mais simples. Eles definem uma classe de hipóteses $\mathcal{H}$ sobre a reta real $\mathbb{R}$ com dimensão VC 1 e um sistema de vizinhança de intervalo uniforme (pontos podem se mover dentro de um raio fixo $r$). Apesar da complexidade mínima tanto da classe quanto da estrutura de custos, a classe estratégica induzida $\mathcal{H}^N$ é mostrada como tendo dimensão VC infinita, tornando-a não PAC-aprendível. Esta construção depende da codificação de subconjuntos arbitrários de índices em intervalos disjuntos, permitindo que a transformação estratégica quebre (shatter) conjuntos finitos arbitrariamente grandes.

2. Resultado Positivo (Definibilidade Geométrica):
   Para superar o resultado negativo, os autores introduzem uma suposição estrutural: Definibilidade Geométrica. Eles modelam tanto a classe de hipóteses quanto a relação de vizinhança usando fórmulas de primeira ordem sobre a estrutura $\mathbb{R}_{\exp}$ (o corpo real expandido com a função exponencial).

   • Definibilidade em $\mathbb{R}_{\exp}$: Hipóteses e vizinhanças são definidas por fórmulas envolvendo operações aritméticas ($+, \cdot$), comparações ($<, =$) e a função exponencial ($\exp$), juntamente com logaritmos (via $\exp$). Isso captura uma ampla gama de classes naturais, incluindo classificadores lineares, funções de limiar polinomiais, redes neurais com ativações padrão e funções de custo baseadas em normas $\ell_p$, distância de Wasserstein e divergência KL.
   • Transformação Estratégica como Quantificação Existencial: A hipótese estratégica induzida $h^N(x) = 1$ se e somente se $\exists x' \in N_x$ tal que $h(x') = 1$. Isso introduz um quantificador existencial na fórmula definidora.
   • Ferramentas da Teoria dos Modelos: A análise aproveita o fato de que $\mathbb{R}_{\exp}$ é uma estrutura o-minimal (teorema de Wilkie). Em estruturas o-minimais, conjuntos definíveis admitem decomposições celulares finitas e possuem funções de crescimento limitadas polinomialmente. Os autores utilizam resultados da topologia suave e decomposição celular efetiva (especificamente para conjuntos Pfaffianos restritos) para limitar a função de crescimento da classe estratégica induzida.

Contribuições e Resultados Principais

1. Não-Aprendibilidade Estratégica:
   O artigo prova que o comportamento estratégico pode transformar um problema aprendível (dimensão VC 1) em um não aprendível (dimensão VC infinita) mesmo sob vizinhanças de intervalo simples. Isso demonstra que a simplicidade combinatória por si só é insuficiente para garantir a aprendibilidade estratégica.

2. Aprendibilidade Qualitativa via $\mathbb{R}_{\exp}$:
   O Teorema Principal 2 estabelece que, se tanto a classe de hipóteses $\mathcal{H}$ quanto o sistema de vizinhança $N$ forem definíveis em $\mathbb{R}_{\exp}$, então a classe estratégica induzida $\mathcal{H}^N$ é PAC-aprendível. A complexidade de amostra é controlada pelo número de parâmetros $k$ usados nas fórmulas definidoras. Especificamente, a função de crescimento $\Pi_{\mathcal{H}^N}(m)$ é limitada por $C m^k$, implicando dimensão VC finita. Este resultado depende da o-minimalidade de $\mathbb{R}_{\exp}$ e do teorema de crescimento polinomial para famílias definíveis.

3. Limites Quantitativos (Caso Semialgébrico):
   O Teorema Principal 3 fornece limites explícitos e construtivos para o caso em que as definições são restritas à linguagem do corpo real $\mathbb{R}$ (fórmulas livres de quantificadores envolvendo polinômios, ou seja, conjuntos semialgébricos). Ao aplicar eliminação quantitativa de quantificadores (Tarski-Seidenberg), os autores derivam limites explícitos para a dimensão VC e a complexidade de amostra em termos da complexidade de descrição $D$ (número de polinômios e seus graus).

   • Resultado: $VC(\mathcal{H}^N) = O(k^2 l \log D)$ e a complexidade de amostra escala de forma similar.

4. Limites Quantitativos (Caso Existencial $\mathbb{R}_{\exp}$):
   O Teorema Principal 4 estende a análise quantitativa para a configuração completa de $\mathbb{R}_{\exp}$, restrita a fórmulas existenciais ($\Sigma_1$). Isso cobre muitos cenários estratégicos naturais (por exemplo, bolas $\ell_p$, Distância Earth Mover) onde a relação de vizinhança é definida por um quantificador existencial.

   • Os autores definem "formato" ($F$) e "grau" ($D$) para essas fórmulas.
   • Resultado: $VC(\mathcal{H}^N) = O_F(\log D)$ e a complexidade de amostra é $O\left(\frac{k \log(1/\varepsilon) + \gamma(F) \log D + \log(1/\delta)}{\varepsilon}\right)$, onde $\gamma$ é uma função explicitamente computável.
   • A prova utiliza teoremas de decomposição celular efetiva para estruturas Pfaffianas restritas para lidar com a função exponencial.

Significado e Alegações
O artigo afirma resolver a tensão entre simplicidade combinatória e aprendibilidade estratégica ao identificar a suavidade geométrica como o fator crucial.

• Limitação das Medidas Combinatórias: O trabalho demonstra que a baixa dimensão VC da classe base não implica aprendibilidade sob manipulação estratégica; a estrutura da função de custo e da classe de hipóteses importa fundamentalmente.
• Restauração via Definibilidade: Ao restringir a atenção a classes geométricas "suaves" (definíveis em $\mathbb{R}_{\exp}$), o artigo mostra que a aprendibilidade estratégica é restaurada. A complexidade da classe estratégica é controlada pela complexidade lógica (número de parâmetros, formato e grau) das fórmulas definidoras, em vez da complexidade combinatória bruta da classe induzida.
• Escopo: A estrutura captura uma ampla variedade de cenários práticos, incluindo classificadores polinomiais, árvores de decisão, redes neurais com ativações comuns e várias métricas de distância ($\ell_p$, KL, Wasserstein).
• Limitações: Os autores observam que seus resultados positivos dependem da "suavidade" das estruturas. Vizinhanças com estruturas oscilatórias ou periódicas ilimitadas (por exemplo, definidas por $\sin$) ficam fora da estrutura $\mathbb{R}_{\exp}$ e podem levar à não aprendibilidade. Além disso, os limites quantitativos para $\mathbb{R}_{\exp}$ estão atualmente restritos a fórmulas existenciais; quantificadores universais são tratados apenas qualitativamente.

Em resumo, o artigo estabelece que, embora o comportamento estratégico possa aumentar catastroficamente a complexidade de aprendizado em geral, essa patologia é evitada para uma ampla e natural classe de problemas geométricos definidos pela lógica de primeira ordem sobre os reais com exponenciação. A complexidade de amostra desses problemas é governada pela complexidade descritiva das definições geométricas subjacentes.