Bayesian MAP model selection of chain event graphs

Chain event graphs are graphical models that while retaining most of the structural advantages of Bayesian networks for model interrogation, propagation and learning, more naturally encode asymmetric state spaces and the order in which events happen than Bayesian networks do. In addition, the class of models that can be represented by chain event graphs for a finite set of discrete variables is a strict superset of the class that can be described by Bayesian networks. In this paper we demonstrate how with complete sampling, conjugate closed form model selection based on product Dirichlet priors is possible, and prove that suitable homogeneity assumptions characterise the product Dirichlet prior on this class of models. We demonstrate our techniques using two educational examples.     

On expressiveness of the chain graph interpretations

In this article we study the expressiveness of the different chain graph interpretations. Chain graphs is a class of probabilistic graphical models that can contain two types of edges, representing different types of relationships between the variables in question. Chain graphs is also a superclass of directed acyclic graphs, i.e. Bayesian networks, and can thereby represent systems more accurately than this less expressive class of models. Today there do however exist several different ways of interpreting chain graphs and what conditional independences they encode, giving rise to different so-called chain graph interpretations. Previous research has approximated the number of representable independence models for the Lauritzen–Wermuth–Frydenberg and the multivariate regression chain graph interpretations using an MCMC based approach. In this article we use a similar approach to approximate the number of models representable by the latest chain graph interpretation in research, the Andersson–Madigan–Perlman interpretation. Moreover we summarize and compare the different chain graph interpretations with each other. Our results confirm previous results that directed acyclic graphs only can represent a small fraction of the models representable by chain graphs, even for a low number of nodes. The results also show that the Andersson–Madigan–Perlman and multivariate regression interpretations can represent about the same amount of models and twice the amount of models compared to the Lauritzen–Wermuth–Frydenberg interpretation. However, at the same time almost all models representable by the latter interpretation can only be represented by that interpretation while the former two have a large intersection in terms of representable models.     

Chain graph interpretations and their relations revisited

In this paper we study how different theoretical concepts of Bayesian networks have been extended to chain graphs. Today there exist mainly three different interpretations of chain graphs in the literature. These are the Lauritzen–Wermuth–Frydenberg, the Andersson–Madigan–Perlman and the multivariate regression interpretations. The different chain graph interpretations have been studied independently and over time different theoretical concepts have been extended from Bayesian networks to also work for the different chain graph interpretations. This has however led to confusion regarding what concepts exist for what interpretation.In this article we do therefore study some of these concepts and how they have been extended to chain graphs as well as what results have been achieved so far. More importantly we do also identify when the concepts have not been extended and contribute within these areas. Specifically we study the following theoretical concepts: Unique representations of independence models, the split and merging operators, the conditions for when an independence model representable by one chain graph interpretation can be represented by another chain graph interpretation and finally the extension of Meek's conjecture to chain graphs. With our new results we give a coherent overview of how each of these concepts is extended for each of the different chain graph interpretations.     

利用贝叶斯网络分析基因表达数据

利用基因表达数据提出一种新的网络模型—贝叶斯网络,发现基因的互作.一个贝叶斯网络是多变量联合概率分布的有向图模型,表示变量间的条件独立属性.首先我们阐明贝叶斯网络如何表示基因间的互作,然后介绍从基因芯片数据学习贝叶斯网络的方法.     

Speeding-up structured probabilistic inference using pattern mining

In many domains where experts are the main source of knowledge, e.g., in reliability and risk management, a framework well suited for modeling, maintenance and exploitation of complex probabilistic systems is essential. In these domains, models usually define closed-world systems and result from the aggregation of multiple patterns repeated many times. Object Oriented-based Frameworks such as Probabilistic Relational Models (PRM) thus offer an effective way to represent such systems. They define patterns as classes and substitute large Bayesian networks (BN) by graphs of instances of these classes. In this framework, Structured Inference avoids many computation redundancies by exploiting class knowledge, hence reducing BN inference times by orders of magnitude. However, to keep modeling and maintenance costs low, object oriented-based framework’s classes often encode only generic situations. More complex situations, even those repeated many times, are only represented by combinations of instances. In this paper, we propose to determine online such combination patterns and exploit them as classes to speed-up Structured Inference. We prove that determining an optimal set of patterns is NP-hard. We also provide an efficient algorithm to approximate this set and show numerical experiments that highlight its practical efficiency.     

Modelling and inference with Conditional Gaussian Probabilistic Decision Graphs

