Method and apparatus for selecting links to include in a probabilistic generative model for text

• US 9,418,335 B1
• Filed: 05/04/2012
• Issued: 08/16/2016
• Est. Priority Date: 08/01/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lerner, Uri N., Jahr, Michael
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US13/464,399
• Time in Patent Office: 1,565 Days
• Field of Search: 706/55
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A method may include receiving, at one or more processors, a current model. The current model may include a group of nodes representing words, at least one cluster of nodes representing related words, and a group of links. Each link may connect two nodes of the group of nodes. Each link may include a corresponding weight. The method may further include applying, by one or more processors, a set of training documents to the model to produce new weights for the group of links to create a new model; and making, by one or more processors, the new model the current model.

Claims

1. A computer-implemented method comprising:

applying training documents to links in a current generative model that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, to determine a respective expected count for each of the links;

selecting, from the links that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, a first subset of one or more links that are each associated with more than a predetermined number of sources of the training documents;

for each selected link of the first subset, determining (i) a significance of the link, and (ii) a link rating for the link based on the expected count for the link and the significance;

ranking the selected links of the first subset based on the link ratings;

selecting a second subset of the ranked links; and

generating a new generative model using only the selected links of the second subset, without using any of the links in the current generative model that were not selected for the second subset.

2. The method of claim 1, wherein applying a training document to links in a current generative model that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, to determine a respective expected count for each of the links comprises:

activating each of one or more respective terminal nodes;

determining a model structure based on the one or more activated respective terminal nodes; and

determining, based on the one or more activated respective terminal nodes, expected counts for the links.

3. The method of claim 2, wherein activating each respective terminal node comprises modifying a probability that a concept causes the respective terminal node to fire, wherein the concept produces the one or more words.

4. The method of claim 1, wherein applying training documents to links in a current generative model that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, to determine a respective expected count for each of the links further comprises:

applying training documents to prospective links in a current generative model that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, to determine a respective expected count for each of the prospective links.

5. The method of claim 1, wherein determining a link rating for the link based on the expected count for the link and the significance comprises:

determining a significance of the link based on a child and parent associated with the link; and

determining the link rating by multiplying the significance of the link by the expected count for the link.

6. The method of claim 5, wherein determining a significance of the link based on a child and parent associated with the link comprises:

determining a first probability that a child associated with the link arises in a context of a parent associated with the link;

determining a second probability that the child associated with the link arises independently of the parent associated with the link; and

determining the link rating by dividing the first probability by the second probability.

7. The method of claim 1, wherein selecting a second subset of the ranked links comprises:

selecting, from the ranked links, a first count of links for each iteration in a specified number of training iterations; and

selecting, from the ranked links, a second count of links for a last iteration in the specified number of training iterations.

8. A system comprising:

a non-transitory computer readable medium having instructions stored thereon; and

data processing apparatus programmed to execute the instructions to perform operations comprising;

applying training documents to links in a current generative model that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, to determine a respective expected count for each of the links;

selecting, from the links that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, a first subset of one or more links that are each associated with more than a predetermined number of sources of the training documents;

for each selected link of the first subset, determining (i) a significance of the link, and (ii) a link rating for the link based on the expected count for the link and the significance;

ranking the selected links of the first subset based on the link ratings;

selecting a second subset of the ranked links; and

generating a new generative model using only the selected links of the second subset, without using any of the links in the current generative model that were not selected for the second subset.

9. The system of claim 8, wherein applying a training document to links in a current generative model that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, to determine a respective expected count for each of the links comprises:

activating each of one or more respective terminal nodes;

determining a model structure based on the one or more activated respective terminal nodes; and

determining, based on the one or more activated respective terminal nodes, expected counts for the links.

10. The system of claim 9, wherein activating each respective terminal node comprises modifying a probability that a concept causes the respective terminal node to fire, wherein the concept produces the one or more words.

11. The system of claim 8, wherein applying training documents to links in a current generative model that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, to determine a respective expected count for each of the links further comprises:

applying training documents to prospective links in a current generative model that each connect a respective terminal node that represents a corresponding word to a respective cluster node that represents a corresponding cluster of conceptually related words, to determine a respective expected count for each of the prospective links.

12. The system of claim 8, wherein determining a link rating for the link based on the expected count for the link and the significance comprises:

determining a significance of the link based on a child and parent associated with the link; and

determining the link rating by multiplying the significance of the link by the expected count for the link.

13. The system of claim 12, wherein determining a significance of the link based on a child and parent associated with the link comprises:

determining a first probability that a child associated with the link arises in a context of a parent associated with the link;

determining a second probability that the child associated with the link arises independently of the parent associated with the link; and

determining the link rating by dividing the first probability by the second count probability.

14. The system of claim 8, wherein selecting a second subset of the ranked links comprises:

selecting, from the ranked links, a first count of links for each iteration in a specified number of training iterations; and

selecting, from the ranked links, a second count of links for a last iteration in the specified number of training iterations.