📊 statistics

An Optimal Agnostic PAC Algorithm

Este artigo apresenta um algoritmo de aprendizagem PAC agnóstica para classificação binária que alcança um limite de risco estatisticamente ótimo, estabelecendo a complexidade de amostra até constantes universais ao igualar limites inferiores estabelecidos.

Autores originais: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Publicado 2026-08-07

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando ensinar um robô a distinguir entre gatos e cachorros. Você mostra a ele milhares de fotos, mas o mundo é bagunçado: às vezes o gato está escondido no escuro, às vezes o cachorro está usando um chapéu e, às vezes, os rótulos que você fornece ao robô estão simplesmente errados. Este é o mundo do aprendizado de máquina, especificamente um campo chamado teoria do aprendizado estatístico. A grande questão aqui é: quantos exemplos um robô precisa ver antes de se tornar bom em adivinhar?

Para responder a isso, os cientistas usam um conceito chamado dimensão VC (nomeado em homenagem a Vapnik e Chervonenkis). Pense na dimensão VC como uma medida de quão "confuso" ou "complexo" é o céreu do robô. Um cérebro simples que olha apenas para o formato das orelhas tem uma dimensão VC baixa; um cérebro supercomplexo que olha para cada pixel individual tem uma dimensão VC alta. O objetivo é encontrar um "ponto ideal" onde o robô aprenda rápido o suficiente para ser útil, mas não seja tão complexo a ponto de memorizar as fotos de treinamento em vez de aprender as regras. Por décadas, matemáticos tentaram encontrar a fórmula perfeita que nos diz exatamente quanto de erro "extra" um robô cometerá em comparação com o melhor robô possível, dados um certo número de exemplos e um certo nível de complexidade.

Por muito tempo, houve uma lacuna em nosso conhecimento. Sabíamos a velocidade máxima de aprendizado quando os dados eram perfeitos (sem erros nos rótulos) e sabíamos a velocidade quando os dados eram muito bagunçados. Mas e o meio termo? E se os dados estiverem apenas um pouco ruidosos? Tentativas anteriores de resolver isso foram como tentar correr uma corrida com uma mochila pesada; elas estavam próximas, mas carregavam um peso "logarítmico" extra que as tornava mais lentas do que precisavam ser. A grande questão era: podemos construir um aprendiz que corra na velocidade absolutamente mais rápida possível, não importa o quanto de ruído haja nos dados, sem carregar esse peso extra?

Este artigo, intitulado "An Optimal Agnostic PAC Algorithm", responde a essa pergunta com um "sim" retumbante. Os autores, Markus Engelund Mathiasen, Jian Qian e Nikita Zhivotovskiy, construíram um algoritmo de aprendizado específico que alcança o limite de risco estatisticamente ótimo. Em termos simples, isso significa que eles encontraram uma maneira de treinar um classificador que comete o menor número possível de erros, provando matematicamente que nenhum outro método pode superá-los (até certos constantes universais) para qualquer nível fixo de ruído. Eles não apenas adivinharam; eles provaram.

Aqui está como eles fizeram isso, usando uma história sobre uma biblioteca muito organizada e um jogo inteligente de "um-incluído".

O Problema: A Biblioteca Ruidosa

Imagine uma biblioteca enorme onde cada livro é uma foto, e cada livro tem um rótulo na lombada dizendo "Gato" ou "Cachorro". No entanto, o bibliotecário é um pouco desastrado. Às vezes ele rotula um livro incorretamente, ou o livro está danificado. Você quer construir um sistema que possa olhar para um novo livro, sem rótulo, e adivinhar seu rótulo corretamente.

O sistema "melhor possível" (vamos chamá-lo de Oráculo) conhece as verdadeiras regras do universo. Mesmo o Oráculo cometerá alguns erros porque os rótulos do bibliotecário às vezes estão errados. Essa taxa de erro mínima é chamada de $L^*$ . Seu objetivo é construir um sistema que chegue o mais próximo possível do desempenho do Oráculo, usando um número limitado de livros ( $n$ ) da biblioteca.

