Extensible bayesian network editor with inferencing capabilities

• US 7,720,779 B1
• Filed: 01/23/2007
• Issued: 05/18/2010
• Est. Priority Date: 01/23/2006
• Status: Expired due to Fees

• Current Assignee: Quantum Leap Research, Inc.
• Original Assignee: Quantum Leap Research, Inc.
• Inventors: Faulkner, Eli T., Perry, Benjamin Beau
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US11/626,354
• Time in Patent Office: 1,211 Days
• Field of Search: 706/45
• US Class Current: 706/45
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A system for the representation, editing, evaluation, and inference of graphical models is disclosed which can be used to construct and evaluate a graphical model or graphical network and to calculate inference values. An efficient method of updating graphical models is demonstrated, and provides the basis for an improved system for manipulation and evaluation of probabilistic models. The graphical network editor is useful in the construction of graphical modes such as Bayesian Networks. The graphical network and network graphical user interface (GUI) are used in conjunction with each other to model a system wherein failure probabilities and the current state of components are taken into account to monitor the health and progress of a system for an engineer or engineering software to evaluate and monitor. The evaluation is useful in the monitoring of assets and other real systems having multiple, dependent, and independently operating components such as a pump, a manufacturing plant, a production line, an assembly line, where asset health and quality control is a concern. The asset components each influencing some overall outcome of a system or situation. Success or failure or probability of success, probability of failure and health of the system can be monitored and manipulated by altering the values of prior probability and posterior probability values. Failure correlation between components can be evaluated wherein failure rates of asset is unknown. Production and quality can be monitored and altered.

Claims

1. In a computer system, having at least one processor or virtual machine, at least one memory unit, at least one input device and at least one output device, and optionally a network and optionally memory shared among the at least one processor, a data processing method for modifying probabilistic data structures comprising the computer implemented steps of:

g. creating a representation of a first event and a representation of a second event of a model system;

h. creating a representation of at least one logical influential relationship between the first event and the second event;

i. creating a representation of a probabilistic relational data structure incorporating probabilistic influences of the at least one logical influential relationship between the first event and the second event;

j. populating the probabilistic relational data structure with a first set of probabilities representing the probabilistic influences between the first event and the second event;

k. creating a modified probabilistic relational data structure while maintaining the logical influential relationships between the first event and the second event; and

l. populating the modified probabilistic relational data structure with a second set of probabilities representing modified probabilistic influences between the first event and the second event while preserving the logical influential relationships between the first event and the second event.

2. The method of claim 1, further comprising providing the user with the ability to encode a behavior of a boolean operator in the representation, by creating a probabilistic relational data structure incorporating probabilistic influences of the at least one logical influential relationship between the first event and the second event, where the boolean operator is at least one chosen from the group consisting of:

“

AND”

, “

OR”

, “

NOT”

, “

NOR”

, “

NAND”

, and “

XOR”

.

3. The method of claim 2, wherein creating a representation of a probabilistic relational data structure encoding the behavior of a Boolean operator provides the user with mechanisms and tools for encoding expert rules in a network comprised of probabilistic relationships.

4. The method of claim 2, further comprising encoding the representation of the events and logical influential relationships, reflecting constraints implicit in a graphical model, where the graphical model is at least one selected from the group consisting of:

a Bayesian network, a directed acyclic graph, a graphical Gaussian model, and a Hidden Markov model.

5. The method of claim 2, further comprising encoding the representation of the events and logical influential relationships of the probabilistic relational data structure, reflecting constraints implicit in a graphical model, wherein the graphical model is at least one selected from the group consisting of:

a Bayesian network, a directed acyclic graph, a graphical Gaussian model, a Markov network, and a hidden Markov model.

6. The method of claim 2, further comprising encoding the representation of the events and logical influential relationships of the modified probabilistic relational data structure, reflecting constraints implicit in a graphical model, wherein the graphical model is at least one selected from the group consisting of:

a Bayesian network, a directed acyclic graph, a graphical Gaussian model, a Markov network, and a hidden Markov model.

