Granted Patent B2

US 10,235,403 · App. 14/325,429 · Granted Mar 19, 2019

Abstract

Claims (63)

1. A system for matrix factorization, said system comprising:

at least one processor programmed to:

receive at least one matrix to be factorized into a plurality of lower-dimension matrices defining a latent feature model;

set at least some of the entries in the plurality of lower-dimension matrices to zero in order to apply sparsification to the plurality of lower dimension matrices; and

update the latent feature model to approximate the at least one matrix, the latent feature model including a plurality of latent features, and the update performed by:

cycling through the plurality of latent features at least once; and

alternatingly updating the plurality of lower-dimension matrices during each cycle;

wherein the update includes:

partitioning first and second matrices of the plurality of lower-dimension matrices into blocks;

dynamically assigning the blocks to a plurality of workers to alternatingly update the plurality of lower-dimension matrices during each cycle, wherein the assigning includes:

assigning the blocks of the first matrix to the plurality of workers as the plurality of workers become free to update the first matrix in parallel; and

once all of the blocks of the first matrix are assigned, and regardless of whether a worker of the plurality of workers is processing a block of the first matrix, assigning the blocks of the second matrix to the plurality of workers as the plurality of workers become free to update the second matrix in parallel;

wherein:

the at least one processor is further programmed to end the update when a current inner-iteration reduces a localized objective function to less than a specified value;

the update is performed based on cyclic coordinate descent (CCD);

the at least one matrix includes a plurality of matrices, and wherein the at least one processor is further programmed to fuse and factorize the plurality of matrices by the update;

the plurality of matrices include a user-by-item matrix and a user-by-user matrix, the user-by-item matrix describing user interactions with items, and the user-by-user matrix describing user interactions with other users; and

the at least one processor is further programmed to generate recommendations from the plurality of lower-dimension matrices without use of the at least one matrix.

2. The system according to claim 1 , wherein the at least one matrix represents a graph or a dataset of rows and columns.

3. The system according to claim 1 , wherein the at least one processor is further programmed to:

automatically optimize parameters of the latent feature model based on the at least one matrix before the update to minimize an objective function.

4. The system according to claim 1 , wherein the plurality of lower-dimension matrices are alternatingly updated in place during each cycle.

5. The system according to claim 1 , wherein the at least one processor is further programmed to:

receive a stream of updates to the at least one matrix in real time; update the at least one matrix with the updates of the stream;

project a new column or row of the at least one matrix into a latent feature space of the latent feature model, the column or row newly added to the at least one matrix by the updates; and

add the projection to the plurality of lower-dimension matrices.

6. A method for matrix factorization, said method comprising:

receiving, by at least one processor, at least one matrix to be factorized into a plurality of lower-dimension matrices defining a latent feature model;

setting at least some of the entries in the plurality of lower-dimension matrices to zero in order to apply sparsification to the plurality of lower dimension matrices; and

updating, by the at least one processor, the latent feature model to approximate the at least one matrix, the latent feature model including a plurality of latent features, and the updating performed by:

cycling through the plurality of latent features at least once;

and

alternatingly updating the plurality of lower-dimension matrices during each cycle;

wherein the updating further includes:

partitioning first and second matrices of the plurality of lower-dimension matrices into blocks;

dynamically assigning the blocks to a plurality of workers of the at least one processor to alternatingly update the plurality of lower-dimension matrices during each cycle, wherein the assigning includes:

assigning the blocks of the first matrix to the plurality of workers as the plurality of workers become free to update the first matrix in parallel; and

updating the second matrix in parallel by: once all of the blocks of the first matrix are assigned, and regardless of whether a worker of the plurality of workers is processing a block of the first matrix, assigning the blocks of the second matrix to the plurality of workers as the plurality of workers become free;

wherein:

the updating is ended when a current inner-iteration reduces a localized objective function to less than a specified value;

the updating is performed based on cyclic coordinate descent (CCD);

the at least one matrix includes a plurality of matrices, and wherein the method further includes fusing and factorizing the plurality of matrices by the updating;

the plurality of matrices include a user-by-item matrix and a user-by-user matrix, the user-by-item matrix describing user interactions with items, and the user-by-user matrix describing user interactions with other users; and

the method further includes generating recommendations from the plurality of lower-dimension matrices without use of the at least one matrix.

7. The method according to claim 6 , further including:

automatically optimizing parameters of the latent feature model based on the at least one matrix before the updating to minimize an objective function.

8. The method according to claim 6 , wherein the plurality of lower-dimension matrices are alternatingly updated in place during each cycle.

9. The method according to claim 6 , further including:

receiving a stream of updates to the at least one matrix in real time;

updating the at least one matrix with the updates of the stream;

projecting a new column or row of the at least one matrix into a latent feature space of the latent feature model, the column or row newly added to the at least one matrix by the updates; and

adding the projection to the plurality of lower-dimension matrices.

10. The system according to claim 1 , wherein the specified value is EΔ max , where E is a positive ratio, and Δ max is a maximum function reduction for past inner iterations of a current outer iteration.

11. The method according to claim 6 , wherein the specified value is EΔ max , where E is a positive ratio, and Δ max is a maximum function reduction for past inner iterations of a current outer iteration.

12. A system for matrix factorization, said system comprising:

at least one processor programmed to:

randomly initialize each of a user feature matrix, an item feature matrix and a social network feature matrix;

set at least some of the entries in each of the user feature matrix, the item feature matrix and the social network feature matrix to zero in order to apply sparsification to each of the user feature matrix, the item feature matrix and the social network feature matrix;

alternatingly update, using column-wise updates, each of the user feature matrix, the item feature matrix and the social network feature matrix, the update including:

partitioning each of the user feature matrix, the item feature matrix and the social network feature matrix into blocks;

dynamically assigning the blocks to a plurality of workers to alternatingly update the user feature matrix, the item feature matrix and the social network feature matrix during each cycle, wherein the assigning includes:

assigning the blocks of a first matrix of the user feature matrix, the item feature matrix and the social network feature matrix to the plurality of workers as the plurality of workers become free to update the first matrix in parallel; and

once all of the blocks of the first matrix are assigned, and regardless of whether a worker of the plurality of workers is processing a block of the first matrix, assigning the blocks of a second matrix of the user feature matrix, the item feature matrix and the social network feature matrix to the plurality of workers as the plurality of workers become free to update the second matrix in parallel.

Assignments (10)

Cited By (1)

US 12,406,189