Methods for monitoring conflicts in inference systems

• US 7,447,670 B1
• Filed: 09/08/2005
• Issued: 11/04/2008
• Est. Priority Date: 09/08/2005
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Chen, Yang
• Primary Examiner(s): Starks, Jr.; Wilbert L
• Application Number:
  US11/223,858
• Time in Patent Office: 1,153 Days
• Field of Search: 705/37, 382/103, 706/25, 706/52, 706/45
• US Class Current: 706/52
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

The present invention provides a system and a method to keep track of conflicts resulting from combining basic probability assignments (BPAs) without actually performing the normalization operation at every step of combination. This approach can be applied recursively, allowing the system to keep track of the normalization and conflict of the belief combinations inside a large belief inference system without ever performing a normalization operation as long as the computing system precision allows. The present invention can be applied to monitor conflicts within most inference systems, including the Valuation Based System (VBS) framework for Dempster-Shafer (D-S) evidential reasoning.

Claims

1. A method for determining valuation-based system characteristics of a physical system represented as a set of basic probability assignments (BPAs), the method comprising acts, performed on a data processing system, of:

receiving a sequence of normalized basic probability assignments (BPAs) designated m_i, for index i=1, . . . , n;

having intermediate combined, unnormalized BPAs designated m′

⁽ⁿ⁾;

determining a valuation-based system characteristic selected from a group consisting of

a local cumulative normalization factor,

a local incremental normalization factor,

a local cumulative conflict measure,

a local incremental conflict measure,

a global cumulative normalization factor,

a Type I global incremental normalization factor,

a Type II global incremental normalization factor,

a global cumulative conflict measure,

a Type I global incremental conflict measure, and

a Type II global incremental conflict measure

determined from;

k₁₂=k/(k₁k₂),

where

k₁ is a normalization factor for a first BPA m₁,

k₂ is a normalization factor for a second BPA m₂,

k is an overall normalization factor, and

k₁₂ represents an incremental normalization factor;

outputting the valuation-based system characteristic;

whereby the valuation-based system characteristic provides information for evaluating the physical system.

2. A method as set forth in claim 1, where the valuation-based system characteristic determined is a local cumulative normalization factor, determined from:

$k^{\left(n\right)}=\underset{\forall <br><br>A\subseteq <br><br>\mathrm{\Theta <br><br>}}{\sum <br><br>}<br><br>m^{\mathrm{\prime <br><br>}<br><br>\left(n\right)}<br><br>\left(A\right),$

where;

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n;

m′

⁽ⁿ⁾ denotes an non-normalized, combined BPA, and is represented by a recursive relation m′

⁽ⁿ⁾=m′

^(n-1){circle around (×

)}m_n, having an initial condition m′

⁽⁰⁾=m₀, where m₀ is a normalized BPA initially residing in a node under consideration; and

A denotes a subset of Θ

, where Θ

represents a collection of exclusive and collectively exhaustive outcomes of states of the physical system represented by a node under consideration for the valuation-based system.

3. A method as set forth in claim 2, wherein the valuation-based system characteristic is a local cumulative conflict measure, determined from:

C⁽ⁿ⁾=1−

k⁽ⁿ⁾,

where;

C⁽ⁿ⁾ denotes the local cumulative conflict measure, cumulative to a current BPA m_n; and

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n.

4. A method as set forth in claim 2, where the valuation-based system is represented by a Markov Tree, and wherein the valuation-based system characteristic is a global cumulative normalization factor, determined from:

$k_{\mathrm{\Sigma <br><br>}}=\underset{\forall <br><br>A\subseteq <br><br>\mathrm{\Theta <br><br>}}{\sum <br><br>}<br><br>m_{\mathrm{\Sigma <br><br>}}^{\mathrm{\prime <br><br>}}<br><br>\left(A\right);<br><br>$

where

k_Σ

denotes the global cumulative normalization factor;

m′

_Σ

denotes an non-normalized, combined BPA, and is equal to m′

⁽ⁿ⁾{circle around (×

)}m_δ

, and m_δ

represents a combination of messages from all neighboring nodes; and

A denotes a subset of Θ

, where Θ

represents a collection of exclusive and collectively exhaustive outcomes of states of the physical system represented by a node under consideration for the valuation-based system.

5. A method as set forth in claim 1, where the valuation-based system characteristic determined is a local incremental normalization factor, determined from:

k_n=k⁽ⁿ⁾/k^(n-1),

where;

k_n denotes the local incremental normalization factor;

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n; and

k^(n-1) denotes a local cumulative normalization factor, cumulative to a previous BPA m_n-1.

6. A method as set forth in claim 5, wherein the valuation-based system characteristic is a local incremental conflict measure, determined from:

C_n=1−

k_n;

where;

