检索结果-内蒙古大学图书馆

A Fast pc algorithm for High Dimensional Causal Discovery with Multi-Core pcs

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2019年第5期16卷 1483-1495页

作者： Thuc Duy Le Hoang, Tao Li, Jiuyong Liu, Lin Liu, Huawen Hu, Shu Univ South Australia Sch Informat Technol & Math Sci Mawson Lakes SA 5095 Australia Zhejiang Normal Univ Dept Comp Sci Jinhua 321004 Zhejiang Peoples R China USTC Dept Comp Sci Hefei 230026 Anhui Peoples R China

Discovering causal relationships from observational data is a crucial problem and it has applications in many research areas. The pc algorithm is the state-of-the-art constraint based method for causal discovery. However, runtime of the pc algorithm, in the worst-case, is exponential to the number of nodes (variables), and thus it is inefficient when being applied to high dimensional data, e.g., gene expression datasets. On another note, the advancement of computer hardware in the last decade has resulted in the widespread availability of multi-core personal computers. There is a significant motivation for designing a parallelized pc algorithm that is suitable for personal computers and does not require end users' parallel computing knowledge beyond their competency in using the pc algorithm. In this paper, we develop parallel-pc, a fast and memory efficient pc algorithm using the parallel computing technique. We apply our method to a range of synthetic and real-world high dimensional datasets. Experimental results on a dataset from the DREAM 5 challenge show that the original pc algorithm could not produce any results after running more than 24 hours;meanwhile, our parallel-pc algorithm managed to finish within around 12 hours with a 4-core CPU computer, and less than six hours with a 8-core CPU computer. Furthermore, we integrate parallel-pc into a causal inference method for inferring miRNA-mRNA regulatory relationships. The experimental results show that parallel-pc helps improve both the efficiency and accuracy of the causal inference algorithm.

关键词： algorithm design and analysis Gene expression Inference algorithms Microcomputers Parallel processing Runtime Causal discovery gene expression data high dimensional data miRNA targets parallel computing pc algorithm

来源：评论

学校读者我要写书评

暂无评论

Automated hyperparameter selection for the pc algorithm

引用

PATTERN RECOGNITION LETTERS 2021年 151卷 288-293页

作者： V. Strobl, Eric Davidson County Tennessee United States

The pc algorithm infers causal relations using conditional independence tests that require a pre-specified Type I alpha level. pc is however unsupervised, so we cannot tune alpha using traditional cross-validation. We therefore propose Autopc, a fast procedure that optimizes alpha directly for a user chosen metric. We in particular force pc to double check its output by executing a second run on the recovered graph. We choose the final output as the one which maximizes stability between the two runs. Autopc consistently outperforms the state of the art across multiple metrics. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Causal discovery Hyperparameter pc algorithm

来源：评论

学校读者我要写书评

暂无评论

cupc: CUDA-Based Parallel pc algorithm for Causal Structure Learning on GPU

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2020年第3期31卷 530-542页

作者： Zarebavani, Behrooz Jafarinejad, Foad Hashemi, Matin Salehkaleybar, Saber Sharif Univ Technol Learning & Intelligent Syst Lab Dept Elect Engn Tehran *** Iran

The main goal in many fields in the empirical sciences is to discover causal relationships among a set of variables from observational data. pc algorithm is one of the promising solutions to learn underlying causal structure by performing a number of conditional independence tests. In this paper, we propose a novel GPU-based parallel algorithm, called cupc, to execute an order-independent version of pc. The proposed solution has two variants, cupc-E and cupc-S, which parallelize pc in two different ways for multivariate normal distribution. Experimental results show the scalability of the proposed algorithms with respect to the number of variables, the number of samples, and different graph densities. For instance, in one of the most challenging datasets, the runtime is reduced from more than 11 hours to about 4 seconds. On average, cupc-E and cupc-S achieve 500X and 1300X speedup, respectively, compared to serial implementation on CPU.

关键词： Bayesian networks causal discovery CUDA GPU machine learning parallel processing pc algorithm

来源：评论

学校读者我要写书评

暂无评论

Controlling the False Discovery Rate of the Association/Causality Structure Learned with the pc algorithm

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2009年第2期10卷 475-514页

作者： Li, Junning Wang, Z. Jane Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

In real world applications, graphical statistical models are not only a tool for operations such as classification or prediction, but usually the network structures of the models themselves are also of great interest (e.g., in modeling brain connectivity). The false discovery rate (FDR), the expected ratio of falsely claimed connections to all those claimed, is often a reasonable error-rate criterion in these applications. However, current learning algorithms for graphical models have not been adequately adapted to the concerns of the FDR. The traditional practice of controlling the type I error rate and the type II error rate under a conventional level does not necessarily keep the FDR low, especially in the case of sparse networks. In this paper, we propose embedding an FDR-control procedure into the pc algorithm to curb the FDR of the skeleton of the learned graph. We prove that the proposed method can control the FDR under a user-specified level at the limit of large sample sizes. In the cases of moderate sample size (about several hundred), empirical experiments show that the method is still able to control the FDR under the user-specified level, and a heuristic modification of the method is able to control the FDR more accurately around the user-specified level. The proposed method is applicable to any models for which statistical tests of conditional independence are available, such as discrete models and Gaussian models.

