Providing Personalized Item Recommendations Using Scalable Matrix Factorization With Randomness

Abstract

Some embodiments include a method of providing personalized item recommendations using scalable matrix factorization with randomness. Other embodiments of related systems and methods are also disclosed.

What is claimed is: 
     
         1 . A method of providing personalized item recommendations to at least one user of a plurality of users based on item interactions by the plurality of users, the method being implemented via execution of computer instructions configured to run at one or more processing modules and configured to be stored at one or more non-transitory memory storage modules, the method comprising:
 receiving an item interaction matrix, denoted by A, wherein the item interaction matrix A has a plurality of rows corresponding to the plurality of users, a number of rows of the item interaction matrix A equals a number of the plurality of users, the item interaction matrix A has a plurality of columns corresponding to item interaction weightings for a plurality of items, and a number of columns of the item interaction matrix A equals a number of potential item interaction weightings; and   factorizing the item interaction matrix A into a user feature matrix, denoted by P, and an item feature matrix, denoted by Q, the factorizing comprising:
 generating the item feature matrix Q comprising:
 computing a thin matrix, denoted by B, wherein the thin matrix B is an estimated projection of the item interaction matrix A, a number of rows of the thin matrix B is equal to a selected number of latent factors, and the number of rows of the thin matrix B is less than the number of the plurality of users; 
 performing a singular value decomposition on the thin matrix B; and 
 computing the item feature matrix Q; and 
 
 computing the user feature matrix P by performing alternative least squares using the item feature matrix Q; 
   computing item interaction scores using the user feature matrix P and the item feature matrix Q; and   selecting at least one item of the plurality of items for recommendation to at least one user from the plurality of users based on the item interaction scores.   
     
     
         2 . The method of  claim 1 , wherein receiving the item interaction matrix A comprises:
 receiving two or more item interaction type matrices each having rows and columns, wherein the rows of each of the two or more item interaction type matrices correspond to a plurality of users, and the columns of each of the two or more item interaction type matrices correspond to item interaction weightings for a type of item interaction for a plurality of items; and   generating the item interaction matrix A by concatenating the two or more item interaction type matrices.   
     
     
         3 . The method of  claim 2 , wherein the two or more item interaction type matrices comprise at least one of: (a) an item purchase type matrix, (b) an item browse type matrix, (c) an item search type matrix, and (d) an item cart type matrix. 
     
     
         4 . The method of  claim 1 , wherein each of the item interaction weightings are calculated based on an item interaction, a time decay adjustment, and an item popularity adjustment. 
     
     
         5 . The method of  claim 1 , wherein the number of rows of thin matrix B is not more than 1000. 
     
     
         6 . The method of  claim 1 , wherein the number of rows of thin matrix B is not more than 0.01% of the number of the plurality of users. 
     
     
         7 . The method of  claim 1 , wherein the number of the plurality of users is greater than or equal to 500,000, and the number of potential item interaction weightings is greater than or equal to 100,000. 
     
     
         8 . The method of  claim 1 , wherein computing the thin matrix B comprises:
 generating a random Gaussian matrix, denoted by G, wherein the random Gaussian matrix G has a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors;   computing a matrix Y, wherein the matrix Y is a matrix product of the item interaction matrix A and the random Gaussian matrix G, wherein the matrix Y has a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors;   decomposing the matrix Y by a QR factorization into a matrix Q Y  and a matrix R Y , wherein the matrix Y is a matrix product of the matrix Q Y  and the matrix R Y , wherein the matrix Q Y  is an orthonormal matrix having a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors, and wherein the matrix R Y  is a matrix having a number of rows and a number of columns each equal to the selected number of latent factors; and   calculating the thin matrix B, wherein the thin matrix B is a matrix product of a transpose of the matrix Q Y  and of the item interaction matrix A, and wherein a number of columns of the thin matrix B is equal to the number of potential item interaction weightings.   
     
     
         9 . The method of  claim 8 , wherein computing the matrix Y is devoid of using a power iteration. 
     
     
         10 . The method of  claim 1 , wherein:
 performing the singular value decomposition on the thin matrix B comprises decomposing the thin matrix B into a matrix U, a matrix Σ, and a matrix V, wherein the thin matrix B is a matrix product of the matrix U, the matrix Σ, and a transpose of the matrix V, wherein the matrix U is an orthonormal matrix having a number of rows and a number of columns each equal to the selected number of latent factors, wherein the matrix Σ is a diagonal matrix having a number of rows and a number of columns each equal to the selected number of latent factors, and wherein the matrix V is an orthonormal matrix having a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors; and   computing the item feature matrix Q comprises computing a matrix product of the matrix V and a matrix square root of the matrix Σ, wherein the item feature matrix Q has a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors.   
     
     
         11 . The method of  claim 1 , wherein computing the item feature matrix Q is devoid of using the matrix U. 
     
     
         12 . The method of  claim 1 , wherein computing the user feature matrix P comprises computing the user feature matrix P by performing alternative-least-squares with weighted-λ-regularization (ALS-WR) using the item interaction matrix A and the item feature matrix Q, wherein the user feature matrix P has a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors. 
     
     
         13 . The method of  claim 12 , wherein computing the user feature matrix P further comprises performing ALS-WR though a parallel or distributed computing infrastructure. 
     
     
         14 . The method of  claim 1  wherein:
 computing the thin matrix B comprises:
 generating a random Gaussian matrix, denoted by G, wherein the random Gaussian matrix G has a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors; 
 computing a matrix Y, wherein the matrix Y is a matrix product of the item interaction matrix A and the random Gaussian matrix G, wherein the matrix Y has a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors, and wherein computing the matrix Y is devoid of using a power iteration; 
 decomposing the matrix Y by a QR factorization into a matrix Q Y  and a matrix R Y , wherein the matrix Y is a matrix product of the matrix Q Y  and the matrix R Y , wherein the matrix Q Y  is an orthonormal matrix having a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors, and wherein the matrix R Y  is a matrix having a number of rows and a number of columns each equal to the selected number of latent factors; and 
 calculating the thin matrix B, wherein the thin matrix B is a matrix product of a transpose of the matrix Q Y  and of the item interaction matrix A, and wherein a number of columns of the thin matrix B is equal to the number of potential item interaction weightings; 
 
 performing the singular value decomposition on the thin matrix B comprises decomposing the thin matrix B into a matrix U, a matrix Σ, and a matrix V, wherein the thin matrix B is a matrix product of the matrix U, the matrix Σ, and a transpose of the matrix V, wherein the matrix U is an orthonormal matrix having a number of rows and a number of columns each equal to the selected number of latent factors, wherein the matrix Σ is a diagonal matrix having a number of rows and a number of columns each equal to the selected number of latent factors, and wherein the matrix V is an orthonormal matrix having a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors; 
 computing the item feature matrix Q comprises computing a matrix product of the matrix V and a matrix square root of the matrix Σ, wherein the item feature matrix Q has a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors, and wherein computing the item feature matrix Q is devoid of using the matrix U; 
 computing the user feature matrix P comprises computing the user feature matrix P by performing alternative-least-squares with weighted-λ-regularization (ALS-WR) through a parallel or distributed computing infrastructure using the item interaction matrix A and the item feature matrix Q, wherein the user feature matrix P has a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors. 
 
     
     
         15 . The method of  claim 1 , wherein computing the item interaction scores comprises computing an item interaction score vector for a user of the plurality of users. 
     
     
         16 . The method of  claim 1 , wherein computing the item interaction scores comprises computing an item interaction scores matrix for the plurality of users. 
     
     
         17 . The method of  claim 14 , wherein:
 receiving the item interaction matrix A comprises:
 receiving two or more item interaction type matrices each having rows and columns, wherein the rows of each of the two or more item interaction type matrices correspond to a plurality of users, and the columns of each of the two or more item interaction type matrices correspond to item interaction weightings for a type of item interaction for a plurality of items, and wherein the two or more item interaction type matrices comprise at least one of: (a) an item purchase type matrix, (b) an item browse type matrix, (c) an item search type matrix, and (d) an item cart type matrix; and 
 generating the item interaction matrix A by concatenating the two or more item interaction type matrices; and 
   computing the item interaction scores comprises computing an item interaction scores matrix for the plurality of users,   wherein:
 each of the item interaction weightings are calculated based on an item interaction, a time decay adjustment, and an item popularity adjustment; 
 the number of rows of thin matrix B is not more than 0.01% of the number of the plurality of users; 
 the number of the plurality of users is greater than or equal to 500,000; and 
 the number of potential item interaction weightings is greater than or equal to 100,000. 
   
     
     
         18 . A system for providing personalized item recommendations to at least one user of a plurality of users based on item interactions by the plurality of users, the system comprising:
 one or more processing modules; and   one or more non-transitory memory storage modules storing computing instructions configured to run on the one or more processing modules and perform the acts of:
 receiving an item interaction matrix, denoted by A, wherein the item interaction matrix A has a plurality of rows corresponding to the plurality of users, a number of rows of the item interaction matrix A equals a number of the plurality of users, the item interaction matrix A has a plurality of columns corresponding to item interaction weightings for a plurality of items, and a number of columns of the item interaction matrix A equals a number of potential item interaction weightings; and 
 factorizing the item interaction matrix A into a user feature matrix, denoted by P, and an item feature matrix, denoted by Q, the factorizing comprising:
 generating the item feature matrix Q comprising:
 computing a thin matrix, denoted by B, wherein the thin matrix B is an estimated projection of the item interaction matrix A, a number of rows of the thin matrix B is equal to a selected number of latent factors, and the number of rows of the thin matrix B is less than the number of the plurality of users; 
 performing a singular value decomposition on the thin matrix B; and 
 computing the item feature matrix Q; and 
 
 computing the user feature matrix P by performing alternative least squares using the item feature matrix Q; 
 
 computing item interaction scores using the user feature matrix P and the item feature matrix Q; and 
 selecting at least one item of the plurality of items for recommendation to at least one user from the plurality of users based on the item interaction scores. 
   
     
     
         19 . The system of  claim 18 , wherein the computing instructions are further configured such that:
 computing the thin matrix B comprises:
 generating a random Gaussian matrix, denoted by G, wherein the random Gaussian matrix G has a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors; 
 computing a matrix Y, wherein the matrix Y is a matrix product of the item interaction matrix A and the random Gaussian matrix G, wherein the matrix Y has a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors, and wherein computing the matrix Y is devoid of using a power iteration; 
 decomposing the matrix Y by a QR factorization into a matrix Q Y  and a matrix R Y , wherein the matrix Y is a matrix product of the matrix Q Y  and the matrix R Y , wherein the matrix Q Y  is an orthonormal matrix having a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors, and wherein the matrix R Y  is a matrix having a number of rows and a number of columns each equal to the selected number of latent factors; and 
 calculating the thin matrix B, wherein the thin matrix B is a matrix product of a transpose of the matrix Q Y  and of the item interaction matrix A, and wherein a number of columns of the thin matrix B is equal to the number of potential item interaction weightings; 
   performing the singular value decomposition on the thin matrix B comprises decomposing the thin matrix B into a matrix U, a matrix Σ, and a matrix V, wherein the thin matrix B is a matrix product of the matrix U, the matrix Σ, and a transpose of the matrix V, wherein the matrix U is an orthonormal matrix having a number of rows and a number of columns each equal to the selected number of latent factors, wherein the matrix Σ is a diagonal matrix having a number of rows and a number of columns each equal to the selected number of latent factors, and wherein the matrix V is an orthonormal matrix having a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors;   computing the item feature matrix Q comprises computing a matrix product of the matrix V and a matrix square root of the matrix Σ, wherein the item feature matrix Q has a number of rows equal to the number of potential item interaction weightings and a number of columns equal to the selected number of latent factors, and wherein computing the item feature matrix Q is devoid of using the matrix U;   computing the user feature matrix P comprises computing the user feature matrix P by performing alternative-least-squares with weighted-λ-regularization (ALS-WR) through a parallel or distributed computing infrastructure using the item interaction matrix A and the item feature matrix Q, wherein the user feature matrix P has a number of rows equal to the number of the plurality of users and a number of columns equal to the selected number of latent factors.   
     
     
         20 . The system of  claim 19 , wherein the computing instructions are further configured such that:
 receiving the item interaction matrix A comprises:
 receiving two or more item interaction type matrices each having rows and columns, wherein the rows of each of the two or more item interaction type matrices correspond to a plurality of users, and the columns of each of the two or more item interaction type matrices correspond to item interaction weightings for a type of item interaction for a plurality of items, and wherein the two or more item interaction type matrices comprise at least one of: (a) an item purchase type matrix, (b) an item browse type matrix, (c) an item search type matrix, and (d) an item cart type matrix; and 
 generating the item interaction matrix A by concatenating the two or more item interaction type matrices; and 
   computing the item interaction scores comprises computing an item interaction scores matrix for the plurality of users,   wherein:
 each of the item interaction weightings are calculated based on an item interaction, a time decay adjustment, and an item popularity adjustment; 
 the number of rows of thin matrix B is not more than 0.01% of the number of the plurality of users; 
 the number of the plurality of users is greater than or equal to 500,000; and 
 the number of potential item interaction weightings is greater than or equal to 100,000.