Method for establishing fault diagnosis technique based on contingent Bayesian networks

Abstract

A method for establishing fault diagnosis technique based on contingent Bayesian networks, comprising steps of: step (1) determining a domain of an unknown object to be reasoned; step (2) defining a model structure by adopting a first-order logic language; step (3) generating a Blog model; step (4) transforming the Blog model into the contingent Bayesian networks; step (5) defining the contingent Bayesian networks; step (6) learning parameters of the contingent Bayesian networks; and step (7) reasoning a fault of the contingent Bayesian networks by utilizing a Markov chain Monte Carlo Method. By the steps mentioned above, establishing fault diagnosis technique based on contingent Bayesian networks is achieved.

Claims

1. A method for establishing fault diagnosis technique based on contingent Bayesian networks, comprising steps of: step (1) determining a domain of an unknown object to be reasoned; step (2) defining a model structure by adopting a first-order logic language; step (3) generating a Blog model; step (4) transforming the Blog model into the contingent Bayesian networks; step (5) defining the contingent Bayesian networks; step (6) learning parameters of the contingent Bayesian networks; and step (7) reasoning a fault of the contingent Bayesian networks by utilizing a Markov chain Monte Carlo Method; wherein by steps mentioned above, establishing the fault diagnosis technique based on the contingent Bayesian networks is completed; based on a contingent Bayesian networks theory, the Blog model is established by an unknown quantity of interferences of fault phenomenon and fault environment; and then the Blog model is transformed into the contingent Bayesian networks; and finally the fault of the contingent Bayesian networks is reasoned by utilizing the Markov chain Monte Carlo Method; the present invention is suitable for solving practical software faults diagnosis problems; adopting the technique is capable of fully taking advantage characteristics of contingent Bayesian networks of having rings and containing an infinite number of variables, so as to meet actual diagnostic requirements of random faults of embedded software, improve quality of fault diagnosis, and possess high practical application value.

2. The method for establishing fault diagnosis technique based on the contingent Bayesian networks, as recited in claim 1, wherein the step (1) of determining a domain of an unknown object to be reasoned comprises steps of: determining a type of software fault in which an amount of software to be tested is unknown and a type of environmental constrain that the software is facing during operation by software testing; wherein Fault represents software fault, Constrain represents environmental constrain which causes fault; amounts of both the Fault and Constrain are unknown.

3. The method for establishing fault diagnosis technique based on the contingent Bayesian networks, as recited in claim 1, wherein in the step (2) defining the model structure by adopting the first-order logic language, the first-order logic language which is typed comprises a set of type symbols and a set of functor symbols f, each of the functor symbols f has a type tag ts(t.sub.1, . . . , t.sub.i, . . . , t.sub.or), wherein i=1, 2, . . . , or, each of the t.sub.i is a type symbol, or is an order of a functor symbol, if or=0, the functor symbol is a constant symbol; meanwhile, each of the functor symbol f has a return value R, and the return value R is a null value null; wherein W represents a defined model structure, W defines an extension of each type, an interpretation of each function statement, and specifies object sets exist in each type and values of each function symbol; W comprises extensions [R].sup.w of each type, wherein [R].sup.w is a set of objects of the type in W, an extension of the type symbols t.sub.i is denoted as [t.sub.i].sup.w each of the functor symbols f comprises an explanation [f].sup.w, wherein [f].sup.w is a function at a range of [t.sub.i].sup.w to [R].sup.w.

