Efficient Markov Network Structure Discovery Using Independence Tests

We present two algorithms for learning the structure of a Markov network from data: GSMN* and GSIMN. Both algorithms use statistical independence tests to infer the structure by successively constraining the set of structures consistent with the results of these tests. Until very recently, algorithms for structure learning were based on maximum likelihood estimation, which has been proved to be NP-hard for Markov networks due to the difficulty of estimating the parameters of the network, needed for the computation of the data likelihood. The independence-based approach does not require the computation of the likelihood, and thus both GSMN* and GSIMN can compute the structure efficiently (as shown in our experiments). GSMN* is an adaptation of the Grow-Shrink algorithm of Margaritis and Thrun for learning the structure of Bayesian networks. GSIMN extends GSMN* by additionally exploiting Pearl's well-known properties of the conditional independence relation to infer novel independences from known ones, thus avoiding the performance of statistical tests to estimate them. To accomplish this efficiently GSIMN uses the Triangle theorem, also introduced in this work, which is a simplified version of the set of Markov axioms. Experimental comparisons on artificial and real-world data sets show GSIMN can yield significant savings with respect to GSMN*, while generating a Markov network with comparable or in some cases improved quality. We also compare GSIMN to a forward-chaining implementation, called GSIMN-FCH, that produces all possible conditional independences resulting from repeatedly applying Pearl's theorems on the known conditional independence tests. The results of this comparison show that GSIMN, by the sole use of the Triangle theorem, is nearly optimal in terms of the set of independences tests that it infers.     

A conditional independence algorithm for learning undirected graphical models

When it comes to learning graphical models from data, approaches based on conditional independence tests are among the most popular methods. Since Bayesian networks dominate research in this field, these methods usually refer to directed graphs, and thus have to determine not only the set of edges, but also their direction. At least for a certain kind of possibilistic graphical models, however, undirected graphs are a much more natural basis. Hence, in this area, algorithms for learning undirected graphs are desirable, especially, since first learning a directed graph and then transforming it into an undirected one wastes resources and computation time. In this paper I present a general algorithm for learning undirected graphical models, which is strongly inspired by the well-known Cheng–Bell–Liu algorithm for learning Bayesian networks from data. Its main advantage is that it needs fewer conditional independence tests, while it achieves results of comparable quality.     

基于互信息的贝叶斯网络结构学习算法

结构学习是贝叶斯网络的重要分支之一,而由数据学习贝叶斯网络是NP-完全问题,提出了一个由数据学习贝叶斯网络的改进算法。该算法基于互信息知识构造初始无向图,并通过条件独立测试对无向边添加方向;同时提出了一个针对4节点环和5节点环的局部优化方法来构造初始框架,最后利用贪婪搜索算法得到最优网络结构。数值实验结果表明,改进的算法无论是在BIC评分值,还是在结构的误差上都有一定的改善,并且在迭代次数、运行时间上均有明显降低,能较快地确定出与数据匹配程度最高的网络结构。     

Lazy Learning of Bayesian Rules

The naive Bayesian classifier provides a simple and effective approach to classifier learning, but its attribute independence assumption is often violated in the real world. A number of approaches have sought to alleviate this problem. A Bayesian tree learning algorithm builds a decision tree, and generates a local naive Bayesian classifier at each leaf. The tests leading to a leaf can alleviate attribute inter-dependencies for the local naive Bayesian classifier. However, Bayesian tree learning still suffers from the small disjunct problem of tree learning. While inferred Bayesian trees demonstrate low average prediction error rates, there is reason to believe that error rates will be higher for those leaves with few training examples. This paper proposes the application of lazy learning techniques to Bayesian tree induction and presents the resulting lazy Bayesian rule learning algorithm, called LBR. This algorithm can be justified by a variant of Bayes theorem which supports a weaker conditional attribute independence assumption than is required by naive Bayes. For each test example, it builds a most appropriate rule with a local naive Bayesian classifier as its consequent. It is demonstrated that the computational requirements of LBR are reasonable in a wide cross-section of natural domains. Experiments with these domains show that, on average, this new algorithm obtains lower error rates significantly more often than the reverse in comparison to a naive Bayesian classifier, C4.5, a Bayesian tree learning algorithm, a constructive Bayesian classifier that eliminates attributes and constructs new attributes using Cartesian products of existing nominal attributes, and a lazy decision tree learning algorithm. It also outperforms, although the result is not statistically significant, a selective naive Bayesian classifier.     

