Learning new words

• US 10,133,725 B2
• Filed: 04/03/2017
• Issued: 11/20/2018
• 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:
  US15/477,921
• Publication Number:
  US 20180039619A1
• Time in Patent Office: 596 Days
• Field of Search: 704 10
• 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, 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;

for each received differentially private n-gram sketch, determining a matching differentially private n-gram sketch to the received sketch, wherein the matching differentially private n-gram sketch, W, has k rows and m columns, wherein each row ∈

[k] corresponds to a hash function h in the set of k hash functions, H={h₁, . . . , h_k};

adding the received differentially private n-gram sketch data to the matching differentially private sketch n-gram sketch;

determining a frequency of each matching differentially private n-gram sketch among the batch;

selecting the matching differentially private n-grams having a frequency greater than a threshold value;

generating a plurality of combinations of differentially private n-grams from the selected matching differentially private sketches of n-grams having a frequency greater than a threshold value;

determining one or more new terms using the plurality of combinations of differentially private n-grams; and

adding at least one of the one or more new terms to an asset catalog to form an updated asset catalog.

2. The method of claim 1, wherein the received differentially private n-gram sketch data comprises a vector v_Hadamard, a selected function h∈

H={h₁, . . . h_k} was used to generate v_Hadamard, and a selected index j used to generate V_Hadmard, and adding the received differentially private n-gram sketch data to the matching differentially private n-gram sketch comprises;

adding vector v_Hadamard to the selected matching differentially private n-gram sketch W[h,j].

3. The method of claim 1, the received differentially private n-gram sketch data comprises a vector v_priv, and a selected function h∈

H={h₁, . . . h_k} was used to generate v_priv, and adding the received differentially private n-gram sketch data to the matching differentially private n-gram sketch comprises;

adding vector v_priv to the selected matching differentially private n-gram sketch W at row W_h.

4. The method of claim 1, further comprising:

de-identifying the received batch of differentially private sketches of n-grams.

5. The method of claim 1, further comprising:

transmitting the updated asset catalog to at least one client device.

6. A system comprising:

a processing system coupled to a memory programmed with executable instructions that, when executed by the processing system 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;

for each received differentially private n-gram sketch, determining a matching differentially private n-gram sketch to the received sketch, wherein the matching differentially private n-gram sketch, W, has k rows and m columns, wherein each row ∈

[k] corresponds to a hash function h in the set of k hash functions, H={h₁, . . . , h_k};

adding the received differentially private n-gram sketch data to the matching differentially private sketch n-gram sketch;

determining a frequency of each matching differentially private n-gram sketch among the batch;

selecting the matching differentially private n-grams having a frequency greater than a threshold value;

generating a plurality of combinations of differentially private n-grams from the selected matching differentially private sketches of n-grams having a frequency greater than a threshold value;

determining one or more new terms using the plurality of combinations of differentially private n-grams; and

adding at least one of the one or more new terms to an asset catalog to form an updated asset catalog.

7. The system of claim 6, wherein the received differentially private n-gram sketch data comprises a vector v_Hadamard, a selected function h∈

H={h₁, . . . h_k} was used to generate v_Hadamard, and a selected index j used to generate V_Hadmard, and adding the received differentially private n-gram sketch data to the matching differentially private n-gram sketch comprises;

adding vector v_Hadamard to the selected matching differentially private n-gram sketch W[h,j].

8. The system of claim 6, the received differentially private n-gram sketch data comprises a vector v_priv, and a selected function h∈

H={h₁, . . . h_k} was used to generate v_priv, and adding the received differentially private n-gram sketch data to the matching differentially adding vector v_priv to the selected matching differentially private n-gram sketch W at row W_h.

9. The system of claim 6, the operations further comprising:

de-identifying the received batch of differentially private sketches of n-gram.

10. The system of claim 6, the operations further comprising:

transmitting the updated asset catalog to at least one client device.

11. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors, 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;

for each received differentially private n-gram sketch, determining a matching differentially private n-gram sketch to the received sketch, wherein the matching differentially private n-gram sketch, W, has k rows and m columns, wherein each row ∈

[k] corresponds to a hash function h in a set of k hash functions, H={h₁, . . . , h_k};

adding the received differentially private n-gram sketch data to the matching differentially private sketch n-gram sketch;

determining a frequency of each matching differentially private n-gram sketch among the batch;

selecting the matching differentially private n-grams having a frequency greater than a threshold value;

generating a plurality of combinations of differentially private n-grams from the selected matching differentially private sketches of n-grams having a frequency greater than a threshold value;

determining one or more new terms using the plurality of combinations of differentially private n-grams; and

adding at least one of the one or more new terms to an asset catalog to form an updated asset catalog.

12. The non-transitory machine-readable medium of claim 11, wherein the received differentially private n-gram sketch data comprises a vector v_Hadamard, a selected function h∈

H={h₁, . . . h_k} was used to generate v_Hadamard, and a selected index j used to generate V_Hadmard, and adding the received differentially private n-gram sketch data to the matching differentially private n-gram sketch comprises;

adding vector v_Hadamard to the selected matching differentially private n-gram sketch W[h,j].

13. The non-transitory machine-readable medium of claim 11, the received differentially private n-gram sketch data comprises a vector v_priv, and a selected function h∈

H={h₁, . . . h_k} was used to generate v_priv, and adding the received differentially private n-gram sketch data to the matching differentially private n-gram sketch comprises;

adding vector v_priv to the selected matching differentially private n-gram sketch W at row W_h.

14. The non-transitory machine-readable medium of claim 11, the operations further comprising:

de-identifying the received batch of differentially private sketches of n-grams.

15. The non-transitory machine-readable medium of claim 11, the operations further comprising:

transmitting the updated asset catalog to at least one client device.