Skip to main content

Possibility Theory

  • Reference work entry
Computational Complexity

Article Outline

Glossary

Definition of the Subject

Introduction

Historical Background

Basic Notions of Possibility Theory

Qualitative Possibility Theory

Quantitative Possibility Theory

Probability-Possibility Transformations

Applications and Future Directions

Bibliography

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

Access this chapter

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 1,500.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 1,399.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Abbreviations

Possibility distribution :

A possibility distribution restricts a set of possible values fora variable of interest in an elastic way. It is represented by a mapping from a universe gathering the potential values of the variable toa scale such as the unit interval of the real line, or a finite linearly ordered set, expressing to what extent each value is possible for thevariable. Thus, a possibility distribution restricts a set of more or less possible values belonging to a universe that may be also ordered suchas a subpart of real line for a numerical variable, or not ordered if for instance the variable takes its value in the set of interpretations ofa logical language. This may be used for representing uncertainty if the restriction pertains to possible values for an ill-known state of the world, orfor representing preferences if the restriction encodes a set of values that are considered as more or less satisfactory for somepurpose.

Possibility measure :

A possibility measure is a set function (increasing in the wide sense) that returns the maximum of a possibility distribution over a subset representing an event.

Necessity measure :

A necessity measure is a set function, associated by duality to a possibility measure through a relation expressing that an event is all the more necessarily true (all the more certain) as the opposite event is less possible. A necessity measure estimates to what extent the information represented by the underlying possibility distribution entails the occurrence of the event.

Guaranteed possibility :

A guaranteed possibility measure is a set function (decreasing in the wide sense) that returns the minimum of a possibility distribution over a subset representing an event. While possibility measures evaluate the consistency of the information between an event and the available information represented by the underlying possibility distribution, guaranteed possibility measures capture another view of the idea of possibility related to the idea of (guaranteed) feasibility, or sufficiency condition.

Possibilistic logic :

Standard possibilistic logic is a weighted logic where formulas are pairs made of a classical logical formula and a weight that acts as a lower bound of the necessity of the logical formula. Extended possibilistic logics may include formulas weighted in terms of lower bounds of possibility or guaranteed possibility measures.

