Dagor: aprendizaje de DAGs a través de ordenamientos topológicos y factorización QR
Autores: Zuo, Hao; Jiang, Jinshen; Zhou, Yun
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Dagor: aprendizaje de DAGs a través de ordenamientos topológicos y factorización QR
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Adquisición de grafos acíclicos dirigidos causales
Optimización continua
Aprendizaje de DAGs
Problema NP-duro
Clasificaciones topológicas de grafos
Caracterización de aciclicidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 23
Citaciones: Sin citaciones
Recientemente, la tarea de adquirir grafos acíclicos dirigidos causales (DAGs) a partir de datos empíricos ha sido modelada como un proceso iterativo dentro del marco de optimización continua con una caracterización de aciclicidad diferenciable. Sin embargo, aprender DAGs a partir de datos es un problema NP-duro ya que el espacio DAG aumenta de forma superexponencial con el número de variables. En este trabajo, introducimos los ordenamientos topológicos de grafos en la resolución del problema de optimización continua, que es sustancialmente más pequeño que el espacio DAG y beneficioso para evitar óptimos locales. Además, el espacio de ordenamientos topológicos no requiere consideración de aciclicidad, lo que puede reducir significativamente el costo computacional. Para tratar aún más las asimetrías inherentes de los DAGs, investigamos la caracterización de aciclicidad y proponemos una nueva estrategia de optimización de aprendizaje de DAGs basada en la factorización QR, llamada DAGOR. Primero, utilizando la transformación congruente de matrices, la matriz de adyacencia del DAG se transforma en una matriz triangular superior con un ordenamiento topológico. Luego, utilizando la factorización QR como base, construimos una función de penalización de mínimos cuadrados como restricciones para la optimización en el marco del autoencoder de grafos. Se realizan experimentos numéricos para validar aún más nuestros resultados teóricos y demostrar el rendimiento competitivo de nuestro método.
Descripción
Recientemente, la tarea de adquirir grafos acíclicos dirigidos causales (DAGs) a partir de datos empíricos ha sido modelada como un proceso iterativo dentro del marco de optimización continua con una caracterización de aciclicidad diferenciable. Sin embargo, aprender DAGs a partir de datos es un problema NP-duro ya que el espacio DAG aumenta de forma superexponencial con el número de variables. En este trabajo, introducimos los ordenamientos topológicos de grafos en la resolución del problema de optimización continua, que es sustancialmente más pequeño que el espacio DAG y beneficioso para evitar óptimos locales. Además, el espacio de ordenamientos topológicos no requiere consideración de aciclicidad, lo que puede reducir significativamente el costo computacional. Para tratar aún más las asimetrías inherentes de los DAGs, investigamos la caracterización de aciclicidad y proponemos una nueva estrategia de optimización de aprendizaje de DAGs basada en la factorización QR, llamada DAGOR. Primero, utilizando la transformación congruente de matrices, la matriz de adyacencia del DAG se transforma en una matriz triangular superior con un ordenamiento topológico. Luego, utilizando la factorización QR como base, construimos una función de penalización de mínimos cuadrados como restricciones para la optimización en el marco del autoencoder de grafos. Se realizan experimentos numéricos para validar aún más nuestros resultados teóricos y demostrar el rendimiento competitivo de nuestro método.