An Efficient Triplet-Based Algorithm for Evidential Reasoning

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

Linear-time computational techniques based on the structure of an evidence space have beendeveloped for combining multiple pieces of evidence using Dempster’s rule (orthogonal sum),which is available on a number of contending hypotheses. They offer a means of making thecomputation-intensive calculations involved more efficient in certain circumstances. Unfortunately,they restrict the orthogonal sum of evidential functions to the dichotomous structure thatapplies only to elements and their complements. In this paper, we present a novel evidence structurein terms of a triplet and a set of algorithms for evidential reasoning. The merit of this structureis that it divides a set of evidence into three subsets, distinguishing the trivial evidential elementsfrom the important ones—focusing particularly on some elements of an evidence space. It avoidsthe deficits of the dichotomous structure in representing the preference of evidence and estimatingthe basic probability assignment of evidence. We have established a formalism for this structureand the general formulae for combining pieces of evidence in the form of the triplet, which havebeen theoretically and empirically justified. C
LanguageEnglish
Pages483-516
JournalInternational Journal of Intelligent Systems
Volume23
Issue number4
DOIs
Publication statusPublished - Apr 2008

Fingerprint

Evidential Reasoning
Evidence
Computational Techniques
Divides
Linear Time
Trivial
Assignment
Complement
Subset

Cite this

@article{a10de9c9af8148bcab5a11832605e0f3,
title = "An Efficient Triplet-Based Algorithm for Evidential Reasoning",
abstract = "Linear-time computational techniques based on the structure of an evidence space have beendeveloped for combining multiple pieces of evidence using Dempster’s rule (orthogonal sum),which is available on a number of contending hypotheses. They offer a means of making thecomputation-intensive calculations involved more efficient in certain circumstances. Unfortunately,they restrict the orthogonal sum of evidential functions to the dichotomous structure thatapplies only to elements and their complements. In this paper, we present a novel evidence structurein terms of a triplet and a set of algorithms for evidential reasoning. The merit of this structureis that it divides a set of evidence into three subsets, distinguishing the trivial evidential elementsfrom the important ones—focusing particularly on some elements of an evidence space. It avoidsthe deficits of the dichotomous structure in representing the preference of evidence and estimatingthe basic probability assignment of evidence. We have established a formalism for this structureand the general formulae for combining pieces of evidence in the form of the triplet, which havebeen theoretically and empirically justified. C",
author = "Yaxin Bi",
note = "Reference text: Denoeux T. A neural network classifier based on Dempster–Shafer theory. IEEE Trans Syst, Man Cybern A 2000;30(2):131–150. Kennes R, Smets Ph. Computational aspects of the Moebius transform. In Proc. of the 6th Conf. on Uncertainty in Artificial Intelligence, 1991. pp. 401–416. 3. Kennes R. Computational aspects of theM¨obius transform of graphs. IEEE Trans Syst, Man, Cybern 1992;22:201–223. 4. Moral S,Wilson N. Markov chainMonte–Carlo algorithms for the calculation of Dempster– Shafer belief. In: Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA. Menlo Park, CA. AAAI Press: 1994. pp. 269–274. 5. Wilson N. A Monte Carlo algorithm for Dempster–Shafer belief. In: Proc the 7th Conf. on Uncertainty in Artificial Intelligence; 1991. pp. 414–417. 6. Denoeux T, Yaghlane A. Approximating the combination of belief functions using the fast M¨obius transform in a coarsened frame. Special issue on Dempster–Shafer theory, methodology, and applications. Int J Approx Reason 2002;31(1/2): 77–101. 7. Haenni R, Lehmann N. Resource bounded and anytime approximation of belief function computations. Special issue on Dempster–Shafer theory, methodology, and applications. Int J Approx Reason 2002;31(1/2):103–154. 8. Barnett JA. Computational methods for a mathematical theory of evidence. In Proc. of 17th Joint Conf. of Artificial Intelligence, 1981; pp. 868–875. 9. Shafer G, Logan R. Implementing Dempsters rule for hierarchical evidence. Artif Intell 1987;33:271–298. 10. Gordon J, Shortliffe EH. A method for managing evidential reasoning in a hierarchical hypothesis space. Artif Intell 1985;26:323–357. 11. Guan J, Bell D. Computational methods for automated reasoning in knowledge based systems. In Proc. of Florid Artificial Intelligence Research Symposium; 1995. pp. 238–242. 12. Guan J, D. Bell D. Efficient algorithms for automated reasoning in expert systems. The 3rd IASTED Int. Conf. on Robotics and Manufacturing; 1995. pp. 336–339. 13. Srivastava R. Alternative form of Dempster’s rule for binary variables. Int J Intell Syst 2005;20(8):789-797. 14. Xu L, Krzyzak A, Suen CY. Several methods for combining multiple classifiers and their applications in handwritten character recognition. IEEE Trans. Syst, Man Cybern 1992;2(3):418–435. 15. Bi Y. Combining multiple classifiers for text categorization using the Dempster–Shafer theory of evidence, PhD thesis, University of Ulster, UK, 2004. 16. Bi Y, Guan J. An efficient triplet-based algorithm for evidential reasoning. In Proc of the 22nd Conference on Uncertainty in Artificial Intelligence; 2006. pp. 31–38. 17. Bi Y, McClean S, Anderson T. On combining multiple classifiers using an evidential approach. The Twenty-First National Conference on Artificial Intelligence (AAAI-06).Menlo Park, CA: AAAI Press; 2006. pp. 324–328. 18. Shafer G. A mathematical theory of evidence. Princeton, NJ: Princeton University Press, 1976. 19. Bi Y, Bell D,Wang H, Guo G, Guan J. Combining multiple classifiers for text categorization using Dempster’s rule of combination. J Appl Artif Intell 2007;21:211–239.",
year = "2008",
month = "4",
doi = "10.1002/int.20278",
language = "English",
volume = "23",
pages = "483--516",
journal = "International Journal of Intelligent Systems",
issn = "0884-8173",
number = "4",

}

