A General Framework on Conditions for Constraint-based Causal Learning

Resumo Técnico: Um Framework Geral para Condições de Aprendizado Causal Baseado em Restrições

1. O Problema

O objetivo principal da inferência causal baseada em grafos é a descoberta causal: recuperar a estrutura causal subjacente (o grafo causal verdadeiro) a partir de dados observacionais.

• Abordagens Baseadas em Restrições: Métodos como o algoritmo PC e SGS operam testando independências condicionais. Para que esses algoritmos retornem o grafo causal correto (ou sua classe de equivalência Markoviana), eles dependem de suposições sobre a relação entre a distribuição de probabilidade dos dados e a estrutura do grafo.
• A Limitação da Fidelidade (Faithfulness): A suposição padrão é a fidelidade, que exige que todas as independências condicionais na distribuição de dados sejam exatamente representadas pelas separações gráficas do grafo causal. No entanto, a fidelidade é frequentemente violada em cenários práticos e teóricos (ex: cancelamentos de parâmetros), sendo considerada uma condição de correção muito forte e, por vezes, irrealista.
• A Lacuna: Existem algoritmos propostos com condições de correção mais fracas (ex: Algoritmo de Permutação Mais Esparsa - SP), mas não havia um quadro teórico unificado para:
  1. Derivar as condições exatas de correção para qualquer algoritmo existente.
  2. Comparar a força das condições de correção entre diferentes algoritmos.
  3. Projetar novos algoritmos garantindo que suas condições de correção sejam fracas o suficiente antes mesmo de definir os passos computacionais.

2. Metodologia e Framework Proposto

Os autores introduzem um framework teórico geral baseado no conceito de "Propriedade" (Property).

• Representação de Algoritmos como Propriedades:
  Qualquer algoritmo de aprendizado causal baseado em restrições que mapeia uma distribuição de entrada $P$ para um conjunto de grafos de saída $G(P)$ pode ser representado por uma propriedade $A$.

  • Definição: $A(P, G) = \top$ se e somente se $G \in G(P)$.
  • Isso estabelece uma dualidade: o algoritmo é definido pela propriedade que seus grafos de saída satisfazem.

• Teorema 1 (Condições de Correção Exatas):
  O teorema central do paper estabelece que, dado um algoritmo correspondente a uma propriedade $A$, a condição necessária e suficiente para o algoritmo ser correto (retornar grafos Markovianamente equivalentes ao grafo verdadeiro $G_0$) é:
  $$A(P, G_0) = \top \quad \text{E} \quad U_A(P) = \top$$
  Onde:

  • $A(P, G_0) = \top$: A distribuição verdadeira satisfaz a propriedade em relação ao grafo verdadeiro.
  • $U_A(P) = \top$ (Unicidade): O conjunto de grafos $\{G \in \mathcal{G} : A(P, G) = \top\}$ pertence à mesma Classe de Equivalência Markoviana (MEC). Ou seja, a propriedade $A$ identifica o grafo de forma única (até equivalência Markoviana).

• Paradigma de Projeto de Algoritmos:
  O framework sugere uma nova ordem de projeto:

  1. Selecionar uma propriedade $A$ (ex: "mais esparsa", "fidelidade de adjacência").
  2. Estudar a condição de correção resultante ($A \land U_A$) para verificar se é fraca o suficiente.
  3. Projetar os passos computacionais do algoritmo para encontrar grafos que satisfaçam $A$.

• Comparação de Força:
  Os autores definem o suporte de uma propriedade ($supp(A)$) como o conjunto de pares $(P, G)$ onde a condição de correção do algoritmo correspondente é válida.

  • Se $supp(A) \subseteq supp(B)$, o algoritmo correspondente a $A$ tem uma condição de correção mais forte (mais restritiva) do que o de $B$.
  • São apresentadas proposições (2 e 3) para comparar a força das condições de correção de diferentes propriedades, mesmo quando as propriedades individuais não são comparáveis diretamente.

