Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks

Resumo Técnico: Aproximação Rápida e Aprendizado de Tarefas de Classificação Binária em Estruturas O-minimais usando Redes Neurais ReLU

Enunciado do Problema
O artigo investiga problemas de classificação binária onde o conjunto de decisão $A \subseteq [-1/2, 1/2]^n$ é definido dentro de uma expansão o-minimal do corpo real. Embora as redes neurais profundas tenham demonstrado sucesso empírico, a compreensão teórica de seu poder de aproximação e aprendizado estatístico frequentemente depende de suposições estruturais específicas sobre o conjunto alvo, como a suavidade da fronteira ou classes de funções do tipo Barron. Os autores visam estabelecer taxas quantitativas de aproximação e aprendizado para uma classe mais ampla de conjuntos "tame" (domados) definidos por o-minimalidade, o que inclui conjuntos semi-algébricos e várias estruturas analíticas, sem depender de suposições de suavidade global que podem não se sustentar para fronteiras de decisão complexas.

Metodologia
Os autores introduzem uma classe de conjuntos chamada conjuntos traçáveis (traceable sets) como um proxy clássico para conjuntos definíveis em estruturas o-minimais. Este conceito é motivado pelos teoremas de decomposição de células inerentes à geometria o-minimal.

1. Conjuntos Traçáveis: Um conjunto $A$ é definido como $m$-traçável se puder ser construído indutivamente via mapas $C^m$ limitados $f_i, g_i$ que definem as fronteiras do conjunto de maneira fibra a fibra. Especificamente, o conjunto é construído como uma sequência de funções de "horizonte", onde cada camada é limitada por funções suaves. Os autores definem conjuntos $(m, \ell)$-traçáveis como uniões disjuntas finitas de tais conjuntos.
2. Propriedades de Extensão: Para facilitar a aproximação, o artigo impõe uma propriedade de extensão $(m, B)$, exigindo que as funções de fronteira $f_i, g_i$ possam ser estendidas para funções $C^m$ em todo o domínio com normas de Sobolev limitadas.
3. Estratégia de Aproximação: A técnica central de aproximação envolve:
   • Aproximar as "funções de horizonte" (funções características de regiões delimitadas por grafos suaves) usando redes neurais ReLU. Isso aproveita resultados existentes sobre a aproximação de funções suaves e suas composições.
   • Construir a função característica do conjunto traçável através da composição dessas aproximações usando operações de mínimo e máximo baseadas em ReLU (visto que $\chi_{\cap} = \min$ e $\chi_{\cup} = \max$).
   • Utilizar o fato de que a fronteira (limite) desses conjuntos tem medida de Lebesgue zero sob as suposições de extensão, garantindo que a aproximação do fechamento do conjunto seja suficiente para a aproximação $L^p$.
4. Estrutura de Aprendizado: A análise de aprendizado estatístico combina as taxas de aproximação derivadas com estimativas de entropia (números de cobertura) para classes de redes neurais ReLU. Os autores aplicam a minimização do risco empírico (ERM) com perda hinge sobre essas classes específicas de redes para derivar limites de generalização.

Contribuições Principais e Resultados

• Taxas Quantitativas de Aproximação: O artigo prova que a função característica $\chi_\Omega$ de qualquer conjunto $(m, \ell)$-traçável $\Omega \subseteq [-1/2, 1/2]^n$ pode ser aproximada em norma $L^p$ com precisão $\epsilon$ por uma rede neural ReLU $\Phi_\epsilon$.

  • Tamanho da Rede: O número de pesos não nulos (tamanho) necessário é $O(\epsilon^{-p(n-1)/m})$.
  • Profundidade: A profundidade da rede é limitada independentemente de $\epsilon$, especificamente $O(\log(\ell n) + \log(m))$.
  • Pesos: Os pesos crescem, no máximo, polinomialmente em $1/\epsilon$.
  • Este resultado estende-se a uma subclasse de mapas definíveis $f: [-1/2, 1/2]^n \to \mathbb{R}$ que são suavemente por partes em domínios traçáveis.

• Taxas de Aprendizado Estatístico: Para $N$ amostras independentes extraídas uniformemente do domínio, os autores derivam taxas de aprendizado para a minimização do risco empírico sobre as classes de redes ReLU construídas.

  • O erro de classificação esperado do classificador resultante é limitado por $O(N^{-m/(m+pn-p)})$ até um fator de perda polinomial arbitrariamente pequeno $N^\kappa$.
  • Esta taxa é derivada combinando os limites de erro de aproximação com a entropia de cobertura da classe de hipóteses.

• Aplicação a Estruturas O-minimais: Os autores demonstram que coleções definíveis "$m$-admissíveis" em estruturas o-minimais (coleções de fibras de conjuntos definíveis com limites uniformes na decomposição de células) satisfazem as propriedades de conjuntos traçáveis. Consequentemente, as taxas de aproximação e aprendizado derivadas aplicam-se diretamente a essas coleções definíveis.

Significância e Alegações
O artigo afirma fornecer uma noção matematicamente robusta de regularidade para a teoria da classificação baseada na definibilidade em estruturas o-minimais. Ao isolar as características analíticas (traçabilidade e extensões suaves) necessárias para uma aproximação rápida, os autores mostram que a o-minimalidade captura uma ampla gama de conjuntos de decisão práticos, ao mesmo tempo que permite taxas fortes de aproximação e estimativa quantitativa.

A significância reside em unir a teoria dos modelos (o-minimalidade) com a teoria moderna de aprendizado profundo. Os autores argumentam que as estruturas o-minimais oferecem um arcabouço unificador natural onde a teoria da aproximação, o aprendizado estatístico e a otimização podem ser estudados simultaneamente. Diferente dos cenários do tipo Barron, que podem ter dificuldades com a composição de funções, o arcabouço o-minimal acomoda naturalmente a composição repetida de mapas afins e ativações não lineares encontradas em redes neurais profundas, uma vez que a composição de mapas definíveis permanece definível.

Os resultados sugerem que, para fronteiras de decisão que são "tame" (definíveis em uma estrutura o-minimal), as redes neurais ReLU podem alcançar taxas ótimas ou próximas do ótimo, dependendo do parâmetro de suavidade $m$ e da dimensão $n$, sem exigir que as fronteiras sejam globalmente suaves. O artigo observa explicitamente que essas taxas são derivadas para subclasses específicas de conjuntos e mapas definíveis, e que as taxas de aprendizado dependem das propriedades de finitude uniforme (limites uniformes em componentes conexas e dimensão VC) inerentes às coleções definíveis em estruturas o-minimais.