article

Plausibility measures and default reasoning

Journal of the ACM (JACM), Volume 48, Issue 4

Pages 648 - 685

https://doi.org/10.1145/502090.502092

Published: 01 July 2001 Publication History

Abstract

We introduce a new approach to modeling uncertainty based on plausibility measures. This approach is easily seen to generalize other approaches to modeling uncertainty, such as probability measures, belief functions, and possibility measures. We focus on one application of plausibility measures in this paper: default reasoning. In recent years, a number of different semantics for defaults have been proposed, such as preferential structures, ε-semantics, possibilistic structures, and κ-rankings, that have been shown to be characterized by the same set of axioms, known as the KLM properties. While this was viewed as a surprise, we show here that it is almost inevitable. In the framework of plausibility measures, we can give a necessary condition for the KLM axioms to be sound, and an additional condition necessary and sufficient to ensure that the KLM axioms are complete. This additional condition is so weak that it is almost always met whenever the axioms are sound. In particular, it is easily seen to hold for all the proposals made in the literature.

References

[1]

ADAMS, E. 1975. The Logic of Conditionals. Reidel, Dordrecht, Netherlands.

Google Scholar

[2]

BACCHUS, F., GROVE, A. J., HALPERN,J.Y.,AND KOLLER, D. 1996. From statistical knowledge bases to degrees of belief. Artificial Intelligence 87, 1-2, 75-143.

Digital Library

Google Scholar

[3]

BEN-DAVID, S., AND BEN-ELIYAHU, R. 1994. A modal logic for subjective default reasoning. In Proc. 9th IEEE Symp. on Logic in Computer Science. IEEE Press, 477-486.

Crossref

Google Scholar

[4]

BOSSU, G., AND SIEGEL, P. 1985. Saturation, nonmonotonic reasoning and the closed-world assumption. Artificial Intelligence 25, 13-63.

Digital Library

Google Scholar

[5]

BOUTILIER, C. 1994. Conditional logics of normality: a modal approach. Artificial Intelligence 68, 87-154.

Digital Library

Google Scholar

[6]

BURGESS, J. 1981. Quick completeness proofs for some logics of conditionals. Notre Dame Journal of Formal Logic 22, 76-84.

Google Scholar

[7]

