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

A novel chow-liu algorithm and its application to gene differential analysis

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2017年 80卷 1-18页

作者： Suzuki, Joe Osaka Univ Dept Math Suita Osaka 565 Japan

This paper proposes an estimator of mutual information for both discrete and continuous variables and applies it to the chow-liu algorithm to find a forest that expresses probabilistic relations among them. The state-of-the-art assumes that the continuous variables are Gaussian and that the graphical model under discrete and continuous variables is ANOVA. Consequently, it is difficult to obtain the maximum likelihood of three connected variables such that the center is Gaussian and the other two are discrete, and thus, the state-of-the-art restricts the class to the forest such that there is no Gaussian node between discrete variables. The proposed method executes in a general setting without any assumptions, preparing several meshes, computing the mutual information values, and selecting the maximum value. We prove that the number of meshes to be prepared is at most 0 (log(2) n) and that the estimated mutual information is no larger than zero if and only if the variables are independent for large n. Finally, we apply the proposed method to the problems of gene differential analysis and relation discovery between gene expression and SNP5 (single nucleotide polymorphisms). In particular, for the latter experiment, we demonstrate that the proposed method successfully captures the relation among them but that the state-of-the-art fails because of the merits and demerits of the proposed and existing methods. (C) 2016 Published by Elsevier Inc.

关键词： Mutual information chow-liu algorithm Forest graphical model Gene differential analysis ANOVA

来源：评论

学校读者我要写书评

暂无评论

Beyond Maximum Likelihood: Boosting the chow-liu algorithm for Large Alphabets 50

Beyond Maximum Likelihood: Boosting the Chow-Liu Algorithm f...

引用

50th Asilomar Conference on Signals, Systems and Computers (ASILOMARSSC)

作者： Jiao, Jiantao Han, Yanjun Weissman, Tsachy Stanford Univ EE Dept Stanford CA 94305 USA

ISBN: (纸本)9781538639542

We show that in high dimensional distributions, i.e., the regime where the alphabet size of each node is comparable to the number of observations, the chow-liu algorithm on learning graphical models is highly sub-optimal. We propose a new approach, where the key ingredient is to replace the empirical mutual information in the chow-liu algorithm with a minimax rate-optimal estimator proposed recently by Jiao, Venkat, Han, and Weissman [1]. We demonstrate the improved performance of the new approach in two problems: learning tree graphical models and Bayesian network classification.

关键词： chow-liu algorithm mutual information estimation approximation theory high dimensional statistics nonsmooth functional estimation

来源：评论

学校读者我要写书评

暂无评论

Learning of Tree-Structured Gaussian Graphical Models on Distributed Data Under Communication Constraints

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2019年第1期67卷 17-28页

作者： Tavassolipour, Mostafa Motahari, Seyed Abolfazl Shalmani, Mohammad-Taghi Manzuri Sharif Univ Technol Dept Comp Engn Tehran *** Iran

In this paper, learning of tree-structured Gaussian graphical models from distributed data is addressed. In our model, samples are stored in a set of distributed machines where each machine has access to only a subset of features. A central machine is then responsible for learning the structure based on received messages from the other nodes. We present a set of communication-efficient strategies, which are theoretically proved to convey sufficient information for reliable learning of the structure. In particular, our analyses show that even if each machine sends only the signs of its local data samples to the central node, the tree structure can still be recovered with high accuracy. Our simulation results on both synthetic and real-world datasets show that our strategies achieve a desired accuracy in inferring the underlying structure while spending a small budget on communication.

关键词： Structure learning chow-liu algorithm Gaussian graphical model

来源：评论

学校读者我要写书评

暂无评论

Minimax Estimation of Functionals of Discrete Distributions

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第5期61卷 2835-2885页

作者： Jiao, Jiantao Venkat, Kartik Han, Yanjun Weissman, Tsachy Stanford Univ Dept Elect Engn Stanford CA 94305 USA Tsinghua Univ Dept Elect Engn Beijing 100084 Peoples R China

