Method and apparatus for learning a probabilistic generative model for text

• US 8,024,372 B2
• Filed: 04/27/2007
• Issued: 09/20/2011
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Shazeer, Noam M., Harik, Georges
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US11/796,383
• Publication Number:
  US 20070208772A1
• Time in Patent Office: 1,607 Days
• Field of Search: 707/803, 707/688, 707/694, 707/723, 707/726, 707/765, 707/792, 707/802, 707/737
• US Class Current: 707/803
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30

Abstract

One embodiment of the present invention provides a system that learns a generative model for textual documents. During operation, the system receives a current model, which contains terminal nodes representing random variables for words and cluster nodes representing clusters of conceptually related words. Within the current model, nodes are coupled together by weighted links, so that if a cluster node in the probabilistic model fires, a weighted link from the cluster node to another node causes the other node to fire with a probability proportionate to the link weight. The system also receives a set of training documents, wherein each training document contains a set of words. Next, the system applies the set of training documents to the current model to produce a new model.

Claims

1. A method for constructing a model that generates text, the method comprising:

in a computer system, performing the operations of;

representing a concept as a cluster node;

representing a word as a terminal node;

assigning a weight to a link between two nodes; and

training the model based on a set of documents, comprising;

for each cluster node, computing a probabilistic cost of a corresponding concept existing in a document but not triggering any words.

2. The method of claim 1, wherein the weight assigned to a link from a first node and a second node indicates a probability of the second node triggering additional nodes when the first node triggers the second node.

3. The method of claim 1, wherein training the model based on the documents further comprises:

for a given link, producing a weight function for each document; and

optimizing a product of all the weight functions for the given link.

4. The method of claim 3, wherein for the given link and a given document, the corresponding weight function is based on a probability of the document'"'"'s terminal nodes firing when all other link weights remain constant.

5. The method of claim 1, further comprising iteratively training the model over progressively more documents.

6. The method of claim 1, further comprising:

generating a universal node that is always active;

generating terminal nodes which represent words in the documents; and

directly linking the universal node to the terminal nodes.

7. The method of claim 1, further comprising generating a new link between:

a cluster node assumed to be active in generating a given document, and

a terminal node that represents a given word in the given document;

wherein the given word is not associated with the concept represented by the cluster node.

8. The method of claim 1, further comprising generating a new link between:

a first cluster node and a second cluster node that is not associated with the first cluster node;

wherein both the first and second cluster nodes are assumed to be active in generating a given document.

9. The method of claim 1, further comprising:

generating a new cluster node based on a given document; and

generating new links between the new cluster and other cluster nodes assumed to be involved in generating the given document, or terminal nodes representing words in the given document, or both.

10. The method of claim 1, further comprising computing an activation for each cluster node in each document, wherein the activation indicates how many terminal nodes the cluster node can trigger.

11. The method of claim 1, further comprising numbering the cluster nodes based on a number of documents each cluster node is active in generating.

12. The method of claim 1, wherein the concept represents conceptually related words.

13. The method of claim 1, wherein the word comprises:

a single word;

or

a compound comprising two or more words.

14. The method of claim 1, wherein a concept triggering a word comprises a cluster node representing the concept triggering a terminal node representing the word.

15. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for constructing a model that generates text, the method comprising:

representing a concept as a cluster node;

representing a word as a terminal node;

assigning a weight to a link between two nodes; and

training the model based on a set of documents, comprising;

for each cluster node, computing a probabilistic cost of a corresponding concept existing in a document but not triggering any words.

16. The computer-readable storage medium of claim 15, wherein the weight assigned to a link from a first node and a second node indicates a probability of the second node triggering additional nodes when the first node triggers the second node.

17. The computer-readable storage medium of claim 15, wherein training the model based on the documents further comprises:

for a given link, producing a weight function for each document; and

optimizing a product of all the weight functions for the given link.

18. The computer-readable storage medium of claim 17, wherein for the given link and a given document, the corresponding weight function is based on a probability of the document'"'"'s terminal nodes firing when all other link weights remain constant.

19. The computer-readable storage medium of claim 15, wherein the method further comprises iteratively training the model over progressively more documents.

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

