The effect of finite set representations on the evaluation of Dempster’s rule of combination
Martin G. Oxenham · International Conference on Information Fusion · 2008
Overcoming the computational complexity of Dempsterpsilas rule of combination for fusing data and information continues to be an actively researched problem within Dempster-Shafer theory. Previous efforts to reduce the computational complexity have employed a variety of strategies. However, most have avoided directly evaluating the expression for combining two belief potentials because this involves calculating all possible intersections of the focal elements of one belief potential with those of the other. For a frame of discernment Omega of size n, the typical way of representing the focal elements (subsets of Omega) is as binary strings of length n. Set operations such as the intersection of two focal elements are then performed bitwise and so algorithms for set operations generally have complexity O(n). In this paper, the effect of reducing the computational complexity of the set operations is investigated to see what impact this may have on the overall effectiveness of the direct computation of Dempsterpsilas rule of combination. First finite field theory is used to determine a representation of focal elements for which set operations can be performed with complexity O(1). Using this representation, Monte Carlo simulations are then employed to compare the direct calculation of Dempsterpsilas rule of combination against arguably the fastest known approach which is that based on the use of the commonalities of the belief potentials in conjunction with the fast Mobius transform. The paper concludes with some discussion on the efficacy of the technique and some ideas for future research.