SYSTEM AND METHOD FOR FINDING UNEXPECTED, BUT RELEVANT CONTENT IN AN INFORMATION RETRIEVAL SYSTEM

• US 20110179019A1
• Filed: 01/15/2010
• Published: 07/21/2011
• Est. Priority Date: 01/15/2010
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Vassilvitskii, Sergei, Amer-Yahia, Sihem, Yu, Cong
• Granted Patent: US 8,204,878 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering

Abstract

An improved method for information retrieval in web query and recommendation systems, where items that are likely unfamiliar to the users of the system, but potentially relevant, are recommended. In a recommendation system having ratings by a plurality of users for a plurality of items, items are assigned to one or more data regions based on item attributes or user activity. Source regions are identified for each of the data regions. For a given user, data regions with which both the user and the user'"'"'s social network are unfamiliar are identified. Within a given data region, the relevance of items to the user within such regions is evaluated using ratings provided by other users who have entered ratings similar to the user in source regions for the data region. Items receiving the highest relevance score are recommended to the user.

Claims

1. A method comprising the steps of:

receiving, over a network, item ratings from a plurality of users, wherein each rating relates to one of a plurality of items;

assigning, using at least one computing device, each of the plurality of items to at least one of a plurality data regions;

identifying, using the at least one computing device, at least one source region for each of the plurality of data regions;

determining, using the at least one computing device, for a selected one user of the plurality of users, a region potential interest score for each of the plurality of data regions, wherein the region potential interest score increases as the number of the plurality of items assigned to the respective data region rated by the selected user decreases, and wherein the region potential interest score additionally increases as the number of the plurality of items assigned to the respective data region rated by a user network decreases, wherein the user network comprises a subset of the plurality of users related to the selected user by at least one relationship criteria;

determining, using the at least one computing device, for the selected user, for each one of the plurality of regions, a user similarity score for each one of the plurality of users, wherein the user similarity score is computed by comparing item ratings transmitted by the selected user and the each respective one of the plurality of users for each of the plurality of items assigned to each of the at least one source regions assigned to the respective one of the plurality of data regions;

determining, using the at least one computing device, for the selected user, for each one of the plurality of regions, a regional relevance score for each of the plurality of items assigned to the respective data region, wherein the regional relevance score is computed using the user similarity score for each of the plurality of users that rated the respective item and the ratings transmitted by the respective user;

determining, using the at least one computing device, for the selected user, for each of the plurality of items, an overall relevance score using the regional relevance scores and the region potential interest scores for respective items;

selecting, using the at least one computing device, for the selected user, a list of recommended items, wherein the list of recommended items comprises at least one reference to at least one item having a positive overall relevance score; and

transmitting, over the network, the list of recommended items to the selected user.

2. The method of claim 1 wherein each of the plurality of items has at least one intrinsic attribute and each of the plurality of data regions has at least one region dimension, wherein each of the plurality of items is assigned to one or more data regions where the at least one intrinsic attribute of the respective item matches the at least one region dimensions of the respective data region.

3. The method of claim 2 wherein the set of region dimensions for the plurality of data regions comprises a subset of the at least one intrinsic attributes of the plurality of items.

4. The method of claim 1 wherein each of the plurality of items is assigned to one of the plurality of data regions by clustering the plurality of items by at least one action performed by one or more of the plurality of users with respect to the respective item.

5. The method of claim 4 wherein the plurality of items is clustered using a Jaccard dissimilarity function, d(i, j), wherein

6. The method of claim 5 wherein The method of claim 5 wherein the each of the plurality of items is assigned to one of the plurality of data regions using the Jaccard dissimilarity function, d(i, j), and the k-means++ algorithm.

7. The method of claim 1 wherein the at least one source region for each of the plurality of data regions is identified by a system administrator using an interface provided by the at least one computing device.

8. The method of claim 1 wherein the at least one source region for each of the plurality of data regions is automatically identified by the computing device using a support function, supp(r), where supp(r) is the proportion of ratings in the plurality of ratings which are assigned to one of the plurality of data regions r, wherein

