Manifold Dimension Estimation via Local Graph Structure

Resumo Técnico: Estimação da Dimensão de Variedade via Estrutura Gráfica Local

Declaração do Problema
Estimar a dimensão intrínseca $d$ de uma variedade embutida em um espaço ambiente de alta dimensão $\mathbb{R}^p$ é um desafio fundamental na redução de dimensionalidade não linear. Embora muitos estimadores existentes (por exemplo, PCA Local, DanCo, TwoNN) dependam da "hipótese de planicidade" — aproximando vizinhanças locais como subespaços lineares $d$-dimensionais —, essa abordagem enfrenta dificuldades quando as variedades exibem curvatura significativa ou são embutidas de forma não linear. Métodos recentes, como PCA Ajustada por Curvatura (CA-PCA), tentam abordar isso corrigindo explicitamente as estruturas de autovalores para a curvatura, mas frequentemente sofrem de superestimação em espaços ambientes de alta dimensão ou instabilidade computacional. Os autores identificam uma lacuna em métodos capazes de modelar robustamente a curvatura local sem depender de estimativa direta instável de curvatura ou detecção de lacuna de autovalores.

Metodologia
Os autores propõem um novo quadro que reformula a estimação da dimensão da variedade como um problema de regressão sobre coordenadas de PCA local. Em vez de assumir planicidade local ou estimar explicitamente tensores de curvatura, o método modela a vizinhança local de um ponto $x_k$ como o gráfico de uma função suave $g: \mathbb{R}^d \to \mathbb{R}^{p-d}$.

1. Representação Gráfica Local: Para um ponto $x_k$ e seus $K$ vizinhos mais próximos, os autores realizam PCA para estabelecer um sistema de coordenadas local alinhado com o espaço tangente estimado. As primeiras $d$ coordenadas representam o espaço tangente, enquanto as coordenadas restantes $p-d$ representam o espaço normal.
2. Formulação de Regressão: O quadro postula que as coordenadas normais podem ser expressas como uma função das coordenadas tangentes. Como a expansão de Taylor de primeira ordem dessa função é zero (por definição do espaço tangente), os autores utilizam termos de segunda ordem (quadráticos) para capturar a curvatura local.
3. Sondagem de Dimensões Candidatas: O algoritmo itera através de dimensões candidatas $j$ (de 1 a $p-1$). Para cada $j$, trata as primeiras $j$ coordenadas de PCA como entradas e a $(j+1)$-ésima coordenada como saída, ajustando um modelo de regressão quadrática.
4. Dois Estimadores:
   • Embutimento Quadrático (QE): Utiliza Mínimos Quadrados Ordinários (OLS) para ajustar o modelo quadrático. Avalia a qualidade do ajuste usando a estatística $F$ e o $R^2$ ajustado. A dimensão estimada é a menor $j$ onde o ajuste do modelo se torna estatisticamente significativo (valor-p < 1%) e permanece significativo para todas as dimensões superiores.
   • Mínimos Quadrados Totais (TLS): Utiliza Mínimos Quadrados Totais para contabilizar erros tanto nas variáveis de entrada quanto nas de saída. Em vez de estatísticas $F$, avalia a queda relativa no erro total TLS ($\eta_j$) entre dimensões consecutivas. A dimensão estimada corresponde ao pico da queda relativa.

Principais Contribuições

• Quadro Baseado em Regressão: O artigo introduz uma perspectiva nova que lança a estimação de dimensão como um problema de regressão recursiva. Isso substitui a estimativa geométrica local instável (como cálculo direto de curvatura) por um procedimento de ajuste estatisticamente agregado, oferecendo maior robustez à esparsidade de amostragem e ruído.
• Modelagem Consciente de Curvatura: Ao empregar modelos quadráticos, o método captura explicitamente a curvatura da variedade sem exigir estimativa explícita de curvatura ou correção de autovalores, mitigando assim os problemas de superestimação comuns em métodos baseados em PCA.
• Robustez a Ruído e Não Linearidade: O quadro acomoda naturalmente o ruído e é projetado para performar bem em variedades com embutimentos complexos e não lineares onde as hipóteses de planicidade falham.
• Implementação Prática: Os autores fornecem dois estimadores concretos (QE e TLS) com algoritmos detalhados, incluindo heurísticas para limitar o espaço de busca ($p_{max}$) com base no tamanho da vizinhança para garantir a viabilidade computacional.

Resultados Experimentais
Os autores avaliaram QE e TLS em 18 variedades sintéticas (incluindo esferas, esferas deformadas e superfícies gaussianas) e 6 conjuntos de dados do mundo real (ISOMAP, MNIST, ISOLET, Fashion MNIST, Frey Face, Gas Sensor Array Drift).

• Dados Sintéticos: QE e TLS demonstraram desempenho competitivo ou superior em comparação com métodos do estado da arte (PCA Local, CA-PCA, DanCo, TwoNN, MADA, etc.), particularmente em regimes de pequena amostra e em variedades embutidas não linearmente (por exemplo, esferas deformadas). Eles mitigaram efetivamente a superestimação observada em CA-PCA e PCA Local quando a dimensão ambiente $p$ excede significativamente a dimensão intrínseca $d$.
• Robustez a Ruído: Na presença de ruído gaussiano, uniforme e de Laplace, os métodos propostos mantiveram desempenho robusto, superando muitos estimadores baseados em planicidade cuja precisão degradou-se significativamente.
• Dados do Mundo Real: Em conjuntos de dados do mundo real, os estimadores produziram resultados consistentes com faixas de consenso (por exemplo, estimando ISOMAP $\approx 3$, MNIST $\approx 8-11$). Notavelmente, evitaram a superestimação severa vista em PCA Local e CA-PCA em conjuntos de dados com altas dimensões ambientes.
• Limitações Observadas: Os métodos mostraram desempenho reduzido em variedades "triviais" com curvatura zero (por exemplo, hipersferas), onde o modelo quadrático é uma especificação incorreta. Além disso, o TLS é limitado inferiormente por 2 devido à sua dependência de quedas de erro relativo entre dimensões.

Significado e Alegações
O artigo alega que, ao mudar o paradigma da aproximação geométrica para a regressão estatística, o quadro proposto alcança robustez e precisão aprimoradas, particularmente em regimes desafiadores envolvendo tamanhos de amostra pequenos e curvatura complexa. Os autores afirmam que seus métodos oferecem uma alternativa convincente aos estimadores existentes de melhor desempenho, abordando efetivamente as limitações tanto das abordagens baseadas em planicidade quanto das correções de curvatura baseadas em autovalores. Eles concluem que, embora a formulação quadrática atual seja eficaz, trabalhos futuros poderiam explorar modelos mais expressivos se ferramentas de diagnóstico confiáveis para estatísticas de amostra forem desenvolvidas. O trabalho é apresentado como um passo significativo rumo à resolução dos desafios persistentes na estimação da dimensão de variedades, embora os autores permaneçam modestos quanto à necessidade de refinamento adicional nos critérios de avaliação (especificamente para TLS) e no tratamento do ruído na estimação do espaço tangente.