Custom language models

• US 8,826,226 B2
• Filed: 11/05/2008
• Issued: 09/02/2014
• Est. Priority Date: 11/05/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wu, Jun, Ou, Henry, Tang, Xiliu, Wang, Yong-Gang, Liu, Yongyan
• Primary Examiner(s): Dao, Thuy
• Assistant Examiner(s): Luu, Cuong V
• Application Number:
  US13/127,417
• Publication Number:
  US 20110296374A1
• Time in Patent Office: 2,127 Days
• US Class Current: 717/104
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

Systems, methods, and apparatuses including computer program products for generating a custom language model. In one implementation, a method is provided. The method includes receiving a collection of documents; clustering the documents into one or more clusters; generating a cluster vector for each cluster of the one or more clusters; generating a target vector associated with a target profile; comparing the target vector with each of the cluster vectors; selecting one or more of the one or more clusters based on the comparison; and generating a language model using documents from the one or more selected clusters.

Claims

1. A computer-implemented method comprising:

receiving, at a computing device having one or more processors, a collection of documents;

clustering, at the computing device, the documents into one or more clusters;

generating, at the computing device, a cluster vector for each cluster of the one or more clusters;

generating, at the computing device, a target vector associated with a target profile, the target profile being associated with an identified user;

storing, at the computing device, the target profile;

comparing, at the computing device, the target vector with each of the cluster vectors;

selecting, at the computing device, one or more of the one or more clusters based on the comparison of the target vector with each of the cluster vectors; and

generating, at the computing device, a custom language model for the identified user using documents from the one or more selected clusters.

2. The method of claim 1, where generating the custom language model includes:

identifying, at the computing device, a collection of n-grams from the documents from the one or more selected clusters, each n-gram having a corresponding relative frequency of occurring in the documents from the one or more selected clusters.

3. The method of claim 1, where each cluster is associated with a topic or domain.

4. The method of claim 1, where each cluster vector represents a centroid for a corresponding cluster.

5. The method of claim 4, where clustering the documents includes:

randomly assigning, at the computing device, each document to a cluster; and

iteratively calculating, at the computing device, a centroid for each cluster and reassigning each document to a cluster based on a nearest centroid, until convergence.

6. The method of claim 1, where the target vector comprises a term frequency vector.

7. The method of claim 1, where the target vector is generated from at least one of a custom dictionary for the identified user or input from the identified user.

8. The method of claim 1, where the comparing includes:

calculating, at the computing device, a cosine similarity between the target vector and each of the cluster vectors.

9. The method of claim 1, further comprising:

receiving, at the computing device, one or more additional documents; and

updating, at the computing device, the language model based on the one or more additional documents.

10. A computer-implemented method comprising:

receiving, at a computing device having one or more processors, a user input identifying a user;

identifying, at the computing device, a user profile corresponding to the user;

using, at the computing device, the identified user profile to generate a user specific language model, including;

receiving a collection of documents associated with the user,

clustering the documents into one or more clusters,

generating a cluster vector for each cluster of the one or more clusters,

generating a target vector associated with the identified user profile,

comparing the target vector with each of the cluster vectors,

selecting one or more of the one or more clusters based on the comparison between the target vector and each of the cluster vectors, and

generating the user specific language model for the user using documents from the one or more selected clusters; and

sending, by the computing device, the user specific language model to a first client associated with the user.

11. The method of claim 10, further comprising:

sending, by the computing device, the user specific language model to a second client.

12. The method of claim 10, where generating the user specific language model includes:

identifying, at the computing device, a collection of n-grams from the documents from the one or more selected clusters, each n-gram having a corresponding relative frequency of occurring in the documents from the one or more selected clusters.

13. A computer program product, encoded on a non-transitory program carrier, operable to cause data processing apparatus to perform operations comprising:

receiving a collection of documents;

clustering the documents into one or more clusters;

generating a cluster vector for each cluster of the one or more clusters;

generating a target vector associated with a target profile, the target profile being associated with an identified user;

comparing the target vector with each of the cluster vectors;

selecting one or more of the one or more clusters based on the comparison between the target vector and each of the cluster vectors; and

generating a custom language model for the identified user using documents from the one or more selected clusters.

14. A system, comprising:

a non-transitory machine-readable storage device including a program product; and

one or more computers operable to execute the program product and perform operations comprising;

receiving a collection of documents;

clustering the documents into one or more clusters;

generating a cluster vector for each cluster of the one or more clusters;

generating a target vector associated with a target profile, the target profile being associated with an identified user;

comparing the target vector with each of the cluster vectors;

selecting one or more of the one or more clusters based on the comparison between the target vector and each of the cluster vectors; and

generating a custom language model for the identified user using documents from the one or more selected clusters.