4. The method for establishing fault diagnosis technique based on the contingent Bayesian networks, as recited in claim 1, wherein in the step (3) of generating the Blog model, the Blog model is a probabilistic model describing an unknown object, which describes a production process for sampling the model structure W to determine probability distribution of W; the Blog model comprises two types of sampling operations, wherein a first type sampling operation is to create a new object, which is completed by a numeric statement, a second type sampling operation is to sample values of functor of some objects, which is completed by a dependency statement, wherein the dependency statement and the numerical statement form a main part of the Blog model; the dependency statement describes how to determine a value of the functor applied to each object; wherein a left side of the dependency statement is the functor symbols and parameter variables of the functor symbols, and a right side is statements containing a structure of if-then-else; when sampling, each sentence of the if-then-else statement is checked until a true sentence is found, a value of the functor corresponding to the true sentence is a parameter of the conditional probability distribution; if sentences of the if-then-else statement are all false, a return value of the functor is null, and a parameter of corresponding conditional probability distribution is also null; the numerical statement creates a new object of the model, a left side of the numerical statement contains a set of conditions that constitute a potential object, a right side of the numerical statement has an identical form as the dependency statement; besides the dependency statement and the numerical statement, the Blog model also comprises: a type declaration statement for introducing a type; a random function declaration statement for specifying a type label of the functor symbol, whose value is randomly selected during a generation process; a guarantee statement for guaranteeing and naming all the different objects in W; on a basis of the model structure W, the Blog model is established by the dependency statement and the numerical statement to describe a generation process; the Blog model is configured to continuously add new objects to the model based on existing objects, so the Blog model is capable of containing objects which are changing and with unlimited number and uncertain relationships between the objects.

5. The method for establishing fault diagnosis technique based on the contingent Bayesian networks, as recited in claim 1, wherein the step (4) of transforming the Blog model into the contingent Bayesian networks comprises: taking type symbols t.sub.i and a set of functor symbols f in the Blog model as nodes of the Bayesian networks; taking a function symbol on a right side of a dependency statement of the functor symbol f, and a function symbol on a right side of a numerical statement of the symbols t.sub.i as a parent node; according to a generation process described by the Blog model, compiling an entire Bayesian network, which is denoted as BNs; wherein for the present invention, the software fault Fault and the environmental constrain Constrain of the software fault are nodes of the BNs; because an amount of the objects of the Blog model is uncertain, dependence relationships between the objects of the Blog model are also uncertain, BNs compiled according to the Blog model contain an infinite number of nodes and contain rings.

6. The method for establishing fault diagnosis technique based on the contingent Bayesian networks, as recited in claim 1, wherein the step (5) of defining the contingent Bayesian networks, comprises steps of: wherein a topology of the Bayesian network is a directed acyclic graph, and the BNs compiled according to the Blog model contain an infinite number of nodes and have a ring, which does not conform to definition of classical Bayesian networks, thus in the present invention BNs is converted to Contingent Bayesian Networks, denoted as CBNs; according to actual situations, specifying mutually exclusive conditions for edges in the BNs pointing to an identical node and from identical nodes, under specific conditions, only a limited number of edges satisfy the specific conditions and are active, nodes connected by the limited number of edges have a logical causal relationship, and the nodes in an inactive state are ignored in analysis, that is, even there are an infinite number of ancestor nodes in the CBNs, the CBNs is only affected by a limited number of ancestors during analysis; and furthermore, specifying mutually exclusive conditions for edges of each ring of the CBNs as well; wherein only edges satisfying specific condition are active; edges failing to satisfy the specific condition are temporarily removed in analysis; by generating the CBNs for the edges of the BNs, problems of an unlimited number of nodes and rings are solved.

