Quantitative possibility theory: logical- and graphical-based representations.

*(English)*Zbl 1400.68219Summary: In the framework of quantitative possibility theory, two representation modes were developed: logical-based representation in terms of quantitative possibilistic bases and graphical-based representation in terms of product-based possibilistic networks. This paper deals with logical and graphical representations of uncertain information using a quantitative possibility theory framework. We first provide a deep analysis of the relationships between these two forms of representational frameworks. Then, in the logical setting, we develop syntactic relations between penalty logic and quantitative possibilistic logic. These translations are useful for different applications and are interesting for taking advantage of each format at the inferential level. We also provide an algorithm for reasoning with quantitative possibilistic logic. The algorithm takes inspiration from the syntactic relations between quantitative possibilistic logic bases and penalty logic. Finally, we provide experimental results that compare the uncertainty propagation algorithms developed for the possibilistic product-based networks and the inference algorithms based on WMAXSAT developed in this paper.

##### MSC:

68T37 | Reasoning under uncertainty in the context of artificial intelligence |

68T30 | Knowledge representation |

##### Keywords:

quantitative possibilistic bases; product-based possibilistic networks; penalty logic; uncertainty propagation algorithm
PDF
BibTeX
XML
Cite

\textit{H. F. Khellaf-Haned} and \textit{S. Benferhat}, J. Appl. Non-Class. Log. 24, No. 3, 236--261 (2014; Zbl 1400.68219)

Full Text:
DOI

##### References:

[1] | Ayachi, R., Ben Amor, N., & Benferhat, S. (2011). Compiling min-based possibilistic causal networks: A mutilated-based approach. In W. Liu (Ed.), Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Belfast, UK, June 29-July 1, 2011. Proceedings (pp. 700-712). Berlin: Springer. · Zbl 1341.68236 |

[2] | Ayachi, R., Ben Amor, N., & Benferhat, S. (2012). Inference using compiled product-based possibilistic networks. In S. Greco, et al. (Eds.), Advances in Computational Intelligence - 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU 2012, Catania, Italy, July 9-13, 2012, proceedings, part III (pp. 470-480). Berlin: Springer. · Zbl 1252.68294 |

[3] | Baioletti, M., Coletti, G., Petturiti, D., & Vantaggi, B. (2011). Inferential models and relevant algorithms in a possibilistic framework. International Journal of Approximate Reasoning,52, 580-598. · Zbl 1214.68393 |

[4] | Ben Amor, N., Benferhat, S., Dubois, D., Geffner, H., & Prade, H. (2000). Independence in qualitative uncertainty frameworks. In A. G. Cohn, F. Giunchiglia, & B. Selman (Eds.), KR 2000, Principles of Knowledge Representation and Reasoning: Proceedings of the Seventh International Conference, Breckenridge, Colorado, USA, April 11-15, 2000 (pp. 235-246). San Francisco, CA: Morgan Kaufmann. |

[5] | Ben Amor, N., Benferhat, S., Dubois, D., Mellouli, K., & Prade, H. (2002). A theoretical framework for possibilistic independence in a weakly ordered setting. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems,10, 117-155. · Zbl 1084.68126 |

[6] | Ben Amor, N., Benferhat, S., & Mellouli, K. (2003). Anytime propagation algorithm for min-based possibilistic graphs. Soft Computing,8, 150-161. · Zbl 1054.68674 |

[7] | Benferhat, S., Dubois, D., & Prade, H. (1997a). From semantic to syntactic approaches to information combination in possibilistic logic. In B. Bouchon-Meunier (Ed.), Aggregation and fusion of imperfect information (pp. 141-151). Heidelberg: Physica. · Zbl 0898.68079 |

[8] | Benferhat, S., Dubois, D., & Prade, H. (1997b). Nonmonotonic reasoning, conditional objects and possibility theory. Artificial Intelligence,92, 259-276. · Zbl 1017.68539 |

