When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

Resumo Técnico: Abordagem de Instâncias Ambíguas em Redução de Dimensionalidade por Divisão

Definição do Problema
A Redução de Dimensionalidade (RD) é uma ferramenta fundamental para a visualização de dados de alta dimensão, contudo é inerentemente um processo com perdas. Embora a literatura existente tenha catalogado várias distorções, como o rasgamento de variedades, este artigo identifica uma fonte previamente negligenciada de artefatos visuais: instâncias ambíguas. Estas são pontos de dados que são altamente semelhantes a múltiplos vizinhanças mutuamente dissimilares no espaço de alta dimensão.

Os métodos padrão de RD mapeiam cada instância de dados para um único ponto no espaço visual. Consequentemente, uma instância ambígua não pode representar fielmente sua pertença a múltiplas vizinhanças distintas simultaneamente. Ela é forçada a uma única localização, resultando em incorporação parcial de vizinhança. Neste estado, a instância parece pertencer a apenas uma vizinhança (ou nenhuma), obscurecendo sua verdadeira relação com outros grupos dissimilares. Este artefato é particularmente problemático para análises ao nível de instância, como Inteligibilidade Artificial Explicável (XAI) ou biologia de célula única, onde a compreensão da estrutura precisa da vizinhança é crítica. Métricas existentes, como confiabilidade e continuidade, falham em distinguir a incorporação parcial de vizinhança de outras distorções porque operam sobre a incorporação final sem acesso à ambiguidade subjacente dos dados.

Metodologia
Os autores propõem uma abordagem baseada em grafos para identificar e resolver essas ambiguidades "dividindo" instâncias ambíguas em múltiplos pontos, cada um posicionado dentro de sua respectiva vizinhança. A metodologia segue o framework de RD em duas fases (relação e mapeamento) introduzido por Paulovich et al.:

1. Construção e Esparsificação do Grafo:

   • As relações de alta dimensão são modeladas como um grafo ponderado não direcionado $G$.
   • Para expor estruturas de vizinhança significativas e remover arestas redundantes causadas por proximidade incidental, os autores aplicam esparsificação espectral utilizando o algoritmo de Spielman-Srivastava. Isso produz um grafo reduzido $\bar{G}$ que preserva as propriedades estruturais e algébricas do original, removendo conexões fracas.

2. Identificação de Instâncias Ambíguas:

   • A ambiguidade é definida topologicamente. Os autores adaptam o conceito de Pontos de Articulação Locais (PALs). Um vértice é considerado um PAL se sua remoção aumentar o número de componentes conectados dentro de uma vizinhança induzida local de $r$ passos.
   • Uma instância é considerada ambígua se for um PAL no grafo esparsificado $\bar{G}$. Isso indica que a instância conecta vizinhanças disjuntas que, de outra forma, estariam separadas.
   • O Lema 3.1 é utilizado para otimizar o cálculo: se um vértice não é um PAL em um determinado raio $r$, ele não pode ser um PAL em qualquer raio maior $r' > r$.

3. Divisão de Vértices e Regras de Decisão:

   • Uma vez identificado um vértice ambíguo $v_i$, ele é dividido em $K$ cópias, onde $K$ corresponde ao número de componentes conectados restantes após a remoção de $v_i$ de sua vizinhança local.
   • Regras de Decisão: Nem todas as divisões potenciais são executadas. A abordagem filtra:
     • Conexões PAL-PAL: Se uma aresta conecta duas vizinhanças e ambas as extremidades são PALs, a divisão é suprimida para evitar criar isolamento artificial.
     • Conexões fracas: Um limiar definido pelo usuário $\tau_w$ (razão entre a força da conexão e o componente mais forte) filtra divisões onde a conexão com uma vizinhança é muito fraca para ser significativa. Isso previne a criação de pontos visualmente isolados devido a forças de atração insuficientes.

4. Mapeamento e Visualização:

   • O grafo modificado, contendo vértices divididos, é projetado no espaço visual usando técnicas padrão de RD local (por exemplo, UMAP ou ForceAtlas2).
   • Codificação Visual: Instâncias divididas são renderizadas como marcadores distintos (por exemplo, cruzes) conectados por linhas tracejadas à sua posição original ou entre si, permitindo que analistas rastreiem as múltiplas pertenças de vizinhança de um único ponto de dados.

Principais Contribuições

• Definição de Incorporação Parcial de Vizinhança: O artigo introduz e define formalmente este artefato específico decorrente de instâncias ambíguas, distinguindo-o de distorções gerais de RD.
• Detecção Baseada em Teoria dos Grafos: Apresenta um método para identificar instâncias ambíguas usando Pontos de Articulação Locais em grafos de vizinhança esparsificados.
• Mecanismo de Divisão: Os autores propõem uma abordagem concreta, com complexidade de tempo quase linear, para dividir instâncias ambíguas, replicando-as na projeção para refletir múltiplas pertenças de vizinhança.
• Validação Empírica: A abordagem é demonstrada em diversos conjuntos de dados (SVHN, MNIST, corpora de texto e sequenciamento de RNA de célula única), mostrando que revela pertenças de vizinhança ocultas não visíveis em projeções padrão.

Resultados

• Insights Qualitativos: No conjunto de dados SVHN, um dígito '1' mal classificado (previsto como '7') foi mostrado no UMAP padrão como pertencendo exclusivamente à vizinhança '7'. A abordagem proposta dividiu a instância, revelando sua similaridade simultânea com a vizinhança '1', explicando assim a ambiguidade do erro do classificador. Da mesma forma, em dados textuais, um artigo sobre "Modelos Assistidos por ILP para Toxicologia" foi mostrado como pertencendo tanto aos clusters de ILP quanto de Raciocínio Baseado em Casos (CBR), uma dualidade obscurecida em projeções padrão.
• Análise Quantitativa:
  • Impacto da Esparsificação: Experimentos medindo os $k$-vizinhos mais próximos ($k$NN) preservados mostraram que a esparsificação espectral retém estruturas de vizinhança local comparáveis ao grafo original (razões próximas a 1 para a maioria dos conjuntos de dados), embora alguma variância tenha sido observada em dados de célula única de alta dimensionalidade intrínseca.
  • Limitações de Métricas: Métricas padrão (confiabilidade e continuidade) foram consideradas ineficazes para identificar instâncias ambíguas, pois esses pontos são distribuídos de forma semelhante aos pontos não ambíguos nas distribuições das métricas.
  • Sensibilidade a Parâmetros: Aumentar o número de vizinhos no grafo inicial geralmente reduziu o número de divisões detectadas, pois o aumento da conectividade conecta vizinhanças que, de outra forma, pareceriam disjuntas.

Significado e Alegações
O artigo argumenta que reconhecer a ambiguidade é essencial para interpretar estruturas locais de alta granularidade na RD. Os autores afirmam que não levar em conta instâncias ambíguas pode levar a interpretações incompletas ou incorretas, particularmente em domínios como XAI e biologia, onde o contexto ao nível de instância é vital. Ao dividir essas instâncias, o método fornece uma representação mais fiel da topologia de alta dimensão dos dados, revelando "pertenças de vizinhança anteriormente ocultas". O trabalho sugere que as métricas atuais de qualidade de RD são insuficientes para este tipo específico de artefato e que futuros frameworks de avaliação devem levar em conta a ambiguidade orientada por dados, e não apenas a instabilidade induzida pelo mapeamento.