Methods and apparatus for modeling relationships at multiple scales in ratings estimation
View Patent ↗Systems and techniques for generating item ratings for a user in order to allow for recommendations of selected items for that user. A set of known ratings of different items for a plurality of users is collected and maintained, and these known ratings are used to estimate rating factors influencing ratings, including user and item factors. Initial user and item factors are estimated and new user and item factors are successively added, with the original rating factors being progressively shrunk so as to reduce their magnitude and their contribution to the rating estimation as successive factors are added. When an appropriate number of user and item factors has been estimated, the rating factors are used to estimate ratings of items for a user, and the estimated ratings are employed to generate recommendations for that user.
1. A method for estimating a rating of a first item by a first user, using a sparse matrix of known ratings κ={(u, i)|r ui is known} wherein r ui are ratings by users u for items i, comprising:
by a processor, iteratively pre-computing a matrix P containing a plurality of user factors for each user u and a matrix Q containing a plurality of item factors for each item i, by performing the following for each f th successive factor until a difference between factor-based estimates and known ratings κ is below a threshold value:
computing a residual res ui for each known rating r ui as follows:
res
ui
←
r
ui
-
∑
l
=
1
f
-
1
P
ul
Q
il
;
adjusting the residual res ui to provide shrinkage as follows:
res
ui
←
support
ui
res
ui
support
ui
+
α
f
,
wherein α is a constant and support ui is a support behind the known rating r ui ;
computing an f th user factor P uf for each user u:
P
uf
←
∑
i
:
(
u
,
i
)
∈
k
res
ui
Q
if
∑
i
:
(
u
,
i
)
∈
k
Q
if
2
;
computing an f th item factor Q if for each item i:
Q
if
←
∑
u
:
(
u
,
i
)
∈
k
res
ui
P
uf
∑
u
:
(
u
,
i
)
∈
k
P
uf
2
;
and
by the processor, estimating the rating of the first item by the first user, as a vector product of item factors Q if for the first item and user factors P uf for the first user.
2. The method of claim 1 , wherein the difference between factor-based estimates and known ratings κ is defined as an error function Err(P, Q):
Err
(
P
,
Q
)
=
∑
(
u
,
i
)
(
r
ui
-
p
u
T
q
i
)
2
,
wherein p u is a u th row of P and q i is an i th column of Q.
3. The method of claim 1 , wherein the items are movies and the users are movie distribution service users.
4. The method of claim further comprising determining an optimal number of factors f so as to capture the most prominent features of the ratings data while leaving out relatively insignificant features.
5. The method of claim 1 , wherein the factors f are late features of the sparse matrix not requiring additional external information.
6. The method of claim 1 , wherein iteratively pre-computing the matrix P and the matrix Q is performed off-line.
7. The method of claim 6 , wherein iteratively pre-computing the matrix P and the matrix Q is performed upon receipt of new rating data.
8. The method of claim 1 , wherein the support support ui behind the known rating r ui is a minimum of a number of ratings by a user u and a number of users that rated item i.
9. A non-transitory computer-usable medium having computer readable instructions stored thereon for execution by a processor to perform a method for estimating a rating of a first item by a first user, using a sparse matrix of known ratings κ={(u, i)|r ui is known} wherein r ui are ratings by users u for items the method comprising:
iteratively pre-computing a matrix P containing a plurality of user factors for each user u and a matrix Q containing a plurality of item factors for each item i, by performing the following for each f th successive factor until a difference between factor-based estimates and known ratings κ is below a threshold value:
computing a residual res ui for each known rating r ui as follows:
res
ui
←
r
ui
-
∑
l
=
1
f
-
1
P
ul
Q
il
;
adjusting the residual res ui to provide shrinkage as follows:
res
ui
←
support
ui
res
ui
support
ui
+
α
f
,
wherein α is a constant and support ui is a support behind the known rating r ui ;
computing an f th user factor P uf for each user u:
P
uf
←
∑
i
:
(
u
,
i
)
∈
k
res
ui
Q
if
∑
i
:
(
u
,
i
)
∈
k
Q
if
2
;
and
computing any f th item factor Q if for each item i:
Q
if
←
∑
u
:
(
u
,
i
)
∈
k
res
ui
P
uf
∑
u
:
(
u
,
i
)
∈
k
P
uf
2
;
and
estimating the rating of the first item by he first user, as a vector product of item factors Q if for the first item and user factors P uf for the first user.
10. The non-transitory computer-usable medium of claim 9 , wherein the difference between factor-based estimates and known ratings κ is defined as an error function Err(P,Q):
Err
(
P
,
Q
)
=
∑
(
u
,
i
)
(
r
ui
-
p
u
T
q
i
)
2
,
wherein p u is a u th row of P and q i is an i th column of Q.
11. The non-transitory computer-usable medium of claim 9 , wherein the items are movies and the users are movie distribution service users.
12. The non-transitory computer-usable medium of claim 9 , wherein the method further comprises determining an optimal number of factors f so as to capture the most prominent features of the ratings data while leaving out relatively insignificant features.
13. The non-transitory computer-usable medium of claim 9 , wherein the factors f are latent features of the sparse matrix not requiring additional external information.
14. The non-transitory computer-usable medium of claim 9 , wherein iteratively pre-computing the matrix P and the matrix Q is performed off-line.
15. The non-transitory computer-usable medium of claim 14 , wherein iteratively pre-computing the matrix P and the matrix Q is performed upon receipt of new rating data.
16. The non-transitory computer-usable medium of claim 9 , wherein the support support ui behind the known rating r ui is a minimum of a number of ratings by a user u and a number of users that rated item i.