Approximate inference for first-order probabilistic languages

1 Introduction

Recent work in AI has made clear the advantages to be derived from combining probability theory with (at least some of) the expressive power of first-order logic [Wellman et al., 1992]. We will call languages that exhibit such a combination first-order probabilistic languages (FOPLs). The ability to handle objects, relations, and quantification gives such languages a huge advantage in representational efficiency in certain situations. To take a purely logical example: the rules of chess can be written in about one page of Prolog but require perhaps millions of pages in a propositional language. A recent thesis on first-order probabilistic languages [Pfeffer, 2000] describes a battlespace management system involving potentially thousands of objects whose relationships are unknown and changing. [Pasula et al., 1999] describe a freeway traffic surveillance involving probabilistic inference about the identities and properties of thousands of vehicles. These applications would be infeasible without some ability to specify and reason with FOPL knowledge bases.

The semantics of FOPLs are based on the idea that each model of a FOPL knowledge base should be viewed as a probability measure over the possible worlds (logical models) defined by the constant, function, and predicate symbols of the knowledge base [Halpern, 1990]. Although "wildly undecidable" in full generality, highly restricted FOPLs appear to be practical, especially with finite models. Two threads have arisen, based on semantic networks (e.g., [Koller and Pfeffer, 1998]) and logic programming (e.g., [Sato and Kameya, 1997]).

In this paper, we focus on the family of relational probability models (RPMs) [Pfeffer, 2000], although our ideas apply equally to other languages. RPMs, like semantic networks, are based on classes containing instances, with each instance possessing attributes. (See Section 2 for details.) RPMs allow one to specify probability distributions over the attribute values of an instance, either directly or via inheritance from classes. These distributions may depend on other attribute values of the instance or of other instances. For example, a PhD student's success may depend on the fame of his or her advisor.

[Pfeffer et al., 1999] describe an exact inference algorithm for RPM knowledge bases called structured variable elimination (SVE). Roughly speaking, SVE applies the variable elimination algorithm [Zhang and Poole, 1996] to a dynamically constructed Bayesian network whose nodes are all those ground propositional variables defined by the knowledge base and relevant to the current query. SVE derives an efficient variable ordering from the structure of the knowledge base and reuses computation results where possible. It is often able to answer queries involving hundreds of variables in a few seconds.

Despite SVE's excellent performance, its runtime is at least exponential in the size of the largest clique in the optimal triangulation of the network. The expressive power of RPMs makes it very easy to construct knowledge bases whose corresponding Bayesian networks have very large cliques. For example, [Pfeffer, 2000] describes a model for matches in a sports league. The knowledge base consists of a single, generic conditional distribution for the outcome of a match given the quality of the two teams, a single prior distribution for the quality of the teams, and the results of some matches. If every team plays every other, then the team qualities form a clique in the corresponding Bayesian network and the inference cost is exponential in the number of teams. Similar problems will arise in any application in which there are complex relationships among large numbers of objects-i.e., precisely those domains for which FOPLs are really necessary.

The situation is exacerbated when the RPM language is extended to allow for structural uncertainty-i.e., uncertainty about which probabilistic dependencies actually exist. We consider two forms of structural uncertainty:

reference uncertainty: the value of a relational attribute may be uncertain-e.g., we may not know which of two professors is the advisor of a certain student;

identity uncertainty: we may not knowwhether two objects in the knowledge base are the same-e.g., when we see a red bus at two different camera locations on the freeway.

Each of these extensions may lead to Bayesian networks whose size alone causes difficulties and whose high connectivity makes exact inference completely impractical. For example, the inference problem in the freeway surveillance application of [Pasula et al., 1999] is known to be #P-hard, i.e., almost certainly exponential in the number of vehicles.