7. The method of claim 2, further comprising populating the first set or the second set of probabilities of the probabilistic relational data structure of the model system by at least one technique selected from the group of techniques consisting of:

an exact inference technique;

an approximate inference technique;

a sampling technique; and

a random data generation technique.

8. The method of claim 2, further comprising defining the node functionality of the first event and the second event of a graphical model by enforcing a conditional probability table that associates the first event with the second event.

9. The method of claim 8, further comprising enforcing a logic operation between the first event and the second event wherein the logic operation is at least one selected from the group consisting of:

a unary Boolean logic operation relationship and a binary Boolean logic operation relationship.

10. The method of claim 8, further comprising enforcing at least one Boolean logic operation relationship selected from the group of relationships consisting of:

associativity, commutativity, absorption, distributivity and compliment;

by filling appropriate values of a conditional probability table.

11. The method of claim 8, further comprising representing a Boolean logic operation relationship by using at least one node selected from the group consisting of:

an OR node, an AND node, a NOR node, a NAND node, an XOR node, and a NOT node.

12. The method of claim 8, further comprising representing a Boolean logic operational relationship involving multiple operators by a composed node exhibiting composed Boolean logic operational relationships wherein the composed node is composed of at least one selected from the group consisting of:

an OR node, an AND node, a NOR node, a NAND node, an XOR node, and a NOT node.

13. The method of claim 8, further comprising populating the probabilistic relational data structure and the modified probabilistic relational data structure by iteratively recalculating the values for the probabilistic relational data structure and the modified probabilistic relational data structure until a predetermined condition is met, wherein the predetermined condition is at least one selected from a group consisting of:

steady state convergence, expected value convergence, expected threshold attainment, expected range attainment, finite iteration execution, expected bound attainment, and divergence.

14. A monitoring system incorporating the method of claim 2, wherein the monitoring system monitors data sources relating to a dynamically changing system, and constructs alerts or communications relating to particular events or patterns of events occurring in the system, wherein the system is at least one selected from the group consisting of:

an engineering processor, a chemical processor, an electrical processor, an asset processor, a mechanical processor, a biological processor, a biomedical processor, a solar processor, a radiological processor, a manufacturing processor, an environmental processor, an agricultural processor, a monitoring processor, and an assembly processor.

15. In a computer system, having at least one processor or virtual machine, at least one memory unit, at least one input device and at least one output device, and optionally a network and optionally memory shared among the at least one processor, a method for processing relationships within a graphical model comprising the computer implemented steps of:

e. creating a probabilistic relational data structure comprising entries of a first probability of at least a first state of a first event and entries of a second probability of at least a second state of a second event, wherein the probabilistic relational data structure reflects constraints of (probabilistic relationships, logical relationships and influential relationships) as represented by the graphical model;

f. manipulating the first probability of the first state of the first event;

g. calculating the second probability of the second state of the second event based upon the manipulations of the first probability of the first event; and

h. maintaining the constraints imposed by the logical relationships between the events of the graphical model.

16. The method of claim 15, further comprising creating a representation of a probabilistic relational data structure incorporating probabilistic influences of the at least one logical influential relationship between the first event and the second event provides the user with the ability to encode a the behavior of a Boolean operator in the representation, where the Boolean operator is composed of at least one chosen from the group consisting of:

“

AND”

, “

OR”

, “

NOT”

, “

NOR”

, “

NAND”

, and “

XOR”

.

17. The method of claim 16, further comprising providing the user with the ability to encode expert rules in a network comprised of probabilistic relationships by encoding the behavior of a Boolean operator in the representation of a probabilistic relational data structure.

18. The method of claim 16, further comprising obtaining a parameter that controls the constraint requiring crisp logic behavior of the Boolean operator in the representation.

19. The method of claim 16, further comprising obtaining a parameter from the user wherein the parameter dictates the degree of crisp logic behavior to apply to at least one Boolean operator in the representation.