O artigo prova que o novo sistema deles, vamos chamá-lo de O Otimizador, terá uma taxa de erro ( $L(\hat{h})$ ) que é limitada por:
$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
Não deixe a matemática te assustar. A parte principal é o termo da raiz quadrada. Esta fórmula diz que os erros extras que você comete (o "risco excessivo") diminuem à medida que você obtém mais livros ( $n$ ), e diminuem na velocidade mais rápida permitida pelas leis da probabilidade. Métodos anteriores tinham fatores extras (como $\log(n)$ ) que os tornavam mais lentos, mas O Otimizador elimina esses fatores.

O Ingrediente Secreto: O Cubo e a Orientação

Como eles fizeram isso? Eles usaram uma combinação brilhante de duas ideias: O Gráfico de Um-Inclusão e a Média de Sufixo.

1. O Gráfico de Um-Inclusão (O Jogo do Cubo)
Imagine todas as formas possíveis de os livros em sua amostra serem rotulados. Se você tem $n$ livros, existem $2^n$ combinações possíveis de rótulos. Você pode visualizar essas combinações como os cantos de um cubo gigante multidimensional (um "cubo Booleano").

Dois cantos são conectados por uma aresta se diferirem em exatamente um rótulo de livro.
O "Oráculo" (a melhor regra possível) vive em algum lugar deste cubo.
O objetivo é descobrir em qual direção apontar quando você está em um canto, para que você se mova mais perto do Oráculo.

Os autores usam uma técnica chamada orientação. Imagine que você está parado em um canto deste cubo. Você precisa decidir para que lado ir. O artigo introduz uma ferramenta matemática nova chamada Lema 2.1, que é uma "desigualdade isoperimétrica dependente da classe". Em nossa analogia da biblioteca, isso é como uma regra que diz: "O número de caminhos que você precisa verificar para encontrar a direção certa depende de quão longe você está do Oráculo e de quão complexa é a biblioteca".

Eles provam que você pode atribuir uma direção a cada aresta neste cubo gigante de tal forma que, não importa onde você comece, você nunca terá que dar mais do que um número específico de passos para chegar perto da resposta certa. Este passo é crucial porque transforma um jogo de adivinhação bagunçado em um caminho determinístico.

2. Média de Sufixo (O Voto do Comitê)
Uma vez que tenham essa orientação perfeita, eles precisam transformá-la em um preditor do mundo real. Eles usam um truque chamado média de sufixo.
Imagine que você está construindo uma equipe de especialistas. Você não pede apenas a opinião de um especialista. Em vez disso, você pede a opinião de uma série de especialistas que viram quantidades ligeiramente diferentes de dados.

O Especialista 1 viu os primeiros $k$ livros.
O Especialista 2 viu os primeiros $k+1$ livros.
...
O Especialista $m$ viu os primeiros $2k-1$ livros.

A previsão final é a média das opiniões de todos esses especialistas. Isso é poderoso porque suaviza a aleatoriedade. Se um especialista tiver azar com um livro ruidoso, os outros o equilibram. O artigo prova que este processo de média, combinado com a orientação perfeita do cubo, mantém a taxa de erro baixa mesmo quando os dados são ruidosos.

3. O Polimento Final: Limiarização (Thresholding)
O resultado médio é um número entre -1 e 1 (uma "pontuação"). Para obter uma resposta final de "Gato" ou "Cachorro", eles usam um limiar (threshold). Eles testam alguns pontos de corte diferentes em um conjunto separado de livros de validação para escolher o que funciona melhor. Este passo garante que o resultado final seja uma regra simples e determinística (um classificador binário) em vez de uma probabilidade difusa.

Por Que Isso Importa

Antes deste artigo, se você quisesse a taxa de aprendizado mais rápida possível, tinha que escolher entre métodos que funcionavam bem para dados perfeitos e métodos que funcionavam bem para dados bagunçados. Você não podia ter o melhor dos dois mundos sem pagar uma penalidade.

Este artigo mostra que você pode, sim, ter o melhor dos dois mundos. Eles construíram um aprendiz que:

Não precisa conhecer o nível de ruído: Ele funciona sem saber o quão bagunçados são os dados ( $L^*$ ) ou o quão confiante você quer estar ( $\delta$ ).
É ótimo: Ele corresponde ao limite inferior teórico (a velocidade limite do aprendizado) estabelecido por pesquisadores anteriores como Devroye, Györfi e Lugosi.
É determinístico: Não depende da sorte; dá a mesma resposta toda vez que você o executa nos mesmos dados.

