This is quite different from the classical machine learn-(See also [Aha97 ng challenge of learning distributions over tuples(i.e dividual rows of a single relational database) Addressing this type of relational learning and infer- 2 Standard Probabilistic Relational ence problem is exactly the kind of problem Probabilis- Models tic Relational Models(PRMs)[KP98 were designed to do. In this paper we show how PRMs can be success- A PRM can be viewed as an extension of Bayesian fully applied to this learning scenario, for addressing Networks to a relational setting. PRMS learn class- the Collaborative Filtering(CF)problem. We exam- level dependencies that can subsequently be used t he the effectiveness of standard PRMs applied to the make inferences about a particular instance of a class CF task on the EachMovie[Eac] dataset, then we eval- For example, we might connect(the class of)teenage uate the effectiveness of an extended version of PRMs boys to(the class of )action movies, then use that called hierarchical PRMS(hPRMs)[Geto2]. We show to infer that the teenage boy Fred likes the action that standard PRMs can be used to achieve competi- movie Terminator. Of course, we could do some- tive results on the CF task. Furthermore, we demon- thing like that in a standard Bayesian Network, by strate that hPRMs can outperform standard PRMs on first transforming this relational information into a the CF task non-structured, propositionalized form. While this useful for inference(and in fact is what we will do) In the remainder of this section we will provide an this is not an effective way to learn the interrelation overview the CF problem. In Section 2 we describe ships. A PRM can be learned directly on a relational standard PRMs and our application of the PRM database, thereby retaining and leveraging the rich framework to the CF domain. Section 3 introduces structure contained therein how an hPRM can provide a more expressive model We base our notation and conventions for PRMs on of the EachMovie dataset. Finally, Section 4 demon- those used in[Get02]. A PRM operates on a Relational strates the overall effectiveness of PRMs in the CF Schema, which consists of two fundamental elements: problem domain, and in particular the superiority of a set of classes, &=X Xn, and a set of reference hPRMs over standard PrMs slots that define the relationships between the classes Each class X is composed of a set of descriptive at- 1.1 Collaborative Filtering tributes, A(X), which in turn take on a range of val Collaborative Filtering is an area that has attracted in- scribing a domain describing votes on movies. This creasing attention in recent years. In the most general schema has three classes called Vote, Person, and sense, the CF problem involves predicting a users pref- Movie. For the Vote class, the descriptive attribute is erence for a particular item, such as a movie or a book. Score with values 10,, 5]; for Person the descrip- This prediction is based on both the user's known tive attributes are Age and Gender, which take on val- preferences on other items, and also on the known ues young, middle-aged, old) and Male, Female preferences that other, similar, users have demon- respectively; and for Movie the single descriptive at- strated. Widely used collaborative filtering systems in- tribute is Rating which takes on values G, PG, M, R clude amazon com's book recommender and yahoo ' s Furthermore. a class can be associated with a set of LAUNCHcast music recommender syster reference slots, R(X). A particular reference slot, X p, Traditionally, CF algorithms are divided into two describe how objects of class X are related to objects in other classes in the relational schema. One or more major groups: memory-based algorithms and model- reference slots can composed to form a reference slot based algorithms. Memory-based algorithms operate chain, T, and attributes of related objects can be de- over the entire dataset; when a new prediction is re- noted by using the shorthand X.T.A, where A is a quired, a memory-based algorithm generally iterates descriptive attribute of the related class. Continuing over the entire user database to arrive at a prediction. Breese et al. provide an excellent overview of several our example, the Vote class would be associated with memory-based algorithms in BHK98. Model-based wo reference slots: Vote. ofPerson. which describes algorithms, on the other hand, use the user databas how to link Vote objects to a specific Person; and to create a model of which factors influence help pi Vote. ofMovie. which describes how to link vote ob dict a user's preferences, and use this learned model to Jects to a specific Movie object make predictions for a new user. Clustering [BHK98 A PRM II defines a probability distribution over all and Bayesian Models CHM97 are two examples of possible instantiations I of the relational schema. It odel-based methods that have been used in the past. is made ofof two components: the dependency graphThis is quite different from the classical machine learn￾ing challenge of learning distributions over tuples (i.e., individual rows of a single relational database). Addressing this type of relational learning and infer￾ence problem is exactly the kind of problem Probabilis￾tic Relational Models (PRMs) [KP98] were designed to do. In this paper we show how PRMs can be success￾fully applied to this learning scenario, for addressing the Collaborative Filtering (CF) problem. We exam￾ine the effectiveness of standard PRMs applied to the CF task on the EachMovie [Eac] dataset, then we eval￾uate the effectiveness of an extended version of PRMs called hierarchical PRMS (hPRMs) [Get02]. We show that standard PRMs can be used to achieve competi￾tive results on the CF task. Furthermore, we demon￾strate that hPRMs can outperform standard PRMs on the CF task. In the remainder of this section we will provide an overview the CF problem. In Section 2 we describe standard PRMs and our application of the PRM framework to the CF domain. Section 3 introduces our implementation of hierarchial PRMs, and shows how an hPRM can provide a more expressive model of the EachMovie dataset. Finally, Section 4 demon￾strates the overall effectiveness of PRMs in the CF problem domain, and in particular the superiority of hPRMs over standard PRMs. 1.1 Collaborative Filtering Collaborative Filtering is an area that has attracted in￾creasing attention in recent years. In the most general sense, the CF problem involves predicting a user’s pref￾erence for a particular item, such as a movie or a book. This prediction is based on both the user’s known preferences on other items, and also on the known preferences that other, similar, users have demon￾strated. Widely used collaborative filtering systems in￾clude Amazon.com’s book recommender and Yahoo!’s LAUNCHcast music recommender system. Traditionally, CF algorithms are divided into two major groups: memory-based algorithms and model￾based algorithms. Memory-based algorithms operate over the entire dataset; when a new prediction is re￾quired, a memory-based algorithm generally iterates over the entire user database to arrive at a prediction. Breese et al. provide an excellent overview of several memory-based algorithms in [BHK98]. Model-based algorithms, on the other hand, use the user database to create a model of which factors influence help pre￾dict a user’s preferences, and use this learned model to make predictions for a new user. Clustering [BHK98] and Bayesian Models [CHM97] are two examples of model-based methods that have been used in the past. (See also [Aha97].) 2 Standard Probabilistic Relational Models A PRM can be viewed as an extension of Bayesian Networks to a relational setting. PRMs learn class￾level dependencies that can subsequently be used to make inferences about a particular instance of a class. For example, we might connect (the class of) teenage boys to (the class of) action movies, then use that to infer that the teenage boy Fred likes the action movie Terminator. Of course, we could do some￾thing like that in a standard Bayesian Network, by first transforming this relational information into a non-structured, propositionalized form. While this is useful for inference (and in fact is what we will do), this is not an effective way to learn the interrelation￾ships. A PRM can be learned directly on a relational database, thereby retaining and leveraging the rich structure contained therein. We base our notation and conventions for PRMs on those used in [Get02]. A PRM operates on a Relational Schema, which consists of two fundamental elements: a set of classes, X = X1, . . . , Xn, and a set of reference slots that define the relationships between the classes. Each class X is composed of a set of descriptive at￾tributes, A(X), which in turn take on a range of val￾ues V (X.A). For example, consider a schema de￾scribing a domain describing votes on movies. This schema has three classes called Vote, Person, and Movie. For the Vote class, the descriptive attribute is Score with values {0, . . . , 5}; for Person the descrip￾tive attributes are Age and Gender, which take on val￾ues {young, middle-aged, old} and {Male, Female} respectively; and for Movie the single descriptive at￾tribute is Rating which takes on values {G, PG, M, R}. Furthermore, a class can be associated with a set of reference slots, R(X). A particular reference slot, X.ρ, describe how objects of class X are related to objects in other classes in the relational schema. One or more reference slots can composed to form a reference slot chain, τ , and attributes of related objects can be de￾noted by using the shorthand X.τ.A, where A is a descriptive attribute of the related class. Continuing our example, the Vote class would be associated with two reference slots: Vote.ofPerson, which describes how to link Vote objects to a specific Person; and Vote.ofMovie, which describes how to link Vote ob￾jects to a specific Movie object. A PRM Π defines a probability distribution over all possible instantiations I of the relational schema. It is made of of two components: the dependency graph