Wavelet Tree Ensembles for Triangulable Manifolds

Resumo Técnico: Conjuntos de Árvores de Wavelets para Variedades Trianguláveis

Definição do Problema
O artigo aborda o desafio da regressão não paramétrica em variedades trianguláveis, como esferas ou superfícies curvas gerais. A literatura existente de regressão por wavelets geralmente se baseia em bases de wavelets definidas ao longo de árvores de partição recursivas únicas em grades euclidianas fixas e regulares (ex: intervalos dyádicos). Essas abordagens padrão enfrentam dificuldades em variedades devido à falta de eixos de coordenadas naturais e à distorção causada por sistemas de coordenadas globais. Por outro lado, métodos de conjunto baseados em árvores (ex: Florestas Aleatórias, Boosting) foram generalizados para domínios não euclidianos, mas frequentemente carecem das capacidades de representação multiescala e esparsa das wavelets, o que pode levar a alta variância ou overfitting, particularmente em regimes de baixa relação sinal-ruído. Os autores postulam que é necessária uma estrutura unificada que combine representações de wavelets ortogonais com partições recursivas orientadas por dados e técnicas de conjuntos modernas para melhorar a estimativa e a inferência nesses domínios complexos.

Metodologia
Os autores propõem os Conjuntos de Árvores de Wavelet Haar Desbalanceada (UH), uma estrutura que estende as clássicas árvores de wavelet UH de grades regulares para variedades trianguláveis genéricas. A metodologia consiste em três componentes principais:

1. Construção de Haar Desbalanceada (UH) em Variedades:

   • Em vez de pontos médios fixos, o método emprega partições recursivas orientadas por dados de triângulos geodésicos.
   • Um triângulo é dividido conectando um ponto $\xi$ em uma aresta ao vértice oposto via um arco geodésico. A localização da divisão é escolhida para maximizar o coeficiente de wavelet UH empírico, permitindo divisões "desbalanceadas" que se adaptam à variação local dos dados e à geometria.
   • As funções de wavelet resultantes formam um sistema ortonormal em $L^2(\mu_n)$, onde $\mu_n$ é a medida empírica nos pontos da amostra. Isso garante a reconstrução exata nos locais amostrados e a ortogonalidade independentemente da geometria da variedade subjacente.
   • As regras de divisão incluem "balanço" (bisseção de meio de aresta), "adapt" (escolha da aresta com o maior coeficiente) e "adapt_vertex" (escolha tanto da aresta quanto do ponto de corte baseada nos dados).

2. Estratégias de Aprendizado de Conjunto (Ensemble Learning):

   • Boosting Baseado em Otimização: Os autores desenvolvem um algoritmo de boosting de estágio progressivo (forward stagewise boosting) onde aprendizes fracos são árvores UH ajustadas aos resíduos. Para garantir a diversidade entre as árvores nas variedades, eles utilizam movimentos rígidos aleatórios (ex: rotações em $SO(3)$ para esferas) ou reparametrizações intrínsecas antes de ajustar cada árvore. A regularização é alcançada através de parada antecipada (early stopping), taxas de aprendizado e limiarização suave (soft-thresholding) dos coeficientes de wavelet na reconstrução.
   • Backfitting Bayesiano (RUHWT): Uma formulação probabilística é introduzida onde uma priori é colocada sobre as dimensões e localizações de divisão. Isso induz uma distribuição posterior sobre as estruturas de árvore, permitindo a quantificação de incerteza. Os autores utilizam um amostrador de Gibbs com passos de Metropolis-within-Gibbs para atualizar as estruturas de árvore e os coeficientes, de forma análoga às Árvores de Regressão Aditiva Bayesiana (BART).

3. Análise Teórica:

   • O artigo deriva limites de oracle comparando os estimadores UH propostos aos estimadores "leafwise" padrão (como CART). A análise demonstra que o termo de erro estocástico para os estimadores UH escala com o número de coeficientes ativos (não nulos), enquanto os estimadores leafwise escalam com o número total de folhas. Isso sugere que os conjuntos UH são particularmente vantajosos para sinais que são esparsos no dicionário de wavelets.

Principais Contribuições

• Generalização para Variedades: O trabalho estende as árvores de wavelet UH de grades 2D/3D para variedades trianguláveis, preservando as propriedades de ortogonalidade e reconstrução exata via triangulações geodésicas e medidas empíricas.
• Adaptabilidade Orientada por Dados: Ao contrário das bases Haar balanceadas em grades fixas, o método proposto permite divisões em localizações arbitrárias ao longo das arestas dos triângulos, adaptando-se às variações locais do sinal e densidades de amostragem.
• Integração de Conjuntos (Ensemble): O artigo introduz a primeira estrutura que combina wavelets ortogonais, partições recursivas conscientes da geometria e técnicas de conjunto (tanto boosting quanto bayesianas) para regressão em variedades.
• Quantificação de Incerteza: Uma variante Bayesiana (RUHWT) é fornecida, oferecendo quantificação de incerteza posterior para estimativas de funções em variedades.

Resultos
Os autores avaliam o método em conjuntos de dados sintéticos e do mundo real:

• Redução de Ruído de Imagem (Grade Euclidiana): Em uma imagem de astronauta ruidosa, os conjuntos UH superam substancialmente os conjuntos de Haar Balanceado (BH). Os resultados indicam que o boosting é ineficaz se os aprendizes fracos forem restritos a dividir nos pontos médios; a capacidade de dividir longe dos pontos médios (desbalanceado) é crucial para ganhos de desempenho.
• Regressão em Esfera Sintética: Em dados simulados em uma esfera unitária, a abordagem de Boosting de Rotação Aleatória usando árvores UH alcança o menor Erro Quadrático Médio (MSE) comparado a Florestas de Fréchet, Florestas Aleatórias de Rotação Aleatória e modelos de Processo Gaussiano profundo de última geração. O método suaviza efetivamente as fronteiras artificiais encontradas em predições não rotacionadas.
• Aplicação no Mundo Real (GISS): Aplicado a dados de anomalia de temperatura da superfície global (GISS), o conjunto UH em uma esfera triangulada supera métodos de árvore concorrentes. As predições mostram melhoria na precisão, particularmente ao capturar variações espaciais complexas, com o menor MSE de teste observado no conjunto de Boosting de Rotação Aleatória.

Significância e Alegações
O artigo afirma apresentar o primeiro método de regressão unificado que integra wavelets ortogonais, partições recursivas conscientes da geometria e técnicas de conjunto modernas para variedades trianguláveis. Os autores enfatizam que sua construção preserva três propriedades fundamentais: (i) ortogonalidade e reconstrução exata, (ii) partições recursivas orientadas por dados adaptadas à geometria da variedade, e (iii) compatibilidade tanto com a construção de conjuntos baseada em otimização quanto com a Bayesiana.

Resultados teóricos sugerem que os conjuntos UH oferecem uma representação adaptável à esparsidade, onde o risco é controlado pelo número de coeficientes significativos em vez do tamanho total da árvore, proporcionando uma vantagem teórica sobre os estimadores leafwise tradicionais. Empiricamente, o método demonstra melhorias substanciais sobre conjuntos de árvores clássicos e wavelets de malha não adaptativas, particularmente em cenários de baixas relações sinal-ruído e geometrias complexas. Os autores posicionam este trabalho como uma ferramenta prática e teoricamente fundamentada para regressão multiescala em domínios complexos, preenchendo a lacuna entre a teoria clássica de wavelets e o aprendizado de máquina baseado em árvores moderno.