Incremental Dynamic Construction of Layered Polytree Networks
Keung-Chi Ng, Tod Levitt
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.
Keywords: Incremental, dynamically constructed networks, incremental inference, polytree, layer
PS Link: ftp://camis.stanford.edu/pub/ng-levitt.uai94.ps.Z
PDF Link: /papers/94/p440-ng.pdf
AUTHOR = "Keung-Chi Ng
and Tod Levitt",
TITLE = "Incremental Dynamic Construction of Layered Polytree Networks",
BOOKTITLE = "Proceedings of the Tenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-94)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1994",
PAGES = "440--446"