关键词： Bayesian networks false discovery rate pc algorithm directed acyclic graph skeleton

来源：评论

学校读者我要写书评

暂无评论

Estimating and Controlling the False Discovery Rate of the pc algorithm Using Edge-specific P-Values

引用

ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY 2019年第5期10卷 1-37页

作者： Strobl, Eric, V Spirtes, Peter L. Visweswaran, Shyam Vanderbilt Univ Dept Psychiat & Behav Sci Med Ctr 1601 23rd Ave S Nashville TN 37212 USA Carnegie Mellon Univ Dept Philosophy 5000 Forbes Ave Baker Hall 161 Pittsburgh PA 15213 USA Univ Pittsburgh Dept Biomed Informat 5607 Baum Blvd Pittsburgh PA 15206 USA

Many causal discovery algorithms infer graphical structure from observational data. The pc algorithm in particular estimates a completed partially directed acyclic graph (CPDAG), or an acyclic graph containing directed edges identifiable with conditional independence testing. However, few groups have investigated strategies for estimating and controlling the false discovery rate (FDR) of the edges in the CPDAG. In this article, we introduce pc with p-values (pc-p), a fast algorithm that robustly computes edge-specific p-values and then estimates and controls the FDR across the edges. pc-p specifically uses the p-values returned by many conditional independence (CI) tests to upper bound the p-values of more complex edge-specific hypothesis tests. The algorithm then estimates and controls the FDR using the bounded p-values and the Benjamini-Yekutieli FDR procedure. Modifications to the original pc algorithm also help pc-p accurately compute the upper bounds despite non-zero Type II error rates. Experiments show that pc-p yields more accurate FDR estimation and control across the edges in a variety of CPDAGs compared to alternative methods.

关键词： pc algorithm causal inference false discovery rate Bayesian network directed acyclic graph

来源：评论

学校读者我要写书评

暂无评论

Inferring functional connectivity in MRI using Bayesian network structure learning with a modified pc algorithm

引用

NEUROIMAGE 2013年 75卷 165-175页

作者： Iyer, Swathi P. Shafran, Izhak Grayson, David Gates, Kathleen Nigg, Joel T. Fair, Damien A. Oregon Hlth & Sci Univ Dept Behav Neurosci Portland OR 97239 USA Oregon Hlth & Sci Univ Dept Psychiat Portland OR 97239 USA Oregon Hlth & Sci Univ Adv Imaging Res Ctr Portland OR 97239 USA Oregon Hlth & Sci Univ Dept Biomed Engn Portland OR 97239 USA Univ Calif Davis Ctr Neurosci Davis CA 95616 USA Virginia Polytech Inst & State Univ Dept Psychol Blacksburg VA 24061 USA Virginia Polytech Inst & State Univ Arlington Innovat Ctr Blacksburg VA 24061 USA

Resting state functional connectivity MRI (rs-fcMRI) is a popular technique used to gauge the functional relatedness between regions in the brain for typical and special populations. Most of the work to date determines this relationship by using Pearson's correlation on BOLD fMRI timeseries. However, it has been recognized that there are at least two key limitations to this method. First, it is not possible to resolve the direct and indirect connections/influences. Second, the direction of information flow between the regions cannot be differentiated. In the current paper, we follow-up on recent work by Smith et al. (2011), and apply pc algorithm to both simulated data and empirical data to determine whether these two factors can be discerned with group average, as opposed to single subject, functional connectivity data. When applied on simulated individual subjects, the algorithm performs well determining indirect and direct connection but fails in determining directionality. However, when applied at group level, pc algorithm gives strong results for both indirect and direct connections and the direction of information flow. Applying the algorithm on empirical data, using a diffusion-weighted imaging (DWI) structural connectivity matrix as the baseline, the pc algorithm outperformed the direct correlations. We conclude that, under certain conditions, the pc algorithm leads to an improved estimate of brain network structure compared to the traditional connectivity analysis based on correlations. (C) 2013 Elsevier Inc. All rights reserved.

关键词： fMRI Bayesian network pc algorithm Directed functional connectivity Effective connectivity

来源：评论

学校读者我要写书评

暂无评论

The Dual pc algorithm for Structure Learning 11

The Dual PC Algorithm for Structure Learning

引用

International Conference on Probabilistic Graphical Models

