贝叶斯网络结构学习的简化贪婪算法

基于数据的贝叶斯网络结构学习是一个NP难题.基于条件约束和评分搜索相结合的方法是贝叶斯网络结构学习的一个热点.基于互信息理论提出一种最大支撑树(MWST)机制,并基于最大支撑树结合贪婪搜索的思想提出一种简化贪婪算法.简化贪婪算法不依赖先验知识,完全基于数据集.首先,通过计算互信息建立目标网络的最大支撑树;然后,在最大支撑树的基础上学习初始网络结构,最后,利用简化搜索机制对初始结构进一步优化,最终完成贝叶斯网络的结构学习.数据仿真实验证明,简化贪婪算法不仅具有很高的精度而且具有高效率.     

贝叶斯网络结构稀疏学习研究进展*

贝叶斯网络结构稀疏化学习因其既能简化结构又能保留原始网络中的重要信息,已经成为当前贝叶斯网络的研究热点.文中首先讨论贝叶斯网络结构稀疏学习的必要性、贝叶斯网络稀疏性的定义,并在此基础上介绍现有的贝叶斯网络结构稀疏学习研究思路.然后,回顾一般的贝叶斯网络结构学习方法,并分析它们在高维背景下存在的问题,进而发现基于评分的方法通常适合于贝叶斯网络结构的稀疏学习,因此重点介绍贝叶斯网络结构稀疏学习的目标函数和优化求解算法.最后,探讨未来贝叶斯网络结构稀疏学习的一些研究方向.     

并行的贝叶斯网络参数学习算法

针对大样本条件下EM算法学习贝叶斯网络参数的计算问题,提出一种并行EM算法(Parallel EM,PL-EM)提高大样本条件下复杂贝叶斯网络参数学习的速度.PL-EM算法在E步并行计算隐变量的后验概率和期望充分统计因子;在M步,利用贝叶斯网络的条件独立性和完整数据集下的似然函数可分解性,并行计算各个局部似然函数.实验结果表明PL-EM为解决大样本条件下贝叶斯网络参数学习提供了一种有效的方法.     

基于混合差分蜂群算法的贝叶斯网络结构学习

贝叶斯网络的结构学习是贝叶斯网络理论模型的核心,而现有的贝叶斯网络结构学习算法一般存在效率偏低的问题.针对此问题,文中提出基于混合差分蜂群算法的贝叶斯网络结构学习算法.该算法首先利用最大生成树准则得到初始种群,然后利用差分进化算法中的交叉、变异规则优化初始种群.在使用差分进化算法的过程中,分别将蜂群算法应用于变异阶段和优化改进交叉阶段,并且将云自适应理论应用于选择阶段选择生成个体.在经典贝叶斯网络上的仿真实验证明,文中算法在贝叶斯网络结构学习中具有较强的寻优能力.     

基于条件对数似然函数导数的贝叶斯网络分类器优化算法

通常基于鉴别式学习策略训练的贝叶斯网络分类器有较高的精度,但在具有冗余边的网络结构之上鉴别式参数学习算法的性能受到一定的限制.为了在实际应用中进一步提高贝叶斯网络分类器的分类精度,该文定量描述了网络结构与真实数据变量分布之间的关系,提出了一种不存在冗余边的森林型贝叶斯网络分类器及其相应的FAN学习算法(Forest-Augmented Naive Bayes Algorithm),FAN算法能够利用对数条件似然函数的偏导数来优化网络结构学习.实验结果表明常用的限制性贝叶斯网络分类器通常存在一些冗余边,其往往会降低鉴别式参数学习算法的性能;森林型贝叶斯网络分类器减少了结构中的冗余边,更加适合于采用鉴别式学习策略训练参数;应用条件对数似然函数偏导数的FAN算法在大多数实验数据集合上提高了分类精度.     

类基于蚁群优化的贝叶斯置信网结构学习策略及性能分析*

针对贝叶斯置信网的结构学习问题,提出一种遵循典型ACO算法框架(ACO-TSP)的贝叶斯网结构学习算法（ACO-BN）,并拓展为包括EAS-BN、ACS-BN和MMAS-BN在内的一类算法。用这类算法在若干典型贝叶斯网络结构学习问题上分别与经典贝叶斯网学习算法(K2、B)、用于贝叶斯网学习的通用优化算法（simulated annealing、Tabu searching和genetic searching）以及L. M. de Campos等人提出的基于蚁群优化的贝叶斯网络结构学习算法 Ant-K2SN     

基于模拟退火的贝叶斯网络结构学习算法

贝叶斯网络的学习可分为结构学习和参数学习。基于模拟退火的结构学习算法是一种以搜索最高记分函数为原则的智能优化方法。本文以KL距离、相互信息以及最大相互信息为基础，通过附加合适的约束函数降低学习搜索的复杂度，提出一种附加约束的最大熵优化函数作为模拟退火算法的能量优化函数，并结合贝叶斯网络结构学习的特点设计了适合模拟退火的变量表示和邻近值产生机制。通过与其他用于结构学习的模拟退火算法，以及遗传和进化算法比较分析，结果表明本文中提出的基于模拟退火的贝叶斯网络结构学习算法在时间和精度上都具有较好的效果。     