conf(rr′

)=supp(r∪

r′

)/supp(r).

where r and r′

are any two of the plurality of data regions and conf(r=>

r′

) is the confidence that two regions r and r′

are correlated, wherein r is identified as a source region of r′

if conf(r=>

r′

) falls within a predetermined range.

9. The method of claim 1 wherein at least one relationship criteria is a social relationship maintained on a social networking service.

10. The method of claim 1 wherein at least one relationship criteria is a topical interest.

11. The method of claim 1 wherein the region potential interest score is an otb score wherein

otb(u,r)=otbBase(u,r)×

otbFactor(u,r)

where

u and r denotes one of the plurality of users and one of the plurality of data regions respectively,

otbBase (u, r) is a base unfamiliarity for data region r by user u, and

otbFactor (u, r) is an exposure factor for a data region r by user u,

where

12. A method of claim 11 wherein the user similarity score is an expanded similarity scores, exSim(u, u′

, r), where

exSim(u,u′

,r)=max<sub>r′

ε

sources(r)</sub>userSim(u,u′

,r)

where u and u′

are two of the plurality of users and r denotes one of the plurality of data regions, and

sources(r) is the set source regions for data region r, and

where userSim(u, u′

, r) is a similarity between the two users u and u′

restricted to the data region r, where

13. The method of claim 12 wherein the regional relevance score is a relevance score, relevance(u,r,i), wherein

relevance(u,r,i)=Σ

<sub>u′

ε

exNetwork(u,r)</sub>exSim(u,u′

,r)×

rating(u′

,i)

where

u and u′

are two of the plurality of users, r is one of the plurality of data regions, and i one of the plurality of items

exSim(u, u′

, r) is the expanded similarity score between users u and u′

rating (u′

, i) is user u′

rating for item i

sources(r) is the set of source regions for data region r, and

exNetwork(u, r) is the set formed by users who share similar interests with u over source regions of data region r which may be defined as

u′

ε

U|exSim(u,u′

,r)≧

θ

where θ

is an application-dependent threshold.

14. The method of claim 13 wherein the overall relevance score is an overall relevance score, overall(u, i) where

overall(u,i):

=Σ

<sub>rε

regions(i)</sub>otb(u,r)×

relevance(u,r,i).

15. The method of claim 1 wherein the list of recommended items comprises references to the items having the top n overall relevance scores, where n is a fixed number.

16. A system comprising:

a rating receiving module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for receiving, over a network, item ratings from a plurality of users, wherein each rating relates to one of a plurality of items;

a data region assignment module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for assigning each of the plurality of items to at least one of a plurality data regions;

a source region identification module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for identifying at least one source region for each of the plurality of data regions;

a data region potential interest determination module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for determining, for selected users of the plurality of users, a region potential interest score for each of the plurality of data regions, wherein the region potential interest score increases as the number of the plurality of items assigned to the respective data region rated by the selected user decreases, and wherein the region potential interest score additionally increases as the number of the plurality of items assigned to the respective data region rated by a user network decreases, wherein the user network comprises a subset of the plurality of users related to the selected user by at least one relationship criteria;

a user similarity determination module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for determining, for the selected user, for each one of the plurality of regions, a user similarity score for each one of the plurality of users, wherein the user similarity score is computed by comparing item ratings transmitted by the selected user and the each respective one of the plurality of users for each of the plurality of items assigned to each of the at least one source regions assigned to the respective one of the plurality of data regions;

a regional relevance score determination module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for determining for the selected user, for each one of the plurality of regions, a regional relevance score for each of the plurality of items assigned to the respective data region, wherein the regional relevance score is computed using the user similarity score for each of the plurality of users that rated the respective item and the ratings transmitted by the respective user;

an overall relevance score determination module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for determining, for the selected user, for each of the plurality of items, an overall relevance score using the regional relevance scores and the region potential interest scores for respective items;

a recommendation selection module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for selecting, for the selected user, a list of recommended items, wherein the list of recommended items comprises at least one reference to at least one item having a positive overall relevance score;