7. The method for establishing fault diagnosis technique based on the contingent Bayesian networks, as recited in claim 1, wherein the step (6) learning parameters of the contingent Bayesian networks comprises steps of: wherein since the present invention generates the contingent Bayesian networks from the Blog model, the network structure is determined, only performing parameter learning of the network, that is, determining conditional probability of each node of the contingent Bayesian networks; wherein the parameter learning refers to under conditions of a given network topology G and a training sample set D, utilizing a priori knowledge to determine the conditional probability distribution of each node of the dependence Bayesian network model; performing parameter learning of the CBNs utilizing maximum likelihood estimation, assuming that there are n nodes in which the CBNs are active under specific conditions, which is noted as {X.sub.1, . . . , X.sub.i, . . . X.sub.n}, and meanwhile assuming that the i-th node has r.sub.i values, and a parent node of X.sub.i is denoted as pa(X.sub.i), pa(X.sub.i) has q.sub.i values; parameters to be calculated is ={.sub.ijk|i=1, . . . , n; j=1, . . . , q.sub.i; k=1, . . . , r.sub.i}, where j and k respectively refer to values of the parent nodes pa(X.sub.i) and the node X.sub.i; and logging likelihood function L(|D) to obtain: $l\left(.Math.D\right)=\log L\left(.Math.D\right)=\log \underset{l=1}{\overset{m}{.Math.}}P\left(d_l.Math.\right)=\underset{i=1}{\overset{n}{.Math.}}\underset{j=1}{\overset{q_i}{.Math.}}\underset{k=1}{\overset{r_i}{.Math.}}{m}_{\mathrm{ijk}}\log {}_{\mathrm{ijk}};$ wherein m.sub.ijk is a sample capacity in a sample set D that satisfies X.sub.i=k and pa(X.sub.i)=j, the sum, l(|D) is a logarithm of the likelihood function L(|D), and performing Lagrangian multiplier method to a formula mentioned above to obtain maximum likelihood estimate of a parameter , thereby determining parameters of the CBNs.

8. The method for establishing fault diagnosis technique based on the contingent Bayesian networks, as recited in claim 1, wherein in the step (7) of reasoning a fault of the contingent Bayesian networks by utilizing a Markov chain Monte Carlo Method, the Markov chain Monte Carlo Method is denoted as MCMC, wherein the MCMC is widely applied in Bayesian inference, Gibbs sampling which is of widest use in MCMC is adopted in the present invention to perform fault reasoning on the contingent Bayesian networks; Gibbs sampling is a special case in MCMC, wherein a first dimension is alternately fixed, and values of other dimension are adopted to sample a value in the first dimension; if a probability of occurrence of an event A={X.sub.1, X.sub.2, . . . X.sub.s} needs to be reasoned, wherein X.sub.1, X.sub.2, . . . , X.sub.s are nodes of CBNs, i.e., software fault Fault and environmental constrain of the fault Constrain, and sn, wherein a joint probability distribution of an event A is denoted as (A), wherein a process of the Gibbs sampling comprises steps of: (1) initializing comprising: randomly giving X.sub.1, X.sub.2, . . . , X.sub.s initial values A.sub.0={X.sub.1.sup.0, X.sub.2.sup.0, . . . X.sub.s.sup.0}; (2) generating X.sub.1.sup.1 by p(X.sub.1|X.sub.2.sup.0, . . . X.sub.s.sup.0); (3) in a same way as the step (2), fixing other variables, generating X.sub.2.sup.1, . . . , X.sub.s.sup.1 in sequence to obtain a new event A.sub.1={X.sub.1.sup.1, X.sub.2.sup.1, . . . X.sub.s.sup.1}; and (4) repeating steps 2-3 to obtain a Markov chain {A.sub.1, A.sub.2, . . . A.sub.t} wherein t is a sampling time; wherein through steps mentioned above, the conditional distribution is simulated to simulate the joint distribution, and then the conditional distribution is directly derived through the joint distribution simulated, in such a manner that the contingent Bayesian networks reasoning is achieved to complete fault diagnosis.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flow chart of overall steps of the method of the present invention.

(2) FIG. 2 is a simple sketch view of contingent Bayesian networks of the present invention.

(3) References numbers, symbols in the Figures are as follows.

(4) Steps 1-8 in FIG. 1 are corresponding steps in the technical solutions;

(5) The Fault and Constrain in FIG. 1 are software faults and environmental constrains;

(6) The w, f, ts, and R in FIG. 1 are respectively model structure, functor symbol, type label, and return value;

(7) The BNs and CBNs in FIG. 1 are Bayesian networks and contingent Bayesian networks;

(8) The MCMC in FIG. 1 is the Markov chain Monte Carlo method;

(9) U, V, W, and X in FIG. 2 are events.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

(10) In order to make the technical problems to be solved, the technical solutions and advantages of the present invention more apparent, further description of the present invention is illustrated in detail combining with the accompanying drawings.