作者： Giudice, Enrico Kuipers, Jack Moffa, Giusi Univ Basel Dep Math & Comp Sci Basel Switzerland Swiss Fed Inst Technol Dep Biosyst Sci & Engn Basel Switzerland UCL Div Psychiat London England

Learning the graphical structure of Bayesian networks is key to describing data generating mechanisms in many complex applications and it poses considerable computational challenges. Observational data can only identify the equivalence class of the directed acyclic graph underlying a Bayesian network model, and a variety of methods exist to tackle the problem. Under certain assumptions, the popular pc algorithm can consistently recover the correct equivalence class by reverse-engineering the conditional independence (CI) relationships holding in the variable distribution. Here, we propose the dual pc algorithm, a novel scheme to carry out the CI tests within the pc algorithm by leveraging the inverse relationship between covariance and precision matrices. By exploiting block matrix inversions we can efficiently supplement partial correlation tests at each step with those of complementary (or dual) conditioning sets. The multiple CI tests of the dual pc algorithm proceed by first considering marginal and full-order CI relationships and progressively moving to central-order ones. Simulation studies show that the dual pc algorithm outperforms the classic pc algorithm both in terms of run time and in recovering the underlying network structure, even in the presence of deviations from Gaussianity.

关键词： Bayesian Networks Graphical Models Directed Acyclic Graphs Structure Learning pc algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallelisation of the pc algorithm 16th

Parallelisation of the PC Algorithm

引用

16th Conference of the Spanish-Association-for-Artificial-Intelligence (CAEPIA)

作者： Madsen, Anders L. Jensen, Frank Salmeron, Antonio Langseth, Helge Nielsen, Thomas D. HUGIN EXPERT AS Aalborg Denmark Aalborg Univ Dept Comp Sci Aalborg Denmark Univ Almeria Dept Math Almeria Spain Norwegian Univ Sci & Technol Dept Comp & Informat Sci N-7034 Trondheim Norway

ISBN: (纸本)9783319245980;9783319245973

This paper describes a parallel version of the pc algorithm for learning the structure of a Bayesian network from data. The pc algorithm is a constraint-based algorithm consisting of five steps where the first step is to perform a set of (conditional) independence tests while the remaining four steps relate to identifying the structure of the Bayesian network using the results of the (conditional) independence tests. In this paper, we describe a new approach to parallelisation of the (conditional) independence testing as experiments illustrate that this is by far the most time consuming step. The proposed parallel pc algorithm is evaluated on data sets generated at random from five different real-world Bayesian networks. The results demonstrate that significant time performance improvements are possible using the proposed algorithm.

关键词： Bayesian network pc algorithm Parallelisation

来源：评论

学校读者我要写书评

暂无评论

A Study on Causal Rule Discovery with pc algorithm

A Study on Causal Rule Discovery with PC Algorithm

引用

International Conference on Infocom Technologies and Unmanned Systems (Trends and Future Directions) (ICTUS)

作者： Rama, B. Praveen, P. Sinha, Harshit Choudhury, Tanupriya Kakatiya Univ Univ Coll Dept Comp Sci Warangal Telangana India Amity Univ Comp Sci & Engn Noida India

ISBN: (纸本)9781538605141

Guarantee of the mining of the data of extricating unforeseen information from unpleasantly huge databases. Ways are created to make link comments since gigantic data sets. These demonstrate the quality of relationship of two or a more data attributes. From numerous points of view, the enthusiasm for association decides is that they give the guarantee (or hallucination) of causative, or at least, prophetic connections. Regardless of whether it is frequently same that any association rules straight out a causative relationship must be inspected. The term causality is assuming on basic part in basic essential by giving a premise to picking what is probably going to head a coveted outcome.

关键词： Association rule decision-making causality DAG pc algorithm

来源：评论

学校读者我要写书评

暂无评论

On Using the pc algorithm for Learning Continuous Bayesian Networks: An Experimental Analysis

On Using the PC Algorithm for Learning Continuous Bayesian N...

引用

15th Conference of the Spanish-Association-for-Artificial-Intelligence (CAEPIA)

作者： Fernandez, Antonio Perez-Bernabe, Inmaculada Salmeron, Antonio Univ Almeria Dept Math E-04120 Almeria Spain

ISBN: (纸本)9783642406423;9783642406430

Mixtures of truncated basis functions (MoTBFs) have been recently proposed as a generalisation of mixtures of truncated exponentials and mixtures of polynomials for modelling conditional distributions in hybrid Bayesian networks. However, no structural learning algorithm has been proposed so far for such models. In this paper we investigate the use of the pc algorithm as a means of obtaining the underlying network structure, that is finally completed by plugging in the conditional MoTBF densities. We show through a set of experiments that the approach is valid and competitive with current alternatives of discretizing the variables or adopting a Gaussian assumption. We restrict the scope of this work to continuous variables.

关键词： continuous Bayesian networks pc algorithm mixtures of truncated basis functions structural learning

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：