Dynamic Bayesian network state prediction based on variable relationship

Abstract

In order to improve the accuracy of the state prediction model, a dynamic Bayesian network state prediction model based on the relationship of prediction variables is designed. The prediction model of dynamic Bayesian network structure learning algorithm was improved, integrated into the Gibbs sampling algorithm model prediction, joined the predicted relationship between different factors affecting the node, is given based on the variable relationship between the dynamic Bayesian network structure design, using a moment on the different nodes and state influence factors to predict the probability distribution of the moment state nodes. The experimental results show that the model is simple in structure, more accurate than the traditional learning method of Bayesian network structure, and more practical.

Keywords

Dynamic Bayesian network designing of networks structure the state prediction model the probability distribution

1. Introduction

At present, there are two main methods for learning Bayesian network structure. One is the scoring search [1] learning method, the basic idea is to traverse all possible structures, and then use a standard to measure each structure, and then find the best structure. This method is simple and standard, but it requires the operation of scoring function and the search of structure space to increase the complexity of operation exponentially with the increase of variables. Therefore, it is only suitable for local learning or heuristic learning with certain structure prior knowledge. The other is a learning method based on dependency analysis. The core idea of this method is: firstly, conduct statistical tests on training data sets, especially conditional independence tests, to determine the conditional independence between variables; Then, a directed acyclic graph is constructed by using the conditional independence between variables to cover as much of these conditional independence as possible. In fact, it is to find a measure that can best fit with a given instance data set, the former is called network parameter learning, the latter is called network structure learning. Therefore, structural learning is an important part of Bayesian network learning. In addition, through the variable conditions between independence test and $d$ – separation standard to determine the existence and direction of edge, complicated algorithm, when the potential of Bayesian network structure is more complex, the algorithm’s time complexity is intolerable, but with polynomial complexity but in the real application, most of the data set on the potential of Bayesian network is sparse directed acyclic graph, so this method can be applied in the actual problem.

With the application of Bayesian network in computational biology, engineering and many other fields, the learning method of network structure in the construction of Bayesian model can be improved to play a greater role. In view of the shortcomings of the traditional learning methods, such as long computation time, difficult reasoning and low efficiency, this paper combines the above two algorithms to improve the Bayesian network structure learning algorithm based on the prediction relationship of prediction variables, which can more accurately infer the Bayesian network structure. After the Bayesian network structure is determined, we give the state prediction model, which can fully reflect the dependence between different influencing factors and state nodes at adjacent moments, as well as the dependence between influencing factors and state nodes at the same time, so as to improve the accuracy of the prediction model.

2. Dynamic Bayesian network

Dynamic Bayesian network is an extension of Bayesian network modeling, and also it is a series timely process. Its set of random variables can evolve over time and is a compressed representation of complex random processes. The widely used Markov chain [2] prediction is a typical application of dynamic Bayesian networks for prediction. A general dynamic Bayesian network has two characteristics:

1)
The topology of the network is the same in each time slice, and the slices are connected by a similar arc;
2)
The network at time $t$ is only. It is related to the network at times $t+1$ and $t-1$ , and has nothing to do with other network slices.

Figure 1.
Simplified initial network and transfer network.

Figure 1 simplified initial network and transfer network. Assume $x=\{X_{1},X_{2},\ldots,X_{n}\}$ is a collection of random variables that evolve over time, $X_{i}[t]$ is the time $t$ variable $X_{1}$ Value, $X[t]$ random variable $X_{i}[t]$ collection, the distribution of random processes can be expressed as

$\displaystyle P(X\left[1\right],X\left[2\right],\ldots,P(X\left[t\right])=P([X% _{1}])P([X_{2}\left|{X_{1}}\right.])\ldots P(X[t]\left|{X[1],\ldots X[t-1]}% \right.)$ (1)

Based on the dynamic Bayesian network characteristics 1), the evolution of dynamic Bayesian networks can be simplified to the initial Bayesian network. $B_{0}$ and the joint distribution of the transfer network $b\to$ in the result that an ordered pair can be used ( $B_{0}$ , $B\to$ ) represents a dynamic Bayesian network, as shown in Fig. 1. Based on this, the above formula can be simplified as:

$\displaystyle P_{B}(X\left[0\right],\ldots X\left[T\right])=P_{B_{0}}(X\left[0% \right])P_{B\to}^{T}(X\left[1\right]\left|{X\left[0\right]}\right.)$ (2)

In the term of the dynamic Bayesian network characteristics 2), the above formula can be simplified as

$\displaystyle P(X\left[1\right],X\left[2\right],\ldots,P(X\left[t\right])=P([X% _{1}])P([X_{2}\left|{X_{1}}\right.])\ldots P(X[t]\left|{X[t-1]}\right.)$ (3)
3. Bayesian network structure learning algorithm based on variable relationship

Bayesian network structure [3] learning algorithm based on predictive variable prediction relationship has two main parts:

(1)
Establishing initial Bayesian network structure based on absolute prediction ability;
(2)
Adjusting initial Bayesian based on conditional prediction ability Network structure (increasing the missing arc, removing the extra arc, adjusting the direction of the arc).

3.1 Prediction relationship between different influencing factors

Discrete influence factor node $X_{1}$ , $X_{2}$ , $\ldots$ , $X_{n}$ , $x_{1}$ , $x_{2}$ , $\ldots$ , $x_{n}$ . The value of the influencing factor node; D is the influencing factor node $X_{1}$ , $X_{2}$ , $\ldots$ , $X_{n}$ . The resulting size is a random data set of N.

Definition 1: Remember $f$ ( $X_{i}\to X_{i}$ ). As a variable $X_{i}$ self-predictive ability,

$\displaystyle f(X_{i}\to X_{i})=\max X_{i}\{P(X_{i})\}$ (4)

Definition 2: Remember $f(X_{m_{1}},\ldots,X_{m_{t}}\to X_{i})$ is a variable group $X_{m_{1}},\ldots,X_{m_{t}}$ pair of variables $X_{i}$ predictive ability,

$\displaystyle F(X_{m_{1}},\ldots,X_{m_{t}}\to X_{i})=\sum\limits_{X_{m_{1}}}% \ldots\sum\limits_{X_{m_{t}}}P(X_{m_{1}}\ldots X_{m_{t}})$ (5) $\displaystyle\mathop{\max}\limits_{X(X_{m_{1}}\ldots X_{m_{t}})}\left\{P\left% \langle X_{i}|X_{m_{1}}\ldots X_{m_{t}}\right\rangle\right\},m_{j}\neq i，j=1% ,\ldots,t$

Definition 3: If

$\displaystyle P(X_{i}|X_{m_{1}},\ldots,X_{m_{t}},X_{j})=P((X_{i}|X_{m_{1}},% \ldots,X_{m_{t}})$ (6)

Established $X_{m_{1}},\ldots,X_{m_{t}}$ conditional variable $X_{i}$ versus $X_{j}$ . The conditions are independent.

3.2 Bayesian network structure learning algorithm description based on variable relationship

Based on the definition of the prediction relationship between the nodes of different influencing factors, we will give a description of the Bayesian structure [4] learning algorithm based on the prediction relationship of predictors. The specific steps are as follows: $p_{i}=p_{o}=p_{s}=\alpha$ .

Step 1 calculates the predictive power between nodes.

Step 2 determines the initial Bayesian network structure.

$\displaystyle\text{If}\ \frac{F(X_{j}\to X_{i})}{F(X_{i})}\succ\frac{F(X_{i}% \to X_{j})}{F(X_{j})}$ (7) $\displaystyle\max\left\{{\frac{F(X_{j}\to X_{i})}{F(X_{i})},\frac{F(X_{i}\to X% _{j})}{F(X_{j})}}\right\}\succ P_{i}$ (8)

then oriented ( $X_{j}\to X_{i}$ ).

$\displaystyle\text{If}\ \frac{F(X_{i}\to X_{j})}{F(X_{j})}\succ\frac{F(X_{j}% \to X_{i})}{F(X_{i})}$ (9)

$\displaystyle\max\left\{{\frac{F(X_{i}\to X_{j})}{F(X_{j})},\frac{F(X_{j}\to X% _{i})}{F(X_{i})}}\right\}\succ P_{i}$ (10)

then oriented ( $X_{j}\to X_{i}$ )

$\displaystyle\text{If}\ \frac{F(X_{i}\to X_{j})}{F(X_{j})}\prec P_{s}\bigcap{% \frac{F(X_{j}\to X_{i})}{F(X_{i})}}\prec P_{s}$ (11)

then random orientation.

Step 3 increases the missing arc, mincutset ( $X_{i},X_{j}$ ) is minimum d-separating set of a variable $X_{i}$ and $X_{j}$ .

$\displaystyle\text{min{\_}cutset1}=\text{find (mincutset}(X_{i},X_{j}))$ (12)

$\displaystyle\text{if}\ \frac{F(\min\_\textit{cutset1},X_{j}\to X_{i})}{F(\min% \_\textit{cutset1}\to X_{i})}\succ\frac{F(\min\_\textit{cutset1},X_{i}\to X_{j% })}{F(\min\_\textit{cutset1}\to X_{j})}$ (13)

and

$\displaystyle\max\left\{{\frac{F(\min\_\textit{cutset1},X_{j}\to X_{i})}{F(% \min\_\textit{cutset1}\to X_{i})}\succ\frac{F(\min\_\textit{cutset1},X_{i}\to X% _{j})}{F(\min\_\textit{cutset1}\to X_{j})}}\right\}\succ P_{\lambda}$ (14)

then oriented ( $X_{j}\to X_{i}$ )

$\displaystyle\text{if}\ \frac{F(\min\_\textit{cutset1},X_{i}\to X_{j})}{F(\min% \_\textit{cutset1}\to X_{j})}\succ\frac{F(\min\_\textit{cutset1},X_{j}\to X_{i% })}{F(\min\_\textit{cutset1}\to X_{i})}$ (15)

$\displaystyle\max\left\{{\frac{F(\min\_\textit{cutset1},X_{i}\to X_{j})}{F(% \min\_\textit{cutset1}\to X_{j})}\succ\frac{F(\min\_\textit{cutset1},X_{j}\to X% _{i})}{F(\min\_\textit{cutset1}\to X_{i})}}\right\}\succ P_{i}$ (16)

then oriented ( $X_{j}\to X_{i})$ .

Step 4 removes the extra arc

$\displaystyle\text{min{\_}cutset2}=\text{find (mincutset}(X_{i}\to X_{j}))$ (17)

$\displaystyle\text{if}\ \frac{F(\min\_\textit{cutset2},X_{j}\to X_{i})}{F(\min% \_\textit{cutset2}\to X_{i})}\prec P_{o}\bigcap\frac{F(\min\_\textit{cutset2},% X_{i}\to X_{j})}{F(\min\_\textit{cutset2}\to X_{j})}\prec P_{o}$ (18)

then delete (arc( $X_{i},X_{j})$ ).

Step 5 adjusts the direction of the arc

$\displaystyle\text{min{\_}cutset3}=\text{find}(\text{mincutset}(X_{i}X_{j}))$ (19)

$\displaystyle\text{if}\ \frac{F(\min\_\textit{cutset3},X_{j}\to X_{i})}{F(\min% \_\textit{cutset3}\to X_{i})}\succ\frac{F(\min\_\textit{cutset3},X_{i}\to X_{j% })}{F(\min\_\textit{cutset3}\to X_{j})}$ (20)

then oriented ( $X_{j}\to X_{i}$ ).

$\displaystyle\text{if}\ \frac{F(\min\_\textit{cutset3},X_{i}\to X_{j})}{F(\min% \_\textit{cutset3}\to X_{j})}\succ\frac{F(\min\_\textit{cutset3},X_{j}\to X_{i% })}{F(\min\_\textit{cutset3}\to X_{i})}$ (21)

then oriented ( $X_{j}\to X_{i}$ ).

The discrete Bayesian network structure learning algorithm based on the predictive ability between variables has the following characteristics:

(1)

High learning efficiency and accuracy;

(2)

Building a Bayesian network structure based on predictive ability to make the learned structure tend to be simple so that this can avoid over-fitting of data;

(3)

It can process incomplete data, does not require variable ordering, and has anti-noise data function.

4. State prediction model

The state model [5] can be constructed under the condition that the above-mentioned Bayesian network structure and assumption parameters are known. The model proposed in this paper contains two nodes: state node and influencing factor node; and three kinds of dependencies: the dependence between different influencing factors and state nodes in adjacent time and the influencing factors. The dependency between the state nodes. There is only one state node and multiple influencing factor nodes at the same time. The general idea of the prediction F165 algorithm proposed in this paper is: when the value of the influencing factor is unknown at this moment, the Gibbs sampling prediction algorithm is used to predict the probability distribution of the influencing factors at that moment based on the value of the influencing factor at the previous moment. Then combine the value of the state node at the previous moment to predict the current state.

4.1 Gibbs sampling prediction algorithm

The Gibbs sampling prediction algorithm is a simple MCMC (Markov chain-Monte Carlo) method. The MCMC method is an important random method related to statistical physics, which is widely used in Bayesian inference and machine learning. The Gibbs sampling prediction algorithm has the advantages of simplicity and fast calculation speed, and is a local optimization algorithm. The algorithm for finding a model based on the Gibbs sampling prediction algorithm is as follows:

choose randomly $\left\{{x_{1}^{0},x_{2}^{0},\ldots,x_{n}^{0}}\right\}$ Recorded as $X_{0}$ , calculating the counting matrix $C_{i,j}^{0}$ Position weight matrix $Q_{i,j}$ ;

While (Count matrix $C_{i,j}^{0}$ Does not converge).

For (scan all sequences in sequence).

Select $x_{i}^{n}$ The first time taking $i=1$ , $n=$ 0, put back the original sequence and recalculate the counting matrix. $C_{i,j}^{0}$ Position weight matrix $Q_{i,j}$ ;

Sampling update: calculating the fitness of the model $A_{x}$ , $i=i+1$ ,

End For

$\displaystyle n=n+1$ (22)

End While.

Finally, the output convergence counting matrix is obtained, and the pseudo-calculation probability matrix is calculated $Q_{c_{i,j}}$ . And the prediction model is output.

4.2 Support between nodes

In order to measure the degree of influence between random events, we propose the concept of support between events, which supports positive values, regardless of the negative effects between events. Regarding the support between events, we give the following definitions:

Definition 4: An event $y_{j}$ Given another event $x_{i}$ information definition is called mutual information, using $i$ ( $x_{i};y_{j}$ ) said. $I(x_{i};y_{j})=I(x_{i})-I\left({x_{i}\left|{y_{j}}\right.}\right)=\log\frac{p(% x_{i}\left|{y_{j}}\right.)}{p(x_{i})}$ when $x_{i}$ with $y_{j}$ When they are independent of each other, $i(x_{i}$ ; $y_{j})=$ 0. Different random events will have different effects on the same random event, some will promote the occurrence of random events, and some will hinder the occurrence of random events.

Based on this, we give the definition of the degree of support of the influencing factor node to the state node: if the values of the $d$ influencing factors are known respectively $v_{11_{i}}$ , $v_{22_{i}}$ , $\ldots$ , $v_{dd_{i}}$ , then the d influencing factors on the state $q_{j}$ . The support is:

$\displaystyle\lambda_{j}^{\prime}=\sum\limits_{l=1}^{d}{I(q_{j};v_{ll_{i}})}$

4.3 State prediction algorithm

Based on the construction of dynamic Bayesian network [6] and the predictive relationship, this paper uses the Bayesian network inference method and the Gibbs sampling prediction algorithm to predict the state. The steps of the complete state prediction algorithm are as follows:

•
After obtaining the value of the influencing factor at the last moment, the Gibbs sampling prediction algorithm is used to predict the probability distribution of the influencing factors at that moment;
•
Calculate the support level of the influencing factor node to the state node;
•
Calculating the support of the state node of the previous time to the state node at the current time;
•
Using the support obtained in step 3) to correct the support results obtained in step 2);

