\documentstyle[theapa,jair,twoside,11pt,psfig]{article}
\input epsf %% at top of file
\include{defn}
\include{bghkmac}
\newcommand{\Lunaeqnoarg}{\Laeq}
\newcommand{\Infected}{\mbox{\em Infected-By\/}}
\newcommand{\nworldsvoc}[1]{{{\it \#[#1]worlds}}_{N}^{\epsvec}}

\jairheading{2}{1994}{33--88}{4/94}{8/94}
\ShortHeadings{Random Worlds and Maximum Entropy}%
{Grove, Halpern, \& Koller}
\firstpageno{33}

\begin{document}
\title{Random Worlds and Maximum Entropy}

\author{\name
        Adam J. Grove   \email grove@research.nj.nec.com \\
\addr     NEC Research Institute,
4 Independence Way\\
Princeton, NJ 08540
\AND
\name   Joseph Y. Halpern \email halpern@almaden.ibm.com\\
\addr     IBM Almaden Research Center,
650 Harry Rd.\\
San Jose, CA 95120
\AND
\name         Daphne Koller \email daphne@cs.berkeley.edu\\
\addr     Computer Science Division, University of California\\
Berkeley, Berkeley, CA 94720}
\maketitle

\begin{abstract}
Given a knowledge base $\KB$ containing first-order and statistical
facts, we consider a principled method, called the {\em random-worlds
method}, for computing a degree of belief that some formula $\phi$
holds given $\KB$.
If we are reasoning about a world or system consisting of $N$ individuals,
then we can consider
all possible worlds, or first-order models,
with domain $\{1,\ldots, N\}$ that satisfy $\KB$, and compute the fraction
of them in which $\phi$ is true. We define the degree of belief to be the
asymptotic value of this fraction as $N$ grows large.
We show that when the vocabulary underlying $\phi$ and $\KB$ uses constants
and unary predicates only,
we can naturally associate an {\em entropy} with
each world. As $N$ grows larger, there are many more worlds with higher
entropy. Therefore,
we can use a {\em maximum-entropy} computation to
compute the degree of belief.
This result is in a similar spirit to previous work in physics
and artificial intelligence,
but is far more general.
Of equal interest to the
result itself
are the limitations on its scope.
Most importantly, the restriction to unary predicates seems necessary.
Although the random-worlds method makes sense in general, the
connection to maximum entropy seems to disappear in the non-unary case.
These observations suggest unexpected limitations to the applicability of
maximum-entropy methods.
\end{abstract}



\section{Introduction}

Consider an agent (or expert system)
with some information about a particular subject, such as internal
medicine.
Some facts,
such as ``all patients with hepatitis exhibit jaundice'',
can be naturally expressed in a standard first-order logic, while
others,
such as ``80\% of patients that exhibit jaundice have hepatitis'', are
statistical.
Suppose the agent wants to use this information to make decisions.
For example, a doctor might
need to decide whether to administer antibiotics to a particular
patient Eric.  To apply standard tools
of decision theory (see \cite{LuceR} for an introduction),
the agent must assign probabilities, or {\em degrees of
belief}, to various events.  For example, the doctor may need to
assign a degree of belief to an event such as ``Eric has hepatitis''.
We would therefore
like techniques for computing degrees of
belief in a principled manner, using
all the data at hand.  In this paper we investigate the properties of one
particular formalism for doing this.

The method we consider, which we call the {\em random-worlds method}, has
origins that go back to Bernoulli and Laplace \citeyear{Laplace}.
It is essentially an application of what has been called
the {\em principle of indifference\/} \cite{Keynes}.  The basic idea is quite
straightforward.  Suppose we are interested in attaching a degree of belief
to a formula $\phi$ given a knowledge base $\KB$.
One useful
way of assigning
semantics to degrees of belief formulas is to use a probability
distribution over a set of {\em possible worlds\/} \cite{Hal4}.
More concretely,
suppose for now that we are reasoning about $N$ individuals,
$1, \ldots, N$.
A {\em world\/} is a complete description of which individuals have
each of the properties of interest.  Formally, a world is just a
model, or interpretation, over our first-order language.  For example, if
our language consists of the unary predicates $\Hepatitis$, $\Jaundice$,
$\Child$, and $\BlueEyed$, the binary predicate $\Infected$, and the
constant $\Eric$, then a world describes which subset of the $N$
individuals satisfies each of the unary predicates, which set of
pairs is in the $\Infected$ relation, and which of the $N$ individuals
is $\Eric$.
Given a prior probability distribution over the set of possible
worlds, the agent can obtain a degree of belief in $\phi$ given $\KB$
by conditioning on $\KB$ to obtain a posterior distribution, and then
computing the probability of $\phi$ according to this new
distribution.
The random-worlds method uses the principle of indifference to choose a
particular prior distribution over the set of worlds: all the worlds
are taken to be equally likely.
It is easy to see that the degree of belief in $\phi$ given $\KB$ is
then precisely the fraction of worlds satisfying $\KB$
that also satisfy $\phi$.


The approach so far described applies whenever we actually know the
precise domain size $N$; unfortunately this is fairly uncommon.
In many cases, however,
it is reasonable to believe that $N$ is ``large''.
We are thus particularly interested in the asymptotic behavior
of this fraction; that is, we take our degree of belief to be the asymptotic
value of this fraction as $N$ grows large.

For example,
suppose we want to reason about a domain of hospital patients, and
$\KB$ is the conjunction of the following four formulas:
\begin{itemize}
\item
$\forall x (\Hepatitis(x) \rimp \Jaundice(x))$ (``all patients with
hepatitis exhibit jaundice''),
\item
$\cprop{\Hepatitis(x)}{\Jaundice(x)}{x} \approx 0.8$ (``approximately 80\% of
patients that exhibit jaundice have hepatitis''; we
explain this formalism and the reason we say ``approximately 80\%'' rather
than ``exactly 80\%'' in Section~\ref{prelim.stat}),
\item $\prop{\BlueEyed(x)}{x} \approx 0.25$ (``approximately 25\% of patients have
blue eyes''),
\item
$\Jaundice(\Eric) \land \Prem(\Eric)$ (``Eric is
a child who exhibits jaundice'').
\end{itemize}
Let
$\phi$ be $\Hepatitis(\Eric)$; that is, we want to ascribe a degree of belief
to the statement ``Eric has hepatitis''.
Suppose the domain has size $N$.  Then we want to consider all
worlds
with domain $\{1, \ldots, N \}$ such that
the set of individuals satisfying $\Hepatitis$ is a subset of
those satisfying $\Jaundice$,
approximately 80\% of the individuals satisfying
$\Jaundice$ also satisfy $\Hepatitis$,
approximately 25\% of the individuals satisfy $\BlueEyed$,
and (the
interpretation of) $\Eric$ is an individual satisfying $\Jaundice$ and $\Prem$.
It is straightforward to show that, as expected,
$\Hepatitis(\Eric)$ holds
in approximately 80\% of these structures.  Moreover, as
$N$ gets large, the fraction of structures in which $\Hepatitis(\Eric)$ holds
converges to exactly~$0.8$.

Since 80\% of the patients that exhibit jaundice have hepatitis and Eric
exhibits jaundice, a degree of belief of 0.8 that Eric has hepatitis seems
justifiable.  Note that, in this example, the information that Eric is a
child is essentially
treated as irrelevant.  We would get the same answer if
we did not have the information $\Prem(\Eric)$.
It can also be shown
that the degree of belief in $\BlueEyed(\Eric)$ converges to $0.25$ as $N$
gets large.
Furthermore,
the degree of belief of
$\BlueEyed(\Eric) \land \Jaundice(\Eric)$ converges to $0.2$, the product
of $0.8$ and $0.25$.
As we shall see, this is because
the random-worlds method treats
$\BlueEyed$ and $\Jaundice$ as being independent, which is
reasonable because there is no evidence to the contrary.
(It would surely be strange to postulate that two properties were
correlated unless there were reason to believe they
were connected in some way.)

Thus, at least in this example, the random-worlds
method gives answers that follow from the heuristic
assumptions made in many standard AI systems
\cite{Pearl90,Pollock84,Speigelhalter}.
Are such intuitive results typical?
When do we get convergence?
And when we do, is there a practical way to compute
degrees of belief?

The answer to the first question is yes, as we discuss
in detail in \cite{BGHKfull}.
In that paper, we show that the random-worlds method
is remarkably successful at satisfying the desiderata
of both nonmonotonic (default) reasoning
\cite{Readings.Nonmon} and reference class reasoning
\cite{Kyburg:Reference.Class}.
The results of \cite{BGHKfull} show that
the behavior we saw in the example above holds
quite generally, as do many other properties we would
hope to have satisfied.
Thus, in this paper we do not spend time justifying the random-worlds
approach, nor do we discuss its strengths and weaknesses;
the reader is referred to \cite{BGHKfull} for such discussion
and for an examination of previous work in the spirit of random worlds
(most notably \cite{Carnap,Carnap2} and subsequent work).
Rather,
we focus on the latter two questions asked above.
These questions may seem quite familiar to
readers aware of the work on asymptotic probabilities
for various logics.
For example, in the context of first-order formulas, it is well-known
that a
formula with no constant or
function symbols has an asymptotic probability of either 0 or 1
\cite{Fagin01,Glebskii}. Furthermore, we can decide
which \cite{Gr83}.
However, the 0-1 law fails if the language includes constants or if we
look at conditional
probabilities \cite{Fagin01}, and we need
both these features in order
to reason about degrees of belief
for formulas involving particular individuals, conditioned on
what is known.

In two companion papers \cite{GHK1a,GHK1b},
we consider the question of
what happens in the pure first-order case (where there is no statistical
information) in greater detail.
We show that as long as there is at least one binary predicate symbol
in the language, then not only do we not get asymptotic conditional
probabilities in general
(as was already shown by Fagin~\citeyear{Fagin01}), but almost all the
questions one might want to ask (such as deciding whether the limiting
probability exists) are highly undecidable.
However, if we restrict to a
vocabulary with only unary predicate symbols and constants,
then as long as the formula on which we are conditioning is
satisfiable in arbitrarily large models (a question which is decidable in
the unary case), the asymptotic conditional probability exists and can
be computed effectively.

In this paper, we
consider
the much more useful
case where the knowledge base has statistical
as well as first-order information.
In light of the results of \cite{GHK1a,GHK1b}, for most of the
paper we restrict attention to the case when the knowledge base
is expressed in a unary language.
Our major result
involves showing that
asymptotic conditional probabilities can often be computed using
{\em the principle of maximum entropy\/} \cite{Jaynes57,ShannonWeaver}.

To understand the use of maximum entropy, suppose the vocabulary consists of
the unary predicate symbols $P_1, \ldots, P_k$.  We can consider the $2^k$
{\em atoms} that can be formed from these predicate symbols, namely, the
formulas of the form $P'_1 \land \ldots \land P'_k$, where each $P'_i$ is
either $P_i$ or $\neg P_i$.  We can view the knowledge base as placing constraints
on the proportion of domain elements satisfying each atom. For example, the
constraint $\cprop{P_1(x)}{P_2(x)}{x} = 1/2$ says that the proportion of the
domain satisfying some atom that contains $P_2$ as a conjunct is twice the
proportion satisfying atoms that contain both $P_1$ and $P_2$ as conjuncts.
Given a model of $\KB$, we can define the entropy of this model as the
entropy of the vector denoting the proportions of the different atoms. We
show that, as $N$ grows large, there are many more models with high entropy
than with lower entropy. Therefore, models with high entropy dominate. We
use this {\em concentration phenomenon} to show that our degree of belief in
$\phi$ given $\KB$ according to the random-worlds method is closely
related to the assignment of proportions to atoms that has maximum
entropy among all assignments consistent with the constraints imposed
by $\KB$.

The concentration phenomenon relating entropy to the random-worlds method is
well-known \cite{Jaynes1,Jaynes2}.  In physics, the ``worlds''
are the possible configurations of a system typically consisting
of many particles or molecules,
and the mutually exclusive
properties (our atoms) can be, for example, quantum states. The
corresponding entropy measure is at the heart of statistical mechanics and
thermodynamics.  There are subtle but important differences between our
viewpoint and that of the physicists.
The main one
lies in our choice of language.
We want to express some intelligent
agent's knowledge, which is why we take first-order logic as our starting
point.
The most specific difference concerns constant symbols. We need
these because the most
interesting questions for us arise when we have some knowledge about---and
wish to assign degrees of belief to statements concerning---a
particular individual.
The parallel in physics would address properties of a single particle, which
is generally considered to be well outside the scope of statistical
mechanics.

Another work that examines the connection between
random worlds and entropy from our point of view---computing degrees of
belief for formulas in a particular logic---is that of Paris and Vencovska
\citeyear{PV}. They restrict the knowledge base to consist of a
conjunction of constraints that (in our notation) have the form
$\cprop{\pf(x)}{\ps(x)}{x} \approx r$ and $\prop{\pf(x)}{x} \approx r$,
where $\ps$ and $\pf$ are quantifier-free formulas involving unary
predicates only, with no constant symbols.
Not only is most of the expressive power of first-order logic
not available in their approach, but the statistical information
that can be expressed is quite limited.
For example, it is not possible to make general
assertions about statistical independence.
Paris and Vencovska show that
the degree of belief can be computed using maximum entropy
for their language. Shastri \citeyear{Shastri} has also shown such a result,
of nearly equivalent scope.
But, as we have already suggested, we believe that it is important
to look at a far richer language.
Our language allows arbitrary
first-order assertions, full Boolean logic,
arbitrary polynomial combinations of statistical expressions, and
more;
these are all features that are actually useful to
knowledge-representation practitioners. Furthermore, the random-worlds
method makes perfect sense in this rich setting.
The goal of this paper is to discover whether the connection to
maximum entropy also holds. We show that maximum entropy
continues to be widely useful, covering many problems that are
far outside the scope of \cite{PV,Shastri}.


On the other hand, it turns out that we cannot make this connection for our
entire language.
For one thing, as we hinted earlier, there are
problems if we try
to condition on a knowledge base that includes non-unary predicates;
we suspect that maximum entropy has no role whatsoever in this case.
In addition, we show that there are subtleties that arise involving the
interaction
between statistical information and first-order quantification.
We feel that an important contribution of this paper lies in
pointing out some limitations of maximum-entropy methods.

The rest of this paper is organized as follows.  In the next section, we
discuss our formal framework (essentially, that of
\cite{Bacchus,Hal4}).
We discuss the syntax and semantics of
statistical assertions, issues
involving ``approximately equals'', and define the random-worlds method
formally.
In Section~\ref{methm} we state the basic results that connect
maximum entropy to random-worlds, and in Section~\ref{compute} we
discuss how to use these results as effective computational procedures.
In Section~\ref{binary} we
return to the issue of unary versus
non-unary predicates, and the question of how widely applicable the
principle of maximum entropy is.
We conclude in Section~\ref{discussion} with some discussion.

\section{Technical preliminaries}\label{prelim.stat}
In this section, we give the formal definition of our language
and the random-worlds method.  The material is largely taken
>from \cite{BGHKfull}.

\subsection{The language}
\label{language}
We are interested in a formal logical language that allows
us to express both statistical information and first-order
information. We therefore define a statistical language $\Laeq$,
which is a variant of a language designed by Bacchus \citeyear{Bacchus}.
For the remainder of the paper, let $\vocab$ be
a finite first-order vocabulary, consisting of predicate and constant
symbols, and let $\X$ be a set of variables.%
\footnote{For simplicity, we assume that $\vocab$ does not contain
function symbols, since these can be defined in terms of predicates.}

Our statistical language augments standard first-order logic with a
form of statistical quantifier.  For a formula $\psi(x)$,
the term $\prop{\psi(x)}{x}$ is a {\em
proportion expression}.  It will be interpreted as a rational number
between 0 and 1, that represents the proportion of
domain elements satisfying $\psi(x)$.
We actually allow an arbitrary set of variables in the subscript
and in the formula $\psi$.
Thus, for example, $\prop{\Child(x,y)}{x}$ describes, for a fixed $y$,
the proportion of domain elements that are children of $y$;
$\prop{\Child(x,y)}{y}$ describes, for a fixed $x$, the proportion of
domain elements whose child is $x$; and $\prop{\Child(x,y)}{x,y}$
describes the proportion of pairs of domain elements that are in the
child relation.%
\footnote{Strictly speaking, these proportion expression should be
written with sets of variables in the subscript, as in
$\prop{\Child(x,y)}{\set{x,y}}$.  However, when the interpretation is
clear, we often abuse notation and drop the set delimiters.}

We also allow proportion expressions of the form
$\cprop{\psi(x)}{\theta(x)}{x}$, which we call {\em conditional
proportion expressions}. Such an expression is intended to denote
the proportion of domain elements satisfying
$\psi$ from among those elements satisfying $\theta$.
Finally, any rational number is also considered to be a proportion
expression, and the set of proportion
expressions is closed under addition and multiplication.

One important difference between our syntax and that of \cite{Bacchus}
is the use of {\em approximate equality} to compare proportion
expressions.
There are both philosophical and practical reasons why
exact comparisons can be inappropriate. Consider a statement
such as ``80\% of patients with jaundice have hepatitis''.  If this
statement appears in a knowledge base, it is almost certainly there as
a summary of a large pool of data. So it would be wrong to
interpret the value too literally, to mean that
{\em exactly\/} 80\% of all patients with jaundice have
hepatitis.  Furthermore, this interpretation would imply (among other
things) that the number of
jaundiced patients is a multiple of five! This is unlikely to be something
we intend.
We therefore use the approach described in
\cite{BGHKfull,KH92},
and compare proportion expressions using
(instead of $=$ and $\leq$) one of an infinite family of connectives
$\aeq_i$ and $\aleq_i$, for $i = 1,2,3\ldots{}$ (``$i$-approximately
equal'' or ``$i$-approximately less than or equal'').
For example, we can express the statement ``80\% of jaundiced patients
have hepatitis'' by the {\em proportion formula}
$\cprop{\Hep(x)}{\Jaun(x)}{x} \aeq_1 0.8$.
The intuition behind the semantics of approximate equality is that
each comparison should be interpreted using some small tolerance
factor to account for measurement error, sample variations, and so on.
The appropriate tolerance will differ for various
pieces of information, so our logic allows different
subscripts on the ``approximately equals'' connectives.  A formula such as
$\cprop{\Fly(x)}{\Bird(x)}{x} \aeq_1 1 \land \cprop{\Fly(x)}{\Bat(x)}{x}
\aeq_2 1$ says that both
$\cprop{\Fly(x)}{\Bird(x)}{x}$ and $\cprop{\Fly(x)}{\Bat(x)}{x}$ are
approximately $1$, but the notion of ``approximately'' may be different in
each case.
The actual choice of subscript for $\aeq$ is unimportant.  However,
it is important to use different subscripts for different approximate
comparisons unless the tolerances for the different measurements are
known to be the same.

We can now give a recursive definition of the language $\Laeq$.
\dfn\label{Laeqdfn}
The set of {\em terms} in $\Laeq$ is $\X \union \C$ where $\C$ is the
set of constant symbols in $\vocab$.
The set of {\em proportion expressions} is
the least set that
\begin{itemize}
\item[(a)]
contains the rational numbers,
\item[(b)] contains {\em proportion terms} of the form
$\prop{\psi}{X}$ and $\cprop{\psi}{\theta}{X}$ for formulas
$\psi, \theta \in \Laeq$ and a finite set of variables $X
\subseteq \X$, and
\item[(c)] is closed under addition
and multiplication.
\end{itemize}
The set of formulas in $\Laeq$ is the least set that
\begin{itemize}
\item[(a)] contains {\em atomic
formulas\/} of the form $R(t_1, \ldots, t_r)$, where $R$ is
a predicate symbol in $\vocab \union \{=\}$ of arity $r$ and
$t_1,\ldots,t_r$ are terms,
\item[(b)] contains {\em proportion formulas\/} of the
form $\zeta \aeq_i \zeta'$ and $\zeta \aleq_i \zeta'$, where
$\zeta$ and $\zeta'$ are proportion expressions
 and $i$ is a natural number, and
\item[(c)] is closed under
conjunction, negation, and
first-order quantification. \qed
\end{itemize}
\end{definition}
Note that $\Laeq$ allows the use of equality when comparing
terms, but not when comparing proportion expressions.

This definition allows
arbitrary nesting of quantifiers and proportion expressions.
As observed in \cite{Bacchus}, the subscript $x$ in a
proportion expressions binds the variable $x$ in the expression;
indeed, we can view $\prop{\cdot}{x}$ as a new type of quantification.

We now need to define the semantics of the logic.  As we shall see
below, most of the definitions are fairly straightforward. The two
features that cause problems are approximate comparisons and
conditional proportion expressions. We interpret the approximate
connective $\zeta \aeq_i \zeta'$ to mean that $\zeta$ is very close
to $\zeta'$.  More precisely, it is within some very small
tolerance factor. We formalize this using a {\em tolerance vector}
$\epsvec = \langle \epscom_1, \epscom_2, \ldots \rangle$, $\epscom_i
> 0$. Intuitively $\zeta \aeq_i \zeta'$ if the values of
$\zeta$ and $\zeta'$ are within $\epscom_i$ of each other.
Of course, one problem with this is that we generally will not know
the value of $\epscom_i$.
We postpone discussion of this issue until the next section.

Another difficulty arises when interpreting conditional proportion
expressions.
The problem is that
$\cprop{\psi}{\theta}{X}$ cannot be defined as a conditional probability
when there are no assignments to
the variables in $X$ that would satisfy $\theta$,
because we cannot
divide by zero.
When standard equality is used rather than approximate equality this
problem is easily overcome,
simply by avoiding conditional probabilities
in the semantics altogether.
Following \cite{Hal4}, we can
eliminate conditional
proportion expressions altogether by viewing a statement
such as $\cprop{\psi}{\theta}{X} = \alpha$ as an abbreviation for
$\prop{\psi \land \theta}{X} = \alpha\prop{\theta}{X}$.
Thus, we never actually form quotients of probabilities.
This
approach agrees completely with the standard interpretation of conditionals
so long as $\prop{\theta}{X} \ne 0$.
If $\prop{\theta}{X} = 0$, it enforces the convention that formulas
such as $\cprop{\psi}{\theta}{X} = \alpha$ or $\cprop{\psi}{\theta}{X} \le
\alpha$ are true
for any $\alpha$.
(Note that we do not really care much what happens in
such cases, so long as it is consistent and well-defined. This convention
represents one reasonable choice.)

We used the same approach in an earlier version of this paper \cite{GHK2}
in the context of a language that uses approximate equality.
Unfortunately, as the following example shows, this has problems.
Unlike the case for true equality, if we multiply
by $\prop{\theta}{X}$
to clear all quotients, we do not obtain an equivalent formula
even if $\prop{\theta}{X}$ is nonzero.



\xam\label{aeqproblem}
First consider the knowledge base
$\KB = (\cprop{\Fly(x)}{\Penguin(x)}{x} \aeq_1 0)$.  This says that
the number of flying penguins forms a tiny proportion of
all penguins.  However, if we interpret conditional proportions
as above and multiply out, we obtain the knowledge base
$\KBp = \prop{\Fly(x) \land
\Penguin(x)}{x} \aeq_1 0 \cdot \prop{\Penguin(x)}{x}$, which is
equivalent to
$\prop{\Fly(x) \land
     \Penguin(x)}{x} \aeq_1 0$.
$\KB'$ just says that the number of flying penguins
is small, and has lost the (possibly important) information that
the number of flying penguins is small {\em relative to the number of
penguins}.  It is quite consistent with $\KBp$
that all penguins fly (provided the total number of penguins is
small); this is not consistent with $\KB$.
Clearly, the process of multiplying out
across an approximate connective does not preserve the
intended interpretation of the formulas.
\exam

This example demonstrates
an undesirable interaction between the semantics we have
chosen for approximate equality and the process of multiplying-out to
eliminate conditional proportions.
We expect $\cprop{\psi}{\theta}{X} \aeq_1 \alpha$ to
mean that $\cprop{\psi}{\theta}{X}$ is within some
tolerance $\tau_1$ of $\alpha$. Assuming $\prop{\theta}{X} > 0$,
this is the same as saying that
$\prop{\psi \land \theta}{X}$ is within
$\tau_1\,\prop{\theta}{X}$ of $\alpha\, \prop{\theta}{X}$.
On the other hand, the expression that results by multiplying out
is $\prop{\psi \land \theta}{X} \aeq_1 \alpha \prop{\theta}{X}$.
This says that
$\prop{\psi \land \theta}{X}$ is within $\tau_1$ (not
$\tau_1\,\prop{\theta}{X}$!) of $\alpha\, \prop{\theta}{X}$.
As we saw above,
the difference between the two interpretations can be significant.

Because of this problem, we cannot treat conditional proportions as
abbreviations and instead
have added
them as
primitive expressions in the language.
Of course, we now have to give them a semantics
that avoids the problem illustrated by Example~\ref{aeqproblem}.
We would like to maintain the
conventions used
when we had equality in the language.  Namely, in worlds where
$\prop{\theta(x)}{x} \ne 0$, we want
$\cprop{\psi(x)}{\theta(x)}{x}$ to denote
the fraction of elements satisfying $\theta(x)$ that also
satisfy $\psi(x)$.  In worlds where $\prop{\theta(x)}{x} = 0$,
we want formulas of the form $\cprop{\psi(x)}{\theta(x)}{x} \aeq_i
\alpha$ or $\cprop{\psi(x)}{\theta(x)}{x} \aleq_i \alpha$ to be true.
There are a number of ways of accomplishing this.  The way we take is
perhaps not the simplest, but it introduces machinery that will
be helpful later.
The basic idea
is to make the interpretation of
$\aeq$ more explicit, so that we can eliminate conditional proportions
by multiplication and keep track of all the consequences of doing so.

We give semantics to the language $\Laeq$ by
providing a translation from formulas
in $\Laeq$ to formulas in a language $\Leq$ whose semantics is more
easily described.
The language $\Leq$ is essentially the language of
\cite{Hal4}, that uses true equality rather than approximate equality
when comparing proportion expressions.
More precisely, the definition of $\Leq$ is identical to the definition
of $\Laeq$ given in Definition~\ref{Laeqdfn}, except that:
\begin{itemize}
\item
we use $=$ and $\le$ instead of $\aeq_i$ and $\aleq_i$,
\item
we allow the set of proportion expressions to include arbitrary real
numbers (not just rational numbers),
\item
we do not allow conditional proportion expressions,
\item
we assume that $\Leq$ has a special family of variables
$\vareps_i$, for
$i = 1,2,\ldots$,
interpreted over the reals.
\end{itemize}
The variable $\vareps_i$ is used to
explicitly
interpret the approximate equality connectives $\aeq_i$ and $\aleq_i$.
Once this is done, we can safely multiply out the conditionals, as
described above.
More precisely,
every formula $\chi \in \Laeq$ can be associated with
a formula $\chi^* \in \Leq$
as follows:
\begin{itemize}
\item
every proportion formula $\zeta \aleq_i \zeta'$
in $\chi$ is (recursively) replaced by
$\zeta - \zeta' \leq \vareps_i$,
\item
every proportion formula $\zeta \aeq_i \zeta'$ in $\chi$ is
(recursively) replaced by
the conjunction $(\zeta - \zeta' \leq \vareps_i) \land
(\zeta' - \zeta \leq \vareps_i)$,
\item finally, conditional proportion expressions are eliminated
by multiplying out.
\end{itemize}
This translation allows us to embed $\Laeq$ into $\Leq$.
Thus, for the remainder of the paper, we regard $\Laeq$ as a sublanguage
of $\Leq$.
This embedding avoids the problem encountered in Example~\ref{aeqproblem},
because when we multiply to clear conditional proportions the
tolerances are explicit, and so are also multipled as appropriate.

The semantics for $\Leq$ is quite straightforward, and
is similar to that in
\cite{Hal4}.
We give semantics to $\Leq$ in terms of {\em worlds\/}, or
finite first-order models.  For any natural number $N$, let $\WN$
consist of all worlds with domain $\{1,\ldots, N\}$.
Thus, in $\WN$, we have one world for each possible interpretation
of the symbols in $\Phi$ over the domain $\{1, \ldots, N\}$.
Let $\Winf$ denote $\union_N \WN$.

Now, consider some world $\world \in \Winf$ over the domain
$D = \{1, \ldots, N \}$, some
valuation $\val : \X \rightarrow D$ for the variables
in $\X$, and some tolerance vector $\epsvec$.
We simultaneously assign to each proportion expression $\zeta$ a real
number $[\zeta]_{(\world,\val,\epsvec)}$ and to each formula $\xi$ a
truth value with respect to $(\world, \val, \epsvec)$.
Most of the clauses of the definition are completely standard, so we
omit them here.  In particular, variables are interpreted using
$\val$, the tolerance variables $\vareps_i$ are interpreted using the
tolerances $\eps_i$, the predicates and constants are interpreted
using $\world$, the Boolean connectives and the first-order
quantifiers are defined in the standard fashion, and when interpreting
proportion expressions, the real numbers, addition, multiplication,
and $\le$ are given their standard meaning. It remains to interpret
proportion terms.  Recall that we eliminate conditional proportion
terms by multiplying out, so that we need to deal only with
unconditional proportion terms. If $\zeta$ is the proportion expression
$\prop{\psi}{x_{i_1},\ldots,x_{i_k}}$ (for $i_1 < i_2 < \ldots < i_k$),
then
$$
[\zeta]_{(\world,\val,\epsvec)} = \frac{1}{|D^k|}
\Bigl|\left\{(d_1,\ldots,d_k) \in D^k\ :\
    (\world,\val[x_{i_1}/d_1,\ldots,x_{i_k}/d_k],\epsvec) \sat
         \psi\right\}\Bigr|.
$$
Thus, if $|D| = N$, the proportion expression
$\prop{\psi}{x_{i_1},\ldots,x_{i_k}}$
denotes the fraction of the $N^k$ $k$-tuples
in $D^k$ that satisfy $\psi$.
For example, $[\prop{\Child(x,y)}{x}]_{(\world,\val,\epsvec)}$ is the
fraction of domain elements $d$ that are children of $\val(y)$.


Using our embedding of $\Laeq$ into $\Leq$, we now have semantics for
$\Laeq$.
For $\chi \in \Laeq$, we say that $(\world,\val,\epsvec) \sat
\chi$ iff $(\world,\val,\epsvec) \sat \chi^*$.
It is sometimes useful in our future results to incorporate particular
values for the tolerances into the formula $\chi^*$.  Thus, let
$\chi[\epsvec]$ represent the formula that results from $\chi^*$ if
each variable $\vareps_i$ is replaced with its value according to
$\epsvec$, that is, $\eps_i$.%
\footnote{Note that some of the tolerances $\eps_i$ may
be irrational; it is for this reason that we allowed irrational
numbers in proportion expressions in $\Leq$.}

Typically we are interested in closed sentences,
that is, formulas with no free variables.
In that case, it is not hard to show that the valuation plays
no role.  Thus, if $\chi$ is closed, we write $(\world, \epsvec)
\sat \chi$ rather than $(\world, \val,\epsvec) \sat \chi$.
Finally, if $\KB$ and $\chi$ are closed formulas, we write
$\KB \sat \chi$ if $(\world,\epsvec) \sat \KB$ implies
$(\world,\epsvec) \sat \chi$.


\subsection{Degrees of belief}\label{degbelief}
As we explained in the introduction, we give semantics to degrees
of belief by considering all worlds of size $N$ to be equally likely,
conditioning on $\KB$, and then checking the probability of $\phi$ over
the resulting probability distribution.
In the previous section, we defined what it means for a sentence
$\chi$ to be satisfied in a world of size $N$ using a tolerance
vector $\epsvec$.
Given $N$ and $\epsvec$, we define $\nworlds(\chi)$ to be the number
of worlds in $\WN$ such that $(\world,\epsvec) \sat \chi$.
Since we are taking all worlds to be equally likely,
the degree of belief in $\phi$ given $\KB$
with respect to $\WN$ and $\epsvec$ is
$$
\prNw(\phi|\KB) =
  \frac{\nworlds(\phi\land\KB)}{\nworlds(\KB)}.
$$
If $\nworlds(\KB) = 0$, this degree of belief is not well-defined.

The careful reader may have noticed a potential problem with
this definition. Strictly speaking, we should write $\WN(\vocab)$
rather than $\WN$, since the set of worlds under consideration clearly depends
on the vocabulary.
Hence, the number of worlds in $\WN$
also
depends on the vocabulary.
Thus, both $\nworlds(\phi)$ and $\nworlds(\phi \land \KB)$ depend
on the choice of $\vocab$.  Fortunately, this
dependence ``cancels out'':
If $\vocab' \supset \vocab$, then there is a constant $c$ such that
for all formulas $\chi$ over the vocabulary $\Phi$,
$\nworldsvoc{\Phi'}(\chi) = c\nworldsvoc{\Phi}(\chi)$.
This result, from which it follows that
the degree of belief $\prNw(\phi|\KB)$ is independent of
our choice of vocabulary, is proved in \cite{GHK1b}.

Typically, we know neither $N$ nor $\epsvec$
exactly.  All we know is that $N$ is ``large'' and that $\epsvec$ is
``small''. Thus, we would like to take our {\em degree of belief\/} in
$\phi$ given $\KB$ to be $\lim_{\epsvec \tendsto \vec{0}}\, \lim_{N
\tendsto \infty}\, \prNw(\phi|\KB)$.
Notice that the order of the two
limits over $\epsvec$ and $N$ is important. If the limit
$\lim_{\epsvec \tendsto \vec{0}}$ appeared last, then we would gain
nothing by using approximate equality, since the result would be
equivalent to treating approximate equality as exact equality.

This definition, however, is not sufficient; the limit may not
exist. We observed above that
$\prNw(\phi|\KB)$ is not always well-defined.  In particular, it may
be the case that for certain values of $\epsvec$, $\prNw(\phi|\KB)$ is
not well-defined for arbitrarily large $N$.
In order to deal with this problem of well-definedness, we define
$\KB$ to be {\em eventually consistent} if for all sufficiently small
$\epsvec$ and sufficiently
large $N$, $\nworlds(\KB) > 0$. Among other things, eventual
consistency implies
that the $\KB$ is satisfiable in finite domains of arbitrarily
large size.
For example, a $\KB$
stating that ``there are exactly 7 domain elements'' is not
eventually consistent. For the remainder of the paper, we assume that
all knowledge bases are eventually consistent.
In practice, we expect eventual consistency to be no harder to check
than consistency.  We do not expect a knowledge base to
place bounds on the domain size, except when the bound is readily
apparent.  For those unsatisfied with this intuition, it is also possible
to find formal conditions ensuring eventual consistency.
For instance, it is possible to show that the following conditions are
sufficient to guarantee that $\KB$ is eventually consistent:
(a) $\KB$ does not use any non-unary predicates, including equality
between terms and (b) $\KB$ is consistent for {\em some\/} domain
size when all approximate comparisons are replaced by exact comparisons.
Since we concentrate on unary languages
in this paper, this result covers most cases of interest.


Even if $\KB$ is eventually consistent, the limit may not exist.
For example, it may be the case that $\prNw(\phi|\KB)$ oscillates
between $\alpha + \epscom_i$ and $\alpha - \epscom_i$ for some $i$ as
$N$ gets large.  In this case, for any particular $\epsvec$, the
limit as $N$ grows will not exist.  However, it seems as if the limit
as $\epsvec$ grows small should, in this case, be $\alpha$, since
the oscillations about $\alpha$ go to~0.  We avoid such problems by
considering the {\em lim sup} and {\em lim inf}, rather than the limit.
For any set $S \subset \reals$, the infimum of $S$, $\inf S$, is
the greatest lower bound of $S$. The {\em lim inf} of a sequence is the
limit of the infimums; that is,
$$\liminf_{N \tendsto \infty} a_N =
    \lim_{N \tendsto \infty} \inf\{a_i: i>N\}.$$
The lim inf exists for any sequence bounded from below, even if the
limit does not. The {\em lim sup\/} is defined analogously, where
$\sup S$ denotes the least upper bound of $S$. If $\lim_{N \tendsto
\infty} a_N$ does exist, then $\lim_{N \tendsto \infty} a_N =
\liminf_{N \tendsto \infty} a_N = \limsup_{N \tendsto \infty} a_N$.
Since, for any $\epsvec$, the sequence $\prNw(\phi|\KB)$ is always
bounded from above and below, the lim sup and lim inf always exist.
Thus, we do not have to worry about the problem of nonexistence for
particular values of $\epsvec$.  We can now present the final form of
our definition.

\dfn
If
$$
\lim_{\epsvec \tendsto \vec{0}}\, \liminf_{N \tendsto \infty}\,
  \prNw(\phi|\KB)
\mbox{~~and~~}
\lim_{\epsvec \tendsto \vec{0}}\, \limsup_{N \tendsto \infty}\,
   \prNw(\phi|\KB)
$$
both exist and are equal, then
the {\em degree of belief in $\phi$ given $\KB$}, written
$\priw(\phi|\KB)$, is defined as the common limit;
otherwise $\priw(\phi|\KB)$ does not exist.
\end{definition}

We close this section with a few remarks on our definition.
First note that,
even using this definition, there are many cases
where the degree of belief does not exist.
However, as some of our later examples show, in many situations the
nonexistence of a degree of belief can be understood intuitively
(for instance, see Example~\ref{esspos} and the subsequent discussion).
We could, alternatively, have taken the degree of belief to be
the interval defined by
$\lim_{\epsvec \tendsto \vec{0}}\, \liminf_{N \tendsto \infty}\,
  \prNw(\phi|\KB)$
and
$\lim_{\epsvec \tendsto \vec{0}}\, \limsup_{N \tendsto \infty}\,
   \prNw(\phi|\KB)$, provided each of them exist.
   This would have
been a perfectly reasonable choice; most of the results we state
would go through with very little change if we had taken this definition.
Our definition simplifies the exposition slightly.

Finally, we remark that it may seem unreasonable to take limits
if we know the domain size or have a bound on the domain size.
Clearly, if we know $N$ and $\epsvec$, then it seems more reasonable
to use $\prNw$ rather than $\Prinf$ as our degree of belief.
Indeed, as shown in \cite{BGHKfull}, many of the important properties
that hold for the degree of belief defined by $\Prinf$ hold
for $\prNw$, for all choices of $N$ and $\epsvec$.  The connection
to maximum entropy that we make in this paper holds only at
the limit, but because (as our proofs show) the convergence is
rapid,
the degree of belief $\Prinf(\phi|\KB)$ is typically
a very good approximation to $\prNw(\phi|\KB)$, even for moderately
large $N$  and moderately small $\epsvec$.

\section{Degrees of belief and entropy}
\label{methm}

\subsection{Introduction to maximum entropy}
\label{me.intro}

The idea of maximizing {\em entropy\/} has played an
important role in many fields, including the study of
probabilistic models for inferring degrees of belief
\cite{Jaynes57,ShannonWeaver}.
In the simplest setting, we can view entropy as a real-valued
function
on finite probability spaces.
If $\Omega$ is a finite
set and $\mu$ is a probability measure on $\Omega$, the
entropy $H(\mu)$ is defined to be
$-\sum_{\omega \in
        \Omega}\mu(\omega)\:\ln\,\mu(\omega)$
(we take $0\ln\,0 = 0$).

One standard application of entropy is the following.  Suppose we know the
space $\Omega$, but have only partial information about $\mu$, expressed
in the form of constraints.
For example, we might have a constraint such as $\mu(\omega_1) +
\mu(\omega_2) \ge 1/3$.
Although there may be many measures $\mu$ that are consistent with
what we know, the {\em principle of maximum entropy\/} suggests
that we adopt that $\mu^*$ which has the largest entropy
among all the consistent possibilities.
Using the appropriate
definitions, it can be shown that there is a sense in which
this $\mu^*$
incorporates the ``least'' additional information \cite{ShannonWeaver}.
For example, if we have no constraints on
$\mu$, then $\mu^*$ will be the
measure that assigns equal probability to all elements of $\Omega$.
Roughly speaking, $\mu^*$ assigns probabilities
as equally as possible given the constraints.


\subsection{From formulas to constraints}
\label{constraints}


Like maximum entropy, the random-worlds method is also used to
determine degrees of belief (\ie probabilities) relative to a knowledge base.
Aside from this, is there any connection between the two ideas?
Of course, there is the rather trivial observation that
random-worlds considers a uniform probability distribution
(over the set of worlds satisfying $\KB$), and it is well-known that
the uniform distribution over any set has the highest possible entropy.
But in this section we show another, entirely different and much deeper,
connection between random-worlds and the principle of maximum entropy.
This connection holds {\em provided that we restrict the knowledge base so
that it uses only unary predicates and constants.}
In this case we can consider probability distributions,
and in particular the maximum-entropy distribution, over the set of atoms.
Atoms are of course very different from possible worlds; for instance, there
are only finitely many of them (independent of the domain size $N$).
Furthermore, the maximum-entropy distributions we consider will typically
not be uniform. Nevertheless, maximum entropy in this new space can
tell us a lot about the degrees of belief defined by random worlds.
In particular, this connection will allow us to use
maximum entropy as a tool for computing degrees of belief.
We believe that the restriction to unary predicates is necessary for
the connection we are about to make.
Indeed, as long as the knowledge base makes use of a binary
predicate symbol
(or unary function symbol),
we suspect that there is no useful
connection between the two approaches
at all;
see Section~\ref{binary} for some discussion.

Let $\Lunaeq$ be the sublanguage of $\Laeq$ where only unary
predicate symbols and constant symbols appear in formulas; in particular,
we assume that equality
between terms
does not occur in formulas in $\Lunaeq$.%
\footnote{We remark that many of our results can be extended to
the case where the $\KB$ mentions equality, but the extra
complexity obscures many of the essential ideas.}
(Recall that in $\Laeq$, we allow equality between terms, but disallow
equality between proportion expressions.)
Let $\Luneq$ be the corresponding sublanguage of $\Leq$.
In this subsection, we show that
the expressive power of a knowledge base $\KB$ in the language
$\Lunaeq$ is quite limited.  In fact, such a $\KB$ can essentially
only place constraints on the proportions of the atoms.
If we then think of these as constraints on the
``probabilities of the atoms'', then
we have the ingredients necessary to apply
maximum entropy. In Section~\ref{concent} we show
that there is a strong connection
between the maximum-entropy distribution found this way and
the degree of belief generated by random-worlds method.

To see what constraints a formula places on the probabilities of
atoms, it is useful to convert the formula to a certain canonical
form.  As a first step to doing this, we formalize the
definition of atom given in the introduction.
Let
$\P = \{P_1, \ldots, P_k\}$ consist of the
unary predicate symbols in the vocabulary $\vocab$.
\dfn
An {\em atom (over $\P$)\/} is
conjunction of the form $P'_1(x) \land \ldots \land P'_k(x)$, where each
$P'_i$ is either $P_i$ or $\neg P_i$.
Since the variable $x$ is irrelevant to our concerns, we typically
suppress it and describe an atom as a conjunction of the form
$P'_1 \land \ldots \land P'_k$.
\edfn
Note that there are $2^{|\P|} = 2^k$ atoms over $\P$ and that they
are mutually exclusive and exhaustive. Throughout this paper,
we use $K$ to denote $2^k$
and
$A_1, \ldots, A_K$ to denote the atoms
over $\P$, listed in some fixed order.
\xam\label{four.atoms}
There are $K = 4$ atoms over $\P = \{P_1,P_2\}$:
$A_1=P_1\land P_2$, $A_2=P_1\land\neg P_2$,
$A_3=\neg P_1\land P_2$, $A_4=\neg P_1\land \neg P_2$.
\exam

The {\em atomic proportion terms\/}
$\prop{A_1(x)}{x},\ldots{},\prop{A_K(x)}{x}$
will play a significant role in our technical development.
It turns out that $\Lunaeq$ is a rather weak language: a formula
$\KB \in \Lunaeq$ does little more than constrain the proportion
of the atoms. In other words, for any such $\KB$ we can find an
equivalent formula in which the only proportion expressions are
these unconditional proportions of atoms.
The more complex syntactic machinery in
$\Lunaeq$---proportions over tuples, first-order quantification, nested
proportions, and conditional proportions---does not add expressive
power. (It does add convenience, however; knowledge can often be
expressed far more succinctly if the full power of the language is
used.)

Given any $\KB$, the first step towards applying maximum entropy is to use
$\Lunaeq$'s lack of expressivity and replace all
proportion terms by atomic proportion terms.
It is also useful to make various
other simplifications to $\KB$ that will help us in Section~\ref{compute}.
We combine these steps and require that $\KB$ be transformed into
a special {\em canonical form}
which we now describe.

\dfn
An {\em atomic term $t$ over $\P$\/} is a polynomial over terms of the
form $\prop{A(x)}{x}$, where $A$ is an atom over $\P$.
Such an atomic term $t$ is {\em positive \/} if every coefficient
of the polynomial $t$ is positive.
\edfn

\dfn\label{canonical.defn}
A (closed) sentence $\chi \in \Luneq$ is in {\em canonical form\/} if
it is a disjunction of conjunctions, where each conjunct is one of the
following:
\begin{itemize}
\item $t' = 0$, $(t' > 0 \land t \le t'\vareps_i)$, or
$(t' > 0 \land \neg(t \le t'\vareps_i))$, where $t$ and $t'$ are atomic
terms and $t'$ is positive,
\item $\exists x\, A_i(x)$ or $\neg\exists x\, A_i(x)$
 some atom $A_i$, or
\item
$A_i(c)$ for
some atom $A_i$ and some constant $c$. %But NOT the negations of such.
\end{itemize}
Furthermore, a disjunct cannot contain both
$A_i(c)$ and $A_j(c)$ for $i \neq j$ as conjuncts, nor can it contain
both $A_i(c)$ and $\neg \exists x\, A_i(x)$.
(Note that these last conditions are simply minimal consistency requirements.)
\edfn

\thm\label{flattening}
Every formula in $\Luneq$
is equivalent to a formula in canonical form.
Moreover, there is an effective procedure that, given a formula
$\xi \in \Luneq$, constructs an equivalent formula $\canxi$ in
canonical form.
\ethm
The proof of this theorem, and of all theorems in this paper, can be
found in the appendix.

We remark that the length of the formula $\canxi$ is typically
exponential in the length of $\xi$.  Such a blowup seems inherent in
any scheme defined in terms of atoms.


Theorem~\ref{flattening} is a generalization of Claim~5.7.1
in~\cite{Hal4}.  It, in turn, is a generalization of a well-known
result
which says that any first-order formula with only unary predicates
is equivalent to one with only depth-one quantifier nesting.
Roughly speaking, this is because for
a quantified formula such as $\exists x\, \xi'$, subformulas
talking about a variable $y$ other than $x$ can be moved outside
the scope of the quantifier. This is possible because no literal
subformula can talk about $x$ and $y$ together.
Our proof uses the same idea and extends it to proportion statements.
In particular, it shows that for any $\xi \in \Lunaeq$ there
is an equivalent $\hat{\xi}$ which has no nested
quantifiers or nested proportions.

Notice, however, that such a result does not hold once we allow even
a single binary predicate in the language.
For example, the formula
$\forall y\, \exists x\, R(x,y)$ clearly needs nested quantification because
$R(x,y)$ talks about both $x$ and $y$ and so must remain within the
scope of both quantifiers. With binary predicates,
each additional depth of nesting really does add expressive power.
This shows that there can be no ``canonical form'' theorem quite like
Theorem~\ref{flattening} for richer languages. This issue is one of the main
reasons why we restrict the $\KB$ to a unary language in this paper.
(See Section~\ref{binary} for further discussion.)

Given any formula in  canonical form we can immediately derive from
it, in a syntactic manner, a set of constraints on the possible
proportions of atoms.
\dfn\label{constraints.defn}
Let $\KB$ be in canonical form. We construct
a formula $\constraints(\KB)$ in the language of real closed fields
(\ie over the vocabulary $\{0,1,+,\times\}$)
as follows, where
$u_1, \ldots, u_K$ are
fresh
variables (distinct from the tolerance variables
$\vareps_j$):
\begin{itemize}
\item
we replace each occurrence of the formula $A_i(c)$ by
$u_i > 0$,
\item
we replace each occurrence of $\exists x\, A_i(x)$ by $\ucom_i > 0$ and
replace each occurrence of $\neg \exists x\, A_i(x)$ by $\ucom_i = 0$,
\item we replace each occurrence of
$\prop{A_i(x)}{x}$ by $\ucom_i$. \ \ \bbox
\end{itemize}
\end{definition}
Notice that $\constraints(\KB)$ has two types of variables: the new
variables $u_i$ that we just introduced, and the tolerance variables
$\vareps_i$.
In order to eliminate the dependence on the latter, we often consider
the formula $\constraints(\KB[\epsvec])$ for some tolerance vector
$\epsvec$.
\dfn
Given a formula $\gamma$ over the variables
$u_1, \ldots, u_K$,
let $\Sol[\gamma]$ be the set of vectors in $\propspace = \{\vec{u}
\in [0,1]^K: \sum_i^K u_i = 1\}$ satisfying $\gamma$.
Formally, if $(a_1, \ldots, a_K) \in \propspace$, then
$(a_1, \ldots, a_K) \in \Sol[\gamma]$ iff $(\IR,V) \sat \gamma$, where
$V$ is a valuation such that $V(u_i) = a_i$.
\edfn
\dfn
The {\em solution space of $\KB$ given $\epsvec$}, denoted
$\SS{\epsvec}{\KB}$, is defined to be the closure of
$\Sol[\constraints(\KB[\epsvec])]$.%
\footnote{Recall that the {\em closure\/} of a set $X \subseteq \IR^K$
consists of all $K$-tuples that are the limit of a sequence of
$K$-tuples in $X$.}
\edfn
If $\KB$ is not in canonical form, we define $\constraints(\KB)$ and
$\SS{\epsvec}{\KB}$ to be $\constraints(\canKB)$ and
$\SS{\epsvec}{\canKB}$, respectively, where $\canKB$ is the formula in
canonical form equivalent to $\KB$ obtained by the procedure appearing
in the proof of Theorem~\ref{flattening}.

\xam
Let $\P$ be $\{P_1, P_2\}$, with the atoms ordered as in
Example~\ref{four.atoms}. Consider
$$\KB = \forall x \, P_1(x) \land 3 \|P_1(x) \land P_2(x)\|_x \aleq_i 1.$$
The canonical formula $\canKB$ equivalent to $\KB$ is:%
\footnote{Note that here we are viewing $\KB$ as a formula in $\Leq$,
under the translation defined earlier; we do this throughout the paper
without further comment.}
$$    \neg\exists x\, A_3(x) \land
             \neg\exists x\, A_4(x) \land
             3\prop{A_1(x)}{x} - 1 \leq \vareps_i. $$
As expected, $\canKB$ constrains both
$\prop{A_3(x)}{x}$ and $\prop{A_4(x)}{x}$ (\ie $u_3$ and $u_4$)
to be~0.  We also see that $\prop{A_1(x)}{x}$ (\ie $\ucom_1$) is
(approximately) at most $1/3$. Therefore:
$$\SS{\epsvec}{\KB} = \set{( \ucom_1, \ldots, \ucom_4 ) \in \Delta^4:
\ucom_1 \le 1/3 + \eps_i/3, \ucom_3 = \ucom_4 = 0}.~~~\bbox$$
\end{example}

\subsection{The concentration phenomenon}
\label{concent}

With every world $\world \in \Winf$, we can associate a particular
tuple $(\ucom_1, \ldots{}, \ucom_K)$, where $\ucom_i$ is the
fraction of the domain satisfying atom $A_i$ in $\world$:
\dfn
Given a world $\world \in \Winf$, we define $\vecof{\world} \in
\propspace$ to be
$$(\prop{A_1(x)}{x},\prop{A_2(x)}{x},\ldots{},\prop{A_K(x)}{x})$$
where the values of the proportions are interpreted over $\world$.
We say that the vector $\vecof{\world}$ is the {\em point\/}
associated with $\world$.
\edfn

We define the {\em entropy\/} of any model $\world$ to be the entropy
of $\vecof{\world}$;
that is, if $\vecof{\world} = (u_1, \ldots, u_K)$, then the
entropy of $\world$ is
$H(u_1,\ldots,u_K)$.
As we are about to show, the entropy of $\uvec$ turns out to be a very
good asymptotic indicator of how many worlds $\world$ there are
such that $\pi(\world) = \uvec$.
In fact, there are so many more worlds near points of high entropy
that we can ignore all the other points when computing degrees of belief.
This {\em concentration\/} phenomenon, as Jaynes \citeyear{Jaynes1}
has called it,
is essentially the content of the next lemma and
justifies our interest in the  maximum-entropy point(s) of
$\SS{\epsvec}{\KB}$.




For any $\S \subseteq \propspace$ let $\nwrldPnt{\S}(\KB)$ denote the
number of worlds $\world$ of size $N$ such that $(\world,\epsvec) \sat
\KB$ and such that $\vecof{\world} \in \S$; for any
$\uvec \in \propspace$ let
$\nwrldPnt{\uvec}(\KB)$ abbreviate $\nwrldPnt{\set{\uvec}}(\KB)$.
Of course $\nwrldPnt{\uvec}(\KB)$ is necessarily zero unless all components of
$\uvec$ are multiples of $1/N$. However, if there are any models
associated with $\uvec$ at all, we can estimate their number quite
accurately
using the entropy function:

\lem\label{countworlds}
There exist some function $h: \IN \rightarrow \IN$ and two strictly positive
polynomial functions
$f,g : \IN \rightarrow \IR$
such that, for $\KB \in \Lunaeq$ and $\uvec \in \propspace$,
if $\nwrldPnt{\uvec}(\KB) \ne 0$, then
\begin{displaymath}
(h(N)/f(N)) e^{N H(\uvec)} \leq
       \nwrldPnt{\uvec}(\KB) \leq
             h(N) g(N) e^{N H(\uvec)}.
\end{displaymath}
\elem

Of course, it follows from the lemma that tuples whose entropy
is near maximum have overwhelmingly more worlds associated with
them than tuples whose entropy is further from maximum.  This is
essentially the concentration phenomenon.

Lemma~\ref{countworlds} is actually fairly easy to prove.
The following simple example illustrates the main idea.

\xam\label{countworlds.xam}
Suppose $\vocab = \{P\}$ and $\KB = \true.$
We have
 $$\propspace = \Delta^2 = \set{(\ucom_1,1-\ucom_1): \;\;\; 0 \leq \ucom_1
\leq 1},$$
where the atoms are $A_1 = P$ and $A_2 = \neg P$.
For any $N$, partition the worlds in $\WN$ according to the point to
which they correspond.  For example, the graph in
Figure~\ref{concfour} shows us the partition of $\W_4$.
\begin{figure}

\centerline{\psfig{figure=concent1.idraw,height=3in}}
\caption{Partition of $\W_4$ according to $\vecof{\world}$.}
\label{concfour}
\end{figure}
In general, consider some point $\uvec = (r/N, (N-r)/N)$.
The number of worlds corresponding to $\uvec$ is simply the number
of ways of choosing the denotation of $P$.  We need to choose
which $r$ elements satisfy $P$; hence, the
number of such worlds is $\binco{N}{r} = \frac{N!}{r!
(N-r)!}$.  Figure~\ref{concr} shows the qualitative behavior of
this function for large values of $N$.  It is easy to see the
asymptotic concentration around $\uvec = (0.5,0.5)$.
\begin{figure}[htb]
\centerline{\psfig{figure=graph.ps,height=3in}}
\caption{Concentration phenomenon for worlds of size $N$.}
\label{concr}
\end{figure}

We can estimate the factorials appearing in this expression using
Stirling's approximation, which asserts that the factorial $m!$ is
approximately $m^m = e^{m \ln m}$.
So, after substituting for the three factorials, we can estimate
$\binco{N}{r}$ as $e^{N\log N -({r\log r + (N-r) \log (N-r)})}$,
which reduces to $e^{N H(\uvec)}$.
The entropy term in the general case
arises from the use of Stirling's approximation in an analogous way.
(A more careful estimate is done in the proof of Lemma~\ref{countworlds}
in the appendix.)
\exam

Because of the exponential dependence on $N$ times the entropy, the
number of worlds
associated with points of high entropy swamp all
other worlds as $N$ grows large.  This concentration phenomenon,
well-known in the field of statistical physics, forms the
basis for our main result in this section.
It asserts that it is possible to compute degrees of belief according to
random worlds while ignoring all but those worlds whose entropy is near
maximum. The next theorem essentially formalizes this phenomenon.

\thm\label{thm.concent.general}
For all sufficiently small $\epsvec$, the following is true.
Let $\mepts$ be the points with greatest entropy in
$\SSc{\epsvec}{\KB}$ and let $\OS \subseteq \IR^K$ be any open set containing
$\mepts$. Then  for all $\theta \in \Laeq$ and for ${\lim^*} \in
\set{\limsup, \liminf}$ we have
$$
{\lim_{N \rightarrow \infty}}^{\!\!\!*}\:
                                          \PrN^{\epsvec}(\theta|\KB) =
  %\lim_{\epsvec \rarrow \vec{0}}\,
{\lim_{N \rarrow \infty}}^{\!\!\!*}\:
\frac{\nwrldPnt{\OS}(\theta \land \KB)}{\nwrldPnt{\OS}(\KB)}.$$
\ethm

We remark that this is quite a difficult theorem. We have discussed
why Lemma~\ref{countworlds} lets us look at {\em models of $\KB$\/}
whose entropy is (near) maximum.
But the theorem tells us to look at the maximum-entropy
points of $\SSc{\epsvec}{\KB}$, which we defined using a (so far
unmotivated) syntactic procedure applied to $\KB$.
It seems reasonable to expect that $\SSc{\epsvec}{\KB}$ should tell
us {\em
something\/} about models of $\KB$. But making this connection precise,
and in particular showing how the maximum-entropy points of
$\SSc{\epsvec}{\KB}$ relate to models of $\KB$ with near-maximum entropy,
is difficult. However, we
defer all details of the proof of that result to the appendix.

In general, Theorem~\ref{thm.concent.general}
may seem to be of limited usefulness: knowing
that we only have to look at worlds near the maximum-entropy point
does not substantially reduce the number of worlds we need to
consider.  (Indeed, the whole point of the concentration phenomenon is
that almost all worlds have high entropy.)
Nevertheless, as the rest of this paper shows, this result can be quite
useful
when combined with the following two results.
The first of these says
that if all the worlds near the maximum-entropy
points have a certain property, then we should have  degree of belief 1
that this property is true.

\cor\label{thm.concent.eqone}
For all sufficiently small $\epsvec$, the following is true.
Let $\mepts$ be the points with greatest entropy in
$\SSc{\epsvec}{\KB}$,
let $\OS \subseteq \IR^K$ be an open set containing $\mepts$,
and let $\theta[\OS] \in \Leq$
be an assertion
that holds for every world $\world$ such that $\vecof{\world} \in \OS$.  Then
$$ \Prinf^\epsvec(\theta[\OS] | \KB) = 1.$$
\ecor

\xam
For the knowledge base $\true$ in Example~\ref{countworlds.xam},
it is easy to see that the
maximum-entropy point is $(0.5,0.5)$.  Fix some arbitrary  $\epsilon > 0$.
Clearly, there is some open set $\OS$ around this point such that the
assertion $\theta = \prop{P(x)}{x} \in [0.5-\epsilon,0.5+\epsilon]$ holds
for every world in $\OS$.  Therefore, we can conclude that
$$ \Prinfeps \left( \prop{P(x)}{x} \in [0.5-\epsilon,0.5+\epsilon]
  \left| \true \right )  = 1. \right.\ \ \bbox$$
\end{example}

As we show in \cite{BGHKfull}, formulas $\theta$ with degree of belief~1
can essentially be treated just like other knowledge in $\KB$. That is,
the degrees of belief relative
to $\KB$ and $\KB \land \theta$ will be identical
(even if  $\KB$ and $\KB \land \theta$ are not
logically equivalent).
More formally:

\begin{theorem}{\rm \cite{BGHKfull}}
\label{cumulativity}
If $\Prinf^\epsvec(\theta|\KB) = 1$
and
${\lim^*} \in \set{\limsup, \liminf}$, then for any formula $\phi$:
$$
{\lim_{N \rightarrow \infty}}^{\!\!\!*}\:
          \PrN^{\epsvec}(\phi|\KB) =
{\lim_{N \rightarrow \infty}}^{\!\!\!*}\:
          \PrN^{\epsvec}(\phi|\KB \land \theta).$$
\ethm
\prf
For completeness, we repeat the proof from \cite{BGHKfull} here.
Basic probabilistic reasoning shows that, for any $N$ and $\epsvec$:
$$\PrN^\epsvec(\phi|\KB)
     =  \PrN^\epsvec(\phi|KB\land\theta)\,
        \PrN^\epsvec(\theta|\KB)\; +
        \PrN^\epsvec(\phi|KB\land\neg\theta)\;
        \PrN^\epsvec(\neg\theta|\KB).$$
By assumption, $\PrN^\epsvec(\theta|\KB)$ tends to 1 when we take limits,
so the first term tends to $\PrN^\epsvec(\phi|\KB\land\theta)$. On the
other hand, $\PrN^\epsvec(\neg\theta|\KB)$ has limit 0. Because
$\PrN^\epsvec(\phi|KB\land\neg\theta)$ is bounded, we conclude that
the second product also tends to 0. The result follows.
\eprf

As we shall see in the next section, the combination of
Corollary~\ref{thm.concent.eqone} and Theorem~\ref{cumulativity} is
quite powerful.

\section{Computing degrees of belief}
\label{compute}
Although the concentration phenomenon is interesting,
its application
to actually computing degrees of belief may not be obvious.
Since we know that almost all worlds will have high entropy, a
direct application of Theorem~\ref{thm.concent.general} does not
substantially reduce the number of worlds we must consider.
Yet, as we show in this section,
the concentration
theorem can form the basis of a practical technique for computing degrees
of belief  in many cases.  We begin in
Section~\ref{maxent.restrictions} by presenting the intuitions underlying
this technique.
In Section~\ref{one.individual} we
build on these intuitions by presenting results for a
restricted class of formulas: those queries which are quantifier-free
formulas over a unary language with a single constant
symbol. In spite of this restriction,
many of the issues arising in the general case
can be seen here.
Moreover, as we show in Section~\ref{ppl}, this restricted sublanguage
is rich enough to allow us to embed two well-known propositional
approaches that make use of maximum entropy:
Nilsson's {\em probabilistic logic\/} \cite{Nil}
and the maximum-entropy extension of $\epsilon$-semantics
\cite{Geffner:Framework.Reasoning.With.Defaults} due to
Goldszmidt, Morris, Pearl \citeyear{GMP} (see also \cite{GMPfull}).
In Section~\ref{extending.queries}, we consider whether
the results for the restricted language can be extended.  We
show that they can, but several difficult and subtle issues arise.

\subsection{The general strategy}
\label{maxent.restrictions}

Although the random-worlds method is defined by counting worlds,
we can sometimes find more direct ways to calculate the degrees
of belief it yields.
In \cite{BGHKfull}
we present a number of such techniques, most of which apply only in
very special cases.
One of the simplest and most intuitive
is the following
version of what philosophers have termed {\em direct inference}
\cite{Reichenbach:Theory.Of.Probability}.
Suppose that all we know about
an individual $c$ is some assertion $\psi(c)$; in other words,
$\KB$ has the form $\psi(c) \land \KB'$, and the constant $c$ does
not appear in $\KB'$.
Also suppose that $\KB$, together with a particular
tolerance $\epsvec$,
implies that
$\cprop{\phi(x)}{\psi(x)}{x}$
is in some interval $[\alpha,\beta]$.
It seems reasonable to argue that $c$ is should be treated as
a ``typical'' element satisfying $\psi(x)$, because by assumption
$\KB$ contains no information suggesting otherwise.
Therefore, we might hope to use the statistics directly, and conclude
that $\Prinf^\epsvec(\phi(c) | \KB) \in [\alpha,\beta].$
This is indeed the case, as the following theorem shows.

\begin{theorem}{\rm \cite{BGHKfull}}
\label{direct}
Let $\KB$ be a knowledge base of the form $\KBconst(\ctuple) \land
\KBprop$,
and assume that for all sufficiently small tolerance vectors $\epsvec$,
$$
\KB[\epsvec] \sat \cprop{\phi(\xtuple)}{\psi(\xtuple)}{\xtuple} \in
  [\alpha,\beta].
$$
If no constant in $\ctuple$ appears in $\KBprop$, in $\phi(\xtuple)$, or
in $\psi(\xtuple)$, then $\priw(\phi(\ctuple)|\KB) \in [\alpha,\beta]$
(if the degree of belief exists at all).
\ethm

This result, in combination with the results of the previous section,
provides us with a very powerful tool.
Roughly speaking,
we propose to use the following strategy:
The basic concentration phenomenon says that most worlds
are very similar in a certain sense.
As shown in Corollary~\ref{thm.concent.eqone}, we can use this to find some
assertions that are ``almost certainly'' true (\ie with degree of belief
1) even if they are not logically implied by $\KB$.
Theorem~\ref{cumulativity} then tells us that we can treat these new
assertions as if they are in fact known with certainty.
When these new assertions state statistical ``knowledge'', they can
vastly increase our opportunities to apply direct inference.
The following example illustrates this idea.

\xam\label{simple.computing}
Consider a very simple knowledge base over a vocabulary containing
the single unary predicate $\{P\}$:
$$
 \KB = (\prop{P(x)}{x} \aleq_1 0.3).
$$
There are two atoms $A_1$ and $A_2$ over $\P$, with $A_1 = P$ and
$A_2 = \neg P$.  The solution space of this $\KB$ given $\epsvec$ is
clearly
$$ \SSc{\epsvec}{\KB} =
  \{(u_1,u_2) \in \Delta^2 \ :\ u_1 \leq 0.3 + \eps_1\}.$$
A straightforward computation shows that, for $\eps_1 < 0.2$, this
has a unique  maximum-entropy point $\mept = (0.3 + \eps_1, 0.7 - \eps_1)$.

Now, consider the query $P(c)$.  For all $\epsilon > 0$, let
$\theta[\epsilon]$ be the formula $\prop{P(x)}{x} \in
[(0.3+\eps_1)-\epsilon,(0.3+\eps_1)+\epsilon]$. This satisfies the
condition of Corollary~\ref{thm.concent.eqone}, so it follows that
$ \Prinf^\epsvec(\theta[\epsilon] | \KB) = 1.$
Using Theorem~\ref{cumulativity}, we know that for
$\lim^* \in \{\liminf,\limsup\}$,
$$
\limNstar \PrNeps(P(c) | \KB) = \limNstar \PrNeps(P(c) | \KB \land
  \theta[\epsilon]).
$$
But now we can use direct inference. (Note that
here, our ``knowledge'' about $c$ is vacuous, \ie ``$\true(c)$''.)
We conclude that, if there is any limit at all, then necessarily
$$ \Prinfeps(P(c) | \KB \land \theta[\epsilon]) \in
  [(0.3+\eps_1)-\epsilon,(0.3+\eps_1)+\epsilon].$$
So, for all $\epsilon > 0$,
$$ \Prinfeps(P(c)|\KB) \in [(0.3+\eps_1)-\epsilon,(0.3+\eps_1)+\epsilon].$$
Since this is true for all $\epsilon$, the only possible value for
 $\Prinfeps(P(c)|\KB)$ is
$0.3+\eps_1$, which is the value of $u_1$
(\ie $\prop{P(x)}{x}$)
{\em at\/} the maximum-entropy point. Note that it
is also clear what
happens as $\epsvec$ tends to $\zerovec$:
$\Prinf(P(c)|\KB)$ is $0.3$.
\exam

This example demonstrates the main steps of one possible strategy
for computing degrees of belief.
First the maximum-entropy points of the space
$\SSc{\epsvec}{\KB}$ are computed as a function of $\epsvec$.  Then,
these are used to compute $\Prinfeps(\phi|\KB)$, assuming the limit
exists (if not, the $\limsup$ and $\liminf$ of $\PrN(\phi|\KB)$ are
computed instead).  Finally, we compute the limit of this probability
as $\epsvec$ goes to zero.


Unfortunately, this strategy has a serious potential problem.
We clearly cannot compute $\Prinfeps(\phi|\KB)$ separately for each of
the infinitely many tolerance vectors $\epsvec$ and then take the limit
as $\epsvec$ goes to 0.  We might hope to
compute
this probability as an explicit function of $\epsvec$, and then compute
the limit.  For instance, in Example~\ref{simple.computing}
$\Prinfeps(P(c)|\KB)$ was found to be $0.3+\eps_1$, and so it
is easy to see what happens as $\eps_1 \tendsto 0$.
But there is no reason to believe that $\Prinfeps(\phi|\KB)$
is, in general, an easily characterizable function of $\epsvec$. If it
is not, then
computing the limit as $\epsvec$ goes to 0 can be difficult or impossible.
We would like to find a way to avoid this explicit limiting process
altogether. It turns out that this is indeed possible in some
circumstances. The main requirement is that
the maximum-entropy points of
$\SSc{\epsvec}{\KB}$ converge to the maximum-entropy points of
$\SSzero{\KB}$.
(For future reference, notice that $\SSzero{\KB}$ is
the closure of the solution space of the constraints
obtained from
$\KB$ by replacing all occurrences of $\aeq_i$ by $=$ and all
occurrences of $\aleq_i$ by $\le$.) In many such cases, we can compute
$\Prinf(\phi|\KB)$ directly in terms of the maximum-entropy points of
$\SSzero{\KB}$, without taking limits at all.

As the following example shows, this type of continuity
does not hold in general:
the maximum-entropy points of $\SS{\epsvec}{\KB}$ do not necessarily
converge to those of $\SS{\zerovec}{\KB}$.
\xam\label{esspos}
Consider the knowledge base
$$\KB = (\prop{P(x)}{x} \aeq_1 0.3 \lor \prop{P(x)}{x} \aeq_2
0.4) \land \prop{P(x)}{x} \not \aeq_3 0.4 \ .$$
It is easy to see that $\SSczero{\KB}$ is just $\set{(0.3,0.7)}$:
The point $(0.4,0.6)$ is disallowed by the second conjunct.
Now, consider $\SS{\epsvec}{\KB}$ for $\epsvec > \zerovec$.
If $\eps_2 \leq \eps_3$, then $\SSc{\epsvec}{\KB}$ indeed does not
contain points where $u_1$ is near $0.4$; the maximum-entropy point of
this space is easily seen to be $0.3 + \eps_1$.  However, if $\eps_2 >
\eps_3$ then there will be points in $\SSc{\epsvec}{\KB}$ where $u_1$
is around $0.4$; for instance, those where
$0.4 + \eps_3 < u_1 \leq 0.4 + \eps_2$. %there are also others.
Since these points have a higher entropy than the points in the
vicinity of $0.3$, the former will dominate.  Thus, the set of
maximum-entropy points of $\SSc{\epsvec}{\KB}$ does not converge to a single
well-defined set. What it converges to (if anything) depends on how
$\epsvec$ goes to $\zerovec$.  This nonconvergence has consequences for
degrees of belief. It is not hard to show
$\Prinfeps(P(c)|\KB)$ can be either $0.3 + \eps_1$ or $0.4+ \eps_2$,
depending on the precise relationship between $\eps_1$, $\eps_2$, and
$\eps_3$.  It follows that $\Prinf(P(c)|\KB)$ does not exist.
\exam
We say that a degree of belief $\Prinf(\phi|\KB)$ is not {\em
robust\/} if the behavior of $\Prinfeps(\phi|\KB)$ (or of $\liminf
\PrNeps(\phi|KB)$ and $\limsup \PrNeps(\phi|KB)$) as $\epsvec$ goes to
$\zerovec$ depends on {\em how\/} $\epsvec$ goes to $\zerovec$.
In other worlds, nonrobustness describes situations when
$\Prinf(\phi|\KB)$ does not exist because of sensitivity to the exact
choice of tolerances.
We shall see a number of other examples of nonrobustness in later
sections.

It might seem that the notion of robustness is an artifact of our approach.
In particular, it seems to depend on the fact that our language has the
expressive power to say that the two tolerances represent a different
degree of approximation, simply by using different subscripts ($\aeq_2$
vs.~$\aeq_3$ in the example).  In an approach to representing
approximate equality that does not make these distinctions,
we are bound to get the
answer $0.3$ in the example above, since then $\prop{P(x)}{x} \not
\aeq_3 0.4$ really would be the negation of $\prop{P(x)}{x} \aeq_2 0.4$.
We would argue that the answer
$0.3$ is not as reasonable as it might at first seem.  Suppose one of
the two different instances of $0.4$ in the previous example had been
slightly different; for example, suppose we had used $0.399$ rather than
$0.4$ in the first of them.
In this case, the second conjunct is essentially vacuous, and can be
ignored.  The maximum-entropy point in $\SSzero{\KB}$ is now $0.399$,
and we indeed derive a degree of belief of $0.399$ in $P(c)$.
Thus, arbitrarily small changes to the numbers in the original
knowledge base can cause large changes in our degrees of belief.  But
these numbers are almost always the result of approximate observations;
this is reflected by our decision to use approximate
equality rather than equality when referring to them.   It does
not seem reasonable to base actions on a degree of belief that can change
so drastically in the face of small changes in the measurement of data.
Note that, if we know that the two instances of $0.4$ do, in fact,
denote exactly the same number, we can represent this by using the same
approximate equality connective in both disjuncts.  In this case, it is
easy to see that we do get the answer $0.3$.

A close look at the example shows that the nonrobustness arises
because of the negated proportion
expression $\prop{P(x)}{x}
\not \aeq_3 0.4$. Indeed, we can show that if we start with a $\KB$ in
canonical form that does not contain negated proportion expressions
then, in a precise sense, the set of maximum-entropy
points of $\SSc{\epsvec}{\KB}$ necessarily converges to the set of
maximum-entropy points of  $\SSczero{\KB}$.  An argument can be made that we
should eliminate negated proportion expressions from the language
altogether.  It is one thing to argue that sometimes
we have statistical values whose accuracy we are unsure about, so that
we want to make logical assertions less stringent than exact numerical
equality. It is harder to think of cases in which the opposite
is true, and {all\/} we know is that some statistic is
``not even approximately'' equal to some value.
However, we do not eliminate negated proportion expressions from the language,
since without them we would not be able to prove an analogue
to Theorem~\ref{flattening}. (They arise when we try to flatten nested
proportion expressions, for example.)
Instead, we have identified a weaker condition that is sufficient to
prevent problems such as that seen in Example~\ref{esspos}.
{\em Essential positivity\/} simply tests that negations are not
interacting with the maximum-entropy computation in a harmful way.

\dfn\label{essposdef}
Let $\constpos(\KB[\zerovec])$ be the result of replacing each strict
inequality in $\constraints(\KB[\zerovec])$ with its weakened version.  More
formally, we replace each subformula of the form $t < 0$ with
$t \leq 0$, and each subformula of the form $t > 0$ with
$t \geq 0$.  (Recall that these are the only constraints
possible in $\constraints(\KB[\zerovec])$, since all tolerance
variables $\vareps_i$ are assigned 0.)
Let $\SSpos{\KB}$ be $\overline{\Sol[\constpos(\KB[\zerovec])]}$,
where we use $\overline{X}$ to denote the closure of $X$.
We say that $\KB$ is
{\em essentially positive\/} if the sets $\SSpos{\KB}$ and
$\SSzero{\KB}$ have the same maximum-entropy points.
\edfn

\xam
Consider again the knowledge base $\KB$ from Example~\ref{esspos}.
The constraint formula $\constraints(\KB[\zerovec])$ is (after
simplification):
$$
(u_1 = 0.3 \lor u_1 = 0.4) \land (u_1 < 0.4 \lor u_1 > 0.4).
$$
Its ``weakened'' version is $\constpos(\KB[\zerovec])$:
$$
(u_1 = 0.3 \lor u_1 = 0.4) \land (u_1 \leq 0.4 \lor u_1 \geq 0.4),
$$
which is clearly equivalent to $u_1 = 0.3 \lor u_1 = 0.4$.
Thus, $\SSzero{\KB} = \{(u_1,u_2) \in \Delta^2 \ :\ u_1 \leq 0.3\}$
whereas $\SSpos{\KB} = \SSczero{\KB} \union \{(0.4,0.6)\}$.
Since the two spaces have different maximum-entropy points, the
knowledge base $\KB$ is not essentially positive.
\exam
As the following result shows,
essential positivity suffices to guarantee that the maximum-entropy
points of $\SSc{\epsvec}{\KB}$ converge to those of $\SSczero{\KB}$.

\pro\label{maxent.close}
Assume that $\KB$ is essentially positive and let $\mepts$ be the set
of maximum-entropy points of $\SSczero{\KB}$ (and thus also of
$\SSpos{\KB}$).  Then for all $\epsilon > 0$ and all sufficiently
small tolerance vectors $\epsvec$ (where ``sufficiently
small'' may depend on $\epsilon$), every maximum-entropy point of
$\SSc{\epsvec}{\KB}$ is within $\epsilon$ of some maximum-entropy point
in $\mepts$.
\epro

\subsection{Queries for a single individual}
\label{one.individual}
We now show how to compute
$\Prinf(\phi|\KB)$ for a certain restricted class of first-order
formulas $\phi$ and knowledge bases $\KB$.  The most significantly
restriction is that the
query $\phi$ should be a quantifier-free (first-order) sentence over the
vocabulary $\P \union \{c\}$; thus, it is a query about a single
individual, $c$.  While this class is rather restrictive, it suffices
to express many real-life examples.  Moreover,
it is significantly richer than the language considered by Paris and
Vencovska \citeyear{PV}.

The following definition helps define the class of interest.
\dfn\label{essprop}
A formula is {\em essentially
propositional\/} if it is a quantifier-free and proportion-free formula
in the language $\Laeq(\set{P_1,\ldots,P_k})$ (so that, in particular,
it has no constant symbols) and has only one free variable $x$.
\edfn

We say that $\phi(c)$ is a {\em simple query for $\KB$\/} if:
\begin{itemize}
\item $\phi(x)$ is essentially propositional,
\item $\KB$ is of the form $\KBconst(c) \land \KBprop$, where
$\KBconst(x)$ is essentially propositional and $\KBprop$ does not
mention $c$.
\end{itemize}
Thus, just as in Theorem~\ref{direct}, we suppose that $\KBconst(c)$
summarizes all that is known about $c$.
In this section, we focus on computing the degree of belief
$\Prinf(\phi(c)|\KB)$ for a formula $\phi(c)$ which is a simple query
for $\KB$.

Note that an essentially propositional formula $\xi(x)$ is equivalent
to a disjunction of atoms.  For example, over the vocabulary
$\set{P_1,P_2}$, the formula $P_1(x) \lor P_2(x)$ is equivalent to
$A_1(x) \lor A_2(x) \lor A_3(x)$ (where the atoms are ordered as
in Example~\ref{four.atoms}).
For an essentially propositional formula $\xi$,
we take $\Atoms(\xi)$ be the (unique) set of atoms
such that $\xi$ is equivalent to $\bor_{A_j \in \Atoms(\xi)} A_j(x)$.

If we view a tuple $\uvec \in \propspace$ as a probability assignment to
the atoms, we can extend $\uvec$ to a probability assignment on all
essentially propositional formulas using this identification of an
essentially propositional formula with a set of atoms:
\dfn
Let $\xi$ be an essentially propositional formula.
We define a function
$\probfun{\xi} : \propspace \rightarrow \IR$ as follows:
$$
\probfun{\xi}(\uvec) = \sum_{A_j \in \Atoms(\xi)} u_j.
$$
For essentially propositional formulas $\phi(x)$ and $\KBconst(x)$
we define the (partial) function $\probf{\phi}{\KBconst} : \propspace
\rightarrow \IR$ to be:
$$
\probf{\phi}{\KBconst}(\uvec) =
  \frac{\probfun{\phi \land \KBconst}(\uvec)}
       {\probfun{\KBconst}(\uvec)}.
$$
Note that this function is undefined when $\probfun{\KBconst}(\uvec) = 0$.
\edfn

As the following result shows, if $\phi$ is a simple query for
$\KB$ (of the form $\KBconst(c) \land \KBprop$),
then all
that matters in computing $\Prinf(\phi|\KB)$
is $\probf{\phi}{\KBconst}(\uvec)$ for tuples $\uvec$ of
maximum entropy.  Thus, in a sense, we are only using $\KBprop$ to
determine the space over which we maximize entropy.  Having defined this
space, we can focus on $\KBconst$ and $\phi$ in determining the degree
of belief.

\thm\label{dob.inrange}
Suppose $\phi(c)$ is a simple query for $\KB$.
For all $\epsvec$ sufficiently small, if $\mepts$ is the set of
maximum-entropy points in $\SSc{\epsvec}{\KB}$ and
$\probfun{\KBconst}(\mept) > 0$ for all $\mept \in
\mepts$, then for $\lim^* \in \{\limsup,\liminf\}$ we have
$$
\limNstar \PrNeps(\phi(c)|\KB) \in
\left[ \inf_{\mept \in \mepts} \probf{\phi}{\KBconst}(\mept),
   \sup_{\mept \in \mepts} \probf{\phi}{\KBconst}(\mept) \right].
$$
\ethm

The following is an immediate but important corollary of this theorem.
It asserts that, if the space $\SSc{\epsvec}{\KB}$ has a unique
maximum-entropy point, then its value uniquely determines the probability
$\Prinfeps(\phi(c)|\KB)$.

\cor\label{tau.one.mept}
Suppose $\phi(c)$ is a simple query for $\KB$.
For all $\epsvec$ sufficiently small, if $\mept$ is the unique
maximum-entropy point in $\SSc{\epsvec}{\KB}$ and
$\probfun{\KBconst}(\mept) > 0$, then
$$  \Prinfeps(\phi(c) | \KB) = \probf{\phi}{\KBconst}(\mept).  $$
\ecor

We are interested in $\Prinf(\phi(c)|\KB)$, which means that we are
interested in the limit of  $  \Prinfeps(\phi(c) | \KB)$ as $\epsvec
\tends \zerovec$.  Suppose $\KB$ is
essentially positive. Then, by the results of the previous section and
the continuity of $\probf{\phi}{\KBconst}$,
it is enough to look
directly at the maximum-entropy points of $\SSczero{\KB}$.
More formally, by combining
Theorem~\ref{dob.inrange} with Proposition~\ref{maxent.close},
we can show:
\thm\label{compute.oneconst}
Suppose $\phi(c)$ is a simple query for $\KB$.
If the space $\SSzero{\KB}$ has a unique maximum-entropy
point $\mept$, $\KB$ is essentially positive, and
$\probfun{\KBconst}(\mept) > 0$, then $$
\Prinf(\phi(c)|\KB) = \probf{\phi}{\KBconst}(\mept).
$$
\ethm

We believe that this theorem will turn out to cover a lot of cases
that occur in practice.
As our examples and the discussion in
the next section show, we often do get simple queries and knowledge
bases that are essentially positive.  Concerning the assumption
of a unique maximum-entropy point, note that the entropy function is
convex and so this assumption is automatically satisfied if $\SSzero{\KB}$ is
a {\em convex\/} space.  Recall that a space $S$ is convex if for all
$\uvec, \uvec' \in S$, and all $\alpha \in [0,1]$, it is also the case
that $\alpha \uvec + (1-\alpha) \uvec' \in S$.
The space $\SSczero{\KB}$ is surely convex if it is
defined using a conjunction of linear constraints.
While it is clearly possible to create knowledge bases where
$\SSczero{\KB}$ has multiple maximum-entropy points (for example,
using disjunctions), we expect that such knowledge bases arise rarely in
practical applications.
Perhaps the most restrictive assumption made by this theorem is the
seemingly innocuous requirement that $\probfun{\KBconst}(\mept) > 0$.  This
assumption is obviously necessary
for the theorem to hold;
without it, the function $\probf{\phi}{\KBconst}$ is simply not defined.
Unfortunately, we show in Section~\ref{extending.queries} that
this requirement is, in fact, a severe one; in particular, it prevents
the theorem from being applied to most examples derived from default
reasoning, using our statistical interpretation of defaults
\cite{BGHKfull}.

We close this subsection with an example of the theorem in action.
\xam
\label{hep.maxent}
Let the language consist of $\P = \{\Hepatitis, \Jaundice, \BlueEyed\}$
and the constant $\Eric$.
There are eight atoms in this language.
We use $A_{P'_1P'_2P'_3}$ to denote the atom $P'_1(x) \land P'_2(x) \land
P'_3(x)$, where $P'_1$ is either $H$ (denoting $\Hepatitis$) or $\bH$
(denoting $\neg \Hepatitis$), $P'_2$ is $J$ or $\bJ$ (for $\Jaundice$
and $\neg \Jaundice$, respectively), and $P'_3$ is $B$ or $\bB$ (for
$\BlueEyed$ and $\neg \BlueEyed$, respectively).

Consider the knowledge base $\KBhep$:
$$
\begin{array}{l}
\forall x \, (\Hepatitis(x) \rimp \Jaundice(x))\; \land \\
\cprop{\Hepatitis(x)}{\Jaundice(x)}{x} \aeq_1 0.8\; \land \\
\prop{\BlueEyed(x)}{x} \aeq_2 0.25\; \land\\
\Jaundice(\Eric).
\end{array}
$$

If we order the atoms as
$A_{H\/J\/B}$,$A_{H\/J\/\bB}$,$A_{H\/\bJ\/B}$,$A_{H\/\bJ\/\bB}$,
$A_{\bH\/J\/B}$,$A_{\bH\/J\/\bB}$,$A_{\bH\/\bJ\/B}$,$A_{\bH\/\bJ\/\bB}$,
then it is not hard to show that $\constraints(\KBhep)$ is:
$$\begin{array}{llll}
u_3 & = & 0  & \land \\
u_4 & = & 0 & \land \\
(u_1 + u_2) & \leq & (0.8 + \vareps_1) (u_1+u_2+u_5+u_6) & \land \\
(u_1 + u_2) & \geq & (0.8 - \vareps_1) (u_1+u_2+u_5+u_6) & \land \\
(u_1 + u_3 + u_5 + u_7) & \leq & (0.25 + \vareps_2) & \land \\
(u_1 + u_3 + u_5 + u_7) & \geq & (0.25 - \vareps_2) & \land \\
(u_1+u_2+u_5+u_6) & > & 0. &
\end{array} $$
To find the space $\SSczero{\KBhep}$ we simply set $\vareps_1 = \vareps_2 =
0$.
Then it is
quite straightforward to find the maximum-entropy point in this space,
which, taking $\gamma = 2^{1.6}$, is:
$$
 (\mecoord_1,\mecoord_2,\mecoord_3,\mecoord_4,\mecoord_5,\mecoord_6,
     \mecoord_7,\mecoord_8) =
   \left( \frac{1}{5+\gamma},\frac{3}{5+\gamma},0,0,
      \frac{1}{4(5+\gamma)},\frac{3}{4(5+\gamma)},
      \frac{\gamma}{4(5+\gamma)},\frac{3\gamma}{4(5+\gamma)} \right).
$$

Using $\mept$, we can compute various asymptotic
probabilities very easily. For example,
\begin{eqnarray*}
\Prinf(\Hepatitis(\Eric) | \KBhep) & = &
  \probf{\Hepatitis}{\Jaundice}(\mept) \\
&=&\frac{\mecoord_1+\mecoord_2}{\mecoord_1+\mecoord_2+\mecoord_5+\mecoord_6} \\
 & = & \frac{\frac{1}{5+\gamma}+\frac{3}{5+\gamma}}
            {\frac{1}{5+\gamma}+\frac{3}{5+\gamma}+
             \frac{1}{4(5+\gamma)},\frac{3}{4(5+\gamma)}} = 0.8,
\end{eqnarray*}
as expected.
Similarly, we can show that $\Prinf(\BlueEyed(\Eric)|\KBhep) = 0.25$ and
that
$\Prinf(\BlueEyed(\Eric) \land \Hepatitis(\Eric)|\KBhep) = 0.2$.
Note that the first two answers
also follow from the direct inference principle (Theorem~\ref{direct}),
which happens to be applicable in this case.
The third answer shows that $\BlueEyed$ and $\Hepatitis$ are being
treated as independent.  It is a special case of a more
general independence phenomenon that applies to random worlds;
see \cite[Theorem 5.27]{BGHKfull}.
\exam


\subsection{Probabilistic propositional logic}
\label{ppl}
\label{gmp}

In this section we consider two variants of {\em probabilistic
propositional logic.}
As the following discussion shows, both can
easily be captured by our framework. The embedding we discuss
uses simple queries throughout, allowing us to appeal to
the results of the previous section.

Nilsson~\citeyear{Nil} considered the problem of what could be inferred
about the probability of certain propositions given some constraints.
For example, we might know that
$\Pr(\fly|\bird) \geq 0.7$ and that $\Pr(\yellow) \leq 0.2$, and be
interested in
$\Pr(\fly|\bird \land \yellow)$.
Roughly speaking, Nilsson suggests computing this by considering
all probability distributions consistent with the constraints,
and then computing the range of values given to $\Pr(\fly|\bird \land
\yellow)$ by these distributions.  Formally,
suppose our language consists of $k$ primitive proposition,
$p_1, \ldots, p_k$.
Consider the set $\Omega$ of $K =
2^k$ truth assignments
these propositions.
We give
semantics to probabilistic statements over this language in terms of a
probability distribution $\mu$ over the set $\Omega$ (see \cite{FHM}
for details).  Since each truth assignment $\omega \in \Omega$
determines the truth value of every propositional formula $\propform$, we
can determine the probability of every such formula:
$$
{\Pr}_\mu(\propform) = \sum_{\omega \sat \propform} \mu(\omega).
$$
Clearly, we can determine whether a probability distribution $\mu$
satisfies a set $\propconsts$ of probabilistic constraints.  The
standard notion of
probabilistic propositional inference would say that
\mbox{$\propconsts \sat \Pr(\propform) \in [\lambda_1,\lambda_2]$}
if $\Pr_\mu(\propform)$ is within
the range $[\lambda_1,\lambda_2]$
for every distribution $\mu$ that satisfies the constraints in
$\propconsts$.


Unfortunately, while this is a very natural definition,
the constraints that one can derive from it are typically quite weak.
For that reason,
Nilsson suggested strengthening this notion of inference by applying the
principle of maximum entropy: rather
than considering all distributions $\mu$ satisfying $\propconsts$, we
consider only the distribution(s) $\mu^*$ that have the greatest entropy
among those satisfying the constraints.
As we now show, one implication of our results is that the random-worlds
method provides a principled motivation for this introduction
of maximum entropy to probabilistic propositional reasoning.
In fact, the connection between
probabilistic propositional reasoning and random worlds
should now be fairly clear:
\begin{itemize}
\item
The primitive propositions $p_1,\ldots,p_k$ correspond to the unary
predicates $P_1,\ldots,P_k$.
\item
A propositional formula $\propform$ over $p_1,\ldots,p_k$ corresponds
uniquely to an essentially propositional formula $\foversion{\propform}$ as
follows: we replace each occurrence of the propositional symbol $p_i$
with $P_i(x)$.
\item
The set $\propconsts$ of probabilistic constraints corresponds to a
knowledge base $\KBprop[\propconsts]$---a constant-free knowledge base
containing only proportion expressions.  The correspondence is as
follows:
\begin{itemize}
\item
A probability expression of the form $\Pr(\propform)$ appearing in
$\propconsts$ is replaced by the proportion expression
$\prop{\foversion{\propform}(x)}{x}$.  Similarly, a conditional
probability expression $\Pr(\propform|\propform')$ is replaced by
$\cprop{\foversion{\propform}(x)}{\foversion{\propform'}(x)}{x}$.
\item
Each comparison connective $=$ is replaced by $\aeq_i$ for some $i$, and
each $\leq$ with $\aleq_i$.  (The particular choices for the approximate
equality connectives do not matter
in this context.)
\end{itemize}
The other elements that can appear in a proportion formula (such as
rational numbers and arithmetical connectives) remain unchanged.
For example, the formula $\Pr(\fly|\bird) \geq 0.7$ would correspond
to the proportion formula $\cprop{\Fly(x)}{\Bird(x)}{x} \ageq_i 0.7$.
\item
There is a one-to-one correspondence between truth assignments and
atoms:
the  truth assignment $\omega$ corresponds to the atom $A =
P'_1 \land \ldots \land P'_k$ where  $P'_i$ is
$P_i$ if $\omega(p_i) = \true$ and $\neg P_i$ otherwise.
Let $\omega_1,\ldots{},\omega_K$ be
the truth assignments corresponding to the atoms
$A_1,\ldots,A_K$, respectively.
\item
There is a one-to-one correspondence between probability distributions
over the set $\Omega$ of truth assignments and points in $\propspace$.
For each point $\uvec \in \propspace$, let
$\Prmu{\uvec}$ denote the corresponding probability distribution over
$\Omega$, where $\Prmu{\uvec}(\omega_i) = u_i$.
\end{itemize}

\rem\label{fo.equiv.prop}
Clearly, $\omega_j \sat \propform$ iff $A_j \in
\Atoms(\foversion{\propform})$.  Therefore, for all $\uvec$, we have
$$ \probfun{\foversion{\propform}}(\uvec) =
    {\Pr}_{\Prmu{\uvec}}(\propform). \ \ \ \bbox$$
\end{remark}

The following result demonstrates the tight connection between
probabilistic propositional reasoning using maximum entropy and random
worlds.

\thm\label{prop.rw.maxent}
Let $\propconsts$ be a conjunction of constraints of the form
$\Pr(\propform|\propform') = \lambda$ or $\Pr(\propform|\propform') \in
[\lambda_1,\lambda_2]$.
There is a unique probability distribution $\mu^*$ of
maximum entropy satisfying $\propconsts$.
Moreover, for all
$\propform$ and $\propform'$, if $\Pr_{\mu^*}(\propform') > 0$, then
  \begin{displaymath}
    \Prinf(\foversion{\propform}(c) | \foversion{\propform'}(c) \land
            \KBprop[\propconsts]) = {\Pr}_{\mu^*}(\propform|\propform').
  \end{displaymath}
\ethm

Theorem~\ref{prop.rw.maxent} is an easy corollary of
Theorem~\ref{compute.oneconst}. To check that the preconditions of
the latter theorem apply, note that
the constraints in
$\propconsts$ are linear, and so the space $\SSczero{\KBprop[\propconsts]}$
has a unique maximum-entropy point $\mept$.
In fact, it is easy to show
that $\Prmu{\mept}$ is the (unique) maximum-entropy probability
distribution over $\Omega$ satisfying the constraints $\propconsts$.
In addition, because there are no negated proportion expressions in
$\propconsts$, the
formula $\KB = \foversion{\propform'}(c) \land \KBprop[\propconsts]$
is certainly essentially positive.

Most applications of probabilistic propositional
reasoning consider simple constraints of the
form used in the theorem, and so such applications can be viewed as very
special cases of the random-words approach.
In fact, this theorem is essentially a very old one. The connection
between counting ``worlds'' and the entropy maximum in a space defined
as a conjunction of linear constraints is very well-known.
It has been
extensively studied in the field of thermodynamics,
starting with the 19th
century work of Maxwell and Gibbs.
Recently, this type of reasoning has been applied to problems in an AI
context by Paris and Vencovska \citeyear{PV} and Shastri \citeyear{Shastri}.
The work of Paris and Vencovska is particularly relevant because
they also realize the necessity of adopting a formal notion
of ``approximation'', although the precise details of their approach
differ from ours.

To the best of our knowledge,
most of the work on probabilistic propositional reasoning and all
formal
presentations of the entropy/worlds connection (in particular,
those of \cite{PV,Shastri}) have limited themselves to
conjunctions of linear constraints.
Our more general language gives us a great deal of additional expressive
power.  For example, it is quite reasonable to
want the ability to express that properties are (approximately)
statistically independent. For example, we may wish to assert that
$\Bird(x)$ and $\Yellow(x)$ are independent properties by saying
$\prop{\Bird(x) \land \Yellow(x)}{x} \aeq
\prop{\Bird(x)}{x} \cdot \prop{\Yellow(x)}{x}$. Clearly, such constraints are
not linear. Nevertheless, our
Theorem~\ref{compute.oneconst} covers such cases and much more.

A version of probabilistic propositional reasoning has also been used to
provide probabilistic semantics for default reasoning
\cite{Pearl90}. Here also, the connection to random worlds is of interest.
In particular, it follows from Corollary~\ref{tau.one.mept} that the recent
work of Goldszmidt, Morris, and Pearl \citeyear{GMP} can be embedded in
the random-worlds framework. In the rest of this subsection, we explain
their approach and the embedding.

Consider a language consisting of propositional formulas
over the propositional variables $p_1, \ldots, p_k$, and default rules
of the form $B \default C$ (read ``$B$'s are typically $C$'s''), where
$B$ and $C$ are propositional formulas. A distribution $\mu$ is said
to {\em $\epsilon$-satisfy\/} a default rule $B \default C$ if $\mu(C|B)
\geq 1-\epsilon$.  In addition to default rules, the framework also
permits the use of material implication in a rule, as in $B \rimp C$.  A
distribution $\mu$ is said to satisfy such a rule if $\mu(C|B) = 1$.  A {\em
parameterized probability distribution} (PPD) is a collection
$\{\mu_\epsilon\}_{\epsilon>0}$ of probability distributions over
$\Omega$, parameterized by $\epsilon$. A PPD
$\{\mu_\epsilon\}_{\epsilon>0}$ $\epsilon$-satisfies a set $\R$ of
rules if for every $\epsilon$, $\mu_\epsilon$ $\epsilon$-satisfies every
default rule $r \in \R$ and satisfies every non-default rule $r \in \R$.
A set $\R$ of default rules $\epsilon$-entails $B \rarrow C$ if for every
PPD that $\epsilon$-satisfies $\R$, $\lim_{\epsilon \tends 0}
\mu_\epsilon(C|B) = 1$.

As shown in \cite{Geffner:Framework.Reasoning.With.Defaults},
$\epsilon$-entailment possesses a number of reasonable properties typically
associated with default reasoning, including a preference for more
specific information. However, there are a number of desirable
properties that it does not have.  Among other things, irrelevant
information is not ignored. (See \cite{BGHKfull} for an extensive
discussion of this issue.)

To obtain additional desirable properties, $\epsilon$-semantics
is extended in \cite{GMP} by an application of the principle of maximum
entropy. Instead of considering all possible
PPD's, as above, we consider only the PPD
$\set{\mu^*_{\epsilon,\R}}_{\epsilon>0}$
such that, for each $\epsilon$, $\mu^*_{\epsilon,\R}$ has the
maximum entropy among distributions that $\epsilon$-satisfy all the
rules in $\R$.
(See \cite{GMP} for precise definitions and
technical details.)  Note that, since the constraints used to
define $\mu^*_{\epsilon,\R}$ are all linear,
there is indeed a unique such point of maximum entropy.
A rule $B \default C$ is an {\em ME-plausible
consequence} of $\R$ if $\lim_{\epsilon \tends 0} \mu^*_{\epsilon,\R}(C|B) =
1$. The notion of ME-plausible consequence is analyzed in detail in
\cite{GMP}, where it is shown to inherit all the nice properties of
$\epsilon$-entailment (such as the preference for more specific
information), while successfully ignoring irrelevant information.
Equally importantly, algorithms are provided for computing the
ME-plausible consequences of a set of rules in certain cases.

Our maximum-entropy results can be used to show that the approach of
\cite{GMP} can be embedded in our framework in a straightforward
manner. We simply translate a default rule $r$ of the form $B \default
C$ into a first-order default rule
$$\theta_r \eqdef \cprop{\foversion{C}(x)}{\foversion{B}(x)}{x} \aeq_1
1,$$
as in our earlier translation of Nilsson's approach.
Note that the formulas that arise under this translation all use the
same approximate equality connective $\aeq_1$.  The reason is that the
approach of \cite{GMP} uses the same $\epsilon$ for all default rules.
We can similarly translate a (non-default) rule $r$ of the form $B \rimp
C$ into a first-order constraint using universal quantification:
$$ \theta_r \eqdef \forall x \, (\foversion{B}(x) \rimp \foversion{C}(x)).$$
Under this translation,  we can prove the following theorem.
\thm
\label{thm.gmp}
Let $c$ be a constant symbol.  Using the translation
described above, for a set $\R$ of defeasible rules, $B \default C$ is
an ME-plausible consequence of $\R$ iff
$$
\Prinf \left( \foversion{C}(c) \left|
  \foversion{B}(c) \land \band_{r \in \R} \theta_r \right)  = 1. \right.
$$
\ethm


In particular, this theorem implies that all the computational techniques
and results described in \cite{GMP} carry over to this special case of
the random-worlds method.
It also shows that random-world provides a principled justification
for the approach \cite{GMP} present (one which is quite different from
the justification given in \cite{GMP} itself).

\subsection{Beyond simple queries}
\label{extending.queries}

In Section~\ref{one.individual} we restricted attention to simple
queries.  Our main result, Theorem~\ref{compute.oneconst}, needed other
assumptions as well: essential positivity, the existence of a unique
maximum-entropy point $\mept$, and the requirement that
$\probfun{\KBconst}(\mept) > 0$.   We believe that this theorem is useful
in spite of its limitations, as demonstrated by the discussion in
Section~\ref{ppl}.
Nevertheless, this result allows us to take advantage of only a
 small fragment of our rich language. Can we find a more general theorem?
After all, the basic concentration result
(Theorem~\ref{thm.concent.general}) holds with essentially no
restrictions. In this section we show that it is indeed possible to
extend Theorem~\ref{compute.oneconst} significantly.
However, there are serious limitations and subtleties.
We illustrate these problems by means of examples, and then state an
extended result.

Our attempt to address these problems (so far as is possible) leads to
a rather complicated final result. In fact, the problems we discuss
are as interesting and important as the theorem we actually give: they help
us understand more of the limits of maximum entropy.
Of course, every issue we discuss in this subsection is relatively minor
compared to maximum entropy's main (apparent) restriction, which
concerns the use of non-unary predicates.
For the reader who is less concerned about the other, lesser, issues
we remark that it is possible to skip directly to Section~\ref{binary}.


We first consider the restrictions we placed on the $\KB$, and show the
difficulties that arise if we drop them.
We start with the restriction to a single maximum-entropy point.
As the concentration theorem (Theorem~\ref{thm.concent.general}) shows,
the entropy of almost every world is near maximum.  But it does not follow that
all the maximum-entropy points are surrounded by similar numbers of
worlds.  Thus, in the presence of more than one maximum-entropy point,
we face the problem of finding the relative importance,
or weighting, of each maximum-entropy point.
As the following example illustrates, this weighting is
often sensitive to the tolerance values. For this reason, non-unique
entropy maxima often lead to nonrobustness.
\xam\label{multiple.maxent}
Suppose $\vocab = \set{P,c}$, and consider the knowledge
base
$$ \KB = (\|P(x)\|_x \aleq_1 0.3) \lor (\|P(x)\|_x \ageq_2 0.7).$$
Assume we want to compute $\Prinf(P(c) | \KB)$.
In this case, $\SSc{\epsvec}{\KB}$ is
$$
\{(u_1,u_2) \in \Delta^2\ :\ u_1 \leq 0.3 + \eps_1 \mbox{ or } u_1
  \geq 0.7 - \eps_2\},
$$
and $\SSczero{\KB}$ is
$$
\{(u_1,u_2) \in \Delta^2\ :\ u_1 \leq 0.3 \mbox{ or } u_1 \geq 0.7\}.
$$
Note that $\SSczero{\KB}$ has two maximum-entropy points:
$(0.3,0.7)$ and $(0.7,0.3)$.

Now consider the maximum-entropy points of $\SSc{\epsvec}{\KB}$ for
$\epsvec > \zerovec$.  It is not hard to show that if $\eps_1 >
\eps_2$, then this space has a unique maximum-entropy point,
$(0.3+\eps_1,0.7-\eps_1)$.  In this case, $\Prinfeps(P(c)|\KB) =
0.3+\eps_1$.  On the other hand, if $\eps_1 < \eps_2$, then the unique
maximum-entropy point of this space is $(0.7+\eps_2,0.3-\eps_2)$, in
which case $\Prinfeps(P(c)|\KB) = 0.7+\eps_2$.  If $\eps_1 = \eps_2$,
then the space $\SSc{\epsvec}{\KB}$ has two maximum-entropy
points, and by symmetry we obtain that $\Prinfeps(P(c)|\KB) = 0.5$.
So, by appropriately choosing a sequence of tolerance vectors
converging to $\zerovec$, we can make the asymptotic value of
this fraction either $0.3$, $0.5$, or $0.7$. Thus
$\Prinf(P(c)|\KB)$ does not exist.

It is not disjunctions {\em per se\/} that cause the problem
here: if we consider instead the database
 $\KB' = (\|P(x)\|_x \aleq_1 0.3) \lor (\|P(x)\|_x \ageq_2 0.6)$,
then there is no difficulty.  There is a unique maximum-entropy point
of $\SSczero{\KB'}$---$(0.6,0.4)$---and the asymptotic
probability $\Prinf(P(c)|\KB') = 0.6$, as we would want.%
\footnote{We remark that it is also possible to construct examples of
multiple maximum-entropy points
by using quadratic constraints rather than disjunction.}
\exam
In light of this example (and many similar ones we can construct), we
continue to assume that there is a single
maximum-entropy point.  As we argued earlier, we expect this to be
true in typical practical applications, so the restriction does not seem
very serious.

We now turn our attention to the requirement that
$\probfun{\KBconst}(\mept) > 0$.  As we have already observed, this seems
to be an obvious restriction to make, considering that the
function $\probf{\phi}{\KBconst}(\mept)$ is not defined otherwise.
However, this difficulty is actually a manifestation of a much deeper
problem.  As the following example shows, any approach that just uses the
 maximum-entropy point of $\SSzero{\KB}$
will necessarily fail in some cases where
$\probfun{\KBconst}(\mept) = 0$.

\xam\label{pr.zero}
Consider the knowledge base
$$\KB = (\prop{\Penguin(x)}{x} \aeq_1 0) \land
(\cprop{\Fly(x)}{\Penguin(x)}{x} \aeq_2 0) \land \Penguin(\Tweety).$$
Suppose we want to compute
$\Prinf(\Fly(\Tweety)|\Penguin(\Tweety))$.
We can easily
conclude from Theorem~\ref{direct} that this degree of belief is 0, as we
would expect.  However, we cannot reach this conclusion
using Theorem~\ref{compute.oneconst} or anything like it.
For consider the maximum-entropy point of
$\SSzero{\KB}$.  The coordinates $\mecoord_1$,
corresponding to $\Fly \land \Penguin$, and $\mecoord_2$, corresponding
to $\neg \Fly \land \Penguin$, are both 0.  Hence, $\probfun{\Penguin}(\mept)
= 0$, so that Theorem~\ref{compute.oneconst} does not apply.

But, as we said, the problem is more fundamental.
The information we need (that the proportion of flying penguins is zero)
is simply not present if all we know is the maximum-entropy point $\mept$.
We can obtain the same space $\SSzero{\KB}$
(and thus the same maximum-entropy point) from quite different
knowledge bases. In particular, consider
$\KB'$ which simply asserts that $(\prop{\Penguin(x)}{x} \aeq_1
0) \land \Penguin(\Tweety)$.
This new knowledge base tells us nothing whatsoever about the
fraction of flying penguins, and in fact it is easy to show that
$\Prinf(\Fly(\Tweety)|\KB') = 0.5$.
But of course it is impossible to
distinguish this case from the previous one just by looking at $\mept$.
It follows that no result
in the spirit of Theorem~\ref{compute.oneconst} (which just uses the
value of $\mept$) can be comprehensive.
\exam

The example shows that the philosophy behind
Theorem~\ref{compute.oneconst} cannot be extended very far, if at all:
it is inevitable that there will be problems when
$\probfun{\KBconst}(\mept) = 0$.
But it is natural to ask whether there is a different approach
altogether in which this restriction can be relaxed.
That is, is it possible to
construct a technique for computing degrees of belief in those cases
where $\probfun{\KBconst} = 0$?
As we mentioned in Section~\ref{maxent.restrictions},
we might hope to do this by computing $\Prinfeps(\phi|\KB)$ as
a function of $\epsvec$ and then taking the limit as $\epsvec$ goes
to 0.  In general, this seems very hard. But, interestingly,
the computational
technique of \cite{GMP} does use this type of parametric
analysis, demonstrating that things might not be so bad for various
restricted cases.
Another source of hope is to remember
that maximum entropy is, for us, merely one
tool for computing random-worlds degrees of belief.
There may be other approaches that bypass entropy entirely.
In particular, some of the theorems we give in
\cite{BGHKfull} can be seen as doing this; these theorems will
often apply even if $\probfun{\KBconst} = 0$.

Another assumption made throughout Section~\ref{one.individual} is
that the knowledge base has a special form, namely $\KBconst(c) \land
\KBprop$, where $\KBconst$ is essentially propositional and $\KBprop$
does not contain any occurrences of $c$.  The more
general theorem we state later relaxes this somewhat, as follows.
\dfn \label{separability}
A knowledge base $\KB$ is said to be {\em separable with respect to
query $\phi$\/} if it
has the form $\KBconst \land \KBprop$, where $\KBconst$ contains neither
quantifiers nor proportions, and $\KBprop$ contains none of the constant
symbols appearing in $\phi$ or in $\KBconst$.%
\footnote{Clearly, since our approach is semantic, it also suffices if the
knowledge base is equivalent to one of this form.}~\edfn
It should be clear that if a query $\phi(c)$ is simple for $\KB$ (as
assumed in previous subsection), then the separability condition is
satisfied.

As the following example shows, if we do not assume separability, we
can easily run into nonrobust behavior:
\xam\label{why.separable}
Consider the following knowledge base $\KB$
over the vocabulary $\vocab = \{P,c\}$:
$$ (\prop{P(x)}{x} \aeq_1 0.3 \land P(c)) \lor
     (\prop{P(x)}{x} \aeq_2 0.3 \land \neg P(c)).
$$
$\KB$ is not separable with respect to the query $P(c)$.
The space $\SSczero{\KB}$ consists of a unique point $(0.3,0.7)$, which is
also the maximum-entropy point.  Both disjuncts of $\KB$ are consistent
with the maximum-entropy point, so we might expect that the presence of
the conjuncts $P(c)$ and $\neg P(c)$ in the disjuncts would not affect
the degree of belief.  That is, if it were possible to ignore or discount
the role of the tolerances, we would expect
$\Prinf(P(c)|\KB) = 0.3$.
However, this is not the case.  Consider the behavior of
$\Prinfeps(P(c)|\KB)$ for $\epsvec > \zerovec$.  If $\eps_1 > \eps_2$,
then the maximum-entropy point of $\SSc{\epsvec}{\KB}$ is $(0.3 + \eps_1,
0.7 - \eps_1)$.  Now, consider some $\epsilon > 0$ sufficiently small so
that $\eps_2 + \epsilon < \eps_1$.
By Corollary~\ref{thm.concent.eqone}, we deduce that
$\Prinfeps((\prop{P(x)}{x} > 0.3 + \eps_2) \,|\, \KB) = 1$.  Therefore,
by Theorem~\ref{cumulativity},
$\Prinfeps(P(c) | \KB) = \Prinfeps(P(c) \, | \, \KB \land
(\prop{P(x)}{x} > 0.3 + \eps_2))$ (assuming the limit exists).  But since
the newly added expression is inconsistent with the second disjunct, we
obtain that $\Prinfeps(P(c)|\KB) = \Prinfeps(P(c) \, | \, P(c) \land
(\prop{P(x)}{x} \aeq_1 0.3)) = 1$, and not $0.3$.  On the other hand, if
$\eps_1 < \eps_2$, we get the symmetric behavior, where
$\Prinfeps(P(c)|\KB) = 0$.  Only if $\eps_1 = \eps_2$ do we get the
expected value of $0.3$ for $\Prinfeps(P(c)|\KB)$.
Clearly, by appropriately choosing a sequence of tolerance vectors
converging to $\zerovec$, we can make the asymptotic value of
this fraction any of $0$, $0.3$, or $1$, or not exist at all.
Again, $\Prinf(P(c) | \KB)$ is not robust.
\exam

We now turn our attention to restrictions on the query.  In
Section~\ref{one.individual}, we restricted to queries of the form
$\phi(c)$, where $\phi(x)$ is essentially propositional.  Although we
intend to ease this restriction, we do not intend to allow queries that
involve statistical information.  The following example illustrates the
difficulties.
\xam\label{nostat}
Consider the knowledge base $\KB = \prop{P(x)}{x} \aeq_1 0.3$ and
the query $\phi = \prop{P(x)}{x} \aeq_2 0.3$.
It is easy to see that the unique maximum-entropy point of
$\SSc{\epsvec}{\KB}$ is $(0.3 + \eps_1, 0.7 - \eps_1)$.
First suppose $\eps_2 < \eps_1$. From Corollary~\ref{thm.concent.eqone},
it follows that $\Prinfeps((\prop{P(x)}{x} > 0.3 + \eps_2)\,|\,\KB) = 1$.
Therefore, by Theorem~\ref{cumulativity},
$\Prinfeps(\phi | \KB) = \Prinfeps(\phi | \KB \land (\prop{P(x)}{x} > 0.3
+ \eps_2))$ (assuming the limit exists).  The latter expression is
clearly 0.
On the other hand, if $\eps_1 < \eps_2$, then $\KB[\epsvec] \sat
\phi[\epsvec]$, so that $\Prinfeps(\phi | \KB) = 1$.  Thus, the
limiting behavior of $\Prinfeps(\phi | \KB)$ depends on how $\epsvec$
goes to $\zerovec$, so that $\Prinf(\phi|\KB)$ is nonrobust.
\exam

The real problem here is the semantics of proportion expressions in
queries.
While the utility of the $\aeq$ connective in expressing statistical
information in the knowledge base should be fairly uncontroversial,
its role
in {\em conclusions\/} we might draw, such as $\phi$ in
Example~\ref{nostat}, is much less clear. The formal semantics
we have defined requires that we consider all possible tolerances for
a proportion expression in $\phi$, so it is not surprising that
nonrobustness is the usual result. One might argue that the tolerances in
queries should be allowed to depend more closely on tolerances of
expressions in the knowledge base.  It is possible to formalize
this intuition, as is done in \cite{KH92}, to give an alternative
semantics for dealing with proportion expressions in queries that often
gives more reasonable behavior.
Considerations of this alternative semantics would lead us too far
afield here; rather, we focus for the rest of the section on first-order
queries.

In fact, our goal is to allow
arbitrary first-order queries, even
those that involve predicates of arbitrary arity and equality (although
we still need to restrict the knowledge base to the unary
language $\Lunaeq$).  However, as the following example shows,
quantifiers too can cause problems.
\xam\label{exists.x}
Let $\vocab = \{P,c\}$ and consider $\KB_1 =
\forall x\, \neg P(x)$,
$\KB_2 = \prop{P(x)}{x} \aeq_1 0$, and $\phi = \exists x \, P(x)$.  It is
easy to see that $\SSczero{\KB_1} = \SSczero{\KB_2} = \{(0,1)\}$, and
therefore the unique maximum-entropy point in both is $\mept = (0,1)$.
However, $\Prinf(\phi | \KB_1)$ is clearly 0, whereas
$\Prinf(\phi|\KB_2)$ is actually 1.
To see the latter fact, observe that the vast majority of
models of $\KB_2$ around $\mept$ actually satisfy $\exists x\, P(x)$.
There is actually only a single world associated with $(0,1)$ at
which $\exists x\, P(x)$ is false.
This example is related to Example~\ref{pr.zero}, because
it illustrates another case in which
$\SSzero{\KB}$ cannot suffice to determine degrees of belief.~~\bbox
\end{example}

In the case of the knowledge base $\KB_1$, the maximum-entropy point
$(0,1)$ is quite misleading about the nature of nearby
worlds. We must avoid this
sort of ``discontinuity'' when
finding the degree of belief of a formula that involves first-order
quantifiers.   The notion of stability defined below is intended to deal
with this problem.  To define it, we first need the following notion of
a {\em size description.}
\dfn
A {\em size description (over $\P$)\/}
is a conjunction of $K$ formulas: for each atom
$A_j$ over $\P$, it includes exactly one of $\exists x\,A_j(x)$
and $\neg \exists x\, A_j(x)$.
For $\uvec \in \propspace$, the {\em size description associated
with $\uvec$\/}, written $\sizeof{\uvec}$, is that size description which
includes $\neg \exists x\, A_i(x)$ if $u_i = 0$
and $\exists x\, A_i(x)$ if $u_i > 0$.
\edfn

The problems
that we want to avoid
occur when there is a maximum-entropy point $\mept$ with
size description $\sizeof{\mept}$ such that
in a neighborhood of $\mept$, most of the worlds satisfying $\KB$
are associated with other
size descriptions.  Intuitively, the problem with this is that the
coordinates of $\mept$ alone give us misleading information about
the nature of worlds near $\mept$, and so about degrees of belief.%
\footnote{We actually conjecture that problems of this sort cannot arise
in the context of a maximum-entropy point of $\SSc{\epsvec}{\KB}$ for
$\epsvec > \zerovec$.  More precisely, for sufficiently small $\epsvec$
and a maximum-entropy point $\mept$ of $\SSc{\epsvec}{\KB}$ with
$\KB \in \Lunaeq$,  we
conjecture that $\Prinfeps[\OS](\sizeof{\mept}|\KB) = 1$ where $\OS$
is an open set that contains $\mept$ but no other maximum-entropy
point of $\SSc{\epsvec}{\KB}$.
If this is indeed the case, then the machinery of stability that we are
about to introduce is unnecessary, since it holds in all cases that we
need it.  However, we have been unable to prove this.}
We give a sufficient condition which can be used to avoid this problem in
the context of our theorems. This condition is effective
and uses machinery (in particular, the ability to find
solution spaces) that is needed to use the maximum-entropy approach
in any case.
\dfn
Let $\mept$ be a maximum-entropy
point of $\SSc{\epsvec}{\KB}$.  We say that $\mept$ is {\em
safe\/}
(with respect to $\KB$ and $\epsvec$) if $\mept$ is not contained in
$\SSc{\epsvec}{\KB \land \neg\sizeof{\mept}}$.
We say that {\em $\KB$ and $\epsvec$ are stable for $\mesize$}
if for every maximum-entropy point $\mept \in \SSc{\epsvec}{\KB}$ we have
that $\sizeof{\mept} = \mesize$ and that $\mept$ is safe with respect to
$\KB$ and $\epsvec$.
\edfn

The next result is the key property of stability that we need.
\thm\label{stability}
If $\KB$ and $\epsvec > \zerovec$ are stable for $\mesize$ then
$\Prinfeps(\mesize|\KB) = 1$.
\ethm

Our theorems will use the assumption that there exists some $\mesize$
such that, for all sufficiently small $\epsvec$, $\KB$ and $\epsvec$ are
stable for $\mesize$.  We note that this does not imply that $\mesize$
is necessarily the size description associated with the
maximum-entropy point(s) of
$\SSczero{\KB}$.
\xam
Consider the knowledge base $\KB_2$ in Example~\ref{exists.x}, and recall
that $\mept = (0,1)$ is the maximum-entropy point of $\SSczero{\KB_2}$.
The size description $\sizeof{\mept}$ is $\neg \exists x \, A_1(x) \land
\exists x \, A_2(x)$.  However the maximum-entropy
point of $\SSc{\epsvec}{\KB_2}$ for $\epsvec > 0$ is
actually $(\eps_1,1-\eps_1)$, so that the appropriate $\mesize$ for
such  a
$\epsvec$ is $\exists x \, A_1(x) \land \exists x \, A_2(x)$.~\exam


As we now show, the restrictions outlined above and in
Section~\ref{maxent.restrictions} suffice for our next result on
computing degrees of
belief.  In order to state this result, we need one additional
concept.  Recall that in Section~\ref{one.individual} we
expressed an essentially propositional formula $\phi(x)$ as a disjunction
of atoms.  Since we wish to also consider formulas $\phi$ using
more than one constant and non-unary predicates, we need a richer concept
than atoms.  This is the motivation behind the definition of {\em
complete descriptions}.
\dfn
\label{completedescription}
Let $\Z$ be some set of variables and constants.
A {\em complete description} $D$ over $\vocab$
and $\Z$
is an unquantified conjunction of formulas such that:
\begin{itemize}
\item
For every predicate $R \in \vocab \union \{=\}$ of arity $r$
and for every $z_{i_1},\ldots,z_{i_r} \in \Z$,
$D$ contains exactly one of $R(z_{i_1},\ldots,z_{i_r})$ or $\neg
R(z_{i_1},\ldots,z_{i_r})$ as a conjunct.
\item $D$ is consistent.%
\footnote{Inconsistency is possible because  of the
use of equality.  For example, if $D$ includes
$z_1 = z_2$ as well as both $R(z_1,z_3)$ and $\neg R(z_2,z_3)$, it
is inconsistent.} \bbox
\end{itemize}
\end{definition}
Complete descriptions simply extend the role of atoms in the context of
essentially propositional formulas to the more general setting.
As in the case of atoms, if we fix some arbitrary ordering of the conjuncts
in a complete description, then complete descriptions are mutually exclusive
and exhaustive.
Clearly, a formula $\xi$ whose free variables and constants
are contained in $\Z$, and which is
is quantifier- and proportion-free, is equivalent to some
disjunction of complete descriptions over $\Z$.  For
such
a formula $\xi$, let
$\Atoms(\xi)$ be a set of complete descriptions over $\Z$ such that
$\xi$ is equivalent to the disjunction $\bor_{D \in \Atoms(\xi)} D$, where
$\Z$ is the set of constants and free variables in $\xi$.


For the purposes of the remaining discussion (except within proofs), we
are interested only in complete descriptions over an empty set of
variables.  For a set of constants $\Z$, we can view a description $D$
over $\Z$ as describing the different properties of the constants in
$\Z$.  In our construction,
when considering a $\KB$ of the form $\KBconst \land \KBprop$ which is
separable with respect to a query $\phi$,
we define the set $\Z$ to contain
precisely those constants in $\phi$ and in $\KBconst$.  In particular,
this means that
$\KBprop$ will mention no constant in $\Z$.

A complete description $D$ over a set of constants $\Z$ can be decomposed
into three parts:
the {\em unary part} $\unaryD$ which
consists of those conjuncts of $D$ that involve unary predicates
(and thus determines an atom for each of the constant
symbols), the {\em equality part} $\eqD$ which consists of those
conjuncts of $D$ involving equality (and thus determines which of the
constants are equal to each other), and the {\em non-unary part}
$\nonunD$ which consists of those conjuncts of $D$ involving
non-unary predicates (and thus determines the
non-unary properties other than equality of the constants).
As we suggested, the unary part of such a complete description $D$ extends the
notion of ``atom''
to the case of multiple constants.  For this purpose,
we also extend $\probfun{A}$ (for an atom $A$) and define $\probfun{D}$
for a description $D$.
Intuitively, we are treating each of the individuals as independent,
so that the probability that constant $c_1$ satisfies atom $A_{j_1}$ and
that constant $c_2$ satisfies $A_{j_2}$ is just the product of the
probability that $c_1$ satisfies $A_{j_1}$ and the probability that
$c_2$ satisfies $A_{j_2}$.
\dfn
For a complete description $D$ without variables
whose unary part is equivalent to $A_{j_1}(c_1) \land \ldots \land
A_{j_m}(c_m)$ (for distinct constants $c_1,\ldots,c_m$) and for
a point $\uvec \in \propspace$, we define
$$\probfun{D}(\uvec) = \prod_{\ell=1}^m u_{j_\ell}.\ \ \ \bbox$$
\end{definition}
Note that $\probfun{D}$ is
depends only on $\unaryD$, the unary part of $D$.

As we mentioned, we can extend our approach to deal with formulas $\phi$
that also use non-unary predicate symbols.  Our computational procedure
for such formulas uses the maximum-entropy approach described
above combined with the techniques of \cite{GHK1b}.  These latter were
used in \cite{GHK1b} to compute asymptotic conditional probabilities
when conditioning on a first-order knowledge base $\KBfo$.  The basic
idea in that case is as follows:  To compute $\Prinf(\phi|\KBfo)$, we
examine the behavior of $\phi$ in finite models of $\KBfo$. We partition
the models of $\KBfo$ into a finite collection of classes such that
$\phi$ behaves {\em uniformly\/} in each individual class. By this we
mean that almost all worlds in the class satisfy $\phi$ or almost none
do; \ie there is a {\em 0-1 law\/} for the asymptotic probability of $\phi$
when we restrict attention to models in a single class.
In order to compute $\Prinf(\phi|\KBfo)$ we therefore identify the
classes, compute the relative weight of each class (which is required
because the classes are not necessarily of equal relative size), and then
decide for each class whether the asymptotic probability of $\phi$
is zero or one.

It turns out that much the same ideas continue to work in this
framework.  In this case, the classes are defined using complete
descriptions and the appropriate size description $\mesize$.
The main difference is that, rather than examining all worlds consistent
with the knowledge base, we now concentrate on those worlds in the
vicinity of the maximum-entropy points, as outlined in the previous
section.  It turns out that the restriction to these worlds affects very
few aspects of this computational procedure.  In fact, the only
difference is in computing the relative weight of the different classes.
This last step can be done using maximum entropy, using the tools
described in Section~\ref{one.individual}.

\thm\label{maxent.nonunary}
Let $\phi$ be a formula in $\Laeq$ and let
$\KB = \KBconst \land \KBprop$ be an essentially positive knowledge base
in $\Lunaeq$ which is separable with respect to $\phi$.  Let $\Z$ be the
set of constants appearing in $\phi$ or in $\KBconst$ (so that $\KBprop$
contains none of the constants in $\Z$) and let $\alldiff$ be the
formula $\band_{c,c' \in \Z} c \neq c'$.  Assume that
there exists a size description $\mesize$ such that, for all $\epsvec >
0$, $\KB$ and $\epsvec$ are stable for $\mesize$, and that the space
$\SSczero{\KB}$ has a unique maximum-entropy point $\mept$.  Then
$$
\Prinf(\phi|\KB) =
  \frac{\sum_{D \in \Atoms(\KBconst \land \alldiff)}
           \Prinf(\phi|\mesize \land D) \probfun{D}(\mept)}
       {\sum_{D \in \Atoms(\KBconst \land \alldiff)}
           \probfun{D}(\mept)}
$$
if the denominator is positive.
\ethm
Since both $\phi$ and $\mesize \land D$ are first-order formulas and
$\mesize \land D$ is precisely of the required form in \cite{GHK1b},
then $\Prinf(\phi|\mesize \land D)$ is either 0 or 1, and we
can use the algorithm of \cite{GHK1b} to compute this limit, in the time
bounds outlined there.

One corollary of the above is that the formula $\alldiff$
holds with probability 1 given any knowledge base $\KB$ of the
form we are interested in.  This corresponds to a default assumption of
{\em unique names\/}, a property often considered to be desirable in
inductive reasoning systems.

While this theorem does represent a significant generalization of
Theorem~\ref{compute.oneconst}, it still has numerous restrictions.
There is no question that some of these can be loosened to some extent,
although we have not been able to find a clean set of conditions
significantly more general than the ones that we have stated.  We leave
it as an open problem whether such a set of conditions exists.  Of course,
the most significant restriction we have made is that of allowing only
unary predicates in the $\KB$.  This issue is the subject of the next
section.

\section{Beyond unary predicates}
\label{binary}

The random-worlds method makes complete sense for the full language
$\Laeq$
(and, indeed, for even richer languages).
On the other hand,
our application of maximum entropy is limited to unary knowledge
bases. Is this restriction essential?
While we do not have a theorem to this effect (indeed, it is not even
clear what the wording of such a theorem would be), we conjecture
that it is.

Certainly none of the techniques we have used in this paper
can be generalized significantly.
One difficulty is that, once we have a binary or
higher arity predicate, we see no analogue to the
notion of atoms and no canonical form theorem.
In Section~\ref{constraints} and in the proof of Theorem~\ref{flattening},
we discuss why it becomes impossible to get rid of nested quantifiers
and proportions when we have non-unary predicates.
Even considering matters on a more intuitive level, the problems
seem formidable. In a unary language,
atoms are useful because they are simple descriptions that summarize
everything that might be known about a domain element in a model.
But consider a language with a single binary predicate $R(x,y)$.
Worlds over this language include all finite graphs (where we think of
$R(x,y)$ as holding if there is an edge from $x$ to $y$).
In this language, there are infinitely many properties that may be true or
false about a domain element.  For example, the assertions ``the node $x$
has $m$ neighbors'' are expressible in the language for each $m$.
Thus, in order to partition the domain elements according to the
properties they satisfy, we would need to define infinitely many
partitions.
Furthermore, it can be shown that ``typically'' (\ie in almost all graphs of
sufficiently great size) each node satisfies a different set of
first-order properties.  Thus, in most graphs, all the nodes
are ``different'', so a partition of domain elements
into a finite number of ``atoms'' makes little
sense.  It is very hard to see how the basic proof
strategy we have used, of summarizing a model by listing the number
of elements with various properties, can possibly be useful here.

The difficulty of finding an analogue to entropy in the presence of
higher-arity predicates is supported by results from \cite{GHK1a}.
In this paper we have shown that maximum entropy can be a useful tool
for computing degrees of belief in certain cases, if
the $\KB$ involves only unary predicates.
In \cite{GHK1a} we show that
there can be {\em no\/} general computational technique to compute degrees of
belief once we have non-unary predicate symbols in the
$\KB$.
The problem of finding degrees of belief in this case is highly
undecidable. This result was proven without statistical assertions in the
language, and in fact holds for quite weak sublanguages of first-order logic.
(For instance,
in a language without equality and with
only depth-two quantifier nesting.)
So even if there is some generalized version of maximum entropy,
it will either be extremely restricted in application or will be useless
as a computational tool.



\section{Conclusion}\label{discussion}
This paper has had two major thrusts.  The first is to establish
a connection between maximum entropy and the random-worlds approach
for a significant fragment of our language, one far richer than
that considered by Paris and Vencovska \citeyear{PV} or Shastri
\citeyear{Shastri}.
The second is to suggest that such a result is unlikely to obtain for
the full language.

The fact that we have a connection between maximum entropy and random
worlds is significant.  For one thing, it allows us to
utilize
all the tools that have been developed for computing maximum entropy
efficiently (see
\cite{Goldman87} and the further references therein),
and may thus lead to
efficient algorithms for computing degrees of belief for
a large class of knowledge bases.  In addition, maximum entropy is
known to have many attractive properties \cite{Jaynes}.  Our
result shows these properties are shared by the random-worlds approach
in the domain where these two approaches agree.  Indeed, as shown
in \cite{BGHKfull}, the random-worlds approach has many of these
properties for the full
(non-unary)
language.

On the other hand, a number of properties of maximum entropy, such as
its dependence on the choice of language and its inability
to handle causal reasoning appropriately,
have been severely criticized \cite{Pearl,GMP}.
Not surprisingly, these criticisms apply to random worlds as well.
A discussion of these criticisms, and whether they
really should be viewed as shortcomings of the random-worlds
method, is beyond the scope of this paper; the interested reader
should consult \cite[Section 7]{BGHKfull} for a more thorough discussion
of these issues and additional references.

We believe that our observations regarding
the limits
of the connection
between the random-worlds method and maximum entropy are also significant.
The question of how widely maximum entropy applies is quite
important.  Maximum entropy has been gaining prominence as a means of
dealing with uncertainty both in AI and other areas.  However, the
difficulties of using the method once we move to non-unary predicates seem not
to have been fully appreciated.  In retrospect, this is not that hard to
explain; in almost all applications where maximum entropy has been used (and
where its application can be best justified in terms of the random-worlds
method) the knowledge base is described in terms of unary predicates (or,
equivalently, unary functions with a finite range).  For example, in physics
applications we are interested in such predicates as quantum state (see
\cite{Denbigh}).  Similarly, AI applications and expert systems typically
use only unary predicates such as symptoms and diseases \cite{Cheeseman83}.
We suspect that this is not an accident, and that deep problems will arise
in more general cases. This poses a challenge to proponents of maximum
entropy since, even if one accepts the maximum-entropy principle, the
discussion above suggests that it may simply be inapplicable in a large
class of interesting examples.



\appendix
\section{Proofs for Section~\protect\ref{constraints}}
\label{flatten.proof}

\othm{flattening}
Every formula in $\Luneq$
is equivalent to a formula in canonical form.
Moreover, there is an effective procedure that, given a formula
$\xi \in \Luneq$ constructs an equivalent formula $\canxi$ in
canonical form.
\eothm

\bigskip

\prf
We show how to effectively transform $\xi \in \Luneq$ to an equivalent
formula in canonical form.  We first rename variables if necessary, so
that all variables used in $\xi$ are distinct (\ie no two quantifiers,
including proportion expressions, ever bind the same variable
symbol).

We next transform $\xi$ into an equivalent {\em flat\/} formula
$\xi_f \in \Lunaeq$,
where a flat formula is one where no quantifiers (including proportion
quantifiers) have within their scope a constant or variable other
than the variable(s) the quantifier itself binds.
(Note that in this transformation we
do not require that $\xi$ be closed.
Also, observe that flatness implies that there are no nested
quantifiers.)

We define the transformation by induction on the structure of $\xi$.
There are three easy steps:
\begin{itemize}
\item If $\xi$ is an unquantified formulas, then $\xi_f = \xi$.
\item $(\xi' \lor \xi'')_f = \xi'_f \lor \xi''_f$
\item $(\neg \xi')_f = \neg (\xi_f)$.
\end{itemize}
All that remains is to consider quantified formulas of the form
$\exists x\, \xi'$, $\prop{\xi'}{\xvec}$, or
$\cprop{\xi'}{\xi''}{\xvec}$.
It turns out that the same transformation works in all three cases.
We illustrate the transformation by
looking at the case where $\xi$ is of the form $\prop{\xi'}{\xvec}$.
By the inductive hypothesis, we can assume that $\xi'$ is flat.
For the purposes of this proof, we define a {\em basic\/} formula
to be an atomic formula (\ie one of the form $P(z)$), a proportion formula,
or a quantified formula (\ie one of the form $\exists x \, \chi$).
Let $\chi_1, \ldots{}, \chi_k$ be all
basic
subformulas of $\xi'$
that do not mention any variable in $\xvec$.
Let $z$ be a variable or constant symbol not in $\xvec$
that is mentioned in $\xi'$.
Clearly $z$ must occur in some basic subformula of $\xi'$, say $\chi'$.
By the inductive hypothesis, it is easy to see that $\chi'$ cannot
mention
any variable in $\xvec$ and so, by construction, it is in
$\set{\chi_1, \ldots{}, \chi_\ell}$. In other words, not only
do $\set{\chi_1, \ldots{}, \chi_\ell}$ not mention any variable in $\xvec$,
but they also contain all occurrences of the other variables and constants.
(Notice that this argument fails if the language contains any high-arity
predicates, including equality. For then $\xi'$ might include subformulas
of the form $R(x, y)$ or $x = y$, which can mix variables
outside $\xvec$ with those in $\xvec$.)

Now, let $B_1, \ldots{}, B_{2^\ell}$ be all the ``atoms'' over
$\chi_1, \ldots{}, \chi_\ell$. That is, we consider all formulas
$\chi'_1 \land \ldots{} \land \chi'_\ell$
where $\chi'_i$ is either $\chi_i$ or
$\neg\chi_i$. Now consider the disjunction:
 $$\bor_{i=1}^{2^\ell} (B_i \land \prop{\xi'}{\xvec}).$$
This is surely equivalent to $\prop{\xi'}{\xvec}$, because some $B_i$
must be true. However, if we assume that a particular $B_i$ is true, we
can simplify $\prop{\xi'}{\xvec}$ by replacing all the $\chi_i$ subformulas
by $\true$ or $\false$, according to $B_i$. (Note that this is
allowed only because the $\chi_i$ do not mention any variable in $\xvec$).
The result is that we can simplify each disjunct
$(B_i \land \prop{\xi'}{\xvec})$ considerably. In fact, because of our
previous observation about $\set{\chi_1, \ldots{}, \chi_\ell}$,
there will be no constants or variables outside $\xvec$ left within the
proportion quantifier. This completes
this step of the induction.  Since the other quantifiers can
be treated similarly, this proves the flatness result.


It now remains to show how a flat formula can be transformed to
canonical form.  Suppose $\xi \in \Lunaeq$ is flat.  Let $\xi^* \in
\Luneq$ be the formula equivalent to $\xi$ obtained by using the
translation of Section~\ref{language}.
Every proportion comparison in $\xi^*$ is
of the form $t \leq t' \vareps_i$ where $t$ and $t'$
are polynomials over flat unconditional proportions.
In fact, $t'$ is simply a product of
flat unconditional proportions
(where the empty product is taken to be 1).
Note also that since we cleared away conditional proportions
by multiplying by $t'$, if $t' = 0$ then so is $t$, and so the
formula $t \leq t' \vareps_i$ is automatically true. We can therefore
replace the comparison by $(t' = 0) \lor (t \leq t' \vareps_i \land t' > 0)$.
Similarly, we can replace a negated comparison by an expression of the
form $\neg(t \leq t' \vareps_i) \land t' > 0$.

The next step is to rewrite all the flat unconditional proportions
in terms of atomic proportions. In any such proportion
$\prop{\xi'}{\xvec}$, the formula $\xi'$ is a Boolean combination of
$P(x_i)$ for predicates $P \in \P$ and $x_i \in \xvec$.
Thus, the formula $\xi'$ is equivalent to a disjunction
$\bor_j (A^j_1(x_{i_1}) \land  \ldots{} \land  A^j_m(x_{i_m}))$,
where each $A^j_i$ is an atom over $\P$ and
$\xvec = \set{x_{i_1},\ldots,x_{i_m}}$.
These disjuncts are mutually exclusive and the
semantics treats distinct variables as being independent, so
$$\prop{\xi'}{\xvec} = \sum_j \prod_{i=1}^m \prop{A^j_i(x)}{x}.$$
We perform this replacement for each proportion expression.
Furthermore, any term $t'$ in an expression of the form
$t \leq t' \vareps_i$ will be a product of such
expressions, and so will be positive.

Next, we must put all pure first-order formulas in the
right form.
We first rewrite $\xi$ to push all
negations inwards as far as possible, so that only atomic subformulas
and existential formulas are negated.
Next, note that since $\xi$ is flat, each existential subformula must have
the form $\exists x\, \xi'$,
where $\xi'$ is a quantifier-free formula which mentions no constants and only
the variable $x$.  Hence, $\xi'$ is a Boolean combination of $P(x)$ for
predicates $P \in \P$.  Again, the formula $\xi'$
is equivalent to a disjunction of
atoms of the form $\bor_{A \in \Atoms(\xi)} A(x)$, so $\exists x \,
\xi'$ is equivalent to $\bor_{A \in \Atoms(\xi)} \exists x\, A(x)$.
We replace $\exists x\, \xi'$ by this expression.
Finally, we must deal with formulas of the form $P(c)$
or $\neg P(c)$ for $P \in \P$.  This is easy: We can
again replace a formula $\xi$ of the form $P(c)$ or $\neg P(c)$
by the disjunction $\bor_{A \in \Atoms(\xi)} A(c)$.

The penultimate step is to convert $\xi$ into disjunctive normal form.
This essentially brings things into canonical form.  Note that since we
dealt with formulas of the form $\neg P(c)$ in the previous step,
we do not have to deal with conjuncts of the form $\neg A_i(c)$.

The final step is to check that we do not have $A_i(c)$ and either
$\neg \exists x\, A_i(x)$ or $A_j(c)$ for some $j \ne i$
as conjuncts of some disjunct.  If we do, we simply remove that
disjunct. %the consistency of the  proportion-free
\eprf


\section{Proofs for Section~\protect\ref{concent}}
\label{countworlds.proof}

\olem{countworlds}
There exist some function $h: \IN \rightarrow \IN$ and two strictly positive
polynomial functions
$f,g : \IN \rightarrow \IR$
such that, for $\KB \in \Lunaeq$ and $\uvec \in \propspace$,
if $\nwrldPnt{\uvec}(\KB) \ne 0$, then
\begin{displaymath}
(h(N)/f(N)) e^{N H(\uvec)} \leq
       \nwrldPnt{\uvec}(\KB) \leq
             h(N) g(N) e^{N H(\uvec)}.
\end{displaymath}
\eolem

\prf
To choose a world $\world \in \WN$ satisfying $\KB$ such that
$\vecof{\world} = \uvec$,
we must partition the domain among the atoms according to
the proportions in $\uvec$, and then choose an assignment for the
constants in the language subject to the constraints imposed by $\KB$.
Finally, even though $\KB$ mentions only unary predicates, if
there are any non-unary predicates in the vocabulary we must choose
a denotation for them.

Suppose $\uvec = (u_1, \ldots, u_K)$, and
let $N_i = u_i N$ for $i = 1,\ldots,K$. The number of partitions of the
domain into atoms is ${N \choose {N_1,\ldots,N_K}}$; each such
partition completely determines the denotation for the unary predicates.
We must also specify the denotations of
the constant symbols.  There are at most
$N^{|\C|}$ ways of choosing these.
On the other hand, we know there is at least one model $(\world, \epsvec)$ of
$\KB$ such that $\vecof{\world} = \uvec$, so there there at least one
choice. In fact,
there is at least one world $\world' \in \WN$ such that
$(\world',\epsvec) \sat \KB$ for each of the ${N \choose
{N_1,\ldots,N_K}}$ ways of partitioning the elements of the domain (and
each such world $\world'$ is isomorphic to $\world$).
Finally we must choose the denotation of the non-unary predicates.
However, $\uvec$ does not constrain this choice and, by assumption,
neither does $\KB$. Therefore the number of such choices is some function
$h(N)$ which is independent of $\uvec$.%
\footnote{It is easy to verify that in fact
  \begin{displaymath}
    h(N) = \prod_{R \in \vocab - \unvocab} 2^{N^{\arity(R)}},
  \end{displaymath}
where $\unvocab$ is the unary fragment of $\vocab$ and
$\arity(R)$ denotes the arity of the predicate symbol $R$.
}
We conclude that:
\begin{displaymath}
h(N) {N \choose {N_1, \ldots, N_K}} \leq
  \nwrldPnt{\uvec}(\KB) \leq
     h(N) N^{|\C|} {N \choose {N_1, \ldots, N_K}}.
\end{displaymath}
It remains to estimate
$$
{N \choose {N_1, \ldots, N_K}} = \frac{N!}{N_1! N_2! \ldots N_K!}.
$$
To obtain our result, we use Stirling's approximation for the
factorials, which says that
$$ m! = \sqrt{2\pi m} \, m^m e^{-m} (1 + O(1/m)).$$
It follows that exist constants $L,U > 0$ such that
$$L \, m^m e^{-m} \leq m! \leq U m \, m^m e^{-m}$$
for all $m$. Using these bounds, as well as the fact that $N_i \leq N$,
we get:
\begin{displaymath}
\frac{L}{U^K N^K}
\frac{N^N \prod_{i=1}^K e^{N_i}}{e^N \prod_{i=1}^{K} N_i^{N_i}} \leq
   \frac{N!}{N_1! N_2! \ldots N_K!} \leq
\frac{U N}{L^K}
  \frac{N^N \prod_{i=1}^K e^{N_i}}{e^N \prod_{i=1}^{K} N_i^{N_i}}.
\end{displaymath}
Now, consider the expression common to both bounds:
\begin{eqnarray*}
\frac{N^N \prod_{i=1}^K e^{N_i}}{e^N \prod_{i=1}^{K} N_i^{N_i}} & = &
 \frac{N^N}{\prod_{i=1}^{K} N_i^{N_i}} \\
 & = & \prod_{i=1}^{K} \left( \frac{N}{N_i} \right)^{N_i}\\
 & = & \prod_{i=1}^{K} e^{N_i \ln(N/N_i)} \\
 & = & e^{- N \sum_{i=1}^{K} u_i \ln(u_i)} = e^{N H(\uvec)}.
\end{eqnarray*}
We obtain that
$$
\frac{h(N) L}{U^K N^K} e^{N H(\uvec)} \leq
  \nwrldPnt{\uvec}(\KB) \leq
     N^{|\C|} h(N) \frac{U N}{L^K} e^{N H(\uvec)},
$$
which is the desired result.
\eprf

We next want to prove Theorem~\ref{thm.concent.general}.  To do this,
it is useful to have an alternative representation of the solution space
$\SSc{\epsvec}{\KB}$.  Towards this end, we have the following
definition.
\dfn
Let $\PIN{\epsvec}{\KB} = \{\vecof{\world} : W \in \WN;
  (\world,\epsvec) \sat \KB\}$.
Let $\Pinf{\epsvec}{\KB}$ be the limit of these spaces.
Formally,
$$
  \Pinf{\epsvec}{\KB} = \{\uvec\;:\; \exists N_0~\mbox{\it s.t.}~\forall N
        \geq N_0 \;
        \exists \uvec^N \in \PIN{\epsvec}{\KB}~\mbox{\it s.t.}~
        \lim_{N \tendsto \infty} \uvec^N = \uvec\}. \ \ \ \bbox$$
\end{definition}

The following theorem establishes a tight connection between
$\SSc{\epsvec}{\KB}$ and $\Pinf{\epsvec}{\KB}$.
\thm\label{main.s.equals.pi}
\begin{itemize}
\item[(a)] For all $N$ and $\epsvec$, we have
   $\PIN{\epsvec}{\KB} \subseteq \SSc{\epsvec}{\KB}$.
\item[(b)]
For all sufficiently small $\epsvec$, we have
$\Pinf{\epsvec}{\KB} = \SSc{\epsvec}{\KB}$.
\end{itemize}
\ethm
\prf
Part~(a) is immediate:
If $\uvec \in \PIN{\epsvec}{\KB}$, then $\uvec = \vecof{\world}$ for
some $\world \in \WN$ such that $(\world,\epsvec) \sat \KB$.
It is almost immediate from the definitions that $\vecof{\world}$
must satisfy $\constraints(\KB[\epsvec])$, so
$\vecof{\world} \in \Sol[\constraints(\KB[\epsvec])]$.
The inclusion
$\PIN{\epsvec}{\KB} \subseteq \SS{\epsvec}{\KB}$ now follows.

One direction of part~(b) follows immediately from part~(a).  Recall that
$\PIN{\epsvec}{\KB} \subseteq \SS{\epsvec}{\KB}$ and that the points in
$\Pinf{\epsvec}{\KB}$ are limits of a sequence of points in
$\PIN{\epsvec}{\KB}$.  Since $\SS{\epsvec}{\KB}$ is closed, it follows
that $\Pinf{\epsvec}{\KB} \subseteq \SS{\epsvec}{\KB}$.

For the opposite inclusion, the general strategy of the proof is to show
the following:
\begin{enumerate}
\item[(i)]
If $\epsvec$ is sufficiently small, then for all $\uvec \in
\SSc{\epsvec}{\KB}$, there is some sequence of points
$\set{\uvec^{N_0},\uvec^{N_0+1},\uvec^{N_0+2},\uvec^{N_0+3},\ldots}
\subset \Sol[\constraints(\KB[\epsvec])]$ such
that, for all $N \geq N_0$, the coordinates of $\uvec^N$ are all integer
multiples of $1/N$
and $\lim_{N \tends \infty}{\uvec^N} = \uvec$.
\item[(ii)] if $\wvec \in \Sol[\constraints(\KB[\epsvec])]$
and all its coordinates are integer multiples of $1/N$, then
$\wvec \in \PIN{\epsvec}{\KB}$.
\end{enumerate}
This clearly suffices to prove that $\uvec \in \Pinf{\epsvec}{\KB}$.


We begin with the proof of (ii), which is straightforward.  Suppose
the point \linebreak
$\wvec = (r_1/N,r_2/N,\ldots,r_K/N)$ is in $\Sol[\constraints(\KB[\epsvec])]$.
We construct a world $\world \in \WN$ such that $\vecof{\world} = \wvec$
as follows. The denotation of atom $A_1$ is the set
of elements $\{1,\ldots,r_1\}$, the denotation of atom $A_2$ is the set
$\{r_1+1,\ldots,r_1+r_2\}$, and so on.  It remains to
choose the denotations of the constants (since the denotation of the
predicates of arity greater than 1 is irrelevant).  Without loss of
generality we can assume $\KB$ is
in canonical form.  (If not, we consider $\canKB$.)
Thus, $\KB$ is a disjunction of conjunctions, say $\bor_j \xi_j$.
Since $\wvec \in \Sol[\constraints(\KB[\epsvec])]$, we must have
$\wvec \in \Sol[\constraints(\xi_j[\epsvec])]$ for some $j$.
We use $\xi_j$ to define the properties of the constants.
If $\xi_j$ contains $A_i(c)$ for some atom $A_i$, then
we make $c$ satisfy $A_i$. Note that, by Definition~\ref{constraints.defn},
if $\xi_j$ has such a conjunct then $\ucom_i > 0$.
If $\xi_j$ contains no atomic conjunct
mentioning the constant $c$,
then we make $c$ satisfy $A_i$ for some arbitrary atom with $u_i > 0$.
It should now be clear that $(\world,\epsvec)$ satisfies $\xi_j$, and so
satisfies $\KB$.
Note that in this construction it is important
that we started with $\wvec$ in $\Sol[\constraints(\KB[\epsvec])]$, rather
than just in the closure space $\SS{\epsvec}{\KB}$; otherwise, the point would
not necessarily satisfy $\constraints(\KB[\epsvec])$.


We now consider condition (i).
This is surprisingly difficult to prove; the proof
involves techniques from
algebraic geometry.  Our job would be relatively easy if
$\Sol[\constraints(\KB[\epsvec])]$ were an open set.
Unfortunately, it is not.   On the other hand, it would behave essentially
like an open set
if we could replace the occurrences of $\le$ in
$\constraints(\KB[\epsvec])$ by $<$.  It turns out that, for our purposes here,
this replacement is possible.

Let $\constraints^{<}(\KB[\epsvec])$ be
the same as $\constraints(\KB[\epsvec])$ except that
every (unnegated) conjunct of the form $(t \le \eps_i t')$
is replaced by $(t < \eps_i t')$.
(Notice that this is essentially the opposite transformation to the one
used when defining essential positivity in Definition~\ref{essposdef}.)
Finally, let $\SS{< \epsvec}{\KB}$ be
$\overline{\Sol[\constraints^{<}(\KB[\epsvec])]}$.
It turns out that, for
all sufficiently small $\epsvec$,
$\SS{< \epsvec}{\KB} = \SS{\epsvec}{\KB}$. This result, which
we label as Lemma~\ref{brumfiel}, will be stated and proved later.
For now we use the lemma to continue the proof of the main result.


Consider some $\uvec \in \SS{\epsvec}{\KB}$.  It suffices to show that
for all $\delta > 0$ there exists $N_0$ such that for all $N > N_0$,
there exists a point $\uvec^N \in \Sol[\constraints^{<}(\KB[\epsvec])]$
such that all the coordinates of $\uvec^N$ are integer multiples of $1/N$
and such that $|\uvec - \uvec^N| < \delta$.
(For then we
can take smaller and smaller $\delta$'s to create a sequence $\uvec^N$
converging to $\uvec$.)  Hence, let $\delta > 0$.  By
Lemma~\ref{brumfiel}, we can find some $\uvec' \in
\Sol[\constraints^{<}(\KB[\epsvec])]$ such that $|\uvec - \uvec'| <
\delta/2$.  By definition, every conjunct in
$\constraints^{<}(\KB[\epsvec])$ is of the form $q'(\wvec) = 0$,
$q'(\wvec) > 0$, $q(\wvec) < \eps_i q'(\wvec)$, or $q(\wvec) >
\eps_i q'(\wvec)$, where  $q'$ is a positive polynomial.
Ignore for the moment the constraints of the form $q'(\wvec) = 0$, and
consider the remaining constraints that $\uvec'$ satisfies.  These
constraints all involve strict inequalities, and the functions involved
($q$ and $q'$) are continuous.  Thus, there exists some $\delta' > 0$
such that for all $\wvec$ for which $|\uvec' - \wvec| < \delta'$, these
constraints are also satisfied by $\wvec$.  Now consider a conjunct of
the form $q'(\wvec) = 0$ that is satisfied by $\uvec'$. Since $q'$ is
positive, this happens if and only if the following condition holds:
for every coordinate $w_i$ that actually appears in $q'$, we have
$\ucom'_i = 0$.  In particular, if $\wvec$ and $\uvec'$ have the same
coordinates with value $0$, then $q'(\wvec) = 0$. It follows that
for all $\wvec$, if $|\uvec' - \wvec| < \delta'$ and
$\uvec'$ and $\wvec$ have the same coordinates with value $0$, then
$\wvec$ also satisfies $\constraints^{<}(\KB[\epsvec])$.

We now construct $\uvec^N$ that satisfies the requirements.
Let $i^{\ast}$ be the index of that component of $\uvec'$ with the
largest value. We define $\uvec^N$ by considering each of its components
$\ucom^N_i$, for $1 \leq i \leq K$:
$$
\ucom^N_i = \left\{
             \begin{array}{ll}
             0 &
                 \ucom'_i = 0 \\
             \lceil N\ucom'_i\rceil/N &
                 i \neq i^{\ast}
                 \mbox{ and } \ucom'_i > 0\\
             \ucom^N_i -
                \sum_{j \neq i^{\ast}}(\ucom^N_{j} - \ucom'_{j}) &
                 i = i^{\ast} .
             \end{array}
             \right.
$$
It is easy to verify that the components of $\uvec^N$ sum to $1$.
All the components in $\uvec'$, other than the $i^{\ast}$'th, are
increased by at most $1/N$.
The component $\ucom^N_{i^{\ast}}$ is decreased by at most $K/N$.
We will show that $\uvec^N$ has the right properties for all
$N > N_0$, where $N_0$ is such that $1/N_0 < \min(\ucom_{i^{\ast}},
\delta/2, \delta')/2K$. The fact that $K/N_0 < \ucom_{i^{\ast}}$
guarantees that $\uvec^N$ is in $\propspace$ for all $N > N_0$.  The
fact that $2K/N_0 < \delta/2$ guarantees that $\uvec^N$ is within
$\delta/2$ of $\uvec'$, and hence within $\delta$ of $\uvec$. Since
$2K/N_0 < \delta'$, it follows that $|\uvec' - \uvec^N| < \delta'$.
Since $\uvec^N$ is constructed to have exactly the same 0 coordinates
as $\uvec'$, we conclude that $\uvec^N \in
\Sol[\constraints^{<}(\KB[\epsvec])]$, as required.
Condition (i), and hence the entire theorem, now follows.~\eprf

It now remains to prove Lemma~\ref{brumfiel},
which was used in the proof just given.
As we hinted earlier,
this requires tools from algebraic geometry.  We base our definitions
on the presentation in \cite{Bochnak.Geometrie}.
A subset $A$ of $\IR^\ell$ is said to be {\em
semi-algebraic\/} if it is definable in the language of real-closed
fields.  That is, $A$ is semi-algebraic if there is a first-order
formula $\phi(x_1, \ldots, x_\ell)$ whose free variables are $x_1,
\ldots, x_\ell$ and whose only non-logical symbols are 0, 1, $+$,
$\times$, $<$ and $=$,
 such that $\IR \sat \phi(u_1, \ldots, u_\ell)$ iff $(u_1,
\ldots, u_\ell) \in A$.%
\footnote{In \cite{Bochnak.Geometrie}, a set is taken to be semi-algebraic
if it is definable by a quantifier-free formula in the language of real closed
fields.  However, as observed in~\cite{Bochnak.Geometrie}, since the theory
of real closed fields admits elimination of quantifiers \cite{Tar1}, the two
definitions are equivalent.}
A function $f : X \rightarrow Y$, where $X \subseteq \IR^h$ and $Y
\subseteq \IR^\ell$, is said to be semi-algebraic if its graph
(\ie $\set{(\uvec,\wvec): f(\uvec) = \wvec}$) is semi-algebraic.
The main tool we use is the following {\em Curve Selection
Lemma} (see \cite[p.~34]{Bochnak.Geometrie}):
\lem
Suppose that $A$ is a semi-algebraic set in $\IR^\ell$ and $\uvec \in
\overline{A}$.  Then there exists a continuous, semi-algebraic function
$f : [0,1] \rightarrow \IR^\ell$ such that $f(0) = \uvec$ and $f(t) \in A$
for all $t \in (0,1]$.
\elem

Our first use of the Curve Selection Lemma is in the following, which
says that, in a certain sense, semi-algebraic functions behave ``nicely''
near limits. The type of phenomenon we wish to avoid is illustrated
by $x\sin{\frac{1}{x}}$ which is continuous at $0$, but has infinitely
many local maxima and minima near $0$.

\pro\label{nowiggling}
Suppose that $g: [0,1] \rightarrow \IR$ is a continuous, semi-algebraic
function such that $g(u) > 0$ if $u > 0$ and $g(0) = 0$.  Then there exists
some $\epsilon > 0$ such that $g$ is strictly increasing in the interval
$[0,\epsilon]$.
\epro

\prf
Suppose, by way of contradiction, that $g$ satisfies the hypotheses of
the proposition but there is no $\epsilon$ such that $g$ is
increasing in the interval $[0,\epsilon]$.  We define a point $u$ in
$[0,1]$ to be {\em bad\/} if for some $u' \in [0,u)$ we have $g(u') \geq
g(u)$.
Let $A$ be the set of all the bad points. Since $g$ is
semi-algebraic
so is $A$, since $u' \in A$ iff
$$
 \exists u'\,( (0 \leq u' < u) \land (g(u) \leq g(u'))).$$

Since, by assumption, $g$ is not
increasing in any interval $[0,\epsilon]$, we can find bad points
arbitrarily close to $0$ and so $0 \in \overline{A}$.
By the Curve Selection Lemma, there is a continuous
semi-algebraic curve $f: [0,1] \rarrow \IR$ such that $f(0) = 0$ and
$f(t) \in A$ for all $t \in (0,1]$.  Because of the continuity of $f$,
the range of $f$, \ie $f([0,1])$, is $[0,r]$ for some $r \in [0,1]$.
By the definition of $f$, $(0,r] \subseteq A$.  Since $0 \not\in A$, it
follows that $f(1) \neq 0$; therefore $r > 0$ and so, by
assumption, $g(r) > 0$.  Since $g$ is a continuous function, it
achieves a maximum $v > 0$ over the range $[0,r]$.  Consider the minimum
point in the interval where this maximum is achieved.  More precisely,
let $u$ be the infimum of the set $\{u' \in [0,r] \ :\ g(u') = v\}$;
clearly, $g(u) = v$. Since $v>0$ we obtain that $u > 0$ and therefore
$u \in A$.  Thus, $u$ is bad.  But that means that there
is a point $u' < u$
for which $g(u') \geq g(u)$, which contradicts the choice of $v$ and
$u$. \eprf

We can now prove Lemma~\ref{brumfiel}. Recall, the result we need is
as follows.
\lem\label{brumfiel}
For all sufficiently small $\epsvec$,
$\SSc{< \epsvec}{\KB} = \SSc{\epsvec}{\KB}$.
\elem
\prf
Clearly $\SSc{< \epsvec}{\KB} \subseteq \SSc{\epsvec}{\KB}$.
To prove the reverse inclusion we consider $\canKB$, a canonical form
equivalent of $\KB$.
We consider each disjunct of $\canKB$ separately.
Let $\xi$ be a conjunction that is one
of the disjuncts in $\canKB$.  It clearly suffices to show that
$\Sol[\constraints(\xi[\epsvec])] \subseteq \SSc{< \epsvec}{\xi} =
\overline{\Sol[\constraints^{<}(\xi[\epsvec])]}$.
Assume, by way of contradiction, that for arbitrarily small $\epsvec$,
there exists some $\uvec \in \Sol[\constraints(\xi[\epsvec])]$ which is
``separated'' from the set $\Sol[\constraints^{<}(\xi[\epsvec])]$, \ie
is not in its closure.  More formally, we say that $\uvec$ is {\em
$\delta$-separated\/} from $\Sol[\constraints^{<}(\xi[\epsvec])]$ if
there is no $\uvec' \in \Sol[\constraints^{<}(\xi[\epsvec])]$ such that
$|\uvec - \uvec'| < \delta$.

We now consider those $\epsvec$ and those points in
$\Sol[\constraints(\xi[\epsvec])]$ that are separated from
$\Sol[\constraints^{<}(\xi[\epsvec])]$:%
\footnote{We consider only those components in the infinite vector
$\epsvec$ that actually appear in $\Sol[\constraints(\xi[\epsvec])]$.}
$$
A = \{(\epsvec, \uvec, \delta)\ :\ \epsvec > \vec{0}, \ \delta >
0, \ \uvec \in \Sol[\constraints(\xi[\epsvec])]
         \mbox{ is $\delta$-separated from }
               \Sol[\constraints^{<}(\xi[\epsvec])]\}.
$$
Clearly $A$ is semi-algebraic.  By assumption, there are points in
$A$ for arbitrarily small tolerance vectors $\epsvec$.
Since $A$ is a bounded subset of $\IR^{m+K+1}$ (where $m$ is
the number of tolerance values in $\epsvec)$, we can use the
Bolzano--Weierstrass Theorem to conclude that
this set of points has an accumulation point whose first
component is $\vec{0}$.
Thus, there is a point $(\vec{0},\wvec,\delta')$ in
$\overline{A}$. By the Curve Selection Lemma, there is a continuous
semi-algebraic function $f : [0,1] \rightarrow \IR^{m+K+1}$ such that
$f(0) = (\vec{0},\wvec,\delta')$ and $f(t) \in A$ for $t \in (0,1]$.

Since $f$ is semi-algebraic, it is semi-algebraic in each of its
coordinates.  By Lemma~\ref{nowiggling}, there is
some $v > 0$ such that $f$ is strictly increasing in each of its first
$m$ coordinates over the domain $[0,v]$. Suppose that $f(v) =
(\epsvec, \uvec, \delta)$.  Now, consider the constraints in
$\constraints(\xi[\epsvec])$ that have the form $q(\wvec) > \eps_j
q'(\wvec)$.  These constraints are all satisfied by $\uvec$ and they
all involve
strong inequalities. By the continuity of the
polynomials $q$ and $q'$, there exists some $\epsilon > 0$ such that, for
all $\uvec'$ such that $|\uvec - \uvec'| < \epsilon$, $\uvec'$ also
satisfies these constraints.

Now, by the continuity of $f$, there exists a point $v' \in (0,v)$
sufficiently close to $v$ such that if $f(v') = (\epsvec', \uvec',
\delta')$, then $|\uvec - \uvec'| < \min(\delta,\epsilon)$.  Since
$f(v) = (\epsvec,\uvec,\delta) \in A$ and $|\uvec - \uvec'| < \delta$,
it follows that $\uvec' \not\in \Sol[\constraints^{<}(\xi[\epsvec])]$.
We conclude the proof by showing that this is impossible.  That is, we
show that $\uvec' \in \Sol[\constraints^{<}(\xi[\epsvec])]$.
The constraints appearing in $\constraints^{<}(\xi[\epsvec])$ can be of
the following forms: $q'(\wvec) = 0$, $q'(\wvec) > 0$, $q(\wvec) <
\eps_j q'(\wvec)$, or $q(\wvec) > \eps_j q'(\wvec)$, where $q'$ is a
positive polynomial.  Since $f(v') \in A$, we know that $\uvec' \in
\Sol[\constraints(\xi[\epsvec'])]$.  The constraints of the form
$q'(\wvec)=0$ and $q'(\wvec)>0$ are identical in
$\constraints(\xi[\epsvec'])$ and in $\constraints^{<}(\xi[\epsvec])$,
and are therefore satisfied by $\uvec'$.  Since $|\uvec' - \uvec| <
\epsilon$, our discussion in the previous paragraph implies that the
constraints of the form $q(\wvec) > \eps_j q'(\wvec)$ are also
satisfied by $\uvec'$.  Finally, consider a constraint of the form
$q(\wvec) < \eps_j q'(\wvec)$.  The corresponding constraint in
$\constraints(\xi[\epsvec'])$ is $q(\wvec) \leq \eps'_j q'(\wvec)$.
Since $\uvec'$ satisfies this latter constraint, we know that
$q(\uvec') \leq \eps'_j q'(\uvec')$.  But now, recall that we proved
that $f$ is increasing over $[0,v]$ in the first $m$ coordinates.  In
particular, $\eps'_j < \eps_j$.  By the definition of canonical
form, $q'(\uvec') > 0$, so that we conclude
$q(\uvec') \leq \eps'_j q'(\uvec') < \eps_j q'(\uvec')$.  Hence the
constraints of this type are also satisfied by $\uvec'$.  This
concludes the proof that $\uvec' \in
\Sol[\constraints^{<}(\KB[\epsvec])]$, thus deriving a contradiction
and proving the result.
\eprf

We are finally ready to prove Theorem~\ref{thm.concent.general}.

\medskip

\othm{thm.concent.general}
For all sufficiently small $\epsvec$, the following is true.
Let $\mepts$ be the points with greatest entropy in
$\SSc{\epsvec}{\KB}$ and let $\OS \subseteq \IR^K$ be any open set containing
$\mepts$. Then  for all $\theta \in \Laeq$ and for ${\lim^*} \in
\set{\limsup, \liminf}$ we have
$$
{\lim_{N \rightarrow \infty}}^{\!\!\!*}\:
                                          \PrN^{\epsvec}(\theta|\KB) =
  %\lim_{\epsvec \rarrow \vec{0}}\,
{\lim_{N \rarrow \infty}}^{\!\!\!*}\:
\frac{\nwrldPnt{\OS}(\theta \land \KB)}{\nwrldPnt{\OS}(\KB)}.$$
\eothm

\prf
Let $\epsvec$ be small enough so that Theorem~\ref{main.s.equals.pi}
applies and let $\mepts$ and $\OS$ be as in the statement of the
theorem. It clearly suffices to show that the set $\OS$ contains almost
all of the worlds that satisfy $\KB$. More precisely,
the fraction of such worlds that are in $\OS$ tends to $1$ as
$N \tendsto \infty.$

Let $\meval$ be the entropy of the points in $\mepts$.
We begin the proof by showing the existence of $\meval_L < \meval_U \;(<
\meval)$ such that (for sufficiently large $N$) (a) every point $\uvec
\in \PIN{\epsvec}{\KB}$ where $\uvec \not\in \OS$ has entropy at most
$\meval_L$ and (b) there is at least one
point $\uvec \in \PIN{\epsvec}{\KB}$ with $\uvec \in \OS$ and entropy
at least $\meval_U$.

For part (a), consider the space
$\SS{\epsvec}{\KB} - \OS$.  Since this space is closed, the entropy
function takes on a maximum value in this space; let this be $\meval_L$.
Since this space does not include any point with entropy $\meval$
(these are all in $\mepts \subseteq \OS$), we must have $\meval_L <
\meval$.  By
Theorem~\ref{main.s.equals.pi}, $\PIN{\epsvec}{\KB} \subseteq
\SS{\epsvec}{\KB}$.  Therefore, for any $N$, the
entropy of any point in $\PIN{\epsvec}{\KB} - \OS$ is at most
$\meval_L$.

For part (b), let $\meval_U$ be some value in the interval
$(\meval_L,\meval)$
(for example $(\meval_L + \meval)/2$) and let $\mept$ be any point in
$\mepts$. By the continuity of the entropy function, there exists
some $\delta > 0$ such that for all $\uvec$ with $|\uvec - \mept| <
\delta$, we have $H(\uvec) \geq \meval_U$.  Because $\OS$ is open we can,
by considering a smaller $\delta$ if necessary, assume that
$|\uvec - \mept| < \delta$ implies $\uvec \in \OS$.
By the second part of
Theorem~\ref{main.s.equals.pi}, there is a sequence of points
$\uvec^N \in \PIN{\epsvec}{\KB}$ such that $\lim_{N \tendsto \infty}
\uvec^N = \mept$. In particular, for $N$ large enough we have
$|\uvec^N - \mept| < \delta$, so that $H(\uvec^N) > \meval_U$, proving
part (b).

To complete the proof, we use Lemma~\ref{countworlds} to conclude that
for all $N$,
$$\nworlds(\KB) \geq \nwrldPnt{\uvec^N}(\KB) \geq (h(N)/ f(N))
e^{N H(\uvec^N)} \geq (h(N)/ f(N)) e^{N \meval_U}.
$$
On the other hand,
\begin{eqnarray*}
\nwrldPnt{\propspace - \OS}(\KB) & \leq &
 \sum_{\uvec \in \PIN{\epsvec}{\KB} - \OS}
      \nwrldPnt{\uvec}(\KB)   \\
 & \leq & |\{\wvec \in \PIN{\epsvec}{\KB} : \wvec \not\in \OS\}| \,
     h(N) g(N) e^{N \meval_L} \\
 & \leq & (N+1)^K h(N) g(N) e^{N \meval_L}.
\end{eqnarray*}
Therefore the fraction of models of $\KB$ which are outside $\OS$ is
at most
$$
\frac{(N+1)^K h(N) f(N) g(N) e^{N \meval_L}}{h(N) e^{N \meval_U}}
= \frac{(N+1)^K f(N) g(N) }{e^{N (\meval_U - \meval_L)} } \, .
$$
Since $(N+1)^k f(N) g(N)$ is a
polynomial
in $N$, this fraction tends to 0 as $N$ grows large.  The result
follows.~\eprf


\section{Proofs for Section~\protect\ref{compute}}

\opro{maxent.close}~Assume
that $\KB$ is essentially positive and let $\mepts$ be the set
of maximum-entropy points of $\SSczero{\KB}$ (and thus also of
$\SSpos{\KB}$).  Then for all $\epsilon > 0$ and all sufficiently
small tolerance vectors $\epsvec$ (where ``sufficiently
small'' may depend on $\epsilon$), every maximum-entropy point of
$\SSc{\epsvec}{\KB}$ is within $\epsilon$ of some maximum entropy-point
in~$\mepts$.
\eopro

\bigskip

\prf
Fix $\epsilon > 0$.  By way of contradiction, assume that
that there is some
sequence of tolerance vectors $\epsvec^m$, $m = 1,2,\ldots$, that
converges to $\zerovec$, and for
each $m$ a maximum-entropy point $\uvec^m$ of $\SSc{\epsvec^m}{\KB}$
such that for all $m$, $\uvec^m$ is at least $\epsilon$ away from
$\mepts$.  Since the space $\propspace$ is compact, we can assume
without loss of generality that this sequence converges to some point
$\uvec$.
Recall that $\constraints(\KB)$ is a finite combination (using ``and'' and
``or'') of constraints, where every such constraint is of the form
$q'(\wvec) = 0$, $q'(\wvec) > 0$, $q(\wvec) \le \vareps_j
q'(\wvec)$, or $q(\wvec) > \vareps_j q'(\wvec)$, such that $q'$ is a
positive polynomial.
Since the overall number of constraints is finite we can assume, again
without loss of generality, that
all the $\uvec^m$'s satisfy precisely the same constraints.
We claim that the corresponding conjuncts
in $\constpos(\KB[\zerovec])$ are satisfied by $\uvec$.  For a conjunct of
the form $q'(\wvec) = 0$ note that, if $q'(\uvec^m) = 0$ for all $m$,
then this also holds at the limit, so that
$q(\uvec) = 0$. A conjunct of the form $q'(\wvec) > 0$
translates into $q'(\wvec) \geq 0$ in $\constpos(\KB[\zerovec])$; such
conjuncts are trivially satisfied by any point in $\propspace$.  If a
conjunct of the form $q(\wvec) \leq \vareps_j q'(\wvec)$ is satisfied
for all $\uvec^m$ and $\epsvec^m$, then at the limit we have
$q(\uvec) \leq 0$,
which is precisely the corresponding conjunct in
$\constpos(\KB[\zerovec])$.  Finally, for a conjunct of the form
$q(\wvec) > \vareps_j q'(\wvec)$, if $q(\uvec^m) > \eps^m_j
q'(\uvec^m)$ for all $m$, then at the limit we have $q(\uvec) \geq 0$,
which again is the corresponding conjunct in $\constpos(\KB[\zerovec])$.
It follows that $\uvec$ is in $\SSpos{\KB}$.

By assumption, all points  $\uvec^m$ are at least $\epsilon$ away from
$\mepts$.  Hence, $\uvec$ cannot be in $\mepts$.  If we let $\meval$
represent the entropy of the points in $\mepts$, since $\mepts$ is
the set of all maximum-entropy points in $\SSpos{\KB}$, it follows that
$H(\uvec) < \meval$.  Choose $\meval_L$ and $\meval_U$ such that
$H(\uvec) < \meval_L < \meval_U < \meval$.  Since the entropy
function is continuous, we know that for sufficiently large $m$,
$H(\uvec^m) \leq \meval_L$.  Since $\uvec^m$ is a maximum-entropy
point of $\SS{\epsvec^m}{\KB}$, it follows that the entropy achieved in
this space for sufficiently large $m$ is at most $\meval_L$.
We derive a contradiction by showing that for sufficiently large $m$,
there is some point in $\Sol[\constraints(\KB[\epsvec^m])]$
with entropy at least $\meval_U$.  The argument is as follows.  Let
$\mept$ be some point in $\mepts$.  Since $\mept$ is a maximum-entropy
point of $\SSzero{\KB}$, there are points in
$\Sol[\constraints(\KB[\zerovec])]$ arbitrarily
close to $\mept$.  In particular, there is some point $\uvec' \in
\Sol[\constraints(\KB[\zerovec])]$ whose entropy is at least
$\meval_U$.  As we now show, this point is also in
$\Sol[\constraints(\KB[\epsvec])]$
for all sufficiently small $\epsvec$.  Again, consider all the conjuncts in
$\constraints(\KB[\zerovec])$ satisfied by $\uvec'$ and the
corresponding conjuncts in $\constraints(\KB[\epsvec])$.
Conjuncts of the form $q'(\wvec) = 0$ and $q'(\wvec) > 0$ in
$\constraints(\KB[\zerovec])$ remain unchanged in
$\constraints(\KB[\epsvec])$. Conjuncts of the form $q(\wvec) \le
\eps_j q'(\wvec)$ in $\constraints(\KB[\epsvec])$ are
certainly satisfied by $\uvec'$,  since the corresponding conjunct in
$\constraints(\KB[\zerovec])$, namely $q(\wvec) \leq 0$, is satisfied
by $\uvec'$, so that $q(\uvec') \leq 0 \leq \eps_j q'(\uvec')$
(recall that $q'$ is a positive polynomial).  Finally, consider a
conjunct in $\constraints(\KB[\epsvec])$ of the form $q(\wvec) >
\eps_j q'(\wvec)$.  The corresponding conjunct in
$\constraints(\KB[\zerovec])$ is $q(\wvec) > 0$.  Suppose $q(\uvec')
= \delta > 0$.   Since the value of $q'$ is bounded over the compact
space $\propspace$, it follows that for all sufficiently small $\eps_j$,
$\eps_j q'(\uvec') < \delta$.  Thus, $q(\uvec') > \eps_j q'(\uvec')$
for all sufficiently small $\eps_j$, as required.  It follows that
$\uvec'$ is in $\Sol[\constraints(\KB[\epsvec])]$ for all sufficiently
small $\epsvec$ and, in particular, in
$\Sol[\constraints(\KB[\epsvec^m])]$ for all sufficiently large $m$.
But $H(\uvec') \geq \meval_U$, whereas we showed that the maximum
entropy achieved in $\SSc{\epsvec^m}{\KB}$ is at most $\meval_L <
\meval_U$.  This contradiction proves that our
assumption was false, so that the conclusion of the proposition
necessarily holds.~\eprf

\medskip

\othm{dob.inrange}
Suppose $\phi(c)$ is a simple query for $\KB$.
For all $\epsvec$ sufficiently small, if $\mepts$ is the set of
maximum-entropy points in $\SSc{\epsvec}{\KB}$ and
$\probfun{\KBconst}(\mept) > 0$ for all $\mept \in
\mepts$, then for $\lim^* \in \{\limsup,\liminf\}$ we have
$$
\limNstar \PrNeps(\phi(c)|\KB) \in
\left[ \inf_{\mept \in \mepts} \probf{\phi}{\KBconst}(\mept),
   \sup_{\mept \in \mepts} \probf{\phi}{\KBconst}(\mept) \right].
$$
\eothm

\prf
Let $\world \in \Winf$, and let $\uvec = \vecof{\world}$.
The value of the proportion expression $\prop{\KBconst(x)}{x}$ at $\world$
is clearly
$$
\sum_{A_j \in \Atoms(\KBconst)} \prop{A_j(x)}{x} =
\sum_{A_j \in \Atoms(\KBconst)} u_j = \probfun{\KBconst}(\uvec).
$$
If $\probfun{\KBconst}(\uvec) > 0$, then by the same reasoning we
conclude that the value of $\cprop{\phi(x)}{\KBconst(x)}{x}$ at $\world$
is equal to $\probf{\phi}{\KBconst}(\uvec)$.

Now, let $\lambda_L$ and $\lambda_R$ be $\inf_{\mept \in \mepts}
\probf{\phi}{\KBconst}(\mept)$ and $\sup_{\mept \in \mepts}
\probf{\phi}{\KBconst}(\mept)$ respectively; by our assumption,
$\probf{\phi}{\KBconst}(\mept)$ is well-defined for all $\mept \in \mepts$.
Since the denominator is not 0, $\probf{\phi}{\KBconst}$ is a
continuous function at each maximum-entropy point.  Thus, since
$\probf{\phi}{\KBconst}(\mept) \in [\lambda_L,\lambda_R]$ for
all maximum-entropy points, the value of $\probf{\phi}{\KBconst}(\uvec)$
for $\uvec$ ``close'' to some $\mept \in \mepts$,
will either be in the range
$[\lambda_L,\lambda_U]$ or very close to it. More precisely, choose
any $\epsilon > 0$, and define $\theta[\epsilon]$ to be the formula
$$ \cprop{\phi(x)}{\KBconst(x)}{x} \in
  [\lambda_L-\epsilon,\lambda_U+\epsilon]. $$
Since $\epsilon > 0$, it is clear that there is some sufficiently
small open set $\OS$ around $\mepts$ such that this proportion expression
is well-defined and within these bounds at all worlds in $\OS$.
Thus, by Corollary~\ref{thm.concent.eqone},
$\Prinfeps(\theta[\epsilon]|\KB) = 1$.  Using Theorem~\ref{cumulativity},
we obtain that for $\lim^*$ as above,
$$\limNstar \PrNeps(\phi(c)|\KB) =
  \limNstar \PrNeps(\phi(c)|\KB \land \theta[\epsilon]).
$$
But now we can use the direct inference technique outlined earlier.
We are interested in the probability of $\phi(c)$,
where the only information we have about $c$ in the knowledge base is
$\KBconst(c)$ and where we have statistics for
$\cprop{\phi(x)}{\KBconst(x)}{x}$.  These are precisely the conditions
under which
Theorem~\ref{direct}
applies.  We conclude that
$$
\limNstar \PrNeps(\phi(c)|\KB) \in [\lambda_L-\epsilon,\lambda_U+\epsilon].
$$
Since this holds for all $\epsilon > 0$, it is necessarily the case that
$$ \limNstar \PrNeps(\phi(c)|\KB) \in [\lambda_L,\lambda_U], $$
as required.
\eprf

\medskip

\othm{compute.oneconst}
Suppose $\phi(c)$ is a simple query for $\KB$.
If the space $\SSczero{\KB}$ has a unique maximum-entropy
point $\mept$, $\KB$ is essentially positive, and
$\probfun{\KBconst}(\mept) > 0$, then $$
\Prinf(\phi(c)|\KB) = \probf{\phi}{\KBconst}(\mept).
$$
\eothm

\prf
Note that the fact that $\SSczero{\KB}$ has a unique maximum-entropy
point does not guarantee that this is also the case for
$\SSc{\epsvec}{\KB}$.  However, Proposition~\ref{maxent.close}
implies that the maximum-entropy points of the latter
space are necessarily close to $\mept$.  More precisely, if we choose
some $\epsilon > 0$, we conclude that for all sufficiently small
$\epsvec$, all the maximum-entropy points of $\SSc{\epsvec}{\KB}$ will
be within $\epsilon$ of $\mept$.  Now, pick some arbitrary $\delta >
0$. Since $\probfun{\KBconst}(\mept) > 0$, it follows that
$\probf{\phi}{\KBconst}$ is continuous at $\mept$.  Therefore, there
exists some $\epsilon > 0$ such that if $\uvec$ is within $\epsilon$ of
$\mept$, $\probf{\phi}{\KBconst}(\uvec)$ is within $\delta$ of
$\probf{\phi}{\KBconst}(\mept)$.  In particular, this is the case for
all maximum-entropy points of $\SSc{\epsvec}{\KB}$ for all
sufficiently small $\epsvec$.  This allows us to apply
Theorem~\ref{dob.inrange} and conclude that for all sufficiently
small $\epsvec$ and for $\lim^* \in \{\limsup,\liminf\}$,
$\lim^*_{N \rightarrow \infty} \PrNeps(\phi(c)|\KB)$ is within $\delta$
of $\probf{\phi}{\KBconst}(\mept)$.
Hence, this is also the case for $\lim_{\epsvec \tendsto
\vec{0}}\,\lim^*_{N \rightarrow \infty} \PrNeps(\phi(c)|\KB)$.
Since this holds for all $\delta > 0$, it follows that
$$
\lim_{\epsvec \tendsto \vec{0}}\,\liminf_{N \tendsto \infty}
   \PrNeps(\phi(c)|\KB) =
\lim_{\epsvec \tendsto \vec{0}}\,\limsup_{N \tendsto \infty}
   \PrNeps(\phi(c)|\KB) =
       \probf{\phi}{\KBconst}(\mept).$$
Thus, by definition, $\Prinf(\phi(c)|KB) =
\probf{\phi}{\KBconst}(\mept)$.
\eprf

\medskip

\othm{prop.rw.maxent}
Let $\propconsts$ be a conjunction of constraints of the form
$\Pr(\propform|\propform') = \lambda$ or $\Pr(\propform|\propform') \in
[\lambda_1,\lambda_2]$.
There is a unique probability distribution $\mu^*$ of
maximum entropy satisfying $\propconsts$.
Moreover, for all
$\propform$ and $\propform'$, if $\Pr_{\mu^*}(\propform') > 0$, then
  \begin{displaymath}
    \Prinf(\foversion{\propform}(c) | \foversion{\propform'}(c) \land
            \KBprop[\propconsts]) = {\Pr}_{\mu^*}(\propform|\propform').
  \end{displaymath}
\eothm

\prf
Clearly, the formulas $\phi(x) = \foversion{\propform}(x)$ and
$\KBconst(x) = \foversion{\propform'}(x)$ are essentially propositional.
The knowledge base $\KBprop[\propconsts]$ is in the form of a conjunction of
simple proportion formulas, none of which are negated.
As a result, the set of constraints associated with
$\KB = \KBconst(c) \land \KBprop[\propconsts]$ also has a simple form.
$\KBprop[\propconsts]$ generates a conjunction of constraints which can
be taken as having the form
$q(\wvec) \leq \vareps_j q'(\wvec)$.
On the other hand,
$\KBconst(c)$ generates some Boolean combination of constraints all of which
have the form $w_j > 0$.
We begin by considering the set
$\SSpos{\KB}$ (rather than $\SSczero{\KB}$), so we can ignore the
latter constraints for now.

$\SSpos{\KB}$ is defined by a conjunction of linear constraints which
(as discussed earlier) implies that it is convex, and thus has
a unique maximum-entropy point, say $\mept$.  Let $\mu^* = \Prmu{\mept}$
be the distribution over $\Omega$ corresponding to $\mept$.
It is clear that the constraints of
$\constpos(\KB[\zerovec])$ on the points of
$\propspace$ are precisely the same ones as those of $\propconsts$.
Therefore,
$\mu^*$ is the unique maximum-entropy distribution satisfying
the constraints of $\propconsts$.
By Remark~\ref{fo.equiv.prop}, it follows that
$\probfun{\foversion{\propform'}}(\mept) = \mu^*(\propform')$.
Since we have assumed that $\mu^*(\propform') > 0$, we are are almost
in a position to use Theorem~\ref{compute.oneconst}.
It remains to prove essential positivity.

Recall that the difference
between $\constpos(\KB[\zerovec])$ and
$\constraints(\KB[\zerovec])$ is that the latter may
have some conjuncts of the form $w_j > 0$.
Checking definitions~\ref{canonical.defn}~and~\ref{constraints.defn}
we see that such terms can appear only due to $\foversion{\propform'}(c)$
and, in fact, together they assert that
$\probfun{\foversion{\propform'}}(\wvec) > 0$.
But we have assumed that
$\probfun{\foversion{\propform'}}(\mept) > 0$ and
so $\mept$ is a maximum-entropy point of
$\SSczero{\KB}$ as well.
Thus, essential positivity holds and so, by Theorem~\ref{compute.oneconst},
\begin{displaymath}
    \Prinf(\phi(c) | \KBconst(c) \land \KBprop[\propconsts]) =
      \probf{\phi}{\KBconst}(\mu^*) = {\Pr}_{\mu^*}(\propform|\propform')
\end{displaymath}
as required.~~\bbox

\medskip

\othm{thm.gmp}
Let $c$ be a constant symbol.  Using the translation
described in Section~\ref{ppl},
for a set $\R$ of defeasible rules, $B \default C$ is
an ME-plausible consequence of $\R$ iff
$$
\Prinf \left( \foversion{C}(c) \left| \foversion{B}(c) \land
      \band_{r \in \R} \theta_r \right ) = 1. \right.
$$
\eothm

\prf
Let $\KBprop$ denote $\band_{r \in \R} \theta_r$.
For all sufficiently small $\epsvec$ and for $\epsilon = \eps_1$, let
$\mu^*$ denote $\mu^*_{\epsilon,\R}$. It clearly suffices to prove that
$$ \Prinfeps(\foversion{C}(c) | \foversion{B}(c) \land \KBprop) =
       {\Pr}_{\mu^*}(C|B),  $$
where by equality we also mean that one side is defined iff the other is
also defined.  It is easy to verify that a point $\uvec$ in
$\propspace$ satisfies $\constraints(\KBprop[\epsvec])$ iff the
corresponding distribution $\mu$ $\epsilon$-satisfies $\R$.
Therefore,
the maximum-entropy point $\mept$ of $\SSc{\epsvec}{\KBprop}$
(which is unique, by linearity) corresponds precisely to
$\mu^*$.  Now, there are two cases: either $\mu^*(B) > 0$ or $\mu^*(B) =
0$.  In the first case, by Remark~\ref{fo.equiv.prop},
$\Pr_{\mu^*}(\foversion{B}(c)) = \probfun{\foversion{B}(c)}(\mept)$,
so the latter is also
positive.  This also implies that $\mept$ is consistent with the
constraints $\constraints(\KBconst(c))$ entailed by $\KBconst(c) =
\foversion{B}(c)$, so that $\mept$ is also the unique maximum-entropy
point of $\SSc{\epsvec}{\KB}$ (where $\KB = \foversion{B}(c) \land \KBprop$).
We can therefore use Corollary~\ref{tau.one.mept} and
Remark~\ref{fo.equiv.prop} to conclude that
$\Prinfeps(\foversion{C}(c) | \KB) =
\probf{\foversion{C}(c)}{\foversion{B}(c)}(\mept) = \Pr_{\mu^*}(C|B)$
and that all three terms are well-defined.
Assume, on the other hand, that $\mu^*(B) = 0$, so that
$\Pr_{\mu^*}(C|B)$ is not well-defined. In this case, we can use a known
result (see \cite{PV}) for the maximum-entropy point over a space
defined by linear constraints,
and conclude that for all $\mu$ satisfying $\R$, necessarily
$\mu(B) = 0$.
Using the connection between distributions $\mu$ satisfying $\R$ and
points $\uvec$ in $\SSc{\epsvec}{\KBprop}$, we conclude that this is also
the case for all $\uvec \in \SSc{\epsvec}{\KBprop}$.  By part (a) of
Theorem~\ref{main.s.equals.pi}, this means that in any world
satisfying $\KBprop$, the proportion $\prop{\foversion{B}(x)}{x}$
is necessarily 0. Thus, $\KBprop$ is inconsistent with
$\foversion{B}(c)$, and $\Prinfeps(\foversion{C}(c) | \foversion{B}(c)
\land \KBprop)$ is also not well-defined.
\eprf

\section{Proofs for Section~\protect\ref{extending.queries}}

\othm{stability}
If $\KB$ and $\epsvec > \zerovec$ are stable for $\mesize$ then
$\Prinfeps(\mesize|\KB) = 1$.
\eothm

\medskip

\prf
By Theorem~\ref{thm.concent.eqone}, it suffices to show that there is
some open neighborhood containing $\mepts$, the maximum-entropy points of
$\SSc{\epsvec}{\KB}$, such that every world $\world$ of $\KB$ in this
neighborhood has $\sizeof{\world} = \mesize$.  So suppose this is not the
case. Then there is some sequence of worlds $\world_1, \world_2,
\ldots{}$ such that $(\world_i, \epsvec) \sat \KB \land\neg\mesize$ and
$\lim_{i \tendsto \infty} \min_{\mept \in \mepts} {|\vecof{\world_i} -
\mept|} = 0$.  Since $\propspace$ is compact
the sequence
$\vecof{\world_1}, \vecof{\world_2}, \ldots{}$ must have at least one
accumulation point, say $\uvec$.  This point must be in the closure of
the set $\mepts$.  But, in fact, $\mepts$ is a closed set (because
entropy is a continuous function) and so $\uvec \in \mepts$.  By part
(a) of Theorem~\ref{main.s.equals.pi}, $\vecof{\world_i} \in
\SSc{\epsvec}{\KB \land \neg\mesize}$ for every $i$ and so, since this
space is closed, $\uvec \in \SSc{\epsvec}{\KB \land \neg\mesize}$ as
well.  But this means that $\uvec$ is an unsafe maximum-entropy point,
contrary to the definition and assumption of stability.
\eprf

In the remainder of this section we prove
Theorem~\ref{maxent.nonunary}.  For this purpose, fix $\KB = \KBconst
\land \KBprop$, $\phi$, and $\mesize$ to be as in the statement of this
theorem, and let $\mept$ be the unique maximum-entropy point of
$\SSczero{\KB}$.

Let $\Z = \{c_1,\ldots,c_m\}$ be the set of constant symbols appearing
in $\KBconst$ and in $\phi$.  Due to the separability assumption,
$\KBprop$ contains none of the constant symbols in $\Z$.  Let
$\alldiff$ be the formula $\band_{i \neq j} c_i \neq c_j$.  We first
prove that $\alldiff$ has probability 1 given $\KBprop$.
\lem\label{alldiff}
For $\alldiff$ and $\KBprop$ as above, $\Prinf(\alldiff|\KBprop) = 1$.
\elem
\prf
We actually show that $\Prinf(\neg \alldiff|\KBprop) =
0$.  Let $c$ and $c'$ be two constant symbols in $\{c_1,\ldots,c_m\}$ and
consider $\Prinf(c = c'|\KBprop)$.  We again use the direct
inference technique.  Note that for any world of size $N$
the
proportion expression $\prop{x = x'}{x,x'}$ denotes exactly
$1/N$. It is thus easy to see that
$\Prinf(\prop{x = x'}{x,x'} \aeq_i 0 | \KBprop) = 1$ (for any choice of $i$).
Thus, by Theorem~\ref{cumulativity},
$\Prinf(c = c' | \KBprop) =
\Prinf(c = c' | \KBprop \land \prop{x = x'}{x,x'} \aeq_i 0)$.
But since $c$ and $c'$ appear nowhere in
$\KBprop$ we can use Theorem~\ref{direct} to conclude that
$\Prinf(c = c' | \KBprop) = 0$.  It
is straightforward to verify that, since $\neg \alldiff$ is
equivalent to a finite disjunction, each disjunct of which implies $c =
c'$ for at least one pair of constants $c$ and $c'$, we must have
$\Prinf(\neg \alldiff | \KBprop) = 0$.
\eprf

As we stated in Section~\ref{extending.queries}, our general technique
for computing the probability of an arbitrary formula $\phi$ is to
partition the worlds into a finite collection of classes such that
$\phi$ behaves uniformly over each class and then to compute the relative
weights of the classes.  As we show later, the classes are
essentially defined using complete descriptions.  Their relative weight
corresponds to the probabilities of the different complete descriptions
given $\KB$.

\pro\label{prob.description}
Let $\KB = \KBprop \land \KBconst$ and $\mept$ be as above.
Assume that $\Prinf(\KBconst|\KBprop) > 0$.
Let $D$ be a complete description over $\Z$ that is consistent with
$\KBconst$.
\begin{itemize}
\item[(a)] If $D$ is inconsistent with $\alldiff$, then
$\Prinf(D|\KB) = 0$.
\item[(b)] If $D$ is consistent with $\alldiff$, then
$$ \Prinf(D | \KB) = \frac{\probfun{D}(\mept)}
       {\sum_{D' \in \Atoms(\KBconst \land \alldiff)}
           \probfun{D'}(\mept)}.
$$
\end{itemize}
\epro
\prf
First, observe that if all limits exist and the denominator is nonzero,
then
$$\Prinf(\neg \alldiff|\KBconst \land \KBprop) =
  \frac{\Prinf(\neg \alldiff \land \KBconst|\KBprop)}
  {\Prinf(\KBconst|\KBprop)}.$$
By hypothesis, the denominator is indeed nonzero.  Furthermore,
by Lemma~\ref{alldiff}, $\Prinf(\neg \alldiff \land \KBconst|\KBprop)
\leq \Prinf(\neg \alldiff | \KBprop) = 0$.  Hence
$\Prinf(\alldiff|\KB) = \Prinf(\alldiff|\KB' \land \KBconst) = 1$.
We can therefore use
Theorem~\ref{cumulativity} to conclude that
$$ \Prinf(D |\KB) = \Prinf(D|\KB \land \alldiff).$$
Part (a) of the proposition follows immediately.

To prove part (b), recall that $\KBconst$ is equivalent
to the disjunction $\bor_{E \in \Atoms(\KBconst)} E$.
By simple probabilistic reasoning, the assumption that
$\Prinf(\KBconst|\KBprop) > 0$, and part (a), we conclude that
$$\Prinf(D|\KBconst \land \KBprop) = \frac{\Prinf(D \land \KBconst|\KBprop)}
  {\Prinf(\KBconst|\KBprop)} =
\frac{\Prinf(D \land \KBconst|\KBprop)}
  {\sum_{E \in \Atoms(\KBconst \land \alldiff)} \Prinf(E|\KBprop)}.
$$
By assumption, $D$ is consistent with $\alldiff$ and is in
$\Atoms(\KBconst)$. Since $D$ is a complete description, we must have
that $D \rimp \KBconst$ is valid. Thus, the numerator on the right-hand
side of this equation is simply  $\Prinf(D|\KBprop)$.  Hence, the
problem of computing $\Prinf(D|\KB)$ reduces to a series of
computations of the form $\Prinf(E|\KBprop)$ for various complete
descriptions $E$.

Fix any such description $E$.  Recall that $E$ can be
decomposed into three parts: the unary part $E^1$, the non-unary part
$E^{>1}$, and the equality part $E^=$.  Since $E$ is in
$\Atoms(\alldiff)$, we conclude that $\alldiff$ is equivalent to $E^=$.
Using Theorem~\ref{cumulativity} twice and some probabilistic reasoning,
we get:
\begin{eqnarray*}
\Prinf(E^{>1} \land E^1 \land E^= | \KBprop) & = &
  \Prinf(E^{>1} \land E^1 \land E^= | \KBprop \land \alldiff) \\
 & = & \Prinf(E^{>1} \land E^1 | \KBprop \land \alldiff) \\
 & = & \Prinf(E^{>1} | \KBprop \land \alldiff \land E^1) \cdot
       \Prinf(E^1 | \KBprop \land \alldiff)\\
 & = & \Prinf(E^{>1} | \KBprop \land \alldiff \land E^1) \cdot
       \Prinf(E^1 | \KBprop).
\end{eqnarray*}
In order to simplify the first expression, recall that none of the
predicate symbols in $E^{>1}$ occur anywhere in $\KBprop \land \alldiff
\land E^1$.  Therefore, the probability of $E^{>1}$ given $\KBprop
\land \alldiff$ is equal to the probability that the elements
denoting the $|\Z|$ (different) constants satisfy some particular
configuration of non-unary properties.  It should be clear that, by
symmetry, all such configurations are equally likely.  Therefore,
the probability of any one of them is a constant, equal to 1 over the
total number of configurations.%
\footnote{Although we do not need the value of this constant in
our calculations below, it is in fact easy to verify that its
value is $\prod_{R \in (\vocab - \unvocab)} 2^{m^{\arity(R)}}$,
where $m = |\Z|$.}
Let $\rho$ denote the constant which is equal to
$\Prinf(E^{>1} | \KBprop \land \alldiff \land E^1)$ for all $E$.

The last step is to show that, if $E^1$ is
equivalent to $\band_{j=1}^m A_{i_j}(c_j)$, then
$\Prinf(E^1|\KBprop) = \probfun{D}(\mept)$:
\begin{eqnarray*}
\Prinf(\band_{j=1}^m A_{i_j}(c_j) | \KBprop) & \!\!=\! &
\Prinf(A_{i_1}(c_1)| \band_{j=2}^m A_{i_j}(c_j) \land \KBprop) \cdot
      \Prinf(A_{i_2}(c_2)| \band_{j=3}^m A_{i_j}(c_j) \land \KBprop) \\
& & \ \ \ \cdot \ldots \cdot \, \Prinf(A_{i_{m-1}}(c_{m-1}) |
            A_{i_m}(c_m) \land \KBprop) \, \cdot \,
              \Prinf(A_{i_m}(c_m)| \KBprop)\\
& \!\!=\! & \mecoord_{i_1} \cdot \ \ldots \ \cdot \mecoord_{i_m}
       \mbox{ (using Theorem~\ref{compute.oneconst}; see below)}\\
& \!\!=\! & \probfun{D}(\mept).
\end{eqnarray*}
The first step is simply probabilistic reasoning.
The second step uses $m$ applications of
Theorem~\ref{compute.oneconst}.  It is easy to see that
$A_{i_j}(c_j)$ is a simple query for $A_{i_{j+1}}(c_{j+1}) \land
\ldots \land A_{i_m}(c_m) \land \KBprop$. We would like to show that
$$\Prinf(A_{i_j}(c_j)| \band_{\ell=j+1}^m A_{i_\ell}(c_\ell) \land
\KBprop) = \Prinf(A_{i_j}(c_j)| \KBprop) = \mecoord_{i_j},$$
where Theorem~\ref{compute.oneconst} justifies the last equality.
To prove the first equality, we show that for all $j$, the spaces
$\SSczero{\KBprop}$
and $\SSczero{\band_{\ell=j+1}^m A_{i_\ell}(c_j) \land \KBprop}$ have
the same maximum-entropy point, namely $\mept$.
This is proved by backwards induction; the $j = m$ case is trivially true.
The difference between the ($j-1$)st and $j$th
case is the added conjunct
$A_{i_{j}}(c_j)$, which amounts to adding the new constraint $w_{i_j} > 0$.
There are two possibilities. First, if $\mecoord_{i_j} > 0$,
then $\mept$ satisfies this new constraint anyway and so remains the
maximum-entropy point, completing this step of the induction.
If $\mecoord_{i_j} = 0$ this is not the case, and indeed, the property
we are trying to prove can be false (for $j < m$). But this does not
matter, because we then know that $\Prinf(A_{i_{j}}(c_j)|
\band_{\ell={j+1}}^m A_{i_\ell}(c_\ell) \land \KBprop) =
\Prinf(A_{i_j}(c_j)| \KBprop) = v_{i_{j}} = 0$.
Since both of the products in question include a $0$ factor, it is
irrelevant as to whether the other terms agree.

We can now put everything together to conclude that
$$\Prinf(D|\KB) = \frac{\Prinf(D|\KBprop)}
  {\sum_{E \in \Atoms(\KBconst \land \alldiff)} \Prinf(E|\KBprop)} =
  \frac{\probfun{D}(\mept)}
    {\sum_{E \in \Atoms(\KBconst \land \alldiff)} \probfun{E}(\mept)},
$$
proving part (b).
\eprf

We now address the issue of computing $\Prinf(\phi|\KB)$ for an
arbitrary formula $\phi$.  To do that, we must first
investigate the behavior of $\Prinfeps(\phi|\KB)$ for small $\epsvec$.
Fix some sufficiently small $\epsvec > 0$, and let $\mepts$ be the set
of maximum-entropy points of $\SSc{\epsvec}{\KB}$.  Assume $\KB$ and
$\epsvec$ are stable for $\mesize$.  By definition, this means that for
every $\mept \in \mepts$, we have $\sizeof{\mept} = \mesize$.
Let $I$ be the set of $i$'s for which $\mesize$ contains the conjunct
$\exists x A_i(x)$.  Since $\sizeof{\mept} = \mesize$ for all $\mept$,
we must have that $\mecoord_i > 0$ for all $i \in I$.  Since $\mepts$
is a closed set, this implies that there exists some $\epsilon > 0$
such that for all $\mept \in \mepts$ and for all $i \in I$, we have
$\mecoord_i > \epsilon$. Let $\theta[\epsilon]$ be the formula
$$ \band_{i \in I}  \prop{A_i(x)}{x} > \epsilon.$$
The following proposition is now easy to prove:
\pro\label{sumprobsprop}
Suppose that $\KB$ and $\epsvec$ are stable for $\mesize$ and that
$\mepts$, $i$, $\theta[\epsilon]$, and $\alldiff$ are as above.
Then
$$
\Prinfeps(\phi|\KB) = \sum_{D \in \Atoms(\KBconst)}
  \Prinfeps(\phi|\KBprop \land \theta[\epsilon] \land \mesize \land D)
  \cdot \Prinfeps(D|\KB).
$$
\epro
\prf
Clearly, $\theta[\epsilon]$ satisfies the conditions of
Corollary~\ref{thm.concent.eqone}, allowing us to conclude that
$\Prinfeps(\theta[\epsilon]|\KB) = 1$. Similarly, by
Theorem~\ref{stability} and the assumptions of
Theorem~\ref{maxent.nonunary}, we
can conclude that $\Prinfeps(\mesize|\KB) = 1$.  Since the conjunction
of two assertions that have probability~1 also has probability~1, we
can use Theorem~\ref{cumulativity} to conclude that $\Prinfeps(\phi|\KB) =
\Prinfeps(\phi|\KB \land \theta[\epsilon] \land \mesize)$.

Now, recall that $\KBconst$ is equivalent to the disjunction
$\bor_{D \in \Atoms(\KBconst)} D$.  By straightforward probabilistic
reasoning, we can therefore conclude that
$$
\Prinfeps(\phi | \KB \land \theta[\epsilon] \land \mesize) =
  \sum_{D \in \Atoms(\KBconst)}
  \Prinfeps(\phi | \KB \land \theta[\epsilon] \land \mesize \land D)
  \cdot \Prinfeps(D|\KB\land\theta[\epsilon]\land\mesize).$$
By Theorem~\ref{cumulativity} again,
$\Prinfeps(D|\KB\land\theta[\epsilon]\land\mesize) = \Prinfeps(D|\KB)$.
The desired expression now follows.~\eprf

We now simplify the expression
$\Prinfeps(\phi|\KB \land \theta[\epsilon] \land \mesize \land D).$

\pro\label{maxent.zerone}
For $\phi$, $\KB$, $\mesize$, $D$, and $\theta[\epsilon]$ as above,
if $\Prinfeps(D|\KB) > 0$, then
$$
\Prinfeps(\phi | \KB \land \theta[\epsilon] \land \mesize \land D)
     = \Prinf(\phi | \mesize \land D),$$
and its value is either 0 or 1.  Note that since the latter
probability only refers to first-order formulas, it is independent
of the tolerance values. \epro
\prf
That the right-hand side
is either 0 or 1 is proved in
\cite{GHK1b}, where it is shown that the asymptotic
probability of any pure first-order sentence when conditioned
on knowledge of the form $\mesize \land D$ (which is, essentially,
what was called a {\em model description} in \cite{GHK1b}) is
either~0~or~1.  Very similar techniques can be used to show that the
left-hand side
is also either 0 or 1, and that the conjuncts
$\KB \land
\theta[\epsilon]$ do not affect this limit (so that the left-hand side
and the right-hand side are in fact equal).  We briefly sketch the
relevant details here, referring the reader to \cite{GHK1b} for full
details.

The idea (which actually goes back to Fagin \citeyear{Fagin01}) is to
associate with a model description such as $\mesize \land D$ a theory
$T$ which essentially consists of {\em extension axioms}.  Intuitively,
an extension axiom says that any finite substructure of the model
defined by a complete description $D'$ can be extended in all possible
ways definable by another description $D''$.  We say that a description
$D''$ {\em extends\/} a description $D'$ if all conjuncts of $D'$ are
also conjuncts in $D''$.  An extension axiom has the form
$\forall x_1, \ldots, x_j \, (D' \rimp \exists x_{j+1} \, D'')$, where
$D'$ is a complete description over $\X = \set{x_1,\ldots{},x_j}$ and
$D''$ is a complete description over $\X \union \set{x_{j+1}}$, such
that $D''$ extends $D'$, both $D'$ and $D''$ extend $D$, and both are
consistent with $\mesize$.
It is then shown that (a) $T$ is
complete (so that for each formula $\xi$, either $T \sat \xi$ or $T
\sat \neg \xi$) and (b) if $\xi \in T$ then $\Prinf(\xi|\mesize
\land D) = 1$.  From (b) it easily follows that if $T \sat \xi$, then
$\Prinf(\xi|\mesize \land D)$ is also 1.  Using (a), the desired 0-1
law follows.  The only difference from the proof in \cite{GHK1b} is
that we need to show that (b) holds even when we condition on $\KB
\land \theta[\epsilon] \land \mesize \land D$, instead of just on
$\mesize \land D$.

So suppose $\xi$ is the extension axiom $\forall x_1, \ldots, x_j \,
(D' \rimp \exists x_{j+1} \, D'')$.  We must show that
$\Prinf(\xi|\KB \land \theta[\epsilon] \land \mesize \land D) = 1$.
We first want to show that the right-hand side of the conditional
is consistent.
As observed in the previous proof, it follows from
Theorem~\ref{cumulativity} that $\Prinf(D|\KB) =
\Prinfeps(\phi | \KB \land \theta[\epsilon] \land \mesize)$.  Since
we are assuming that $\Prinf(D|\KB) > 0$, it follows that
$\Prinf(\KB \land \theta[\epsilon] \land \mesize \land D) > 0$,
and hence $\KB \land \theta[\epsilon] \land \mesize \land D$ must
be consistent.

Fix a domain size $N$ and consider the set of worlds satisfying
$\KB \land \theta[\epsilon] \land \mesize \land D$.
Now consider some particular $j$ domain elements, say $d_1, \ldots,
d_j$, that satisfy $D'$. Observe that, since $D'$ extends $D$, the
denotations of the constants are all among $d_1,\ldots,d_j$. For a
given $d \not\in \set{d_1,\ldots{},d_j}$, let $B(d)$ denote the event
that $d_1,\ldots{},d_j,d$ satisfy $D''$, given that $d_1,\ldots,d_j$
satisfy $D'$.  What is the probability of $B(d)$ given
$ \KB \land \theta[\epsilon] \land \mesize \land D$?
First, note that since $d$ does
not denote any constant, it cannot be mentioned in any way in the
knowledge base.  Thus, this probability is the same for all $d$.
The description $D''$ determines two types of properties for
$x_{j+1}$.  The unary properties of $x_{j+1}$ itself---\ie the atom
$A_i$ to which $x_{j+1}$ must belong---and the relations between
$x_{j+1}$ and the remaining variables $x_1,\ldots,x_j$ using the
non-unary predicate symbols. Since $D''$ is consistent with $\mesize$,
the description $\mesize$ must contain a conjunct $\exists x \,
A_i(x)$ if $D''$ implies $A_i(x_{j+1})$.  By definition,
$\theta[\epsilon]$ must therefore contain the
conjunct $\prop{A_i(x)}{x} > \epsilon$. Hence, the probability of
picking $d$ in $A_i$ is at least $\epsilon$.  For any sufficiently
large $N$, the probability of picking $d$ in $A_i$ which is different
>from $d_1,\ldots,d_j$ (as required by the definition of the extension
axiom) is at least $\epsilon/2 > 0$.  The probability that
$d_1,\ldots,d_j,d$ also satisfy the remaining conjuncts of $D''$,
given that $d$ is in atom $A_i$ and $d_1,\ldots,d_j$ satisfy $D'$, is
very small but bounded away from $0$.  (For this to hold, we
need the assumption that the non-unary predicates are not mentioned in
the $\KB$.)  This is the case because the total number of possible
ways to choose the properties of $d$ (as they relate to $d_1,\ldots{},d_j)$
is independent of $N$.  We can therefore conclude that the probability
of $B(d)$ (for sufficiently large $N$), given that $d_1,\ldots{},d_j$
satisfy $D$, is bounded away from $0$ by some $\lambda$ independent of
$N$.  Since the properties of an element $d$ and its relation to
$d_1,\ldots{},d_j$ can be chosen independently of the properties of a
different element $d'$, the different events $B(d), B(d'),\ldots{}$
are all independent.  Therefore, the probability that there is no
domain element at all that, together with $d_1,\ldots,d_j$, satisfies
$D''$ is at most $(1-\lambda)^{N-j}$. This bounds the probability of
the extension axiom being false, relative to fixed $d_1, \ldots{},
d_j$. There are $N \choose j$ ways of these choosing $j$ elements,
so the probability of the axiom being false anywhere in a model is at
most ${N \choose j} (1-\lambda)^{N-j}$.  This tends to~0 as
$N$ goes to infinity. Therefore, the extension axiom $\forall x_1,
\ldots, x_j\, (D' \rimp \exists x_{j+1}\, D'')$ has asymptotic
probability 1 given $\KB \land \theta[\epsilon] \land \mesize \land
D$, as desired. \eprf


Finally, we are in a position to prove Theorem~\ref{maxent.nonunary}.

\medskip

\othm{maxent.nonunary}
Let $\phi$ be a formula in $\Laeq$ and let
$\KB = \KBprop \land \KBconst$ be an essentially positive knowledge base
in $\Lunaeq$ which is separable with respect to $\phi$.  Let $\Z$ be the
set of constants appearing in $\phi$ or in $\KBconst$ (so that $\KBprop$
contains none of the constants in $\Z$) and let $\alldiff$ be the
formula $\band_{c,c' \in \Z} c \neq c'$.  Assume that
there exists a size description $\mesize$ such that, for all $\epsvec >
0$, $\KB$ and $\epsvec$ are stable for $\mesize$, and that the space
$\SSczero{\KB}$ has a unique maximum-entropy point $\mept$.  Then
$$
\Prinf(\phi|\KB) =
  \frac{\sum_{D \in \Atoms(\KBconst \land \alldiff)}
           \Prinf(\phi|\mesize \land D) \probfun{D}(\mept)}
       {\sum_{D \in \Atoms(\KBconst \land \alldiff)}
           \probfun{D}(\mept)}
$$
if the denominator is positive.
\eothm

\medskip

\prf
Assume without loss of generality that $\KBconst$ mentions all the constant
symbols in $\phi$, so that $\Atoms(\KBconst \land \alldiff) \subseteq
\Atoms(\KBconst)$. By Proposition~\ref{sumprobsprop},
$$
\Prinfeps(\phi|\KB) = \sum_{D \in \Atoms(\KBconst)}
  \Prinfeps(\phi|\KB \land \theta[\epsilon] \land \mesize \land D) \cdot
  \Prinfeps(D|\KB).
$$
Note that we cannot easily take limits of
$\Prinfeps(\phi|\KB \land \theta[\epsilon] \land \mesize \land D)$ as
$\epsvec$ goes to $\zerovec$, because this expression depends on
$\theta[\epsilon]$ and the value of $\epsilon$ used depends
on the choice of $\epsvec$.  However, applying
Proposition~\ref{maxent.zerone}, we get
$$
\Prinfeps(\phi|\KB) = \sum_{D \in \Atoms(\KBconst)}
  \Prinf(\phi|\mesize \land D) \cdot
  \Prinfeps(D|\KB).
$$
We can now take the limit as $\epsvec$ goes to $\zerovec$.  To do this,
we use Proposition~\ref{prob.description}. The hypotheses of the
theorem imply that $\Prinf(\KBconst|\KBprop) > 0$
(for otherwise, the denominator
${\sum_{D \in \Atoms(\KBconst \land \alldiff)}
           \probfun{D}(\mept)}$ would be zero).
Part~(a) of the proposition
tells us we can ignore those complete descriptions that are inconsistent
with $\alldiff$.  We can now apply part~(b) to get the desired result.
\eprf

\acks{We are very grateful to Professor Gregory Brumfiel, of the
Department of
Mathematics at Stanford University, for his invaluable help
with the proof of Proposition~\ref{brumfiel}.  We would like to
thank Fahiem Bacchus, with whom we started working on this general area
of research, and Moshe Vardi for useful comments on a previous draft of
this paper.
A preliminary version of this paper appeared in {\em Proc.~7th IEEE
Symposium on Logic in Computer Science}.
Some of this research was performed
while Adam Grove and Daphne Koller were at Stanford University and at
the IBM Almaden Research Center.
This research was sponsored in
part by the Air Force Office of Scientific Research (AFSC), under
Contract F49620-91-C-0080,
by an IBM Graduate Fellowship, and by a University of California
President's Postdoctoral Fellowship.
}

\vskip 0.2in
\bibliographystyle{theapa}
\bibliography{z,kv,bghk}
\end{document}













