Recommender system based on expert opinions

FIELD OF THE INVENTION

0001The present invention relates generally to computer systems for recommending items of interest, and more particularly to a recommender system predicting user interest based on expert opinions.

BACKGROUND OF THE INVENTION

0002The goal of Recommender Systems (RS) is to model the user' tastes (preferences) in order to suggest or recommend unseen content that the users would find of interest.

0003Recommender systems have become an important research area because of the abundance of practical applications that help users to deal with information overload and provide personalized recommendations, content, and services to them. Examples of such applications include recommending books, CDs, and other products. Some of the vendors have incorporated recommendation capabilities into their commerce servers.

0004In its most common formulation, the recommendation problem is reduced to the problem of estimating ratings for the items that have not been seen by a user. Intuitively, this estimation is usually based on the ratings given by this user to other items and on some other information that will be formally described below. Once we can estimate ratings for the yet unrated items, we can recommend the item(s) with the highest estimated rating(s) to the user.

0005The recommendation problem can be formulated as follows: Let C be the set of all users and let S be the set of all possible items that can be recommended, such as books, movies, or restaurants. The space S of possible items can be very large, ranging in hundreds of thousands or even millions of items in some applications, such as recommending books or CDs. Similarly, the user space can also be very large-millions in some cases. Let u be a utility function that measures the usefulness of item to user c, i.e.:

0006u: C×S→R

0000where R is a totally ordered set (e.g., non negative integers or real numbers within a certain range). Then, for each user cεC, we want to choose such item s′εS that maximizes the users utility.

0007Each element of the user space C can be defined with a profile that includes various user characteristics, such as age, gender, income, marital status, etc. Similarly, each element of the item space S is defined with a set of characteristics. For example, in a movie recommendation application, where S is a collection of movies, each movie can be represented not only by its ID, but also by its title, genre, director, year of release, leading actors, etc.

0008The central problem of recommender systems lies in that utility u is usually not defined on the whole C×S space, but only on some subset of it. This means that u needs to be extrapolated to the whole space C×S. In recommender systems, utility is typically represented by ratings, which indicates how a particular user liked a particular item and is initially defined only on the items previously rated by the users.

0009Extrapolations from known to unknown ratings are usually done by specifying heuristics that define the utility function and empirically validating its performance and estimating the utility function that optimizes certain performance criterion, such as the mean square error.

0010Once the unknown ratings are estimated, actual recommendations of an item to a user are made by selecting the highest rating among all the estimated ratings for that user, according to [1].

0011Alternatively we can recommend the N best items to a user or a set of users to an item.

0012The new ratings of the not-yet-rated items can be estimated in many different ways using methods from machine learning, approximation theory, and various heuristics. Recommender systems are usually classified according to their approach to rating estimation into the following categories:

0013Content-based recommendations: The user will be recommended items similar to the ones the user preferred in the past. The utility u(c,s) of item s for user c is estimated based on the utilities u(c,s_i) assigned by user c to items s_iεS that are “similar” to item s.

0014Collaborative recommendations (or collaborative filtering, CF): The user will be recommended items that people with similar tastes and preferences liked in the past. In this case, the recommender systems try to predict the utility of items for a particular user based on the items previously rated by other users. More formally, the utility u(c,s) of item s for user c is estimated based on the utilities u(c_j,s) assigned to item by those users c_jεC who are “similar” to user c.

0015One of commonly used technique for collaborative filtering is Nearest Neighbour algorithm (k-NN): is a method for classifying objects based on closest training examples in the feature space where the function is only approximated locally and all computation is deferred until classification. k-NN is based on cosine and correlation functions.

0016Hybrid approaches: These methods combine collaborative and content-based methods.

0017Collaborative filtering is the current mainstream approach used to build web-based recommender systems. CF algorithms assume that in order to recommend items to users, information can be drawn using only what users liked in the past and not any additional information about the users or items. In user-based CF algorithms recommendations are computed by computing similar users and recommending what these users liked in the past. On the other hand, item-based CF algorithms computed similar items to the ones the user liked in the past. For computing these similar items, the only information used is how much other users liked them.