(11) The present invention provides a method for establishing fault diagnosis technique based on contingent Bayesian networks. Technique established by the method of the present invention is capable of improving quality of software fault diagnosis. In the technique, based on the theory of contingent Bayesian networks, for complex embedded software faults have characteristics that the objects are unknown, the quantity is uncertain, and there may be dependencies between random faults, the present invention takes software faults and environmental disturbances as nodes to establish the contingent Bayesian network with infinite nodes and rings. The Markov chain Monte Carlo method is then adopted for diagnostic reasoning. When the technique is adopted for fault diagnosis, the Bayesian network established is more in line with the fault characteristics of large embedded software, and the diagnostic accuracy is higher.

(12) As shown in FIG. 1, the present invention provides a method for establishing fault diagnosis technique based on contingent Bayesian networks, wherein a specific establishing method is as follows:

(13) Step (1) determining a domain of an unknown object to be reasoned, wherein a establishing process is as follows: determining a type of software fault in which an amount of software to be tested is unknown and a type of environmental constrain that the software is facing during operation by software testing; wherein Fault represents software fault, Constrain represents environmental constrain which causes fault; amounts of both the Fault and Constrain are unknown.

(14) Step (2) defining the model structure by adopting the first-order logic language, wherein a establishing method is as follows: the first-order logic language which is typed comprises a set of type symbols and a set of functor symbols f, each of the functor symbols f has a type tag ts(t.sub.1, . . . , t.sub.i, . . . , t.sub.or), wherein i=1, 2, . . . , or, each of the t.sub.i is a type symbol, or is an order of a functor symbol, if or=0, the functor symbol is a constant symbol; meanwhile, each of the functor symbol f has a return value R, and the return value R is a null value null;

(15) wherein when a functor is not suitable for a parameter, return back to the null of a special value, and any function that receives null as a parameter also returns null;

(16) wherein W represents a defined model structure, W defines an extension of each type, an interpretation of each function statement, and specifies object sets exist in each type and values of each function symbol; W comprises extensions [R].sup.w of each type, wherein [R].sup.w is a set of objects of the type in W, an extension of the type symbols t.sub.i is denoted as [t.sub.i].sup.w; each of the functor symbols f comprises an explanation [f].sup.w, wherein [f].sup.w is a function at a range of [t.sub.i].sup.w to [R].sup.w.

(17) Step (3) generating the Blog model wherein a establishing method is as follows: the Blog model is a probabilistic model describing an unknown object, which describes a production process for sampling the model structure W to determine probability distribution of W; the Blog model comprises two types of sampling operations, wherein a first type sampling operation is to create a new object, which is completed by a numeric statement, a second type sampling operation is to sample values of functor of some objects, which is completed by a dependency statement, wherein the dependency statement and the numerical statement form a main part of the Blog model;

(18) the dependency statement describes how to determine a value of the functor applied to each object; wherein a left side of the dependency statement is the functor symbols and parameter variables of the functor symbols, and a right side is statements containing a structure of if-then-else; when sampling, each sentence of the if-then-else statement is checked until a true sentence is found, a value of the functor corresponding to the true sentence is a parameter of the conditional probability distribution; if sentences of the if-then-else statement are all false, a return value of the functor is null, and a parameter of corresponding conditional probability distribution is also null;

(19) the numerical statement creates a new object of the model, a left side of the numerical statement contains a set of conditions that constitute a potential object, a right side of the numerical statement has an identical form as the dependency statement;

(20) besides the dependency statement and the numerical statement, the Blog model also comprises: a type declaration statement for introducing a type; a random function declaration statement for specifying a type label of the functor symbol, whose value is randomly selected during a generation process; a guarantee statement for guaranteeing and naming all the different objects in W;

(21) wherein establishing a Blog Model firstly adopts a type declaration statement, the type of the object introduced, comprises the Fault and Constrain of Step 1; then use a random function statement to specify the type tag of the functor symbol and specify types of the parameters and return value; Secondly, use the guarantee object statement to name all possible objects; if there are i kinds of faults and j kinds of environmental constrain, which can be expressed as Fault.sub.1, Fault.sub.2, . . . Fault.sub.i, Constrain.sub.1, Constrain.sub.2, . . . Constrain.sub.i, and then the dependency statement and the numerical statement are utilized to establish a main part of the Blog model;