a recommendation list transmission module comprising one or more processors programmed to execute software code retrieved from a computer readable storage medium storing software for transmitting, over the network, the list of recommended items to the selected user.

17. The system of claim 16 wherein each of the plurality of items has at least one intrinsic attribute and each of the plurality of data regions has at least one region dimension, wherein each of the plurality of items is assigned to one or more data regions where the at least one intrinsic attribute of the respective item matches the at least one region dimensions of the respective data region.

18. The system of claim 16 wherein each of the plurality of items is assigned by the data region assignment module to one of the plurality of data regions by clustering the plurality of items by at least one action performed by one or more of the plurality of users with respect to the respective item.

19. The system of claim 18 wherein the plurality of items is clustered by the data region assignment module using a Jaccard dissimilarity function, d(i, j), wherein

20. The system of claim 16 wherein the at least one source region for each of the plurality of data regions is automatically identified by the source region identification module using a support function, supp(r), where supp(r) is the proportion of ratings in the plurality of ratings which are assigned to one of the plurality of data regions r, wherein

conf(rr′

)=supp(r∪

r′

)/supp(r).

where r and r′

are any two of the plurality of data regions and conf(r=>

r′

) is the confidence that two regions r and r′

are correlated, wherein r is identified as a source region of r′

if conf(r=>

r′

) falls within a predetermined range.

21. The system of claim 16 wherein the region potential interest score determined by the data region potential interest determination module is an otb score wherein

otb(u,r)=otbBase(u,r)×

otbFactor(u,r)

where

u and r denotes one of the plurality of users and one of the plurality of data regions respectively,

otbBase (u, r) is a base unfamiliarity for data region r by user u, and

otbFactor (u, r) is an exposure factor for a data region r by user u,

where

22. The system of claim 21 wherein the user similarity score determined by the user similarity determination module is an expanded similarity score, exSim(u, u′

, r), where

exSim(u,u′

,r)=max<sub>r′

ε

sources(r)</sub>userSim(u,u′

,r)

where u and u′

are two of the plurality of users and r denotes one of the plurality of data regions, and

sources(r) is the set source regions for data region r, and

where userSim(u, u′

, r) is a similarity between the two users u and u′

restricted to the data region r, where

23. The system of claim 22 wherein the regional relevance score determined by the regional relevance score determination module is a relevance score, relevance(u, r, i), wherein

relevance(u,r,i)=Σ

<sub>u′

ε

exNetwork(u,r)</sub>exSim(u,u′

,r)×

rating(u′

,i)

where

u and u′

are two of the plurality of users, r is one of the plurality of data regions, and i one of the plurality of items

exSim(u, u′

,r) is the expanded similarity score between users u and u′

rating (u′

, i) is user u′

rating for item i

sources(r) is the set of source regions for data region r, and

exNetwork(u, r) is the set formed by users who share similar interests with u over source regions of data region r which may be defined as

u′

ε

U|exSim(u,u′

,r)≧

θ

where θ

is an application-dependent threshold.

24. The system of claim 23 wherein the overall relevance score determined by the overall relevance score determination module is an overall relevance score, overall(u, i) where

overall(u,i):

=Σ

<sub>rε

regions(i)</sub>otb(u,r)×

relevance(u,r,i).

25. A computer-readable medium having computer-executable instructions for a method comprising the steps of:

receiving, over a network, item ratings from a plurality of users, wherein each rating relates to one of a plurality of items;

assigning, using at least one computing device, each of the plurality of items to at least one of a plurality data regions;

identifying, using the at least one computing device, at least one source region for each of the plurality of data regions;

determining, using the at least one computing device, for a selected one user of the plurality of users, a region potential interest score for each of the plurality of data regions, wherein the region potential interest score increases as the number of the plurality of items assigned to the respective data region rated by the selected user decreases, and wherein the region potential interest score additionally increases as the number of the plurality of items assigned to the respective data region rated by a user network decreases, wherein the user network comprises a subset of the plurality of users related to the selected user by at least one relationship criteria;

