Resumo Técnico: Descoberta Causal em Misturas de Populações

Declaração do Problema

O artigo aborda o desafio da descoberta causal na presença de confundimento latente pervasivo (global). Especificamente, os autores consideram um cenário onde variáveis observadas $V$ são geradas a partir de um Grafo Acíclico Dirigido (DAG) $G$, mas os dados são uma mistura de $k$ populações distintas (classes latentes) determinadas por uma variável discreta não observada $U$. No grafo aumentado $G'$, $U$ atua como uma causa comum apontando para todas as variáveis observadas $V \in V$.

Esta estrutura cria um "confundidor global" que d-conecta todos os pares de variáveis observadas, tornando ineficazes os testes padrão de independência condicional (CI). Como $U$ está em todos os conjuntos separadores, nenhuma independência condicional ocorre entre as variáveis observadas na distribuição marginal $Pr(V)$. Métodos existentes para descoberta causal com variáveis latentes normalmente dependem de suposições paramétricas (ex: linearidade, ruído Gaussiano) ou assumem que variáveis latentes afetam apenas poucas variáveis observadas (baixo grau de saída). Este artigo foca no cenário não paramétrico com equações estruturais e funções de ruído arbitrárias, assumindo apenas que o confundidor latente $U$ é discreto com um número conhecido de classes $k$.

Metodologia

A abordagem proposta substitui os testes de CI padrão por testes de posto de matriz e utiliza um framework algorítmico de três fases:

1. Testes de Posto como uma Generalização de CI

A principal percepção teórica é que, embora a CI falhe sob confundimento global, o posto não negativo de matrizes de probabilidade revela a estrutura gráfica.

• Matrizes de Probabilidade: Para variáveis $X, Y$ e conjunto de condicionamento $C$, a matriz $M[X, Y | c]$ é definida pelos termos $Pr(x, y | c)$.
• Lema do Posto: Se $X$ e $Y$ são d-separados por $C$ no verdadeiro DAG $G'$, então o posto não negativo da matriz $M[X, Y | C]$ é no máximo $k$ (o número de classes latentes). Inversamente, se eles são d-conectados, o posto é genericamente maior que $k$.
• Teste de Hipótese: Os autores desenvolvem um teste estatístico de hipótese para o posto de matriz baseado em Ratsimalahelo [2001], que se mostra superior ao limiar de valores singulares (singular value thresholding) ingênuo.

2. Aglomeração para Alfabetos Pequenos

Um desafio prático surge quando as variáveis observadas são binárias (Bernoulli), pois um par único gera uma matriz $2 \times 2$ com posto no máximo 2, o que não consegue distinguir $k \ge 2$.

• Solução: O algoritmo aglomera conjuntos de $\lceil \lg(k+1) \rceil$ variáveis binárias em "supervariáveis" com maior cardinalidade ($k+1$).
• Aglomeração Preservadora de Independência (IPA): O método busca conjuntos de variáveis que podem ser d-separados por um conjunto de condicionamento. Se tal conjunto existir, as supervariáveis aglomeradas exibirão um posto $\le k$ em sua matriz de probabilidade, permitindo que o algoritmo detecte a não-adjacência.

3. Fases Algorítmicas

O algoritmo procede em três fases:

• Fase I (Testes de Posto Aglomerados): Um algoritmo PC modificado que itera sobre conjuntos de condicionamento e supervariáveis aglomeradas. Ele remove arestas entre variáveis que satisfazem a condição de posto $\le k$. Esta fase recupera o "esqueleto" (adjacências), mas pode deixar arestas de Falso Positivo (FP) entre "vértices iniciais" (nós com poucos não-descendentes) onde a aglomeração é impossível.
• Fase II (Correção k-MixProd): Para resolver as arestas de FP, o algoritmo constrói instâncias do problema k-MixProd (identificação de misturas de distribuições de produto). Ele seleciona subconjuntos de variáveis $T_{ij}$ (contendo os endpoints da aresta candidata e seus vizinhos) e outros dois conjuntos aglomerados disjuntos $X_1, X_2$. Ao condicionar em um conjunto específico $Z_{ij}$ (vizinhos de $X_1, X_2$), o algoritmo garante que $T_{ij}, X_1, X_2$ sejam mutuamente independentes dado $U$. Um oráculo resolve a distribuição conjunta $Pr(T_{ij} | u)$, permitindo que testes de CI padrão sejam executados dentro de cada classe latente para verificar ou remover a aresta.
• Fase III (Orientação): Idêntica ao algoritmo PC padrão, utilizando o esqueleto recuperado e conjuntos separadores para orientar as arestas via v-estruturas e regras de Meek, resultando em um CP-DAG (Completed Partial DAG) que representa a Classe de Equivalência de Markov (MEC).

Principais Contribuições

1. Primeiro Algoritmo Não Paramétrico: O artigo apresenta o primeiro algoritmo para identificar estruturas causais em um cenário de mistura com um confundidor discreto global sem fazer suposições paramétricas sobre as variáveis observadas (ex: linearidade ou Gaussianidade).
2. Teste Baseado em Posto: Estabelece que os testes de posto de matriz são uma generalização dos testes de CI para configurações com confundimento pervasivo e fornece um teste de hipótese estatística rigoroso para o posto de matriz.
3. Técnica de Aglomeração: Introduz um método para lidar com variáveis de "alfabeto pequeno" (binárias) através da aglomeração em supervariáveis maiores, permitindo a aplicação de restrições de posto em cenários de baixa cardinalidade.
4. Limites de Identificabilidade: Os autores derivam condições suficientes para a identificabilidade genérica. Especificamente, se o número de variáveis observadas $|V|$ satisfaz:
   $$|V| \ge (\Delta^3 + 2\Delta^2 + 4\Delta + 2)\lceil \lg(k+1) \rceil + 2\Delta^2 + 2\Delta^3$$
   onde $\Delta$ é o grau máximo do DAG, a estrutura causal é identificável até sua MEC.
5. Análise de Complexidade: O algoritmo roda em tempo polinomial em $|V|$ e exponencial em $\Delta$ e $\log(k)$, dependendo de oráculos para posto não negativo e k-MixProd.

Resultados Empíricos

Os autores validam sua abordagem usando dados sintéticos com verdade fundamental conhecida:

• Eficácia do Teste de Posto: O teste de hipótese proposto para o posto de matriz supera significativamente o limiar de valores singulares na distinção entre estruturas de grafos conectados e divididos, particularmente com tamanhos de amostra acima de 2.000.
• Sensibilidade à Densidade: O algoritmo performa de forma robusta em regimes de grafos esparsos (o foco teórico), recuperando corretamente arestas e removendo não-arestas. O desempenho degrada conforme a densidade do grafo aumenta (levando a falsos positivos), o que é esperado, pois as suposições de esparsidade necessárias para a aglomeração tornam-se mais difíceis de satisfazer.
• Comparação: Diferente dos algoritmos PC e FCI, que falham ao modelar o confundidor global e retornam grafos densos independentemente da verdadeira esparsidade, o método proposto remove efetivamente as dependências induzidas pelo confundimento em regimes esparsos.
• Sensibilidade de Parâmetros: Experimentos mostram que o método é sensível à escolha de $k$; um $k$ incorreto leva a grafos excessivamente densos ou excessivamente esparsos, sugerindo uma estratégia de ajuste prático.

Significância e Alegações

O artigo afirma fornecer uma fundação teórica para a descoberta causal em populações heterogêneas onde uma classe latente discreta confunde todas as observações.

• Novidade Teórica: Demonstra que o confundimento global não impede a identificabilidade se o número de classes latentes for pequeno em relação ao tamanho e esparsidade do sistema, mesmo sem restrições paramétricas.
• Utilidade Prática: O método oferece um caminho para aprender estruturas causais a partir de fontes de dados mistas (ex: diferentes demografias ou ambientes) onde métodos padrão falham devido ao confundimento não observado.
• Modéstia: Os autores reconhecem que seus limites de identificabilidade são suficientes, mas não necessariamente apertados (o limite "frouxo" de pior caso). Eles notam que a exigência de um $k$ conhecido é uma limitação comum a modelos de mistura, embora $k$ possa ser estimado ou ajustado. A abordagem foca atualmente em observáveis discretos, embora sugiram extensões para variáveis contínuas via matrizes de momentos.

O trabalho une descoberta causal, modelos de mistura e decomposição tensorial, oferecendo um novo conjunto de ferramentas para aprender estruturas causais em ambientes de dados complexos e heterogêneos.