LEARNING STRUCTURED BAYESIAN NETWORKS: COMBINING ABSTRACTION HIERARCHIES AND TREE-STRUCTURED CONDITIONAL PROBABILITY TABLES

Context-specific independence representations, such as tree-structured conditional probability distributions, capture local independence relationships among the random variables in a Bayesian network (BN). Local independence relationships among the random variables can also be captured by using attribute-value hierarchies to find an appropriate abstraction level for the values used to describe the conditional probability distributions. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. In this paper, we introduce Tree-Abstraction-Based Search (TABS), an approach for learning a data distribution by inducing the graph structure and parameters of a BN from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. To construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. We present empirical results for three real-world domains, finding that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies.     

由Markov网到Bayesian网

Markov网（马尔可夫网）是类似于Bayesian网（贝叶斯网）的另一种进行不确定性揄的有力工具，Markov网是一个无向图，而Bayesian网是一个有向无环图，发现Markov网不需要发现边的方向，因此要比发现Bayesian网容易得多，提出了一种通过发现Markov网得到等价的Bayesian网的方法，首先利用信息论中验证信息独立的一个重要结论，提出了一个基于依赖分析的边删除算法发现Markov网，该算法需O（n^2)次CI（条件独立）测试，CI测试的时间复杂度取决于由样本数据得到的联合概率函数表的大小，经证明，假如由样本数据得到的联合概率函数严格为正，则该算法发现的Markov网一定是样本的最小L图，由发现Markov网，根据表示的联合概率函数相等，得到与其等价的Bayesian网。     

基于模型融合的分布式贝叶斯网络学习算法*

提出了一个从同构数据集中学习贝叶斯网络结构的分布式算法。该算法首先使用搜索评分的方法学习每个局部贝叶斯网络结构,然后取节点对互信息变量和条件互信息变量的数学期望作为全局学习的评价标准,融合所有局部结构得到全局结构。由于只使用了数据集中变量间的互信息和条件互信息,没有直接获取局部个体数据信息,从而可以实现有效的隐私保护。该算法在Alarm数据集上进行测试,边的误差率小于6%,运行时间比集中学习的算法的运行时间短,验证了算法的有效性。     

Learning Causal Bayesian Networks Using Minimum Free Energy Principle

Constraint-based search methods, which are a major approach to learning Bayesian networks, are expected to be effective in causal discovery tasks. However, such methods often suffer from impracticality of classical hypothesis testing for conditional independence when the sample size is insufficiently large. We present a new conditional independence (CI) testing method that is designed to be effective for small samples. Our method uses the minimum free energy principle, which originates from thermodynamics, with the “Data Temperature” assumption recently proposed by us. This CI method incorporates the maximum entropy principle and converges to classical hypothesis tests in asymptotic regions. In our experiments using repository datasets (Alarm/Insurance/Hailfinder/Barley/Mildew), the results show that our method improves the learning performance of the well known PC algorithm in the view of edge-reversed errors in addition to extra/missing errors.     

Structure of the high-order Boltzmann machine from independencemaps

In this paper we consider the determination of the structure of the high-order Boltzmann machine (HOBM), a stochastic recurrent network for approximating probability distributions. We obtain the structure of the HOBM, the hypergraph of connections, from conditional independences of the probability distribution to model. We assume that an expert provides these conditional independences and from them we build independence maps, Markov and Bayesian networks, which represent conditional independences through undirected graphs and directed acyclic graphs respectively. From these independence maps we construct the HOBM hypergraph. The central aim of this paper is to obtain a minimal hypergraph. Given that different orderings of the variables provide in general different Bayesian networks, we define their intersection hypergraph. We prove that the intersection hypergraph of all the Bayesian networks (N!) of the distribution is contained by the hypergraph of the Markov network, it is more simple, and we give a procedure to determine a subset of the Bayesian networks that verifies this property. We also prove that the Markov network graph establishes a minimum connectivity for the hypergraphs from Bayesian networks.     

基于因果影响独立模型的贝叶斯网络参数学习

