Bayesian network

A Bayesian network or Bayesian network ( named after Thomas Bayes ) is a directed acyclic graph (DAG ), in which the nodes random variables and the edges describe conditional dependencies between variables. Each node of the network is given a conditional probability distribution of the random variable represented by him, assigns the random variables at the parent node. They are described by probability tables. This distribution can be arbitrary, but is frequently performed with discrete or normal distributions. Parent of a node v are those nodes from which leads an edge to v.

A Bayesian network is used to represent the joint probability distribution of all the variables involved as compact as possible by exploiting conditional independences known. The conditional (in) dependence of subsets of variables with the a priori knowledge is combined.

If X1, ..., Xn occurring in some of the graphs random variables (which are closed under addition of parental variables), as calculated their joint distribution as

Has no parents a node, then it is in the associated probability distribution for the unconditional distribution.

  • 3.1 Parameter learning
  • 3.2 Structure Learning

Example

Close in Bayesian networks

Is of some of the variables, such as E1, ..., Em, of the known value, i.e., is located in front of evidence, it is possible by means of various algorithms, the conditional probability distribution of X1, ..., Xn, where E1, ... , Em calculated and thus inference be operated.

The inference problem, both the exact as well as the approximate, in Bayesian networks is NP-hard. In larger networks, but the attempt at approximate method. Although exact procedures are somewhat more accurate than approximate, but this frequently takes place in practice, only a minor role, as Bayesian networks are used for decision making, where the exact probabilities are not required.

Is to be observed that in software implementations of exact inference methods often only double-precision floating-point numbers are used. This improves the accuracy of these calculations is limited.

Exact inference

For exact inference in Bayesian networks, inter alia, the following algorithms are:

  • Variable elimination
  • Clustering algorithms

Approximate inference

  • Rejection sampling
  • Likelihood weighting
  • Self- Importance
  • Adaptive Importance
  • Markov chains
  • Monte Carlo algorithm, for example, Gibbs Sampling

Inferenztypen

  • Diagnosis: from effects to causes
  • Causal: from causes to effects
  • Inter causal: Between causes of a common effect
  • Mixed: combination of the foregoing,

Learning Bayesian networks

Target from the available data automatically a Bayesian network can be generated that describes the data as well as possible, then provide two possible problems: Either the graph structure of the network is already in place and one must no longer about identifying conditional independences, but only care for the calculation of the conditional probability distributions at the nodes of the network, or you have to learn a structure of a suitable network in addition to the parameters.

Parameter learning

If it is not from a full ( Bayesian ) probability model, is generally chosen

  • Maximum likelihood estimate ( MLE)

As estimation method. In the event of a complete ( Bayesian ) probability model ideally suited for the point estimate of the

  • Maximum a posteriori estimation (MAP)

Of. Local maxima of the likelihood or A - Posteriorifunktionen, in the case of complete data and fully observed variables commonly associated with conventional optimization algorithms such as

  • Gradient or
  • Newton -Raphson method

Be found. ( To be regarded as the rule) In the case of missing observations is usually the powerful and widely used

  • Expectation-Maximization algorithm ( EM), or the
  • Generalized Expectation-Maximization algorithm ( GEM)

Be used.

Structure learning

May, inter alia, with the structure learning algorithm K2 ( approximate, using a suitable objective function ) take place or the PC algorithm.

Conditional independence

For determining conditional independencies of two variable quantities optionally a third amount such it is sufficient to examine the structure of the network graph. One can show that the ( graph-theoretic ) notion of d- separation coincides with the concept of conditional independence.

Application

Bayesian networks are used as a form of probabilistic expert systems, the application areas are, among others, in bioinformatics, pattern analysis, medicine and engineering. In the tradition of artificial intelligence the focus of Bayesian networks is on the utilization of those graphic structures to enable abductive and deductive conclusions that would be unfeasible in a unfaktorisierten probability model. This is realized by the different inference algorithms.

The basic idea of Bayesian networks, namely the graphical factorization of a probability model is used in other traditions, such as in Bayesian statistics and in the tradition of the so-called graphical models for purposes of data modeling. Areas of application are, above all epidemiology, medicine and social sciences.

Software

  • Genie / Smile
  • Bnlearn R package
Gibbs-Sampling Expectation–maximization algorithm Abductive reasoning
110021
de