(22) on a basis of the model structure, the Blog model is established by the dependency statement and the numerical statement to describe a generation process; the Blog model is configured to continuously add new objects to the model based on existing objects, so the Blog model is capable of containing objects which are changing and with unlimited number and uncertain relationships between the objects.

(23) Step (4) transforming the Blog model into the contingent Bayesian networks, wherein a establishing method is as follows: taking type symbols t.sub.i and a set of functor symbols f in the Blog model as nodes of the Bayesian networks; taking a function symbol on a right side of a dependency statement of the functor symbol f, and a function symbol on a right side of a numerical statement of the symbols t.sub.i as a parent node; according to a generation process described by the Blog model, compiling an entire Bayesian network, which is denoted as BNs; wherein for the present invention, the software fault Fault and the environmental constrain Constrain of the software fault are nodes of the BNs; because an amount of the objects of the Blog model is uncertain, dependence relationships between the objects of the Blog model are also uncertain, BNs compiled according to the Blog model contain an infinite number of nodes and contain rings.

(24) Step (5) defining the contingent Bayesian networks, wherein a establishing method is as follows: a topology of the Bayesian network is a directed acyclic graph, and the BNs compiled according to the Blog model contain an infinite number of nodes and may have a ring, which does not conform to definition of classical Bayesian networks, thus in the present invention BNs is converted to Contingent Bayesian Networks, denoted as CBNs;

(25) according to actual situations, specifying mutually exclusive conditions for edges in the BNs pointing to an identical node and from identical nodes, under specific conditions, only a limited number of edges satisfy the specific conditions and are active, nodes connected by the limited number of edges have a logical causal relationship, and the nodes in an inactive state are ignored in analysis, that is, even there are an infinite number of ancestor nodes in the CBNs, the CBNs is only affected by a limited number of ancestors during analysis; and

(26) furthermore, specifying mutually exclusive conditions for edges of each ring of the CBNs as well; wherein only edges satisfying specific condition are active; edges failing to satisfy the specific condition are temporarily removed in analysis; by generating the CBNs for the edges of the BNs, problems of an unlimited number of nodes and rings are solved.

(27) Step (6) learning parameters of the contingent Bayesian networks, wherein a establishing method is as follows: since the present invention generates the contingent Bayesian networks from the Blog model, the network structure is determined, only performing parameter learning of the network, that is, determining conditional probability of each node of the contingent Bayesian networks; wherein the parameter learning refers to under conditions of a given network topology G and a training sample set D, utilizing a priori knowledge to determine the conditional probability distribution of each node of the dependence Bayesian network model; wherein the prior distribution generally obeys a certain probability distribution family; if the variable has two states, then the variable obeys the distribution; if the variable has more than two states, the variable obeys multiple Dirichlet distributions and a certain strategy is utilized to estimate parameters of the distribution;

(28) performing parameter learning of the CBNs utilizing maximum likelihood estimation, assuming that there are n nodes in which the CBNs are active under specific conditions, which is noted as {X.sub.1, . . . , X.sub.i, . . . X.sub.n}, and meanwhile assuming that the i-th node has r values, and a parent node of X.sub.1 is denoted as pa(X.sub.i), pa(X.sub.i) has q.sub.i values; parameters to be calculated is ={.sub.ijk|i=1, . . . , n; j=1, . . . , q.sub.i; k=1, . . . , r.sub.i}, where j and k respectively refer to values of the parent nodes pa(X.sub.i) and the node X.sub.i; and logging likelihood function L(|D) to obtain:

(29) $l\left(.Math.D\right)=\log L\left(.Math.D\right)=\log \underset{l=1}{\overset{m}{.Math.}}P\left(d_l.Math.\right)=\underset{i=1}{\overset{n}{.Math.}}\underset{j=1}{\overset{q_i}{.Math.}}\underset{k=1}{\overset{r_i}{.Math.}}{m}_{\mathrm{ijk}}\log {}_{\mathrm{ijk}};$

