Resumen Técnico: Recuperación del Grafo Moral de Distribuciones de Probabilidad Discretas mediante Redes de Tensores

1. Planteamiento del Problema

El artículo aborda el problema del aprendizaje de la estructura causal para sistemas de variables aleatorias discretas. Específicamente, el objetivo es recuperar el grafo moral de un Grafo Acíclico Dirigido (DAG) desconocido únicamente a partir de datos observacionales (una distribución de probabilidad conjunta $p$).

El grafo moral es un grafo no dirigido donde existe una arista entre dos variables si estas comparten un vínculo causal directo o son co-padres en una estructura $v$ (v-structure). El grafo moral es un invariante fundamental de la clase de equivalencia de Markov de un DAG y puede identificarse a partir de datos puramente observacionales sin necesidad de intervenciones. Los métodos existentes suelen caer en dos categorías principales:

• Métodos basados en restricciones (p. ej., algoritmo PC): Dependen de pruebas de independencia condicional (CI), las cuales sufren de degradación por muestras finitas y una detección débil de dependencias.
• Métodos basados en puntuación (p. ej., GES, NOTEARS): Reformulan el aprendizaje como una optimización continua sobre DAGs, pero enfrentan espacios de búsqueda combinatorios y requieren restricciones de acyclicidad.

Este trabajo propone un enfoque fundamentalmente distinto que evita las pruebas de CI discretas y la búsqueda en el espacio de los DAGs mediante la descomposición de la distribución de probabilidad en una Red de Tensores Completamente Conectada (FCTN).

2. Metodología

2.1 Ansatz de la Red de Tensores

El método representa la distribución conjunta $p(V_1, \dots, V_m)$ como una contracción de una red de tensores completamente conectada. La red consiste en:

• Tensores Locales ($N^{[i]}$): Asociados con cada variable $V_i$.
• Matrices de Enlace ($B_{ij}$): Conectan cada par de sitios $\{i, j\}$.

Crucialmente, cada matriz de enlace está parametrizada como una línea base más una corrección de bajo rango:
$$B_{ij} = J_{ij} + C_{ij} = J_{ij} + U_{ij}V_{ij}^\top$$
donde $J_{ij}$ es una matriz de unos fijos (que representa la línea base desconectada donde los sitios son independientes) y $C_{ij}$ es una matriz de corrección de bajo rango. Los factores $U_{ij}$ y $V_{ij}$ son parámetros entrenables.

2.2 Función Objetivo y Regularización

El objetivo de aprendizaje minimiza el error de reconstrucción entre la distribución real $p$ y la aproximación de la red de tensores $TN(\theta)$, regularizada por una penalización de norma nuclear sobre las correcciones:
$$J(\theta) = \|p - TN(\theta)\|_2^2 + \frac{\beta}{2} \sum_{\{V_i, V_j\}} (\|U_{ij}\|_F^2 + \|V_{ij}\|_F^2)$$
El término de penalización implementa la norma nuclear $\|C_{ij}\|_*$ mediante la identidad variacional $\|C_{ij}\|_* = \min_{C=UV^\top} \frac{1}{2}(\|U\|_F^2 + \|V\|_F^2)$. Esta penalización continua y diferenciable impulsa las correcciones de enlace innecesarias hacia cero.

2.3 Recuperación del Grafo Efectivo

El grafo efectivo $G_{eff}$ se define como el conjunto de aristas donde la matriz de corrección tiene una norma nuclear no nula (o un rango efectivo $>0$):
$$G_{eff} = \{ \{V_i, V_j\} : \|C_{ij}\|_* > 0 \}$$
El método postula que el optimizador eliminará naturalmente las aristas no morales (estableciendo $C_{ij} = J_{ij}$) mientras retiene las aristas morales, permitiendo que la estructura del grafo emerja directamente de los parámetros optimizados.

3. Marco Teórico y Contribuciones Clave

El artículo proporciona garantías teóricas rigurosas para la recuperación exacta y aproximada bajo supuestos específicos: Fidelidad (Faithfulness), Positividad y un supuesto de No Re-enrutamiento Implícito.

3.1 Mecanismo Central: Costo de Re-enrutamiento

Un lema central (Lema 11) establece que re-enrutar una correlación a través de un nodo intermedio es estrictamente más costoso que representarla directamente.

• Si existe una dependencia entre $V_i$ y $V_j$, representar esto mediante un enlace directo $C_{ij}$ es óptimo.
• Si el enlace directo se elimina, la dependencia debe ser "re-enrutada" a través de otros nodos (p. ej., $V_i \to V_\omega \to V_j$). Esto requiere matrices de paso de identidad que aumentan la penalización de la norma de Frobenius por el rango de la corrección ($K_{ij}$).
• En consecuencia, el optimizador prefiere enlaces directos para dependencias condicionales genuinas.