基于因果影响独立模型及其中形成的特定上下文独立关系,提出一种适于样本学习的贝叶斯网络参数学习算法。该算法在对局部概率模型降维分解的基础上,通过单父节点条件下的子节点概率分布来合成局部结构的条件概率分布,参数定义复杂度较低且能较好地处理稀疏结构样本集。实验结果表明,该算法与标准最大似然估计算法相比,能充分利用样本信息,具有较好的学习精度。     

Learning Bayesian Networks: The Combination of Knowledge and Statistical Data

We describe a Bayesian approach for learning Bayesian networks from a combination of prior knowledge and statistical data. First and foremost, we develop a methodology for assessing informative priors needed for learning. Our approach is derived from a set of assumptions made previously as well as the assumption of likelihood equivalence, which says that data should not help to discriminate network structures that represent the same assertions of conditional independence. We show that likelihood equivalence when combined with previously made assumptions implies that the user's priors for network parameters can be encoded in a single Bayesian network for the next case to be seen—a prior network—and a single measure of confidence for that network. Second, using these priors, we show how to compute the relative posterior probabilities of network structures given data. Third, we describe search methods for identifying network structures with high posterior probabilities. We describe polynomial algorithms for finding the highest-scoring network structures in the special case where every node has at most k = 1 parent. For the general case (k > 1), which is NP-hard, we review heuristic search algorithms including local search, iterative local search, and simulated annealing. Finally, we describe a methodology for evaluating Bayesian-network learning algorithms, and apply this approach to a comparison of various approaches.     

基于先验节点序学习贝叶斯网络结构的优化方法

针对小样本数据集下学习贝叶斯网络 (Bayesian networks, BN)结构的不足, 以及随着条件集的增大, 利用统计方法进行条件独立 (Conditional independence, CI) 测试不稳定等问题, 提出了一种基于先验节点序学习网络结构的优化方法. 新方法通过定义优化目标函数和可行域空间, 首次将贝叶斯网络结构学习问题转化为求解目标函数极值的数学规划问题, 并给出最优解的存在性及唯一性证明, 为贝叶斯网络的不断扩展研究提出了新的方案. 理论证明以及实验结果显示了新方法的正确性和有效性.     

Buried Markov models: a graphical-modeling approach to automatic speech recognition

In this work, buried Markov models (BMM) are introduced. In a BMM, a Markov chain state at time t determines the conditional independence patterns that exist between random variables lying within a local time window surrounding t. This model is motivated by and can be fully described by “graphical models”, a general technique to describe families of probability distributions. In the paper, it is shown how information-theoretic criterion functions can be used to induce sparse, discriminative, and class-conditional network structures that yield an optimal approximation to the class posterior probability, and therefore are useful for classification tasks such as speech recognition. Using a new structure learning heuristic, the resulting structurally discriminative models are tested on a medium-vocabulary isolated-word speech recognition task. It is demonstrated that discriminatively structured BMMs, when trained in a maximum likelihood setting using EM, can outperform both hidden Markov models (HMMs) and other dynamic Bayesian networks with a similar number of parameters.     

基于互信息学习贝叶斯网络等价类*

由数据构造贝叶斯网络结构是NP-难问题,根据互信息和条件独立测试,提出了一种构建最优贝叶斯网络结构的新算法。数值实验表明,新算法能较快地确定出与数据匹配程度最高的网络结构,从而能更高效地学习贝叶斯网络结构。     

Degrees of conditional (in)dependence: A framework for approximate Bayesian networks and examples related to the rough set-based feature selection

Bayesian networks provide the means for representing probabilistic conditional independence. Conditional independence is widely considered also beyond the theory of probability, with linkages to, e.g. the database multi-valued dependencies, and at a higher abstraction level of semi-graphoid models. The rough set framework for data analysis is related to the topics of conditional independence via the notion of a decision reduct, to be considered within a wider domain of the feature selection. Given probabilistic version of decision reducts equivalent to the data-based Markov boundaries, the studies were also conducted for other criteria of the rough-set-based feature selection, e.g. those corresponding to the multi-valued dependencies. In this paper, we investigate the degrees of approximate conditional dependence, which could be a topic corresponding to the well-known notions such as conditional mutual information and polymatroid functions, however, with many practically useful approximate conditional independence models unmanageable within the information theoretic framework. The major paper’s contribution lays in extending the means for understanding the degrees of approximate conditional dependence, with appropriately generalized semi-graphoid properties formulated and with the mathematical soundness of the Bayesian network-like representation of the approximate conditional independence statements thoroughly proved. As an additional contribution, we provide a case study of the approximate conditional independence model, which would not be manageable without the above-mentioned extensions.     

