Viterbi path generation for a Dynamic Bayesian Network

• US 7,584,408 B2
• Filed: 02/13/2006
• Issued: 09/01/2009
• Est. Priority Date: 09/30/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Hu, Wei, Zhang, Yimin
• Primary Examiner(s): Baker; Stephen M
• Application Number:
  US11/352,657
• Publication Number:
  US 20060212786A1
• Time in Patent Office: 1,296 Days
• Field of Search: 714/795, 704/242
• 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 implemented in a computer-accessible medium and executed on one or more processors, the 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; and

(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.

2. 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).

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

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

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

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