Learning new words

• US 10,701,042 B2
• Filed: 10/12/2018
• Issued: 06/30/2020
• Est. Priority Date: 06/12/2016
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Thakurta, Abhradeep Guha, Vyrros, Andrew H., Vaishampayan, Umesh S., Kapoor, Gaurav, Freudiger, Julien, Sridhar, Vivek Rangarajan, Davidson, Doug
• Primary Examiner(s): Roberts, Shaun
• Application Number:
  US16/159,473
• Publication Number:
  US 20190097978A1
• Time in Patent Office: 627 Days
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/374 Thesaurus
• 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 40/205 Parsing
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: G06F 9/30029 Logical and Boolean instructions, e.g. XOR, NOT
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload

Abstract

Systems and methods are disclosed for a server learning new words generated by user client devices in a crowdsourced manner while maintaining local differential privacy of client devices. A client device can determine that a word typed on the client device is a new word that is not contained in a dictionary or asset catalog on the client device. New words can be grouped in classifications such as entertainment, health, finance, etc. A differential privacy system on the client device can comprise a privacy budget for each classification of new words. If there is privacy budget available for the classification, then one or more new terms in a classification can be sent to new term learning server, and the privacy budget for the classification reduced. The privacy budget can be periodically replenished.

Claims

1. A computer implemented method executed on a term learning server, the method comprising:

receiving, by a term learning server, a batch of differentially private sketches of n-grams, each n-gram a sequence of characters forming a subset of one term in a plurality of terms unknown to the term learning server, the batch of differentially private sketches received from one or more client devices;

determining a randomization value based at least on the batch of differentially private sketches;

determining a randomization tolerance based on a set of differentially private sketch data stored on the term learning server; and

in response to determining that the randomization value differs from the randomization tolerance by greater than a threshold value, generating a privacy randomization warning to the term learning server, wherein the privacy randomization warning indicates to the term learning server to perform one or more operations to maintain privacy of the differentially private sketch data stored on the term learning server.

2. The computer implemented method as in claim 1, additionally comprising, in response to the privacy randomization warning, modifying a randomization algorithm on the term learning server.

3. The computer implemented method as in claim 1, additionally comprising, in response to the privacy randomization warning, purging at least a portion of the differentially private sketch data received from the one or more client devices.

4. The computer implemented method as in claim 3, additionally comprising periodically purging at least a portion of the differentially private sketch data received from the one or more client devices.

5. The computer implemented method as in claim 1, additionally comprising generating a privacy randomization warning to a user interface of the term learning server.

6. The computer implemented method as in claim 1, wherein determining a randomization value based at least on the batch of differentially private sketches includes:

for each sketch in the batch of differentially private sketches, determining a row XOR value, the row XOR value equal to an exclusive OR of each bit in a row of the sketch, and determining a sketch XOR value based on a sum of each row XOR value of a sketch; and

determine the randomization value based on an arithmetic mean of sketch XOR values for the batch of differentially private sketches.

7. A non-transitory machine readable medium storing instructions to cause one or more processors to perform operations comprising:

receiving, by a term learning server, a batch of differentially private sketches of n-grams, each n-gram a sequence of characters forming a subset of one term in a plurality of terms unknown to the term learning server, the batch of differentially private sketches received from one or more client devices;

determining a randomization value based at least on the batch of differentially private sketches;

determining a randomization tolerance based on a set of differentially private sketch data stored on the term learning server; and

in response to determining that the randomization value differs from the randomization tolerance by greater than a threshold value, generating a privacy randomization warning to the term learning server, wherein the privacy randomization warning indicates to the term learning server to perform one or more operations to maintain privacy of the differentially private sketch data stored on the term learning server.

8. The non-transitory machine readable medium as in claim 7, the operations additionally comprising, in response to the privacy randomization warning, modifying a randomization algorithm on the term learning server.

9. The non-transitory machine readable medium as in claim 7, the operations additionally comprising, in response to the privacy randomization warning, purging at least a portion of the differentially private sketch data received from the one or more client devices.

10. The non-transitory machine readable medium as in claim 9, the operations additionally comprising periodically purging at least a portion of the differentially private sketch data received from the one or more client devices.

11. The non-transitory machine readable medium as in claim 7, the operations additionally comprising generating a privacy randomization warning to a user interface of the term learning server.

12. The non-transitory machine readable medium as in claim 7, wherein determining a randomization value based at least on the batch of differentially private sketches includes:

for each sketch in the batch of differentially private sketches, determining a row XOR value, the row XOR value equal to an exclusive OR of each bit in a row of the sketch, and determining a sketch XOR value based on a sum of each row XOR value of a sketch; and

determine the randomization value based on an arithmetic mean of sketch XOR values for the batch of differentially private sketches.

13. A data processing system comprising:

a memory to store instructions;

one or more processors to execute instructions stored in memory, wherein the instructions cause the one or more processors to perform operations comprising;

receiving, by a term learning server, a batch of differentially private sketches of n-grams, each n-gram a sequence of characters forming a subset of one term in a plurality of terms unknown to the term learning server, the batch of differentially private sketches received from one or more client devices;

determining a randomization value based at least on the batch of differentially private sketches;

determining a randomization tolerance based on a set of differentially private sketch data stored on the term learning server; and

in response to determining that the randomization value differs from the randomization tolerance by greater than a threshold value, generating a privacy randomization warning to the term learning server, wherein the privacy randomization warning indicates to the term learning server to perform one or more operations to maintain privacy of the differentially private sketch data stored on the term learning server.

14. The data processing system as in claim 13, the operations additionally comprising, in response to the privacy randomization warning, modifying a randomization algorithm on the term learning server.

15. The data processing system as in claim 13, the operations additionally comprising, in response to the privacy randomization warning, purging at least a portion of the differentially private sketch data received from the one or more client devices.

16. The data processing system as in claim 15, the operations additionally comprising periodically purging at least a portion of the differentially private sketch data received from the one or more client devices.

17. The data processing system as in claim 13, the operations additionally comprising generating a privacy randomization warning to a user interface of the term learning server.

18. The data processing system as in claim 13, wherein determining a randomization value based at least on the batch of differentially private sketches includes:

for each sketch in the batch of differentially private sketches, determining a row XOR value, the row XOR value equal to an exclusive OR of each bit in a row of the sketch, and determining a sketch XOR value based on a sum of each row XOR value of a sketch; and

determine the randomization value based on an arithmetic mean of sketch XOR values for the batch of differentially private sketches.