Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

Resumo Técnico: Descoberta Causal Iterativa com Certificados de Impossibilidade por Aresta

Declaração do Problema
Os algoritmos atuais de descoberta causal tipicamente retornam um grafo acíclico direcionado (DAG) totalmente orientado, mas falham em distinguir entre as direções de arestas identificadas pelos dados e aquelas impostas pelo algoritmo para satisfazer restrições de saída. Sob condições padrão de Markov e fidelidade, dados observacionais identificam apenas uma classe de equivalência de Markov; as orientações de arestas não presentes em estruturas-v são indeterminadas pela distribuição conjunta. Os métodos existentes ou forçam orientações em arestas não identificáveis (por exemplo, NOTEARS, DAGMA) sem justificação diagnóstica, ou as deixam não direcionadas (por exemplo, FCI) sem especificar a informação prévia específica necessária para resolvê-las. Além disso, métodos de otimização contínua demonstraram explorar artefatos de dados (por exemplo, varsortabilidade) que mimetizam identificação genuína. Há uma falta de um protocolo principiado que forneça auditabilidade por aresta, separando explicitamente a identificabilidade baseada em dados da imposição algorítmica, e identificando as perguntas específicas de especialistas necessárias para resolver arestas não identificáveis.

Metodologia
O artigo propõe um protocolo determinístico de três estágios para descoberta causal observacional em dados contínuos. O protocolo emite um "certificado de impossibilidade" discreto para cada aresta candidata em um esqueleto baseado apenas em dados, categorizando a aresta como resolvida (identificada ou mediada pelos dados) ou impossível (dados insuficientes, exigindo entrada de especialista).

1. Estágio 1: Busca por Esqueleto e Mediador:

   • Constrói um esqueleto usando testes HSIC controlados por FDR para descartar pares marginalmente independentes.
   • Realiza uma busca por mediador em múltiplos níveis para identificar e remover arestas mediadas por variáveis observadas.

2. Estágio 2: Cascata de Identificabilidade com Portão:

   • Uma cascata de oito níveis avalia as arestas remanescentes. Os níveis incluem métodos clássicos (ANM Linear $L_0$, ANM Não Linear $L_1$, HOC LiNGAM $L_2$) e cinco novos níveis introduzidos neste trabalho: LSNM (Ruído de Escala-Localização), IGCI (Geométrico-Info), Stein (Correspondência de Pontuação), MDL (Condição de Markov Algorítmica) e PEIT (Teste de Inversão de Entropia).
   • Mecanismo de Portão: Cada nível é pré-condicionado por testes estatísticos (por exemplo, Shapiro–Wilk para não Gaussianidade, testes de heterocedasticidade). Se a pré-condição de um nível falhar, ele se abstém em vez de forçar uma orientação.
   • Consenso Inter-níveis: Uma "guarda de discordância" rebaixa compromissos de $L_0$ se níveis de maior precisão (IGCI, Stein, MDL) contradisserem a direção, renomeando a aresta como impossible_l0_disagrees_with_high_tier.
   • Arestas não resolvidas por qualquer nível recebem um rótulo impossible_*, que codifica o modo de falha específico (por exemplo, confusão latente, não linearidade fraca) e a pergunta correspondente para um especialista do domínio.

3. Estágio 3: Consultas Direcionadas ao Oráculo:

   • O protocolo interage com um especialista do domínio apenas em arestas rotuladas impossible_*.
   • Primitivas de Consulta:
     • Consulta por aresta: Solicita direção (FWD/BWD) ou ausência.
     • Consulta de meta-hub: Solicita os top-$K$ nós por grau de saída.
     • Consulta de filhos de nó: Solicita os filhos diretos de um nó específico, comprometendo todas as arestas de saída simultaneamente.
   • Auto-propagação: Após cada compromisso do oráculo, o sistema executa passagens de auto-resolução sem custo (verificações de aciclicidade, regras de Meek, d-separação transitiva) para resolver arestas adicionais sem consultas adicionais.

Principais Contribuições

