Logic in Computer Science (LICS 1992)

Paper: Random worlds and maximum entropy (at LICS 1992)

Authors: Grove, A.J. Halpern, J.Y. Koller, D.

Abstract

Given a knowledge base θ containing first-order and statistical facts, a principled method, called the random-worlds method, for computing a degree of belief that some φ holds given θ is considered. If the domain has size N, then one can consider all possible worlds with domain {1, . . ., N} that satisfy θ and compute the fraction of them in which φ is true. The degree of belief is defined as the asymptotic value of this fraction as N grows large. It is shown that when the vocabulary underlying φ and θ uses constants and unary predicates only, one can in many cases use a maximum entropy computation to compute the degree of belief. Making precise exactly when a maximum entropy calculation can be used turns out to be subtle. The subtleties are explored, and sufficient conditions that cover many of the cases that occur in practice are provided

BibTeX

  @InProceedings{GroveHalpernKoller-Randomworldsandmaxi,
    author = 	 {Grove, A.J. and Halpern, J.Y. and Koller, D.},
    title = 	 {Random worlds and maximum entropy},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1992},
    year =	 1992,
    editor =	 {Andre Scedrov},
    month =	 {June}, 
    pages =      {22--33},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }