Resumo Técnico: A Lacuna na Descrição Causal

Declaração do Problema

A hierarquia causal de Pearl estabelece que consultas observacionais, intervencionais e contrafactuais são qualitativamente distintas, com o Teorema da Hierarquia Causal provando que consultas de degrau superior não podem ser geralmente respondidas a partir de informações de degrau inferior. No entanto, a literatura existente trata essa não-identificabilidade como uma obstrução binária: ou uma resposta de degrau superior é determinada por dados de degrau inferior, ou não é.

Este artigo pergunta uma versão quantitativa dessa questão: Quantos bits adicionais de informação são necessários para especificar uma resposta causal de degrau superior uma vez que as respostas de degrau inferior são conhecidas? Os autores formalizam essa "lacuna na descrição causal" para medir a informação residual necessária para resolver ambiguidades quando a identificação falha.

Metodologia

Os autores introduzem um framework baseado na complexidade de Kolmogorov para quantificar o conteúdo de informação de oráculos de resposta causal.

1. Comprimento de Descrição da Classe de Consulta: Para um Modelo Causal Estrutural (MCE) $M$ e uma classe de consulta $Q$ (por exemplo, observacional, intervencional de nó único, contrafactual), o comprimento de descrição $DL(Q; M)$ é definido como a complexidade de Kolmogorov do oráculo de resposta $Ans_Q(M)$, condicionado ao tamanho do sistema $n$.
2. Lacuna na Descrição Causal: A lacuna $\Delta(Q_2 | Q_1; M)$ é a complexidade de Kolmogorov condicional da resposta de degrau superior dada a resposta de degrau inferior:
   $$\Delta(Q_2 | Q_1; M) := K(Ans_{Q_2}(M) \mid Ans_{Q_1}(M), n)$$
3. Princípio da Ambiguidade para Bits: O artigo estabelece um teorema geral ligando lacunas de descrição ao tamanho do conjunto de ambiguidade. Se uma resposta de degrau inferior $a$ é consistente com $N$ oráculos de resposta de degrau superior distintos, a lacuna de descrição é de pelo menos $\log_2 N$ (até termos de ordem inferior). Isso vale tanto em cenários de pior caso (Kolmogorov) quanto em cenários de caso médio (entropia de Shannon).

Os autores constroem famílias específicas de MCEs binários e acíclicos para instanciar essas lacunas, demonstrando que as lacunas podem escalar polinomialmente com o tamanho do sistema $n$.

Principais Contribuições e Resultados

1. Separações Observacionais–Intervencionais

O artigo constrói famílias de MCEs onde a distribuição observacional tem comprimento de descrição constante ($O(1)$), ainda que o oráculo de resposta intervencional exija significativamente mais bits.

• Construção de Árvore Enraizada ($\Theta(n \log n)$):

  • Configuração: Variáveis formam uma árvore enraizada oculta onde a raiz é aleatória e os filhos copiam os pais.
  • Resultado: Todas as árvores produzem a mesma distribuição observacional (correlação perfeita). No entanto, intervenções de nó único revelam os conjuntos de descendentes, identificando unicamente a estrutura da árvore.
  • Lacuna: A lacuna é $\Theta(n \log n)$, correspondendo à informação necessária para codificar uma árvore rotulada (via sequências de Prüfer). Isso é ótimo em ordem para MCEs com grau de entrada limitado ($d=O(1)$).

• Construção de Grafo Bipartido ($\Theta(n^2)$):

  • Configuração: Um grafo bipartido oculto $G$ entre as camadas $A$ e $B$. A camada $A$ copia a raiz; a camada $B$ computa portas AND baseadas nas arestas em $G$.
  • Resultado: Observacionalmente, todos os grafos produzem a mesma distribuição (todos 0s ou todos 1s). Intervenções em nós da camada $A$ revelam seus vizinhos na camada $B$, efetivamente decodificando a matriz de adjacência de $G$.
  • Lacuna: A lacuna é $\Theta(n^2)$ (especificamente $\approx m^2$ onde $n=2m+1$). Isso é ótimo em ordem para mecanismos densos onde o grau de entrada $d = \Theta(n)$.
  • Robustez: Essa separação quadrática persiste mesmo sob descrições de variação total $\epsilon$-precisas para qualquer $\epsilon < 1/4$ fixo.

