Resumo Técnico: Um Framework de Decomposição Recursiva para Aprendizado de Estrutura Causal na Presença de Variáveis Latentes

Declaração do Problema

A descoberta causal baseada em restrições é uma abordagem fundamental para inferir estruturas causais a partir de dados observacionais. No entanto, sua dependência de testes exaustivos de independência condicional (IC) torna-a computacionalmente proibitiva em cenários de alta dimensionalidade. Embora frameworks de dividir-e-conquistar tenham sido propostos para mitigar esse custo, decompondo tarefas globais de aprendizado em subproblemas menores, os métodos existentes dependem criticamente da suposição de suficiência causal (isto é, a ausência de variáveis latentes). Em sistemas do mundo real onde confundidores latentes são prevalentes, esses métodos falham, pois a presença de causas comuns não observadas induz dependências complexas que violam as premissas necessárias para a decomposição padrão.

A questão central abordada por este trabalho é: É possível generalizar teoricamente estratégias de dividir-e-conquistar para aprendizado de estrutura causal além da suficiência causal, para cenários com variáveis latentes?

Metodologia: O Framework DICOLA

Os autores propõem o DICOLA (Dividir-e-Conquistar para Variáveis Latentes), um framework de decomposição recursiva projetado para recuperar o Gráfico Ancestral Parcial (PAG) que representa a classe de equivalência de Markov do Gráfico Ancestral Maximal (MAG) subjacente na presença de variáveis latentes.

Fundamentos Teóricos

O framework é construído sobre as propriedades da m-separação em grafos ancestrais. Os autores estabelecem três teoremas-chave que justificam o processo de decomposição e reconstrução:

1. Teorema 1: Se um conjunto de variáveis $O$ for particionado em subconjuntos disjuntos $(A, B, C)$ tal que $A \perp\!\!\!\perp B \mid C$, então, para qualquer $X \in A$ e $Y \in A \cup C$, a m-separação de $X$ e $Y$ depende apenas de subconjuntos de $A \cup C$. Variáveis em $B$ são irrelevantes para determinar conjuntos separadores para pares dentro de $A \cup C$.
2. Teorema 2: Para vértices distintos $X, Y \in C$, se eles forem m-separados no conjunto completo $O$, um conjunto separador existe dentro de $A \cup C$ ou $B \cup C$.
3. Teorema 3 (Princípio de Reconstrução): O esqueleto global pode ser recuperado mesclando esqueletos locais de subproblemas. Especificamente, as arestas entre variáveis fora do separador $C$ são herdadas diretamente, enquanto as arestas dentro de $C$ são mantidas apenas se existirem em ambas as sub-soluções.

Implementação Algorítmica

O framework DICOLA segue um paradigma de "dividir-aprender-mesclar":

1. Decomposição (Dividir): O algoritmo identifica uma tripartição válida $(A, B, C)$ das variáveis observadas $K$ tal que $A \perp\!\!\!\perp B \mid C$. Para encontrar isso eficientemente, constrói um Grafo de Independência Não Direcionado (UIG) baseado nos Mantos de Markov das variáveis. O UIG serve como uma estrutura substituta onde separadores de vértices correspondem a separadores de independência condicional válidos no MAG subjacente.
2. Aprendizado Local (Aprender): O problema global é decomposto recursivamente em subproblemas definidos em $A \cup C$ e $B \cup C$. Isso continua até que subproblemas folha sejam alcançados, onde nenhuma tripartição válida adicional existe. Nas folhas, um algoritmo base de descoberta causal (por exemplo, FCI, RFCI) é executado para aprender o esqueleto local.
3. Reconstrução (Mesclar): Esqueletos locais são mesclados de baixo para cima. A etapa de mesclagem aplica o Teorema 3: a união das arestas dos esqueletos filhos forma o esqueleto pai, com arestas dentro do conjunto separador $C$ removidas se estiverem ausentes em qualquer um dos esqueletos filhos. Finalmente, regras de orientação (Zhang, 2008b) são aplicadas ao esqueleto global para produzir o PAG.

Contribuições Principais

1. Generalização Teórica: O artigo estabelece a primeira base teórica para aprendizado de estrutura causal por dividir-e-conquistar na presença de variáveis latentes. Os autores provam que as relações de m-separação se propagam de cima para baixo durante a decomposição e exibem consistência de baixo para cima durante a mesclagem, garantindo que a decomposição não perca informações relativas à classe de equivalência de Markov.
2. Framework DICOLA: Um framework recursivo inovador que se integra a algoritmos existentes baseados em restrições. Os autores provam que, se o aprendiz base for correto e completo, o DICOLA também é correto e completo.
3. Eficiência via Mantos de Markov: O método aproveita a aprendizagem de mantos de Markov para construir UIGs mínimos, permitindo a identificação de decomposições válidas sem testes exaustivos de IC sobre todo o conjunto de variáveis.

Resultados Experimentais

Os autores avaliaram o DICOLA integrando-o a cinco algoritmos de última geração: FCI, RFCI, FCI+, L-MARVEL e ICD. Os experimentos foram conduzidos em dados sintéticos (grafos aleatórios Erdős–Rényi e redes bayesianas de referência) e um conjunto de dados de expressão gênica do mundo real (Arabidopsis thaliana).

• Eficiência Computacional: Em todos os cenários, o DICOLA reduziu significativamente o número de testes de IC e o tempo de execução em comparação com os algoritmos base independentes. A aceleração foi mais pronunciada em grafos esparsos e bem decomponíveis.
• Precisão Estrutural: O framework geralmente manteve ou melhorou as pontuações F1 dos métodos base. Em alguns cenários de grafos mais simples, observou-se uma pequena troca na precisão para combinações específicas (por exemplo, DICOLA+L-MARVEL), mas isso foi mitigado em cenários mais complexos e de alta dimensionalidade com conectividade densa ou maior confundimento latente.
• Aplicação no Mundo Real: Aplicado aos dados de expressão gênica de Arabidopsis thaliana, o DICOLA+FCI recuperou com sucesso a estrutura modular de vias metabólicas conhecidas (MEP e MVA), identificando conexões densas intra-vias e interações inter-vias esparsas consistentes com a literatura biológica.

Significado e Alegações

O artigo alega fornecer uma solução teoricamente justificada para uma limitação de longa data na descoberta causal: a incapacidade de aplicar estratégias de dividir-e-conquistar quando variáveis latentes estão presentes. Ao provar a correção e a completude do framework, os autores demonstram que a eficiência computacional pode ser alcançada sem sacrificar as garantias teóricas necessárias para inferência causal válida na presença de confundimento.

Os autores observam que, embora a aceleração seja substancial para grafos esparsos, os benefícios diminuem à medida que a densidade do grafo aumenta, pois encontrar separadores válidos torna-se mais difícil. No entanto, eles enfatizam que o framework permanece correto mesmo nesses casos, degradando-se efetivamente para o desempenho do aprendiz base em vez de produzir resultados incorretos. O trabalho abre caminho para a aplicação de técnicas escaláveis de dividir-e-conquistar a uma gama mais ampla de problemas de descoberta causal do mundo real, onde o confundimento latente é a norma e não a exceção.