Learning Probabilistic Relational Models

1 Introduction

Relational models are the most common representation of structured data. Enterprise business information, marketing and sales data, medical records, and scientific datasets are all stored in relational databases. Indeed, relational databases are a multi-billion dollar industry. Recently, there has been grow­ ing interest in making more sophisticated use of these huge amounts of data, in particular mining these databases forcer­ tain patterns and regularities. By explicitly modeling these regularities, we can gain a deeper understanding of our do­ main and may discover useful relationships. We can also use our model to "fill in" unknown but important information. For

*The Institute of Computer Science, Hebrew University, Jerusalem 91904, ISRAEL

t Computer Science Department, Stanford University, Gates Building lA, Stanford CA 94305-9010

Daphne Kollert

AviPfeffert

Stanford University koller@cs.stanford.edu Stanford University a vi @cs.stanford.edu

example, we may be interested in predicting whether a person is a potential money-launderer based on their bank deposits, international travel, business connections and arrest records of known associates [Jensen, 1997]. In another case, we may be interested in classifying web pages as belonging to a stu­ dent, a faculty member, a project, etc., using attributes of the web page and of related pages [Craven et al., 1998].

Unfortunately, few inductive learning algorithms are capa­ ble of handling data in its relational form. Most are restricted to dealing with a flat set of instances, each with its own sepa­ rate attributes. To use these methods, one typically "flattens" the relational data, removing its richer structure. This pro­ cess, however, loses information which might be crucial in understanding the data. Consider, for example, the problem of predicting the value of an attribute of a certain entity, e.g., whether a person is a money-launderer. This attribute will be correlated with other attributes of this entity, as well as with attributes of related entities, e.g., of financial transac­ tions conducted by this person, of other people involved in these transactions, of other transactions conducted by these people, etc. In order to "flatten" this problem, we would need to decide in advance on a fixed set of attributes that the learn­ ing algorithm can use in this task. Thus, we want a learning algorithm that can deal with multiple entities and their prop­ erties, and can reach conclusions about an entity's character­ istics based on the properties of the entities to which it is re­ lated. Until now, inductive logic programming (ILP) [Lavrac and Dzeroski, 1994] has been the primary learning frame­ work with this capability. ILP algorithms learn logical Hom rules for determining when some first-order predicate holds. While ILP is an excellent solution in many settings, it may be inappropriate in others. The main limitation is the determin­ istic nature of the rules discovered. In many domains, such as the examples above, we encounter interesting correlations that are far from being deterministic.

Our goal in this paper is to learn more refined probabilis­ tic models, that represent statistical correlations both between the properties of an entity and between the properties of re­ lated entities. Such a model can then be used for reasoning about an entity using the entire rich structure of knowledge encoded by the relational representation.

The starting point for our work is the structured representa­ tion of probabilistic models, as exemplified in Bayesian net­ works (BNs). A BN allows us to provide a compact representation of a complex probability distribution over some fixed set of attributes or random variables. The representa­ tion exploits the locality of influence that is present in many domains. We build on two recent developments in the field of Bayesian networks. The first is the deep understanding of the statistical learning problem in such models [Hecker­ man, 1998; Heckerman et al., 1995] and the role of struc­ ture in providing an appropriate bias for the learning task. The second is the recent development of representations that extend the attribute-based BN representation to incorporate a much richer relational structure [Koller and Pfeffer, 1998; Ngo and Haddawy, 1996; Poole, 1993].

