Resumo Técnico: Quando e Como Canonizar: Uma Perspectiva de Generalização

Declaração do Problema

Em domínios que envolvem dados simétricos (por exemplo, grafos, nuvens de pontos 3D, estruturas moleculares), as funções-alvo são frequentemente invariantes a ações específicas de grupos. Embora arquiteturas invariantes especializadas sejam padrão, há um interesse crescente em alcançar invariância aplicando canonização a backbones não invariantes. A canonização mapeia cada órbita de grupo para um único elemento "canônico" consistente, oferecendo eficiência computacional em comparação com a média de grupo completa. No entanto, as propriedades teóricas de generalização da canonização, particularmente como elas se comparam à média de grupo e como a qualidade de diferentes métodos de canonização afeta a aprendizagem, permanecem pouco compreendidas. Este artigo aborda a falta de um quadro teórico rigoroso para analisar o erro de generalização de modelos canonizados.

Metodologia

Os autores introduzem um quadro teórico baseado em números de cobertura para analisar o erro de generalização de modelos invariantes. Eles utilizam um quadro padrão de limite de generalização (baseado em [32]) que relaciona o erro de generalização às constantes de Lipschitz do modelo e da função-alvo, e ao número de cobertura do domínio de entrada.

O estudo compara três tipos de modelos:

1. Baselines não invariantes: $h = \tilde{h}$ (sem tratamento de simetria).
2. Modelos canonizados: $h = \tilde{h} \circ c$, onde $c$ é uma função de canonização.
3. Modelos com média de grupo: $h(x) = \int_G \tilde{h}(gx) dg$.

O núcleo da metodologia envolve a derivação de limites superiores para o erro de generalização desses modelos, limitando os números de cobertura de seus respectivos domínios:

• Não invariante: O espaço original $K$.
• Canonizado: A imagem da canonização $c(K)$.
• Com média de grupo/Invariante: O espaço quociente $K/G$.

Os autores estabelecem uma hierarquia de números de cobertura: $N(K/G) \leq N(c(K)) \leq N(K)$. Eles investigam ainda as condições sob as quais uma canonização $c$ atinge o limite inferior (ótimo) ou o limite superior (pobre), vinculando essas propriedades à continuidade e isometria da função de canonização.

Principais Contribuições

1. Hierarquia de Generalização de Canonização vs. Média de Grupo

O artigo prova que os limites de erro de generalização de modelos canonizados são no máximo iguais aos de modelos com média de grupo e no mínimo iguais às baselines não invariantes.

• Resultado Teórico: $N(K/G, \rho_G, \epsilon) \leq N(c(K), \rho, \epsilon) \leq N(K, \rho, \epsilon)$.
• Implicação: Embora a canonização ofereça vantagens computacionais (processar um único representante), ela pode vir acompanhada de um custo de desempenho de generalização reduzido em comparação com a média de grupo, dependendo da canonização específica utilizada.

2. O Papel da Continuidade e Isometria

Os autores caracterizam canonizações "ótimas" e "pobres" com base em sua regularidade:

• Canonizações Ótimas: Canonizações isométricas (onde $\rho(c(x), c(y)) = \rho_G([x], [y])$) atingem o limite inferior ótimo de números de cobertura, igualando o desempenho da média de grupo. Exemplos incluem ordenação para permutações e centralização para translações. Crucialmente, canonizações isométricas são sempre contínuas.
• Canonizações Pobres: Canonizações descontínuas podem levar a um desempenho "pobre", onde o número de cobertura da imagem canonizada iguala-se ao do espaço não invariante original. O artigo demonstra que, se uma canonização possui $|G|$ limites parciais em um ponto (descontinuidade forte), um domínio adversário pode ser construído onde o limite de generalização degrada-se ao de um modelo não invariante.

3. Estudo de Caso: Ordenação Lexicográfica vs. Canonização por Curva de Hilbert

Aplicando o quadro ao processamento de nuvens de pontos (grupo de permutação $S_n$):

• Ordenação Lexicográfica (Lexsort): O artigo prova que o número de cobertura do Lexsort cresce exponencialmente com o número de pontos $n$ (especificamente, $\Omega((1/2\epsilon)^{(d-1)n+1})$). Isso é atribuído às descontinuidades severas do Lexsort quando a primeira coordenada dos pontos é idêntica.
• Canonização por Curva de Hilbert: Em contraste, o número de cobertura da canonização por curva de Hilbert cresce apenas polinomialmente em $n$.
• Significado: Isso fornece a primeira justificativa teórica formal para o sucesso empírico da serialização por curva de Hilbert em arquiteturas de última geração como o Point Transformer V3 [30], explicando por que ela supera o Lexsort em generalização.

Resultados Experimentais

Os autores conduziram experimentos para validar suas alegações teóricas:

• Cobertura no ModelNet: Usando dados reais de nuvens de pontos, a "cobertura" (um proxy para número de cobertura) seguiu a hierarquia teórica: Distância de grupo (quociente) < Hilbert < Lexsort < Euclidiano (não invariante).
• Desempenho de Classificação: No ModelNet10 e ModelNet40, um MLP simples com canonização de Hilbert alcançou a maior precisão de teste e o menor erro de generalização (Precisão de Teste - Precisão de Treinamento), superando tanto o Lexsort quanto as baselines não invariantes.
• Média de Grupo vs. Canonização: Experimentos no ModelNet (usando PCA para rotação) e MNIST Rotacionado confirmaram que a média de grupo (ou aumento aproximando-a) geralmente supera a canonização em termos de precisão, apoiando a hierarquia teórica onde a média é ótima.
• Embeddings Espectrais: Experimentos adicionais em embeddings espectrais de grafos (ogbg-molpcba) mostraram que o aumento de grupo aleatório (aproximando a média) performou comparavelmente à canonização determinística, consistente com a teoria de que, para grupos pequenos, a lacuna pode ser negligenciável, mas a hierarquia se mantém.

Significado e Alegações

O artigo alega fornecer a primeira justificativa teórica formal para a preferência empírica da serialização por curva de Hilbert sobre a ordenação lexicográfica no processamento de nuvens de pontos. Ele estabelece uma metodologia rigorosa para comparar diferentes estratégias de canonização via números de cobertura, deslocando o foco de meramente distinguir exemplos simétricos para analisar as propriedades geométricas (regularidade/continuidade) que influenciam a generalização.

Os autores concluem que, embora modelos com média de grupo sejam teoricamente preferíveis para generalização, eles são frequentemente intratáveis computacionalmente. Portanto, a escolha da canonização é crítica: canonizações contínuas e isométricas (como curvas de Hilbert) são necessárias para aproximar os limites de generalização da média de grupo, enquanto canonizações descontínuas (como Lexsort) arriscam degradar o desempenho ao nível de modelos não invariantes. O trabalho complementa a literatura existente ao destacar que a qualidade da função de canonização, especificamente sua continuidade, é um fator decisivo no desempenho de aprendizagem.