[9] | Benferhat, S., Dubois, D., & Prade, H. (1998). Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study. Part 2: The prioritized case. In E. Orlowska. (Ed.), Logic at work: Essays dedicated to the memory of Helena Rasiowa (pp. 473-511). Heidelberg: Physica. · Zbl 0930.68149 |

[10] | Benferhat, S., Dubois, D., Garcia, L., & Prade, H. (2002). On the transformation between possibilistic logic bases and possibilistic causal networks. International Journal of Approximate Reasoning,29, 135-173. · Zbl 1015.68204 |

[11] | Benferhat, S., Khellaf-Haned, F., & Mokhtari, A. (2004). Product-based causal networks and quantitative possibilistic bases. In V. Barr, & Z. Markov (Eds.), Proceedings of the Seventeenth International Florida Artificial Intelligence Research Society Conference, Miami Beach, Florida, USA, May 17-19, 2004 (pp. 832-837). Menlo Park, CA: AAAI Press. · Zbl 1082.03031 |

[12] | Benferhat, S., Khellaf-Haned, F., & Mokhtari, A. (2005). Product-based causal networks and quantitative possibilistic bases. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems,13, 469-493. · Zbl 1082.03031 |

[13] | Benferhat, S. & Tabia, K. (2010). Belief revision of product-based causal possibilistic networks. In A. Farzindar & V. Keselj. (Eds.), Advances in Artificial Intelligence, 23rd Canadian Conference on Artificial Intelligence, Canadian AI 2010, Ottawa, Canada, May 31-June 2, 2010. Proceedings (pp. 244-255). Berlin: Springer. · Zbl 1211.68435 |

[14] | Borchers, B., & Furman, J. (1999). A two-phase exact algorithm for MAXSAT and Weighted MAXSAT problems. Journal of Combinatorial Optimisation,2, 299-306. · Zbl 0954.90026 |

[15] | Borgelt, C., Gebhardt, J., & Kruse, R. (2002). Possibilistic graphical models. In G. Della Riccia, R. Kruse, & H. J. Lenz. (Eds.), omputational intelligence in data mining (pp. 51-68). Vienna: Springer. · Zbl 0979.68106 |

[16] | Boutilier, C., Bacchus, F., & Brafman, R. I. (2001). UCP-networks: A directed graphical representation of conditional utilities. In J. S. Breese, & D. Koller (Eds.), UAI ’01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, University of Washington, Seattle, Washington, USA, August 2-5, 2001 (pp. 56-64). San Francisco, CA: Morgan Kaufmann. |

[17] | Cayrol, C. & Lagasquie-Schiex, M. C. (1994). On the complexity of non-monotonic entailment in syntax-based approaches. Paper presented at the Eleventh European Conference on Artificial Intelligence, Amsterdam, The Netherlands, 8-12 August 1994. |

[18] | Darwiche, A. (2009). Modeling and reasoning with Bayesian networks. Cambridge: Cambridge University Press (ECAI) workshop on Algorithms, Complexity and Commonsense Reasoning. · Zbl 1231.68003 |

[19] | De Campos, L. M., & Huete, J. F. (1998). Independence concepts in possibility theory. Fuzzy Sets and Systems,103, 127-152. · Zbl 0951.68150 |

[20] | Dubois, D., & Prade, H. (1990). The logical view of conditioning and its application to possibility and evidence theories. International Journal of Approximate Reasoning,4, 23-46. · Zbl 0696.03006 |

[21] | Dubois, D., Lang, J., & Prade, H. (1994). Possibilistic logic. In D. M. Gabbay, C. J. Hogger, & J. A. Robinson (Eds.), Handbook of logic in artificial intelligence and logic programming, (Vol. 3, pp. 439-513). Oxford: Oxford University Press. |

