Resumo Técnico: Histogramas de Voronoi para Vetorização Adaptativa de Diagramas de Persistência Esperada

1. Definição do Problema

A Análise de Dados Topológicos (TDA) utiliza a Homologia Persistente (PH) para capturar características topológicas de nuvens de pontos, codificadas como Diagramas de Persistência (PDs). Um PD representa características topológicas (ciclos) como pontos $(b, d)$ em um semiplano aberto $\Omega$, onde $b$ e $d$ denotam os tempos de nascimento (birth) e morte (death). No entanto, os PDs não podem ser usados diretamente como entradas para algoritmos padrão de aprendizado de máquina, necessitando de vetorização.

Um gargalo significativo no uso de PDs é sua alta complexidade computacional; obter um PD pode atingir $O(m^3)$ ou até $O(|X|^9)$ para características unidimensionais. Para mitigar isso, o Diagrama de Persistência Esperada (EPD) foi desenvolvido. Um EPD é uma distribuição de características topológicas derivada pela média dos PDs de múltiplos subconjuntos amostrados de uma nuvem de pontos. Embora os EPDs reduzam os custos de tempo, os métodos de vetorização existentes para EPDs (como Imagens de Persistência, Silhuetas de Persistência e Paisagens de Persistência) dependem de funções de transformação de pontos contínuas predefinidas (ex: núcleos gaussianos ou funções de paisagem) e grades de discretização fixas. Esses métodos introduzem escolhas de design relativas a suavidade, largura de banda (bandwidth) e resolução de grade, o que pode borrar diferenças de massa local ou enfatizar regiões não otimizadas no plano $(nascimento, morte)$.

O artigo aborda a necessidade de um método de vetorização alternativo que evite modelos explícitos de transformação de pontos suaves e, em vez disso, utilize uma partição adaptativa e dependente dos dados para representar a distribuição do EPD.

2. Metodologia: Representação Baseada em Voronoi (Vrep)

Os autores propõem o Vrep, um método de vetorização que trata o EPD empírico como uma distribuição de características topológicas e o representa utilizando histogramas baseados em Diagramas de Voronoi.

Mecanismo Central

1. Amostragem de Codebook: Em vez de uma grade fixa, o Vrep constrói um conjunto de codebooks aleatórios $S$. Cada codebook $C = \{c_1, ..., c_k\}$ consiste em pontos amostrados do suporte do EPD (o conjunto de características topológicas).
2. Particionamento de Voronoi: Para um determinado codebook $C$, o semiplano aberto $\Omega$ é particionado em células de Voronoi $V(c_i)$, onde cada célula contém pontos mais próximos de $c_i$ do que de qualquer outro $c_j$.
3. Construção do Histograma: A representação $\Phi(\bar{\mu}, C)$ é definida como o vetor de massas normalizadas do EPD $\bar{\mu}$ que caem em cada célula de Voronoi:
   $$\Phi(\bar{\mu}, C) = [\bar{\mu}(V(c_1)), \bar{\mu}(V(c_2)), ..., \bar{\mu}(V(c_k))]$$
4. Agregação: Para formar a representação final $\hat{\Phi}(\bar{\mu})$, o método concatena histogramas gerados a partir de múltiplos codebooks amostrados do conjunto de dados.
5. Variante com Consciência da Diagonal (Vrepd): Uma variante específica, o Vrepd, inclui uma célula de Voronia centrada na diagonal $\partial\Omega$ (onde $b=d$). Isso é crucial para separar o ruído (características próximas à diagonal) de características topológicas significativas.

Estratégias de Amostragem de Codebook

O artigo avalia três estratégias para amostragem dos pontos dentro de um codebook:

• Default (Padrão): Amostragem uniforme do suporte do EPD.
• Persistence-Weighted (Pesada pela Persistência): Amostragem ponderada pela persistência ($d-b$), priorizando características significativas.
• Uniform (Uniforme): Amostragem de um retângulo fixo acima da diagonal (irrelevante para o EPD).

Normalização

O método normaliza o EPD para uma norma $l_1$ unitária ($\bar{\mu} \leftarrow \bar{\mu}/\bar{\mu}(\Omega)$). Isso trata o EPD como uma distribuição de probabilidade, garantindo que todos os EPDs tenham a mesma massa, o que permite o uso direto da distância de Wasserstein para análise de estabilidade e medição de dissimilaridade, evitando a necessidade de métricas de Transporte Parcial Ótimo.

3. Contribuições Teóricas

O artigo estabelece garantias teóricas relativas à estabilidade e capacidade representacional do Vrep sob condições específicas:

