×

Representing uncertainty on set-valued variables using belief functions. (English) Zbl 1209.68542

Summary: A formalism is proposed for representing uncertain information on set-valued variables using the formalism of belief functions. A set-valued variable \(X\) on a domain \(\varOmega \) is a variable taking zero, one or several values in \(\varOmega \). While defining mass functions on the frame \(2^{2^\varOmega}\) is usually not feasible because of the double-exponential complexity involved, we propose an approach based on a definition of a restricted family of subsets of \(2^\varOmega \) that is closed under intersection and has a lattice structure. Using recent results about belief functions on lattices, we show that most notions from Dempster-Shafer theory can be transposed to that particular lattice, making it possible to express rich knowledge about \(X\) with only limited additional complexity as compared to the single-valued case. An application to multi-label classification (in which each learning instance can belong to several classes simultaneously) is demonstrated.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
68T30 Knowledge representation

Software:

ML-KNN
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Aguzzoli, S.; Gerla, B.; Marra, V., De Finetti’s no-Dutch-book criterion for Gödel logic, Studia Logica, 90, 1 (2008) · Zbl 1165.03008
[2] Cignoli, R. L.O.; D’Ottaviano, I. M.L.; Mundici, D., Algebraic Foundations of Many-Valued Reasoning, Trends in Logic - Studia Logica Library, vol. 7 (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0937.06009
[3] Cobb, B. R.; Shenoy, P. P., On the plausibility transformation method for translating belief function models to probability models, International Journal of Approximate Reasoning, 41, 3, 314-330 (2006) · Zbl 1093.68112
[4] Denœux, T., A \(k\)-nearest neighbor classification rule based on Dempster-Shafer theory, IEEE Transactions on Systems, Man and Cybernetics, 25, 05, 804-813 (1995)
[5] Denœux, T., Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence, Artificial Intelligence, 172, 234-264 (2008) · Zbl 1182.68298
[6] Denœux, T.; Smets, P., Classification using belief functions: the relationship between the case-based and model-based approaches, IEEE Transactions on Systems, Man and Cybernetics B, 36, 6, 1395-1406 (2006)
[7] Denœux, T.; Zouhal, L. M., Handling possibilistic labels in pattern classification using evidential reasoning, Fuzzy Sets and Systems, 122, 3, 47-62 (2001) · Zbl 1063.68635
[8] Dubois, D.; Prade, H., A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets, International Journal of General Systems, 12, 3, 193-226 (1986)
[9] Dubois, D.; Prade, H., On incomplete conjunctive information, Computers and Mathematics with Applications, 15, 10, 797-810 (1988) · Zbl 0709.94588
[10] Dubois, D.; Prade, H., Representation and combination of uncertainty with belief functions and possibility measures, Computational Intelligence, 4, 244-264 (1988)
[11] Elisseeff, A.; Weston, J., A kernel method for multi-labelled classification, (Dietterich, T. G.; Becker, S.; Ghahramani, Z., Advances in Neural Information Processing Systems, vol. 14 (2002), MIT Press), 681-687
[12] Fürnkranz, J.; Hüllermeier, E.; Mencia, E. L.; Brinker, K., Multilabel classification via calibrated label ranking, Machine Learning, 73, 2, 133-153 (2008) · Zbl 1470.68108
[14] Grabisch, M., Belief functions on lattices, International Journal of Intelligent Systems, 24, 76-95 (2009) · Zbl 1157.68063
[15] Grabisch, M.; Labreuche, C., Bi-capacities - I: definition, Möbius transform and interaction, Fuzzy Sets and Systems, 151, 211-236 (2005) · Zbl 1106.91023
[16] Kroupa, T., Conditional probability on MV-algebras, Fuzzy Sets and Systems, 149, 2, 369-381 (2005) · Zbl 1061.60004
[17] Kroupa, T., Representation and extension of states on MV-algebras, Archive for Mathematical Logic, 45, 4, 381-392 (2006) · Zbl 1101.06008
[19] Labreuche, C.; Grabisch, M., Modeling positive and negative pieces of evidence in uncertainty, (Nielsen, T. D.; Zhang, N. L., Symbolic and Quantitative Approaches to Reasoning with Uncertainty (Proceedings of ECSQARU ’03). Symbolic and Quantitative Approaches to Reasoning with Uncertainty (Proceedings of ECSQARU ’03), Aalborg, Denmark (2003), Springer), 279-290 · Zbl 1274.68536
[20] Matheron, G., Random Sets and Integral Geometry (1975), Wiley: Wiley New York · Zbl 0321.60009
[21] Monjardet, B., The presence of lattice theory in discrete problems of mathematical social sciences. Why, Mathematical Social Sciences, 46, 2, 103-144 (2003) · Zbl 1054.91062
[22] Mundici, D., Averaging the truth-value in Lukasiewicz logic, Studia Logica, 55, 1, 113-127 (1995) · Zbl 0836.03016
[23] Nguyen, H., An Introduction to Random Sets (2006), Chapman and Hall/CRC Press: Chapman and Hall/CRC Press Boca Raton, Florida · Zbl 1100.60001
[24] Nguyen, H. T., On random sets and belief functions, Journal of Mathematical Analysis and Applications, 65, 531-542 (1978) · Zbl 0409.60016
[26] Shafer, G., A Mathematical Theory of Evidence (1976), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0359.62002
[27] Smets, P., The Transferable Belief Model and random sets, International Journal of Intelligent Systems, 7, 37-46 (1992) · Zbl 0768.68200
[28] Smets, P., Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem, International Journal of Approximate Reasoning, 9, 1-35 (1993) · Zbl 0796.68177
[29] Smets, P., The canonical decomposition of a weighted belief, (Int. Joint Conf. on Artificial Intelligence (1995), Morgan Kaufman: Morgan Kaufman San Mateo, CA), 1896-1901
[30] Smets, P.; Kennes, R., The transferable belief model, Artificial Intelligence, 66, 191-243 (1994) · Zbl 0807.68087
[32] Yager, R. R., On different classes of linguistic variables defined via fuzzy subsets, Kybernetes, 13, 103-110 (1984) · Zbl 0544.03008
[33] Yager, R. R., Set-based representations of conjunctive and disjunctive knowledge, Information Sciences, 41, 1-22 (1987) · Zbl 0626.68073
[34] Yager, R. R., Reasoning with conjunctive knowledge, Fuzzy Sets and Systems, 28, 69-83 (1988) · Zbl 0655.68122
[35] Yager, R. R., Veristic variables, IEEE Transactions on Systems, Man and Cybernetics B, 30, 1, 71-84 (2000)
[37] Younes, Z.; Abdallah, F.; Denœux, T., An evidence-theoretic k-nearest neighbor rule for multi-label classification, (Proceedings of the 3rd International Conference on Scalable Uncertainty Management (SUM 2009). Proceedings of the 3rd International Conference on Scalable Uncertainty Management (SUM 2009), Washington, DC, USA. Proceedings of the 3rd International Conference on Scalable Uncertainty Management (SUM 2009). Proceedings of the 3rd International Conference on Scalable Uncertainty Management (SUM 2009), Washington, DC, USA, LNAI, vol. 5785 (2009), Springer-Verlag), 297-308
[38] Zhang, M.-L.; Zhou, Z.-H., ML-KNN: a lazy learning approach to multi-label learning, Pattern Recognition, 40, 7, 2038-2048 (2007) · Zbl 1111.68629
[39] Zouhal, L. M.; Denœux, T., An evidence-theoretic \(k\)-NN rule with parameter optimization, IEEE Transactions on Systems, Man and Cybernetics C, 28, 2, 263-271 (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.