20. The method of claim 16, further comprising supporting user-manipulation of the first probability of the first state from a discrete variable to a continuous variable, and altering a set of complimentary probabilities of the first event and the second event while maintaining the constraints of probabilistic relationships, the logical relationships and the influential relationships imposed by the graphical model.

21. The method of claim 16, further comprising supporting manipulation of the first probability of the first state during run time, and concurrently updating a set of complimentary probabilities.

22. The method of claim 16, further comprising supporting a range of the first probability of the first state between zero and one.

23. The method of claim 16, further comprising supporting a representation of the logical state value of the at least one state of the events in the graphical model wherein the representation is at least one value selected group of values consisting of:

true, false, not-true and not-false.

24. The method of claim 16, further comprising normalizing a probability distribution of each event of each state at run time.

25. The method of claim 16, further comprising creating a probabilistic relational data structure as represented by the graphical model wherein the graphical model is at least one model type selected from the group consisting of:

a Bayesian network, a directed acyclic graph, a graphical Gaussian model, a Markov network, and a hidden Markov model.

26. The method of claim 16, further comprising the steps of:

i. performing iteration of re-evaluation of the probabilities triggered by the manipulation of a distinct probability of the events of the graphical model, and

j. executing the re-evaluation at run time until a pre-determined condition is met.

27. The method of claim 26, further comprising applying a predetermined condition wherein the predetermined condition is least one selected from the group consisting of:

steady state convergence, value convergence, threshold attainment, threshold exceedment, range attainment, finite iteration execution, expected bound attainment, divergence, and time constraint.

28. The method of claim 26, further comprising re-evaluation of the probabilities employing at least one simulation method selected from the group consisting of:

Laplace, semi-analytic, Markov, Monte Carlo, Gibbs, smudge, blend and variational simulation methods.

29. The method of claim 16, further comprising representing each event by a probability vector composed of the probabilities of each state of each event.

30. The method of claim 29 further comprising incorporation of at least one probability of the probability vector in generating of a conditional probability table of a desired state of an event.

31. In a computer system, having at least one processor or virtual machine, at least one memory unit, at least one input device, at least one output device, optionally a network, optionally shared memory among the at least one processor, a method for generating data from a user-specified profile comprising computer implemented steps of:

e. identifying a first element among within a model system that contains at least one second element;

f. creating a user-modifiable incidence profile of the first element per incremental unit of the second element within an interval of units of the second element;

g. creating a probability distribution representing probabilities of a value of the first element within the interval of units of the second element; and

h. generating data cases based on the probability and distribution of the first element.

32. The method of claim 31, further comprising representing successive states of an independent variable as an interval of units of the second element.

33. The method of claim 31, further comprising representing successive times of a time variable as an interval of units of the second element.

34. The method of claim 31, further comprising applying values from the fields of records to the probabilistic influential relationships defined by the probabilistic graphical model, wherein the records are drawn from data cases.

35. The method of claim 31, further comprising creating a probabilistic relational data structure as represented by the graphical model wherein the graphical model is at least one model type selected from the group consisting of:

a Bayesian network, a directed acyclic graph, a graphical Gaussian model, a Markov network, and a hidden Markov model.

36. The method of claim 31, further comprising bounding the incidence profile within a particular range.

37. The method of claim 31, further comprising the steps of:

i. initially obtaining the incidence profile from existing data, and

j. optionally supporting modification of the incidence profile.

38. The method of claim 31, further comprising enabling the user'"'"'s construction of a visible representation of a line, wherein the line represents behavior of the first element with respect to incremental units of a second element, and optionally wherein the user-modifiable incidence profile is created by the user.

39. The method of claim 38, further comprising enabling the user'"'"'s construction of a visible representation of a line wherein the visible representation of a line is accomplished by at least one method selected from the group consisting of:

selecting data points through which a line is constructed by linear regression;

selecting data points through which a line is constructed by non-linear regression;

selecting data points which connect a piece-wise linear line;

selecting data points through which a quadratic function is fit;

