Resumo Técnico: Diagramas de Persistência Não Reduzidos para Aprendizado de Máquina Topológico

Declaração do Problema

A Análise de Dados Topológicos (TDA) combinada com aprendizado de máquina (ML) supervisionado tornou-se uma abordagem padrão para analisar dados complexos em diversos domínios, incluindo biologia, neurociência e ciência dos materiais. O pipeline padrão envolve o cálculo da Homologia Persistente (PH) para gerar Diagramas de Persistência (PDs), vetorizar esses diagramas e treinar modelos de ML.

No entanto, duas ineficiências críticas foram observadas neste pipeline:

1. Redundância de Informação: Evidências empíricas sugerem que modelos de ML frequentemente ignoram porções significativas da informação contida nos PDs vetorizados. Por exemplo, tarefas de regressão mostraram desempenho "próximo ao ideal" usando apenas a persistência do 28º ponto mais persistente, e benchmarks indicam que vetorizações estatísticas ingênuas frequentemente performam tão bem quanto as complexas.
2. Custo Computacional: Calcular PDs totalmente reduzidos é frequentemente a etapa computacionalmente mais exigente do pipeline, exigindo memória e tempo substanciais, particularmente para grandes conjuntos de dados.

A hipótese central deste trabalho é que, se os modelos de ML podem performar bem com vetorizações que descartam informação, então o cálculo completo da PH (especificamente a redução das matrizes de fronteira) pode ser um gasto computacional desnecessário. Os autores propõem evitar a redução da matriz de fronteira inteiramente, utilizando diagramas de persistência não reduzidos derivados diretamente de matrizes de fronteira não reduzidas.

Metodologia

Estrutura Teórica

Os autores definem vários tipos de diagramas de persistência (PDs) não reduzidos construídos a partir de uma matriz de fronteira $M$ sem realizar o algoritmo padrão de redução por colunas. Eles são definidos com base nas propriedades das colunas da matriz:

• Par Aparente (AP) PD: Pares $(low(M_j), j)$ onde a entrada não nula mais baixa na coluna $j$ é a única entrada não nula naquela linha à esquerda (um padrão específico que indica um par de persistência sem redução).
• Par Quasi-Aparente Inferior (qAP↓) PD: Pares $(low(M_j), j)$ onde $\beta(M_j) \neq -1$.
• Par Quasi-Aparente Superior (qAP↑) PD: Pares $(\beta(M_j), j)$ onde $\beta(M_j) \neq -1$. Aqui, $\beta(M_j)$ é o índice de linha mais alto de um 1 na coluna $j$ que não pode ser eliminado pela redução.
• Low-Ones (L1) PD: O multiconjunto de pares $(low(M_j), j)$ para todas as colunas onde $low(M_j) \neq -1$.

As construções L1 e qAP↑ são particularmente enfatizadas para complexos de Vietoris-Rips (VR), pois outros tipos não reduzidos podem resultar apenas em pares efêmeros (persistência zero) em dimensões de homologia superior para essas filtrações.

Análise de Estabilidade

O artigo investiga a estabilidade de Lipschitz das transformações em relação à distância de bottleneck ($d_B$).

• Resultados Teóricos: A transformação de PD totalmente reduzido (FR) é globalmente estável com uma constante de Lipschitz $C=1$. Em contraste, os PDs não reduzidos (AP, qAP) são geralmente não globalmente estáveis. Pequenas perturbações na função de filtração podem reordenar as colunas da matriz de fronteira, causando o aparecimento ou desaparecimento de pares aparentes, levando a uma instabilidade combinatória.
• Estabilidade Local: Os autores provam que os PDs não reduzidos são localmente estáveis de Lipschitz. Se a perturbação na função de filtração for pequena o suficiente para preservar a ordenação dos símplices (especificamente, menor que a metade do intervalo mínimo entre valores de filtração adjacentes), as transformações permanecem estáveis.
• Estabilidade Experimental: Experimentos computacionais em nuvens de pontos perturbadas mostram que, embora ocorram picos de instabilidade de grande escala (onde o número de pontos no diagrama muda), eles são raros. A maioria das perturbações resulta em razões de estabilidade comparáveis ou melhores que o caso totalmente reduzido.

Implementação Computacional

Para comparar as vantagens computacionais, os autores implementaram uma versão modificada do algoritmo Ripser para calcular diagramas qAP↑ para complexos VR.