determining, using the at least one computing device, for the selected user, for each one of the plurality of regions, a user similarity score for each one of the plurality of users, wherein the user similarity score is computed by comparing item ratings transmitted by the selected user and the each respective one of the plurality of users for each of the plurality of items assigned to each of the at least one source regions assigned to the respective one of the plurality of data regions;

determining, using the at least one computing device, for the selected user, for each one of the plurality of regions, a regional relevance score for each of the plurality of items assigned to the respective data region, wherein the regional relevance score is computed using the user similarity score for each of the plurality of users that rated the respective item and the ratings transmitted by the respective user;

determining, using the at least one computing device, for the selected user, for each of the plurality of items, an overall relevance score using the regional relevance scores and the region potential interest scores for respective items;

selecting, using the at least one computing device, for the selected user, a list of recommended items, wherein the list of recommended items comprises at least one reference to at least one item having a positive overall relevance score; and

transmitting, over the network, the list of recommended items to the selected user.

26. The computer-readable medium of claim 25 wherein each of the plurality of items has at least one intrinsic attribute and each of the plurality of data regions has at least one region dimension, wherein each of the plurality of items is assigned to one or more data regions where the at least one intrinsic attribute of the respective item matches the at least one region dimensions of the respective data region.

27. The computer-readable medium of claim 25 wherein each of the plurality of items is assigned to one of the plurality of data regions by clustering the plurality of items by at least one action performed by one or more of the plurality of users with respect to the respective item.

28. The computer-readable medium of claim 27 wherein the plurality of items is clustered using a Jaccard dissimilarity function, d(i, j), wherein

29. The computer-readable medium of claim 25 wherein the at least one source region for each of the plurality of data regions is automatically identified by the computing device using a support function, supp(r), where supp(r) is the proportion of ratings in the plurality of ratings which are assigned to one of the plurality of data regions r, wherein

conf(rr′

)=supp(r∪

r′

)/supp(r).

where r and r′

are any two of the plurality of data regions and conf(r=>

r′

) is the confidence that two regions r and r′

are correlated, wherein r is identified as a source region of r′

if conf(r=>

r′

) falls within a predetermined range.

30. The computer-readable medium of claim 25 wherein the region potential interest score is an otb score wherein

otb(u,r)=otbBase(u,r)×

otbFactor(u,r)

where

u and r denotes one of the plurality of users and one of the plurality of data regions respectively,

otbBase (u, r) is a base unfamiliarity for data region r by user u, and

otbFactor (u, r) is an exposure factor for a data region r by user u,

where

31. The computer-readable medium of claim 30 wherein the user similarity score is an expanded similarity scores, exSim(u, u′

, r), where

exSim(u,u′

,r)=max<sub>r′

ε

sources(r)</sub>userSim(u,u′

,r)

where u and u′

are two of the plurality of users and r denotes one of the plurality of data regions, and

sources(r) is the set source regions for data region r, and

where userSim(u, u′

, r) is a similarity between the two users u and u′

restricted to the data region r, where

32. The computer-readable medium of claim 31 wherein the regional relevance score is a relevance score, relevance(u,r,i), wherein

relevance(u,r,i)=Σ

<sub>u′

ε

exNetwork(u,r)</sub>exSim(u,u′

,r)×

rating(u═

,i)

where

u and u′

are two of the plurality of users, r is one of the plurality of data regions, and i one of the plurality of items

exSim(u, u′

, r) is the expanded similarity score between users u and u′

rating (u′

, i) is user u′

rating for item i

sources(r) is the set of source regions for data region r, and

exNetwork(u, r) is the set formed by users who share similar interests with u over source regions of data region r which may be defined as

u′

ε

U|exSim(u,u′

,r)≧

θ

where θ

is an application-dependent threshold.

33. The computer-readable medium of claim 32 wherein the overall relevance score is an overall relevance score, overall(u, i) where

overall(u,i):

=Σ

<sub>rε

regions(i)</sub>otb(u,r)×

relevance(u,r,i).

34. The computer-readable medium of claim 25 wherein the list of recommended items comprises references to the items having the top n overall relevance scores, where n is a fixed number.