Selectively deleting clusters of conceptually related words from a generative model for text

• US 7,877,371 B1
• Filed: 02/07/2007
• Issued: 01/25/2011
• Est. Priority Date: 02/07/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jahr, Michael, Lerner, Uri, Kasera, Vishal
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US11/703,582
• Time in Patent Office: 1,448 Days
• Field of Search: 707/708, 707/723, 707/724, 707/725, 707/726, 707/727, 707/728, 707/729, 707/730, 707/731, 707/737, 707/748, 707/749, 707/750, 707/751, 707/752, 707/753, 707/754
• US Class Current: 707/708
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

One embodiment of the present invention provides a system that selectively deletes clusters of conceptually-related words from a probabilistic generative model for textual documents. During operation, the system receives a current model, which contains terminal nodes representing random variables for words and contains one or more cluster nodes representing clusters of conceptually related words. Nodes in the current model are coupled together by weighted links, so that if an incoming link from a node that has fired causes a cluster node to fire with a probability proportionate to a weight of the incoming link, an outgoing link from the cluster node to another node causes the other node to fire with a probability proportionate to the weight of the outgoing link. Next, the system processes a given cluster node in the current model for possible deletion. This involves determining a number of outgoing links from the given cluster node to terminal nodes or cluster nodes in the current model. If the determined number of outgoing links is less than a minimum value, or if the frequency with which the given cluster node fires is less than a minimum frequency, the system deletes the given cluster node from the current model.

Claims

1. A method for selectively deleting clusters of conceptually-related words from a probabilistic generative model for textual documents, comprising:

receiving a current model, which contains terminal nodes representing random variables for words and contains one or more cluster nodes representing clusters of conceptually related words;

wherein nodes in the current model are coupled together by weighted links, so that for a cluster node with an incoming link from a node that has fired which causes the cluster node in the current model to fire with a probability proportionate to a weight of the incoming link, an outgoing link from the cluster node to another node causes the other node to fire with a probability proportionate to the weight of the outgoing link; and

processing, at a computer system, a given cluster node in the current model for possible deletion by,

determining a number of outgoing links from the given cluster node to terminal nodes and/or cluster nodes in the current model;

determining that the determined number of outgoing links is less than a minimum value; and

deleting the given cluster node from the current model.

2. The method of claim 1, wherein the method further comprises:

determining a frequency with which the given cluster node is activated;

determining that the determined frequency is less than a minimum frequency; and

deleting the given cluster node from the current model.

3. The method of claim 1, wherein processing the given cluster node for possible deletion involves processing each node in the current model for possible deletion.

4. The method of claim 1, wherein deleting the given cluster node from the current model involves:

deleting outgoing links from the given cluster node;

deleting incoming links into the given cluster node; and

deleting the given cluster node.

5. The method of claim 1, wherein the method further comprises performing training operations, which involves iteratively:

receiving a set of training documents, wherein each training document contains a set of words;

computing expected counts over the set of training documents;

applying the expected counts to the current model to produce a new model, including the frequency with which cluster nodes are activated; and

making the new model the current model.

6. The method of claim 5, wherein during an initial training iteration, the method further comprises generating an initial current model from a set of words by:

generating a universal node that is always active;

generating terminal nodes representing words in the set of words;

generating cluster nodes by selecting training instances; and

directly linking the universal node to the terminal nodes.

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

8. The method of claim 5, wherein producing the new model additionally involves selectively introducing new links from cluster nodes to terminal nodes and from cluster nodes to other cluster nodes.

9. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for selectively deleting clusters of conceptually-related words from a probabilistic generative model for textual documents, the method comprising:

receiving a current model, which contains terminal nodes representing random variables for words and contains one or more cluster nodes representing clusters of conceptually related words;

wherein nodes in the current model are coupled together by weighted links, so that for a cluster node with an incoming link from a node that has fired which causes the cluster node in the current model to fire with a probability proportionate to a weight of the incoming link, an outgoing link from the cluster node to another node causes the other node to fire with a probability proportionate to the weight of the outgoing link; and

processing a given cluster node in the current model for possible deletion by,

determining a number of outgoing links from the given cluster node to terminal nodes and/or cluster nodes in the current model;

determining that the determined number of outgoing links is less than a minimum value; and

deleting the given cluster node from the current model.

10. The computer-readable storage medium of claim 9, wherein the method further comprises:

determining a frequency with which the given cluster node is activated;

determining that the determined frequency is less than a minimum frequency; and

deleting the given cluster node from the current model.

11. The computer-readable storage medium of claim 9, wherein processing the given cluster node for possible deletion involves processing each cluster node in the current model for possible deletion.

12. The computer-readable storage medium of claim 9, wherein deleting the given cluster node from the current model involves:

deleting outgoing links from the given cluster node;

deleting incoming links into the given cluster node; and

deleting the given cluster node.

13. The computer-readable storage medium of claim 9, wherein the method further comprises performing training operations, which involves iteratively:

receiving a set of training documents, wherein each training document contains a set of words;

computing expected counts over the set of training documents;

applying the expected counts to the current model to produce a new model, including the frequency with which cluster nodes are activated; and

making the new model the current model.

14. The computer-readable storage medium of claim 13, wherein during an initial training iteration, the method further comprises generating an initial current model from a set of words by:

generating a universal node that is always active;

generating terminal nodes representing words in the set of words;

generating cluster nodes by selecting training instances; and

directly linking the universal node to the terminal nodes.

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

16. The computer-readable storage medium of claim 13, wherein producing the new model additionally involves selectively introducing new links from cluster nodes to terminal nodes and from cluster nodes to other cluster nodes.

17. An apparatus that selectively deletes clusters of conceptually-related words from a probabilistic generative model for textual documents, comprising:

a processor;

a memory;

a receiving mechanism configured to receive a current model, which contains terminal nodes representing random variables for words and contains one or more cluster nodes representing clusters of conceptually related words;

wherein nodes in the current model are coupled together by weighted links, so that for a cluster node with an incoming link from a node that has fired which causes the cluster node in the current model to fire with a probability proportionate to a weight of the incoming link, an outgoing link from the cluster node to another node causes the other node to fire with a probability proportionate to the weight of the outgoing link; and

a deletion mechanism configured to use the processor to selectively delete cluster nodes from the current model, wherein for a given cluster node the deletion mechanism is configured to,

determine a number of outgoing links from the given cluster node to terminal nodes and/or cluster nodes in the current model;

determine that the determined number of outgoing links is less than a minimum value; and

delete the given cluster node from the current model.

18. The apparatus of claim 17, wherein the deletion mechanism is additionally configured to:

determine a frequency with which the given cluster node is activated;

determine that the determined frequency is less than a minimum frequency; and

delete the given cluster node from the current model.

19. The apparatus of claim 17, wherein while deleting the given cluster node from the current model, the deletion mechanism is configured to:

delete outgoing links from the given cluster node;

delete incoming links into the given cluster node; and

to

delete the given cluster node.

20. The apparatus of claim 17, further comprising a training mechanism which is configured to:

receive a set of training documents, wherein each training document contains a set of words;

compute expected counts over the set of training documents;

apply the expected counts to the current model to produce a new model, including the frequency with which cluster nodes are activated; and

to

make the new model the current model.