General purpose fusion engine

• US 7,424,466 B2
• Filed: 07/24/2002
• Issued: 09/09/2008
• Est. Priority Date: 07/24/2002
• Status: Active Grant

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: Northrop Grumman Corporation
• Inventors: Talbot, Patrick J., Ellis, Dennis R.
• Primary Examiner(s): Vincent; David
• Assistant Examiner(s): Tran; Mai T
• Application Number:
  US10/201,882
• Publication Number:
  US 20040019575A1
• Time in Patent Office: 2,239 Days
• Field of Search: 706/46
• US Class Current: 706/46
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Systems and methods are provided for fusing new evidence and displaying node parameters of a decision network. The decision network can be a belief network, such as a Dempster-Shafer belief network. The Dempster-Shafer belief network includes node parameters that conform to the Dempster-Shafer combination rule, which is based on an evidential interval: the sum of a belief value, a disbelief value and an unknown value is equal to one. A user override is provided to allow a user to override node parameters associated with a hypothesis or outcome and the decision network self-adjusts the appropriate link values or learned to instantiate the override. The back-propagation algorithm is used to adjust the links.

Claims

1. A system for fusing evidence in a decision network, the system comprising:

memory that stores a decision network that includes a plurality of multiple layers of nodes and associated current node parameters, each node representing a given hypothesis associated with the decision network and the current node parameters comprising belief values and disbelief values in a given hypothesis; and

a processing unit for accessing the memory and for executing executable instructions, the executable instructions comprising;

a fusion engine algorithm that fuses new evidence with current node parameters of the decision network to provide updated current node parameters, the new evidence being new belief values and new disbelief values associated with one or more respective nodes and associated hypothesis; and

a graphical user interface that displays the plurality of multiple layers of nodes and associated links between the plurality of multiple layers of nodes and associated current node parameters in a network view, the graphical user interface having a user override that allows a user to modify current node parameters associated with nodes and back propagate the modified node parameters through the decision network.

2. The system of claim 1, the decision network being a Dempster-Shafer belief network.

3. The system of claim 2, the fusion engine algorithm executes a Cartesian Product on current node parameters and new evidence.

4. The system of claim 1, the current node parameters being belief values, disbelief values and unknown values.

5. The system of claim 1, the new evidence being a belief value and a disbelief value relating to at least one node, the fusion engine evaluates an unknown value from the belief value and the disbelief value.

6. The system of claim 5, the sum of the belief value, the disbelief value and the unknown value being equal to one.

7. The system of claim 1, the fusion engine algorithm propagates node parameters from top layers to lower layers during initialization.

8. The system of claim 1, the graphical user interface further comprising a node override editor menu that allows a user to override current node parameters.

9. The system of claim 1, the graphical user interface further comprising an add evidence editor menu that allows a user to add evidence to current node parameters.

10. The system of claim 1, the graphical user interface further comprising a link editor menu that allows a user to modify link values associated with current node parameters of the decision network.

11. The system of claim 1, the user override allows a user to modify current node parameters of nodes in at least one of intermediate node layers and bottom node layers.

12. The system of claim 1, further comprising a second graphical user interface that provides a temporal display view of current node parameters associated with a selected node.

13. A system for comparing decision networks, the system comprising:

memory having a set of decision networks stored therein, wherein a decision network includes a plurality of multiple layers of nodes and associated node parameters, each node representing a given hypothesis associated with the decision network with node parameters comprising belief values and disbelief values in a respective hypothesis; and

a processing unit for accessing the memory and for executing executable instructions, the executable instructions comprising;

a graphical user interface that allows a user to select a first decision network and a second decision network for loading from the set of decision networks in the memory;

a loader that loads a the selected first decision network and the selected second decision network to be executed by an execution engine;

a network overlay component that compares node parameters of the first decision network and the second decision network;

