  Certain classes of problems, including perceptual data understanding,
robotics, discovery, and learning, can be represented as incremental,
dynamically constructed belief networks. These automatically constructed
networks can be dynamically extended and modified as evidence of new
individuals becomes available. The main result of this paper is the incremental
extension of the singly connected polytree network in such a way that the
network retains its singly connected polytree structure after the changes. The
algorithm is deterministic and is guaranteed to have a complexity of single
node addition that is at most of order proportional to the number of nodes (or
size) of the network. Additional speed-up can be achieved by maintaining the
path information. Despite its incremental and dynamic nature, the algorithm can
also be used for probabilistic inference in belief networks in a fashion
similar to other exact inference algorithms.