selecting data points through which a polynomial function is fit;

selecting data points through which an exponential function is fit;

selecting data points through which a trigonometric function is fit;

selecting points through which a cubic spline is fit;

selecting points that are used as control points for a Bezier curve; and

selecting points that are used to patch together segments constructed by some other method.

40. The method of claim 31, further comprising the steps of:

e. initially obtaining the incidence profile from existing data,

f. depicting that profile as a visible line, and

g. optionally modifying the line by obtaining at least one changed feature of the visible line from the user.

41. In a computer implemented system having at least one processor or virtual machine, at least one memory unit, at least one processing unit, at least one input device, at least one output device, optionally a network, optionally shared memory among the at least one processor, a method for generating and manipulating a graphical representation of probabilistically related events, the method comprising the computer implemented steps of:

g. presenting a workspace to a user, the workspace supporting the graphical representation;

h. presenting a first pallet of user manipulable graphical objects, the graphical objects representing at least a first state of a first event;

i. presenting a second pallet of user manipulable graphical tools;

j. presenting at least one user manipulable first conditional probability table of a state of an event exhibiting inference with respect to a second state of a second event;

k. populating a second conditional probability table reflecting the manipulations of the first conditional probability table; and

l. populating the second conditional probability table of the second state to meet a user-selected metric of accuracy.

42. The method of claim 41, further comprising representing independent mathematical relationships and dependent mathematical relationships, wherein the graphical representation is at least one selected from the group consisting of:

a Bayesian network, a directed acyclic graph, a graphical Gaussian model, a Markov network, and a hidden Markov model.

43. The method of claim 41, further comprising monitoring the user manipulable graphical objects comprising nodes and arcs, and concurrently updating the first and second conditional probability tables to reflect the user manipulations of the graphical objects.

44. The method of claim 41, further comprising representing the relationship between at least one state and at least one other state, wherein the user manipulable graphical objects comprise nodes and arcs for representation of the environment, wherein the nodes are representing the states and the arcs are representing mathematical dependence between the states.

45. The method of claim 42, further comprising representing at least one entry of the first conditional probability table and at least one entry of the second conditional probability table as a visible graph, wherein the entries are reflecting mathematical constraints as imposed by the graphical model representation.

46. The method of claim 45, further comprising portraying the probabilities of the states of events of entries of the first conditional probability table and the entries second conditional probability table.

47. The method of claim 46, further comprising portraying the probabilities of the states of events, wherein the probabilities of the states of the events reflect exact inference.

48. The method of claim 41, further comprising representing events as a node, and associating the events with a conditional probability table for the node.

49. The method of claim 42, further comprising using arcs for representing conditional dependencies among connected nodes, and using the lack of arcs between nodes for representing conditional independence.

50. In a computer implemented system having at least one processor or virtual machine, at least one memory unit, at least one processing unit, at least one input device, at least one output device, optionally a network, optionally shared memory among the at least one processor, a method for processing conditional probabilities comprising computer implemented steps of:

e. presenting in a workspace a user manipulable graphical representation of a first set of values of a first conditional probability table representing at least one state of at least one event;

f. reflecting proportional changes of the user manipulated graphical representation in the first conditional probability table;

g. calculating inference of a second state of a second event of a second conditional probability table, the calculation being based on the user changes of the first conditional probability table; and

h. proportionally graphically representing a second set of values of the second conditional probability table in a second graphical representation.

51. The method of claim 50, further comprising representing a graphical model relating the first conditional probability table and the second conditional probability table wherein the graphical model is at least one selected from the group consisting of:

a Bayesian network, a directed acyclic graph, a graphical Gaussian model, a Markov network, a Hidden Markov model and a neural network.

52. The method of claim 50, further comprising the steps of:

e. obtaining a user'"'"'s manipulation of the graphical representations of at least one of the conditional probability tables, and

f. propagating the influences a set of complimentary conditional probability tables of related events.