An Efficient Triplet-Based Algorithm for Evidential Reasoning. / Bi, Yaxin.

In: International Journal of Intelligent Systems, Vol. 23, No. 4, 04.2008, p. 483-516.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An Efficient Triplet-Based Algorithm for Evidential Reasoning

AU - Bi, Yaxin

N1 - Reference text: Denoeux T. A neural network classifier based on Dempster–Shafer theory. IEEE Trans Syst, Man Cybern A 2000;30(2):131–150. Kennes R, Smets Ph. Computational aspects of the Moebius transform. In Proc. of the 6th Conf. on Uncertainty in Artificial Intelligence, 1991. pp. 401–416. 3. Kennes R. Computational aspects of theM¨obius transform of graphs. IEEE Trans Syst, Man, Cybern 1992;22:201–223. 4. Moral S,Wilson N. Markov chainMonte–Carlo algorithms for the calculation of Dempster– Shafer belief. In: Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA. Menlo Park, CA. AAAI Press: 1994. pp. 269–274. 5. Wilson N. A Monte Carlo algorithm for Dempster–Shafer belief. In: Proc the 7th Conf. on Uncertainty in Artificial Intelligence; 1991. pp. 414–417. 6. Denoeux T, Yaghlane A. Approximating the combination of belief functions using the fast M¨obius transform in a coarsened frame. Special issue on Dempster–Shafer theory, methodology, and applications. Int J Approx Reason 2002;31(1/2): 77–101. 7. Haenni R, Lehmann N. Resource bounded and anytime approximation of belief function computations. Special issue on Dempster–Shafer theory, methodology, and applications. Int J Approx Reason 2002;31(1/2):103–154. 8. Barnett JA. Computational methods for a mathematical theory of evidence. In Proc. of 17th Joint Conf. of Artificial Intelligence, 1981; pp. 868–875. 9. Shafer G, Logan R. Implementing Dempsters rule for hierarchical evidence. Artif Intell 1987;33:271–298. 10. Gordon J, Shortliffe EH. A method for managing evidential reasoning in a hierarchical hypothesis space. Artif Intell 1985;26:323–357. 11. Guan J, Bell D. Computational methods for automated reasoning in knowledge based systems. In Proc. of Florid Artificial Intelligence Research Symposium; 1995. pp. 238–242. 12. Guan J, D. Bell D. Efficient algorithms for automated reasoning in expert systems. The 3rd IASTED Int. Conf. on Robotics and Manufacturing; 1995. pp. 336–339. 13. Srivastava R. Alternative form of Dempster’s rule for binary variables. Int J Intell Syst 2005;20(8):789-797. 14. Xu L, Krzyzak A, Suen CY. Several methods for combining multiple classifiers and their applications in handwritten character recognition. IEEE Trans. Syst, Man Cybern 1992;2(3):418–435. 15. Bi Y. Combining multiple classifiers for text categorization using the Dempster–Shafer theory of evidence, PhD thesis, University of Ulster, UK, 2004. 16. Bi Y, Guan J. An efficient triplet-based algorithm for evidential reasoning. In Proc of the 22nd Conference on Uncertainty in Artificial Intelligence; 2006. pp. 31–38. 17. Bi Y, McClean S, Anderson T. On combining multiple classifiers using an evidential approach. The Twenty-First National Conference on Artificial Intelligence (AAAI-06).Menlo Park, CA: AAAI Press; 2006. pp. 324–328. 18. Shafer G. A mathematical theory of evidence. Princeton, NJ: Princeton University Press, 1976. 19. Bi Y, Bell D,Wang H, Guo G, Guan J. Combining multiple classifiers for text categorization using Dempster’s rule of combination. J Appl Artif Intell 2007;21:211–239.

