3 ms·
In practice, one of the main issues with DST is the computational complexity inherent in its reasoning approach. Here are two classic meta-studies devoted to ap
by kleiba 12y ago
In practice, one of the main issues with DST is the computational complexity inherent in its reasoning approach. Here are two classic meta-studies devoted to approximation algorithms that try to tackle this problem:
[1] Tessem, B., Approximations for efficient computation in the theory of evidence, Artificial Intelligence 61,315-329, 1993.
http://www.sciencedirect.com/science/article/pii/000437029390072J http://www.sciencedirect.com/science/article/pii/00043702939... (behind Elsevier paywall)
[2] Bauer, M., Approximation Algorithms and Decision Making in the Dempster-Shafer Theory of Evidence--An Empirical study. International Journal of Approximate Reasoning, Volume 17, Issues 2–3, August–October 1997, Pages 217–237
http://www.sciencedirect.com/science/article/pii/S0888613X97000133 http://www.sciencedirect.com/science/article/pii/S0888613X97...
The first one focuses on quantitative deviations while the second paper considers the qualitaty of a decision.
- eli_gottlieb 12y agoOf course, probabilistic reasoning has similar computational problems, especially related to numerical evaluation of integrals in the denominator of Bayes' Rule. This is why there's a lot of research into how to make variational and Markov-Chain Monte Carlo methods run faster.