Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Incremental Dynamic Construction of Layered Polytree Networks
Keung-Chi Ng, Tod Levitt
Abstract:
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
Pages: 440-446
PS Link: ftp://camis.stanford.edu/pub/ng-levitt.uai94.ps.Z
PDF Link: /papers/94/p440-ng.pdf
BibTex:
@INPROCEEDINGS{Ng94,
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"
}


hosted by DSL   •   site info   •   help