generating a universal node that is always active;

generating terminal nodes which represent words in the documents; and

directly linking the universal node to the terminal nodes.

21. The computer-readable storage medium of claim 15, wherein the method further comprises generating a new link between:

a cluster node assumed to be active in generating a given document, and

a terminal node that represents a given word in the given document;

wherein the given word is not associated with the concept represented by the cluster node.

22. The computer-readable storage medium of claim 15, wherein the method further comprises generating a new link between:

a first cluster node and a second cluster node that is not associated with the first cluster node;

wherein both the first and second cluster nodes are assumed to be active in generating a given document.

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

generating a new cluster node based on a given document; and

generating new links between the new cluster and other cluster nodes assumed to be involved in generating the given document, or terminal nodes representing words in the given document, or both.

24. The computer-readable storage medium of claim 15, wherein the method further comprises computing an activation for each cluster node in each document, wherein the activation indicates how many terminal nodes the cluster node can trigger.

25. The computer-readable storage medium of claim 15, wherein the method further comprises numbering the cluster nodes based on a number of documents each cluster node is active in generating.

26. The computer-readable storage medium of claim 15, wherein the concept represents conceptually related words.

27. The computer-readable storage medium of claim 15, wherein the word comprises:

a single word;

or

a compound comprising two or more words.

28. The computer-readable storage medium of claim 15, wherein a concept triggering a word comprises a cluster node representing the concept triggering a terminal node representing the word.

29. An apparatus for generating text, the apparatus comprising:

a modeling mechanism in a computer system configured to;

represent a concept as a cluster node;

represent a word as a terminal node;

assign a weight to a link from a first node to a second node,

wherein the weight indicates a probability of the second node triggering additional nodes when the first node triggers the second node;

a model-training mechanism in the computer system configured to train the model based on a set of documents, wherein the training comprises;

for each cluster node, computing a probabilistic cost of a corresponding concept existing in a document but not triggering any words.

30. The apparatus of claim 29, wherein the weight assigned to a link from a first node and a second node indicates a probability of the second node triggering additional nodes when the first node triggers the second node.

31. The apparatus of claim 29, wherein, when training the model based on the set of documents, the model-training mechanism is configured to:

for a given link, produce a weight function for each document; and

optimize a product of all the weight functions for the given link.

32. The apparatus of claim 31, wherein for the given link and a given document, the corresponding weight function is based on a probability of the document'"'"'s terminal nodes firing when all other link weights remain constant.

33. The apparatus of claim 29, wherein the model-training mechanism is configured to iteratively train the model over progressively more documents.

34. The apparatus of claim 29, wherein:

the modeling mechanism is configured to generate a universal node that is always active; and

the model-training mechanism is configured to;

generate terminal nodes which represent words in the documents; and

directly link the universal node to the terminal nodes.

35. The apparatus of claim 29, wherein the model-training mechanism is configured to generate a new link between:

a cluster node assumed to be active in generating a given document, and

a terminal node that represents a given word in the given document;

wherein the given word is not associated with the concept represented by the cluster node.

36. The apparatus of claim 29, wherein the model-training mechanism is configured to generate a new link between:

a first cluster node and a second cluster node that is not associated with the first cluster node;

wherein both the first and second cluster nodes are assumed to be active in generating a given document.

37. The apparatus of claim 29, wherein the model-training mechanism is configured to:

generate a new cluster node based on a given document; and

generate new links between the new cluster and other cluster nodes assumed to be involved in generating the given document, or terminal nodes representing words in the given document, or both.

38. The apparatus of claim 29, wherein the model-training mechanism is configured to compute an activation for each cluster node in each document, wherein the activation indicates how many terminal nodes the cluster node can trigger.

39. The apparatus of claim 29, wherein the model-training mechanism is configured to number the cluster nodes based on a number of documents each cluster node is active in generating.

40. The apparatus of claim 29, wherein the concept represents conceptually related words.

41. The apparatus of claim 29, wherein the word comprises:

a single word;

or

a compound comprising two or more words.

42. The apparatus of claim 29, wherein a concept triggering a word comprises a cluster node representing the concept triggering a terminal node representing the word.