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

Authors: Adam J. Grove Joseph Y. Halpern Daphne Koller

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 = 	 {Adam J. Grove and Joseph Y. Halpern and Daphne Koller},
    title = 	 {Random worlds and maximum entropy},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 1992)},
    year =	 {1992},
    month =	 {June}, 
    pages =      {22--33},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }