$p$-adic Principal Component Analysis

O artigo formula um problema de otimização $p$-ádica sobre fatoração de matrizes e investiga um método heurístico análogo à Análise de Componentes Principais (PCA).

O essencial

Imagine que você tem uma pilha gigante de dados: nomes, endereços, códigos de barras, ou até mesmo respostas de "Sim" e "Não". O objetivo é encontrar padrões escondidos nessa bagunça e reduzir a quantidade de dados sem perder a essência da história.

No mundo real, usamos uma ferramenta chamada PCA (Análise de Componentes Principais) para isso. Pense no PCA como um "espremedor de suco" matemático. Ele pega uma fruta complexa (seus dados) e espreme para extrair apenas o suco mais importante (os padrões principais), descartando a polpa e a casca (o ruído).

Mas e se os seus dados não forem frutas, mas sim números que se comportam de maneira estranha e "saltitante"? É aqui que entra o trabalho de Tomoki Mihara.

O Problema: Números que "Pulam" em vez de "Fluírem"

A maioria das nossas ferramentas matemáticas foi feita para números reais (como 1, 2, 3, 1.5, 1.5001...). Eles fluem suavemente, como água em um rio. Se você se move um pouquinho, a distância muda um pouquinho.

Mas existe um outro universo de números chamado números p-ádicos (onde "p" é um número primo, como 2, 3, 5...). Imagine que esses números não fluem como água, mas se comportam como grãos de areia ou pixels em uma imagem digital.

• Eles são "desconectados".
• A distância entre dois números não é medida por quanto eles diferem em valor, mas por quão parecidos são os seus "códigos de barras" internos.
• Se dois números terminam com os mesmos dígitos, eles são "vizinhos", mesmo que um seja 1 e o outro seja 1.000.000.

O problema é que a "espremedora de suco" tradicional (PCA normal) quebra quando tenta espremer esses grãos de areia. Ela tenta usar regras de geometria suave que não funcionam aqui.

A Solução: A Nova "Espremedora" P-ádica

O autor criou uma nova versão do PCA feita especificamente para esse mundo de grãos de areia. Ele chama isso de PCA P-ádico.

Aqui está como ele funciona, usando analogias simples:

1. O Conceito de "Perpendicularidade" (Ortogonalidade)

No mundo real, se você tem duas setas (vetores) que formam um "T" perfeito, elas são perpendiculares. Isso ajuda a separar as informações.
No mundo p-ádico, não existe um "T" perfeito. Em vez disso, o autor define "perpendicularidade" baseada em vizinhança.

• Analogia: Imagine que você está tentando encontrar o ponto mais próximo de uma casa em uma cidade onde as ruas são labirintos. No mundo p-ádico, "perpendicular" significa: "Se eu tentar projetar este dado naquela direção, o erro (a distância) será o menor possível". É como encontrar o caminho mais curto em um labirinto, não o ângulo reto.

2. O Algoritmo: "Cortar e Descartar"

O PCA normal tenta encontrar as direções onde os dados variam mais. O PCA P-ádico faz algo parecido, mas com uma técnica de "corte":

• Ele olha para os dados e tenta encontrar um "padrão mestre" (um vetor) que explique a maior parte deles.
• Ele "subtrai" esse padrão dos dados.
• Repete o processo com o que sobrou.
• A Diferença: Como os números p-ádicos são discretos (saltam), ele usa uma árvore de decisão (chamada Trie Tree) para navegar pelos dígitos dos números, como se estivesse procurando um nome em uma lista telefônica organizada, para encontrar o melhor "corte" possível.

3. Duas Versões da Ferramenta

O autor criou duas versões dessa ferramenta:

• NRPCA (Não Reduzida): É como tentar adivinhar o padrão olhando apenas para o primeiro dado que você vê. É rápido, mas pode errar se o primeiro dado for estranho.
• RPCA (Reduzida): É mais inteligente. Antes de começar a espremer, ela organiza todos os dados, remove as redundâncias (como se arrumasse uma bagunça de roupas antes de dobrá-las) e só então começa a extrair os padrões. É mais lento, mas muito mais preciso.

Por que isso é útil? (O Teste de Detecção de Anomalias)

O autor testou sua ferramenta em um cenário de detecção de fraudes (anomaly detection).