CROCCO, G., AND LAMARRE, P. 1992. On the connection between non-monotonic inference systems and conditional logics. In Proc. Third International Conference on Principles of Knowledge Representation and Reasoning (KR '92). Morgan Kaufmann, San Francisco, 565-571.

Digital Library

Google Scholar

[8]

DARWICHE, A. 1992. A symbolic generalization of probability theory. Ph.D. thesis, Stanford University.

Digital Library

Google Scholar

[9]

DUBOIS,D.AND PRADE, H. 1990. An introduction to possibilistic and fuzzy logics. In Readings in Uncertain Reasoning, G. Shafer and J. Pearl, Eds. Morgan Kaufmann, San Francisco, 742-761.

Digital Library

Google Scholar

[10]

DUBOIS, D., AND PRADE, H. 1991. Possibilistic logic, preferential models, non-monotonicity and related issues. In Proc. Twelfth International Joint Conference on Artificial Intelligence (IJCAI '91). Morgan Kaufmann, San Francisco, 419-424.

Google Scholar

[11]

FREUND, M. 1998. Preferential orders and plausibility measures. Journal of Logic and Computation 8, 2, 147-158.

Crossref

Google Scholar

[12]

FRIEDMAN, N., AND HALPERN, J. Y. 1994. On the complexity of conditional logics. In Principles of Knowledge Representation and Reasoning: Proc. Fourth International Conference (KR '94). Morgan Kaufmann, San Francisco, 202-213.

Digital Library

Google Scholar

[13]

FRIEDMAN, N., AND HALPERN, J. Y. 1995. Plausibility measures: a user's guide. In Proc. Eleventh Conference on Uncertainty in Artificial Intelligence (UAI '95). 175-184.

Digital Library

Google Scholar

[14]

FRIEDMAN,N.AND HALPERN, J. Y. 1996. A qualitative Markov assumption and its implications for belief change. In Proc. Twelfth Conference on Uncertainty in Artificial Intelligence (UAI '96). 263-273.

Digital Library

Google Scholar

[15]

FRIEDMAN, N., HALPERN,J.Y.,AND KOLLER, D. 2000. First-order conditional logic for default reasoning revisited. ACM Trans. on Computational Logic 1, 2, 175-207.

Digital Library

Google Scholar

[16]

GABBAY, D. M., HOGGER,C.J.,AND ROBINSON, J. A., Eds. 1993. Nonmonotonic Reasoning and Uncertain Reasoning. Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3. Oxford University Press, Oxford, UK.

Digital Library

Google Scholar

[17]

GARDENFORS, P. 1988. Knowledge in Flux. MIT Press, Cambridge, Mass.

Google Scholar

[18]

GARDENFORS,P.,AND MAKINSON, D. 1988. Revisions of knowledge systems using epistemic entrenchment. In Proc. Second Conference on Theoretical Aspects of Reasoning about Knowledge. Morgan Kaufmann, San Francisco, 83-95.

Digital Library

Google Scholar

[19]

GARDENFORS,P.,AND MAKINSON, D. 1989. Relations between the theory of change and nonmonotonic logic. In Logic of Theory Change. Workshop proceedings, A. Fuhrmann and M. Morreau, Eds. Springer-Verlag, 185-205.

Digital Library

Google Scholar

[20]

GEFFNER, H. 1992a. Default Reasoning. MIT Press, Cambridge, Mass.

Google Scholar

[21]

GEFFNER, H. 1992b. High probabilities, model preference and default arguments. Mind and Machines 2, 51-70.

Crossref

Google Scholar

[22]

GINSBERG, M. L., Ed. 1987. Readings in Nonmonotonic Reasoning. Morgan Kaufmann, San Francisco.

Digital Library

Google Scholar

[23]

GOLDSZMIDT, M., MORRIS,P.,AND PEARL, J. 1993. A maximum entropy approach to nonmonotonic reasoning. IEEE Transactions of Pattern Analysis and Machine Intelligence 15, 3, 220-232.

Digital Library

Google Scholar

[24]

GOLDSZMIDT, M., AND PEARL, J. 1992. Rank-based systems: A simple approach to belief revision, belief update and reasoning about evidence and actions. In Proc. Third International Conference on Principles of Knowledge Representation and Reasoning (KR '92). Morgan Kaufmann, San Francisco, 661-672.

Google Scholar

[25]

GRECO, G. H. 1987. Fuzzy integrals and fuzzy measures with their values in complete lattices. Journal of Mathematical Analysis and Applications 126, 594-603.

Crossref

Google Scholar

[26]

GROVE, A. 1988. Two modelings for theory change. Journal of Philosophical Logic 17, 157-170.

Crossref

Google Scholar

[27]

HALPERN, J. Y. 2001. Conditional plausibility measures and Bayesian networks. Journal of A.I. Research 14, 359-389.

Digital Library

Google Scholar

[28]

HANSSON, B. 1969. An analysis of some deontic logics. Nous 3, 373-398. Reprinted in R. Hilpinen ed. Deontic Logic: Introductory and systematic readings, Reidel, Dordrecht, 1971, pp. 121-147.

Crossref

Google Scholar

[29]

JEFFREYS, H. 1961. Theory of Probability. Oxford University Press, Oxford, UK.

Google Scholar

[30]

KATSUNO, H., AND SATOH, K. 1991. A unified view of consequence relation, belief revision and conditional logic. In Proc. Twelfth International Joint Conference on Artificial Intelligence (IJCAI '91). Morgan Kaufmann, San Francisco, 406-412.

Digital Library

Google Scholar

[31]

KRAUS, S., LEHMANN, D., AND MAGIDOR, M. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence 44, 167-207.

Digital Library

Google Scholar

[32]

LEHMANN, D., AND MAGIDOR, M. 1992. What does a conditional knowledge base entail? Artificial Intelligence 55, 1-60.

Digital Library

Google Scholar

[33]

LEWIS, D. K. 1973. Counterfactuals. Harvard University Press, Cambridge, Mass.

Google Scholar

[34]

PEARL, J. 1989. Probabilistic semantics for nonmonotonic reasoning: a survey. In Proc. First International Conference on Principles of Knowledge Representation and Reasoning (KR '89), R. J. Brachman, H. J. Levesque, and R. Reiter, Eds. 505-516. Reprinted in Readings in Uncertain Reasoning, G. Shafer and J. Pearl (Eds.), Morgan Kaufmann, San Francisco, 1990, pp. 699-710.

Digital Library

Google Scholar

[35]

PEARL, J. 1990. System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In know90. Morgan Kaufmann, San Francisco, 121-135.

Digital Library

Google Scholar

[36]

SCHLECHTA, K. 1995. Defaults as generalized quantifiers. Journal of Logic and Computation 5, 4, 473-494.

Crossref

Google Scholar

[37]

SCHLECHTA, K. 1997. Filters and partial orders. Logic Journal of the IGPL 5, 5, 753-772.

Crossref

Google Scholar

[38]

SHAFER, G. 1976. A Mathematical Theory of Evidence. Princeton University Press, Princeton, N.J.

Google Scholar

[39]

SHOHAM, Y. 1987. A semantical approach to nonmonotonic logics. In Proc. 2nd IEEE Symp. on Logic in Computer Science. 275-279. Reprinted in M. L. Ginsberg (Ed.), Readings in Nonmonotonic Reasoning, Morgan Kaufman, San Francisco, 1987, pp. 227-250.

Digital Library

Google Scholar

[40]

SPOHN, W. 1988. Ordinal conditional functions: a dynamic theory of epistemic states. In Causation in Decision, Belief Change, and Statistics, W. Harper and B. Skyrms, Eds. Vol. 2. Reidel, Dordrecht, Netherlands, 105-134.

Google Scholar

[41]

WANG, Z., AND KLIR, G. J. 1992. Fuzzy Measure Theory. Plenum Press, New York.

Digital Library

Google Scholar

[42]

WEBER, S. 1991. Uncertainty measures, decomposability and admissibility. Fuzzy Sets and Systems 40, 395-405.

Digital Library

Google Scholar

[43]

WEYDERT, E. 1994a. Doxastic normality logic: A qualitative probabilistic modal framework for defaults. In Logic, Action and Information, A. Fuhrmann and H. Rott, Eds. de Gruyter, New York, 152-171.

Google Scholar

[44]

WEYDERT, E. 1994b. General belief measures. In Proc. Tenth Annual Conference on Uncertainty Artificial Intelligence. Morgan Kaufmann, San Francisco, 575-582.

Digital Library

Google Scholar

Cited By

View all

Gliozzi VPozzato GTessore GValese A(2024)Sequent calculi and an efficient theorem prover for conditional logics with selection function semanticsJournal of Logic and Computation10.1093/logcom/exae037Online publication date: 29-Jul-2024
https://doi.org/10.1093/logcom/exae037
Schockaert S(2024)Embeddings as epistemic statesInternational Journal of Approximate Reasoning10.1016/j.ijar.2023.108981171:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.ijar.2023.108981
Delande EJones BJah M(2023)Exploring an Alternative Approach to the Assessment of Collision RiskJournal of Guidance, Control, and Dynamics10.2514/1.G00670946:3(467-482)Online publication date: Mar-2023
https://doi.org/10.2514/1.G006709
Show More Cited By

Index Terms

Plausibility measures and default reasoning

Recommendations

First-order conditional logic for default reasoning revisited

Conditional logics play an important role in recent attempts to formulate theories of default reasoning. This paper investigates first-order conditional logic. We show that, as for first-order probabilistic logic, it is important not to confound ...
Plausibility measures and default reasoning
AAAI'96: Proceedings of the thirteenth national conference on Artificial intelligence - Volume 2

In recent years, a number of different semantics for defaults have been proposed, such as preferential structures, ε-semantics, possibilistic structures, and κ-rankings, that have been shown to be characterized by the same set of axioms, known as the ...
Plausibility Measures and Default Reasoning: An Overview
LICS '99: Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science

We introduce a new approach to modeling uncertainty based on plausibility measures. This approach is easily seen to generalize other approaches to modeling uncertainty, such as probability measures, belief functions, and possibility measures. We then ...

Reviews

Reviewer: Teodor Rus

The authors introduce a new approach to modeling uncertainty by generalizing a Kolmogorov probability space to a plausibility space. The generalization is obtained by replacing the probability measure on the interval [0,1] with an arbitrary partially ordered set called a plausibility measure. Kolmogorov axioms are replaced by the requirement that a subset must be at least as plausible as any of its subsets. This approach is easily seen to generalize other approaches to modeling uncertainty, such as belief functions, and possibility measures. The authors focus on one particular application of plausibility measures: default reasoning. A number of different semantics for defaults have been proposed, such as preferential structures, epsilon-semantics, possibilistic structures, and k-rankings. All these semantics have been shown to be characterized by the same set of axioms, known as the KLM properties. While this was viewed as a surprise, the authors show in this paper that this is almost inevitable. That is, the authors give a necessary condition for the KLM axioms to be sound, and an additional necessary condition to ensure that the KLM axioms are complete. This additional condition is so weak that it is almost always met whenever the axioms are sound. In particular, it is easily seen to hold for all the proposals made in the literature. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 48, Issue 4

July 2001

303 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/502090

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2001

Published in JACM Volume 48, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
1,130
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gliozzi VPozzato GTessore GValese A(2024)Sequent calculi and an efficient theorem prover for conditional logics with selection function semanticsJournal of Logic and Computation10.1093/logcom/exae037Online publication date: 29-Jul-2024
https://doi.org/10.1093/logcom/exae037
Schockaert S(2024)Embeddings as epistemic statesInternational Journal of Approximate Reasoning10.1016/j.ijar.2023.108981171:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.ijar.2023.108981
Delande EJones BJah M(2023)Exploring an Alternative Approach to the Assessment of Collision RiskJournal of Guidance, Control, and Dynamics10.2514/1.G00670946:3(467-482)Online publication date: Mar-2023
https://doi.org/10.2514/1.G006709
Mata Díaz APino Pérez R(2023)On manipulation in merging epistemic statesInternational Journal of Approximate Reasoning10.1016/j.ijar.2023.01.005155:C(66-103)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.ijar.2023.01.005
Raidl EGomes G(2023)The Implicative ConditionalJournal of Philosophical Logic10.1007/s10992-023-09715-653:1(1-47)Online publication date: 27-Nov-2023
https://doi.org/10.1007/s10992-023-09715-6
Koutras CNomikos CHong JBures MPark JCerny T(2022)Topological semantics for default conditional logicProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507138(897-902)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3477314.3507138
Olivetti NPanic NPozzato G(2022)Labelled Sequent Calculi for Conditional Logics: Conditional Excluded Middle and Conditional Modus Ponens Finally TogetherAIxIA 2022 – Advances in Artificial Intelligence10.1007/978-3-031-27181-6_24(345-357)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-27181-6_24
Koutras CMoyzes CNomikos CTsaprounis KZikos Y(2021)On weak filters and ultrafilters: Set theory from (and for) knowledge representationLogic Journal of the IGPL10.1093/jigpal/jzab03031:1(68-95)Online publication date: 20-Oct-2021
https://doi.org/10.1093/jigpal/jzab030
Stojanović TIkodinović NDavidović TOgnjanović Z(2021)Automated non-monotonic reasoning in System PAnnals of Mathematics and Artificial Intelligence10.1007/s10472-021-09738-289:5-6(471-509)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10472-021-09738-2
Sinatra GLombardi D(2020)Evaluating sources of scientific evidence and claims in the post-truth era may require reappraising plausibility judgmentsEducational Psychologist10.1080/00461520.2020.1730181(1-12)Online publication date: 26-Mar-2020
https://doi.org/10.1080/00461520.2020.1730181
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

First-order conditional logic for default reasoning revisited