Evidence decay in probabilistic trees via pseudo virtual evidence

An apparatus comprising:

• at least one processor configured to:
• implement a probabilistic graphical model (PGM) of random variables whose conditional dependence is represented by a probabilistic tree structure including parent and child nodes that represent unobservable query and observable evidence random variables, each node having a belief vector of n possible values whose probabilities sum to one for a random variable, said belief vectors computed by inference using belief propagation (BP) in which lambda messages representing the probability of a sub-network below the parent node given the belief of the parent node are passed upwards to the parent nodes and pi messages representing the probability of a sub-network including the parent node and above are passed downward to each child node, said method comprising:
• initialize the PGM by executing BP on the tree structure to assign current beliefs to each belief vector for all of the nodes;
• create virtual evidence nodes for one or more nodes representative of observable evidence variables;
• upon occurrence of an evidence update, applying evidence to the model by,
• update the current belief to a deterministic state in which a single value equals 1 based on an observation of the random variable for that node;
• and
• for any node within a decay period after an observation, said virtual evidence node
• compute a step along a path from the node's current belief to a target belief at the end of the decay period to determine a specified belief, and
• generate a lambda message that when combined with other evidence in the model forces a specified belief onto the node;
• execute BP on the tree structure to process the pi and lambda messages to update the current beliefs;
• and
• for each node within the decay period, execute BP on the tree structure absent the evidence of that node and saving the resulting belief as an updated target belief.

A non-transitory machine-readable medium including instructions which, when executed by at least one processor, cause the at least one processor to:

• implement a probabilistic graphical model (PGM) of random variables whose conditional dependence is represented by a probabilistic tree structure including parent and child nodes that represent unobservable query and observable evidence random variables, each node having a belief vector of n possible values whose probabilities sum to one for a random variable, said belief vectors computed by inference using belief propagation (BP) in which lambda messages representing the probability of a sub-network below the parent node given the belief of the parent node are passed upwards to the parent nodes and pi messages representing the probability of a sub-network including the parent node and above are passed downward to each child node, said method comprising:
• initialize the PGM by executing BP on the tree structure to assign current beliefs to each belief vector for all of the nodes;
• create virtual evidence nodes for one or more nodes representative of observable evidence variables;
• upon occurrence of an evidence update, applying evidence to the model by,
• update the current belief to a deterministic state in which a single value equals 1 based on an observation of the random variable for that node;
• and
• for any node within a decay period after an observation, said virtual evidence node
• remove evidence of the observation from the node at the onset of the decay period,
• compute a step along a path from the node's current belief to a target belief at the end of the decay period to determine a specified belief, and
• generate a lambda message that when combined with other evidence in the model forces a specified belief onto the node;
• execute BP on the tree structure to process the pi and lambda messages to update the current beliefs;
• and
• for each node within the decay period, execute BP on the tree structure absent the evidence of that node and saving the resulting belief as an updated target belief.