0018As shown in “<i>Collaborative filtering using dual information sources</i>” (CHO J. et al, IEEE Intelligent Systems, 22(3):30-38, 2007), the use of experts, instead of the whole available group of users, to generate predictions in a recommender system has been explored. The approach is focused on identifying expert users from a closed community of users, by deriving a “domain authority” reputation-like score for each user in the data set.

0019The idea of expertise is also related to that of trust. In trust-aware recommender systems the influence of neighbors is weighed by a measure of how trustworthy they are for the current user. The trust measure can be defined and obtained in different ways, for instance, a measure of trust is computed by looking at how well a neighbor has predicted past ratings.

0020One option to obtain a set of ratings from a reduced population of experts in a given domain is to obtain item evaluations from trusted sources and use a rating inference model (as in “<i>Modeling online reviews with multi</i>-<i>grain topic models</i>”, TITOV I. et al, In Proc. of WWW '08, 2008), or an automatic expert detection model (“Broad expertise retrieval in sparse data environments”, BALOG K. et al, In Proc. of SIGIR '07, 2007). In domains where there are online expert evaluations (e.g. movies, books, cars, etc.) that include a quantitative rating, it is feasible to crawl the web in order to gather expert ratings.

0021Alternative approaches to populate a database of expert ratings include—but are not limited to—a manually-maintained database of dedicated experts, or the compilation of expert opinions collected by crawling and inferring quantitative ratings from online reviews.

0022The main problems with existing solutions are the following ones:

0023Data sparsity: In a standard collaborative recommender system, the user-rating data is very sparse. Although dimensionality techniques of reduction offer some help, this problem is still a source of inconsistency and noise in the predictions.

0024Noise and malicious ratings: Users introduce noise when giving their feedback to a recommender system, both in the form of careless ratings and malicious entries, which will affect the quality of predictions. It has been found that a significant part of the error in explicit feedback-based CF algorithms is due to the noise in the users' explicit feedback.

0025Cold start problem: In a CF system, new items lack rating data and cannot be recommended; the same is true when a new user enters the system.

0026Scalability: Computing the similarity matrix for N users in an M-item collection is an O(N²M) problem. This matrix needs to be updated on a regular basis, as new items and/or users enter the system. Therefore, CF based approaches typically suffer from scalability limitations. While there are several ways to address this issue—such as k-means clustering (“<i>Scalable collaborative filtering using cluster</i>-<i>based smoothing</i>”, XUE G. et al, In Proc. of SIGIR '05, 2005), scalability is still an open research problem in CF systems.

0027Privacy: Privacy in CF recommender systems is a growing concern and still an area of research. In order to maintain and update the similarity matrix, the system has to transmit all user ratings to a central node where the matrix is computed.

0028k-NN: The Nearest Neighbor algorithm, for each user, tries to find a number of similar users whose profiles can then be used to predict recommendations. However, defining similarity between users is not an easy task: basically it is limited by the sparsity and noise in the data and is computationally expensive.

SUMMARY OF THE INVENTION

0029The invention refers to a method for recommending one or more available items to a target user u according to claim <b>1</b>. Preferred embodiments of the method are defined in the dependent claims.

0030In order to overcome the problems of the existent recommender systems, the present invention provides a method for recommending an item which is a variation of traditional collaborative filtering: rather than applying a nearest neighbor algorithm to the user-rating data, predictions are computed using a set of expert neighbors from an independent dataset, whose opinions are weighted according to their similarity to the user.

0031An expert (professional raters in a given domain) is defined as an individual that can be trusted to have produced thoughtful, consistent and reliable evaluations (ratings) of items in a given domain.

0032The invention refers to a method for recommending one or more available items to a target user u, comprising the steps of:

0033obtaining a set of ratings for a plurality of available items from a group of expert users E={e₁, . . . , e_k};

0034computing a similarity measure between a target user u and an expert e according to the following equation:

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>sim</mi><mo></mo><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>e</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mrow><msup><mo>∑</mo><mi>i</mi></msup><mo></mo><mrow><mo>(</mo><mrow><msub><mi>r</mi><mi>ui</mi></msub><mo></mo><msub><mi>r</mi><mi>ei</mi></msub></mrow><mo>)</mo></mrow></mrow><mrow><msqrt><mrow><msup><mo>∑</mo><mi>i</mi></msup><mo></mo><msubsup><mi>r</mi><mi>ui</mi><mn>2</mn></msubsup></mrow></msqrt><mo></mo><msqrt><mrow><msup><mo>∑</mo><mi>i</mi></msup><mo></mo><msubsup><mi>r</mi><mi>ei</mi><mn>2</mn></msubsup></mrow></msqrt></mrow></mfrac><mo>·</mo><mfrac><mrow><mn>2</mn><mo></mo><msub><mi>N</mi><mrow><mi>u</mi><mo>⋃</mo><mi>e</mi></mrow></msub></mrow><mrow><msub><mi>N</mi><mi>u</mi></msub><mo>+</mo><msub><mi>N</mi><mi>e</mi></msub></mrow></mfrac></mrow></mrow></mtd><mtd><mrow><mo>[</mo><mn>2</mn><mo>]</mo></mrow></mtd></mtr></mtable></math></maths>

0000where r_uiand r_eiare the target user and expert ratings for item i, respectively, N_uand N_eare the number of items rated by the target user and the expert, respectively, and N_u∪eis the number of co-rated items;

0035determining a set E′ of the group of experts E, E′<img id="CUSTOM-CHARACTER-00001" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />E, whose similarity to the target user is greater than a pre-established threshold δ;

0036computing a predicted rating for an item j by means of a similarity-weighted average of the ratings input from each expert e in E′:

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>r</mi><mi>uj</mi></msub><mo>=</mo><mrow><msub><mi>σ</mi><mi>u</mi></msub><mo>+</mo><mfrac><mrow><msub><mo>∑</mo><mrow><mi>e</mi><mo>⊆</mo><msup><mi>E</mi><mi>′</mi></msup></mrow></msub><mo></mo><mrow><mrow><mo>(</mo><mrow><msub><mi>r</mi><mi>ej</mi></msub><mo>-</mo><msub><mi>σ</mi><mi>e</mi></msub></mrow><mo>)</mo></mrow><mo>·</mo><mrow><mi>sim</mi><mo></mo><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>e</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mrow><mo>∑</mo><mrow><mi>sim</mi><mo></mo><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>e</mi></mrow><mo>)</mo></mrow></mrow></mrow></mfrac></mrow></mrow></mtd><mtd><mrow><mo>[</mo><mn>3</mn><mo>]</mo></mrow></mtd></mtr></mtable></math></maths>

