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

• US 8,180,725 B1
• Filed: 07/21/2008
• Issued: 05/15/2012
• Est. Priority Date: 08/01/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jahr, Michael, Lerner, Uri N.
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US12/176,621
• Time in Patent Office: 1,394 Days
• Field of Search: 706/55
• US Class Current: 706/55
• 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

Some embodiments of the present invention provide a system that selects links while updating a probabilistic generative model for textual documents. During operation, the system receives a current model, which contains terminal nodes representing words and cluster nodes representing clusters of conceptually related words, wherein nodes in the current model are coupled together by weighted links, wherein if a node fires, a link from the node to another node is activated and causes the other node to fire with a probability proportionate to the weight of the link. Next, the system applies a set of training documents containing words to the current model to produce a new model. While doing so, the system: determines expected counts for activations of links and prospective links; determines link-ratings for the links and the prospective links based on the expected counts, and selects links to be included in the new model based on the determined link-ratings. Finally, the system makes the new model the current model.

Claims

1. A method for selecting links while updating a probabilistic generative model for textual documents, comprising:

receiving a current model, which contains terminal nodes representing words and cluster nodes representing clusters of conceptually related words, wherein nodes in the current model are coupled together by weighted links, wherein if a node fires, a link from the node to another node is activated and causes the other node to fire with a probability proportionate to the weight of the link;

applying a set of training documents containing words to the current model to produce a new model, and while doing so,

determining expected counts for activations of links and prospective links,

determining link-ratings for the links and the prospective links based on the expected counts, and

selecting links to be included in the new model based on the determined link-ratings; and

making the new model the current model.

2. The method of claim 1, wherein selecting the links to be included in the new model involves ensuring source diversity by selecting links which are associated with at least a minimum number of sources.

3. The method of claim 1, wherein the minimum number of sources is three sources.

4. The method of claim 1, wherein determining the link-rating for a given link between a cluster and a terminal involves:

determining an expected count for the given link which indicates an expected number of times the given link was activated;

calculating a significance for the given link by dividing a probability of the child given the parent by a probability of the child, significance=p(child|parent)/p(child); and

calculating the link-rating for the given link as a function of the significance and the expected count for the given link.

5. The method of claim 4, wherein the function for the link-rating is significance²×

expected count.

6. The method of claim 4, wherein determining the expected count for the given link involves reducing the value of the expected count if the given link is a prospective link.

7. The method of claim 1, wherein selecting links to be included in the new model based on the determined link-ratings involves:

ranking the links and prospective links based on the determined link ratings and

selecting the N top-ranked links and prospective links to be included in the new model.

8. The method of claim 1, wherein applying the set of training documents to the current model involves:

applying the set of training documents to the links defined in the current model to produce expected counts for corresponding links and prospective new links in the new model; and

using these expected counts to produce weights for links in the new model.

9. The method of claim 1, wherein producing the new model additionally involves selectively introducing new cluster nodes into the current model.

10. The method of claim 1, wherein producing the new model additionally involves selectively deleting nodes from the new model.

11. The method of claim 1, wherein the method further comprises selectively merging nodes in the current model.

12. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for selecting links while updating a probabilistic generative model for textual documents, the method comprising:

receiving a current model, which contains terminal nodes representing words and cluster nodes representing clusters of conceptually related words, wherein nodes in the current model are coupled together by weighted links, wherein if a node fires, a link from the node to another node is activated and causes the other node to fire with a probability proportionate to the weight of the link;

applying a set of training documents containing words to the current model to produce a new model, and while doing so,

determining expected counts for activations of links and prospective links,

determining link-ratings for the links and the prospective links based on the expected counts, and

selecting links to be included in the new model based on the determined link-ratings; and

making the new model the current model.

13. The computer-readable storage medium of claim 12, wherein selecting the links to be included in the new model involves ensuring source diversity by selecting links which are associated with at least a minimum number of sources.

