Viterbi path generation for a dynamic Bayesian network

• US 20060212786A1
• Filed: 02/13/2006
• Published: 09/21/2006
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Hu, Wei, Zhang, Yimin
• Granted Patent: US 7,584,408 B2
• Time in Patent Office: Days
• US Class Current: 714/795
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Methods, systems, and apparatus are provided to generate a Viterbi path for a DBN. The DBN is converted to a chain of junction trees, where each tree represents a decision-making process. The trees are forwardly iterated and the Viterbi path is generated during the forward iteration (forward pass). This is achieved by maintaining backpointers to previously processed junction trees during the forward pass and dynamically assembling the Viterbi with each pair of junction trees during the forward pass.

Claims

1. A method, comprising:

(a) forwardly iterating trees of a Dynamic Bayesian Network (DBN) representing a decision process implemented in a computer-accessible medium; and

(b) dynamically building a Viterbi path during forward iterations of (a) for a given problem.

2. The method of claim 1 further comprising:

(c) selectively backwardly evaluating pairs of the trees; and

(d) dynamically assembling variables of the pairs that are needed for dynamically building the Viterbi path.

3. The method of claim 1 wherein (a) further includes (1) maintaining back pointers to previously processed trees and providing the back pointers to (b) for each iteration of (a).

4. The method of claim 3 wherein (a) further includes (2) providing the back pointers in data structures indexed on a current iteration through the trees for (a).

5. The method of claim 1 wherein (b) further includes (1) performing a local backtrack operation on a previously processed tree during iterations of (a).

6. The method of claim 5 wherein (1) further includes (2) iterating children nodes of a parent node identified as a root node of the previously processed tree.

7. The method of claim 5 wherein (1) further includes (2) identifying a best path from iterating the children nodes and concatenating the best path to the Viterbi path.

8. A method, comprising:

receiving a Dynamic Bayesian Network (DBN) representation of a decision process in a computer-accessible medium;

providing a Viterbi path generator that when processed forwardly iterates the DBN and dynamically constructs a Viterbi path through the DBN while forwardly iterating.

9. The method of claim 8 wherein providing further includes maintaining, by the Viterbi path generator when executed, pointers to previously processed trees of the DBN, wherein the pointers are used during iterations to determine a best path through each previously processed tree, and wherein the best paths are assembled as the Viterbi path.

10. The method of claim 8 further comprising executing the Viterbi path generator to acquire the Viterbi path and a result for the decision process, wherein the Viterbi path is a most probable explanation for reaching the result for a given problem.

11. The method of claim 10 wherein executing further includes using the Viterbi path of the decision process for obtaining the result wherein the result is an answer related to the problem, and the problem and the answer are communicated via speech and captured and processed in a computer-accessible medium.

12. The method of claim 8 wherein receiving further includes representing the DBN as a series of trees and each tree representing a series of discrete states for a portion of the decision process.

13. The method of claim 12 wherein receiving further includes identifying a number of the trees as interface cliques, in-cliques, and out-cliques.

14. The method of claim 13 wherein receiving further includes grouping sets of the cliques as junction trees.

15. A system, comprising:

a Dynamic Bayesian Network (DBN) generator to generate and to provide an electronic representation of a decision process as a DBN in a computer-accessible medium; and

a dynamic Viterbi path generator that when processed forwardly iterates the DBN and dynamically constructs a Viterbi path through the DBN during the forward iterations.

16. The system of claim 15 wherein the DBN includes junction trees having in-cliques and out-cliques, and wherein the DBN includes interface cliques linked to each junction tree.

17. The system of claim 15 wherein the dynamic Viterbi path generator examines probabilities and values for known variables of a given problem while forwardly iterating the DBN in order to generate the Viterbi path.

18. The system of claim 17 wherein the Viterbi path is a most probable explanation for a result of the problem.

19. A machine accessible medium having associated data, which when accessed, results in a machine performing:

(a) forwardly iterating an electronic representation of a decision process represented as a Dynamic Bayesian Network (DBN); and

(b) dynamically building a Viterbi path through the DBN for a most probable explanation for a result of a problem being posed to the decision process during forward iterations of (a).

20. The medium of claim 19 wherein the DBN includes trees having nodes identified as decision states and the nodes are linked within and between the trees as state transitions.

21. The medium of claim 20 wherein the decision states are sub trees within the DBN.

22. The medium of claim 19 wherein the problem is communicated and analyzed within the medium as at least one of audio, video, and image data.

23. An apparatus comprising:

a Dynamic Bayesian Network (DBN) representing a decision process in a computer-accessible medium; and

a path generator to forwardly iterate the DBN for a given problem and to dynamically generate a Viterbi path through the DBN for the problem during the forward iteration.

24. The apparatus of claim 23 wherein the DBN includes junction trees, in-clique trees, and out-clique trees representing various decision states and relationships between the decision states to one another.

25. The apparatus of claim 24 wherein the Viterbi path is the most probable explanation for a result of the problem.