Os autores explicitamente descartam a ideia de que precisamos de fatores "polilogarítmicos" (aqueles atrasos extras) para obter resultados ótimos no cenário agnóstico (com ruído). Eles provam que esses fatores são desnecessários. Eles também mostram que, embora alguns métodos anteriores (como votos de maioria simples) funcionem bem para dados perfeitos, eles falham em manter a velocidade ótima quando o ruído é introduzido.

Em suma, este artigo fecha um capítulo de longa data na história da teoria do aprendizado de máquina. Ele fornece o algoritmo "perfeito" para classificação binária no mundo real, onde os dados nunca são perfeitos. É um pouco como encontrar um mapa que garante que você possa chegar ao tesouro no número mínimo de passos, não importa quantos buracos existam na estrada. Os autores não apenas sugeriram que isso era possível; eles construíram o mapa e provaram que ele funciona.

Resumo Técnico: Um Algoritmo PAC Agnóstico Ótimo

Enunciado do Problema
O artigo aborda o problema fundamental de determinar limites de risco agudos (sharp) no aprendizado Probably Approximately Correct (PAC) agnóstico para classificação binária. Seja $H \subseteq \{-1, +1\}^{\mathcal{X}}$ uma classe de hipóteses com dimensão VC $d \geq 1$ . Dado um exemplo i.i.d. $S$ de tamanho $n$ de uma distribuição sobre $\mathcal{X} \times \{-1, +1\}$ , o objetivo é construir um aprendiz que produza um classificador $\hat{h}$ tal que seu risco $L(\hat{h})$ seja próximo do risco ótimo $L^* = \min_{h \in H} L(h)$ .

Historicamente, os limites neste cenário foram derivados via dois regimes distintos:

Caso Realizável ( $L^*=0$ ): Taxas ótimas de $O(d/n)$ são alcançadas usando argumentos combinatórios como o grafo de uma inclusão (Haussler, Littlestone, Warmuth) ou esquemas de agregação específicos.
Caso Agnóstico ( $L^* > 0$ ): Métodos clássicos de processos empíricos (encadeamento, cobertura) produzem taxas ótimas de $O(\sqrt{d/n})$ quando $L^*$ está afastado de zero.

A questão em aberto, estabelecida por limites inferiores de Devroye, Györfi e Lugosi, é se um único algoritmo pode alcançar a taxa ótima em todo o espectro de $L^*$ , especificamente correspondendo ao limite:
$L(\hat{h}) \leq L^* + C \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
Limites superiores anteriores ou incorriam em fatores polilogarítmicos subótimos no termo de taxa rápida ou exigiam condições específicas sobre $L^*$ (por exemplo, $L^* \lesssim (d+\log(1/\delta))/n$ ) para alcançar a otimalidade.

Metodologia
Os autores constroem um aprendiz determinístico, geralmente impróprio, que alcança o limite ótimo sem conhecimento prévio de $L^*$ ou do parâmetro de confiança $\delta$ . A metodologia procede em três estágios principais:

