Structure-aware divergences for comparing probability distributions

Título: Divergências Conscientes da Estrutura para Comparar Distribuições de Probabilidade

Autores: Rohit Sahasrabuddhe e Renaud Lambiotte
Instituições: Universidade de Oxford e Complexity Science Hub, Viena.

---

1. Problema e Motivação

Muitos sistemas naturais e sociais são descritos por distribuições de probabilidade sobre elementos que possuem relações intrínsecas (ex: ocupações com habilidades compartilhadas, espécies com traços funcionais similares).

• Limitação Atual: As ferramentas padrão da teoria da informação, como a Entropia de Shannon e as divergências $f$ (incluindo a Divergência de Kullback-Leibler - KL), tratam os elementos como intercambiáveis e "cegos" à estrutura de similaridade entre eles. Elas assumem que os elementos são ou idênticos ou completamente distintos.
• Necessidade: Existe uma lacuna na literatura para medidas de dissimilaridade (divergências) que incorporem a estrutura do domínio subjacente, permitindo comparar distribuições levando em conta que certos elementos são mais "próximos" ou "similares" do que outros.
• Alternativas Existentes: Métodos como o Transporte Ótimo (OT) conseguem lidar com essa estrutura, mas envolvem problemas de otimização computacionalmente caros (complexidade alta), tornando-os inviáveis para grandes conjuntos de dados ou análises em tempo real.

2. Metodologia Proposta

Os autores introduzem uma nova família de divergências conscientes da estrutura (structure-aware divergences). A abordagem é construída sobre os seguintes pilares teóricos:

A. Entropia Consciente da Estrutura

Baseiam-se no trabalho de Ricotta e Szeidl (e Leinster e Cobbold) para definir uma entropia que considera uma matriz de similaridade $Z$.

• Seja $p$ uma distribuição de probabilidade e $Z$ uma matriz de similaridade ($0 \le Z_{ij} \le 1$, simétrica, $Z_{ii}=1$).
• A Entropia Consciente da Estrutura de ordem $\alpha$ ($H^Z_\alpha$) é definida como:
  • Para $\alpha \neq 1$: $H^Z_\alpha(p) = \frac{1}{\alpha-1} (1 - p^\top (Zp)^{\alpha-1})$
  • Para $\alpha = 1$: $H^Z_1(p) = -p^\top \ln(Zp)$
• Interpretação: A entropia aumenta quando elementos com alta probabilidade são dissimilares. O parâmetro $\alpha$ controla a sensibilidade a elementos raros.

B. Divergência de Bregman

Para criar uma medida de dissimilaridade entre duas distribuições ($p$ e $q$), os autores utilizam a conexão geométrica entre entropias e divergências de Bregman.

• Teorema de Concavidade: Eles provam que, sob a condição de que a matriz $Z$ seja definida positiva ($Z \succ 0$) e $\alpha \ge 2$, a função $-H^Z_\alpha$ é estritamente convexa no interior do simplex de probabilidade.
• Definição da Divergência: A divergência consciente da estrutura, $d^Z_\alpha(p || q)$, é definida como a divergência de Bregman induzida pela função $-H^Z_\alpha$.
  • Fórmula: $d^Z_\alpha(p || q) = H^Z_\alpha(q) - H^Z_\alpha(p) - \langle \nabla H^Z_\alpha(p), q-p \rangle$.
  • Para $\alpha=2$, esta divergência reduz-se à distância de Mahalanobis quadrática: $(p-q)^\top Z (p-q)$.

C. Construção de Matrizes de Similaridade

O artigo discute como garantir que $Z$ seja definida positiva, essencial para a validade matemática da divergência:

• Transformação exponencial de métricas de tipo negativo (ex: $Z_{ij} = \exp(-\tau D_{ij})$).
• Exemplos de espaços métricos válidos: subconjuntos de espaços euclidianos, árvores ponderadas (hierarquias) e grafos com distância de resistência efetiva.
• Se uma matriz de similaridade não for definida positiva, propõe-se um problema de otimização convexa para encontrar a matriz definida positiva mais próxima.

3. Contribuições Principais