End.
5. Experiment and analysis of results

The dynamic Bayesian network state prediction model [7] is generated according to the constructed Bayesian network structure and state prediction algorithm based on the variable prediction relationship [8]. The model and the traditional model were used to predict the pond water quality, and then compared with the actual measured pond water quality to obtain the prediction accuracy of the dynamic Bayesian network state prediction model and the traditional model. The measured parameters of pond water quality factors include water temperature, dissolved oxygen, ammonia nitrogen, total phosphorus, total nitrogen, permanganate, etc. According to expert knowledge and consulting related books, the obtained data will be discretized accordingly. After the water quality is divided into five grades, the pre-processed parameter data is input into the prediction model to predict the model accuracy. The test results are shown in Table 1.

Table 1
Experimental result data

Group	Typical number of cases	Number of traditional cases tested	Revised the number of cases	Diagnose the correct number of cases	Traditional accuracy	Corrected accuracy
1	321	87	74	67	77.01%	90.54%
2	510	109	97	90	82.57%	92.78%
3	763	248	230	213	85.89%	92.60%
4	950	342	320	285	83.33%	89.06%
5	439	101	88	79	78.22%	89.77%
6	820	261	246	224	85.82%	91.05%
7	166	62	50	46	74.19%	92.00%
8	998	346	331	298	86.13%	90.03%