53. The method of claim 50, further comprising graphically presenting a visible representation of values of the first or second the conditional probability table to the user, wherein the visible representation is proportional to the magnitude of the individual values of the conditional probability table.

54. The method of claim 50, further comprising graphically presenting a visible representation of values of the first or second conditional probability tables by at least one visible representation selected from the group consisting of:

a histogram, a bar graph, a radial bar graph, a bar chart, a block diagram, a candlestick chart, a glyph, a pictogram, a pie chart, a scatterplot, a scatter graph, a Karnaugh map, a Veitch diagram, a box plot, a Venn diagram, a Euler diagram, a Johnston diagram, a box-and-whisker diagram, a Smith chart, and a graphic reflecting an associated probability of an event with a graphical dimension proportional to the magnitudes of at least one of the values of the conditional probability table of a node.

55. In a data-processing system, having:

one or more processors or virtual machines,

each processor comprising one or more cores,

the system comprising one or more memory units,

one or more input devices,

one or more output devices,

optionally a network, and

optionally shared memory supporting communication among the processors, a computer implemented system for modifying probabilistic data structures and processing relationships comprising;

i. a means of creating a representation of a first event and a representation of a second event of a model system;

j. a means of creating a representation of at least one logical influential relationship between the first event and the second event;

k. a means of creating a representation of a probabilistic relational data structure incorporating probabilistic influences of the at least one logical influential relationship between the first event and the second event;

l. a means of populating the probabilistic relational data structure with a first set of probabilities representing the probabilistic influences between the first event and the second event;

m. a means of creating a modified probabilistic relational data structure while maintaining the logical influential relationships between the first event and the second event;

n. a means of populating the modified probabilistic relational data structure with a second set of probabilities representing modified probabilistic influences between the first event and the second event while preserving the logical influential relationships between the first event and the second event;

manipulating the first probability of the first state of the first event;

o. a means of calculating the second probability of the second state of the second event based upon the manipulations of the first probability of the first event; and

p. a means of maintaining the constraints imposed by the logical relationships between the events of the graphical model.

56. In a data-processing system, having:

one or more processors or virtual machines,

each processor comprising one or more cores,

the system comprising one or more memory units,

one or more input devices,

one or more output devices,

optionally a network, and

optionally shared memory supporting communication among the processors, a computer implemented system for generating data from a user-specified profile comprising;

e. a means of identifying a first element among within a model system that contains at least one second element;

f. a means of creating a user-modifiable incidence profile of the first element per incremental unit of the second element within an interval of units of the second element;

g. a means of creating a probability distribution representing probabilities of a value of the first element within the interval of units of the second element; and

h. a means of generating data cases based on the probability and distribution of the first element.

57. In a data-processing system, having:

one or more processors or virtual machines,

each processor comprising one or more cores,

the system comprising one or more memory units,

one or more input devices,

one or more output devices,

optionally a network, and

optionally shared memory supporting communication among the processors, a computer implemented system for generating and manipulating a graphical representation of probabilistically related events and processing conditional probabilities comprising;

g. a means of presenting a workspace to a user, the workspace supporting the graphical representation;

h. a means of presenting a first pallet of user manipulable graphical objects, the graphical objects representing at least a first state of a first event;

i. a means of presenting a second pallet of user manipulable graphical tools;

j. presenting at least one user manipulable first conditional probability table of a state of an event exhibiting inference with respect to a second state of a second event; and

k. a means of populating a second conditional probability table reflecting the manipulations of the first conditional probability table;

l. a means of populating the second conditional probability table of the second state to meet a user-selected metric of accuracy;

m. a means of presenting in a workspace a user manipulable graphical representation of a first set of values of a first conditional probability table representing at least one state of at least one event;

n. a means of reflecting proportional changes of the user manipulated graphical representation in the first conditional probability table;

o. a means of calculating inference of a second state of a second event of a second conditional probability table, the calculation being based on the user changes of the first conditional probability table; and

p. a means of proportionally graphically representing a second set of values of the second conditional probability table in a second graphical representation.