Resumo Técnico: Regressão de Esqueleto (Skeleton Regression)

1. Problema e Motivação

O artigo aborda o desafio de realizar regressão não paramétrica em dados de alta dimensão onde as covariadas residem em torno de uma estrutura de variedade de baixa dimensão (manifold).

• O Dilema da Dimensionalidade: Métodos tradicionais sofrem com a "maldição da dimensionalidade" quando a dimensão do espaço ambiente ($d$) é grande, mesmo que a dimensão intrínseca dos dados seja pequena.
• Limitações das Abordagens Atuais:
  • Métodos baseados em projeção (como PCR ou PLS) ou estimadores locais em planos tangentes (como MALLER) muitas vezes não são robustos a perturbações que afastam as covariadas da verdadeira estrutura da variedade.
  • Métodos de aprendizado de variedade existentes (como regularização de variedade ou séries espectrais) podem falhar quando os dados consistem na união de múltiplas variedades desconectadas ou na presença de ruído aditivo significativo.
• Objetivo: Desenvolver um framework que utilize a estrutura geomética subjacente para estimar funções de regressão, sendo robusto a ruídos e capaz de lidar com componentes desconectados, sem depender da dimensão ambiente.

2. Metodologia Proposta: Regressão de Esqueleto

A proposta central é um framework de duas etapas que combina a construção de um grafo representativo (o "esqueleto") com técnicas de regressão não paramétrica.

Etapa 1: Construção do Esqueleto (Skeleton Construction)

O espaço de covariadas é representado por um grafo denso, chamado de esqueleto, que captura a geometria subjacente.

• Nós (Knots): Pontos representativos do espaço de covariadas, construídos via algoritmo de k-means com um número elevado de centros (tipicamente da ordem de $\sqrt{n}$).
• Arestas (Edges): Conectam os nós baseando-se na região de vizinhança de 2-vizinhos (2-NN) dos dados. Se a região entre dois nós contém pontos de dados, uma aresta é formada.
• Densidade de Voronoi: Utilizada para pesar as arestas e segmentar o grafo em componentes desconectados se necessário, ajudando a lidar com variedades múltiplas e desconectadas.
• Diferencial: Diferente de grafos comuns onde cada amostra é um nó, o esqueleto tem $k \ll n$ nós, tornando-o computacionalmente eficiente e uma representação sumarizada da densidade.

Etapa 2: Projeção de Dados

As covariadas originais ($\mathbf{x}_i$) são projetadas no esqueleto ($\mathbf{s}_i \in \mathcal{S}$).

• Se os dois nós mais próximos de $\mathbf{x}_i$ estiverem conectados, a projeção ocorre na aresta que os une (projeção ortogonal).
• Caso contrário, o ponto é projetado no nó mais próximo.
• Isso mapeia o espaço de alta dimensão para um espaço métrico unidimensional (ou de dimensão baixa) definido pelo grafo.

Etapa 3: Regressão no Esqueleto

Uma vez projetados, os dados são tratados como pontos em um espaço métrico definido pelas distâncias no grafo. O artigo propõe três métodos principais:

1. Kernel Regression no Esqueleto (S-Kernel):

   • Estima a função de regressão usando uma média ponderada local baseada na distância no grafo ($d_S$).
   • A distância é definida como o comprimento do caminho mais curto no grafo (geodésica no grafo), não a distância euclidiana no espaço ambiente.
   • Vantagem: A taxa de convergência depende da dimensão intrínseca (1D nas arestas), ignorando a dimensão ambiente.

2. k-NN no Esqueleto (S-kNN):

   • Seleciona os $k$ vizinhos mais próximos usando a distância no grafo, em vez da distância euclidiana.
   • Robusto a ruídos e alta dimensionalidade.

3. Spline Linear no Esqueleto (S-Lspline):

   • Modela a função de regressão como linear em cada aresta e contínua nos nós.
   • Teorema do Representante: A função é unicamente determinada pelos valores nos nós.
   • Pode ser formulada como um modelo de regressão linear com covariadas transformadas (interpolando linearmente entre os valores dos nós), permitindo solução analítica via mínimos quadrados.

Desafios de Outros Métodos