Experiments show that the dynamic Bayesian network based on predicted link state prediction model is not only simple in structure, and high accuracy, is larger than the traditional model, basic can achieve about 90%, and the typical cases, some cases with missing data, through the experiment proved that the model can deal with missing data, also can prevent data for fitting phenomenon, is one of the better state prediction model, is worthy of application.

6. Conclusions

This paper proposes a dynamic Bayesian network state prediction model based on prediction relationship. The construction of dynamic Bayesian network model mainly includes network structure learning and probability table construction. In the construction of the network model, firstly, we consider the prediction relationship between the nodes of different influencing factors and establish the Bayesian network structure [9]. On this basis, we not only consider the influence relationship between the state nodes but also introduce the state prediction algorithm is established by the dependence between the influencing factor node and the state node and the different influencing factors at the adjacent time. The proposed dynamic Bayesian network structure based on the prediction relationship can simplify the structure obtained by learning, prevent over-fitting, and has high accuracy. The state prediction algorithm uses the influencing factor node of the previous moment to predict the current state [10]. The probability distribution of the node is corrected by the state node at the previous moment, which greatly improves the accuracy of the state prediction model. In summary, the dynamic Bayesian network state prediction based on prediction relationship combines the advantages of dynamic Bayesian network structure and state prediction model based on prediction relationship, and improves the prediction accuracy of the model.