In this paper, we combine these two advances. Indeed, one of our key contributions is to show that many of the tech­ niques of Bayesian network learning can be extended to the task of learning these more complex models. This contribu­ tion generalizes [Koller and Pfeffer, 1997l's preliminary work on this topic. We start by describing the semantics of proba­ bilistic relational models. We then examine the problems of parameter estimation and structure selection for this class of models. We deal with some crucial technical issues that dis­ tinguish the problem of learning relational probabilistic mod­ els from that of learning Bayesian networks. We provide a formulation of the likelihood function appropriate to this set­ ting, and show how it interacts with the standard assumptions of BN learning. The search over coherent dependency struc­ tures is significantly more complex than in the case of learn­ ing BN structure and we introduce the necessary tools and concepts to do this effectively. We then describe experimen­ tal results on synthetic and real-world datasets, and finally discuss possible extensions and applications.

2 Underlying framework

2.1 Relational model

We describe our relational model in generic terms, closely re­ lated to the language of entity-relationship models. This gen­ erality allows our framework to be mapped into a variety of specific relational systems, including the probabilistic logic programs of [Ngo and Haddawy, 1996; Poole, 1993], and the probabilistic frame systems of [Koller and Pfeffer, 1998]. Our learning results apply to all of these frameworks.

The vocabulary of a relational model consists of a set of classes X 1, .. . , X n and a set of relations R1, . . . , Rm. Each entity type is associated with a set of attributes A(Xi). Each attribute Aj E A(Xi ) takes on values in some fixed domain of values V ( Aj). Each relation R is typed. This vocabulary defines a schema for our relational model.

Consider a simple genetic model of the inheritance of a single gene that determines a person's blood type. Each per­ son has two copies of the chromosome containing this gene, one inherited from her mother, and one inherited from her fa­ ther. There is also a possibly contaminated test that attempts to recognize the person's blood type. Our schema contains two classes Person and Blood-Test, and three relations Father, Mother, and Test-of. Attributes of Person are Name, Gender, ?-Chromosome (the chromosome inherited from the father), M-Chromosome (inherited from the mother). The attributes of Blood-Test are Serial-Number, Date, Contaminated, and Result.

An instance I of a schema defines a set of entities (JL (Xi) for each entity type x i. For each entity X E oi (Xi), and each attribute AJ E A(Xi) , the instance has an associated at­ tribute x.aj; its value in I is denoted I x.a 1 · For each relation R~X1, ... , Xk) and each (x1 , ... ,xk) E oi(X1) X . . . X 0 (Xk), I specifies whether R(x1, . . . , xk ) holds.

We are interested in describing a probability model over instances of a relational schema. However, some attributes, such as a name or social security number, are fully deter­ mined. We label such attributes as fixed. We assume that they are known in any instantiation of the schema. The other attributes are called probabilistic. A skeleton structure CJ of a relational schema is a partial specification of an instance of the schema. It specifies the set of objects 0" (Xi ) for each class, the values of the fixed attributes of these objects, and the relations that hold between the objects. However, it leaves the values of probabilistic attributes unspecified. A comple­ tion I of the skeleton structure CJ extends the skeleton by also specifying the values of the probabilistic attributes.

One final definition which will tum out to be useful is the notion of a slot chain. If R( X 1 , .. . , X k) is any relation, we can project R onto its i -th and j-th arguments to obtain a binary relation p(Xi , X j ), which we can then view as a slot of x i. For any X in Xi, we let x .p denote all the elements y in Xj such that p(x, y) holds. (In relational algebra notation x.p = IIx 1 CJX;=x R .) Objects in this set are called p-relatives of x. We can concatenate slots to form longer slot chains r = p1 . · · · ·Pm, defined by composition of binary relations. (Each of the Pi's in the chain must be appropriately typed.)

2.2 Probabilistic Relational Models

We now proceed to the definition of probabilistic relational models (PRMs). The basic goal here is to model our uncer­ tainty about the values of the non-fixed, or probabilistic, at­ tributes of the objects in our domain of discourse. In other words, given a skeleton structure, we want to define a proba­ bility distribution over all completions of the skeleton.

Our probabilistic model consists of two components: the qualitative dependency structure, S , and the parameters as­ sociated with it, Bs. The dependency structure is defined by associating with each attribute X .A a set of parents Pa(X.A). These correspond to formal parents; they will be instantiated in different ways for different objects in X. Intuitively, the parents are attributes that are "direct influences" on X.A.

We distinguish between two types of formal parents. The attribute X .A can depend on another probabilistic attribute B of X . This formal dependence induces a corresponding de­ pendency for individual objects: for any object x in 0" (X), x.a will depend probabilistically on x.b. The attribute X.A can also depend on attributes of related objects X .r .B, where r is a slot chain. To understand the semantics of this formal dependence for an individual object x, recall that x.r repre­ sents the set of objects that are r-relatives of x . Except in cases where the slot chain is guaranteed to be single-valued, we must specify the probabilistic dependence of x.a on the multiset {y.b : y E x.r}. The notion of aggregation from database theory gives us precisely the right tool to address this issue; i.e., x.a will depend probabilistically on some ag­ gregate property of this multiset. There are many natural and useful notions of aggregation: the mode of the set (most fre­ quently occurring value); mean value of the set (if values are numerical); median, maximum, or minimum (if values are ordered); cardinality of the set; etc.

More formally, our language allows a notion of an aggre­ gate 1 ; 1 takes a multiset of values of some ground type, and returns a summary of it. The type of the aggregate can be the same as that of its arguments. However, we allow other types as well, e.g., an aggregate that reports the size of the multiset. We allow X.A to have as a parent 1(X.r.B); the semantics is that for any x E X, x .a will depend on the value of 1(x.r .b). We define V('Y(X.r.b)) in the obvious way.

Returning to our genetics example, consider the attribute Blood-Test.Result. Since the result of a blood test depends on whether it was contaminated, it has Blood-Test.Contaminated as a parent. The result also depends on the ge­ netic material of the person tested. Since Test-of is single-valued, we add Blood-Test.Test-of.M-Chromosome and Blood-Test.Test-of.P-Chromosome as parents. Figure 1 shows the structure of a simple PRM for this domain.

Given a set of parents Pa(X.A) for X.A, we can define a local probability model for X.A. We associate X.A with a conditional probability distribution (CPD) that specifies P(X.A I Pa(X.A)). More precisely, let U be the set of par­ ents of X.A. Recall that each of these parents Ui- whether a simple attribute in the same relation or an aggregate of a set of r relatives- has a set of values V(Ui) in some ground type. For each tuple of values u E V(U), the CPO specifies a distribution P(X.A I u) over V(X.A). The parameters in all of these CPDs comprise B s.

Given a skeleton structure for our schema, we want to use these local probability models to define a probability distri­ bution over completions of the skeleton. First, note that the skeleton determines the set of objects in our model. We asso­ ciate a random variable x.a with each probabilistic attribute A of each object x. The skeleton also determines the relations between objects, and thereby the set of r-relatives associated with every object for each relationship chain r. Also note that by assuming that the relations between objects are al­ ways specified by a, we are disallowing uncertainty over the relational structure of the model.

To define a coherent probabilistic model over this skele­ ton, we must ensure that our probabilistic dependencies are acyclic, so that a random variable does not depend, directly or indirectly, on its own value. Consider the parents of an attribute X.A. When X.B is a parent of X.A, we define an edge x.b -+11 x.a; when 1(X.r.B) is a parent of X.A and y E x.r, we define an edge y.b -+11 x.a. We say that a dependency structure S is acyclic relative to a skeleton a if the directed graph defined by -+11 over the variables x.a is acyclic. In this case, we can define a coherent probabilistic model over complete instantiations I consistent with a :

Proposition 2.1: If S is acyclic relative to a, then ( 1) defines a distribution over completions I of a.

We briefly sketch a proof of this proposition, by showing how to construct a BN over the probabilistic attributes of a skeleton using (S,Bs). This construction is reminiscent of the knowledge-based model construction approach [Wellman et al., 1992]. Here, however, the construction is merely a thought-experiment; our learning algorithm never constructs this network. In this network there is a node for each vari­ able x.a and for aggregate quantities required by parents. The parents of these aggregate random variables are all of the at­ tributes that participate in the aggregation, according to the relations specified by a . The CPDs of random variables that correspond to probabilistic attributes are simply the CPDs de­ scribed by Bs, and the CPDs of random variables that corre­ spond to aggregate nodes capture the deterministic function of the particular aggregate operator. It is easy to verify that if the probabilistic dependencies are acyclic, then so is the induced Bayesian network. This construction also suggests one way of answering queries about a relational model. We can "compile" the corresponding Bayesian network and use standard tools for answering queries about it.

Although for each skeleton, we can compile a PRM into a Bayesian network, a PRM expresses much more information than the resulting BN. A BN defines a probability distribution over a fixed set of attributes. A PRM specifies a distribution over any skeleton; in different skeletons, the set (and num­ ber) of entities in the domain will vary, as will the relations between the entities. In a way, PRMs are to BNs as a set of rules in first-order logic is to a set of rules in propositional logic: A rule such as \:lx, y, z.Parent(x, y) 1\ Parent(y , z) => Grandparent( x, z) induces a potentially infinite set of ground (propositional) instantiations.

3 Parameter Estimation

We now move to the task of learning PRMs. We begin with learning the parameters for a PRM where the dependency structure is known. In other words, we are given the structure S that determines the set of parents for each attribute, and our task is to learn the parameters Bs that define the CPDs for this structure. Our learning is based on a particular training set, which we will take to be a complete instance I. While this task is relatively straightforward, it is of interest in and of itself. In addition, it is a crucial component in the structure learning algorithm described in the next section.

The key ingredient in parameter estimation is the likelihood function, the probability of the data given the model. This function captures the response of the probability distribution to changes in the parameters. As usual, the likelihood of a parameter set is defined to be the probability of the data given the model: L(Bs I I,a,S) = P(I I a,S,Bs). As usual, we typically work with the log of this function:

The key insight is that this equation is very similar to the log-likelihood of data given a Bayesian network [Heck­ erman, 1998]. In fact, it is the likelihood function of the Bayesian network induced by the structure given the skele­ ton. The main difference from standard Bayesian network parameter learning is that parameters for different nodes in the network are forced to be identical. Thus, we can use the well-understood theory of learning from Bayesian networks. Consider the task of performing maximum likelihood param­ eter estimation. Here, our goal is to find the parameter set­ ting Bs that maximizes the likelihood L(Bs I I, a, S) for a given I, a and S. This estimation is simplified by the de­ composition of log-likelihood function into a summation of terms corresponding to the various attributes of the different classes. Each of the terms in the square brackets in (2) can be maximized independently of the rest. Hence, maximal likeli­ hood estimation reduces to independent maximization prob­ lems, one for each CPD.

For multinomial CPDs, maximum likelihood estimation can be done via sufficient statistics which in this case are just the counts C x.A [v, u] of the different values v, u that the at­ tribute X. A and its parents can jointly take.

Proposition 3.1: Assuming multinomial CPDs, the maximum likelihood parameter setting Bs is

As a consequence of this proposition, parameter learning in PRMs is reduced to counting sufficient statistics. We need to count one vector of sufficient statistics for each CPD. Such counting can be done in a straightforward manner using stan­ dard databases queries.

Note that this proposition shows that learning parameters in PRMs is very similar to learning parameters in Bayesian net­ works. In fact, we might view this as learning parameters for the BN that the PRM induces given the skeleton. However, as discussed above, the learned parameters can then be used for reasoning about other skeletons, which induce a completely different BN.

In many cases, maximum likelihood parameter estimation is not robust, as it overfits the training data. The Bayesian ap­ proach uses a prior distribution over the parameters to smooth the irregularities in the training data, and is therefore sig­ nificantly more robust. As we will see ih Section 4.2, the Bayesian framework also gives us a good metric for evaluat­ ing the quality of different candidate structures. Due to space limitations, we only briefly describe this alternative approach.

Roughly speaking, the Bayesian approach introduces a prior over the unknown parameters, and performs Bayesian conditioning, using the data as evidence, to compute a poste­ rior distribution over these parameters. To apply this idea in our setting, recall that the PRM parameters Bs are composed of a set of individual probability distribution B X. AIV for each conditional distribution of the form P(X.A I Pa(X.A) = u). Following the work on Bayesian approaches for learn­ ing Bayesian networks [Heckerman, 1998], we make two as­ sumptions. First, we assume parameter independence: the priors over the parameters eX.AIV for the different X, A and v are independent. Second, we assume that the prior over e X.AIV is a Dirichlet distribution. Briefly, a Dirichlet prior for a multinomial distribution of a variable W is specified by a set of hyperparameters {a[w] :wE v(W)}. A distribution on the parameters of P(W) is Dirichlet if Pr(Bw) ex Tiw e~[wl . (For more details see [DeGroot, 1970].)

For a parameter prior satisfying these two assumptions, the posterior also has this form. That is, it is a product of inde­ pendent Dirichlet distributions over the parameters e X.AIV' which can be computed easily.

Proposition 3.2: If I is a complete assignment, and the prior satisfies parameter independence and Dirichlet with hyper­ parameters ax.A[v, u], then the posterior P(Bs I I,a,S) is a product of Dirichlet distributions with hyperparameters a' x.A[v, u] = ax.A[v, u] + Cx.A[v, u].

Once we have updated the posterior, how do we evaluate the probability of new data? In the case of BN learning, we assume that instances are liD, which implies that they are in­ dependent given the value of the parameters. Thus, to evalu­ ate a new instance, we only need the posterior over the param­ eters. The probability of the new instance is then the proba­ bility given every possible parameter value, weighted by the posterior probability over these values. In the case of BNs, this term can be rewritten simply as the instance probabil­ ity according to the expected value of the parameters (i.e., the mean of the posterior Dirichlet for each parameter). This sug­ gests that we might use the expected parameters for evaluat­ ing new data. Indeed, the formula for the expected parameters is analogous to the one for BNs:

Proposition 3.3: Assuming multinomial CPDs, prior in­ dependence, and Dirichlet priors, with hyperparameters ax.A[v, u], we have that:

Unfortunately, the expected parameters are not the proper Bayesian solution for computing probability of new data. There are two possible complications.

The first problem is that, in our setting, the assumption of liD data is often violated. Specifically, a new instance might not be conditionally independent of old ones given the param­ eters. Consider the genetics domain, and assume that our new data involves information about the mother x' of some per­ son x already in the database. In this case, the introduction of the new object x' also changes our probability about the attributes of x': We therefore cannot simply use our old pos­ terior about the parameters to reason about the new instance. This problem does not occur if the new data is not related to the training data, that is, when the new data is essentially a disjoint database with the same scheme. More interestingly, the problem also disappears when attributes of new objects are not parents of any attribute in the training set. In the ge­ netics example, this means that we can insert new people into our database, as long as they are not ancestors of people al­ ready in the database.

The second problem involves the formal justification for using expected parameters values. This argument depends on the fact that the probability of a new instance is linear in the value of each parameter. That is, each parameter is "used" at most once. This assumption is violated when we consider the probability of a complex database involving multiple in­ stances from the same class. In this case, our integral of the probability of the new data given the parameters can no longer be reduced to computing the probability relative to the ex­ pected parameter value. The correct expression is called the marginal likelihood of the (new) data; we use it in Section 4.2 for scoring structures. For now, we note that if the posterior is sharply peaked (i.e., we have seen many training instances), we can approximate this term by using the expected parame­ ters of Proposition 3.3, as we could for a single instance. In practice, we will often use these expected parameters as our learned model.

4 Structure selection

We now move to the more challenging problem of learning a dependency structure automatically, as opposed to having it given by the user. There are three important issues that need to be addressed. We must determine which dependency struc­ tures are legal; we need to evaluate the "goodness" of differ­ ent candidate structures; and we need to define an effective search procedure that finds a good structure.

4.1 Legal structures

When we consider different dependency structures, it is im­ portant to be sure that the dependency structure S we choose results in coherent probability models. To guarantee this property, we see from Proposition 2.1 that the skeleton a must be acyclic relative to S. Of course, we can easily verify for a given candidate structure S that it is acyclic relative to the skeleton a of our training database. However, we also want to guarantee that it will be acyclic relative to other databases that we may encounter in our domain. How do we guarantee acyclicity for an arbitrary database? A simple approach is to ensure that dependencies among attributes respect some order (i.e., are stratified). More precisely, we say that X.A directly depends on Y.B if either (a) X = Y and X.B is a parent of X.A, or (b) r(X.T.B) is a parent of X.A and the T-relatives of X are of class Y. We then require that X.A directly de­ pends only on attributes that precede it in the order.

While this simple approach clearly ensures acyclicity, it is too limited to cover many important cases. Con­ sider again our genetic model. Here, the genotype of a person depends on the genotype of her parents; thus, we have Person.P-Chromosome depending directly on Person.P-Chromosome, which clearly violates the require­ ments of our simple approach. In this model, the appar­ ent cyclicity at the attribute level is resolved at the level of individual objects, as a person cannot be his/her own an­ cestor. That is, the resolution of acyclicity relies on some prior knowledge that we have about the domain. To allow our learning algorithm to deal with dependency models such as this we must allow the user to give our algorithm prior knowledge. We allow the user to assert that certain slots R 9 a = {PI, ... , pk} are guaranteed acyclic; i.e., we are guaranteed that there is a partial ordering -( 9 a such that if y is a p-relative for some p E R 9 a of x, then y -( 9 a x. We say that T is guaranteed acyclic if each of its components p's is guaranteed acyclic.

We use this prior knowledge determine the legality of cer­ tain dependency models. We start by building a graph that describes the direct dependencies between the attributes. In this graph, we have a yellow edge X.B -7 X.A if X.B is a parent of X.A. If r(X.T.B) is a parent of X.A, we have an edge Y.B -7 X.A which is green if T is guaranteed acyclic and red otherwise. (Note that there might be several edges, of different colors, between two attributes). The intuition is that dependency along green edges relates objects that are or­ dered by an acyclic order. Thus these edges by themselves or combined with intra-object dependencies (yellow edges) can­ not cause a cyclic dependency. We must take care with other dependencies, for which we do not have prior knowledge, as these might form a cycle. This intuition suggests the follow­ ing definition: A (colored) dependency graph is stratified if every cycle in the graph contains at least one green edge and no red edges.

Proposition 4.1: If the colored dependency graph of Sand R 9 a is stratified, then for any skeleton a for which the slots in R 9 a are jointly acyclic, S defines a coherent probability distribution over assignments to a.

This notion of stratification generalizes the two special cases we considered above. When we do not have any guaran­ teed acyclic relations, all the edges in the dependency graph are colored either yellow or red. Thus, the graph is strati­ fied if and only if it is acyclic. In the genetics example, all the relations would be in R 9 a. Thus, it suffices to check that dependencies within objects (yellow edges) are acyclic.

Proposition 4.2: Stratification of a colored graph can be de­ termined in time linear in the number of edges in the graph.

We omit the details of the algorithm for lack of space, but it relies on standard graph algorithms. Finally, we note that it is easy to expand this definition of stratification for situations where our prior knowledge involves several sets of guaran­ teed acyclic relations, each set with its own order (e.g., ob­ jects on a grid with a north-south ordering and an east-west ordering). We simply color the graph with several colors, and check that each cycle contains edges with exactly one color other than yellow, except for red.

4.2 Evaluating different structures

Now that we know which structures are legal, we need to de­ cide how to evaluate different structures in order to pick one that fits the data well. We adapt Bayesian model selection methods to our framework. Formally, we want to compute the posterior probability of a structure S given an instantia­ tion I. Using Bayes rule we have that P(S I I, a) <X P(I I S ,a)P(S I a). This score is composed of two main parts: the prior probability of the structure, and the probability of the data assuming that structure.

The first component is P(S I a), which defines a prior over structures. We assume that the choice of structure is in­ dependent of the skeleton, and thus P(S I a) = P(S) . In the context of Bayesian networks, we often use a simple uniform prior over possible dependency structures. Unfortunately, this assumption does not work in our setting. The problem is that there may be infinitely many possible structures. In our ge­ netics example, a person's genotype can depend on the geno­ type of his parents, or of his grandparents, or of his great­ grandparents, etc. A simple and natural solution penalizes long indirect slot chains, by having log P(S) proportional to the sum of the lengths of the chains r appearing inS.

The second component is the marginal likelihood:

If we use a parameter independent Dirichlet prior (as above, this integral decomposes into a product of integrals each of which has a simple closed form solution. (This is a sim­ ple generalization of the ideas used in the Bayesian score for Bayesian networks.)

Proposition 4.3: If I is a complete assignment, and P(Bs I S) satisfies parameter independence and is Dirichlet with hy­ perparameters ax.A[v, u], then, P(I I S, a) , the marginal likelihood ofi givenS, is equal to

where

Hence, the marginal likelihood is a product of simple terms, each of which corresponds to a distribution P(X.A I u) where u E V(Pa(X.A)). Moreover, the term for P(X.A I u) depends only on the hyperparameters ax.A[v , u] and the sufficient statistics Cx.A[v, u] for v E V(X.A).

The marginal likelihood term is the dominant term in the probability of a structure. It balances the complexity of the structure with its fit to the data. This balance can be made explicitly via the asymptotic relation of the marginal likeli­ hood to explicit penalization, such as the MDL score (see, e.g., [Heckerman, 1998]).

Finally, we note that the Bayesian score requires that we assign a prior over parameter values for each possible struc­ ture. Since there are many (perhaps infinitely many) alter­ native structures, this is a formidable task. In the case of Bayesian networks, there is a class of priors that can be de­ scribed by a single network [Heckerman et al., 1995]. These priors have the additional property of being structure equiva­ lent, that is, they guarantee that the marginal likelihood is the same for structures that are, in some strong sense, equivalent. These notions have not yet been defined for our richer struc­ tures, so we defer the issue to future work. Instead, we simply assume that some simple Dirichlet prior (e.g., a uniform one) has been defined for each attribute and parent set.

4.3 Structure search

Now that we have a test for determining whether a structure is "legal", and a scoring function that allows us to evaluate dif­ ferent structures, we need only provide a procedure for find­ ing legal high-scoring structures. For Bayesian networks, we know that this task is NP-Hard [Chickering, 1996]. As PRM learning is at least as hard as BN learning (a BN is simply a PRM with one class and no relations), we cannot hope to find an efficient procedure that always finds the highest scoring structure. Thus, we must resort to heuristic search. The sim­ plest such algorithm is greedy hill-climbing search, using our score as a metric. We maintain our current candidate structure and iteratively improve it. At each iteration, we consider a set of simple local transformations to that structure, score all of them, and pick the one with highest score. We deal with local maxima using random restarts.

As in Bayesian networks, the decomposability property of the score has significant impact on the computational ef­ ficiency of the search algorithm. First, we decompose the score into a sum of local scores corresponding to individual attributes and their parents. Now, if our search algorithm con­ siders a modification to our current structure where the parent set of a single attribute X.A is different, only the component of the score associated with X .A will change. Thus, we need only reevaluate this particular component, leaving the others unchanged; this results in major computational savings.

There are two problems with this simple approach. First, as discussed in the previous section, we have infinitely many possible structures. Second, even the atomic steps of the search are expensive; the process of computing sufficient statistics requires expensive database operations. Even if we restrict the set of candidate structures at each step of the search, we cannot afford to do all the database operations nec­ essary to evaluate all of them.

We propose a heuristic search algorithm that addresses both these issues. At a high level, the algorithm proceeds in phases. At each phase k, we have a set of potential parents Potk(X.A) for each attribute X .A . We then do a standard structure search restricted to the space of structures in which the parents of each X.A are in Potk(X.A). The advantage of this approach is that we can precompute the view corresponding to X.A, Potk(X.A); most of the expensive computations - the joins and the aggregation required in the definition of the parents - are precomputed in these views. The suffi­ cient statistics for any subset of potential parents can easily be derived from this view. The above construction, together with the decomposability of the score, allows the steps of the search (say, greedy hill-climbing) to done very efficiently.

The success of this approach depends on the choice of the potential parents. Clearly, a wrong initial choice can result to poor structures. Following [Friedman et al., I999], which ex­ amines a similar approach in the context of learning Bayesian networks, we propose an iterative approach that starts with some structure (possibly one where each attribute does not have any parents), and select the sets Potk(X.A) based on this structure. We then apply the search procedure and get a new, higher scoring, structure. We choose new potential par­ ents based on this new structure and reiterate, stopping when no further improvement is made.

It remains only to discuss the choice of Potk (X.A) at the different phases. Perhaps the simplest approach is to begin by setting Pot1 (X.A) to be the set of attributes in X. In succes­ sive phases, Potk+1 (X. A) would consist of all of Pak (X.A), as well as all attributes that are related to X via slot chains of length < k. Of course, these new attributes would require aggregation; we sidestep the issue by predefining possible ag­ gregates for each attribute.

This scheme expands the set of potential parents at each iteration. However, it usually results in large set of poten­ tial parents. Thus, we actually use a more refined algorithm that only adds parents to Potk+1 (X.A) if they seem to "add value" beyond Pak (X.A) . There are several reasonable ways of evaluating the additional value provided by new parents. Some of these are discussed in [Friedman et al., I999] in the context of learning Bayesian networks. Their results suggest that we should evaluate a new potential parent by measur­ ing the change of score for the family of X.A if we add the r(X.T.B) to its current parents. We then choose the highest scoring of these, as well as the current parents, to be the new set of potential parents. This approach allows us to signifi­ cantly reduce the size of the potential parent set, and thereby of the resulting view, while being unlikely to cause significant degradation in the quality of the learned model.

5 Implementation and experimental results

We implemented our learning algorithm on top of the Post­ gres object-relational database management system. All re­ quired counts were obtained simply through database selec­ tion queries, and cached to avoid performing the same query twice. During the search process, we created temporary ma­ terialized views corresponding to joins between different re­ lations, and these views were then used for computing the counts.

We tested our proposed learning algorithm on two do­ mains, one real and one synthetic. The two domains have very different characteristics. The first is a movie database 1 that contains three relations: Movie, Actor and Appears, which relates actors to movies in which they played. The database contains about IIOOO movies and 7000 actors. While this database has a simple structure, it presents the kind of problems one often encounters when dealing with real data: missing values, large domains for attributes, and incon­ sistent use of values. The fact that our algorithm was able to deal with this kind of real-world problem is quite promis­ ing. Our algorithm learned the model shown in Figure 2(a). This model is reasonable, and close to one that we would con­ sider to be "correct". It learned that the Genre of a movie depended on its Decade and its film Process (color, black & white, technicolor etc.) and that the Decade depended on its film Process. It also learned an interesting dependency com­ bining all three relations: the Role-Type played by an actor in a movie depends on the Gender of the actor and the Genre of the movie.

1 0btained from http , 1 / www-db. stanford. edu / pub / movies /doc. html

The second database, an artificial genetic database similar to the example in this paper, presented quite different chal­ lenges. For one thing, the recursive nature of this domain allows arbitrarily complex joins to be defined. In addition, the probabilistic model in this domain is fairly subtle. Each person has three relevant attributes - ?-Chromosome, M­ Chromosome, and BloodType - all with the same domain and all related somehow to the same attributes of the person's mother and father. The gold standard is the model used to generate the data; the structure of that model was shown ear­ lier in Figure I. We trained our· algorithm on datasets of var­ ious sizes ranging up to 800. A data set of size n consisted of a family tree containing n people, with an average of 0.6 blood tests per person. We evaluated our algorithm on a test set of size I 0,000. Figure 2(b) shows the log-likelihood of the test set for the learned models. In most cases, our algorithm learned a model with the correct structure, and scored well. However, in a small minority of cases, the algorithm got stuck in local maxima, learning a model with incorrect structure that scored quite poorly. This can be seen in the scatter plots of Figure 2(b) which show that the median log-likelihood of the learned models is quite reasonable, but there are a few outliers. Standard techniques such as random restarts can be used to deal with local maxima.

6 Discussion and conclusions

In this paper, we defined a new statistical learning task: learn­ ing probabilistic relational models from data. We have shown that many of the ideas from Bayesian network learning carry over to this new task. However, we have also shown that it also raises many new challenges.

Scaling these ideas to large databases is an important issue. We believe that this can be achieved by a closer integration with the technology of database systems, including indices and query optimization. Furthermore, there has been a lot of recent work on extracting information from massive data sets, including work on finding frequently occurring combinations of values for attributes. We believe that these ideas will help significantly in the computation of sufficient statistics.

There are also several important possible extensions to this work. Perhaps the most obvious one is the treatment of miss­ ing data and hidden variables. We can extend standard tech­ niques (such as Expectation Maximization for missing data)

to this task (see [Koller and Pfeffer, 1997] for some prelim­ inary work on related models.) However, the complexity of inference on large databases with many missing values make the cost of a naive application of such algorithms prohibitive. Clearly, this domain calls both for new inference algorithms and for new learning algorithms that avoid repeated calls to inference over these very large problems. Even more interest­ ing is the issue of automated discovery of hidden variables. There are some preliminary answers to this question in the context of Bayesian networks [Friedman, 1997], in the con­ text of ILP [Lavrac and Dzeroski, 1994], and very recently in the context of simple binary relations [Hofmann et al., 1998]. Combining these ideas and extending them to this more com­ plex framework is a significant and interesting challenge.

Another direction extends the class of models we consider. Here, we assumed that the relational structure is specified be­ fore the probabilistic attribute values are determined. A richer class of PRMs (e.g., that of [Koller and Pfeffer, 1998]) would allow probabilities over the siructure of the model; for ex­ ample: uncertainty over the set of objects in the model, e.g., the number of children a couple has, or over the relations be­ tween objects, e.g., whose is the blood that was found on a crime scene. Ultimately, we would want these techniques to help us automatically discover interesting entities and rela­ tionships that hold in the world.

Acknowledgments

Nir Friedman was supported by a grant from the Michael Sacher Trust. Lise Getoor, Daphne Koller, and Avi Pfef­ fer were supported by ONR contract N66001-97-C-8554 un­ der DARPA's HPKB program, by ONR grant N00014-96-l0718, by the ARO under the MURI program "Integrated Ap­ proach to Intelligent Systems," and by the generosity of the Sloan Foundation and of the Powell foundation.