Distributed and privacy-preserving prediction method

Patent metadata

Field	Value
Publication number	US-10102478-B2
Application number	US-201514752129-A
Country	US
Kind code	B2
Filing date	Jun 26, 2015
Priority date	Jun 26, 2015
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

Each computer of a peer-to-peer (P2P) network performs an iterative computer-based modeling task defined by a set of training data including at least some training data that are not accessible to the other computers of the P2P network, and by a set of parameters including a shared parameter. The modeling task optimizes an objective function comparing a model parameterized by the set of parameters with the training data. Each iteration includes: performing an iterative gradient step update of parameter values stored at the computer based on the objective function; receiving parameter values of the shared parameter from other computers of the P2P network; adjusting the parameter value of the shared parameter stored at the computer by averaging the received parameter values; and sending the parameter value of the shared parameter stored at the computer to other computers of the P2P network.

First claim

The invention claimed is:

1. A non-transitory storage medium storing instructions executable by a local computer to perform iterative computer-based modeling in conjunction with remote computers connected with the local computer as a peer-to-peer (P2P) network, the iterative computer-based modeling including the operations of:
receiving, at the local computer, parameter values of shared parameters from the remote computers via the P2P network;
storing, at the local computer, parameter values for a set of parameters including at least the shared parameters;
performing an iterative gradient step update to update the parameter values of the set of parameters stored at the local computer, the iterative gradient step updates of the iterative computer-based modeling operating to optimize an objective function that is not known to the remote computers and that is functionally dependent upon the set of parameters wherein the objective function quantitatively compares a model with a set of training data including at least some training data accessible by the local computer that are not accessible by the remote computers;
adjusting the parameter values of the shared parameters stored at the local computer by averaging parameter values of the shared parameters received at the local computer from remote computers via the P2P network wherein the adjusting comprises adjusting the parameter value θ u i stored at the local computer of each shared parameter θ u by averaging the parameter values θ u ij ∈q u i of the shared parameter θ u received at the local computer from the remote computers according to:
θ u i ←a u ii θ u i +Σ {θ u ij ∈q u i } a u ij θ u ij

where θ u denotes the shared parameter, θ u i is the parameter value for the shared parameter stored at the local computer, q u i is the set of parameter values for the shared parameter θ u received at the local computer from remote computers via the P2P network, a u ii is a weight assigned to the parameter value of the shared parameter stored at the local computer, and a u ij is a weight assigned to the parameter value of the shared parameter θ u received at the local computer from the j th remote computer via the P2P network; and
sending the parameter values of the shared parameters stored at the local computer from the local computer to the remote computers via the P2P network.

2. The non-transitory storage medium of claim 1 wherein each iteration of the iterative modeling process includes performing an iterative gradient step update, adjusting the parameter values, and sending the parameter values.

3. The non-transitory storage medium of claim 2 wherein in each iteration of the iterative modeling process the sending is performed after the adjusting and comprises sending the adjusted parameter values.

4. The non-transitory storage medium of claim 1 wherein
Σ( a u ii +Σ {θ u ij ∈q u i } a u ij )=1

and the weights a u ii and a u ij have non-negative values.

5. The non-transitory storage medium of claim 1 wherein the iterative gradient step update comprises updating the parameter value θ u i stored at the local computer for each shared parameter θ u according to:
θ u i ←a u ii θ u i −γ u i ∇ θ u ƒ i (θ i )

where ƒ i (θ i ) denotes the objective function that is functionally dependent upon the set of parameters denoted θ i , ∇ θ u denotes a gradient operator with respect to the shared parameter θ u , and γ u i denotes a step size for the iterative gradient step update.

6. The non-transitory storage medium of claim 1 wherein the iterative gradient step update comprises a matrix factorization update factorizing a matrix Y i representing the set of training data into factor matrices U i and V i defined by the set of parameters θ i to optimize an objective function ƒ i (θ i ) quantifying a difference |U i V i −Y i |.

7. The non-transitory storage medium of claim 6 wherein the training data comprises text-based documents, the matrix Y i represents the text-based documents as a document-word matrix, the factor matrix U i comprises parameters of the set of parameters representing document embeddings which are not shared parameters, and the factor matrix V i comprises parameters of the set of parameters representing word embeddings which are the shared parameters of the set of parameters.

8. A computer-based modeling system comprising:
a plurality of computers interconnected as a peer-to-peer (P2P) network to send parameter values of one or more shared parameters between sender and recipient computers of the P2P network,
wherein each computer of the P2P network is programmed to perform an iterative computer-based modeling task defined by a set of training data including at least some training data that are not accessible to the other computers of the P2P network and by a set of parameters including the one or more shared parameters, the iterative computer-based modeling task optimizing an objective function that is not known to the other computers of the plurality of computers and that quantitatively compares a model parameterized by the set of parameters with the set of training data, wherein each iteration of the iterative computer-based modeling task includes:
storing, at the computer, parameter values for a set of parameters including at least the one or more shared parameters;
performing an iterative gradient step update of the parameter values of the set of parameters stored at the computer based on the objective function;
receiving, at the computer, parameter values of the one or more shared parameters of the set of parameters from other computers of the plurality of computers via the P2P network;
adjusting the parameter values of the one or more shared parameters stored at the computer by averaging the received parameter values of the one or more shared parameters wherein the adjusting comprises adjusting the parameter value θ u i stored at the computer of each shared parameter θ u by averaging the parameter values θ u ij ∈q u i of the shared parameter θ u received at the local computer from the other computers according to:
θ u i ←a u ii θ u i +Σ {θ u ij ∈q u i } a u ij θ u ij

where θ u denotes the shared parameter, θ u i is the parameter value for the shared parameter stored at the computer, q u i is the set of parameter values for the shared parameter θ u received from the other computers during the receiving operation, a u ii is a weight assigned to the parameter value θ u i stored at the computer of the shared parameter θ u stored at the computer, and a u ij is a weight assigned to the parameter value θ u ij of the shared parameter θ u received during the receiving operation from a j th other computer of the P2P network; and
sending the parameter values of the one or more shared parameters stored at the computer to the other computers of the P2P network.

9. The computer-based modeling system of claim 8 wherein in each iteration of the computer-based modeling the adjusting is performed after the iterative gradient step update and the sending is performed after the adjusting.

10. The computer-based modeling system of claim 8 wherein
Σ( a u ii +Σ {θ u ij ∈q u i } a u ij )=1

and the weights a u ii and a u ij have non-negative values.

11. The computer-based modeling system of claim 8 wherein the iterative gradient step update comprises a matrix factorization update factorizing a matrix Y i representing the set of training data into factor mat

Assignees

• Conduent Business Services Llc
• Conduent Business Services Inc

Inventors

• Bouchard Guillaume
• Perez Julien
• Henderson James Brinton

Classifications

• G06N99/005

  Physics · mapped topic

• H04L67/104

  Peer-to-peer [P2P] networks · CPC title

• G06N7/005 Primary

  Physics · mapped topic

• G06F21/6263

  during internet communication, e.g. revealing personal data from cookies · CPC title

• H04W4/21

  for social networking applications · CPC title