1. Certificados por Aresta: O protocolo atribui um código discreto a cada aresta. Os códigos resolved_* citam o teorema específico (por exemplo, $L_{Stein}$) que justifica a direção, enquanto os códigos impossible_* registram o modo de falha e a pergunta específica necessária para resolvê-lo.
2. Abstenção Consciente de Níveis: A introdução de cinco novos níveis com portão (LSNM, IGCI, Stein, MDL, PEIT) garante que as direções sejam comprometidas apenas quando um teorema de identificabilidade específico é satisfeito. Se uma pré-condição falhar, o sistema se abstém em vez de forçar uma orientação potencialmente espúria.
3. Limite de Interação 1+K: O artigo estabelece um limite superior informacional de $1+K$ interações de especialista para recuperar qualquer DAG de verdade fundamental, onde $K$ é o número de vértices não-folha. Isso é alcançado combinando uma única consulta de meta-hub (para identificar alvos) com $K$ consultas de filhos de nó.
4. Elicitação Direcionada: Ao contrário de métodos de aprendizado ativo que podem solicitar ordens topológicas completas ou intervenções amplas, este protocolo isola apenas as arestas não identificáveis e solicita as informações específicas necessárias para resolvê-las.

Resultados Experimentais
O protocolo foi avaliado em quatro benchmarks padrão (Asia, Sachs, Child, Alarm) e dados sintéticos projetados para testar especificamente níveis específicos.

• Desempenho de Oráculo Ideal: Sob a suposição de um oráculo perfeito, o protocolo recuperou o DAG de verdade fundamental com Precisão = Revocação = F1 = 1.000 em todos os quatro benchmarks usando exatamente $1+K$ interações.
  • Alarm (V=37): 46 arestas recuperadas em 27 interações.
  • Sachs (V=11): 17 arestas recuperadas em 8 interações.
• Eficácia da Cascata: No conjunto de dados Sachs, a cascata sozinha resolveu 5 de 19 arestas verdadeiras apenas a partir dos dados. A adição dos novos níveis seguros melhorou a precisão da direção de 61,5% (base L0-L2) para 66,7% quando a guarda de discordância estava ativa.
• Especificidade do Nível: Testes de estresse sintéticos confirmaram que cada novo nível é positivo em precisão em seu regime nativo (por exemplo, LLSNM em ruído de escala-localização, LIGCI em dados quase determinísticos) e se abstém (dispara 0/40) em dados fora do regime, prevenindo falsos positivos.
• Fronteira de Pareto: Em Sachs, o protocolo demonstrou uma compensação entre contagem de consultas e pontuação F1. Uma abordagem "apenas-SEGURO" (cascata sem oráculo) alcançou F1=0,571 com 5 consultas, enquanto o protocolo completo alcançou F1=1.000 com 13 consultas (usando a cascata para reduzir a carga do oráculo).

Significado e Alegações
O artigo afirma abordar uma lacuna fundamental na descoberta causal: a incapacidade dos métodos atuais de distinguir entre direções identificadas pelos dados e aquelas impostas algoritmicamente. Ao anexar um "certificado" a cada aresta, o protocolo fornece um rastro de auditoria transparente.

• Contribuição Teórica: O limite $1+K$ representa o contraparte do lado da eliciação aos limites de orçamento de intervenção na descoberta causal ativa, quantificando a informação mínima necessária para resolver um DAG quando o conhecimento de especialista está disponível.
• Utilidade Prática: O protocolo permite que os praticantes foquem o esforço do especialista exclusivamente em arestas não identificáveis, reduzindo a carga cognitiva ao apresentar perguntas específicas e conscientes do regime em vez de direções de arestas brutas.
• Limitações: Os autores notam explicitamente que o escopo atual é restrito a variáveis contínuas; redes bayesianas discretas são tratadas apenas como uma verificação de robustez para a camada do oráculo. O protocolo assume um oráculo perfeito; o tratamento de respostas de especialistas ruidosas ou probabilísticas é identificado como trabalho futuro. Além disso, a fase de construção do esqueleto impõe um limite de revocação, pois arestas podadas pelo teste HSIC inicial não podem ser recuperadas.

O trabalho posiciona-se não como um substituto para otimização contínua escalável ou métodos baseados em restrições, mas como uma abordagem ortogonal que prioriza a auditabilidade por aresta e minimiza o custo da eliciação de especialistas por meio de consultas direcionadas e orientadas por certificados.