14. The computer-readable storage medium of claim 12, wherein the minimum number of sources is three sources.

15. The computer-readable storage medium of claim 12, wherein determining the link-rating for a given link between a parent and a child involves:

determining an expected count for the given link which indicates an expected number of times the given link was activated;

calculating a significance for the given link by dividing a probability of the child given the parent by a probability of the child, significance=p(child|parent)/p(child); and

calculating the link-rating for the given link as a function of the significance and the expected count for the given link.

16. The computer-readable storage medium of claim 15, wherein the function for the link-rating is significance²×

expected count.

17. The computer-readable storage medium of claim 15, wherein determining the expected count for the given link involves reducing the value of the expected count if the given link is a prospective link.

18. The computer-readable storage medium of claim 12, wherein selecting links to be included in the new model based on the determined link-ratings involves:

ranking the links and prospective links based on the determined link ratings and

selecting the N top-ranked links and prospective links to be included in the new model.

19. The computer-readable storage medium of claim 12, wherein applying the set of training documents to the current model involves:

applying the set of training documents to the links defined in the current model to produce expected counts for corresponding links and prospective new links in the new model; and

using the expected counts to produce weights for links in the new model.

20. The computer-readable storage medium of claim 12, wherein producing the new model additionally involves selectively introducing new cluster nodes into the current model.

21. The computer-readable storage medium of claim 12, wherein producing the new model additionally involves selectively deleting nodes from the new model.

22. The computer-readable storage medium of claim 12, wherein the method further comprises selectively merging nodes in the current model.

23. An apparatus that selects links while updating a probabilistic generative model for textual documents, comprising:

a data store configured to store a current model, which contains terminal nodes representing words and cluster nodes representing clusters of conceptually related words, wherein nodes in the current model are coupled together by weighted links, wherein if a node fires, a link from the node to another node is activated and causes the other node to fire with a probability proportionate to the weight of the link;

a training mechanism configured to apply a set of training documents containing words to the current model to produce a new model, wherein the training mechanism is configured to,

determine expected counts for activations of links and prospective links,

determine link-ratings for the links and the prospective links based on the expected counts, and

select links to be included in the new model based on the determined link-ratings; and

an updating mechanism configured to make the new model the current model.

24. The apparatus of claim 23, wherein the training mechanism is configured to ensure source diversity by selecting links which are associated with at least a minimum number of sources.

25. The apparatus of claim 24, wherein the minimum number of sources is three sources.

26. The apparatus of claim 24, wherein while determining the link-rating for a given link between a cluster and a terminal, the training mechanism is configured to:

determine an expected count for the given link which indicates an expected number of times the given link was activated;

calculate a significance for the given link by dividing a probability of the child given the parent by a probability of the parent, significance=p(child|parent)/p(child); and

calculate the link-rating for the given link as a function of the significance and the expected count for the given link.

27. The apparatus of claim 26, wherein the function for the link-rating is significance²×

expected count.

28. The apparatus of claim 26, wherein while determining the expected count for the given link, the training mechanism is configured to reduce the value of the expected count if the given link is a prospective link.

29. The apparatus of claim 23, wherein while selecting links to be included in the new model, the training mechanism is configured to:

rank the links and prospective links based on the determined link ratings and

select the N top-ranked links and prospective links to be included in the new model.

30. The apparatus of claim 23, wherein while applying the set of training documents to the current model, the training mechanism is configured to:

apply the set of training documents to the links defined in the current model to produce expected counts for corresponding links and prospective new links in the new model; and

use the expected counts to produce weights for links in the new model.

31. The apparatus of claim 23, wherein while producing the new model, the training mechanism is configured to selectively introduce new cluster nodes into the current model.

32. The apparatus of claim 23, wherein while producing the new model, the training mechanism is configured to selectively delete nodes from the new model.

33. The apparatus of claim 23, wherein the apparatus further comprises a merging mechanism configured to selectively merge nodes in the current model.