×

zbMATH — the first resource for mathematics

Inference in possibilistic network classifiers under uncertain observations. (English) Zbl 1252.68295
Summary: Possibilistic networks, which are compact representations of possibility distributions, are powerful tools for representing and reasoning with uncertain and incomplete information in the framework of possibility theory. They are like Bayesian networks but lie on possibility theory to deal with uncertainty, imprecision and incompleteness. While classification is a very useful task in many real world applications, possibilistic network-based classification issues are not well investigated in general and possibilistic-based classification inference with uncertain observations in particular.
In this paper, we address on one hand the theoretical foundations of inference in possibilistic classifiers under uncertain inputs and propose on the other hand a novel efficient algorithm for the inference in possibilistic network-based classification under uncertain observations. We start by studying and analyzing the counterpart of Jeffrey’s rule in the framework of possibility theory. After that, we address the validity of Markov-blanket criterion in the context of possibilistic networks used for classification with uncertain inputs purposes. Finally, we propose a novel algorithm suitable for possibilistic classifiers with uncertain observations without assuming any independence relations between observations. This algorithm guarantees the same results as if classification were performed using the possibilistic counterpart of Jeffrey’s rule. Classification is achieved in polynomial time if the target variable is binary. The basic idea of our algorithm is to only search for totally plausible class instances through a series of equivalent and polynomial transformations applied on the possibilistic classifier taking into account the uncertain observations.

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
62F15 Bayesian inference
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggarwal, C.C.: Managing And Mining Uncertain Data. Series: Advances in Database Systems, vol. 35. Springer, New York (2009) · Zbl 1185.68271
[2] Aggarwal, C.C., Yu, P.S.: A survey of uncertain data algorithms and applications. IEEE Trans. Knowl. Data Eng. 21(5), 609–623 (2009) · doi:10.1109/TKDE.2008.190
[3] Amor, N.B., Benferhat, S., Elouedi Z., Mellouli K.: Decision trees and qualitative possibilistic inference: application to the intrusion detection problem. In: 7th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2003, pp. 419–431 (2003)
[4] Axelsson S.: Intrusion Detection Systems: a Survey and Taxonomy. Technical Report 99–15, Chalmers University (2000)
[5] Ben-Amor, N., Benferhat, S., Mellouli, K.: A two-steps algorithm for min-based possibilistic causal networks. In: ECSQARU’01, pp. 266–277 (2001) · Zbl 1001.68532
[6] Benczúr, A., Bíró, I., Csalogány, K., Sarlós, T.: Web spam detection via commercial intent analysis. In: AIRWeb ’07: Proceedings of the 3rd International Workshop on Adversarial Information Retrieval on the Web, pp. 89–92, New York, NY (2007)
[7] Benferhat, S., Tabia, K.: An efficient algorithm for naive possibilistic classifiers with uncertain inputs. In: The 2nd International Conference on Scalable Uncertainty Management (SUM’08). Springer LNAI, Naples, Italy (2008) · Zbl 1192.68667
[8] Benferhat, S., Sedki, K.: Alert correlation based on a logical handling of administrator preferences and knowledge. In: International Conference on Security and Cryptography (SECRYPT’08), Porto, Portugal (2008) · Zbl 1192.68658
[9] Bi, J., Zhang T.: Support vector classification with input data uncertainty. In: Neural Information Processing Systems, NIPS (2004)
[10] Borgelt, C., Gebhardt, J.: A naive bayes style possibilistic classifier. In: Proceedings of the 7th European Congress on Intelligent Techniques and Soft Computing, Germany (1999)
[11] Borgelt, C., Kruse, R.: Graphical Models: Methods for Data Analysis and Mining. Wiley Inc., USA (2002) · Zbl 1017.62002
[12] Borgelt, C., Kruse, R.: Learning from imprecise data: possibilistic graphical models. Comput. Stat. Data Anal. 38(4), 449–463 (2002) · Zbl 1072.68627 · doi:10.1016/S0167-9473(01)00071-8
[13] Bouchon-Meunier, B., Coletti, G., Marsala, C.: Independence and possibilistic conditioning. Ann. Math. Artif. Intell. 35(1–4), 107–123 (2002) · Zbl 1004.60001 · doi:10.1023/A:1014579015954
[14] Chan, H., Darwiche, A.: On the revision of probabilistic beliefs using uncertain evidence. Artif. Intell. 163(1), 67–90 (2005) · Zbl 1132.68767 · doi:10.1016/j.artint.2004.09.005
[15] Chow, C.: On optimum recognition error and reject tradeoff. IEEE Trans. Inf. Theory 16(1):41–46 (1970) · Zbl 0185.47804 · doi:10.1109/TIT.1970.1054406
[16] Corani, G., Zaffalon, M.: Lazy naive credal classifier. In: KDD Workshop on Knowledge Discovery from Uncertain Data, pp. 30–37 (2009)
[17] Cowell, R.G., Dawid, P.A., Lauritzen, S.L., Spiegelhalter, D.J.: Probabilistic Networks and Expert Systems (Information Science and Statistics). Springer, New York (2003) · Zbl 0937.68121
[18] Cuppens, F., Miège, A.: Alert correlation in a cooperative intrusion detection framework. In: SP ’02: Proceedings of the 2002 IEEE Symposium on Security and Privacy, p. 202. IEEE Computer Society, Washington, DC (2002)
[19] Debar, H., Wespi, A.: Aggregation and correlation of intrusion-detection alerts. In: RAID ’00: Proceedings of the 4th International Symposium on Recent Advances in Intrusion Detection, pp. 85–103. Springer, London (2001) · Zbl 1052.68837
[20] Denoeux, T., Zouhal, L.M.: Handling possibilistic labels in pattern classification using evidential reasoning. Fuzzy Sets Syst 122(3), 409–424 (2001) · Zbl 1063.68635 · doi:10.1016/S0165-0114(00)00086-5
[21] Dubois, D., Prade, H.: Possibility Theory. Plenum Press, New York (1988)
[22] Dubois, D., Prade, H.: Possibility Theory: An Approach to Computerized Processing of Uncertainty. Plenum Press, New York (1988) · Zbl 0703.68004
[23] Dubois, D., Prade, H.: A synthetic view of belief revision with uncertain inputs in the framework of possibility theory. Int. J. Approx. Reason. 17(2–3), 295–324 (1997) · Zbl 0935.03026 · doi:10.1016/S0888-613X(97)00019-4
[24] Dubois, D.: Possibility theory and statistical reasoning. Comput. Statist. Data Anal. 51, 47–69 (2006) · Zbl 1157.62309 · doi:10.1016/j.csda.2006.04.015
[25] Dubois, D., Prade, H., Philippe, S.: A definition of subjective possibility. Int. J. Approx. Reason. 48, 352–364 (2008) · Zbl 1184.68507 · doi:10.1016/j.ijar.2007.01.005
[26] Fonck, P.: A comparative study of possibilistic conditional independence and lack of interaction. Int. J. Approx. Reason. 16(2), 149–171 (1997) · Zbl 0939.68115 · doi:10.1016/S0888-613X(96)00095-3
[27] Haouari, B.A., Elouedi, Z., Ben-Amor, N., Mellouli, K.: Naive possibilistic network classifier. In: Proceedings of The 13th Congress of International Association for Fuzzy-Set Management and Economy, SIGEF (2006) · Zbl 1192.68519
[28] Hisdal, E.: Conditional possibilities independence and non interaction. Fuzzy Sets Syst. 1(4), 283–297 (1978) · Zbl 0393.94050
[29] Howard, R.A., Matheson, J.E.: Influence diagrams. In: Readings on the Principles and Applications of Decision Analysis, pp. 721–762. Strategic Decisions Group (1984)
[30] Huete, J.F., De Campos, L.M., Moral, S.: Possibilistic independence. In: Proceedings of EUFIT 95, vol. 1, pp. 69–73 (1995)
[31] Hüllermeier, E.: Possibilistic induction in decision-tree learning. In: ECML ’02: Proceedings of the 13th European Conference on Machine Learning, pp. 173–184. Springer, London (2002) · Zbl 1014.68520
[32] Jeffrey, R.C.: The Logic of Decision. McGraw Hill, NY (1965) · Zbl 0139.22501
[33] Jensen, F.V.: An Introduction to Bayesian Networks. UCL Press, London (1996)
[34] Kuncheva, L.I.: Combining Pattern Classifiers: Methods and Algorithms. Wiley-Interscience (2004) · Zbl 1066.68114
[35] Maskell, S.: A bayesian approach to fusing uncertain, imprecise and conflicting information. Inf. Fusion 9(2):259–277 (2008) · Zbl 05423112 · doi:10.1016/j.inffus.2007.02.003
[36] Masson, M.-H., Den, T.: Inferring a possibility distribution from empirical data. Fuzzy Sets Syst. 157(3):319–340 (2006) · Zbl 1083.68125 · doi:10.1016/j.fss.2005.07.007
[37] Mittal, A.: Bayesian Network Technologies: Applications and Graphical Models. IGI Publishing, USA (2007)
[38] Neapolitan, R.E.: Learning Bayesian Networks. Prentice Hall (2003)
[39] Ning, P., Cui, Y., Reeves, D.S.: Constructing attack scenarios through correlation of intrusion alerts. In: CCS ’02: Proceedings of the 9th ACM Conference on Computer and Communications Security, pp. 245–254. ACM, New York (2002)
[40] Patcha, A., Park, J.: An overview of anomaly detection techniques: existing solutions and latest technological trends. Comput. Netw. 51(12), 3448–3470 (2007) · doi:10.1016/j.comnet.2007.02.001
[41] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco, CA (1988) · Zbl 0746.68089
[42] Sarma, A.D., Nabar, S.U., Widom, J.: Representing uncertain data: uniqueness, equivalence, minimization, and approximation. Technical Report 2005–38, Stanford InfoLab (2005)
[43] Scotney, B., McClean, S.: Database aggregation of imprecise and uncertain evidence. Inf. Sci. 155(3–4), 245–263 (2003) (Knowledge Discovery from Distributed Information Sources) · Zbl 02015439 · doi:10.1016/S0020-0255(03)00172-5
[44] Spohn, W.: Ordinal conditional functions: a dynamic theory of epistemic states. In: Causation in Decision, Belief Change, and Statistics, vol. II, pp. 105–134. Kluwer Academic Publishers (1988)
[45] Tjhai, G.C., Papadaki, M., Furnell, S., Clarke, N.L.: Investigating the problem of ids false alarms: an experimental study using snort. In: 23rd International Information Security Conference SEC 2008, pp. 253–267 (2008)
[46] Troffaes, M.C.M.: Decision making under uncertainty using imprecise probabilities. Int. J. Approx. Reason. 45(1), 17–29 (2007) · Zbl 1119.91028 · doi:10.1016/j.ijar.2006.06.001
[47] Valtorta, M., Kim, Y.-G., Vomlel, J.: Soft evidential update for probabilistic multiagent systems. Int. J. Approx. Reason. 29(1), 71–106 (2002) · Zbl 1015.68208 · doi:10.1016/S0888-613X(01)00056-1
[48] van Rijsbergen, C.J.: Getting Into Information Retrieval. Lectures on Information Retrieval, pp. 1–20 (2001)
[49] Vomlel, J.: Probabilistic reasoning with uncertain evidence. Neural Netw. World, Int. J. Neural and Mass-Parallel Comput. Inf. Sys. 14(5), 453–456 (2004)
[50] Zadeh, L.A.: Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets Syst. 1(3), 3–28 (1978) · Zbl 0377.04002
[51] Zadrozny, B., Elkan, C.: Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In: ICML ’01: Proceedings of the 18th International Conference on Machine Learning, pp. 609–616. Morgan Kaufmann Publishers Inc., San Francisco, CA (2001)
[52] Zadrozny, B., Pappa, G.L., Meira, W., Jr., Gonçalves, M. A., Rocha, L., Salles, T.: Exploiting contexts to deal with uncertainty in classification. In: U ’09: Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data, pp. 19–22. ACM, New York (2009)
[53] Zadrozny, S., Nowacka, K.: Fuzzy information retrieval model revisited. Fuzzy Sets and Systems 160(15), 2173–2191 (2009). Special Issue: The Application of Fuzzy Logic and Soft Computing in Information Management · Zbl 1187.68201 · doi:10.1016/j.fss.2009.02.012
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.