IP Library Granted Patent US 10,262,154
Granted Patent B1
US 10,262,154 · App. 15/618,554 · Granted Apr 16, 2019

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

Inventors: Krishnaram Kenthapadi (Sunnyvale, CA); Stuart MacDonald Ambler (Longmont, CO)
Assignee: Microsoft Technology Licensing, LLC
G06F21/6254G06F17/16G06F21/6227G06N99/005H04L9/14G06Q50/01
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,262,154
App. No.
15/618,554
Granted
Apr 16, 2019
Kind
B1
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 (67)

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.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 3, 2017
From: LINKEDIN CORPORATION
To: MICROSOFT TECHNOLOGY LICENSING, LLC
Reel/Frame 044779/0602 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 9, 2017
From: KENTHAPADI, KRISHNARAM; AMBLER, STUART MACDONALD
To: LINKEDIN CORPORATION
Reel/Frame 042661/0087 →