判别贝叶斯网络的CEM学习算法

当数据存在缺值时,通常应用EM算法学习贝叶斯网络.然而,EM算法以联合似然作为目标函数,与判别预测问题的目标相偏离.与EM算法不同,CEM(Conditional Expectation Maximum)算法直接以条件似然作为目标函数.研究了判别贝叶斯网络学习的CEM算法,提出一种使得CEM算法具有单调性和收敛性的Q函数.为了简化计算,在CEM算法的E步,应用Q函数的一种简化形式;在CEM算法的M步,应用梯度下降法的一次搜索结果作为最优值的近似.最后,在UCI数据集上的实验结果表明了CEM算法在判别贝叶斯网络学习中的有效性.     

贝叶斯网络结构改进方法研究

针对两阶段的贝叶斯网络建模任务,提出基于网络度量的贝叶斯网络结构改进方法.定义基于条件独立互信息测度、以网络复杂度为惩罚函数的网络度量.该方法通过添加必要的弧和删除多余的弧两个主要步骤,搜索具有最小网络测度的贝叶斯网络为改进后的最佳网络.给出方法的详细过程,证明方法的正确性,并进一步分析算法的复杂度.通过熟知的贝叶斯网络Alarm的实验,验证方法的有效性.     

基于粒子群优化建模的贝叶斯网络结构学习方法

贝叶斯网络(BN)在不确定性的条件下表示信息和推理论证具有良好的性能,但由于其结构搜索空间的复杂性,通常将从一个数据集合中学习贝叶斯网络的结构认为是一种NP-hard的问题。基于此,提出一种新的基于粒子群优化算法建模的贝叶斯网络结构学习方法。为了学习一个贝叶斯网络的结构,该方法先使用粒子群优化算法在排序空间中进行搜索,然后运行K2算法计算每个排序的吻合度。每个排序都会有一个网络结构与之一致,该方法会返回这个网络的计分。仿真结果表明,在不同规模的数据集中,该算法相对于其他贝叶斯网络结构学习算法对不同类型的网络都具有更好的网络稳定性。     

An efficient data mining method for learning Bayesian networks using an evolutionary algorithm-based hybrid approach

Given the explosive growth of data collected from current business environment, data mining can potentially discover new knowledge to improve managerial decision making. This paper proposes a novel data mining approach that employs an evolutionary algorithm to discover knowledge represented in Bayesian networks. The approach is applied successfully to handle the business problem of finding response models from direct marketing data. Learning Bayesian networks from data is a difficult problem. There are two different approaches to the network learning problem. The first one uses dependency analysis, while the second one searches good network structures according to a metric. Unfortunately, both approaches have their own drawbacks. Thus, we propose a novel hybrid algorithm of the two approaches, which consists of two phases, namely, the conditional independence (CI) test and the search phases. In the CI test phase, dependency analysis is conducted to reduce the size of the search space. In the search phase, good Bayesian network models are generated by using an evolutionary algorithm. A new operator is introduced to further enhance the search effectiveness and efficiency. In a number of experiments and comparisons, the hybrid algorithm outperforms MDLEP, our previous algorithm which uses evolutionary programming (EP) for network learning, and other network learning algorithms. We then apply the approach to two data sets of direct marketing and compare the performance of the evolved Bayesian networks obtained by the new algorithm with those by MDLEP, the logistic regression models, the na/spl inodot//spl uml/ve Bayesian classifiers, and the tree-augmented na/spl inodot//spl uml/ve Bayesian network classifiers (TAN). In the comparison, the new algorithm outperforms the others.     

基于遗传算法和强化学习的贝叶斯网络结构学习算法

遗传算法是基于自然界中生物遗传规律的适应性原则对问题解空间进行搜寻和最优化的方法。贝叶斯网络是对不确定性知识进行建模、推理的主要方法,Bayesian网中的学习问题(参数学习与结构学习)是个NP-hard问题。强化学习是利用新顺序数据来更新学习结果的在线学习方法。介绍了利用强化学习指导遗传算法,实现对贝叶斯网结构进行有效学习。     

A heuristic method for learning Bayesian networks using discrete particle swarm optimization

Bayesian networks are a powerful approach for representing and reasoning under conditions of uncertainty. Many researchers aim to find good algorithms for learning Bayesian networks from data. And the heuristic search algorithm is one of the most effective algorithms. Because the number of possible structures grows exponentially with the number of variables, learning the model structure from data by considering all possible structures exhaustively is infeasible. PSO (particle swarm optimization), a powerful optimal heuristic search algorithm, has been applied in various fields. Unfortunately, the classical PSO algorithm only operates in continuous and real-valued space, and the problem of Bayesian networks learning is in discrete space. In this paper, two modifications of updating rules for velocity and position are introduced and a Bayesian networks learning based on binary PSO is proposed. Experimental results show that it is more efficient because only fewer generations are needed to obtain optimal Bayesian networks structures. In the comparison, this method outperforms other heuristic methods such as GA (genetic algorithm) and classical binary PSO.     