an inverse execution engine algorithm that extracts node parameters from at least one node of the first decision network or the second decision network and desired node parameters comprising a desired belief value and a desired disbelief value of the at least one node and determines an inverse of the node parameters by evaluating the relationship that an evidence matrix fused with an inverse matrix produces an identity matrix and solving for the inverse matrix associated with the node parameters, the inverse matrix corresponding to an amount of evidence necessary to achieve a desired decision making threshold, the amount of evidence being a difference value between at least one of the belief value and disbelief value and at least one of the corresponding desired belief value and desired disbelief value; and

wherein the graphical user interface displays a node parameter comparison view of the first network and the second network.

14. The system of claim 13, the first decision network and the second decision network being Dempster-Shafer belief networks.

15. The system of claim 14, the network overlay component determines ratios of belief values of similar nodes of the first decision network and the second decision network, and provides the ratio to the graphical user interface, the graphical user interface displaying a comparison view of the first and second networks, wherein unmatched nodes from the first decision network and the second decision network are one of ignored or combined into other nodes.

16. A system for determining an inverse of a decision network, the system comprising:

memory that stores a Dempster-Shafer belief network with a plurality of nodes and associated node parameters, each node representing a given hypothesis associated with the decision network and the node parameters comprising belief values and disbelief values in a given hypothesis; and

a processing unit for accessing the memory and for executing executable instructions, the executable instructions comprising;

an inverse execution engine algorithm that extracts node parameters from at least one node of the Dempster-Shafer belief network and desired node parameters comprising a desired belief value and a desired disbelief value of the at least one node and determines an inverse of the node parameters by evaluating the relationship that an evidence matrix fused with an inverse matrix produces an identity matrix and solving for the inverse matrix associated with the node parameters, the inverse matrix corresponding to an amount of evidence necessary to achieve a desired decision making threshold, the amount of evidence being a difference value between at least one of the belief value and disbelief value and at least one of the corresponding desired belief value and desired disbelief value; and

a graphical user interface that displays the difference value of the at least one node and an associated linguistic term based on the difference value.

17. The system of claim 16, the node parameters being a belief value, a disbelief value and an unknown value forming a triad used in the evidence matrix, the identity matrix and the inverse matrix.

18. The system of claim 17, the inverse matrix being determined by evaluating the relationships:

B=−

b/[(b+u)(u−

bd/{b+u}−

bd/{d+u})];

U=1/(u−

bd/{b+u}−

bd/{d+u}); and

D=−

d/[(d+u)(u−

bd/{b+u}−

bd/{d+u})]

where b is the current belief value, d is the current disbelief value and u is the unknown value of the evidence, B is the belief value, D is the disbelief value and U is the unknown value of the inverse matrix.

19. A system for fusing evidence in a decision network, the system comprising:

a memory that stores a decision network that includes a plurality of multiple layers of nodes and associated node parameters, each node representing a given hypothesis associated with the decision network and the node parameters comprising belief values and disbelief values in a given hypothesis; and

a processing unit for accessing the memory and for executing executable instructions, the executable instructions comprising;

a fusion algorithm that fuses new evidence with current node parameters of the decision network to provide updated current node parameters, the new evidence being new belief values and new disbelief values associated with one or more respective nodes and associated hypothesis;

an evidence source that provides the fusion algorithm with new evidence;

a fog component algorithm that perturbs new evidence from the evidence source prior to fusing the new evidence with current node parameters by fusing perturbation variables with the new evidence; and

a graphical user interface that allows a user to select a frequency associated with the perturbation variables.

20. The system of claim 19, the perturbation variables comprising data perturbation variables and human perturbation variables.

21. The system of claim 19, further comprising a graphical user interface that displays node parameters over time.

22. The system of claim 21, the decision network being a Dempster-Shafer belief network, the graphical user interface displaying a belief value, a disbelief value and an unknown value associated with a selected node.

23. A computer readable medium having computer executable instructions for performing a method, the method comprising:

retrieving a belief network from memory;

initializing the belief network with initial node parameter values to provide current node parameter values, the initial node parameter values and current node parameter values comprising belief values and disbelief values associated with a given node, the node representing a respective hypothesis;

fusing new evidence with current node parameter values to provide updated current node parameter values, the new evidence being new belief values and new disbelief values associated with one or more respective nodes and associated hypothesis;

propagating the updated current node parameter values through the belief network;

determining if a user overfire has been invoked and if at least one of the current node parameter values has been modified, wherein modifying a current node parameter values is one of overriding node parameter values, adding to node parameter values and modifying link values associated with a node;

propagating the modified current node parameters backward through the belief network if at least one of the current node parameter values has been modified;

selecting the number of layers of the network to back propagate the modified current node parameters backward through the belief network, the number of layers associated with a node layer containing the modified current node parameters; and

propagating the belief network downward after propagating the network backward through the network.

24. The computer readable medium of claim 23, the belief network being a Dempster-Shafer belief network.

25. The computer readable medium of claim 23, further comprising comparing node parameter values of the belief network with node parameter values of another belief network to determine the effectiveness of one belief network with respect to the other.

26. The computer readable medium of claim 23, further comprising perturbing the new evidence prior to fusing the new evidence with the current node parameter values.

27. The computer readable medium of claim 23, further comprising graphically displaying node parameter values over time in a temporal display.

28. A computer readable medium having computer executable instructions for performing a method, the method comprising:

extracting an actual node belief value from a belief network residing in memory;

determining an inverse on the actual node belief value and a desired belief value to determine a difference node belief value corresponding to the amount of evidence necessary to achieve the desired belief value, the amount of evidence being the difference in a belief value necessary to achieve the desired belief value;

associating a linguistic term with the determined difference node belief value;

providing the difference node belief value and the associated linguistic term to a graphical user interface; and

displaying the difference node belief value and the associated linguistic term via the graphical user interface on a display.

29. The computer readable medium of claim 28, the belief network being a Dempster-Shafer belief network and the inverse being determined for a disbelief value and an unknown value in addition to the belief value.

30. The computer readable medium of claim 29, the inverse being determined by evaluating the relationships:

B=−

b/[(b+u)(u−

bd/{b+u}−

bd/{d+u})];

U=1/(u−

bd/{b+u}−

bd/{d+u}); and

D=−

d/[(d+u)(u−

bd/{b+u}−

bd/{d+u})]

where b is the current belief value, d is the current disbelief value and u is the unknown value of the evidence, B is the belief value, D is the disbelief value and U is the unknown value of the inverse matrix.

31. A system for fusing evidence in a Dempster-Shafer belief network having a plurality of node layers, the system comprising:

means for storing a Dempster-Shafer belief network having a plurality of node layers and associated node parameters, each node representing a given hypothesis associated with the decision network and associated node parameters comprising belief values and disbelief values associated with a respective hypothesis;

means for processing executable instructions and accessing the means for storing;

means for fusing new evidence with current node parameters associated with nodes of the Dempster-Shafer belief network, the new evidence being new belief values and new disbelief values associated with one or more respective nodes and associated hypothesis;

means for overriding current node parameters associated with nodes within the plurality of node layers;

means for automatically back propagating modified node parameters through the Dempster-Shafer belief network;

means for displaying the plurality of multiple layers of nodes and associated links between the plurality of multiple layers of nodes and associated node parameters in a network view;

means for degrading the current node parameters over time in the means for displaying a graphical view of current node parameters; and

means for determining an inverse of current node parameters and desired node parameters to provide difference node parameters corresponding to additional evidence required to reach a decision threshold.

32. The system of claim 31, further comprising means for displaying a graphical view of current node parameters over time associated with a selected node.

33. The system of claim 31, further comprising means for overlaying node parameters of two Dempster-Shafer belief networks.

34. The system of claim 31, further comprising means for perturbing new evidence prior to fusing the evidence with the current node parameters.