Monte-Carlo methods make Dempster-Shafer formalism feasible
Владик Крейнович, Andrew Bernat, Walter Borrett, Yvonne Mariscal, Elsa Villa · NASA Technical Reports Server (NASA) · 1994
Abstract: One of the main obstacles to the applications of Dempster-Shafer formalism is its computational complexity. If we combine rn different pieces of knowledge, then in general case we have to perform up to 2 m computational steps, which for large m is infeasible. For several important cases algorithms with smaller running time have been proposed. We prove, however, that if we want to compute the belief bd(Q) in any given query Q, then exponential time is inevitable. It is still inevitable, if we want to compute bel(Q) with given precision e. This restric-tion corresponds to the natural idea that since initial masses are known only approximately, there is no sense in trying to compute beI(Q) precisely. A further idea is that there is al-ways some doubt in the whole knowledge, so there is always a probability P0 that the expert's knowledge is wrong. In view of that it is sufficient to have an algorithm that gives a correct answer a probability> 1-P0. If we use the original Dempster's combination rule, this possibility diminishes the running time, but still leaves the problem infeasible in the general case. We show that for the alternative combination rules proposed by Smets and Yager