“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Introduction to the

The above chapter mainly introduces the definition of Bayes and some basic contents of the structural form of Bayes. Now this chapter mainly introduces the definition of Bayesian network and the structure learning of Bayesian network.

Bayesian network

Definition of Bayesian networks

It consists of structure G and parameter θ. Structure G is a directed acyclic graph G= (V, E), where the node set is V={X1, X2… The directed edge set E describes the dependencies between variables. Parameter Θ into a set of conditional probability distribution of each node is stored between itself and its parent set conditional probability distribution of the P (Xi | Pa (Xi), Pa (Xi) on behalf of the Xi father node set. At the same time, Bayesian network also includes qualitative and quantitative parts. G is the qualitative knowledge representation of the model, which is used to describe the probabilistic dependence or independent relationship between variables. The direction of arc has a causal definition, which can be used for causal reasoning. θ is the quantitative knowledge representation of the model and is used to express the degree of probability dependence among variables.

From the perspective of algorithm, Bayesian network is divided into structure learning and parameter learning, and parameter learning is built on the basis of known structure, so network structure learning is the key. And BN structure learning algorithm can be divided into accurate learning algorithm and approximate learning algorithm. The exact learning algorithm presents BN reasoning and learning problems as function optimization. By traversing the entire search space, it can guarantee to find the global optimal solution, but it is limited by memory and running time. The approximate learning algorithm searches the space of possible solutions through efficient meta-heuristic algorithm to obtain good solutions.

Bayesian structure learning

BN structure learning under complete data:

The main idea of BN structure learning is to select a network structure that best conforms to the logic of given data set and has the best fitting effect from several Bayesian networks obtained by inference based on the sample set of generated data. The difficulty is that the search space increases exponentially as the number of nodes n increases.

There are two methods to construct the structure of Bayesian network, one is manually constructed by experts’ domain experience (empiricism), the other is obtained by data analysis (posteriori). The first one is suitable for the network structure with few network variables and obvious causal relationship between them. The disadvantage is that it has obvious subjective judgment, and different network structures can be obtained from different sequence of variables. The second algorithm is based on data mining to obtain the bayesian network structure with the highest degree of fitting with the data set. The disadvantage is that the accurate algorithm cannot find the optimal solution in a limited time, and the approximate heuristic search method cannot obtain the optimal solution.

Under complete data, BN approximate structure learning algorithm can be divided into three types: independent test based, scoring based search and hybrid search.

Structure learning based on independence test:

The method of independence test regards BN network as a network model representing the relationship of independent variables, finds the relationship between nodes by calculating mutual information and conditional independence to judge the existence of edges in the network, and finally finds a network structure conforming to the independent relationship. Mutual information represents the extent to which a variable contains information about another variable, and conditions represent independently whether the change of a variable will affect another variable.

remarks

This chapter first introduces the definition of Bayesian network, and then preliminarily introduces the branches of Bayesian network. The following chapters will introduce the specific content of Bayesian network structure learning in detail.

Reappearance of past classics

• Bayes review (1) – Gold Digging (juejin. Cn)