PY - 2008/4

Y1 - 2008/4

N2 - Linear-time computational techniques based on the structure of an evidence space have beendeveloped for combining multiple pieces of evidence using Dempster’s rule (orthogonal sum),which is available on a number of contending hypotheses. They offer a means of making thecomputation-intensive calculations involved more efficient in certain circumstances. Unfortunately,they restrict the orthogonal sum of evidential functions to the dichotomous structure thatapplies only to elements and their complements. In this paper, we present a novel evidence structurein terms of a triplet and a set of algorithms for evidential reasoning. The merit of this structureis that it divides a set of evidence into three subsets, distinguishing the trivial evidential elementsfrom the important ones—focusing particularly on some elements of an evidence space. It avoidsthe deficits of the dichotomous structure in representing the preference of evidence and estimatingthe basic probability assignment of evidence. We have established a formalism for this structureand the general formulae for combining pieces of evidence in the form of the triplet, which havebeen theoretically and empirically justified. C

AB - Linear-time computational techniques based on the structure of an evidence space have beendeveloped for combining multiple pieces of evidence using Dempster’s rule (orthogonal sum),which is available on a number of contending hypotheses. They offer a means of making thecomputation-intensive calculations involved more efficient in certain circumstances. Unfortunately,they restrict the orthogonal sum of evidential functions to the dichotomous structure thatapplies only to elements and their complements. In this paper, we present a novel evidence structurein terms of a triplet and a set of algorithms for evidential reasoning. The merit of this structureis that it divides a set of evidence into three subsets, distinguishing the trivial evidential elementsfrom the important ones—focusing particularly on some elements of an evidence space. It avoidsthe deficits of the dichotomous structure in representing the preference of evidence and estimatingthe basic probability assignment of evidence. We have established a formalism for this structureand the general formulae for combining pieces of evidence in the form of the triplet, which havebeen theoretically and empirically justified. C

U2 - 10.1002/int.20278

DO - 10.1002/int.20278

M3 - Article

VL - 23

SP - 483

EP - 516

JO - International Journal of Intelligent Systems

T2 - International Journal of Intelligent Systems

JF - International Journal of Intelligent Systems

SN - 0884-8173

IS - 4

ER -