(30) wherein m.sub.ijk is a sample capacity in a sample set D that satisfies X.sub.i=k and pa(X.sub.i)=j, the sum, l(|D) is a logarithm of the likelihood function L(|D), and performing Lagrangian multiplier method to a formula mentioned above to obtain maximum likelihood estimate of a parameter , thereby determining parameters of the CBNs.

(31) Step (7) reasoning a fault of the contingent Bayesian networks by utilizing a Markov chain Monte Carlo Method, wherein a establishing method is as follows: the Markov chain Monte Carlo Method is denoted as MCMC, based on the Markov process, in order to sample on a specified distribution, according to the Markov process, first simulate the Markov process from any state, continuously perform state transition, and finally converge to a stationary distribution; wherein the MCMC is widely applied in Bayesian inference, Gibbs sampling which is of widest use in MCMC is adopted in the present invention to perform fault reasoning on the contingent Bayesian networks;

(32) Gibbs sampling is a special case in MCMC, wherein a first dimension is alternately fixed, and values of other dimension are adopted to sample a value in the first dimension; if a probability of occurrence of an event A={X.sub.1, X.sub.2, . . . X.sub.s} needs to be reasoned, wherein X.sub.1, X.sub.2, . . . , X.sub.s are nodes of CBNs, i.e., software fault Fault and environmental constrain of the fault Constrain, and sn, wherein a joint probability distribution of an event A is denoted as (A), wherein a process of the Gibbs sampling comprises steps of:

(33) (1) initializing comprising: randomly giving X.sub.1, X.sub.2, . . . , X.sub.s initial values A.sub.0={X.sub.1.sup.0, X.sub.2.sup.0, . . . X.sub.s.sup.0};

(34) (2) generating X.sub.1.sup.1 by p(X.sub.1|X.sub.2.sup.0, . . . X.sub.s.sup.0);

(35) (3) in a same way as the step (2), fixing other variables, generating X.sub.2.sup.1, . . . , X.sub.s.sup.1 in sequence to obtain a new event A.sub.1={X.sub.1.sup.1, X.sub.2.sup.1, . . . X.sub.s.sup.1}; and

(36) (4) repeating steps 2-3 to obtain a Markov chain {A.sub.1, A.sub.2, . . . A.sub.t} wherein t is a sampling time;

(37) wherein through steps mentioned above, the conditional distribution is simulated to simulate the joint distribution, and then the conditional distribution is directly derived through the joint distribution simulated, in such a manner that the contingent Bayesian networks reasoning is achieved to complete fault diagnosis.

(38) Through the above steps, the establishment of the fault diagnosis technique based on the contingent Bayesian networks can be completed. In this technique, we take advantage of the characteristics that Bayesian network theory can contain infinite nodes and rings. We take embedded software faults and environmental constrains with characteristics of unknown objects, uncertain quantities, and possible dependencies between random faults as the node of the contingent Bayesian network, and a condition indicating the activation state is specified for each edge of the network to indicate the uncertainty of the dependency. Then the Markov chain Monte Carlo method is used for the reasoning diagnosis. When the technology is used for fault diagnosis, the Bayesian network established is more suitable for the fault characteristics of large embedded software, and the diagnostic accuracy is higher.

(39) The fault prediction technology is constructed based on the theory of contingent Bayesian networks, and a more practical fault diagnosis technology based on contingent Bayesian networks is formed.

(40) The details not described in the present invention is well known to the skills in the art.

(41) One skilled in the art will understand that the embodiment of the present invention as shown in the drawings and described above is exemplary only and not intended to be limiting.

(42) It will thus be seen that the objects of the present invention have been fully and effectively accomplished. Its embodiments have been shown and described for the purposes of illustrating the functional and structural principles of the present invention and is subject to change without departure from such principles. Therefore, this invention includes all modifications encompassed within the spirit and scope of the following claims.