Probabilistic Decision Graphs (PDGs) are probabilistic graphical models that represent a factorisation of a discrete joint probability distribution using a “decision graph”-like structure over local marginal parameters. The structure of a PDG enables the model to capture some context specific independence relations that are not representable in the structure of more commonly used graphical models such as Bayesian networks and Markov networks. This sometimes makes operations in PDGs more efficient than in alternative models. PDGs have previously been defined only in the discrete case, assuming a multinomial joint distribution over the variables in the model. We extend PDGs to incorporate continuous variables, by assuming a Conditional Gaussian (CG) joint distribution. We also show how inference can be carried out in an efficient way.     

A PC algorithm variation for ordinal variables

Bayesian networks are graphical models that represent the joint distribution of a set of variables using directed acyclic graphs. The graph can be manually built by domain experts according to their knowledge. However, when the dependence structure is unknown (or partially known) the network has to be estimated from data by using suitable learning algorithms. In this paper, we deal with a constraint-based method to perform Bayesian networks structural learning in the presence of ordinal variables. We propose an alternative version of the PC algorithm, which is one of the most known procedures, with the aim to infer the network by accounting for additional information inherent to ordinal data. The proposal is based on a nonparametric test, appropriate for ordinal variables. A comparative study shows that, in some situations, the proposal discussed here is a slightly more efficient solution than the PC algorithm.     

Bayesian selection of graphical regulatory models

We define a new class of coloured graphical models, called regulatory graphs. These graphs have their own distinctive formal semantics and can directly represent typical qualitative hypotheses about regulatory processes like those described by various biological mechanisms. They admit an embellishment into classes of probabilistic statistical models and so standard Bayesian methods of model selection can be used to choose promising candidate explanations of regulation. Regulation is modelled by the existence of a deterministic relationship between the longitudinal series of observations labelled by the receiving vertex and the donating one. This class contains longitudinal cluster models as a degenerate graph. Edge colours directly distinguish important features of the mechanism like inhibition and excitation and graphs are often cyclic. With appropriate distributional assumptions, because the regulatory relationships map onto each other through a group structure, it is possible to define a conditional conjugate analysis. This means that even when the model space is huge it is nevertheless feasible, using a Bayesian MAP search, to a discover regulatory network with a high Bayes Factor score. We also show that, like the class of Bayesian Networks, regulatory graphs also admit a formal but distinctive causal algebra. The topology of the graph then represents collections of hypotheses about the predicted effect of controlling the process by tearing out message passers or forcing them to transmit certain signals. We illustrate our methods on a microarray experiment measuring the expression of thousands of genes as a longitudinal series where the scientific interest lies in the circadian regulation of these plants.     

Learning Bayesian network classifiers by risk minimization

Bayesian networks (BNs) provide a powerful graphical model for encoding the probabilistic relationships among a set of variables, and hence can naturally be used for classification. However, Bayesian network classifiers (BNCs) learned in the common way using likelihood scores usually tend to achieve only mediocre classification accuracy because these scores are less specific to classification, but rather suit a general inference problem. We propose risk minimization by cross validation (RMCV) using the 0/1 loss function, which is a classification-oriented score for unrestricted BNCs. RMCV is an extension of classification-oriented scores commonly used in learning restricted BNCs and non-BN classifiers. Using small real and synthetic problems, allowing for learning all possible graphs, we empirically demonstrate RMCV superiority to marginal and class-conditional likelihood-based scores with respect to classification accuracy. Experiments using twenty-two real-world datasets show that BNCs learned using an RMCV-based algorithm significantly outperform the naive Bayesian classifier (NBC), tree augmented NBC (TAN), and other BNCs learned using marginal or conditional likelihood scores and are on par with non-BN state of the art classifiers, such as support vector machine, neural network, and classification tree. These experiments also show that an optimized version of RMCV is faster than all unrestricted BNCs and comparable with the neural network with respect to run-time. The main conclusion from our experiments is that unrestricted BNCs, when learned properly, can be a good alternative to restricted BNCs and traditional machine-learning classifiers with respect to both accuracy and efficiency.     

Networks of probabilistic events in discrete time

The usual methods of applying Bayesian networks to the modeling of temporal processes, such as Dean and Kanazawa’s dynamic Bayesian networks (DBNs), consist in discretizing time and creating an instance of each random variable for each point in time. We present a new approach called network of probabilistic events in discrete time (NPEDT), for temporal reasoning with uncertainty in domains involving probabilistic events. Under this approach, time is discretized and each value of a variable represents the instant at which a certain event may occur. This is the main difference with respect to DBNs, in which the value of a variable V_i represents the state of a real-world property at time t_i. Therefore, our method is more appropriate for temporal fault diagnosis, because only one variable is necessary for representing the occurrence of a fault and, as a consequence, the networks involved are much simpler than those obtained by using DBNs. In contrast, DBNs are more appropriate for monitoring tasks, since they explicitly represent the state of the system at each moment. We also introduce in this paper several types of temporal noisy gates, which facilitate the acquisition and representation of uncertain temporal knowledge. They constitute a generalization of traditional canonical models of multicausal interactions, such as the noisy OR-gate, which have been usually applied to static domains. We illustrate the approach with the example domain of modeling the evolution of traffic jams produced on the outskirts of a city, after the occurrence of an event that obliges traffic to stop indefinitely.     