0000where r_ujis the predicted rating of item j for user u, r_ejis the known rating for expert e of item j, and σ_uand σ_eare the respective mean ratings; and

0037recommending that item j to the target user u if said predicted rating r_ujis above a pre-established value.

0038In order to avoid the drawback of using a fixed-threshold δ which has the risk of finding very few neighbors, the invention further comprises:

0039defining a confidence threshold τ as the minimum number of experts who must have rated item i in order to trust their prediction;

0040determining a subset E″={e₁, . . . , e_n} of the set of experts E′, E″<img id="CUSTOM-CHARACTER-00002" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />E′, which includes the experts who have rated item j; and, <ul><li id="ul0001-0001" num="0000"><ul><li id="ul0002-0001" num="0041">if the number n of experts in the subset E″ is equal or above said confidence threshold τ, the predicted rating r_ujcomputed according to equation [3] is returned;</li><li id="ul0002-0002" num="0042">if the number n of experts in the subset E″ is less than said confidence threshold τ, no prediction can be made and the mean rating σ_ufor that user is returned.</li></ul></li></ul>

0043The step of obtaining a set of ratings from a population of experts in a given domain can be obtained in several possible ways, such as: <ul><li id="ul0003-0001" num="0000"><ul><li id="ul0004-0001" num="0044">item evaluations from trusted sources and use a rating inference model;</li><li id="ul0004-0002" num="0045">using an automatic expert detection model;</li><li id="ul0004-0003" num="0046">maintaining a database of dedicated experts.</li></ul></li></ul>

0047The goal when using external data sources is not as much on prediction accuracy as it is on addressing some of the common problems found in traditional CF recommender systems described previously.

0048Data sparsity: this issue is addressed since domain experts are more likely to have rated a large percentage of the items.

0049Noise and malicious ratings: Experts are expected to be more consistent and conscious with their ratings, thus reducing noise. In addition, an expert data set can be immune to malicious, profile-injection attacks as it is an easy to control and stable data set.

