Nonlinear Causal Discovery through a Sequential Edge Orientation Approach

Aquí presento un resumen técnico detallado del artículo "Causal Discovery by Sequential Edge Orientation" (Descubrimiento Causal mediante Orientación Secuencial de Aristas), escrito por Stella Huang y Qing Zhou.

1. El Problema

El descubrimiento causal busca inferir la estructura de un Grafo Acíclico Dirigido (DAG) que representa las relaciones causales entre un conjunto de variables a partir de datos observacionales.

• Limitaciones actuales: La mayoría de los métodos existentes asumen modelos lineales con ruido gaussiano, lo que solo permite identificar la clase de equivalencia de Markov (representada por un CPDAG) y no el DAG verdadero.
• Desafíos en modelos no lineales: Aunque se ha demostrado la identificabilidad de DAGs bajo Modelos de Ruido Aditivo (ANM) no lineales, los métodos actuales para aprenderlos sufren de:
  • Suposiciones restrictivas del modelo.
  • Dependencia excesiva de pruebas de independencia generalizadas (como las basadas en kernels), que son computacionalmente costosas ($O(n^2)$ o peor) y difíciles de ajustar.
  • Falta de escalabilidad para grafos grandes.
  • Sensibilidad a la especificación incorrecta del modelo (misspecification).

2. Metodología Propuesta: SNOE

Los autores proponen un nuevo algoritmo llamado SNOE (Sequential Nonlinear Orientation of Edges). En lugar de inferir un orden topológico global de los nodos, SNOE se enfoca en orientar secuencialmente las aristas no dirigidas de un CPDAG (o PDAG) estimado previamente.

Conceptos Clave

1. Modelo de Ruido Aditivo Pareado (PANM):

   • Es el núcleo teórico del método. Para una arista no dirigida $X - Y$ en un PDAG, el modelo PANM verifica si la relación causal puede identificarse condicionalmente a los conjuntos de padres ya identificados de $X$ y $Y$.
   • Si la orientación correcta es $X \to Y$, entonces $Y = f(X, Z_2) + \epsilon_Y$ donde $\epsilon_Y \perp \{X, Z_2\}$, y viceversa.
   • El teorema principal demuestra que, bajo un ANM restringido, siempre existe al menos una arista no dirigida en el CPDAG que satisface el PANM en cada iteración, permitiendo su orientación correcta sin propagar errores.

2. Procedimiento de Orientación Secuencial:

   • Ranking de Aristas: Se define una medida de dependencia (basada en la información mutua normalizada entre los residuos y los padres) para clasificar las aristas no dirigidas. Las aristas que cumplen con el PANM (residuos independientes de los padres) obtienen un puntaje de dependencia cero y se priorizan para su evaluación.
   • Prueba de Orientación (Likelihood Ratio Test): Una vez seleccionada una arista candidata, se realiza una prueba estadística basada en la razón de verosimilitud (likelihood ratio).
     • Se comparan dos modelos condicionales: $X \to Y$ vs. $Y \to X$.
     • Se utiliza una división de muestra (train-test split) para estimar los modelos (usando Modelos Aditivos Generalizados - GAM) y evaluar la verosimilitud en datos de prueba independientes.
     • La prueba determina si una dirección es estadísticamente superior a la otra, proporcionando una decisión definitiva sobre la dirección causal.

3. Reglas de Actualización:

   • Tras orientar una arista, se aplican las reglas de Meek y reglas específicas del algoritmo para orientar aristas adyacentes (por ejemplo, si $X \to Y$ y comparten un vecino $k$, se infiere $X \to k$ y $Y \to k$ bajo ciertas condiciones), reduciendo el conjunto de aristas no dirigidas restantes.

4. Poda de Aristas:

   • Una etapa final elimina aristas espurias mediante pruebas de significancia en los coeficientes de regresión, refinando la estructura final.

3. Contribuciones Clave

• Criterio PANM: Introducción de un criterio local basado en el Modelo de Ruido Aditivo Pareado para determinar la identificabilidad de aristas individuales en un PDAG, sin necesidad de evaluar todo el grafo simultáneamente.
• Algoritmo con Garantías Teóricas: Demostración de que el procedimiento de orientación secuencial recupera el DAG verdadero desde su CPDAG en el límite de gran muestra (consistencia estructural).
• Prueba de Razón de Verosimilitud Robusta: Desarrollo de una prueba estadística que compara direcciones causales competitivas, ofreciendo mayor robustez frente a la violación de suposiciones de ruido y menor costo computacional que las pruebas de independencia basadas en kernels.
• Eficiencia Computacional: El enfoque local evita la optimización global sobre todo el espacio de DAGs, logrando una complejidad mucho menor que los métodos basados en puntuación (score-based) o optimización continua.

4. Resultados Experimentales

Los autores evaluaron SNOE en datos sintéticos y del mundo real, comparándolo con métodos de vanguardia como CAM, NOTEARS, DAGMA, SCORE, kPC y RESIT.

• Precisión (F1 Score): SNOE superó consistentemente a los métodos competidores en todos los escenarios (funciones lineales, invertibles no lineales y no invertibles no lineales). En particular, mostró una mejora significativa (hasta un 100% en algunos casos) sobre NOTEARS y DAGMA en grafos no lineales.
• Robustez: El método mantuvo un alto rendimiento incluso cuando el ruido no era gaussiano (distribuciones t, Laplace, Gumbel) y bajo especificación incorrecta del modelo funcional.
• Velocidad: SNOE fue significativamente más rápido que los métodos competidores. Por ejemplo, en redes grandes, fue al menos 7.7 veces más rápido que los métodos basados en optimización continua, debido a su enfoque local y al uso de reglas gráficas para reducir el espacio de búsqueda.
• Datos Reales:
  • Citometría de Flujo (Sachs Network): SNOE logró el puntaje F1 más alto, recuperando la estructura causal con menos falsos positivos que otros métodos.
  • Pares Causa-Efecto (Tübingen): En un conjunto de 98 pares, la variante de validación cruzada (SNOE-CV) alcanzó una precisión del 66.3%, superando a la mayoría de los enfoques basados en entropía existentes.

5. Significado e Impacto

Este trabajo representa un avance significativo en el campo del descubrimiento causal no lineal al:

1. Resolver el problema de escalabilidad: Ofrece una alternativa viable a los métodos basados en kernels, que son prohibitivos para conjuntos de datos grandes.
2. Puente entre teoría y práctica: Conecta la teoría de identificabilidad (ANM) con un algoritmo práctico que no requiere suposiciones de linealidad ni ruido gaussiano, siendo robusto ante desviaciones del modelo.
3. Enfoque Local vs. Global: Cambia el paradigma de buscar un orden topológico global (que es difícil de estimar con ruido) a una orientación secuencial local basada en la independencia condicional de residuos, lo que resulta en una mayor estabilidad y precisión.

En resumen, SNOE proporciona una herramienta eficiente, teóricamente fundamentada y robusta para aprender estructuras causales complejas a partir de datos observacionales, superando las limitaciones de los métodos actuales en términos de precisión computacional y flexibilidad de modelo.