Pattern Generalization with Graphs and Words: A Cross-Sectional and Longitudinal Analysis of Middle School Students' Representational Fluency

Cross-sectional and longitudinal data from students as they advance through the middle school years (grades 6-8) reveal insights into the development of students' pattern generalization abilities. As expected, students show a preference for lower-level tasks such as reading the data, over more distant predictions and generation of abstractions. Performance data also indicate a verbal advantage that shows greater success when working with words than graphs, a replication of earlier findings comparing words to symbolic equations. Surprisingly, students show a marked advantage with patterns presented in a continuous format (line graphs and verbal rules) as compared to those presented as collections of discrete instances (point-wise graphs and lists of exemplars). Student pattern-generalization performance also was higher when words and graphs were combined. Analyses of student performance patterns and strategy use contribute to an emerging developmental model of representational fluency. The model contributes to research on the development of representational fluency and can inform instructional practices and curriculum design in the area of algebraic development. Results also underscore the impact that perceptual aspects of representations have on students' reasoning, as suggested by an Embodied Cognition view.     

Multiagent bayesian forecasting of structural time-invariant dynamic systems with graphical models

Time series are found widely in engineering and science. We study forecasting of stochastic, dynamic systems based on observations from multivariate time series. We model the domain as a dynamic multiply sectioned Bayesian network (DMSBN) and populate the domain by a set of proprietary, cooperative agents. We propose an algorithm suite that allows the agents to perform one-step forecasts with distributed probabilistic inference. We show that as long as the DMSBN is structural time-invariant (possibly parametric time-variant), the forecast is exact and its time complexity is exponentially more efficient than using dynamic Bayesian networks (DBNs). In comparison with independent DBN-based agents, multiagent DMSBNs produce more accurate forecasts. The effectiveness of the framework is demonstrated through experiments on a supply chain testbed.     

Generalizing Swendsen–Wang for Image Analysis

Markov chain Monte Carlo (MCMC) methods have been used in many fields (physics, chemistry, biology, and computer science) for simulation, inference, and optimization. In many applications, Markov chains are simulated for sampling from target probabilities π(X) defined on graphs G. The graph vertices represent elements of the system, the edges represent spatial relationships, while X is a vector of variables on the vertices which often take discrete values called labels or colors. Designing efficient Markov chains is a challenging task when the variables are strongly coupled. Because of this, methods such as the single-site Gibbs sampler often experience suboptimal performance. A well-celebrated algorithm, the Swendsen–Wang (SW) method, can address the coupling problem. It clusters the vertices as connected components after turning off some edges probabilistically, and changes the color of one cluster as a whole. It is known to mix rapidly under certain conditions. Unfortunately, the SW method has limited applicability and slows down in the presence of “external fields;” for example, likelihoods in Bayesian inference. In this article, we present a general cluster algorithm that extends the SW algorithm to general Bayesian inference on graphs. We focus on image analysis problems where the graph sizes are in the order of 10³–10⁶ with small connectivity. The edge probabilities for clustering are computed using discriminative probabilities from data. We design versions of the algorithm to work on multi grid and multilevel graphs, and present applications to two typical problems in image analysis, namely image segmentation and motion analysis. In our experiments, the algorithm is at least two orders of magnitude faster (in CPU time) than the single-site Gibbs sampler.     

A theoretical investigation of regular equivalences for fuzzy graphs

The notion of regular equivalence or bisimulation arises in different applications, such as positional analysis of social networks and behavior analysis of state transition systems. The common characteristic of these applications is that the system under modeling can be represented as a graph. Thus, regular equivalence is a notion used to capture the similarity between nodes based on their linking patterns with other nodes. According to Borgatti and Everett, two nodes are regularly equivalent if they are equally related to equivalent others. In recent years, fuzzy graphs have also received considerable attention because they can represent both the qualitative relationships and the degrees of connection between nodes. In this paper, we generalize the notion of regular equivalence to fuzzy graphs based on two alternative definitions of regular equivalence. While the two definitions are equivalent for crisp graphs, they induce different generalizations for fuzzy graphs. The first generalization, called regular similarity, is based on the characterization of regular equivalence as an equivalence relation that commutes with the underlying graph edges. The regular similarity is then a fuzzy binary relation that specifies the degree of similarity between nodes in the graph. The second generalization, called generalized regular equivalence, is based on the definition of coloring. A coloring is a mapping from the set of nodes to a set of colors. A coloring is regular if nodes that are mapped to the same color, have the same colors in their neighborhoods. Hence, generalized regular equivalence is an equivalence relation that can determine a crisp partition of the nodes in a fuzzy graph.     