0050Cold start problem: Motivated expert users typically rate a new item entering the collection as soon as they know of its existence and therefore minimize item cold-start.

0051Scalability: the recommender system of the present invention is less sensitive to scale, as it creates recommendations from a much reduced set of experts.

0052Privacy: The present invention does not need to keep a centralized matrix will all user data, since the similarity matrix only includes expert data and the target user. In expert-CF, the current expert ratings can be easily transmitted thanks to the reduced size of the matrix, such that all computation is performed locally on the client. This advantage is particularly relevant in a mobile scenario.

0053Thus, the present invention uses a set of expert ratings to generate predictions for a large population of users, such as, for example, using online reviews from critics. Therefore, the present invention uses feedback from less noisy sources (i.e. experts) to build recommendations.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0054Reference will now be made in detail to a preferred embodiment of the recommender system of the present invention, in which professional raters in a given domain (i.e. experts) can predict the behavior of the general population. The expert is defined as an individual that can be trusted to have produced thoughtful, consistent and reliable evaluations (ratings) of items in a given domain.

0055The proposed invention consists of a recommender system that uses a set of expert ratings to generate predictions for a large population of users, such as, for example, using online reviews from critics. This way, recommendations are built using feedback from less noisy sources, i.e., the experts.

0056The present example is based on using online reviews from movie critics. However, it is also possible to think of a small set of “professional” raters maintaining a rating database. This is reminiscent but less demanding than content-based recommender systems that rely on experts to manually categorize and label content.