We propose a general methodology for the construction and analysis of essentially minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the support size S is unknown and may be comparable with or even much larger than the number of observations n. We treat the respective regions where the functional is nonsmooth and smooth separately. In the nonsmooth regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the smooth regime, we apply a bias-corrected version of the maximum likelihood estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing the performance of the resulting schemes for estimating two important information measures: 1) the entropy H(P) = Sigma(S)(i=1)-p(i) ln p(i) and 2) F-alpha(P) = Sigma(S)(i=1) p(i)(alpha), alpha > 0. We obtain the minimax L-2 rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity n similar to S/ln S for entropy estimation. We also demonstrate that the sample complexity for estimating F-alpha(P), 0 < alpha < 1, is n similar to S-1/alpha/ln S, which can be achieved by our estimator but not the MLE. For 1 < alpha < 3/2, we show the minimax L-2 rate for estimating F-alpha(P) is (n ln n)(-2(alpha-1)) for infinite support size, while the maximum L-2 rate for the MLE is n(-2(alpha-1)). For all the above cases, the behavior of the minimax rate-optimal estimators with n samples is essentially that of the MLE (plug-in rule) with n ln n samples, which we term "effective sample size enlargement." We highlight the practical advantages of our schemes for the estimation of entropy and mutual information. We compare our performance with various existing approaches, and demonstrate that our approach reduces running time and boosts the accuracy. Moreover, we show that the minimax rate-optimal mutual information est

关键词： Mean squared error entropy estimation nonsmooth functional estimation maximum likelihood estimator approximation theory minimax lower bound polynomial approximation minimax-optimality high dimensional statistics Renyi entropy chow-liu algorithm

来源：评论

学校读者我要写书评

暂无评论

Predictive Learning on Hidden Tree-Structured Ising Models

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2021年第1期22卷 1-82页

作者： Nikolakakis, Konstantinos E. Kalogerias, Dionysios S. Sarwate, Anand D. Rutgers State Univ Dept Elect & Comp Engn 94 Brett Rd Piscataway NJ 08854 USA Michigan State Univ Dept Elect & Comp Engn 428 S Shaw Lane E Lansing MI 48824 USA