3.2 Recuperación Exacta (Error Cero)

El Teorema 16 establece que bajo fidelidad, positividad y el supuesto de no re-enrutamiento implícito, cada FCTN óptimo con error de reconstrucción cero ($\varepsilon = 0$) tiene un grafo efectivo exactamente igual al grafo moral.

• Cota Inferior (Teorema 13): Las aristas morales deben tener correcciones no nulas. Si una arista moral fuera cero, la dependencia tendría que ser re-enrutada, incurriendo en una penalización mayor, lo que contradice la optimalidad.
• Cota Superior (Teorema 15): Las aristas no morales deben tener correcciones de cero. Las aristas no morales portan cero información mutua condicional (CMI). Cualquier corrección no nula en tal arista sería un artefacto nulo, un re-enrutamiento explícito (subóptimo) o un re-enrutamiento implícito (descartado por el Supuesto 3).

3.3 Recuperación Aproximada (Error No Nulo)

Para el régimen donde el error de reconstrucción $\varepsilon > 0$, el artículo deriva cotas de recuperación explícitas utilizando la continuidad de Fannes–Audenaert de la información mutua condicional.

• Teorema 18: Si el error de reconstrucción es suficientemente pequeño de modo que la cota de continuidad $f(\varepsilon)$ sea menor que la información mutua condicional mínima de las verdaderas aristas morales ($\delta_{min}$), el grafo efectivo contiene todas las aristas morales.
• Las aristas espurias (no morales) con correcciones no nulas están acotadas por $f(\varepsilon)$, lo que permite su eliminación mediante umbralización.

4. Resultados Experimentales

Los autores validaron el método en cuatro distribuciones discretas sintéticas generadas a partir de DAGs causales conocidos:

1. Cadena (Chain): $X \to Z \to Y$
2. Horquilla (Fork): $Z \to X, Z \to Y$
3. Colisionador (Collider): $X \to Z \leftarrow Y$
4. Diamante (Diamond): Una combinación de una estructura $v$ y una cadena.

Hallazgos:

• En los cuatro casos, el grafo efectivo basado en el rango extraído de las matrices de enlace optimizadas coincidió exactamente con el grafo moral real.
• El método identificó con éxito la arista moral entre los co-padres en las estructuras de colisionador y diamante.
• Un diagnóstico de Información Mutua Condicional (CMI) post-hoc sobre la distribución reconstruida fue menos robusto cuando el error de reconstrucción era alto, confirmando la necesidad teórica del criterio basado en el rango sobre la simple umbralización de CMI en el régimen aproximado.

5. Significado y Reivindicaciones

El artículo afirma la siguiente significancia:

• Unicidad de la Solución: A diferencia de muchos resultados de aprendizaje de estructura que prueban la existencia, este trabajo demuestra un enunciado de unicidad: cada solución de error cero con error cero produce el grafo moral correcto, no solo algunas.
• Relajación Continua del Aprendizaje de Estructura: Reemplaza las pruebas de CI discretas con una función objetivo continua y diferenciable, aprovechando la geometría de las redes de tensores.
• Rigor Teórico: Proporciona cotas explícitas para la recuperación aproximada, vinculando el error de reconstrucción directamente con las garantías de recuperación de grafos mediante la continuidad de la teoría de la información.
• Novedad en el Descubrimiento Causal: Es la primera aplicación de correcciones de enlace regularizadas por norma nuclear en redes de tensores específicamente para la recuperación del grafo moral de DAGs causales, distinguiéndose de las aplicaciones estándar de redes de tensores en física o compresión.

6. Limitaciones

Los autores reconocen varias limitaciones:

• Supuesto de No Re-enrutamiento Implícito: Las garantías teóricas dependen del supuesto de que los tensores locales no pueden computar internamente dependencias multivariables para sustituir los enlaces directos. Aunque se cumple empíricamente en los experimentos (donde las dimensiones de enlace eran menores que los espacios de estado), se deja como trabajo futuro una prueba estructural formal.
• No Convexidad: La función objetivo es no convexa, lo que significa que la optimalidad global no está garantizada por el descenso de gradiente, aunque la naturaleza discreta del grafo efectivo hace que la solución sea robusta a pequeñas perturbaciones.
• Escalabilidad: La Red de Tensores Completamente Conectada tiene un ancho de árbol (treewidth) de $m-1$, lo que conduce a costos de contracción exponenciales $O(d^m r^{m-1})$. Esto limita el método a un número pequeño de variables ($m \lesssim 10$) en hardware convencional. Los autores sugieren estrategias de contracción aproximada (p. ej., truncamiento, renormalización) como un camino a seguir para sistemas más grandes.
• Orientación Causal: El método recupera el grafo moral no dirigido. Orientar las aristas para recuperar el DAG completo requiere información adicional (intervenciones) o reglas de orientación separadas.