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

Resumen Técnico: Descubrimiento Causal Iterativo con Certificados de Imposibilidad por Arista

Enunciado del Problema
Los algoritmos actuales de descubrimiento causal suelen devolver un grafo acíclico dirigido (DAG) completamente orientado, pero no logran distinguir entre las direcciones de las aristas identificadas por los datos y las impuestas por el algoritmo para satisfacer las restricciones de salida. Bajo las condiciones estándar de Markov y fidelidad, los datos observacionales identifican únicamente una clase de equivalencia de Markov; las orientaciones de las aristas que no forman estructuras-v quedan indeterminadas por la distribución conjunta. Los métodos existentes o bien fuerzan orientaciones en aristas no identificables (por ejemplo, NOTEARS, DAGMA) sin justificación diagnóstica, o las dejan sin dirección (por ejemplo, FCI) sin especificar la información previa concreta necesaria para resolverlas. Además, se ha demostrado que los métodos de optimización continua explotan artefactos de los datos (por ejemplo, la varsortabilidad) que imitan una identificación genuina. Existe una falta de un protocolo principista que proporcione auditabilidad por arista, separando explícitamente la identificabilidad basada en datos de la imposición algorítmica, e identificando las preguntas específicas de expertos necesarias para resolver las aristas no identificables.

Metodología
El artículo propone un protocolo determinista de tres etapas para el descubrimiento causal observacional en datos continuos. El protocolo emite un "certificado de imposibilidad" discreto para cada arista candidata en un esqueleto basado solo en datos, categorizando la arista como resuelta (identificada o mediada por datos) o imposible (datos insuficientes, requiriendo entrada de experto).

1. Etapa 1: Búsqueda de Esqueleto y Mediadores:

   • Construye un esqueleto utilizando pruebas HSIC controladas por FDR para descartar pares marginalmente independientes.
   • Realiza una búsqueda de mediadores multinivel para identificar y eliminar aristas mediadas por variables observadas.

2. Etapa 2: Cascada de Identificabilidad con Puertas:

   • Una cascada de ocho niveles evalúa las aristas restantes. Los niveles incluyen métodos clásicos (ANM Lineal $L_0$, ANM No Lineal $L_1$, HOC LiNGAM $L_2$) y cinco nuevos niveles introducidos en este trabajo: LSNM (Ruido de Escala-Localización), IGCI (Geometría de la Información), Stein (Emparejamiento de Puntuaciones), MDL (Condición de Markov Algorítmica) y PEIT (Prueba de Inversión de Entropía).
   • Mecanismo de Puerta: Cada nivel está precondicionado por pruebas estadísticas (por ejemplo, Shapiro–Wilk para no gaussianidad, pruebas de heterocedasticidad). Si falla la precondición de un nivel, este se abstiene en lugar de forzar una orientación.
   • Consenso Trans-Nivel: Una "guardia de desacuerdo" degrada los compromisos de $L_0$ si niveles de mayor precisión (IGCI, Stein, MDL) contradicen la dirección, reetiquetando la arista como impossible_l0_disagrees_with_high_tier.
   • Las aristas no resueltas por ningún nivel reciben una etiqueta impossible_*, que codifica el modo de fallo específico (por ejemplo, confusión latente, no linealidad débil) y la pregunta correspondiente para un experto del dominio.

3. Etapa 3: Consultas Dirigidas al Oráculo:

   • El protocolo interactúa con un experto del dominio únicamente en aristas etiquetadas como impossible_*.
   • Primitivas de Consulta:
     • Consulta por arista: Pide la dirección (FWD/BWD) o la ausencia.
     • Consulta de meta-hub: Pide los nodos top-$K$ por grado de salida.
     • Consulta de hijos de nodo: Pide los hijos directos de un nodo específico, comprometiendo todas las aristas de salida simultáneamente.
   • Auto-propagación: Después de cada compromiso del oráculo, el sistema ejecuta pasadas de auto-resolución de costo cero (comprobaciones de aciclicidad, reglas de Meek, d-separación transitiva) para resolver aristas adicionales sin consultas adicionales.

Contribuciones Clave