Bibliography

  1. Zadeh LA (1978) Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets Syst 1:3–28

    MathSciNet  MATH  Google Scholar 

  2. Gaines BR, Kohout L (1975) Possible automata. In: Proc Int Symp Multiple-ValuedLogic, Bloomington May 13–16. IEEE Press, pp 183–196

    Google Scholar 

  3. Dubois D, Prade H (1998) Possibility theory: Qualitative and quantitative aspects. In: Gabbay DM, Smets PP (eds) Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol 1. Kluwer, Dordrecht, pp 169–226

    Google Scholar 

  4. Dubois D, Nguyen HT, Prade H (2000) Fuzzy sets and probability: Misunderstandings,bridges and gaps. In: Dubois D, Prade H (eds) Fundamentals of Fuzzy Sets. Kluwer, Boston, pp 343–438

    Google Scholar 

  5. Hughes GE, Cresswell MJ (1968) An introduction to modal logic. Methuen, London

    MATH  Google Scholar 

  6. Shackle GLS (1961) Decision, order and time in human affairs, 2nd edn. CambridgeUniversity Press, Cambridge

    Google Scholar 

  7. Spohn W (1990) A general, nonprobabilistic theory of inductive reasoning. In:Shachter RD et al (eds) Uncertainty in Artificial Intelligence, vol 4. North Holland, Amsterdam, pp 149–158

    Google Scholar 

  8. Lewis DL (1973) Counterfactuals. Basil Blackwell, Oxford

    Google Scholar 

  9. Dubois D (1986) Belief structures, possibility theory and decomposable measures on finite sets. Comput AI 5:403–416

    MATH  Google Scholar 

  10. Sudkamp T (2002) Similarity and the measurement of possibility. Actes RencontresFrancophones sur la Logique Floue et ses Applications (Montpellier, France). Cepadues Editions, Toulouse, pp 13–26

    Google Scholar 

  11. Cohen LJ (1977) The probable and the provable. Clarendon, Oxford

    Google Scholar 

  12. Zadeh LA (1979) Fuzzy sets and information granularity. In: Gupta MM, Ragade R, YagerRR (eds) Advances in fuzzy set theory and applications. North-Holland, Amsterdam, pp 3–18

    Google Scholar 

  13. Zadeh LA (1982) Possibility theory and soft data analysis. In: Cobb L, Thrall R (eds) Mathematical frontiers of social and policy sciences. Westview Press, Boulder, pp 69–129

    Google Scholar 

  14. Dubois D, Prade H (1980) Fuzzy sets and systems: Theory and applications. AcademicPress, New York

    MATH  Google Scholar 

  15. Dubois D, Prade H (1988) Possibility theory. Plenum, New York

    MATH  Google Scholar 

  16. Klir GJ, Folger T (1988) Fuzzy sets, uncertainty and information. Prentice Hall, Englewood Cliffs

    MATH  Google Scholar 

  17. Yager RR (1983) An introduction to applications of possibility theory. Hum Syst Manag 3:246–269

    Google Scholar 

  18. Dubois D, Hajek P, Prade H (2000) Knowledge‐driven versus data‐driven logics. J Log Lang Inf 9:65–89

    MathSciNet  MATH  Google Scholar 

  19. Walley P (1996) Measures of uncertainty in expert systems. Artif Intell 83:1–58

    MathSciNet  Google Scholar 

  20. De Cooman G (1997) Possibility theory. Part I: Measure- and integral‐theoretic groundwork; Part II: Conditional possibility; Part III: Possibilistic independence. Int J Gen Syst 25:291–371

    MATH  Google Scholar 

  21. De Campos LM, Huete JF (1999) Independence concepts in possibility theory. Fuzzy Sets Syst 103:127–152 \( { \& } \) 487–506

    Google Scholar 

  22. Dubois DD, Farinas del Cerro L, Herzig A, Prade H (1997) Qualitative relevance andindependence: A roadmap. In: Proc of the 15h Inter Joint Conf on Artif Intell, Nagoya, 23–29 August, 1997. Morgan Kaufmann, San Mateo,pp 62–67

    Google Scholar 

  23. Borgelt C, Gebhardt J, Kruse R (2000) Possibilistic graphical models. In: DellaRiccia G et al (eds) Computational intelligence in data mining. Springer, Wien, pp 51–68

    Google Scholar 

  24. Benferhat S, Dubois D, Garcia L, Prade H (2002) On the transformation between possibilistic logic bases and possibilistic causal networks. Int J Approx Reason 29(2):135–173

    MathSciNet  MATH  Google Scholar 

  25. Ben Amor N, Benferhat S, Mellouli K(2003) Anytime propagation algorithm for min-based possibilistic graphs. Soft Comput 8(2):150–161

    Google Scholar 

  26. Borgelt C, Kruse R (2003) Operations and evaluation measures for learning possibilistic graphical models. Artif Intell 148(1–2):385–418

    MathSciNet  MATH  Google Scholar 

  27. Gärdenfors P (1988) Knowledge in flux. MIT Press, Cambridge

    Google Scholar 

  28. Dubois D, Prade H (1991) Epistemic entrenchment and possibilistic logic. Artif Intell50:223–239

    MathSciNet  MATH  Google Scholar 

  29. Ben Amor N et al (2002) A theoretical framework for possibilistic independence in a weakly ordered setting. Int J Uncert Fuzz \( { \& } \) Knowl-B Syst 10:117–155

    Google Scholar 

  30. Lehmann D, Magidor M (1992) What does a conditional knowledge base entail? Artif Intell 55:1–60

    MathSciNet  MATH  Google Scholar 

  31. Dubois D, Fargier H, Prade H (2004) Ordinal and probabilistic representations of acceptance. J Artif Intell Res 22:23–56

    MathSciNet  MATH  Google Scholar 

  32. Benferhat S, Dubois D, Prade H (1997) Nonmonotonic reasoning, conditional objects and possibility theory Artif Intell 92:259–276

    Google Scholar 

  33. Pearl J (1990) System Z: A natural ordering of defaults with tractable applications todefault reasoning. In: Proc 3rd Conf Theoretical Aspects of Reasoning About Knowledge. MorganKaufmann, San Francisco, pp 121–135

    Google Scholar 

  34. Dubois D, Lang J, Prade H (1994) Possibilistic logic. In: Gabbay DM et al (eds) Handbook of logic in AI and logic programming, vol 3. Oxford University Press, Oxford, pp 439–513

    Google Scholar 

  35. Benferhat S, Dubois D, Prade H (1998) Practical handling of exception‐tainted rules and independence information in possibilistic logic. Appl Intell 9:101–127

    Google Scholar 

  36. Dubois D, Prade H (2004)Possibilistic logic: A retrospective and prospective view. Fuzzy Sets Syst 144:3–23

    MathSciNet  MATH  Google Scholar 

  37. Dubois D, Prade H (2007) Toward multiple‐agent extensions of possibilisticlogic. In: Proc IEEE Inter Conf on Fuzzy Systems (FUZZ-IEEE (2007)), London 23–26 July, 2007. pp 187–192

    Google Scholar 

  38. Benferhat S, Dubois D, Garcia L, Prade H (2002) On the transformation between possibilistic logic bases and possibilistic causal networks. Int J Approx Reason 29:135–173

    MathSciNet  MATH  Google Scholar 

  39. Ben Amor N, Benferhat S (2005) Graphoid properties of qualitative possibilistic independence relations. Int J Uncert Fuzz \( { \& } \) Knowl-B Syst 13:59–97

    Google Scholar 

  40. Savage LJ (1972) The foundations of statistics. Dover, New York

    MATH  Google Scholar 

  41. Yager RR (1979) Possibilistic decision making. IEEE Trans Syst Man Cybern 9:388–392

    MathSciNet  Google Scholar 

  42. Whalen T (1984) Decision making under uncertainty with various assumptions about available information. IEEE Trans Syst Man Cybern 14:888–900

    MathSciNet  Google Scholar 

  43. Grabisch M, Murofushi T, Sugeno M (eds) (2000) Fuzzy measures and integrals theory andapplications. Physica, Heidelberg

    MATH  Google Scholar 

  44. Dubois D, Prade H, Sabbadin R (2000) Qualitative decision theory with Sugeno integrals. In:Grabisch M, Murofushi T, Sugeno M (eds) Fuzzy measures and integrals theory andapplications. Physica, Heidelberg, pp 314–322

    Google Scholar 

  45. Dubois D, Prade H, Sabbadin R (2001) Decision‐theoretic foundations of possibility theory. Eur J Oper Res 128:459–478

    MathSciNet  MATH  Google Scholar 

  46. Dubois D, Fargier H, Perny P, Prade H (2003) Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach. Artif Intell 148:219–260

    MATH  Google Scholar 

  47. Dubois D, Fargier H (2003) Qualitative decision rules under uncertainty. In: DellaRiccia G et al (eds) Planning based on decision theory. CISM courses and Lectures, vol 472. Springer, Wien, pp 3–26

    Google Scholar 

  48. Fargier H, Sabbadin R (2005) Qualitative decision under uncertainty: Back toexpected utility. Artif Intell 164:245–280

    MathSciNet  MATH  Google Scholar 

  49. Dubois D (2006) Possibility theory and statistical reasoning. Comput Stat Data Anal 51(1):47–69

    MATH  Google Scholar 

  50. Dubois D, Prade H (1992) When upper probabilities are possibility measures. Fuzzy Sets Syst 49:s 65–74

    MathSciNet  Google Scholar 

  51. Dubois D, Moral S, Prade H (1997) A semantics for possibility theory based onlikelihoods. J Math Anal Appl 205:359–380

    MathSciNet  MATH  Google Scholar 

  52. Shafer G (1987) Belief functions and possibility measures. In: Bezdek JC (ed) Analysisof fuzzy information, vol I: Mathematics and Logic. CRC Press, Boca Raton, pp 51–84

    Google Scholar 

  53. Benferhat S, Dubois D, Prade H (1999) Possibilistic and standard probabilisticsemantics of conditional knowledge bases. J Log Comput 9:873–895

    MathSciNet  MATH  Google Scholar 

  54. Maslov V (1987) Méthodes Opératorielles. Mir Publications, Moscow

    MATH  Google Scholar 

  55. Kolokoltsov VN, Maslov VP (1997) Idempotent analysis and applications. Kluwer, Dordrecht

    MATH  Google Scholar 

  56. Puhalskii A (2001) Large deviations and idempotent probability. Chapman and Hall,Boca Raton

    MATH  Google Scholar 

  57. Nguyen HT, Bouchon-Meunier B (2003) Random sets and large deviations principle asa foundation for possibility measures. Soft Comput 8:61–70

    MATH  Google Scholar 

  58. De Cooman G, Aeyels D (1999) Supremum‐preserving upper probabilities. Inf Sci 118:173–212

    MATH  Google Scholar 

  59. Walley P, De Cooman G (1999) A behavioural model for linguistic uncertainty. Inf Sci 134:1–37

    Google Scholar 

  60. Gebhardt J, Kruse R (1993) The context model. I Int J Approx Reason 9:283–314

    Google Scholar 

  61. Joslyn C (1997) Measurement of possibilistic histograms from interval data. Int J Gen Syst 26:9–33

    MathSciNet  MATH  Google Scholar 

  62. Neumaier A (2004) Clouds, fuzzy sets and probability intervals. Reliab Comput 10:249–272

    MathSciNet  MATH  Google Scholar 

  63. De Baets B, Tsiporkova E, Mesiar R (1999) Conditioning in possibility with strict order norms. Fuzzy Sets Syst 106:221–229

    MATH  Google Scholar 

  64. Dubois D, Prade H (1997) Bayesian conditioning in possibility theory. Fuzzy Sets Syst 92:223–240

    MathSciNet  MATH  Google Scholar 

  65. De Cooman G (2001) Integration and conditioning in numerical possibility theory. Ann Math AI 32:87–123

    Google Scholar 

  66. Walley P (1991) Statistical reasoning with imprecise probabilities. Chapman andHall, Boca Raton

    MATH  Google Scholar 

  67. Klir GJ (1990) A principle of uncertainty and information invariance. Int J Gen Syst 17:249–275

    MATH  Google Scholar 

  68. Geer JF, Klir GJ (1992) A mathematical analysis of information‐preserving transformations between probabilistic and possibilistic formulations of uncertainty. Int J Gen Syst 20:143–176

    MATH  Google Scholar 

  69. Dubois D, Prade H, Sandri S (1993) On possibility/probability transformations. In:Lowen R, Roubens M (eds) Fuzzy logic: State of the art. Kluwer, Dordrecht, pp 103–112

    Google Scholar 

  70. Klir GJ, Parviz B (1992) Probability B‐possibility transformations: A comparison. Int J Gen Syst 21:291–310

    MATH  Google Scholar 

  71. Dubois D, Prade H (1982) On several representations of an uncertain body of evidence. In: Gupta M, Sanchez E (eds) Fuzzy information and decision processes. North-Holland, Amsterdam, pp 167–181

    Google Scholar 

  72. Smets P (1990) Constructing the pignistic probability function in a context ofuncertainty. In: Henrion M et al (eds) Uncertainty in artificial intelligence, vol 5. North-Holland,Amsterdam, pp 29–39

    Google Scholar 

  73. Dubois D, Prade H (2001) Smets new semantics for quantitative possibilitytheory. In: Proc ESQARU (2001), Toulouse, LNAI 2143. Springer, pp 410–421

    Google Scholar 

  74. Birnbaum ZW (1948) On random variables with comparable peakedness. Ann Math Stat 19:76–81

    MathSciNet  MATH  Google Scholar 

  75. Dubois D, Huellermeier E (2005) A Notion of comparative probabilistic entropybased on the possibilistic specificity ordering. In: Godo L (ed) Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Proc of 8th EuropeanConference, ECSQARU 2005, Barcelona, 6–8. Lecture Notes in Computer Science, vol 3571. Springer, Berlin

    Google Scholar 

  76. Dubois D, Foulloy L, Mauris G, Prade H (2004) Probability‐possibility transformations, triangular fuzzy sets, and probabilistic inequalities. Reliab Comput 10:273–297

    MathSciNet  MATH  Google Scholar 

  77. Mauris G, Lasserre V, Foulloy L (2000) Fuzzy modeling of measurement data acquired from physical sensors. IEEE Trans Meas Instrum 49:1201–1205

    Google Scholar 

  78. Baudrit C, Dubois D, Fargier H (2004) Practical representation of incompleteprobabilistic information. In: Lopz-Diaz M et al (eds) Soft methods in probability andstatistics. Proc 2nd Int Conf. Springer, Oviedo, pp 149–156

    Google Scholar 

  79. Dubois D, Prade H, Smets P (2003) A definition of subjective possibility. Badania Operacyjne i Decyzije (Wroclaw) 4:7–22

    MathSciNet  Google Scholar 

  80. Dubois D, Prade H (1983) Unfair coins and necessity measures: A possibilistic interpretation of histograms. Fuzzy Sets Syst 10(1):15–20

    MATH  Google Scholar 

  81. Dubois D, Prade H (1985) Evidence measures based on fuzzy information. Automatica 21:547–562

    MathSciNet  MATH  Google Scholar 

  82. Van Leekwijck W, Kerre EE (2001) Defuzzification: Criteria and classification. Fuzzy Sets Syst 108:303–314

    Google Scholar 

  83. Dubois D, Prade H (1987) The mean value of a fuzzy number. Fuzzy Sets Syst 24:279–300

    MathSciNet  MATH  Google Scholar 

  84. Yager RR (1981) A procedure for ordering fuzzy subsets of the unit interval. Inf Sci 24:143–161

    MathSciNet  MATH  Google Scholar 

  85. Chanas S, Nowakowski M (1988) Single value simulation of fuzzy variable. Fuzzy Sets Syst 25:43–57

    MathSciNet  MATH  Google Scholar 

  86. Dubois D, Prade H (1996) What are fuzzy rules and how to use them. Fuzzy Sets Syst 84:169–185

    MathSciNet  MATH  Google Scholar 

  87. Dubois D, Prade H, Ughetto L (2003) A new perspective on reasoning with fuzzy rules. Int J Intell Syst 18:541–567

    MATH  Google Scholar 

  88. Galichet S, Dubois D, Prade H (2004) Imprecise specification of ill-known functions using gradual rules. Int J Approx Reason 35:205–222

    MathSciNet  MATH  Google Scholar 

  89. Dubois D, Huellermeier E, Prade H (2003) A note on quality measures for fuzzyassociation rules. In: De Baets B, Bilgic T (eds) Fuzzy sets and systems. Proc of the 10th Int FuzzySystems Assoc World Congress IFSA, Istanbul, 2003, LNAI 2715. Springer, pp 346–353

    Google Scholar 

  90. Dubois D, Fargier H, Prade H (1996) Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty. Appl Intell 6:287–309

    Google Scholar 

  91. Dubois D, Fortemps P (1999) Computing improved optimal solutions to max-min flexible constraint satisfaction problems. Eur J Oper Res 118:95–126

    MATH  Google Scholar 

  92. Dubois D, Fargier H, Prade H (1995) Fuzzy constraints in job-shop scheduling. J Intell Manuf 6:215–234

    Google Scholar 

  93. Slowinski R, Hapke M (eds) (2000) Scheduling under fuzziness. Physica, Heidelberg

    MATH  Google Scholar 

  94. Chanas S, Zielinski P (2001) Critical path analysis in the network with fuzzy activity times. Fuzzy Sets Syst 122:195–204

    MathSciNet  MATH  Google Scholar 

  95. Chanas S, Dubois D, Zielinski P (2002) Necessary criticality in the network with imprecise activity times. IEEE Trans Man Mach Cybern 32:393–407

    Google Scholar 

  96. Dubois D, Kerre E, Mesiar R, Prade H (2000) Fuzzy interval analysis. In: Dubois D,Prade H (eds) Fundamentals of fuzzy sets. Kluwer, Boston, pp 483–581

    Google Scholar 

  97. Dubois D, Prade H (1991) Random sets and fuzzy interval analysis. Fuzzy Sets Syst 42:87–101

    MathSciNet  MATH  Google Scholar 

  98. Helton JC, Oberkampf WL (eds) (2004) Alternative Representations of EpistemicUncertainty. Reliability Engineering and Systems Safety, vol 85. Elsevier, Amsterdam, p 369

    Google Scholar 

  99. Guyonnet D et al (2003) Hybrid approach for addressing uncertainty in risk assessments. J Env Eng 129:68–78

    Google Scholar 

  100. Gil M (ed) (2001) Fuzzy random variables. Inf Sci 133

    Google Scholar 

  101. Krishnapuram R, Keller J (1993) A possibilistic approach to clustering. IEEE Trans Fuzzy Syst 1:98–110

    Google Scholar 

  102. Bezdek J, Keller J, Krishnapuram R, Pal N (1999) Fuzzy models and algorithms forpattern recognition and image processing. In: The Handbooks of Fuzzy Sets Series. Kluwer,Boston

    Google Scholar 

  103. Wolkenhauer O (1998) Possibility theory with applications to data analysis. ResearchStudies Press, Chichester

    MATH  Google Scholar 

  104. Tanaka H, Guo PJ (1999) Possibilistic data analysis for operations research. Physica,Heidelberg

    MATH  Google Scholar 

  105. Borgelt C, Gebhardt J, Kruse R (2000) Possibilistic graphical models. In: DellaRiccia G et al (eds) Computational intelligence in data mining. CISM Series, vol N408. Springer, Berlin

    Google Scholar 

  106. Bosc P, Prade H (1997) An introduction to the fuzzy set and possibility theory‐basedtreatment of soft queries and uncertain of imprecise databases. In: Smets P, Motro A (eds)Uncertainty management in information systems. Kluwer, Dordrecht, pp 285–324

    Google Scholar 

  107. Cayrac D, Dubois D, Prade H (1996) Handling uncertainty with possibility theory andfuzzy sets in a satellite fault diagnosis application. IEEE Trans Fuzzy Syst 4:251–269

    Google Scholar 

  108. Boverie S et al (2002) Online diagnosis of engine dyno test benches: A possibilisticapproach. Proc 15th Eur Conf on Artificial Intelligence, Lyon. IOS Press, Amsterdam,p 658–662

    Google Scholar 

  109. Benferhat S, Dubois D, Prade H, Williams M-A (2002) A practical approach to revising prioritized knowledge bases. Stud Log 70:105–130

    MathSciNet  MATH  Google Scholar 

  110. Amgoud L, Prade H (2004) Reaching agreement through argumentation:A possibilistic approach. In: Proc of the 9th Int Conf on Principles of Knowledge Representation and Reasoning (KR'04), Whistler. AAAI Press, Cambridge,pp 175–182

    Google Scholar 

  111. Dubois D, Huellermeier E, Prade H (2002) Fuzzy set-based methods in instance‐based reasoning. IEEE Trans Fuzzy Syst 10:322–332

    Google Scholar 

  112. Huellermeier E, Dubois D, Prade H (2002) Model adaptation in possibilistic instance‐based reasoning. IEEE Trans Fuzzy Syst 10:333–339

    Google Scholar 

  113. Raufaste E, Da Silva R, Neves C (2003) Mariné testing the descriptive validity of possibility theory in human judgements of uncertainty. Artif Intell 148:197–218

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag

About this entry

Cite this entry

Dubois, D., Prade, H. (2012). Possibility Theory. In: Meyers, R. (eds) Computational Complexity. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-1800-9_139

Download citation

Publish with us

Policies and ethics