Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publicación Capítulo o parte de un libro (BookPart)

Interventional idlBNs in DAG-Space

  • Castelo Valdueza, Robert
Inclusion-driven structure learning of Bayesian networks, or idlBNs, converges to the generative structure as the sample size grows large and as long as that structure is an acyclic digraph (DAG) over the observed random variables. Because Markov equivalence of Bayesian networks organizes the search space of DAGs in equivalence classes, an obvious choice for such an approach is the greedy equivalence search (GES) algorithm, which carefully traverses the space of essential graphs, the canonical elements of those equivalence classes, following an inclusion path. GES is adapted to data produced by multiple intervention experiments in the greedy interventional equivalence search (GIES) algorithm. The algorithmic complexity of both GES and GIES is in the worst case exponential in the number of vertices, but it can be reduced to polynomial by bounding the vertex degree during the search, albeit at the cost of losing the large-sample optimality guarantee. Inclusion-driven structure learning can also be implemented in the search space of DAGs, as in the hill-climber Monte Carlo (HCMC) algorithm, whose stochastic nature confers the advantage of a polynomial-time bounded algorithmic complexity. Here, we introduce the interventional HCMC (iHCMC) algorithm, an inclusion-driven structure learning algorithm for interventional data in DAG-space. Using synthetic Gaussian data, we verify that iHCMC preserves the large-sample optimality for interventional data with polynomial-time complexity independent of the sparsity of the generative structure., This work was supported by the research project PID2019-105595GB-I00 funded by the MICIU/AEI/10.13039/501100011033. The author thanks the anonymous reviewers for useful comments and suggestions that have helped improve this chapter and the developers and contributors of the R package pcalg, which has greatly facilitated running the experimental simulations. The author also wishes to express his most sincere gratitude to Arno Siebes for his mentorship, guidance, and support throughout the pre-doctoral training and beyond.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Capítulo o parte de un libro (BookPart)

Interventional idlBNs in DAG-Space

  • Castelo Valdueza, Robert
Inclusion-driven structure learning of Bayesian networks, or idlBNs, converges to the generative structure as the sample size grows large and as long as that structure is an acyclic digraph (DAG) over the observed random variables. Because Markov equivalence of Bayesian networks organizes the search space of DAGs in equivalence classes, an obvious choice for such an approach is the greedy equivalence search (GES) algorithm, which carefully traverses the space of essential graphs, the canonical elements of those equivalence classes, following an inclusion path. GES is adapted to data produced by multiple intervention experiments in the greedy interventional equivalence search (GIES) algorithm. The algorithmic complexity of both GES and GIES is in the worst case exponential in the number of vertices, but it can be reduced to polynomial by bounding the vertex degree during the search, albeit at the cost of losing the large-sample optimality guarantee. Inclusion-driven structure learning can also be implemented in the search space of DAGs, as in the hill-climber Monte Carlo (HCMC) algorithm, whose stochastic nature confers the advantage of a polynomial-time bounded algorithmic complexity. Here, we introduce the interventional HCMC (iHCMC) algorithm, an inclusion-driven structure learning algorithm for interventional data in DAG-space. Using synthetic Gaussian data, we verify that iHCMC preserves the large-sample optimality for interventional data with polynomial-time complexity independent of the sparsity of the generative structure., This work was supported by the research project PID2019-105595GB-I00 funded by the MICIU/AEI/10.13039/501100011033. The author thanks the anonymous reviewers for useful comments and suggestions that have helped improve this chapter and the developers and contributors of the R package pcalg, which has greatly facilitated running the experimental simulations. The author also wishes to express his most sincere gratitude to Arno Siebes for his mentorship, guidance, and support throughout the pre-doctoral training and beyond.