• Limites de Estabilidade: Os autores provam que o Vrep é estável sob perturbações do EPD. Especificamente, se o EPD sofre uma perturbação $\Delta$ (pequeno movimento de massas de Dirac), a mudança na representação Vrep é Lipschitz contínua em relação a $\Delta$. O limite de erro depende do tamanho do codebook $k$ e das propriedades do conjunto de dados.
• Limites Relacionados a Wasserstein: O artigo fornece um limite inferior condicional relacionando a distância $l_1$ entre dois vetores Vrep à distância de Wasserstein ($W_1$) entre os EPDs subjacentes.
  $$\|\Phi(\bar{\mu}, C) - \Phi(\bar{\nu}, C)\|_1 \geq \frac{W_1(\bar{\mu}, \bar{\nu}) - \text{erros de aproximação}}{d_{max}(C)}$$
  Este resultado esclarece que o Vrep preserva efetivamente as variações de escala de Wasserstein quando o codebook está "bem resolvido" (ou seja, o erro de aproximação é pequeno em relação à separação das distribuições). Não é uma garantia de preservação monótona geral, mas uma afirmação de consistência condicional.

4. Resultados Experimentais

Os autores avaliaram o Vrep e o Vrepd em tarefas de classificação de nuvens de pontos supervisionadas e redução de dimensionalidade não supervisionada, comparando-os com métodos padrão: Imagem de Persistência (PI), Silhuetas de Persistência (PS), Paisagem de Persistência (PL) e a rede end-to-end PointNet.

Desempenho de Classificação

• Datasets: Os experimentos foram conduzidos em diversos conjuntos de dados, incluindo estruturas de Proteínas, componentes mecânicos de CAD e dados de séries temporais (transformados em nuvens de pontos via incorporação de atraso temporal).
• Resultados: O Vrep e o Vrepd alcançaram consistentemente uma precisão de classificação maior ou comparável (usando um classificador Random Forest) ao PI, PS e PL na maioria dos conjuntos de dados sensíveis à topologia.
  • No dataset de Proteína, o Vrep alcançou 98,5% de precisão (contra 95,5% do PI).
  • Nos datasets de CAD, o Vrep e o Vrepd superaram outros métodos não supervisionados, embora o PI tenha mostrado resultados competitivos em certos cenários de ruído.
• Sensibilidade do Codebook: A estratégia de amostragem de codebook persistence-weighted frequentemente apresentou os melhores resultados, particularmente em ambientes ruidosos, pois foca a representação nas características topológicas significativas.

Estabilidade e Escalabilidade

• Estabilidade de Perturbação: Experimentos em um dataset de sistema dinâmico 3D mostraram que o Vrep é estável sob perturbações de ruído Gaussiano. Curiosamente, o Vrepd (com a célula da diagonal) demonstrou uma estabilidade ligeiramente superior ao Vrep, provavelmente devido à melhor separação do ruído próximo à diagonal.
• Complexidade de Tempo:
  • O Vrep possui uma complexidade de tempo de $O(m^2tk)$ para um dataset de tamanho $m$, onde $t$ é o número de codebooks e $k$ é o tamanho do codebook. É quadrática em relação ao tamanho do dataset.
  • No entanto, o Vrep é mais rápido que PL e PS em tempo de execução real e escala melhor com o número de PDs amostrados ($n$), pois subsampleia o suporte do EPD para um tamanho fixo, enquanto PI/PS/PL devem processar cada PD amostrado individualmente.
  • Embora o PointNet (supervisionado) tenha alcançado alta precisão, o Vrep oferece uma alternativa competitiva para tarefas não supervisionadas (como redução de dimensionalidade) onde o PointNet não pode ser aplicado.

Redução de Dimensionalidade Não Supervisionada

Em uma tarefa de visualização t-SNE em um dataset de sistema dinâmico, o Vrep produziu clusters com índices Calinski-Harabasz (CH) mais altos (1751) comparado ao PI (569) e PL (1655), indicando uma separação de clusters superior.

5. Significância e Alegações

O artigo posiciona o Vrep como uma representação complementar, em vez de um substituto universal para os métodos existentes.

• Adaptativo vs. Suave: A principal contribuição é a mudança de aproximações funcionais suaves baseadas em núcleos para uma contagem adaptativa e dependente dos dados. O Vrep agrega massa sobre células definidas pelos próprios dados, tornando-o potencialmente mais fiel à alocação de massa empírica do EPD.
• Trade-off (Compromisso): Os autores reconhecem explicitamente o compromete: o Vrep resume eficientemente a alocação de massa grosseira, mas é inerentemente perdedor (lossy) em relação à geometria de grão fino dentro de uma célula de Voronoi. Consequentmente, métodos suaves (como PI ou métodos de núcleo) podem superar o Vrep quando a variação topológica relevante envolve deslocamentos locais finos ou mudanças de forma dentro de uma célula.
• Utilidade Não Supervisionada: Uma significância chave é a aplicabilidade do método ao aprendizado não supervisionado. Ao contrário de abordhas de aprendizado profundo supervisionadas (ex: PointNet, PersLay), o Vrep não requer rótulos para extração de características, tornando-o adequado para tarefas de redução de dimensionalidade e agrupamento (clustering).
• Alegações Modestas: Os autores não afirmam que o Vrep domina todas as vetorizações. Eles observam que métodos de núcleo (PWGK, SWK) podem superar o Vrep em datasets específicos (ex: CAD), mas a um custo computacional significativamente maior. O artigo conclui que o Vrep é uma alternativa adaptativa competitiva que oferece escalabilidade favorável com o número de PDs amostrados e fornece um viés de aproximação distinto, adequado para classificação sensível à topologia.