DECENTRALIZED RECOMMENDATIONS USING DISTRIBUTED AVERAGE CONSENSUS

• US 20190228453A1
• Filed: 01/18/2019
• Published: 07/25/2019
• Est. Priority Date: 01/19/2018
• Status: Active Grant

• Current Assignee: Hypernet Labs Incorporated
• Original Assignee: Hyperdyne, Inc. (InnovaQuartz, LLC)
• Inventors: Chapman, Todd Allen, Ravlich, Ivan James, Hansen, Christopher Taylor, Maren, Daniel
• Granted Patent: US 10,878,482 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 30/0255 based on user history
• CPC Class Codes: G06Q 30/0631 Item recommendations
• CPC Class Codes: H04L 65/40 Support for services or applications
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A distributed computing device stores user preference data representing preferences of a user with respect to a portion of a set of items. The distributed computing device randomly samples the user preference data to calculate sampled user preference data. The distributed computing device iteratively executes, in conjunction with additional distributed computing devices connected by a network, a process to determine a consensus result for the sampled user preference data. The consensus result is based on the sampled user preference data and additional sampled user preference data calculated by the additional distributed computing devices and based on preferences of additional users. The distributed computing device determines a recommendation model based on the consensus result, the recommendation model reflecting preferences of the user and additional users. The distributed computing device identifies an item to provide to the user as a recommendation based on the recommendation model, and provides recommendation to the user.

Claims

1. A computer-implemented method for generating personalized recommendations comprising:

storing, at a distributed computing device, user preference data representing preferences of a user with respect to a portion of a set of items;

calculating, by the distributed computing device, sampled user preference data by randomly sampling the user preference data;

iteratively executing, by the distributed computing device, in conjunction with a plurality of additional distributed computing devices connected to the distributed computing device by a network, a process to determine a consensus result for the sampled user preference data, the consensus result based on the sampled user preference data calculated by the distributed computing device and additional sampled user preference data calculated by the plurality of additional distributed computing devices, the additional sampled user preference data based on preferences of a plurality of additional users;

determining, by the distributed computing device, a recommendation model based on the consensus result for the sampled user preference data, the recommendation model reflecting the preferences of the user and the plurality of additional users;

identifying, by the distributed computing device, an item of the set of items to provide to the user as a recommendation based on the recommendation model; and

providing, by the distributed computing device, the recommendation of the item to the user.

2. The method of claim 1, wherein the user preference data is a user preference vector, each element in the user preference vector corresponds to an item of the set of items, and wherein calculating the sampled user preference data by randomly sampling the user preference data comprises calculating a sampled user preference matrix by multiplying a random matrix and the user preference vector.

3. The method of claim 2, wherein the consensus result is a global consensus matrix of a same dimensionality as the sampled user preference matrix, and wherein determining a recommendation model based on the consensus result for the sampled user preference data comprises extracting the recommendation model from the global consensus matrix using orthogonal decomposition.

4. The method of claim 3, wherein identifying an item of the set of items to provide to the user as a recommendation based on the recommendation model comprises:

projecting the user preference vector onto the extracted recommendation model to obtain a personalized recommendation vector; and

identifying the item of the set of items to provide to the user as the recommendation based on a value of an element in the personalized recommendation vector corresponding to the item.

5. The method of claim 1, wherein iteratively executing the process to determine the consensus result comprises, for a first iteration of the process:

transmitting, over the network, the sampled user preference data of the distributed computing device to a second distributed computing device of the plurality of additional distributed computing devices;

receiving, over the network, second sampled user preference data generated by the second distributed computing device from the second distributed computing device; and

calculating consensus sampled user preference data by computing an average of the sampled user preference data and the second sampled user preference data.

6. The method of claim 5, wherein iteratively executing the process to determine the consensus result comprises, for a second iteration of the process:

transmitting, over the network, the consensus sampled user preference data of the distributed computing device to a third distributed computing device of the plurality of additional distributed computing devices;

receiving, over the network, an additional consensus sampled user preference data generated by the third distributed computing device from the third distributed computing device; and

updating the consensus sampled user preference data by computing an average of the consensus sampled user preference data and the additional consensus sampled user preference data.

7. The method of claim 6, wherein, after a plurality of iterations, the consensus sampled user preference data calculated by the distributed computing device substantially converges with consensus sampled user preference data calculated by each of remaining ones of the plurality of additional computing devices, and the consensus sampled user preference data calculated by the distributed computing device is the consensus result.

8. The method of claim 5, wherein randomly sampling the user preference data obscures the user preference data, such that the second distributed computing device cannot recover the user preference data from the sampled user preference data.

9. The method of claim 1, wherein iteratively executing the process to determine the consensus result comprises, for each iteration of the process:

transmitting, over the network, a first convergence indicator of the distributed computing device to a second distributed computing device of the plurality of additional distributed computing devices;

receiving, over the network, a second convergence indicator of the second distributed computing device from the second distributed computing device;

updating the first convergence indicator of the distributed computing device by determining a center of mass of the first convergence indicator and the second convergence indicator; and

determining whether the consensus result has been obtained based on the updated first convergence indicator.

10. The method of claim 9, wherein determining whether the consensus result has been obtained based on the updated first convergence indicator comprises determining that the first convergence indicator of the distributed computing device is within a threshold distance of a global center of mass of the first convergence indicator.

11. A non-transitory computer readable storage medium configured to store program code, the program code comprising instructions that, when executed by one or more processors, cause the one or more processors to:

store user preference data representing preferences of a user with respect to a portion of a set of items;

calculate sampled user preference data by randomly sampling the user preference data;

iteratively execute, in conjunction with a plurality of additional distributed computing devices connected to the distributed computing device by a network, a process to determine a consensus result for the sampled user preference data, the consensus result based on the sampled user preference data and additional sampled user preference data calculated by the plurality of additional distributed computing devices, the additional sampled user preference data based on preferences of a plurality of additional users;

determine a recommendation model based on the consensus result for the sampled user preference data, the recommendation model reflecting the preferences of the user and the plurality of additional users;

identify an item of the set of items to provide to the user as a recommendation based on the recommendation model; and

provide the recommendation of the item to the user.

12. The non-transitory computer readable storage medium of claim 11, wherein the user preference data is a user preference vector, each element in the user preference vector corresponds to an item of the set of items, and wherein the instructions to calculate the sampled user preference data by randomly sampling the user preference data comprise instructions to calculate a sampled user preference matrix by multiplying a random matrix and the user preference vector.

13. The non-transitory computer readable storage medium of claim 12, wherein the consensus result is a global consensus matrix of a same dimensionality as the sampled user preference matrix, and wherein the instructions to determine a recommendation model based on the consensus result for the sampled user preference data comprise instructions to extract the recommendation model from the global consensus matrix using orthogonal decomposition.

14. The non-transitory computer readable storage medium of claim 13, wherein the instructions to identify an item of the set of items to provide to the user as a recommendation based on the recommendation model comprise instructions to:

project the user preference vector onto the extracted recommendation model to obtain a personalized recommendation vector; and

identify the item of the set of items to provide to the user as the recommendation based on a value of an element in the personalized recommendation vector corresponding to the item.

15. The non-transitory computer readable storage medium of claim 11, wherein the instructions to iteratively execute the process to determine the consensus result comprise instructions to, for a first iteration of the process:

transmit, over the network, the sampled user preference data to a second distributed computing device of the plurality of additional distributed computing devices;

receive, over the network, second sampled user preference data generated by the second distributed computing device from the second distributed computing device; and

calculate consensus sampled user preference data by computing an average of the sampled user preference data and the second sampled user preference data.

16. The non-transitory computer readable storage medium of claim 15, wherein the instructions to iteratively execute the process to determine the consensus result comprise instructions to, for a second iteration of the process:

transmit, over the network, the consensus sampled user preference data to a third distributed computing device of the plurality of additional distributed computing devices;

receive, over the network, an additional consensus sampled user preference data generated by the third distributed computing device from the third distributed computing device; and

update the consensus sampled user preference data by computing an average of the consensus sampled user preference data and the additional consensus sampled user preference data.

17. The non-transitory computer readable storage medium of claim 16, wherein, after a plurality of iterations, the consensus sampled user preference data substantially converges with additional consensus sampled user preference data calculated by each of remaining ones of the plurality of additional computing devices, and the consensus sampled user preference data is the consensus result.

18. The non-transitory computer readable storage medium of claim 15, wherein randomly sampling the user preference data obscures the user preference data, such that the second distributed computing device cannot recover the user preference data from the sampled user preference data.

19. The non-transitory computer readable storage medium of claim 11, wherein the instructions to iteratively execute the process to determine the consensus result comprise instructions to, for each iteration of the process:

transmit, over the network, a first convergence indicator to a second distributed computing device of the plurality of additional distributed computing devices;

receive, over the network, a second convergence indicator of the second distributed computing device from the second distributed computing device;

update the first convergence indicator by determining a center of mass of the first convergence indicator and the second convergence indicator; and

determine whether the consensus result has been obtained based on the updated first convergence indicator.

20. The non-transitory computer readable storage medium of claim 19, wherein the instructions to determine whether the consensus result has been obtained based on the updated first convergence indicator comprise instructions to determine that the first convergence indicator is within a threshold distance of a global center of mass of the first convergence indicator.