C_n denotes the local incremental conflict measure; and

k_n denotes the local incremental normalization factor.

7. A method as set forth in claim 1, wherein the valuation-based system characteristic is a local cumulative conflict measure, determined from:

C⁽ⁿ⁾=1−

k⁽ⁿ⁾,

where;

C⁽ⁿ⁾ denotes the local cumulative conflict measure, cumulative to a current BPA m_n; and

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n.

8. A method as set forth in claim 1, wherein the valuation-based system characteristic is a local incremental conflict measure, determined from:

C_n=1−

k_n;

where;

C_n denotes the local incremental conflict measure; and

k_n denotes the local incremental normalization factor.

9. A method as set forth in claim 1, where the valuation-based system is represented by a Markov Tree, and wherein the valuation-based system characteristic is a global cumulative normalization factor, determined from:

$k_{\mathrm{\Sigma <br><br>}}=\underset{\forall <br><br>A\subseteq <br><br>\mathrm{\Theta <br><br>}}{\sum <br><br>}<br><br>m_{\mathrm{\Sigma <br><br>}}^{\mathrm{\prime <br><br>}}<br><br>\left(A\right);<br><br>$

where

k_Σ

denotes the global cumulative normalization factor;

m′

_Σ

denotes an unnormalized, combined BPA, and is equal to m′

⁽ⁿ⁾{circle around (×

)}m_δ

, and m_δ

represents the combination of messages from all neighboring nodes; and

A denotes a subset of Θ

, where Θ

represents a collection of exclusive and collectively exhaustive outcomes of states of the physical system represented by a node under consideration for the valuation-based system.

10. A method as set forth in claim 9, where the valuation-based system characteristic is a Type I global incremental normalization factor, determined from:

k_I,n=k_Σ

/k<sub>Σ

-1</sub>;

where

k_I,n denotes the Type I global incremental normalization factor; and

k_Σ

and k<sub>Σ

-1</sub> are the global cumulative normalization factors for a current BPA (m_n) and a previous BPA (m_n-1).

11. A method as set forth in claim 9, where the valuation-based system characteristic is a Type II global incremental normalization factor, determined from:

k_II,n=k_Σ

/(k⁽ⁿ⁾k_δ

);

where

k_II,n denotes the Type II global incremental normalization factor;

k_Σ

denotes the global cumulative normalization factors for the current input BPA (m_n);

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n; and

k_δ

denotes the cumulative normalization factor for m_δ

, which is a combined BPA of all messages from neighboring nodes.

12. A method as set forth in claim 1, where the valuation-based system characteristic is a Type I global incremental normalization factor, determined from:

k_I,n=k_Σ

/k<sub>Σ

-1</sub>;

where

k_I,n denotes the Type I global incremental normalization factor; and

k_Σ

and k<sub>Σ

-1</sub> are the global cumulative normalization factors for the current input BPA (m_n) and the previous input BPA (m_n-1).

13. A method as set forth in claim 12, where the valuation-based system characteristic is a global cumulative conflict measure, determined from:

C_Σ

=1−

k_Σ

;

where;

C_Σ

denotes the global cumulative conflict measure; and

k_Σ

denotes the global cumulative normalization factor.

14. A method as set forth in claim 12, where the valuation-based system characteristic is a Type I global incremental conflict measure, determined from:

C_I,n=1−

k_I,n;

where

C_I,n denotes the Type I global incremental conflict measure;

k_I,n denotes the Type I global incremental normalization factor.

15. A method as set forth in claim 1, where the valuation-based system characteristic is a Type II global incremental normalization factor, determined from:

k_II,n=k_Σ

/(k⁽ⁿ⁾k_δ

);

where

k_II,n denotes the Type II global incremental normalization factor;

k_Σ

denotes the global cumulative normalization factors for the current input BPA (m_n);

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n; and

k_δ

denotes the cumulative normalization factor for m_δ

, which is the combined BPA of all messages from neighboring nodes.

16. A method as set forth in claim 15, where the valuation-based system characteristic is a Type II global incremental conflict measure, determined from:

C_II,n=1−

k_II,n;

where

C_II,n denotes the Type II global incremental conflict measure; and

k_II,n denotes the Type II global incremental normalization factor.

17. A method as set forth in claim 1, where the valuation-based system characteristic is a global cumulative conflict measure, determined from the relationship:

C_Σ

=1−

k_Σ

;

where;

C_Σ

denotes the global cumulative conflict measure; and

k_Σ

denotes the global cumulative normalization factor.

18. A method as set forth in claim 1, where the valuation-based system characteristic is a Type I global incremental conflict measure, determined from the relationship:

C_I,n=1−

k_I,n;

where

C_I,n denotes the Type I global incremental conflict measure; and

