Computerized matrix factorization and completion to infer median/mean confidential values

• US 10,262,154 B1
• Filed: 06/09/2017
• Issued: 04/16/2019
• Est. Priority Date: 06/09/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kenthapadi, Krishnaram, Ambler, Stuart MacDonald
• Primary Examiner(s): Nipa, Wasika
• Application Number:
  US15/618,554
• Time in Patent Office: 676 Days
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In an example embodiment, an anonymized set of confidential data values is obtained for a plurality of combinations of cohorts having a first attribute type and a second attribute type. A matrix of the confidential data values having the first attribute type as a first axis and the second attribute type as the second axis is constructed. A set of candidate low rank approximations of the matrix is calculated using an objective function evaluated using a set of candidate data transformation functions, the objective function having one or more parameters and an error function. One or more parameters that minimize the error function of the objective function are minimized to select one of the candidate low rank approximations of the matrix. Then one or more cells that are missing data, of the selected one of the candidate low rank approximations of the matrix, are inferred.

Claims

1. A system comprising:

one or more hardware processors;

a computer-readable medium having instructions stored thereon, which, when executed by a processor, cause the system to;

obtain, using the one or more hardware processors, an anonymized set of confidential data values for a plurality of combinations of cohorts having a first attribute type and a second attribute type, the confidential data values received via a computerized user interface implemented as a screen of a graphical user interface, the confidential data values entered into a field of the screen of the graphical user interface;

construct, using the one or more hardware processors, a matrix of the confidential data values having the first attribute type as a first axis and the second attribute type as a second axis, with each cell in the matrix corresponding to corresponding different combinations of attributes of the first attribute type and the second attribute type;

compute, using the one or more hardware processors, a set of candidate low rank approximations of the matrix using an objective function evaluated using a set of candidate data transformation functions, the objective function having one or more parameters and an error function, wherein computing a set of candidate low rank approximations includes, for each candidate data transformation function from the set;

applying, using the one or more hardware processors, the candidate data transformation function to the matrix;

obtaining, using the one or more hardware processors, a training matrix by hiding a preset fraction of entries of the transformed matrix;

for each of one or more candidate parameter values for one of the one or more parameters;

computing, using the one or more hardware processors, the objective function using the candidate parameter value; and

calculating, using the one or more hardware processors, the error function using the candidate parameter value;

optimize, using the one or more hardware processors, the one or more parameters that minimizes the error function of the objective function to select one of the candidate low rank approximations of the matrix; and

infer, using the one or more hardware processors, one or more cells that are missing data, of the selected one of the candidate low rank approximations of the matrix.

2. The system of claim 1, wherein the constructing the matrix includes using a machine learning model to generate median confidential data values for one or more cells along with corresponding confidence scores.

3. The system of claim 1, wherein the inferring the one or more cells that are missing data includes:

for each cell that is missing data, of the selected one of the candidate low rank approximations of the matrix;

determining if the cell that is missing data is present in the matrix of the confidential data values; and

in response to a determination that the cell that is missing data is present in the matrix of confidential data values, applying an inverse of the selected candidate low rank approximations to the cell that is missing data.

4. The system of claim 1, wherein the inferring the one or more cells that are missing data includes:

for each cell that is missing data, of the selected one of the candidate low rank approximations of the matrix;

determining if the cell that is missing data is present in the matrix of the confidential data values; and

in response to a determination that the cell that is missing data is not present in the matrix of confidential data values, applying the selected candidate low rank approximation to a corresponding cell in an optimized matrix formed by applying the selected candidate low rank approximation to the matrix of confidential values.

5. The system of claim 1, wherein the set of candidate data transformation functions includes identity, log, and square root transformations.

6. The system of claim 1, wherein the set of candidate data transformation functions includes monotonic transformations.

7. A computerized method comprising:

obtaining, using a hardware processor, an anonymized set of confidential data values for a plurality of combinations of cohorts having a first attribute type and a second attribute type, the confidential data values received via a computerized user interface implemented as a screen of a graphical user interface, the confidential data values entered into a field of the screen of the graphical user interface;

constructing, using the hardware processor, a matrix of the confidential data values having the first attribute type as a first axis and the second attribute type as a second axis, with each cell in the matrix corresponding to corresponding different combinations of attributes of the first attribute type and the second attribute type;

