Hostname: page-component-848d4c4894-m9kch Total loading time: 0 Render date: 2024-06-12T03:41:51.930Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic conditional probabilities: The non-unary case

Published online by Cambridge University Press:  12 March 2014

Adam J. Grove ,
Joseph Y. Halpern  and
Daphne Koller
Adam J. Grove
Affiliation:
Nec Research Institute, 4 Independence Way, Princeton, NJ 08540, E-mail: grove@research.nj.nec.com
Joseph Y. Halpern
Affiliation:
IBM Almaden Research Center, 650 Harry RD., San Jose, CA 95120, E-mail: halpern@almaden.ibm.com
Daphne Koller
Affiliation:
Department of Computer Science, Stanford University, Stanford, CA 94305, E-mail: daphne@cs.stanford.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences φ and θ, we consider the structures with domain {1, …, N} that satisfy θ, and compute the fraction of them in which φ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon'kiĭ [24], if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon'kiĭ also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well-defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 61 , Issue 1 , March 1996 , pp. 250 - 276
Copyright
Copyright © Association for Symbolic Logic 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bacchus, F., Grove, A. J., Halpern, J. Y., and Koller, D., From statistics to belief, Proceedings of the national conference on artificial intelligence (AAAI '92), 1992, pp. 602–608.Google Scholar
[2]Bacchus, F., Grove, A. J., Halpern, J. Y., and Koller, D., Statistical foundations for default reasoning, Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI '93), 1993, A longer version, entitled From statistical knowledge bases to degrees of belief will appear in Artificial Intelligence.Google Scholar
[3]Carnap, R., Logical foundations of probability, University of Chicago Press, Chicago, 1950.Google Scholar
[4]Carnap, R., The continuum of inductive methods, University of Chicago Press, Chicago, 1952.Google Scholar
[5]Cheeseman, P. C., A method of computing generalized Bayesian probability values for expert systems, Proceedings of the eighth international joint conference on artificial intelligence (IJCAI '83), 1983, pp. 198–202.Google Scholar
[6]Compton, K., 0-1 laws in logic and combinatorics, Proceedings of the 1987 NATO advanced study institute on algorithms and order (Rival, I., editor), Reidel, Dordrecht, Netherlands, 1988, pp. 353–383.Google Scholar
[7]de Laplace, P. S., Essai philosophique sur les probabilités, 1820, English translation is Philosophical Essay on Probabilities, Dover Publications, New York, 1951.Google Scholar
[8]Denbigh, K. G. and Denbigh, J. S., Entropy in relation to incomplete knowledge, Cambridge University Press, Cambridge, UK, 1985.Google Scholar
[9]Dreben, B. and Goldfarb, W. D., The decision problem: Solvable classes of quantificational formulas, Addison-Wesley, Reading, MA, 1979.Google Scholar
[10]Fagin, R., Probabilities on finite models, this Journal, vol. 41 (1976), no. 1, pp. 50–58.Google Scholar
[11]Fagin, R., The number of finite relational structures, Discrete Mathematics, vol. 19 (1977). pp. 17–21.CrossRefGoogle Scholar
[12]Gaifman, H., Probability models and the completeness theorem, International congress of logic methodology and philosophy of science, 1960, This is the abstract of which [13] is the full paper, pp. 77–78.Google Scholar
[13]Gaifman, H., Concerning measures in first order calculi, Israel Journal of Mathematics, vol. 2 (1964), pp. 1–18.CrossRefGoogle Scholar
[14]Glebskiĭ, Y. V., Liogon'kiĭ, M. I.Kogan, D. I., and Talanov, V. A., Range and degree of realizability of formulas in the restricted predicate calculus, Kibernetika, vol. 2 (1969), pp. 17–28.Google Scholar
[15]Graham, R. L., Knuth, D. E., and Patashnik, O., Concrete mathematics—a foundation for computer science, Addison-Wesley, Reading, MA, 1989.CrossRefGoogle Scholar
[16]Grove, A. J., Halpern, J. Y., and Koller, D., Asymptotic conditional probabilities for first-order logic, Part II: the unary case, Research report, IBM, 1993, SIAM Journal on Computing, in press.Google Scholar
[17]Grove, A. J., Halpern, J. Y., and Koller, D., Asymptotic conditional probabilities for first-order logic, Proc. 24th ACM symp. on theory of computing, 1992, pp. 294–305.Google Scholar
[18]Grove, A. J., Halpern, J. Y., and Koller, D., Random worlds and maximum entropy, Journal of Artificial Intelligence Research, vol. 2 (1994), pp. 33–38.CrossRefGoogle Scholar
[19]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[20]Jaynes, E. T., Where do we stand on maximum entropy?, The maximum entropy formalism (Levine, R. D. and Tribus, M., editors), MIT Press, 1978, pp. 15–118.Google Scholar
[21]Keynes, J. M., A treatise on probability, Macmillan, London, 1921.Google Scholar
[22]Kolaitis, Ph. G. and Vardi, M. Y., 0-1 laws and decision problems for fragments of second-order logic, Information and Computation, vol. 87 (1990), pp. 302–338.CrossRefGoogle Scholar
[23]Lewis, H. R., Unsolvable classes of quantificational formulas, Addison-Wesley, New York, 1979.Google Scholar
[24]Liogon'kiĭ, M. I., On the conditional satisfiability ratio of logical formulas, Mathematical Notes of the Academy of the USSR, vol. 6 (1969), pp. 856–861.CrossRefGoogle Scholar
[25]Lynch, J., Almost sure theories, Annals of Mathematical Logic, vol. 18 (1980), pp. 91–135.CrossRefGoogle Scholar
[26]Manna, Z. and Pnueli, A., The temporal logic of reactive and concurrent systems, vol. 1, Springer-Verlag, Berlin, 1992.CrossRefGoogle Scholar
[27]Paris, J. B. and Vencovska, A., On the applicability of maximum entropy to inexact reasoning, International Journal of Approximate Reasoning, vol. 3 (1989), pp. 1–34.CrossRefGoogle Scholar
[28]Powell, R. E. and Shah, S. M., Summability theory and applications, Van Nostrand Reinhold, 1972.Google Scholar
[29]Trakhtenbrot, B. A., Impossibility of an algorithm for the decision problem in finite classes, Doklady Akademii Nauk SSSR, vol. 70 (1950), pp. 569–572.Google Scholar
[30]von Kries, J., Die principien der wahrscheinlichkeitsrechnung und rational expectation, Freiburg, 1886.Google Scholar