• Optimalidade Sensível ao Grau:
  Os autores provam um limite superior geral para MCEs com esquema de portas finitas e grau de entrada $d$:
  $$\Delta_{2|1} \le O\left( nd \log \frac{en}{d} + n \log n \right)$$
  Isso confirma que a construção de árvore $\Theta(n \log n)$ é ótima para grau limitado, e a construção bipartida $\Theta(n^2)$ é ótima para grau denso.

2. Separação Contrafactual

Mesmo com conhecimento completo de todas as distribuições intervencionais "hard-do" (o oráculo intervencional completo), consultas contrafactuais podem permanecer ambíguas.

• Construção Modular-XOR ($\Theta(n)$):
  • Configuração: $m$ módulos independentes, cada um sendo ou um mecanismo "sem efeito" (variáveis independentes) ou um mecanismo "XOR" ($Y = X \oplus U$).
  • Resultado: Ambos os mecanismos produzem distribuições observacionais e intervencionais idênticas. No entanto, eles diferem em contrafactuais: sob o mecanismo sem efeito, $Y$ permanece inalterado se $X$ for intervencionado; sob XOR, $Y$ inverte.
  • Lacuna: A lacuna entre o oráculo intervencional completo e o oráculo contrafactual é $\Theta(n)$, correspondendo à string oculta $s \in \{0,1\}^m$ que determina o tipo de mecanismo.

3. Consequências Teóricas de Aprendizado

O artigo deriva um resultado "sem almoço grátis" para aprendizado observacional. Na família bipartida, como todos os mecanismos compartilham a mesma distribuição observacional, a informação mútua entre o grafo oculto e qualquer conjunto de dados observacional é zero. Consequentemente:

• Nenhum aprendiz observacional pode identificar o oráculo intervencional com probabilidade melhor que o palpite aleatório ($2^{-m^2}$).
• Qualquer preditor baseado exclusivamente em dados observacionais tem um erro absoluto esperado de pelo menos $1/4$ para consultas intervencionais.

Significado e Alegações

O artigo afirma transformar a hierarquia qualitativa de Pearl em uma hierarquia de informação quantitativa. Seu significado principal reside em:

1. Refinar a Não-Identificabilidade: Move-se além da questão booleana de "é identificável?" para uma medida precisa de "quanta informação está faltando?".
2. Limites Ótimos em Ordem: Fornece construções explícitas mostrando que a lacuna de informação pode escalar quadraticamente com o tamanho do sistema ($\Theta(n^2)$) para mecanismos densos e linearmente ($\Theta(n)$) para contrafactuais, mesmo quando os dados observacionais são perfeitos.
3. Limites Teóricos de Informação: Demonstra que essas lacunas não são artefatos de dificuldade computacional ou dados finitos; são barreiras fundamentais de teoria da informação. Mesmo com dados observacionais infinitos, a ambiguidade residual permanece, necessitando de intervenções para fechar a lacuna.
4. Princípio Geral: O teorema "Ambiguidade para Bits" unifica esses resultados, mostrando que a lacuna de descrição é fundamentalmente o logaritmo do tamanho do conjunto de ambiguidade residual.

Os autores observam que suas construções são adversariais (binárias, acíclicas, potencialmente violando positividade ou fidelidade) para demonstrar que a adequação observacional por si só não impõe um limite pequeno de descrição causal sem suposições estruturais adicionais. Eles sugerem que trabalhos futuros devem investigar como suposições de esparsidade, ruído ou fidelidade podem reduzir essas ambiguidades residuais.