Isoperimetria Dependente da Classe (Seção 2):
A inovação teórica central é o Lema 2.1, uma desigualdade isoperimétrica de aresta dependente da classe no cubo Booleano. Diferente de resultados anteriores que limitam contagens de arestas apenas pela dimensão VC ou distância a uma traço, este lema introduz pesos $w_{v,p}$ que satisfazem simultaneamente:
- $w_{v,p} + w_{v \oplus p, p} = 1$ (particionamento de arestas).
- $\sum_{p \in D} w_{v,p} \leq \rho_F(v) + R_D(F)$ , onde $\rho_F(v)$ é a distância de Hamming até um traço $F$ e $R_D(F)$ é a largura de Rademacher não normalizada da projeção de $F$ sobre as coordenadas $D$ .
Esta desigualdade permite um limite localizado no número de arestas induzidas $|E_U|$ em um subgrafo, controlando-as via tanto a distância ao traço ótimo quanto a complexidade da projeção.
Orientação Ótima Leave-One-Out (Seção 2):
Usando o Teorema do Casamento de Hall, os autores convertem a desigualdade isoperimétrica em uma orientação determinística $\sigma$ do cubo Booleano completo. Esta orientação garante que, para qualquer vértice $v$ , o grau de saída seja limitado por:
$\text{out}(v; \sigma) \leq \rho_F(v) + 120\sqrt{d \rho_F(v)} + 7202d$
Isso leva a uma regra leave-one-out onde o erro esperado é limitado pelo risco empírico ótimo mais um termo que escala com $\sqrt{d L^*/n}$ e $d/n$ .
De Leave-One-Out para Limites PAC (Seção 3):
Para converter a regra leave-one-out em uma garantia PAC de alta probabilidade, os autores empregam um processo de dois passos de desrandomização e média:
- Simetrização e Média de Sufixo: A regra leave-one-out determinística é simetrizada sobre permutações. Um preditor randomized $\hat{p}$ é construído ao médio os scores simetrizados sobre um sufixo da amostra (índices $k$ a $2k-1$ ). Este passo utiliza argumentos de martingales reversos e diretos (Lemmas 3.1 e 3.2) adaptados de Aden-Ali et al. para controlar a variância e o desvio do excesso de risco, garantindo que o limite seja uniforme em $L^*$ .
- Limiarização (Thresholding) e ERM: O preditor randomized $\hat{p}$ (que assume valores em $[-1, 1]$ ) é convertido em um classificador binário determinístico. Isso é feito considerando uma classe de hipóteses limiares $T_{\hat{p}} = \{ x \mapsto 2\mathbb{1}[\hat{p}(x) \geq u] - 1 \}$ . Um minimizador de risco empírico (ERM) é selecionado desta classe usando uma amostra de validação independente. Crucialmente, a estrutura aninhada da classe de limiares permite um limite de entropia local sem incorrer em um fator logarítmico adicional no tamanho da amostra, preservando o coeficiente ótimo de $L^*$ .

Principais Contribuições e Resultados
O artigo prova o Teorema 1, estabelecendo a existência de um aprendiz determinístico que, para qualquer distribuição, tamanho de amostra $n$ e confiança $\delta$ , produz um classificador $\hat{h}$ satisfazendo:
$L(\hat{h}) \leq L^* + 2 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(48/\delta))}{n}} + \frac{d + \log(48/\delta)}{n} \right)$
com probabilidade de pelo menos $1-\delta$ . A derivação final na prova do Teorema 1 resulta em uma constante mais apertada de aproximadamente $3.1 \cdot 10^7$ .

Otimalidade: Este limite corresponde aos limites inferiores de Devroye, Györfi e Lugosi até constantes universais. É o primeiro resultado a alcançar a taxa ótima para cada $L^*$ fixo, unindo o regime realizável e o regime totalmente agnóstico sem fatores polilogarítmicos subótimos.
Propriedades Algorítmicas: O aprendiz é determinístico, geralmente impróprio (produzindo um classificador que não é necessariamente em $H$ ) e não requer conhecimento de $L^*$ ou $\delta$ .
Novidade Técnica: A prova baseia-se na nova desigualdade isoperimétrica de aresta dependente da classe (Lema 2.1), que controla contagens de arestas induzidas através de uma combinação de erros de aproximação e larguras de Rademacher projetadas, uma técnica distinta de abordagens combinatórias ou puramente de processos empíricos anteriores.

Significância
O artigo afirma resolver a complexidade de amostragem do aprendizado PAC agnóstico até constantes universais. Ao construir um algoritmo que atinge o limite de risco excesso minimax para classificação binária em cada $L^*$ fixo, os autores resolvem uma questão aberta de longa data sobre a existência de um único algoritmo que seja ótimo em todo o espectro de níveis de ruído. O trabalho demonstra que a taxa ótima é alcançável sem sacrificar o coeficiente principal do termo $L^*$ , um feito anteriormente considerado difícil devido à tensão entre as técnicas de análise realizável e agnóstica.

O Problema: A Biblioteca Ruidosa

O Ingrediente Secreto: O Cubo e a Orientação

Por Que Isso Importa

Resumo Técnico: Um Algoritmo PAC Agnóstico Ótimo

Mais como este