Education and demonstration – Psychology
Reexamination Certificate
2000-07-31
2003-12-02
Harrison, Jessica (Department: 3714)
Education and demonstration
Psychology
C707S793000, C707S793000, C705S026640, C705S014270, C705S001100
Reexamination Certificate
active
06655963
ABSTRACT:
§1. BACKGROUND OF THE INVENTION
§1.1 Field of the Invention
The present invention concerns predicting and selectively collecting attribute values, such as a person's preferences, as might be indicated by item ratings for example. Such item ratings may be used for recommending items.
§1.2 Related Art
In last decade or so, computers have become increasingly interconnected by networks, and via the Internet. The proliferation of networks, in conjunction with the increased availability of inexpensive data storage means, has afforded computer users unprecedented access to a wealth of data. Unfortunately, however, the very vastness of available data can overwhelm a user. Desired data can become difficult to find and search heuristics employed to locate desired data often return unwanted data.
Various concepts have been employed to help users locate desired data. In the context of the Internet for example, some services have organized content based on a hierarchy of categories. A user may then navigate through a series of hierarchical menus to find content that may be of interest to them. An example of such a service is the YAHOO™ World Wide Web site on the Internet. Unfortunately, content, in the form of Internet “web sites” for example, must be organized by the service and users must navigate through menus. If a user mistakenly believes that a category will be of interest or include what they were looking for, but the category turns out to be irrelevant, the user must backtrack through one or more hierarchical levels of categories. Moreover, such services which provide hierarchical menus of categories are passive. That is, a user must actively navigate through the hierarchical menus of categories.
Again in the context of the Internet for example, some services provide “search engines” which search databased content or “web sites” pursuant to a user query. In response to a user's query, a rank ordered list, which includes brief descriptions of the uncovered content, as well as hypertext links (text, having associated Internet address information, which, when activated, commands a computer to retrieve content from the associated Internet address) to the uncovered content is returned. The rank ordering of the list is typically based on a match between words appearing in the query and words appearing in the content. Unfortunately, however, present limitations of search heuristics often cause irrelevant content to be returned in response to a query. Again, unfortunately, the very wealth of available content impairs the efficacy of these search engines since it is difficult to separate irrelevant content from relevant content.
Moreover, as was the case with services which provide hierarchical menus of categories, search engines are passive. That is, a user must actively submit a query. To address this disadvantage, systems for recommending an item, such as content, to a user have been implemented.
§1.2.1 Recommender Systems
So-called “recommender systems” have been implemented to recommend an item, such as content, a movie, a book, or a music album for example, to a user. The growth of Internet commerce has stimulated the use of collaborative filtering algorithms as recommender systems. (See, e.g., the article, Schafer et al., “Recommender Systems in E-Commerce”,
Proceedings of the ACM Conference on Electronic Commerce
, pp. 158-166 (November 1999), hereafter referred to as “the Schafer article”.) Although collaborative filtering may be known to one skilled in the art, it is introduced below for the reader's convenience.
§1.2.2 Collaborative Filtering
In view of the drawbacks of the above discussed data location concepts, “collaborative filtering” systems have been developed. A goal of collaborative filtering is to predict the attributes of one user (referred to as “the active user”), based on the attributes of a group of users. Given the growth of Internet commerce, a valuable attribute to predict is an active user's preference for an item. For example, given the active user's ratings for several movies and a database of other users' movie ratings, a collaborative filtering system may be used to predict how the active user would rate movies not seen by the active user (but rated by the other users). More specifically, collaborative filtering systems have assumed that an active user will have similar attributes as similar users and, conversely, collaborative filtering systems may assume that an active user will have dissimilar attributes to dissimilar users. Again, in the context of preferences, similar users may prefer similar items and dissimilar users may prefer dissimilar items. Hence, the effectiveness of collaborative filtering methods has been predicated on the underlying assumption that human preferences are correlated.
Collaborative filtering techniques have been classified into one of two categories—memory-based and model-based. (See, e.g., the article, Breese et al., “Empirical Analysis of Predictive Algorithms for Collaborative Filtering”,
Proceedings of the Fourteenth Annual Conference on Uncertainty in Artificial Intelligence
, pp. 43-52 (July 1998), hereafter referred to as “the Breese article”.) Memory-based collaborative filtering techniques, and drawbacks of such techniques, are introduced in §1.2.2.1 below. Then, model-based collaborative filtering techniques, and drawbacks of such techniques, are introduced in §1.2.2.2 below.
§1.2.2.1 Memory-based Collaborative Filtering Techniques and Their Shortcomings
Memory-based collaborative filtering techniques maintain a database of all users' known attribute values (e.g., item ratings). Each predicted attribute value requires a computation using data from across the entire database.
Examples of memory-based collaborative filtering techniques may be found in the Breese article. Basically, collaborative filtering uses known attribute values (e.g., explicitly entered votes) of a new user (referred to as “the active case”) and known attribute values of other users to predict values of attributes with unknown values of the new user (e.g., attribute values not yet entered by the new user). The mean vote {overscore (v)}
i
for an entity may be defined as:
v
i
_
=
1
M
i
∑
j
∈
I
i
v
i
,
j
where
v
i,j
≡A value of attribute j of entity i. Typically, an integer value.
M≡The number of attributes (e.g., in a database).
I
i
≡A set of attribute indexes for which entity I has known values (e.g., based on an explicitly entered vote). For example, I
2
={3,4} means that entity
2
has values for attributes
3
and
4
.
M
i
≡The number of attributes for which entity i has known values—the number of elements in I
i
.
Denoting parameters for the active case (i.e., new entity) with subscript “a”, a prediction p
a,j
of active case attribute values (e.g., item ratings) for attributes without known values (i.e., attributes not in I
a
) can be defined as:
p
a
,
j
=
v
a
_
+
K
∑
i
=
1
,
n
(
v
i
,
j
-
v
i
_
)
w
a
,
i
where
K is a normalizing factor such that the absolute values of the weights sum to unity.
n≡The number of entities (e.g., users in a database).
w
a,i
≡The estimated weight (or alternatively match) between entity i and entity a.
P
i,j
≡The predicted value of attribute j of entity i.
Hence, a predicted attribute value (e.g., item rating) is calculated from a weighted sum of the attribute values (e.g., votes) of each other user. The appearance of mean values in the formula merely serves to express values in terms of deviation from the mean value (i.e., defines a reference) and has no other significant impact.
The weights can reflect distance, correlation, or similarity between each user “i” and the active user. Many collaborative filtering algorithms differ in the details of the “weight” calculation. Two examples of weight determination techniques are correlation and vector similarity, each of which is briefly introduced below.
The use of correlation for a weight calculation appears i
Horvitz Eric J.
Pennock David M.
Amin & Turocy LLP
Harris Chanda L.
Harrison Jessica
Microsoft Corporation
LandOfFree
Methods and apparatus for predicting and selectively... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for predicting and selectively..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for predicting and selectively... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3130664