Skip to main content
SpringerLink
Log in

Practical Handling of Exception-Tainted Rules and Independence Information in Possibilistic Logic

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

This paper provides a survey of possibilistic logic as a simple and efficient tool for handling nonmonotonic reasoning, with some emphasis on algorithmic issues. In our previous works, two well-known nonmonotonic systems have been encoded in the possibility theory framework: the preferential inference based on System P, and the rational closure inference proposed by Lehmann and Magidor which relies on System P augmented with a rational monotony postulate. System P is known to provide reasonable but very cautious conclusions, and in particular, preferential inference is blocked by the presence of “irrelevant” properties. When using Lehmann's rational closure, the inference machinery, which is then more productive, may still remain too cautious, or on the contrary, provide counter -intuitive conclusions. The paper proposes an approach to overcome the cautiousness of System P and the problems encountered by the rational closure inference. This approach takes advantage of (contextual) independence assumptions of the form: the fact that γ is true (or is false) does not affect the validity of the rule “normally if α then β”. The modelling of such independence assumptions is discussed in the possibilistic framework. Moreover, we show that when a counter-intuitive conclusion of a set of defaults can be inferred, it is always possible to repair the set of defaults by adding suitable information so as to produce the desired conclusions and block unsuitable ones.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. L. Morgenstern, “Inheritance comes of age: Applying nonmonotonic techniques to problems in industry,” in Proc. of the Fiftheenth Int. Joint Conf. on Artificial Intelligence (IJCAI-97), Nagoya, Japan, 1997, pp. 1613- 1613.

  2. L. Morgenstern and M. Singh, “An expert system using nonmonotonic techniques for benefits inquiry in the insurance industry,” in Proc. of the Fifteenth Int. Joint Conf. on Artificial Intelligence (IJCAI-97), Nagoya, Japan, 1997, pp. 655- 661.

  3. D. Dubois, J. Lang, and H. Prade, “Possibilistic logic,” in Handbook of Logic in Artificial Intelligence and Logic Programming, edited by D.M. Gabbay, C.J. Hogger, J.A. Robinson, and D. Nute, Oxford University Press, vol. 3, pp. 439- 513, 1994.

  4. D. Dubois, J. Lang, and H. Prade, “Automated reasoning using possibilistic logic: Semantics, belief revision and variable certainty weights,” IEEE Trans. on Knowledge and Data Engineering, vol. 6, no.1, pp. 64- 71, 1994.

    Google Scholar 

  5. F.F. Monai and T. Chehire, “Possibilistic assumption based truth maintenance system, validation in a data fusion application,” in Proc. of the 8th Conf. on Uncertainty in Artificial Intelligence, edited by D. Dubois et al., 1992, pp. 83- 91.

  6. S. Benferhat, T. Cherire, and F.F. Monai, “Possibilistic ATMS in a data fusion problem,” in Fuzzy Information Engineering: A Guided Tour of Applications, edited by D. Dubois, H. Prade, and R.R. Yager, John Wily & sons, 1997.

  7. S. Benferhat, D. Dubois, and H. Prade, “Representing default rules in possibilistic logic,” in Proc. of the 3rd Int. Conf. on Principles of Knowledge Representation and Reasoning (KR'92), Cambridge, MA, October 1992, pp. 673- 684.

  8. D. Dubois and H. Prade, “Conditional objects, possibility theory and default rules,” in Conditionals: From Philosophy to Computer Sciences, edited by G. Crocco, L. Fariñas del Cerro, and A. Herzig, Oxford University Press, pp. 301- 336, 1995.

  9. S. Kraus, D. Lehmann, and M. Magidor, “Nonmonotonic reasoning, preferential models and cumulative logics,” Artificial Intelligence, vol. 44, pp. 167- 207, 1990.

    Google Scholar 

  10. D. Lehmann and M. Magidor, “What does a conditional knowledge base entail?” Artficial Intelligence, vol. 55, pp. 1- 60, 1992.

    Google Scholar 

  11. S. Benferhat, D. Dubois, and H. Prade, “Beyond counterexamples to nonmonotonic formalisms: A possibility-theoretic analysis,” in Proc. of the 12th Europ. Conf. on Artificial Intelligence (ECAI'96), edited by W. Wahlster, Budapest, Hungary, Wiley: New York, August 1996, pp. 652- 656.

    Google Scholar 

  12. S. Benferhat, D. Dubois, and H. Prade, “Coping with the limitations of rational inference in the framework of possibility theory,” in Proc. of the 12th Conf. on Uncertainty in Artificial Intelligence, edited by E. Horvitz and F. Jensen, Portland, Oregon, Morgan Kaufmann: San Mateo, CA, August 1996, pp. 90- 97.

    Google Scholar 

  13. L.A. Zadeh, “Fuzzy sets as a basis for a theory of possibility,” Fuzzy Sets and Systems, vol. 1, pp. 3- 28, 1978.

    Google Scholar 

  14. D. Dubois and H. Prade, (with the collaboration of H. Farreny, R. Martin-Clouaire, C. Testemale), Possibility Theory—An Approach to Computerized Processing of Uncertainty, Plenum Press: New York, 1988.

    Google Scholar 

  15. P. Gärdenfors, Knowledge in Flux—Modeling the Dynamic of Epistemic States, MIT Press: Cambridge, MA, 1988.

    Google Scholar 

  16. G.L.S. Shackle, Decision, Order and Time in Human Affairs, Cambridge University Press: Cambridge, UK, 1961.

    Google Scholar 

  17. L.J. Cohen, The Probable and the Provable, Clarendon Press: Oxford, UK, 1977.

    Google Scholar 

  18. N. Rescher, Plausible Reasoning: An Introduction to the Theory and Practice of Plausibilistic Inference, Van Gorcum, Amsterdam, 1976.

    Google Scholar 

  19. W. Spohn, “Ordinal conditional functions: A dynamic theory of epistemic states,” in Causation in Decision, Belief Change, and Statistics, edited by W.L. Harper and B. Skyrms, Kluwer Academic Publ.: Dordrecht, pp. 105- 134, 1988.

    Google Scholar 

  20. D. Dubois, “Belief structures, possibility theory, decomposable confidence measures on finite sets,” Computer and Artificial Intelligence, vol. 5, no.5, pp. 403- 417, 1986.

    Google Scholar 

  21. D. Dubois and H. Prade, “Epistemic entrenchment and possibilistic logic,” Artificial Intelligence, vol. 50, pp. 223- 239, 1991.

    Google Scholar 

  22. R.R. Yager, “On the specificity of a possibility distribution,” Fuzzy Sets and Systems, vol. 50, pp. 279- 292, 1992.

    Google Scholar 

  23. Y. Shoham, “Reasoning about Change—Time and Causation from the Standpoint of Artificial Intelligence,” MIT Press: Cambridge, MA, 1988.

  24. D. Dubois and H. Prade, “Possibilistic logic, preferential models, non-monotonicity and related issues,” in Proc. of the Int. Joint Conf. on Artificial Intelligence (IJCAI'91), Sydney, August 1991, pp. 419- 424.

  25. S. Benferhat, D. Dubois, and H. Prade, “Nonmonotonic reasoning, conditional objects and possibility theory,” Artificial Intelligence, vol. 92, pp. 259- 276, 1997.

    Google Scholar 

  26. E. Hisdal, “Conditional possibilities independence and noninteraction,” Fuzzy Sets and Systems, vol. 1, pp. 283- 297, 1978.

    Google Scholar 

  27. D. Dubois and H. Prade, “Necessity measures and the resolution principle,” IEEE Trans. Systems, Man and Cybernetics, vol. 17, pp. 474- 478, 1987.

    Google Scholar 

  28. D. Dubois, J. Lang, and H. Prade, “Theorem proving under uncertainty—A possibility theory-based approah,” in Proc. of the Tenth Int. Joint Conf. on Artificial Intelligence (IJCAI-87), 1987, pp. 984- 986.

  29. J. Lang, “Logique possibiliste: Aspects formels, d´eduction automatique, et applications,” Ph.D. Thesis, Universite P. Sabatier, Toulouse, France, January 1991.

    Google Scholar 

  30. E. Sandewall, “The range of applicability of nonmonotonic logics for the inerrtia problem,” in Proc. of Int. Joint Conf. on Arti-ficial Intelligence (IJCAI-93), 1993, pp. 738- 743.

  31. M.O. Cordier and P. Siegel, “Prioritized transitions for updates,” in Proc. of the AI'93 Workshop on Belief Revision, Melbourn, 1993.

  32. D. Dubois and H. Prade, “Combining hypothetical reasoning and plausible inference in possibilistic logic,” Multiple Valued Logic, vol. 1, pp. 219- 239, 1996.

    Google Scholar 

  33. S. Benferhat, “Handling hard rules and default rules in possibilistic logic,” in Advances in Intelligent Computing—IPMU'94 (Selected Papers of the Inter. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU'94), Paris, France, July 1994) edited by B. Bouchon-Meunier, R.R. Yager, and L.A. Zadeh, Lecture Notes in Computer Science, Springer Verlag: Berlin, vol. 945, 1995, pp. 302- 310.

    Google Scholar 

  34. D.M. Gabbay, “Theoretical foundations for non-monotonic reasoning in expert systems,” in Logics and Models of Concurrent Systems, edited by K.R. Apt, Springer-Verlag, pp. 439- 457, 1985.

  35. D. Makinson, “General theory of cumulative inference,” in Non-Monotonic Reasoning, edited by M. Reinfrank, J. De Kleer, M.L. Ginsberg, and E. Sandewall, LNAI, Springer Verlag: Berlin, vol. 346, pp. 1- 18, 1989.

    Google Scholar 

  36. P. Gärdenfors and D. Makinson, “Nonmonotonic inference based on expectations,” Artificial Intelligence, vol. 65, pp. 197- 245, 1994.

    Google Scholar 

  37. E.W. Adams, The Logic of Conditionals, Reidel: Dordrecht, 1975.

  38. J. Pearl, “System Z: A natural ordering of defaults with tractable applications to default reasoning,” in Proc. of the 3rd Conf. on Theoretical Aspects of Reasoning about Knowledge (TARK'90), San Mateo, CA, 1990, pp. 121- 135.

  39. M. Goldszmidt and J. Pearl, “On the relation between rational closure and System Z,” in Proc. of the 3rd Int. Workshop on Nonmonotonic Reasoning, South Lake Tahoe, 1990, pp. 130- 140.

  40. D. Dubois, L. Fariñas del Cerro, A. Herzig, and H. Prade, “Qualitative relevance and independence: A roadmap,” in Proc. of the Fiftheenth Int. Joint Conf. on Artificial Intelligence (IJCAI-97), Nagoya, Japan, 1997, pp. 62- 67.

  41. S. Benferhat, D. Dubois, and H. Prade, “Expressing independence in a possibilistic framework and its application to default reasoning,” in Proc. of the 11th Europ. Conf. on Artificial Intelligence (ECAI'94), Amsterdam, August 1994, pp. 150- 154.

  42. D. Dubois, L. Fariñas del Cerro, A. Herzig, and H. Prade, “An ordinal view of independence with application to plausible reasoning,” in Proc. of the 10th Conf. on Uncertainty in Artificial Intelligence, edited by R. Lopez de Mantaras and D. Poole, Seattle, WA, July 1994, pp. 195- 203.

  43. D. Dubois, J. Lang, and H. Prade, “A possibilistic assumptions-based truth maintenance systems with uncertain justifications and its application to belief revision,” in Truth Maintenance Systems—Proc. ECAI-90 Workshop, Stockholm, Sweeden, August 1990, edited by J.P. Martins and M. Reinfrank, Lecture Notes in Artificial Intelligence, vol. 55, pp. 87- 106.

    Google Scholar 

  44. S. Nahmias, “Fuzzy variables,” Fuzzy Sets and Systems, pp. 97- 110, 1978.

Download references

Author information

Authors and Affiliations

  1. Institut de Recherche en Informatique de Toulouse (I.R.I.T.), Université Paul Sabatier, C.N.R.S., 118 route de Narbonne, 31062 Toulouse Cedex 4, France

    Salem Benferhat, Didier Dubois & Henri Prade

Authors
  1. Salem Benferhat
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Didier Dubois
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Henri Prade
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Benferhat, S., Dubois, D. & Prade, H. Practical Handling of Exception-Tainted Rules and Independence Information in Possibilistic Logic. Applied Intelligence 9, 101–127 (1998). https://doi.org/10.1023/A:1008259801924

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008259801924

Search

Navigation