The solution proposed by [Pasula et al., 1999] is to use a Markov chain Monte Carlo (MCMC) algorithm (see Section 3 for details). The algorithm samples from possible matchings among vehicles, converging (in some cases polynomially) to approximately correct probabilities. Often a few hundred samples suffice for a state space of BE BDBCBCBC states. The states being sampled are essentially the possible worlds defined by the constant symbols (observed vehicles) and predicates (equality) of the knowledge base. This approachsampling possible worlds with MCMC-can be turned into a general inference algorithm for first-order probabilistic languages, as suggested by [Russell, 1999; Pfeffer, 2000].

In this paper, we investigate MCMC on possible worlds as an inference method to handle reference uncertainty (Section 4) and identity uncertainty (Section 5). We show how the possible worlds may be constructed dynamically and how the transition probabilities may be computed efficiently. For the case of transitions involving a referentially uncertain relational attribute value, we identify a large family of conditional distributions that render the calculation independent of all but the particular values involved in the transition. We illustrate the algorithms using simple examples and give experimental results suggesting that the algorithms scale well.

2 Relational probability models

The following definitions are adapted from [Koller and Pfeffer, 2000]. A relational probability model, in its most basic form, consists of

• AF A set BV of classes denoting sets of objects, related by subclass/superclass relations.
• AF A set
  of named instances denoting objects, each an instance of one class.
• AF A set BT of complex attributes denoting functional relations. Each complex attribute BT has a domain type BWD3D1CJBTCL BE BV and a range type CACPD2CVCTCJBTCL BE BV.
• AF A set BU of simple attributes denoting functions. Each simple attribute BU has a domain type BWD3D1CJBUCL BE BV and a range that is a finite, enumerated set of values CE CPD0CJBUCL.
• AF A set of conditional probability models B4BUCYCPCJBUCLB5 for the simple attributes. CPCJBUCL is the set of BU's parents, each of which is a nonempty chain of (appropriately typed) attributes AR BP BT BD BM A1 A1 A1 BMBT D2 BMBU BC , where BU BC is a simple attribute. Probability models may be attached to instances or inherited from classes.

For now, we will assume that the values of all the complex attributes are known (no reference uncertainty), and that every instance is distinct (unique names assumption, hence no identity uncertainty). Thus, a possible world is defined by the values of the instance variables-the simple attributes for all named instances.

Consider the following very simple RPM. There are two classes, Student and Professor, and two instances, Student BD and Prof BD . There is one complex attribute, advisor (mapping Student to Professor) and the advisor of Student BD is Prof BD . There are three simple attributes, all Boolean: success of a CBD8D9CSCTD2D8 and fame and $$ (funding level) of a D6D3CUCTD7D7D3D6. For any Student D7, D7BMsuccess has one parent, D7BMadvisorBMfame, with an appropriate conditional distribution. For any Professor D4, D4BMfame has no parents and a simple prior distribution, while D4BM$$ depends on D4BMfame. Figure 1 shows the knowledge base with probability distributions and Figure 2 shows the Bayesian network structure for the attribute variables definable from the knowledge base.

3 Markov chainMonte Carlo algorithms

MCMC [Gilks et al., 1996] generates samples from a posterior distribution APB4DCB5 over possible worlds DC by defining a Markov chain whose states are the worlds DC and whose stationary distribution is APB4DCB5. In the Metropolis-Hastings method (henceforth M-H), transitions in the Markov chain are constructed in two steps:

• AF Given the current state DC, a candidate next state is generated from the proposal distribution D5B4DC BC CYDCB5, which may be (more or less) arbitrary.
• AF The transition to DC BC is not automatic, but occurs with an acceptance probability defined by

It is not necessary that all the variables of state DC be updated simultaneously, in a single transition function. Singlecomponent M-H alters each variable in turn. It is also possible to factor D5 into separate transition functions for various subsets of variables. Provided that D5 is defined in such a way that the chain is ergodic, this transition mechanism defines a Markov chain whose stationary distribution is APB4DCB5.

