Premium
Novel strategies to approximate probability trees in penniless propagation
Author(s) -
Cano Andrés,
Moral Serafín,
Salmerón Antonio
Publication year - 2003
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.10083
Subject(s) - pruning , tree (set theory) , computer science , measure (data warehouse) , mathematics , algorithm , quality (philosophy) , data mining , combinatorics , philosophy , epistemology , agronomy , biology
In this article we introduce some modifications over the Penniless propagation algorithm. When a message through the join tree is approximated, the corresponding error is quantified in terms of an improved information measure, which leads to a new way of pruning several values in a probability tree (representing a message) by a single one, computed from the value stored in the tree being pruned but taking into account the message stored in the opposite direction. Also, we have considered the possibility of replacing small probability values by zero. Locally, this is not an optimal approximation strategy, but in Penniless propagation many different local approximations are carried out in order to estimate the posterior probabilities and, as we show in some experiments, replacing by zeros can improve the quality of the final approximations. © 2003 Wiley Periodicals, Inc.