Prototype Selection Using Topological Data Analysis

Resumo Técnico: Seleção de Protótipos Usando Análise de Dados Topológicos

Definição do Problema
Pipelines de classificação modernos frequentemente enfrentam gargalos onde o tamanho do conjunto de treinamento, em vez do custo de uma única predição, domina o tempo de inferência. Enquanto modelos paramétricos (ex: SVMs, Random Forests) deslocam o ônus para o tempo de treinamento, eles ainda escalam com o número de instâncias de treinamento. A seleção de protótipos aborda isso comprimindo o conjunto de treinamento em um subconjunto pequeno e representativo. As taxonomias existentes de seleção de protótipos — incluindo as famílias de condensação, edição, híbrida, baseada em competência e baseada em agrupamento — operam sem uma representação explícita da estrutura topológica dos dados. Consequentemente, a geometria das fronteiras de decisão entre classes, que pode exibir estruturas complexas através de múltiplas escalas espaciais, é capturada apenas implicitamente. Este artigo aborda a lacuna no uso da estrutura topológica multiescala dos dados como um critério direto para a seleção de protótipos.

Metodologia
Os autores introduzem duas variantes de um Seletor de Protótipos Topológico (TPS - Topological Prototype Selector) que utilizam homologia persistente, uma ferramenta central da Análise de Dados Topológicos (TDA), para identificar e reter protótipos. Ambos os métodos baseiam-se na filtração de Rips, mas diferem em como codificam a informação de fronteira:

1. Seletor de Protótipos Topológicos Consciente da Fronteira (BoundaryTPS):

   • Mecanismo: Este é um método de estágio único que utiliza uma filtração de Rips com pesos nos vértices. Ele atribui pesos aos pontos da classe-alvo com base em sua proximidade com classes não-alvo (especificamente, a soma das distâncias aos $k$ vizinhos mais próximos não-alvo).
   • Processo: Pontos próximos à fronteira de decisão recebem pesos baixos e entram na filtração precocemente, enquanto pontos do interior recebem pesos altos e são retardados. Isso garante que a topologia da região da fronteira seja resolvida em escalas mais finas.
   • Seleção: Os protótipos são selecionados identificando características de persistência em um quantil específico da distribuição de tempo de vida (lifetime distribution). Um parâmetro de tolerância $\tau$ permite a seleção de uma janela de características ao redor do quantil alvo para melhorar a robustez.

2. Seletor de Protótipos Topológico (TPS):

   • Mecanismo: Este é um método de dois estágios que codifica a informação de fronteira implicitamente através da construção de uma nuvem de pontos mista contendo observações tanto da classe-alvo quanto da não-alvo.
   • Estágio 1 (Vizinhança de Fronteira): Uma filtração de Rips padrão é construída sobre a nuvem mista para capturar a estrutura topológica entre classes. As características são selecionadas com base em um quantil da distribuição de tempo de vida, e os pontos da classe-alvo sobreviventes são retidos.
   • Estágio 2 (Interior): Uma segunda filtração de Rips é construída sobre os sobreviventes do Estágio 1 para capturar a topologia intra-classe. As características são selecionadas com base no tempo de vida médio para reter amostras típicas do interior.
   • Resultado: O conjunto final combina pontos relevantes da fronteira do Estágio 1 com pontos de suporte do interior do Estágio 2.

Principais Contribuições

• Critério Inovador: O artigo introduz a homologia persistente como um critério de seleção de protótipos, uma capacidade não utilizada anteriormente neste domínio.
• Realizações Duplas: Apresenta o TPS e o BoundaryTPS, demonstrando que a codificação da informação de fronteira via filtrações de classes mistas (TPS) versus pesos de vértices (BoundaryTPS) leva a especializações empiricamente diferentes.
• Benchmarking Abrangente: Ambos os métodos são avaliados contra sete baselines clássicos (CNN, CNN+ENN, DROP3, ICF, IB3, KMeans, SPOTGreedy) em quinze conjuntos de dados do mundo real e seis classificadores descendentes sob validação cruzada aninhada.
• Preservação Topológica: O estudo demonstra que os métodos topológicos preservam a estrutura do diagrama de persistência $H_1$ significativamente melhor do que os baselines baseados em densidade ou decisões encadeadas.
• Estabilidade: Ambos os métodos exibem maior estabilidade de seleção (medida pela similaridade de Jaccard entre dobras/folds) do que qualquer seletor de decisão encadeada testado.
• Desbalanceamento de Classes: Os métodos herdam as proporções de classe do conjunto de origem sem exigir mecanismos sensíveis ao rótulo (label-aware).

Resultos

• Fidelidade Topológica: O BoundaryTPS alcança o menor ranking médio de Friedman (2.00) na distância de Wasserstein-1 de $H_1$, superando significativamente cinco dos sete baselines. O TPS ocupa o terceiro lugar (3.60). Ambos os métodos se agrupam no topo do espectro de desempenho para preservação de estruturas de laços ($H_1$), enquanto os métodos clássicos frequentemente "achatam" essas características.
• Estabilidade de Seleção: O TPS alcança a maior similaridade média de Jaccard (0.225) entre as dobras, seguido pelo BoundaryTPS (0.202). Ambos são significativamente mais estáveis do que métodos de decisão encadeada como CNN+ENN (0.057) e DROP3 (0.080).
• Desempenho de Classificação: No agregado da Média Geométrica (G-Mean), os métodos topológicos são competitivos, mas não líderes. O SPOTGreedy e o KMeans alcançam o maior G-Mean agregado (0.84). O TPS e o BoundaryTPS alcançam 0.79 e 0.76, respectivamente. O artigo observa que, embora não dominem a acurácia de classificação bruta, eles oferecem um ponto de operação distinto no espaço de design, particularmente no que diz respeito à preservação estrutural e estabilidade.
• Escalabilidade: Empiricamente, ambos os métodos escalam de forma sub-quadrática em relação ao tamanho da amostra.

Significância e Alegações
O artigo alega que a principal significância deste trabalho reside na mudança do paradigma da seleção de protótipos de heurísticas puramente geométricas ou estatísticas para um framework fundamentado em invariantes topológicos multiescala. Os autores argumentam que, embora os métodos existentes assumam implicitamente um princípio de proximidade de fronteira, eles falham em resolver a estrutura complexa e multiescala das fronteiras de decisão. Ao utilizar explicitamente a homologia persistente, os métodos propostos oferecem uma maneira fundamentada de reter pontos que definem a "forma" topológica dos dados, particularmente os laços e fronteiras que costumam ser perdidos na redução baseada em densidade.

Os autores caracterizam modestamente os resultados: os métodos topológicos não superam universalmente os baselines existentes em acurácia de classificação descendente (G-Mean), mas ocupam uma região única e valiosa do espaço de design ao oferecer superior preservação topológica e estabilidade de seleção. O trabalho sugere que, para aplicações onde a integridade estrutural da fronteira de decisão ou a reprodutibilidade do processo de seleção são primordiais, os critérios topológicos fornecem uma alternativa distinta e eficaz às abordagens clássicas.