3. Principais Contribuições e Resultados

A. Condições Exatas para o Algoritmo PC
Aplicando o framework ao algoritmo PC (e suas variantes), os autores derivam as condições de correção exatas e necessárias para diferentes regras de orientação de arestas (colliders e não-colliders).

• Eles mostram que a condição de correção para o PC depende da implementação específica da regra de orientação (ex: PC conservador vs. PC padrão).
• Demonstram que essas condições exatas são, em geral, incomparáveis entre si e com outras condições existentes (como a suposição de fidelidade restrita), mas fornecem a caracterização precisa de quando o algoritmo falha ou succeeds.

B. A Propriedade "Sparsest Markov Representation" (SMR) é a Mais Fraca
Um dos resultados mais significativos é a prova de que, para algoritmos que visam outputar grafos ancestrais máximos (MAGs) ou DAGs satisfazendo qualquer noção existente de minimalidade:

• A condição Sparsest Markov Representation (SMR) (do algoritmo SP de Raskutti e Uhler) é a condição de correção mais fraca possível.
• Isso significa que qualquer outro algoritmo baseado em noções de minimalidade (como minimalidade causal, Pearl-minimalidade, etc.) exigirá condições de correção estritamente mais fortes para garantir a correção. O algoritmo SP é, portanto, "ótimo" nesse sentido.

C. Necessidade de Reforçar a Pearl-Minimalidade
Os autores analisam a Pearl-minimalidade (a ideia de que não existe um grafo com menos independências que explique os dados).

• Necessidade: Para evitar casos degenerados (onde o algoritmo retorna grafos completos e não informativos), qualquer propriedade significativa para aprendizado causal deve ser pelo menos tão forte quanto a Pearl-minimalidade.
• Insuficiência: No entanto, a Pearl-minimalidade por si só não é suficiente para relaxar a fidelidade. O framework prova que se a propriedade escolhida for apenas a Pearl-minimalidade, a condição de correção resultante (após considerar a unicidade) é equivalente à fidelidade.
• Conclusão: Para aprender causalidade além da fidelidade, é necessário reforçar a Pearl-minimalidade. Isso pode ser feito através de:
  1. Propriedades mais fortes (ex: fidelidade de adjacência + estabilidade V-OUS).
  2. Inclusão de conhecimento prévio (background knowledge) que exclua certos grafos minimalistas.

4. Significado e Implicações

• Unificação Teórica: O paper fornece a primeira estrutura unificada que conecta algoritmos específicos a suas condições de correção teóricas, permitindo uma análise sistemática em vez de provas ad-hoc para cada novo algoritmo.
• Otimização de Algoritmos: Ao identificar que a condição SMR é a mais fraca possível para algoritmos de minimalidade, o trabalho valida o algoritmo SP como o limite teórico de desempenho para essa classe de métodos.
• Guia para Pesquisa Futura: O framework orienta pesquisadores a não apenas criar novos algoritmos, mas a primeiro definir a propriedade desejada e verificar se a condição de correção resultante é viável. Ele esclarece que simplesmente buscar "minimalidade" não é suficiente para superar a fidelidade; é necessário incorporar restrições adicionais (como conhecimento prévio ou estabilidade estrutural específica).
• Interpretabilidade: O framework permite que condições de correção sejam projetadas para serem interpretáveis por especialistas de domínio (ex: "o grafo mais simples que gera os dados"), o que é crucial para aplicações em áreas como genética e ciências sociais onde a fidelidade estrita é duvidosa.

Em resumo, o artigo estabelece que a dualidade entre algoritmo e propriedade é a chave para entender e projetar métodos de descoberta causal, provando matematicamente os limites do que é possível alcançar sob diferentes suposições de minimalidade e identificando a necessidade de combinar minimalidade com conhecimento prévio para superar as limitações da fidelidade.