k_I,n denotes the Type I global incremental normalization factor.

19. A method as set forth in claim 1, where the valuation-based system characteristic is a Type II global incremental conflict measure, determined from the relationship:

C_II,n=1−

k_II,n;

where

C_II,n denotes the Type II global incremental conflict measure; and

k_II,n denotes the Type II global incremental normalization factor.

20. A computer program product for determining valuation-based system characteristics of a physical system represented as a set of basic probability assignments (BPAs) on a data processing system, the computer program product comprising a computer-readable medium having computer program instructions stored therein for causing a computer to perform operations of:

receiving a sequence of normalized basic probability assignments (BPAs) designated m_i, for index i=1, . . . , n;

having intermediate combined, unnormalized BPAs designated m′

⁽ⁿ⁾;

determining a valuation-based system characteristic selected from a group consisting of

a local cumulative normalization factor,

a local incremental normalization factor,

a local cumulative conflict measure,

a local incremental conflict measure,

a global cumulative normalization factor,

a Type I global incremental normalization factor,

a Type II global incremental normalization factor,

a global cumulative conflict measure,

a Type I global incremental conflict measure, and

a Type II global incremental conflict measure

determined from;

k₁₂=k/(k₁k₂),

where

k₁ is a normalization factor for a first BPA m₁,

k₂ is a normalization factor for a second BPA m₂,

k is an overall normalization factor, and

k₁₂ represents an incremental normalization factor;

outputting the valuation-based system characteristic;

whereby the valuation-based system characteristic provides information for evaluating the physical system.

21. The computer program product as set forth in claim 20, where the valuation-based system characteristic determined is a local cumulative normalization factor, determined from:

$k^{\left(n\right)}=\underset{\forall <br><br>A\subseteq <br><br>\mathrm{\Theta <br><br>}}{\sum <br><br>}<br><br>m^{\mathrm{\prime <br><br>}<br><br>\left(n\right)}<br><br>\left(A\right),$

where;

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n;

m′

⁽ⁿ⁾ denotes an non-normalized, combined BPA, and is represented by a recursive relation m′

⁽ⁿ⁾=m′

^(n-1){circle around (×

)}m_n, having an initial condition m′

⁽⁰⁾=m₀, where m₀ is a normalized BPA initially residing in a node under consideration; and

A denotes a subset of Θ

, where Θ

represents a collection of exclusive and collectively exhaustive outcomes of states of the physical system represented by a node under consideration for the valuation-based system.

22. The computer program product as set forth in claim 21, wherein the valuation-based system characteristic is a local cumulative conflict measure, determined from:

C⁽ⁿ⁾=1−

k⁽ⁿ⁾,

where;

C⁽ⁿ⁾ denotes the local cumulative conflict measure, cumulative to a current BPA m_n; and

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n.

23. The computer program product as set forth in claim 21, where the valuation-based system is represented by a Markov Tree, and wherein the valuation-based system characteristic is a global cumulative normalization factor, determined from:

$k_{\mathrm{\Sigma <br><br>}}=\underset{\forall <br><br>A\subseteq <br><br>\mathrm{\Theta <br><br>}}{\sum <br><br>}<br><br>m_{\mathrm{\Sigma <br><br>}}^{\mathrm{\prime <br><br>}}<br><br>\left(A\right);<br><br>$

where

k_Σ

denotes the global cumulative normalization factor;

m′

_Σ

denotes an non-normalized, combined BPA, and is equal to m′

⁽ⁿ⁾{circle around (×

)}m_δ

, and m_δ

represents a combination of messages from all neighboring nodes; and

A denotes a subset of Θ

, where Θ

represents a collection of exclusive and collectively exhaustive outcomes of states of the physical system represented by a node under consideration for the valuation-based system.

24. The computer program product as set forth in claim 20, where the valuation-based system characteristic determined is a local incremental normalization factor, determined from:

k_n=k⁽ⁿ⁾/k^(n-1),

where;

k_n denotes the local incremental normalization factor;

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n; and

k^(n-1) denotes a local cumulative normalization factor, cumulative to a previous BPA m_n-1.

25. The computer program product as set forth in claim 24, wherein the valuation-based system characteristic is a local incremental conflict measure, determined from:

C_n=1−

k_n;

where;

C_n denotes the local incremental conflict measure; and

k_n denotes the local incremental normalization factor.

26. The computer program product as set forth in claim 20, wherein the valuation-based system characteristic is a local cumulative conflict measure, determined from:

C⁽ⁿ⁾=1−

k⁽ⁿ⁾,

where;

C⁽ⁿ⁾ denotes the local cumulative conflict measure, cumulative to a current BPA m_n; and

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n.

27. The computer program product as set forth in claim 20, wherein the valuation-based system characteristic is a local incremental conflict measure, determined from:

C_n=1−

k_n;

where;

C_n denotes the local incremental conflict measure; and

k_n denotes the local incremental normalization factor.

28. The computer program product as set forth in claim 20, where the valuation-based system is represented by a Markov Tree, and wherein the valuation-based system characteristic is a global cumulative normalization factor, determined from:

$k_{\mathrm{\Sigma <br><br>}}=\underset{\forall <br><br>A\subseteq <br><br>\mathrm{\Theta <br><br>}}{\sum <br><br>}<br><br>m_{\mathrm{\Sigma <br><br>}}^{\mathrm{\prime <br><br>}}<br><br>\left(A\right);<br><br>$

where

k_Σ

denotes the global cumulative normalization factor;

m′

_Σ

denotes an unnormalized, combined BPA, and is equal to m′

⁽ⁿ⁾{circle around (×

)}m_δ

, and m_δ

represents the combination of messages from all neighboring nodes; and

A denotes a subset of Θ

, where Θ

represents a collection of exclusive and collectively exhaustive outcomes of states of the physical system represented by a node under consideration for the valuation-based system.

29. The computer program product as set forth in claim 28, where the valuation-based system characteristic is a Type I global incremental normalization factor, determined from:

k_I,n=k_Σ

/k<sub>Σ

-1</sub>;

where

k_I,n denotes the Type I global incremental normalization factor; and

k_Σ

and k<sub>Σ

-1</sub> are the global cumulative normalization factors for a current BPA (m_n) and a previous BPA (m_n-1).

30. The computer program product as set forth in claim 28, where the valuation-based system characteristic is a Type II global incremental normalization factor, determined from:

k_II,n=k_Σ

/(k⁽ⁿ⁾k_δ

);

where

k_II,n denotes the Type II global incremental normalization factor;

k_Σ

denotes the global cumulative normalization factors for the current input BPA (m_n);

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n; and

k_δ

denotes the cumulative normalization factor for m_δ

, which is a combined BPA of all messages from neighboring nodes.

31. The computer program product as set forth in claim 20, where the valuation-based system characteristic is a Type I global incremental normalization factor, determined from:

k_I,n=k_Σ

/k<sub>Σ

-1</sub>;

where

k_I,n denotes the Type I global incremental normalization factor; and

k_Σ

and k<sub>Σ

-1</sub> are the global cumulative normalization factors for the current input BPA (m_n) and the previous input BPA (m_n-1).

32. The computer program product as set forth in claim 31, where the valuation-based system characteristic is a global cumulative conflict measure, determined from:

C_Σ

=1−

k_Σ

;

where;

C_Σ

denotes the global cumulative conflict measure; and

k_Σ

denotes the global cumulative normalization factor.

33. The computer program product as set forth in claim 31, where the valuation-based system characteristic is a Type I global incremental conflict measure, determined from:

C_I,n=1−

k_I,n;

where

C_I,n denotes the Type I global incremental conflict measure;

k_I,n denotes the Type I global incremental normalization factor.

34. The computer program product as set forth in claim 20, where the valuation-based system characteristic is a Type II global incremental normalization factor, determined from:

k_II,n=k_Σ

/(k⁽ⁿ⁾k_δ

);

where

k_II,n denotes the Type II global incremental normalization factor;

k_Σ

denotes the global cumulative normalization factors for the current input BPA (m_n);

k⁽ⁿ⁾ denotes the local cumulative normalization factor, cumulative to a current BPA m_n; and

k_δ

denotes the cumulative normalization factor for m_δ

, which is the combined BPA of all messages from neighboring nodes.

35. The computer program product as set forth in claim 34, where the valuation-based system characteristic is a Type II global incremental conflict measure, determined from:

C_II,n=1−

k_II,n;

where

C_II,n denotes the Type II global incremental conflict measure; and

k_II,n denotes the Type II global incremental normalization factor.

36. The computer program product as set forth in claim 20, where the valuation-based system characteristic is a global cumulative conflict measure, determined from the relationship:

C_Σ

=1−

k_Σ

;

where;

C_Σ

denotes the global cumulative conflict measure; and

k_Σ

denotes the global cumulative normalization factor.

37. The computer program product as set forth in claim 20, where the valuation-based system characteristic is a Type I global incremental conflict measure, determined from the relationship:

C_I,n=1−

k_I,n;

where

C_I,n denotes the Type I global incremental conflict measure; and

k_I,n denotes the Type I global incremental normalization factor.

38. The computer program product as set forth in claim 20, where the valuation-based system characteristic is a Type II global incremental conflict measure, determined from the relationship:

C_II,n=1−

k_II,n;

where

C_II,n denotes the Type II global incremental conflict measure; and

k_II,n denotes the Type II global incremental normalization factor.