• Cenário: Imagine um banco com milhões de transações normais e algumas poucas fraudulentas.
• O Desafio: As transações fraudulentas podem parecer "normais" em valor, mas têm uma estrutura interna diferente.
• O Resultado: A ferramenta RPCA foi incrível. Ela conseguiu identificar as transações fraudulentas mesmo quando elas tinham valores altos (o que confundiria outros métodos). Ela percebeu que a "estrutura interna" (os dígitos finais) das transações fraudulentas não se encaixava no padrão dos dados normais.

Resumo da Ópera

Imagine que você tem um quebra-cabeça feito de peças magnéticas que só se encaixam de um jeito muito específico (números p-ádicos).

• O PCA antigo tentava forçar as peças a se encaixarem como se fossem de madeira (números reais), e o quebra-cabeça não funcionava.
• O PCA P-ádico do autor aprendeu a lógica magnética. Ele organiza as peças, encontra as que formam a imagem principal e descarta as que não servem, conseguindo ver a "imagem" (o padrão) mesmo em meio a peças que parecem estranhas à primeira vista.

Em suma: Este paper é sobre ensinar computadores a "enxergar" padrões em dados que têm uma estrutura matemática totalmente diferente da nossa, usando uma nova lógica de "perpendicularidade" e "espremedor" feita sob medida para esse universo digital e desconectado. É uma ponte entre a teoria dos números antiga e a inteligência artificial moderna.

Resumo técnico

Resumo Técnico: Análise de Componentes Principais p-ádica

1. O Problema e o Contexto

A Análise de Componentes Principais (PCA) é uma ferramenta fundamental para redução de dimensionalidade em dados contínuos reais, baseada em álgebra linear sobre $\mathbb{R}$. No entanto, sua aplicação direta a variáveis categóricas (especialmente aquelas com estruturas algébricas, como $\{0, 1\}$ com operações booleanas ou $\mathbb{Z}/n\mathbb{Z}$ com aritmética modular) é problemática.

• Limitação Atual: Embeddings tradicionais em espaços euclidianos frequentemente ignoram a estrutura algébrica original dos dados, criando componentes que são combinações formais irreais das categorias.
• Desafio p-ádico: O autor propõe formular a PCA no contexto dos números p-ádicos ($\mathbb{Q}_p$ e $\mathbb{Z}_p$), que possuem estruturas algébricas e topológicas distintas dos reais (ex: total desconexão, métrica ultramétrica).
• Obstáculos Técnicos:
  • A ausência de uma teoria de gradientes natural em $\mathbb{Q}_p$ impede o uso de métodos de otimização baseados em derivadas (como descida de gradiente clássica).
  • Matrizes simétricas não são necessariamente diagonalizáveis em $\mathbb{Q}_p$, invalidando a técnica padrão de PCA baseada na diagonalização da matriz de covariância.
  • A norma padrão e o produto interno p-ádico não satisfazem propriedades de não-degenerescência ou ortogonalidade de forma análoga aos reais.
  • O uso da norma $\ell_\infty$ (comum em teoria de números p-ádicos via forma normal de Smith) é inadequado para detecção de anomalias, pois frequentemente leva a empates de valores devido à natureza discreta dos valores p-ádicos.

2. Metodologia Proposta

O artigo desenvolve uma abordagem heurística para PCA p-ádica baseada em fatoração de matrizes e minimização de erro sob a norma $\ell_q$ (para $q \in [1, \infty)$), em vez de $\ell_\infty$.

A. Ortogonalidade p-ádica
O autor redefine a ortogonalidade não através de um produto interno, mas através da relação geométrica entre perpendicularidade e o ponto mais próximo:

• Um vetor $\vec{w}$ é a componente de $\vec{v}_0$ ao longo de $\vec{v}_1$ se $\vec{w}$ for o vizinho mais próximo de $\vec{v}_0$ na linha gerada por $\vec{v}_1$ (minimizando a distância).
• $\vec{v}_0$ é dito ortogonal a $\vec{v}_1$ se a projeção de $\vec{v}_0$ sobre $\vec{v}_1$ for zero.
• Algoritmos de Otimização: Para encontrar essas projeções, o autor utiliza uma árvore Trie (árvore de prefixos) para realizar uma busca em profundidade (DFS) sobre os dígitos p-ádicos, permitindo o cálculo eficiente da projeção ótima módulo $p^E$.

B. Algoritmos de PCA
São propostas duas variações heurísticas para a decomposição de baixa rank:

1. NRPCA (Non-reduced p-adic PCA):
   • Seleciona vetores de base dinamicamente a partir dos dados de entrada (primeira entrada não nula disponível).
   • É mais rápido, mas não garante que o sistema de coordenadas resultante seja ortogonal.