O artigo discute por que métodos clássicos falham neste contexto:

• Regressão Polinomial Local: Requer orientação e derivadas bem definidas, o que é problemático em nós (vértices) onde múltiplas arestas se encontram.
• Splines de Ordem Superior: A definição de derivadas de ordem superior é ambígua em nós sem orientação fixa.
• Bases Ortogonais e Árvores: A construção de bases ou partições ótimas em grafos complexos é não trivial e arbitrária.

3. Contribuições Principais

1. Novo Framework de Regressão: Introdução da "Regressão de Esqueleto", que desacopla a estimação da função de regressão da dimensão ambiente, focando na estrutura geométrica do grafo.
2. Definição de Métrica e Projeção: Estabelecimento rigoroso de uma distância baseada no grafo e um algoritmo de projeção que mapeia dados de alta dimensão para o esqueleto.
3. Garantias Teóricas:
   • Prova de consistência e taxas de convergência para o estimador de Kernel no esqueleto.
   • Demonstração de que, em arestas, a taxa de convergência é $O(h) + O_p(1/\sqrt{nh})$ (similar à regressão unidimensional).
   • Análise de nós com massa de probabilidade zero e não zero, mostrando que o estimador converge para a média ponderada dos limites das arestas adjacentes.
4. Robustez a Cenários Complexos: O método lida naturalmente com:
   • Uniões de múltiplas variedades desconectadas.
   • Observações ruidosas (ruído aditivo).
   • Dados de alta dimensão (até 1000 dimensões nos experimentos).

4. Resultados Experimentais

Os autores avaliaram o método em dados simulados e reais, comparando com kNN clássico, Ridge, Lasso, Séries Espectrais, Kernel Ridge (Fast-KRR) e Autoencoders (MLP).

• Dados Simulados (Yinyang, Yinyang Ruidoso, SwissRoll):

  • Em dados com múltiplos componentes desconectados (Yinyang), os métodos baseados em esqueleto (S-Kernel, S-kNN, S-Lspline) superaram significativamente o kNN clássico e métodos de aprendizado de variedade (como Séries Espectrais), que falharam em capturar a desconexão.
  • Em dados ruidosos, o S-Kernel demonstrou excelente robustez.
  • No caso do "Swiss Roll" (variedade conectada 2D), os métodos baseados em distância do grafo (S-Kernel, S-kNN) superaram o S-Lspline e outros métodos, indicando que a métrica do grafo aproxima bem a distância geodésica da variedade.
  • Em todas as simulações de alta dimensão ($d=1000$), os métodos baseados em esqueleto mantiveram desempenho superior, enquanto métodos lineares (Ridge/Lasso) e redes neurais simples tiveram desempenho inferior.

• Dados Reais:

  • Imagens de Copas (COIL-20): Previsão do ângulo de rotação. O S-Lspline obteve o melhor desempenho (SSE mais baixo), superando o kNN. Isso sugere que, para estruturas suaves e conectadas, a modelagem linear por partes no esqueleto é muito eficiente.
  • Dados SDSS (Astronomia): Previsão de redshift espectral a partir de magnitudes fotométricas. O kNN e Séries Espectrais tiveram o melhor desempenho de precisão, mas o esqueleto construído revelou claramente a estrutura unidimensional e a tendência monotônica dos dados, demonstrando valor exploratório.

5. Significado e Conclusão

A Regressão de Esqueleto oferece uma alternativa poderosa e computacionalmente eficiente para análise de dados geométricos.

• Independência de Dimensão: Ao projetar dados em um grafo 1D (arestas) e usar métricas de caminho, o método evita a maldição da dimensionalidade.
• Interpretabilidade: O esqueleto gerado não é apenas uma ferramenta de previsão, mas uma visualização da estrutura subjacente dos dados (topologia e densidade).
• Flexibilidade: O framework é compatível com diversas técnicas de regressão não paramétrica (Kernel, kNN, Splines) e adapta-se a dados com ruído e estruturas desconectadas.

O trabalho sugere direções futuras para generalizar o esqueleto para complexos simpliciais (dimensões > 1) e para o desenvolvimento de métodos de atualização online para dados em fluxo.