1. Novo Framework Teórico: Introdução de uma família de divergências que generaliza a KL-divergência e a entropia de Shannon, incorporando explicitamente a estrutura de similaridade do domínio.
2. Eficiência Computacional: Diferente do Transporte Ótimo (OT), que requer a solução de um problema de otimização linear, as novas divergências possuem expressões de forma fechada (closed-form). Isso permite cálculos extremamente rápidos e escaláveis.
3. Propriedades Geométricas: Como são divergências de Bregman, elas herdam propriedades úteis para agrupamento (clustering), como a propriedade de minimização da média (o centroide de um cluster é a média das distribuições do cluster).
4. Informação de Bregman: Definição de uma medida de dispersão (análoga à variância ou informação mútua) para conjuntos de distribuições, permitindo a avaliação da qualidade de partições em tarefas de clustering.

4. Resultados Experimentais

A. Experimentos Sintéticos

• Recuperação de Padrões: Em um cenário de clustering com dados subamostrados, a divergência consciente da estrutura conseguiu recuperar agrupamentos "plantados" (ground truth) que métodos tradicionais (cegos à estrutura) falharam em identificar, especialmente quando as distribuições não tinham sobreposição direta de elementos.
• Desempenho Computacional: A comparação de tempo de execução mostrou que o cálculo da divergência (Jensen-Bregman) é ordens de magnitude mais rápido que o cálculo da distância de Wasserstein (OT). Para grandes conjuntos de dados, a versão vetorializada é ainda mais eficiente.

B. Aplicação em Geografia Econômica (Reino Unido)

• Dados: Composição ocupacional dos 318 distritos locais (Local Authorities) da Inglaterra e País de Gales (Censo 2021).
• Abordagem: Comparação de regiões baseada em duas noções de "relacionamento" entre ocupações:
  1. Similaridade de Habilidades: Baseada em dados ONET.
  2. Similaridade de Co-localização: Baseada em quais ocupações tendem a aparecer juntas nas mesmas regiões.
• Descobertas:
  • A estrutura altera significativamente o ranking de diversidade e representatividade das regiões.
  • A regionalização (agrupamento de distritos) produz resultados qualitativamente diferentes dependendo da definição de similaridade usada.
  • A abordagem baseada em habilidades agrupa regiões industriais e agrícolas devido à sobreposição de habilidades de trabalhadores braçais, enquanto a co-localização revela especializações setoriais distintas.

C. Aplicação em Ecologia (Glaciar Rutor, Itália)

• Dados: Abundância e traços funcionais de 45 espécies de plantas em 59 parcelas ao longo de uma sucessão primária (estágios inicial, médio e tardio).
• Objetivo: Medir a $\beta$-diversidade funcional (variabilidade da composição funcional entre locais).
• Resultados:
  • O método reproduziu insights estabelecidos anteriormente usando OT: os estágios médio e tardio possuem menor diversidade funcional do que o estágio inicial, apesar de terem turnover taxonômico similar.
  • Isso sugere que, embora as espécies mudem, suas funções ecológicas permanecem estáveis nos estágios posteriores.
  • O método oferece uma alternativa computacionalmente viável ao OT sem sacrificar a interpretabilidade biológica.

5. Significado e Conclusão

O trabalho preenche uma lacuna crítica entre a teoria da informação e a análise de dados estruturados.

• Impacto Prático: Permite a análise de grandes conjuntos de dados complexos (como ecossistemas ou economias regionais) onde a similaridade entre elementos é fundamental, mas onde métodos baseados em OT são computacionalmente proibitivos.
• Flexibilidade: A metodologia permite que pesquisadores testem diferentes hipóteses sobre como os elementos se relacionam (ex: habilidades vs. localização geográfica) e observem como isso altera a estrutura global dos dados.
• Escalabilidade: A natureza de forma fechada das divergências torna o método ideal para aplicações em tempo real e para o crescente volume de dados de abundância de espécies e traços funcionais disponíveis na ciência moderna.

Em suma, os autores demonstram que ignorar a estrutura de similaridade pode levar a conclusões errôneas sobre a diversidade e a dissimilaridade de sistemas, e que suas novas ferramentas oferecem uma solução matematicamente elegante, computacionalmente eficiente e empiricamente robusta.