[22] | Dupin De Saint-Cyr, F., Lang, J., & Schiex, T. (1994). Penalty logic and its link with Dempster-Shafer theory. In R. López de Mántaras & D. Poole (Eds.), UAI ’94: Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence, Seattle, Washington, USA, July 29-31, 1994 (pp. 204-211). San Francisco, CA: Morgan Kaufmann. |

[23] | Fonck, P. (1992). Propagating uncertainty in a directed acyclic graph. Paper presented at the 4th International Conference on Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU ’92), Palma de Mallorca, Spain. |

[24] | Fonck, P. (1994). Conditional independence in possibility theory. In R. López de Mántaras, & D. Poole (Eds.), UAI ’94: Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence, Seattle, Washington, USA, July 29-31, 1994 (pp. 221-226). San Francisco, CA: Morgan Kaufmann. |

[25] | Gebhardt, J., & Kruse, R. (1997a). Background and perspectives of possibilistic graphical models. In D. M. Gabbay, R. Kruse, A. Nonnengart, & H. J. Ohlbach (Eds.), Qualitative and Quantitative Practical Reasoning, First International Joint Conference on Qualitative and Quantitative Practical Reasoning ECSQARU-FAPR’97, Bad Honnef, Germany, June 9-12, 1997, proceedings (pp. 108-121). Berlin: Springer. |

[26] | Gebhardt, J., & Kruse, R. (1997b). POSSINFER - a software tool for possibilistic inference. In D. Dubois, H. Prade, & R. Yager (Eds.), Fuzzy set methods in information engineering: A guided tour of applications (pp. 407-418). Chichester: John Wiley & Sons. |

[27] | Hisdal, E. (1978). Conditional possibilities independence and noninteraction. Fuzzy Sets and Systems,1, 283-297. · Zbl 0393.94050 |

[28] | Jensen, V. F. (1996). An introduction to Bayesian networks. London: UCL Press. |

[29] | Jirousek, R., & Shenoy, P. P. (2012). Conditioning in decomposable compositional models in valuation-based systems. In S. Greco, et al. (Eds.), Advances in Computational Intelligence - 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU 2012, Catania, Italy, July 9-13, 2012, proceedings, part III (pp. 676-685). Berlin: Springer. · Zbl 1252.68310 |

[30] | Lang, J. (2000). Possibilistic logic: Complexity and algorithms. In D. M. Gabbay, & P. Smets (Eds.), Handbook of defeasible reasoning and uncertainty management systems, (Vol. 5, pp. 179-220). Dordrecht: Kluwer Academic. · Zbl 0984.03022 |

[31] | Lehmann, D. (1995). Belief revision revisited. In C. R. Perrault, & C. S. Mellish (Eds.), Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal, Québec, Canada, August 20-25, 1995 (pp. 1534-1540). San Francisco, CA: Morgan Kaufmann. |

[32] | Pearl, J. (1988). Probabilistic reasoning in intelligent systems: Networks of plausible inference. San Francisco, CA: Morgan Kaufmann. · Zbl 0746.68089 |

[33] | Peot, M. A., & Shachter, R. D. (1991). Fusion and propagation with multiple observations in belief networks. Artificial Intelligence,48, 299-318. · Zbl 0738.68074 |

[34] | Pinkas, G. (1991). Propositional nonmonotonic reasoning and inconsistency in symmetric neural networks. In J. Mylopoulos, & R. Reiter (Eds.), Proceedings of the 12th International Joint Conference on Artificial Intelligence, Sydney, Australia, August 24-30, 1991 (pp. 525-531). San Francisco, CA: Morgan Kaufmann. · Zbl 0742.68070 |

[35] | Shenoy, P. P. (1989). A valuation-based language for expert systems. International Journal of Approximate Reasoning,3, 383-411. |

[36] | Shenoy, P. P. (1990). Valuations-based systems for propositional logic. Methodologies for Intelligent Systems,5, 305-312. |

[37] | Shenoy, P. P. (1994). Consistency in valuation-based systems. INFORMS Journal on Computing,6, 281-291. · Zbl 0822.90089 |

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.