The Gibbs sampling algorithm for Bayesian networks [Pearl, 1988] is a special case of Metropolis-Hastings in which the proposal distribution samples a single variable CG CX using the distribution B4CG CX CYmbB4CG CX B5B5, where mbB4CG CX B5 denotes the current values of the variables in the Markov blanket of CG CX (its parents CPCJCG CX CL, children CH CY , and children's other parents). In this case, the acceptance probability is always 1. One can show easily that

Gibbs sampling is very simple and also local: transitions are generated referring only to parts of the model directly connected to the variable in question. Hence, the cost per transition is typically independent of model size. M-H sampling is also typically local because all the parts of the model that are not changed by the transition cancel in the ratio APB4DC BC B5BPAPB4DCB5. In particular, if the proposal concerns a single variable CG CX , this ratio reduces to B4DC BC CX CYmbB4CG CX B5B5BPB4DC CX CYmbB4CG CX B5B5, where DC BC CX is the proposed value of CG CX and DC CX is its current value. The M-H algorithm, unlike Gibbs, has the added advantage that the transition may often be computed without referring to the other values of CG CX at all, as we will see.

4 Reference uncertainty

Reference uncertainty arises whenever relations among objects, as described by complex attribute values, are not known with certainty. For example, we may be unsure as to which of three professors is Student BD 's advisor. We need to be able to describe this uncertainty and to specify the dependencies that influence it. The following definitions are adapted from [Pfeffer, 2000]:

• AF With each complex attribute BT, we associate a simple reference attribute D6CTCUCJBTCL, such that CE CPD0CJD6CTCUCJBTCLCL

is a finite, enumerated set of named instances. (Where no confusion arises, we may drop the D6CTCUCJA1CL and use the attribute name itself.) Dependencies are expressed as before by a conditional distribution  B4D6CTCU CJBTCLCY CPCJD6CTCU CJBTCLCLB5. The parents of D6CTCU CJBTCL are those attributes or attribute chains that influence the choice of an instance as the value of attribute BT.

• AF Reference uncertainty modifies the definition of attribute chains. Suppose that an attribute BU depends on the parent chain AR BP BT BD BM A1 A1 A1 BMBT D2 BMBU BC . Any of the complex attributes in the chain may be uncertain. Then the parent variables for BU are all the instance variables reached by the chain for all possible combinations of values of all the uncertain complex attributes, as well as all the reference variables for those attributes.

The simple example of Figure 1 can be extended to include reference uncertainty, if Student BD BMadvisor is unknown. We define a reference attribute D6CTCUCJStudent BD BMadvisorCL with range (say) CUProf BD BN Prof BE BN Prof BF CV. The choice of advisor depends (generically) on the funding (ProfBM$$) of each candidate, which depends (generically) on ProfBMfame. This gives the instance-variable network structure shown in Figure 3. Obviously, when reference attributes have many possible values, very large implicit network structures can result.

4.1 Exact inference with reference uncertainty

As mentioned above, the runtime of any variable elimination algorithm is exponential in the size of the largest clique in the optimally triangulated graph. Looking at Figure 3, it is apparent that a straightforward application leads to two "large" cliques: one containing Student BD BMsuccess and its parents, and one containing D6CTCUCJStudent BD BMadvisorCL and its parents. In general, these will have D2 B7 BE and D2 B7 BD members respectively, where D2 is the number of possible values for the reference attribute. Thus, inference cost grows exponentially with this number.

[Pfeffer, 2000] observes that at least one of these cliquesthe one associated with Student BD BMsuccess-can be decomposed. Given a known value for D6CTCUCJStudent BD BMadvisorCL, Student BD BMsuccess does not depend on the fame of other professors (Figure 4). This is an extreme form of context-specific independence, and allows the D2 B7 BE-variable factor to be replaced by a product of D2 3-variable factors in the variable elimination process. This decomposition applies in general to variables that have referentially uncertain parents.

Unfortunately, the clique associated with the reference attribute itself-D6CTCUCJStudent BD BMadvisorCL in this case-cannot be decomposed. We are left with a network structure that seems (in general) to be intractable for exact inference. The situation becomes worse still as more complex interactions occur among several reference attributes.

4.2 MCMC inference with reference uncertainty

In our approach, we extend the MCMC algorithm commonly used on Bayesian networks by augmenting the Markov chain state space to include reference variables denoting relational uncertainty, and defining appropriate transition functions. Simple attributes, such as Student BD BMsuccess, use Gibbs sampling as usual-and context-specific independence can sometimes be used to simplify those steps further. Reference attributes, such as D6CTCUCJStudent BD BMadvisorCL, depend on a slightly more involved M-H step.

The Gibbs steps

In what follows, we abbreviate Student BD to CB BD , advisor to CP, and so on. Let us consider an extended version of Figure 3 with D2 potential advisors. Let the current value of CB BD BMCP be  CX . Suppose we want to apply Gibbs sampling to  CY BMCU (Prof CY BMfame), where CY BIBP CX. By Equation (1), the sampling distribution is

• BP AB BC B4 CY BMCUB5B4 CY BM$$CY CY BMCUB5

The first step of this derivation uses the fact that CB BD BMD7 depends only on the fame of CB BD 's advisor,  CX BMCU, and not on other professors; the second step simply observes that B4CB BD BMD7CY CX BMCUBN CB BD BMCPBP CX B5 is constant w.r.t.  CY BMCU. Thus, when the reference attribute is instantiated, sampling operates exactly as if the links from non-selected parents were nonexistent. The same holds when sampling a child of the reference variable (e.g., CB BD BMD7). Thus, while reference variables remain constant, the network has a simplified form, such as that shown in Figure 4. MCMC sampling on this simpler network should converge quickly. When the value of the reference variables changes, however, so does the effective structure of the network. We now address this issue.

The Metropolis-Hastings steps

Gibbs sampling for a reference variable with D2 values involves considering D2 possible network structures, so we apply M-H sampling instead. M-H proposes a single new value for the reference variable, and then decides whether to accept it. (We can ignore the proposal distribution, which we will assume for now is uniform and hence cancels.) For the transition from CB BD BMCPBP CX to CB BD BMCPBP CY , then, we need (from Equation (1), and simplifying based on known values of the reference variable) the ratio

At first sight, it seems that calculating this ratio requires accessing the current values of  BD BM$$BN BM BM BM BN  D2 BM$$, i.e., the funding levels of all possible candidate professors, even though the transition involves just two of them. (This is because the probability of picking any one advisor does depend on the funding levels of all candidates.) In turn, this requires that all those nodes be constructed and instantiated, which we prefer to avoid if possible.

It so happens, fortunately, that conditional distributions for "selecting" a value for a relational attribute, given properties of a set of candidates, may have some structural properties that simplify the task. Suppose, for example, that for all CX,

for some arbitrary function CU. Then, in the transition probability ratio given above, the summations  CZ CUB4 CZ BM$$B5 cancel, leaving

which does not mention any values for the reference variable besides  CX and  CY . The property of conditional distributions that we require is satisfied by some well-known conditional distributions, including the softmax distribution:

Softmax is indeed a reasonable model for selecting an advisor based on funding.

The complete algorithm

Once we put the two types of steps together, the complete algorithm alternates between ordinary Gibbs steps on a simplified network and M-H steps altering the network structure. It should be noted that different network structures may result in different sets of variables being, at any given time, relevant or irrelevant to the query. Our approach restricts computation to variables that are strictly relevant [Zhang and Poole, 1996] according to the current structure.

A further possible enhancement is lazy construction of the Bayesian network. The network can, e.g, be grown "from the query outwards", with nodes added as they are needed to sample a node currently in the network. (Structural variables are, like others, instantiated on creation, yielding a network in the usual simplified format.) If necessary, nodes may then be discarded when they become irrelevant to the query under the current network structure. By using an "intelligent" M-H proposal, as discussed in Section 6, we can also focus computation on variables that are "important" to the queryperhaps visiting only an infinitesimal fraction of the potentially relevant variables-without sacrificing the guarantee of convergence to correct probabilities in the limit. This should permit us to apply our approach to very large, or even infinite, knowledge bases.

4.3 Experimental results

To check our algorithm, we applied it first to the knowledge base with reference uncertainty, no identity uncertainty, and three professors. In this case, the algorithm generates and evaluates the network shown in Figure 3. We set values for fame or funding for each professor, and queried the posterior probability of Student BD BMsuccess. In this tiny model, we can compute the exact value for comparison. The MCMC estimates in Figure 5 clearly converge to the correct value.

We also tested the scalability of the algorithm by trying it out on various types of networks of increasing size. As an example, let us consider networks with D2 professors and BGD2B7BD students, each of whom could have any one of the professors as advisor. We specified the success (or otherwise) of BGD2 students and queried the success of the last. Figure 6 shows the inference cost as a function of the total network size. Because we cannot compute the exact values for all D2, we use a standard convergence diagnostic due to [Gelman, 1996], checking against the exact values for small D2. The resulting graph appears to be linear in the size of the network. It would appear that, for this type of network, the sampling algorithm scales well. Note also that cost is measured in terms of singlevariable state transitions performed by the algorithm, hence the number of transitions per variable to reach convergence is approximately constant, regardless of network size. This held in all our experiments, including experiments (not reported here) on genetic inheritance with uncertain parentage, where the number of cascaded reference variables increases with D2.

5 Identity uncertainty

Standard relational probability models [Pfeffer, 2000] incorporate the unique names assumption, i.e., the assumption that each instance present in the knowledge base corresponds to a different object in any given possible world. When this assumption is removed, we must consider the possibility that several instances may denote the same object. Identity uncertainty is especially prevalent in settings where an agent perceives multiple objects over time [Pasula et al., 1999], but also occurs in almost all real databases where "duplicate" records abound.

With identity uncertainty, a "possible world" must specify not only the attribute values for all objects, but also the mapping from instances in the knowledge base to objects in the possible world. (Without identity uncertainty, this mapping is one-to-one and hence no distinction between instances and objects is needed.) We represent this mapping using an equivalence relation-a set of equivalence classes, each of which contains all the instances that co-refer in that particular possible world. 1

Consider the following example, a simplified version of the data association problem studied by [Pasula et al., 1999]. There are two classes, CE CTCWCXCRD0CT and CQD7CTD6DACPD8CXD3D2. There is one complex attribute, CVCTD2CTD6CPD8CTCS CQDD, which maps an CQD7CTD6DACPD8CXD3D2 to the CE CTCWCXCRD0CT that generated it. Each CQD7CTD6DACPD8CXD3D2 of a vehicle reports a CRD3D0D3D9D6, which depends (through a probabilistic model of the sensing process) on the CRD3D0D3D9D6 of the corresponding CE CTCWCXCRD0CT. Instances are added to the KB as follows: whenever a vehicle is detected at some sensor, an CQD7CTD6DACPD8CXD3D2 is instantiated with its colour set to the measured value, and with a new CE CTCWCXCRD0CT instance attached. In this domain, inference involves reasoning about which CE CTCWCXCRD0CTs are, in fact, identical. 2

1 Note that it doesn't matter which object the instances denoteobjects are essentially placeholders in a relational structure.

Figure 7 shows the Bayesian network structure generated when the knowledge base contains observations CQD7 BD and CQD7 BE of vehicles CE CTCW BD and CE CTCW BE , and when the equivalence relation on instances is set to CUCUCE CTCW BD BN CE CTCW BE CVCV (i.e., CE CTCW BD and CE CTCW BE are the same object).

5.1 Defining a probability distribution

Each possible world now contains an equivalence relation AX BE AA as well as the attribute values, and the knowledge base must now specify a unique probability distribution over this enlarged space of worlds. We can write

Given each fixed AX, identity uncertainty is eliminated, and the probability distribution over the attributes can be defined as before. All that remains is to specify the prior  B4AXB5. When doing so, we can use the fact that instances in disjoint classes cannot co-refer-for example, vehicles cannot be observations.  B4AXB5 can thus be factored into terms dealing with each of the classes. Even then, however, the state space of each factor is exponential in the number of objects in its class. Fortunately, there are more compact ways of expressing the AX-distribution for each class. The simplest is to give an explicit distribution over the number of objects in each class, which can be done by adding a number attribute to classes in the knowledge base. In more complex situations, such as full data association, the AX-distributions are specified implicitly in conjunction with object arrival and detection models [Pasula et al., 1999]. The general topic of modular specification of AX-distributions is likely to require a good deal of further research.

5.2 Inference with identity uncertainty

In the presence of identity uncertainty, exact inference calls for a summation over all possible values of AX. This is clearly infeasible when CYAACY is large-and CYAACY is exponential in the number of instances in identity-uncertain classes. MCMC

2 An alternative interpretation for this knowledge base, more familiar to statisticians, is that there are an unknown number of balls in a bag; balls are pulled out one at a time, their colour is measured, and they are replaced.

permits us to replace the summation with a sample. The algorithm now works as follows. In addition to "normal transitions," which run as before given a fixed AX, the algorithm performs "identity transitions" in which AX changes. Because of the large state space of AX, the latter type of transition uses M-H steps. Moreover, these steps propose changes not only to AX, but also to some of the conventional attributes.

The reason for this is that an identity transition can propose (among other things) that two currently separate instances be grouped together in the same equivalence class. Clearly, if these two instances currently have different values for the same attribute, the probability of the destination state will be zero. Hence, identity transitions will have a chance of occurring only when the instances "line up"-that is, a sequence of normal transitions causes all of their attribute values to match exactly. When instances have many attributes, line-up may be very rare, resulting in a low acceptance ratio and a slow algorithm. Moreover, there are cases in which waiting for line-up makes the Markov chain non-ergodic-the algorithm can be trapped in a subset of possible AXs with no escape.

Identity transition proposals

Consider a current assignment AX, and a proposed assignment AX BC . Let D9 be the set of unobserved attributes of all the objects in AX affected by the transition, and let D9 BC be the unobserved attributes of the corresponding objects in AX BC . Let D3 be the set of all other attributes within the Markov blankets of the attributes in D9 or D9 BC : this may include observed attributes, as well as the unobserved attributes of other objects not affected by the transition. Note that all attributes in D3 remain fixed throughout the transition.

Each identity transition proceeds as follows:

• AF AX BC is chosen using a proposal D5
  B4AX BC CYAXB5. This proposal can take many forms: one simple possibility is to suggest that a randomly selected instance move from one equivalence class to another. Another method might suggest merging two equivalence classes, or splitting an equivalence class in two.
• AF Values for all of D9 BC are chosen using a proposal D5 CD B4D9 BC CYAX BC BN AXBN D9BN D3B5. Some possible choices for D5 CD will be explained below.
• AF The proposed change is accepted with probability

which is derived from Equation (3) using Equation (2) and the two-step nature of our proposal.

As an example, let us consider the world state portrayed in Figure 7. In this situation,

• AF AX BP CUCUCE CTCW BD BN CE CTCW BE CVCV
• AF D9 BP CUCUCE CTCW BD BN CE CTCW BE CVBMCRD3D0D3D9D6BN CUCE CTCW BD BN CE CTCW BE CVBMD7CXDECTCV

A split can now be proposed as follows:

• AF AX BC BP CUCUCE CTCW BD CVBN CUCE CTCW BE CVCV
• AF D9 BC BP CUCE CTCW BD BMCRD3D0D3D9D6BN CE CTCW BE BMCRD3D0D3D9D6BN CE CTCW BD BMD7CXDECTBN CE CTCW BE BMD7CXDECTCV

To ensure that the chain is ergodic, new values must then be proposed by D5 CD for at least the newly created attributes.

Choosing the attribute values

One possible D5 CD proposal picks a value uniformly at random from the values available at each attribute. This approach is simple to implement and yields an acceptance ratio that is easy to calculate. The D5 CD B4D9CY BM BM BMB5 terms reduce to BDBP  D9 CX CYD9 CX CY. This is the algorithm that we test experimentally below.

Unfortunately, this D5 CD proposal may suggest very unlikely value combinations for the attributes, resulting in low acceptance ratios. We might be better off with a more intelligent proposal mechanism, such as likelihood weighting which generates samples from D5 CD B4D9CYD3BN AXB5 BP DC CX BED9 B4DC CX CYCPB4DC CX B5BN AXB5 together with weights DBB4D9CYD3BN AXB5 BP DC CX BED3 B4DC CX CYCPB4DC CX B5BN AXB5. Since

the fraction in the acceptance ratio can now cancel to give

This ratio is no longer so simple, as performing the summations may be quite time-consuming. Fortunately, whenever the set of uncertain attributes can be split into several d-separated sets, the summations can be rewritten as products of summations over these sets. If the sets are all small, this algorithm may be feasible.

Yet another approach is to run a "local" MCMC algorithm inside D5 CD to generate attribute values that reflect the current values of D3 and hence are likely to be accepted. (When this method is used, care must be taken to ensure that the chain is run until convergence: stopping it prematurely may result in biased answers.)

5.3 Experimental results

To check our identity uncertainty algorithm, we first performed experiments analogous to those in Section 4.3. We began with a problem that was small enough for exact calculation: it consisted of five observations with known attribute values, and queried the posterior probability of the vehicle generating the first observation. Figure 8 shows that our algorithm's estimates converge to the correct value over time.

We then tested the scalability of the algorithm by, once more, applying it to randomly generated networks of increasing size, and measuring time to convergence using a standard diagnostic. The results shown in Figure 9 were obtained by constructing larger and larger sets of vehicle-observation pairs, and requesting a posterior distribution over the number of vehicles. As before, the algorithm appears to scale well.

Finally, we performed an additional experiment to demonstrate that our algorithmworks as expected. It should be true that, if observations are generated from a specific set of vehicles, increasing the number of observations in the knowledge base will enable us to model characteristics of that set of vehicles with increasing accuracy. Figure 10 shows that adding more and more observations does enable us to infer the number of vehicles responsible for their generation.

6 Conclusions and further work

We have proposed an algorithmic approach for inference in first-order probabilistic languages, based on Markov chain Monte Carlo. Our preliminary investigations suggest that the approach is very promising. We believe that it can significantly increase the expressive power of languages that can be considered "practical" for knowledge representation and reasoning under uncertainty. For example, the lazy exploration approach should make it possible to handle infinite recursive models, including temporal models, with somewhat greater generality than so far envisaged [Koller and Pfeffer, 2000].

The Metropolis-Hastings algorithm allows for a wide variety of proposal distributions. In particular, intelligent proposals can be used to focus computation. One can easily construct data-driven and query-driven proposals, analogous to forward and backward chaining in logical systems, that essentially result in "activation" spreading outwards from query and evidence variables. These concepts can be subsumed by a general mechanism for proposing transitions based on the expected value of computation [Russell and Wefald, 1991]. We can also insert arbitrary domain-specific knowledge into the proposal mechanism-for example, proposing candidate advisors based on the student's research interest. Such knowledge-based proposals, which result in faster convergence, can also be learned via so-called adaptive proposalsthat is, allowing the proposal distribution D5 to change over time based on the algorithm's experience in generating samples and computing acceptances.

Clearly, we have just scratched the surface of this topic. A large effort is needed to apply first-order probabilistic languages to real problems, in order to identify useful language features, common representation structures, and their effect on inference. Having a flexible and general-albeit sometimes slow-MCMC inference engine should help with this task. Finally, we also need to develop complexity results for approximate inference, using tools such as those provided by [Jerrum and Sinclair, 1997].