0057The first step in the invention requires obtaining a set of ratings from a reduced population of experts in a given domain. This collection of expert's ratings can be obtained according to known methods such as: <ul><li id="ul0005-0001" num="0000"><ul><li id="ul0006-0001" num="0058">obtaining item evaluations from trusted sources and either use ratings directly if available or a rating inference model (“<i>Modeling online reviews with multi</i>-<i>grain topic models</i>”, TITOV I. et al, In Proc. of WWW '08, 2008), or</li><li id="ul0006-0002" num="0059">an automatic expert detection model (“Broad expertise retrieval in sparse data environments”, BALOG K. et al, In Proc. of SIGIR '07, 2007), or</li><li id="ul0006-0003" num="0060">manually-maintaining a database of dedicated experts.</li></ul></li></ul>

0061The present invention does not require a particular way of extracting the expert ratings. However, it does require that these expert ratings are obtained from a source that is external to the user database that will be targeted for the predictions. The reason is that we need to guarantee there is limited noise in the ratings and we cannot guarantee this on a general user database.

0062The key of the invention is on using such an external and reduced source of ratings to predict the general population.

0063For example, in a possible implementation of the present invention, the Rotten Tomatoes (http://www.rottentomatoes.com) web site—which aggregates the opinions of movie critics from various media sources—has been crawled to obtain expert ratings of the movies in the Netflix (http://www.netflix.com) data set.

0064In a first stage, a matrix of expert-item ratings is populated. Then, the similarity between all pairs of users is computed, based on a pre-determined measure of similarity. A variation of the cosine similarity is used which includes an adjusting factor to take into account the number of items co-rated by both users.

0065So given a target user u and an expert user e, the similarity between the target user u and an expert user e, sim (u,e) is computed as:

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>sim</mi><mo></mo><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>e</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mrow><msup><mo>∑</mo><mi>i</mi></msup><mo></mo><mrow><mo>(</mo><mrow><msub><mi>r</mi><mi>ui</mi></msub><mo></mo><msub><mi>r</mi><mi>ei</mi></msub></mrow><mo>)</mo></mrow></mrow><mrow><msqrt><mrow><msup><mo>∑</mo><mi>i</mi></msup><mo></mo><msubsup><mi>r</mi><mi>ui</mi><mn>2</mn></msubsup></mrow></msqrt><mo></mo><msqrt><mrow><msup><mo>∑</mo><mi>i</mi></msup><mo></mo><msubsup><mi>r</mi><mi>ei</mi><mn>2</mn></msubsup></mrow></msqrt></mrow></mfrac><mo>·</mo><mfrac><mrow><mn>2</mn><mo></mo><msub><mi>N</mi><mrow><mi>u</mi><mo>⋃</mo><mi>e</mi></mrow></msub></mrow><mrow><msub><mi>N</mi><mi>u</mi></msub><mo>+</mo><msub><mi>N</mi><mi>e</mi></msub></mrow></mfrac></mrow></mrow></mtd><mtd><mrow><mo>[</mo><mn>2</mn><mo>]</mo></mrow></mtd></mtr></mtable></math></maths>

0000where r_uiand r_eiare the target user and expert ratings for item i, N_uand N_eare the number of items rated by the target user and the expert, respectively, and N_u∪eis the number of co-rated items.

0066The present invention uses an approach to collaborative filtering that only uses expert opinions to predict user ratings. Therefore, this invention does not require the user-user similarity to be computed; instead, a similarity matrix between each user and the expert set is built.

0067In order to predict a user's rating for a particular item, we look for experts whose similarity to the target user is greater than a pre-established threshold δ. Formally: given a space V of users and experts and a similarity measure sim: V×V→R, a group of experts E={e₁, . . . , e_k}<img id="CUSTOM-CHARACTER-00003" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />V and a set of users U={u₁, . . . , u_N}<img id="CUSTOM-CHARACTER-00004" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />V are defined. Given a particular user u<img id="CUSTOM-CHARACTER-00005" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />U and a pre-established threshold δ, a set of experts E′<img id="CUSTOM-CHARACTER-00006" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />E is found such that: ∀e<img id="CUSTOM-CHARACTER-00007" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />E′<img id="CUSTOM-CHARACTER-00008" he="3.13mm" wi="3.56mm" file="US20110137726A1-20110609-P00002.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />sim(u,e)≧δ, where the similarity measure sim is obtained according to equation [2] above.

0068One of the drawbacks of using a fixed threshold δ is the risk of finding very few neighbors; furthermore, the ones that are found may not have rated the current item. In order to deal with this problem, a confidence threshold τ may be defined as the minimum number of expert neighbors who must have rated the item in order to trust their prediction. Given the set of experts E′ found in the previous step and an item j, the subset E″<img id="CUSTOM-CHARACTER-00009" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />E′ such that ∀e<img id="CUSTOM-CHARACTER-00010" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />E″<img id="CUSTOM-CHARACTER-00011" he="3.13mm" wi="3.56mm" file="US20110137726A1-20110609-P00002.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />r_ej≠0, where r_ejis the rating of item j by expert e<img id="CUSTOM-CHARACTER-00012" he="2.79mm" wi="2.46mm" file="US20110137726A1-20110609-P00001.TIF" alt="custom-character" img-content="character" img-format="tif" orientation="portrait" inline="no" />E′, and 0 is the value of the unrated item.

0069Once this subset of experts E″=e₁, . . . , e_nhas been identified, if n&lt;τ, no prediction can be made and the user mean is returned. On the other hand, if n≧τ, a predicted rating can be computed. This is done by means of a similarity-weighted average of the ratings input from each expert e in E″:

0000<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>r</mi><mi>uj</mi></msub><mo>=</mo><mrow><msub><mi>σ</mi><mi>u</mi></msub><mo>+</mo><mfrac><mrow><msub><mo>∑</mo><mrow><mi>e</mi><mo>⊆</mo><msup><mi>E</mi><mi>′</mi></msup></mrow></msub><mo></mo><mrow><mrow><mo>(</mo><mrow><msub><mi>r</mi><mi>ej</mi></msub><mo>-</mo><msub><mi>σ</mi><mi>e</mi></msub></mrow><mo>)</mo></mrow><mo>·</mo><mrow><mi>sim</mi><mo></mo><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>e</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mrow><mo>∑</mo><mrow><mi>sim</mi><mo></mo><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>e</mi></mrow><mo>)</mo></mrow></mrow></mrow></mfrac></mrow></mrow></mtd><mtd><mrow><mo>[</mo><mn>3</mn><mo>]</mo></mrow></mtd></mtr></mtable></math></maths>

0000where r_ujis the predicted rating of item j for user u, r_ejis the known rating for expert e to item j, and σ_uand σ_eare the respective mean ratings.

0070The optimal setting of these parameters δ and τ depends on the data set and the application in mind.

0071As indicated before, the present invention relates to a recommender system. It is to be understood that the above disclosure is an exemplification of the principles of the invention and does not limit the invention to the described embodiments.