1. Certificados por Arista: El protocolo asigna un código discreto a cada arista. Los códigos resolved_* citan el teorema específico (por ejemplo, $L_{Stein}$) que justifica la dirección, mientras que los códigos impossible_* registran el modo de fallo y la pregunta específica requerida para resolverlo.
2. Abstención Consciente de Nivel: La introducción de cinco nuevos niveles con puertas (LSNM, IGCI, Stein, MDL, PEIT) asegura que las direcciones solo se comprometan cuando se satisface un teorema de identificabilidad específico. Si falla una precondición, el sistema se abstiene en lugar de forzar una orientación potencialmente espuria.
3. Límite de Interacción 1+K: El artículo establece un límite superior teórica de la información de $1+K$ interacciones de expertos para recuperar cualquier DAG de verdad fundamental, donde $K$ es el número de vértices no hoja. Esto se logra combinando una única consulta de meta-hub (para identificar objetivos) con $K$ consultas de hijos de nodo.
4. Elicitación Dirigida: A diferencia de los métodos de aprendizaje activo que pueden solicitar órdenes topológicos completos o intervenciones amplias, este protocolo aísla únicamente las aristas no identificables y solicita la información específica necesaria para resolverlas.

Resultados Experimentales
El protocolo se evaluó en cuatro puntos de referencia estándar (Asia, Sachs, Child, Alarm) y datos sintéticos diseñados para poner a prueba niveles específicos.

• Rendimiento de Oráculo Ideal: Bajo el supuesto de un oráculo perfecto, el protocolo recuperó el DAG de verdad fundamental con Precisión = Recall = F1 = 1.000 en los cuatro puntos de referencia utilizando exactamente $1+K$ interacciones.
  • Alarm (V=37): 46 aristas recuperadas en 27 interacciones.
  • Sachs (V=11): 17 aristas recuperadas en 8 interacciones.
• Eficacia de la Cascada: En el conjunto de datos Sachs, la cascada por sí sola resolvió 5 de 19 aristas verdaderas solo con datos. La adición de los nuevos niveles seguros mejoró la precisión de la dirección del 61.5% (base L0-L2) al 66.7% cuando la guardia de desacuerdo estaba activa.
• Especificidad del Nivel: Las pruebas de estrés sintéticas confirmaron que cada nuevo nivel es positivo en precisión en su régimen nativo (por ejemplo, LLSNM en ruido de escala-localización, LIGCI en datos casi deterministas) y se abstiene (dispara 0/40) en datos fuera de régimen, evitando falsos positivos.
• Frente de Pareto: En Sachs, el protocolo demostró una compensación entre el recuento de consultas y la puntuación F1. Un enfoque "solo SEGURO" (cascada sin oráculo) logró F1=0.571 con 5 consultas, mientras que el protocolo completo logró F1=1.000 con 13 consultas (utilizando la cascada para reducir la carga del oráculo).

Significado y Afirmaciones
El artículo afirma abordar una brecha fundamental en el descubrimiento causal: la incapacidad de los métodos actuales para distinguir entre direcciones identificadas por datos y las impuestas algorítmicamente. Al adjuntar un "certificado" a cada arista, el protocolo proporciona un rastro de auditoría transparente.

• Contribución Teórica: El límite $1+K$ representa el contraparte del lado de la elicitación de los límites de presupuesto de intervención en el descubrimiento causal activo, cuantificando la información mínima requerida para resolver un DAG cuando está disponible el conocimiento experto.
• Utilidad Práctica: El protocolo permite a los profesionales centrar el esfuerzo del experto exclusivamente en las aristas no identificables, reduciendo la carga cognitiva al presentar preguntas específicas y conscientes del régimen en lugar de direcciones de aristas crudas.
• Limitaciones: Los autores señalan explícitamente que el alcance actual se restringe a variables continuas; las redes bayesianas discretas se tratan solo como una comprobación de robustez para la capa del oráculo. El protocolo asume un oráculo perfecto; el manejo de respuestas de expertos ruidosas o probabilísticas se identifica como trabajo futuro. Además, la fase de construcción del esqueleto impone un límite de recall, ya que las aristas podadas por la prueba HSIC inicial no pueden recuperarse.

El trabajo se posiciona no como un reemplazo para la optimización continua escalable o los métodos basados en restricciones, sino como un enfoque ortogonal que prioriza la auditabilidad por arista y minimiza el costo de la elicitación de expertos mediante consultas dirigidas y basadas en certificados.