We provide high-probability sample complexity guarantees for exact structure recovery and accurate predictive learning using noise-corrupted samples from an acyclic (tree-shaped) graphical model. The hidden variables follow a tree-structured Ising model distribution, whereas the observable variables are generated by a binary symmetric channel taking the hidden variables as its input (flipping each bit independently with some constant probability q is an element of [0, 1/2)). In the absence of noise, predictive learning on Ising models was recently studied by Bresler and Karzand (2020);this paper quantifies how noise in the hidden model impacts the tasks of structure recovery and marginal distribution estimation by proving upper and lower bounds on the sample complexity. Our results generalize state-of-the-art bounds reported in prior work, and they exactly recover the noiseless case (q = 0). In fact, for any tree with p vertices and probability of incorrect recovery delta > 0, the sufficient number of samples remains logarithmic as in the noiseless case, i.e., O(log(p/(delta)), while the dependence on q is O(1/(1 - 2q)(4)), for both aforementioned tasks. We also present a new equivalent of Isserlis' Theorem for sign-valued tree-structured distributions, yielding a new low-complexity algorithm for higher-order moment estimation.

关键词： Ising Model chow-liu algorithm Structure Learning Predictive Learning Distribution Estimation Noisy Data Hidden Markov Random Fields

来源：评论

学校读者我要写书评

暂无评论

Information enhanced model selection for Gaussian graphical model with application to metabolomic data

引用

BIOSTATISTICS 2021年第3期23卷 926-948页

作者： Zhou, Jie Hoen, Anne G. Mcritchie, Susan Pathmasiri, Wimal Viles, Weston D. Nguyen, Quang P. Madan, Juliette C. Dade, Erika Karagas, Margaret R. Gui, Jiang Dartmouth Coll Geisel Sch Med Dept Biomed Data Sci 3 Rope Ferry Rd Hanover NH 03755 USA Dartmouth Coll Geisel Sch Med Dept Epidemiol 3 Rope Ferry Rd Hanover NH 03755 USA Univ North Carolina Chapel Hill Nutr Res Inst Dept Nutr Sch Publ Hlth 500 Laureate Way Kannapolis NC 28081 USA Univ Southern Maine Dept Math & Stat 96 Falmouth St Portland ME 04103 USA

In light of the low signal-to-noise nature of many large biological data sets, we propose a novel method to learn the structure of association networks using Gaussian graphical models combined with prior knowledge. Our strategy includes two parts. In the first part, we propose a model selection criterion called structural Bayesian information criterion, in which the prior structure is modeled and incorporated into Bayesian information criterion. It is shown that the popular extended Bayesian information criterion is a special case of structural Bayesian information criterion. In the second part, we propose a two-step algorithm to construct the candidate model pool. The algorithm is data-driven and the prior structure is embedded into the candidate model automatically. Theoretical investigation shows that under some mild conditions structural Bayesian information criterion is a consistent model selection criterion for high-dimensional Gaussian graphical model. Simulation studies validate the superiority of the proposed algorithm over the existing ones and show the robustness to the model misspecification. Application to relative concentration data from infant feces collected from subjects enrolled in a large molecular epidemiological cohort study validates that metabolic pathway involvement is a statistically significant factor for the conditional dependence between metabolites. Furthermore, new relationships among metabolites are discovered which can not be identified by the conventional methods of pathway analysis. Some of them have been widely recognized in biological literature.

关键词： chow-liu algorithm Metabolite pathway analysis Model pool Prior structure Structural BIC Structure learning algorithm Two-step algorithm Undirected Gaussian graphical model

来源：评论

学校读者我要写书评

暂无评论

Modelling the dependence structure of Y-STR haplotypes using graphical models

引用

FORENSIC SCIENCE INTERNATIONAL-GENETICS 2018年 37卷 29-36页

作者： Andersen, Mikkel Meyer Curran, James de Zoete, Jacob Taylor, Duncan Buckleton, John Aalborg Univ Dept Math Sci Skjernvej 4A DK-9220 Aalborg Denmark Univ Auckland Dept Stat PB 92019 Auckland New Zealand Queen Mary Univ London Sch Elect Engn & Comp Sci 10 Godward Sq London E1 4FZ England Flinders Univ S Australia Sch Biol Sci GPO Box 2100 Adelaide SA 5001 Australia ESR hPB 92021 Auckland New Zealand

Many methods have been suggested for evaluating the evidential value of a matching Y-chromosomal DNA profile obtained from a biological stain associated with a crime scene and the Y-chromosomal DNA profile of a suspect. Most of these methods are based on estimating the population frequency of the Y-profile. The common independence assumption between loci for autosomal DNA profiles cannot be used for Y-chromosomal DNA profiles. In this paper we reconsider the problem of population frequency estimation by application of Bayesian networks and the chow-liu algorithm to model dependencies between loci. We found that the method based on the chow-liu algorithm performs almost as well as the discrete Laplace method. We have also made comparisons to the independence model and we have demonstrated once again that the independence method for Y-profiles cannot be supported.

关键词： Y-chromosome Forensic genetics Lineage markers Weight of evidence chow-liu algorithm Discrete Laplace method

来源：评论

学校读者我要写书评

暂无评论

chow-liu trees are sufficient predictive models for reproducing key features of functional networks of periictal EEG time-series

引用

NEUROIMAGE 2015年 118卷 520-537页

作者： Steimer, Andreas Zubler, Frederic Schindler, Kaspar Univ Bern Inselspital Dept Neurol Univ Hosp Bern CH-3010 Bern Switzerland

Seizure freedom in patients suffering from pharmacoresistant epilepsies is still not achieved in 20-30% of all cases. Hence, current therapies need to be improved, based on a more complete understanding of ictogenesis. In this respect, the analysis of functional networks derived from intracranial electroencephalographic (iEEG) data has recently become a standard tool. Functional networks however are purely descriptive models and thus are conceptually unable to predict fundamental features of iEEG time-series, e.g., in the context of therapeutical brain stimulation. In this paper we present some first steps towards overcoming the limitations of functional network analysis, by showing that its results are implied by a simple predictive model of time-sliced iEEG time-series. More specifically, we learn distinct graphical models (so called chow-liu (CL) trees) as models for the spatial dependencies between iEEG signals. Bayesian inference is then applied to the CL trees, allowing for an analytic derivation/prediction of functional networks, based on thresholding of the absolute value Pearson correlation coefficient (CC) matrix. Using various measures, the thus obtained networks are then compared to those which were derived in the classical way from the empirical CC-matrix. In the high threshold limit we find (a) an excellent agreement between the two networks and (b) key features of periictal networks as they have previously been reported in the literature. Apart from functional networks, both matrices are also compared element-wise, showing that the CL approach leads to a sparse representation, by setting small correlations to values close to zero while preserving the larger ones. Overall, this paper shows the validity of CL-trees as simple, spatially predictive models for periictal iEEG data. Moreover, we suggest straightforward generalizations of the CL-approach for modeling also the temporal features of iEEG signals. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Epilepsy Periictal EEG Predictive modeling Bayesian inference Graphical models chow-liu tree chow-liu algorithm Functional networks Minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

Manifold Learning Analysis and Bayesian Latent-Observational Feature Prediction of a Large Eddy Simulated Turbulence Field

Manifold Learning Analysis and Bayesian Latent-Observational...

引用

OCEANS Hampton Roads Conference

作者： Scott, Nicholas Kukulka, Tobias Riverside Res Open Innovat Ctr Beavercreek OH 45431 USA Univ Delaware Ctr Appl Coastal Res Newark DE USA

ISBN: (数字)9781665468091

ISBN: (纸本)9781665468091

A latent-observational space analytical formulism is applied to a sub-grid modeled turbulent kinetic energy (tke) field emanating from ocean turbulence large eddy simulation (LES) data containing Langmuir cells but no breaking waves. The purpose of the analysis is to illustrate how machine learning modeling can be used to understand the probabilistic structure of observational space and how the allied latent space can be related statistically to it for the purpose of data generation. The Peter and Clark (PC)-algorithm-based Bayesian belief network (BBN) edge-nodal structure for the observational-space tke subdomains demonstrates a distinctive nonlocal connectivity pattern when the multidimensional scaling graph layout is invoked. When the chow-liu algorithm is used, tree-based connectivity in the network is revealed. In particular, a dominant parental root node occupies the far upper left region in the observational-space domain with many edge connections flowing toward the right. Hidden Markov model (HMM) parameter estimation, applied to the maximum and minimum values taken from the mean tke feature matrix and to generative topographic mapping (GTM)-based latent space for the same tke feature nodes, enables estimation of the latent-space state transition matrix and tke latent-observational space emission matrices. The latent-space state transition matrix demonstrates how many columns of latent space, associated with different root-mean-square tke values, possess a high probability of transitioning to other distinct latent-space areas. The tke latent-observational space emission matrix provides spatial subdomain locations most strongly tied to specific vertical columns of GTM-based latent space. The maximum value-based emission matrix shows very high probabilities for single columns on the latent-space perimeter being associated with maximum values occurring at specific observational-space subdomain locations. These observational-space nodal locations have strong st

关键词： ocean turbulence large eddy simulation turbulent kinetic energy generative topographic mapping Bayesian belief network PC algorithm chow-liu algorithm Hidden Markov models emission matrix

来源：评论

学校读者我要写书评

暂无评论

Sample-Optimal and Efficient Learning of Tree Ising Models 2021

Sample-Optimal and Efficient Learning of Tree Ising Models

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Daskalakis, Constantinos Pan, Qinxuan MIT EECS Cambridge MA 02139 USA MIT CSAIL Cambridge MA 02139 USA

ISBN: (纸本)9781450380539

We show that n-variable tree-structured Ising models can be learned computationally-efficiently to within total variation distance ! from an optimal O(n ln n/epsilon(2)) samples, where O(center dot) hides an absolute constant which, importantly, does not depend on the model being learned-neither its tree nor the magnitude of its edge strengths, on which we place no assumptions. Our guarantees hold, in fact, for the celebrated chow-liu algorithm [1968], using the plug-in estimator for estimating mutual information. While this (or any other) algorithm may fail to identify the structure of the underlying model correctly from a finite sample, we show that it will still learn a tree-structured model that is epsilon-close to the true one in total variation distance, a guarantee called "proper learning." Our guarantees do not follow from known results for the chow-liu algorithm and the ensuing literature on learning graphical models, including the very recent renaissance of algorithms on this learning challenge, which only yield asymptotic consistency results, or sample-suboptimal and/or time-inefficient algorithms, unless further assumptions are placed on the model, such as bounds on the "strengths" of the model's edges. While we establish guarantees for a widely known and simple algorithm, the analysis that this algorithm succeeds and is sample-optimal is quite complex, requiring a hierarchical classification of the edges into layers with different reconstruction guarantees, depending on their strength, combined with delicate uses of the subadditivity of the squared Hellinger distance over graphical models to control the error accumulation.

关键词： Tree-Structured Model Bayesian Network Ising Model Markov Random Field chow-liu algorithm Subadditivity Hellinger Distance Estimation Sample Complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：