A gray correlation based Bayesian network model for fault source diagnosis of multistage process – Small sample manufacturing system

Fault source diagnosis methodology is one of the key technologies of quality control and assurance for multi-source & multi-stage manufacturing processes, especially in small sample manufacturing systems. By analyzing the existing research on fault source diagnosis methods, a Bayesian network-based methodology is proposed. Gray correlation theory and mechanism analysis method are used in the process of Bayesian network model construction to reduce the dependence of sample data size for structure learning in the process of small sample manufacturing of complex products. In addition, two fault source diagnosis methods based on manufacturing principle analysis and reverse Bayesian network respectively are proposed. The strategy of the combined use of the two methods in the actual manufacturing scenes is given to cope with the fault source diagnosis scenario in the real manufacturing process. In the end, an example from an actual factory is provided to validate the effectiveness and efficiency of the proposed model and methodologies.     

一种面向非线性回归的迁移学习模型

迁移学习能够有效地在相似任务之间进行信息的共享和迁移.之前针对多任务回归的迁移学习研究大多集中在线性系统上.针对非线性回归问题,提出了一种新的多任务回归模型--HiRBF.HiRBF基于层次贝叶斯模型,采用RBF神经网络进行回归学习,假设各个任务的输出层参数服从某种共同的先验分布.根据各个任务是否共享隐藏层,在构造HiRBF模型时有两种可选方案.在实验部分,将两种方案进行了对比,也将HiRBF与两种非迁移学习算法进行了对比,实验结果表明,HiRBF的预测性能大大优于其它两个算法.     

Classification-oriented structure learning in Bayesian networks for multimodal event detection in videos

We investigate the use of structure learning in Bayesian networks for a complex multimodal task of action detection in soccer videos. We illustrate that classical score-oriented structure learning algorithms, such as the K2 one whose usefulness has been demonstrated on simple tasks, fail in providing a good network structure for classification tasks where many correlated observed variables are necessary to make a decision. We then compare several structure learning objective functions, which aim at finding out the structure that yields the best classification results, extending existing solutions in the literature. Experimental results on a comprehensive data set of 7 videos show that a discriminative objective function based on conditional likelihood yields the best results, while augmented approaches offer a good compromise between learning speed and classification accuracy.     

基于生成对抗网络的模仿学习综述

模仿学习研究如何从专家的决策数据中进行学习,以得到接近专家水准的决策模型.同样学习如何决策的强化学习往往只根据环境的评价式反馈进行学习,与之相比,模仿学习能从决策数据中获得更为直接的反馈.它可以分为行为克隆、基于逆向强化学习的模仿学习两类方法.基于逆向强化学习的模仿学习把模仿学习的过程分解成逆向强化学习和强化学习两个子过程,并反复迭代.逆向强化学习用于推导符合专家决策数据的奖赏函数,而强化学习基于该奖赏函数来学习策略.基于生成对抗网络的模仿学习方法从基于逆向强化学习的模仿学习发展而来,其中最早出现且最具代表性的是生成对抗模仿学习方法(Generative Adversarial Imitation Learning,简称GAIL).生成对抗网络由两个相对抗的神经网络构成,分别为判别器和生成器.GAIL的特点是用生成对抗网络框架求解模仿学习问题,其中,判别器的训练过程可类比奖赏函数的学习过程,生成器的训练过程可类比策略的学习过程.与传统模仿学习方法相比,GAIL具有更好的鲁棒性、表征能力和计算效率.因此,它能够处理复杂的大规模问题,并可拓展到实际应用中.然而,GAIL存在着模态崩塌、环境交互样本利用效率低等问题.最近,新的研究工作利用生成对抗网络技术和强化学习技术等分别对这些问题进行改进,并在观察机制、多智能体系统等方面对GAIL进行了拓展.本文先介绍了GAIL的主要思想及其优缺点,然后对GAIL的改进算法进行了归类、分析和对比,最后总结全文并探讨了可能的未来趋势.