2. RPCA (Reduced p-adic PCA):
   • Realiza um pré-processamento onde os dados de entrada sofrem uma "ortogonalização iterada" (similar a um Gram-Schmidt adaptado, mas repetido até a estabilidade).
   • Seleciona os vetores de base a partir deste sistema ortogonalizado pré-computado.
   • Garante um sistema de coordenadas aproximadamente ortogonal, melhorando a qualidade da aproximação, embora com custo computacional maior.

C. Busca Local e Descida de Coordenada
O artigo introduz "Busca de Linha p-ádica" e "Descida de Coordenada p-ádica" para refinar a solução heurística, verificando se a solução é localmente ótima em relação a subconjuntos de vetores, embora os experimentos mostrem que a RPCA já atinge ótimo local na maioria dos casos.

3. Contribuições Principais

• Formulação Teórica: Estabelece um framework rigoroso para PCA em espaços vetoriais normados sobre corpos locais ($\mathbb{Q}_p$), contornando a falta de diagonalização de matrizes e gradientes.
• Definição de Ortogonalidade: Introduz uma nova definição de ortogonalidade baseada em vizinhança mínima, adaptada à métrica ultramétrica.
• Algoritmos Eficientes: Desenvolve algoritmos baseados em árvores Trie para resolver problemas de otimização de projeção em $\mathbb{Z}_p$ sem erros numéricos (usando aritmética inteira).
• Aplicação em Detecção de Anomalias: Demonstra que a PCA p-ádica baseada em $\ell_q$ supera métodos baseados em $\ell_\infty$ (como a forma normal de Smith) em tarefas de detecção de anomalias, onde anomalias podem ter normas $\ell_\infty$ pequenas, mas ainda serem estruturalmente diferentes.

4. Resultados Experimentais

Os experimentos foram conduzidos com $p=7$, dimensão $D=100$, e precisão $E=5$, focando em tarefas de detecção de anomalias em dois cenários:

1. Bolas Abertas (Open Balls):

   • Dados normais distribuídos em bolas fechadas de raio $|p|^2$.
   • Resultado: A RPCA superou consistentemente a NRPCA, apresentando taxas de verdadeiros positivos (True Positive Ratio) muito mais altas (frequentemente próximas de 1.00) e taxas de falsos positivos baixas.
   • A RPCA conseguiu distinguir componentes significativos (bolas "pares") de anomalias, mesmo quando as anomalias tinham normas $\ell_\infty$ grandes, algo que métodos baseados em Smith não conseguiriam.
   • Quando o número de bolas ($B$) excedia a dimensão de redução ($D^-$), o desempenho caiu, o que é esperado, mas a RPCA ainda manteve superioridade relativa.

2. Subespaços Afins (Affine Subspace):

   • Dados normais gerados em um subespaço afim de dimensão $D'$ com ruído limitado.
   • Resultado: A RPCA manteve um desempenho excepcionalmente alto (True Positive Ratio > 0.96) mesmo quando a dimensão do subespaço ($D'$) era maior que a dimensão de redução alvo ($D^-$).
   • Isso é notável porque métodos puramente algébricos (como eliminação de Gauss sobre $\mathbb{F}_p$ ou forma de Smith) falham nesses cenários não supervisionados quando as anomalias têm normas $\ell_\infty$ maiores que as linhas do gerador do subespaço.

5. Significado e Conclusão

O trabalho de Mihara é significativo por:

• Ponte entre Teoria e Prática: Conectar a teoria profunda dos números p-ádicos com problemas modernos de aprendizado de máquina e análise de dados.
• Novo Paradigma para Dados Categóricos: Oferecer uma alternativa viável para análise de dados categóricos que respeita a estrutura algébrica subjacente (como operações booleanas ou modulares), evitando a perda de informação inerente a embeddings euclidianos.
• Superioridade em Cenários Específicos: Demonstrar que, em contextos onde a topologia ultramétrica é relevante (dados discretos, hierárquicos ou com estrutura modular), a PCA p-ádica pode superar métodos lineares clássicos e métodos baseados em $\ell_\infty$, especialmente em detecção de anomalias complexas.

Em suma, o artigo apresenta uma ferramenta robusta para redução de dimensionalidade em domínios não-euclidianos, validada experimentalmente como superior em cenários onde a estrutura algébrica dos dados é crítica.