Restricted Search Space Graph MCMC via Birth-Death Processes
Inferring a directed acyclic graph (DAG) from data is a computational challenge because graphs exist in a discrete search space that grows super-exponentially. To solve the scalability problem, recent MCMC-based graph inference methods restrict the search space to a subset of edges (where partial scores are computed), and then expand the space until a stopping criterion is met.
In this work, we estimate lower and upper bounds on the error introduced by restricted search space methods. Then, we propose a novel birth-death MCMC method defined by birth and death rates optimized for the error bounds, allowing the search space to expand or contract along the chain. In addition, we reduce computational costs compared to previous methods by using block-matrix operations in the expansion steps and memoization in the contraction steps.
We present extensive simulations characterizing the performance and efficiency of our algorithm, and consider applications in the field of imaging proteomics.
In this work, we estimate lower and upper bounds on the error introduced by restricted search space methods. Then, we propose a novel birth-death MCMC method defined by birth and death rates optimized for the error bounds, allowing the search space to expand or contract along the chain. In addition, we reduce computational costs compared to previous methods by using block-matrix operations in the expansion steps and memoization in the contraction steps.
We present extensive simulations characterizing the performance and efficiency of our algorithm, and consider applications in the field of imaging proteomics.
MCMC de graphes dans un espace de recherche restreint via des processus de naissance et de mort
L'inférence d'un graphe acyclique dirigé à partir de données est un défi informatique car les graphes existent dans un espace de recherche discret qui croît de manière super-exponentielle. Pour résoudre le problème de l'extensibilité, les méthodes récentes d'inférence de graphes par MCMC restreignent l'espace de recherche à un sous-ensemble d'arêtes (où des scores partiels sont calculés), puis étendent l'espace jusqu'à ce qu'un critère d'arrêt soit respecté.
Dans ce travail, nous estimons les limites inférieures et supérieures de l'erreur introduite par les méthodes d'espace de recherche restreint. Ensuite, nous proposons une nouvelle méthode MCMC naissance-mort définie par des taux de naissance et de mort optimisés pour les limites de l'erreur, ce qui permet à l'espace de recherche de s'étendre ou de se contracter tout au long de la chaîne. En outre, nous réduisons les coûts de calcul par rapport aux méthodes antérieures en utilisant des opérations de bloc-matrice dans les étapes d'expansion et la mémoïsation dans les étapes de contraction.
Nous présentons des simulations approfondies qui caractérisent les performances et l'efficacité de notre algorithme, et nous envisageons des applications dans le domaine de l'imagerie protéomique.
Dans ce travail, nous estimons les limites inférieures et supérieures de l'erreur introduite par les méthodes d'espace de recherche restreint. Ensuite, nous proposons une nouvelle méthode MCMC naissance-mort définie par des taux de naissance et de mort optimisés pour les limites de l'erreur, ce qui permet à l'espace de recherche de s'étendre ou de se contracter tout au long de la chaîne. En outre, nous réduisons les coûts de calcul par rapport aux méthodes antérieures en utilisant des opérations de bloc-matrice dans les étapes d'expansion et la mémoïsation dans les étapes de contraction.
Nous présentons des simulations approfondies qui caractérisent les performances et l'efficacité de notre algorithme, et nous envisageons des applications dans le domaine de l'imagerie protéomique.
Date and Time
-
Langue de la présentation orale
Anglais
Langue des supports visuels
Anglais