Footnotes

Acknowledgments

Supported by “the Fundamental Research Funds for the Central Universities” (2242018k30002); National key research and development program of the 13th five-year plan (No. 2018YFF0213601); Supported by the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Grant No. 18KJB510038); supported by the Funds of Nantong Applied Basic Research Plan (GY12017015).

References

Wee

Y.Y.

Cheah

W.P.

Tan

S.C.

et al., A method for root cause analysis with a bayesian belief network and fuzzy cognitive map, Expert Systems with Applications 42(1) (2015), 468–487.

Kaynar

, A taxonomy for attack graph generation and usage in network security, Journal of Information Security and Applications 29(C) (2016), 27–56.

Chen

X.Y.

, Research on Bayesian network structure learning algorithm based on kl distance, Kunming: Graduate School of Yunnan University, 2012.

R.G.

Zhang

H.Q.

et al., Security risk measurement method for vulnerability life cycle, Journal of Software 29(5) (2018), 1213–1229.

Tryfonas

Russell

and Andriotis

, Risk assessment for mobile systems through a multilayered hierarchical Bayesian network, IEEE Transaction on Cybernetics 46(4) (2016), 1749–1759.

Jiao

R.Q.

, Selection of regularization parameters in bayesian penalty regression, Southwest jiaotong university, 2017.

