opening it up with Common Lisp

Favorite weblogs

Lisp Related

Bill Clementson

Finding Lisp


Planet Lisp



Talking Points Memo

This Modern World

Working for Change

Other home


Recent Readings

Book review: Darwinia
Reviewed: Friday, August 11, 2006

Summer reading: Spin
Reviewed: Saturday, August 5, 2006

Reviewed: Tuesday, July 18, 2006

the Omnivoire's Delimma
Reviewed: Wednesday, July 12, 2006

the Golem's Eye
Reviewed: Wednesday, May 31, 2006


Constructing Flexible Dynamic Belief Networks from First-Order Probabalistic Knowledge Bases
Sabine Glesner and Daphne Koller, 1995 , (Paper URL)
Monday, June 28, 2004

Glesner and Koller use Knowledge Based Model Construction (KBMC) to build Dynamic Bayesian Networks extended with a probabilistic First Order Logic (FOL). They also use an FOL to express probability distributions compactly. In particular, they can represent Conditional Probability Tables (CPTs) as decision trees. This is particularly helpful in asymmetric situations where, for example, variable A is dependent on variable B for only certain values of variable C.

Probabalistic FOL adds a probability distribution to the set of possible worlds (models). It is undecidable but one can make headway by restricting the full power of PFOL. For example, Haddawy and Krieger represent a class of Bayesian Networks (BN) using a subset of PFOL. They assume:

  • Each rule body must be the head of some other rule
  • All variables in the body also appear in the head
  • No two rules have ground instances (instances with no variables) with identical heads
  • The rules are acyclic.

Glesner and Koller relax the third rule and make an end-run around the fourth by adding time (so that the tail of a rule can point at the head of the same rule in the next time step). They use the by now familiar "canonical" ICI influence combination methods such as noisy-or. They attach the method to particular nodes in the belief networks (whereas I think that it only makes sense to attach them between pairs of nodes).

Given the rule set, the influence combination annotations and incoming evidence, they can construct a BN incrementally. All of the logic is sound and complete because it is based on Haddawy and Krieger and a similar proof works for both. Finally, the decision tree CPT representation makes making pruning decisions easier so that the resulting netwokrk doesn't get out of control too quickly.

This is more an "idea" paper than a "system" one. In this case, the ideas are quite interesting but there are a few too many "it would be straight forward" assertions to leave one feeling completely comfortable. For example, the pruning work had not actually been done and there are allusions to adding "roll-up" and handle multiple scale temporal reasoning that were as yet just twinkles in the authors eyes. The paper is well expressed, however, and adds another valuable flower to the Bayesian Model construction garden.

Home | About | Quotes | Recent | Archives

Copyright -- Gary Warren King, 2004 - 2006