Probabilistic Inductive Classes of Graphs

A unifying framework—probabilistic inductive classes of graphs (PICGs)—is defined by imposing a probability space on the rules and their left elements from the standard notion of inductive class of graphs. The rules can model the processes creating real-world social networks, such as spread of knowledge, dynamics of acquaintanceships or sexual contacts, and emergence of clusters. We demonstrate the characteristics of PICGs by casting some well-known models of growing networks in this framework. Results regarding expected size and order are derived. For PICG models of connected and 2-connected graphs order, size and asymptotic degree distribution are presented. The approaches used represent analytic alternative to computer simulation, which is mostly used to obtain the properties of evolving graphs.     

Introducing situational signs in qualitative probabilistic networks

A qualitative probabilistic network is a graphical model of the probabilistic influences among a set of statistical variables, in which each influence is associated with a qualitative sign. A non-monotonic influence between two variables is associated with the ambiguous sign ‘?’, which indicates that the actual sign of the influence depends on the state of the network. The presence of such ambiguous signs is undesirable as it tends to lead to uninformative results upon inference. In this paper, we argue that, although a non-monotonic influence may have varying effects, in each specific state of the network, its effect is unambiguous. To capture the current effect of the influence, we introduce the concept of situational sign. We show how situational signs can be used upon inference and how they are updated as the state of the network changes. By means of a real-life qualitative network in oncology, we show that the use of situational signs can effectively forestall uninformative results upon inference.     

Effective dimensions of partially observed polytrees

Model complexity is an important factor to consider when selecting among Bayesian network models. When all variables are observed, the complexity of a model can be measured by its standard dimension, i.e., the number of linearly independent network parameters. When latent variables are present, however, standard dimension is no longer appropriate and effective dimension should be used instead [Proc. 12th Conf. Uncertainty Artificial Intell. (1996) 283]. Effective dimensions of Bayesian networks are difficult to compute in general. Work has begun to develop efficient methods for calculating the effective dimensions of special networks. One such method has been developed for partially observed trees [J. Artificial Intell. Res. 21 (2004) 1]. In this paper, we develop a similar method for partially observed polytrees.     

Random walks and flights over connected graphs and complex networks

Markov chains provide us with a powerful probabilistic tool that allows to study the structure of connected graphs in details. The statistics of events for Markov chains defined on connected graphs can be effectively studied by the method of generalized inverses which we review. The approach is also applicable for directed graphs and interacting networks which share the set of nodes. We discuss a generalization of Lévy flight random walks for large complex networks and study the interplay between the nonlinearity of diffusion process and the topological structure of the network.     

On the transformation between possibilistic logic bases and possibilistic causal networks

Possibilistic logic bases and possibilistic graphs are two different frameworks of interest for representing knowledge. The former ranks the pieces of knowledge (expressed by logical formulas) according to their level of certainty, while the latter exhibits relationships between variables. The two types of representation are semantically equivalent when they lead to the same possibility distribution (which rank-orders the possible interpretations). A possibility distribution can be decomposed using a chain rule which may be based on two different kinds of conditioning that exist in possibility theory (one based on the product in a numerical setting, one based on the minimum operation in a qualitative setting). These two types of conditioning induce two kinds of possibilistic graphs. This article deals with the links between the logical and the graphical frameworks in both numerical and quantitative settings. In both cases, a translation of these graphs into possibilistic bases is provided. The converse translation from a possibilistic knowledge base into a min-based graph is also described.     

Efficient Bayesian Inference for Generalized Bradley–Terry Models

The Bradley–Terry model is a popular approach to describe probabilities of the possible outcomes when elements of a set are repeatedly compared with one another in pairs. It has found many applications including animal behavior, chess ranking, and multiclass classification. Numerous extensions of the basic model have also been proposed in the literature including models with ties, multiple comparisons, group comparisons, and random graphs. From a computational point of view, Hunter has proposed efficient iterative minorization-maximization (MM) algorithms to perform maximum likelihood estimation for these generalized Bradley–Terry models whereas Bayesian inference is typically performed using Markov chain Monte Carlo algorithms based on tailored Metropolis–Hastings proposals. We show here that these MM algorithms can be reinterpreted as special instances of expectation-maximization algorithms associated with suitable sets of latent variables and propose some original extensions. These latent variables allow us to derive simple Gibbs samplers for Bayesian inference. We demonstrate experimentally the efficiency of these algorithms on a variety of applications.