• Paralelização: Diferente do algoritmo de redução padrão, que processa colunas serialmente (da esquerda para a direita), o cálculo de diagramas qAP↑ pode ser paralelizado. O algoritmo busca através das colunas da matriz de cobordaça da filtração de forma independente.
• Eficiência de Memória: A implementação evita armazenar a matriz de fronteira completa e as fronteiras de trabalho necessárias para a redução. Utiliza um mapa de hash para armazenar pares e ignora "pares zero aparentes" (pares efêmeros) precocemente no processo.

Principais Resultados

Desempenho Computacional

O benchmarking em um sistema AMD Ryzen Threadripper PRO de 32 núcleos contra o Ripser padrão revelou ganhos significativos:

• Tempo de Execução (Wall Time): O cálculo paralelizado de qAP↑ alcançou um aumento médio de 20x na velocidade de wall time em comparação com o cálculo de persistência total.
• Memória: A abordagem não reduzida exigiu aproximadamente 1/13 da memória do Ripser para exemplos não limiares e 1/1.86 para exemplos limiares.
• Escalabilidade: Os autores calcularam com sucesso diagramas não reduzidos para o conjunto de dados torus4 (50.000 pontos), uma tarefa onde o Ripser falhou devido a restrições de memória (exigindo >300GB de RAM). Para o conjunto de dados cyclo-octane, o cálculo qAP↑ utilizou 454 vezes menos memória e 59,5 vezes menos tempo de execução que o Ripser.

Desempenho de Aprendizado de Máquina

Os autores avaliaram o desempenho de classificadores e regressores Random Forest treinados em vetorizações de PDs não reduzidos (L1, qAP, AP) versus PDs totalmente reduzidos (FR) através de três tarefas:

1. Classificação de Formas Sintéticas: Classificar nuvens de pontos (círculo, esfera, toro, etc.) com níveis variados de ruído.
2. Classificação Fashion-MNIST: Classificar imagens de roupas usando complexos cubicais.
3. Regressão de Árvore de Artéria Cerebral: Prever a idade do sujeito a partir de dados de varredura cerebral 3D.

Descobertas:

• Paridade e Melhoria: Em todos os experimentos, pelo menos um tipo de PD não reduzido performou tão bem quanto ou melhor que o PD totalmente reduzido.
• Superioridade do L1: Os diagramas L1 consistentemente performaram em par com ou superaram os diagramas FR. Na tarefa Fashion-MNIST, os diagramas L1 superaram os diagramas FR em pelo menos 10 pontos percentuais em precisão média.
• Robustez: Estes resultados foram robustos através de diferentes tipos de filtração (Alpha, Rips), métodos de vetorização (Imagens de Persistência, coordenadas de Adcock-Carlsson) e níveis de ruído.
• Importância das Características: A análise da tarefa Fashion-MNIST revelou que os modelos L1 e FR dependem de regiões distintas do espaço da imagem de persistência. As características mais importantes para os modelos L1 estavam concentradas em $H_0$ (componentes conectadas), enquanto os modelos FR utilizaram características tanto de $H_0$ quanto de $H_1$ de forma mais equilibrada. Isso sugere que os diagramas não reduzidos codificam informações diferentes, potencialmente úteis, que são descartadas durante a redução total.

Significância e Alegações

O artigo conclui que diagramas de persistência não reduzidos são substitutos eficazes para diagramas totalmente reduzidos em pipelines de aprendizado de máquina topológico.

• Eficiência Computacional: Ao evitar a etapa de redução dispendiosa, praticantes podem alcançar reduções significativas no uso de memória e tempo de computação, permitindo a análise de conjuntos de dados que são atualmente intratáveis para os métodos padrão de PH.
• Desempenho: Contrariando a suposição de que a redução é necessária para a qualidade, os autores demonstram que a informação descartada pela redução muitas vezes não é crítica para o desempenho do ML a jusante e que os diagramas não reduzidos podem até capturar características distintas e benéficas.
• Direções Futuras: Os autores observam que, embora os diagramas não reduzidos economizem computação, vetorizá-los pode ser mais lento devido ao maior número de pontos. Eles sugerem que trabalhos futuros devem focar no design de algoritmos que computem vetorizações diretamente de matrizes não reduzidas sem armazenar explicitamente todos os pares, otimizando ainda mais o pipeline.

O estudo alega modestamente que estes resultados sugerem uma mudança na forma como os pipelines de PH-ML são construídos, potencialmente priorizando a eficiência computacional e a retenção de características topológicas "puras" sobre a completude matemática estrita dos diagramas totalmente reduzidos.