Learning Bayesian networks for discrete data

Bayesian networks have received much attention in the recent literature. In this article, we propose an approach to learn Bayesian networks using the stochastic approximation Monte Carlo (SAMC) algorithm. Our approach has two nice features. Firstly, it possesses the self-adjusting mechanism and thus avoids essentially the local-trap problem suffered by conventional MCMC simulation-based approaches in learning Bayesian networks. Secondly, it falls into the class of dynamic importance sampling algorithms; the network features can be inferred by dynamically weighted averaging the samples generated in the learning process, and the resulting estimates can have much lower variation than the single model-based estimates. The numerical results indicate that our approach can mix much faster over the space of Bayesian networks than the conventional MCMC simulation-based approaches.     

Structure learning of Bayesian networks by genetic algorithms: aperformance analysis of control parameters

We present a new approach to structure learning in the field of Bayesian networks. We tackle the problem of the search for the best Bayesian network structure, given a database of cases, using the genetic algorithm philosophy for searching among alternative structures. We start by assuming an ordering between the nodes of the network structures. This assumption is necessary to guarantee that the networks that are created by the genetic algorithms are legal Bayesian network structures. Next, we release the ordering assumption by using a “repair operator” which converts illegal structures into legal ones. We present empirical results and analyze them statistically. The best results are obtained with an elitist genetic algorithm that contains a local optimizer     

An artificial bee colony algorithm for learning Bayesian networks

One basic approach to learn Bayesian networks (BNs) from data is to apply a search procedure to explore the set of candidate networks for the database in light of a scoring metric, where the most popular stochastic methods are based on some meta-heuristic mechanisms, such as Genetic Algorithm, Evolutionary Programming and Ant Colony Optimization. In this paper, we have developed a new algorithm for learning BNs which employs a recently introduced meta-heuristic: artificial bee colony (ABC). All the phases necessary to tackle our learning problem using this meta-heuristic are described, and some experimental results to compare the performance of our ABC-based algorithm with other algorithms are given in the paper.     

Air pollution prediction via multi-label classification

A Bayesian network classifier can be used to estimate the probability of an air pollutant overcoming a certain threshold. Yet multiple predictions are typically required regarding variables which are stochastically dependent, such as ozone measured in multiple stations or assessed according to by different indicators. The common practice (independent approach) is to devise an independent classifier for each class variable being predicted; yet this approach overlooks the dependencies among the class variables. By appropriately modeling such dependencies one can improve the accuracy of the forecasts. We address this problem by designing a multi-label classifier, which simultaneously predict multiple air pollution variables. To this end we design a multi-label classifier based on Bayesian networks and learn its structure through structural learning. We present experiments in three different case studies regarding the prediction of PM2.5 and ozone. The multi-label classifier outperforms the independent approach, allowing to take better decisions.     

Bayes网络学习的MCMC方法

基于Bayes统计理论, 提出了一种从数据样本中学习Bayes网络的Markov链Monte Carlo(MCMC)方法. 首先通过先验概率和数据样本的结合得到未归一化的后验概率, 然后使用此后验概率指导随机搜索算法寻找“好”的网络结构模型. 通过对Alarm网络的学习表明了本算法具有较好的性能.     

New skeleton-based approaches for Bayesian structure learning of Bayesian networks

Automatically learning the graph structure of a single Bayesian network (BN) which accurately represents the underlying multivariate probability distribution of a collection of random variables is a challenging task. But obtaining a Bayesian solution to this problem based on computing the posterior probability of the presence of any edge or any directed path between two variables or any other structural feature is a much more involved problem, since it requires averaging over all the possible graph structures. For the former problem, recent advances have shown that search + score approaches find much more accurate structures if the search is constrained by a previously inferred skeleton (i.e. a relaxed structure with undirected edges which can be inferred using local search based methods). Based on similar ideas, we propose two novel skeleton-based approaches to approximate a Bayesian solution to the BN learning problem: a new stochastic search which tries to find directed acyclic graph (DAG) structures with a non-negligible score; and a new Markov chain Monte Carlo method over the DAG space. These two approaches are based on the same idea. In a first step, both employ a previously given skeleton and build a Bayesian solution constrained by this skeleton. In a second step, using the preliminary solution, they try to obtain a new Bayesian approximation but this time in an unconstrained graph space, which is the final outcome of the methods. As shown in the experimental evaluation, this new approach strongly boosts the performance of these two standard techniques proving that the idea of employing a skeleton to constrain the model space is also a successful strategy for performing Bayesian structure learning of BNs.