computing, using the hardware processor, a set of candidate low rank approximations of the matrix using an objective function evaluated using a set of candidate data transformation functions, the objective function having one or more parameters and an error function, wherein computing a set of candidate low rank approximations includes, for each candidate data transformation function;

applying the candidate data transformation function to the matrix;

obtaining a training matrix by hiding a preset fraction of entries of the transformed matrix;

for each of one or more candidate parameter values for one of the one or more parameters;

computing the objective function using the candidate parameter value; and

calculating the error function using the candidate parameter value;

optimizing the one or more parameters that minimizes the error function of the objective function to select one of the candidate low rank approximations of the matrix; and

inferring one or more cells that are missing data, of the selected one of the candidate low rank approximations of the matrix.

8. The method of claim 7, wherein the constructing the matrix includes using a machine learning model to generate median confidential data values for one or more cells along with corresponding confidence scores.

9. The method of claim 7, wherein the inferring the one or more cells that are missing data includes:

for each cell that is missing data, of the selected one of the candidate low rank approximations of the matrix;

determining if the cell that is missing data is present in the matrix of the confidential data values; and

in response to a determination that the cell that is missing data is present in the matrix of confidential data values, applying an inverse of the selected candidate low rank approximations to the cell that is missing data.

10. The method of claim 7, wherein the inferring the one or more cells that are missing data includes:

for each cell that is missing data, of the selected one of the candidate low rank approximations of the matrix;

determining if the cell that is missing data is present in the matrix of the confidential data values; and

in response to a determination that the cell that is missing data is not present in the matrix of confidential data values, applying an the selected candidate low rank approximation to a corresponding cell in an optimized matrix formed by applying the selected candidate low rank approximation to the matrix of confidential values.

11. The method of claim 7, wherein the set of transformation functions includes identity, log, and square root transformations.

12. The method of claim 7, wherein the set of candidate data transformation functions includes monotonic transformations.

13. A non-transitory machine-readable storage medium comprising instructions, which when implemented by one or more machines, cause the one or more machines to perform operations comprising:

obtaining, using a hardware processor, an anonymized set of confidential data values for a plurality of combinations of cohorts having a first attribute type and a second attribute type, the confidential data values received via a computerized user interface implemented as a screen of a graphical user interface, the confidential data values entered into a field of the screen of the graphical user interface;

constructing, using the hardware processor, a matrix of the confidential data values having the first attribute type as a first axis and the second attribute type as a second axis, with each cell in the matrix corresponding to corresponding different combinations of attributes of the first attribute type and the second attribute type;

computing, using the hardware processor, a set of candidate low rank approximations of the matrix using an objective function evaluated using a set of candidate data transformation functions, the objective function having one or more parameters and an error function, wherein computing a set of candidate low rank approximations includes, for each candidate data transformation function;

applying the candidate data transformation function to the matrix;

obtaining a training matrix by hiding a preset fraction of entries of the transformed matrix;

for each of one or more candidate parameter values for one of the one or more parameters;

computing the objective function using the candidate parameter value; and

calculating the error function using the candidate parameter value;

optimizing the one or more parameters that minimizes the error function of the objective function to select one of the candidate low rank approximations of the matrix; and

inferring one or more cells that are missing data, of the selected one of the candidate low rank approximations of the matrix.

14. The non-transitory machine-readable storage medium of claim 13, wherein the constructing the matrix includes using a machine learning model to generate median confidential data values for one or more cells along with corresponding confidence scores.

15. The non-transitory machine-readable storage medium of claim 13, wherein the inferring the one or more cells that are missing data includes:

for each cell that is missing data, of the selected one of the candidate low rank approximations of the matrix;

determining if the cell that is missing data is present in the matrix of the confidential data values; and

in response to a determination that the cell that is missing data is present in the matrix of confidential data values, applying an inverse of the selected candidate low rank approximations to the cell that is missing data.

16. The non-transitory machine-readable storage medium of claim 13, wherein the inferring the one or more cells that are missing data includes:

for each cell that is missing data, of the selected one of the candidate low rank approximations of the matrix;

determining if the cell that is missing data is present in the matrix of the confidential data values; and

in response to a determination that the cell that is missing data is not present in the matrix of confidential data values, applying an the selected candidate low rank approximation to a corresponding cell in an optimized matrix formed by applying the selected candidate low rank approximation to the matrix of confidential values.

17. The non-transitory machine-readable storage medium of claim 13, wherein the set of candidate data transformation functions includes identity, log, and square root transformations.