Korb

and Nicholson

A.E.

, Bayesian Artificial Intelligence, Chapman & Hall/CRC, 2nd edition, 2010.

Fan

and Yuan

, An Improved Lower Bound for Bayesian Network Structure Learning, AAAI Conference on Artificial Intelligence, 2015.

Nielsen

A.M.

, Neural Networks and Deep Learning, Determination Press, 2015.

10.

Huang

K.K.

Wen

F.D.

Zhang

Y.C.

and Zhu

H.Q.

, Sparse Bayesian learning for network structure reconstruction based on evolutionary game data, Hysica A: Statistical Mechanics and its Applications (2020), 541.

11.

Scanagatta

Salmerón

and Stella

, A survey on Bayesian network structure learning from data, Progress in Artificial Intelligence 8(4) (2019).

12.

Wee

Y.Y.

Cheah

W.P.

Tan

S.C.

et al., A method for root cause analysis with a bayesian belief network and fuzzy cognitive map, Expert Systems with Applications 42(1) (2015), 468–487.

13.

Kaynar

, A taxonomy for attack graph generation and usage in network security, Journal of Information Security and Applications 29(C) (2016), 27–56.

14.

Chen

, Research on Bayesian network structure learning algorithm based on kl distance, Kunming: Graduate School of Yunnan University, 2012.

15.

Zhang

et al., Security risk measurement method for vulnerability life cycle, Journal of Software 29(5) (2018), 1213–1229.

16.

Tryfonas

Russell

and Andriotis

, Risk assessment for mobile systems through a multilayered hierarchical Bayesian network, IEEE Transaction on Cybernetics 46(4) (2016), 1749–1759.

17.

Jiao

, Selection of regularization parameters in bayesian penalty regression, Southwest jiaotong university, 2017.

18.

Korb

and Nicholson

A.E.

, Bayesian Artificial Intelligence. Chapman& Hall/CRC, 2nd edition, 2010.

19.

Fan

and Yuan

, An Improved Lower Bound for Bayesian Network Structure Learning//AAAI Conference on Artificial Intelligence, 2015.

20.

Michael

, Nielsen, Neural Networks and Deep Learning. Determination Press, 2015.

21.

Huang

Deng

Zhang

and Zhu

, Sparse Bayesian learning for network structure reconstruction based on evolutionary game data, Physica A: Statistical Mechanics and its Applications (2020), 541.

22.

Scanagatta

Salmerón

and Stella

, A survey on Bayesian network structure learning from data, Progress in Artificial Intelligence 8(4) (2019).

Dynamic Bayesian network state prediction based on variable relationship

Abstract

Keywords

1. Introduction

2. Dynamic Bayesian network

4.1 Gibbs sampling prediction algorithm

4.3 State prediction algorithm

Table 1 Experimental result data

Footnotes

Acknowledgments

References

Table 1
Experimental result data