Selectively merging clusters of conceptually related words in a generative model for text

• US 9,507,858 B1
• Filed: 11/27/2012
• Issued: 11/29/2016
• Est. Priority Date: 02/28/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lerner, Uri N., Jahr, Michael E.
• Primary Examiner(s): OBERLY, VAN HONG
• Application Number:
  US13/686,781
• Time in Patent Office: 1,463 Days
• Field of Search: 707/797
• US Class Current: 1/1
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

One embodiment of the present invention provides a system that merges similar clusters of conceptually-related words in 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 cluster nodes representing clusters of conceptually related words. Nodes in the current model are coupled together by weighted links, wherein if a node fires, a link from the node to another node causes the other node to fire with a probability proportionate to the weight of the link. Next, the system determines whether cluster nodes in the current model explain other cluster nodes in the current model. If two cluster nodes explain each other, the system merges the two cluster nodes to form a combined cluster node.

Claims

1. A computer-implemented method comprising:

receiving, by at least one processor, a search query comprising one or more terms from a device of a user;

in response to the received search query, accessing, by the at least one processor, data identifying contents of one or more web pages;

obtaining, by the at least one processor, a probabilistic generative model that includes (i) a first node that descends from one or more parent nodes, and (ii) one or more child nodes that descend from a second node;

determining, by the at least one processor, to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend;

in response to determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend, determining that, before the first node and the second node are merged, a particular node of the probabilistic generative model is both (i) one of the one or more parent nodes of the first node, and (ii) one of the one or more child nodes of the second node, then, after the first node and the second node are merged, designating the particular node as (i) a child node that descends from a combined node that results from merging the first node with the second node, and (ii) not a parent node from which the combined node that results from merging the first node with the second node descends;

generating, by the at least one processor, a first concept characterizing the search query and one or more second concepts characterizing each of the web pages using the probabilistic generative model;

determining, by the at least one processor, that at least one of the second concepts matches the first concept, the at least one second concept being associated with at least one of the web pages; and

transmitting, to the user device, a response to the search query that identifies the at least one of the web pages.

2. The method of claim 1, further comprising:

determining, based on the probabilistic generative model, that the first node explains the second node; and

s

wherein determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend to generate the combined node comprises;

based on determining that the first node explains the second node, determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend to generate the combined node.

3. The method of claim 2, further comprising:

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

applying the set of training documents to the probabilistic generative model to produce a new probabilistic generative model; and

selecting the new probabilistic generative model as the probabilistic generative model.

4. The method of claim 2, wherein obtaining the probabilistic generative model comprises:

obtaining a probabilistic generative mode that includes (i) a first node that descends from one or more respective parent nodes, (ii) a second node that descends from one or more respective parent nodes, (iii) one or more child nodes that descend from the first node, and (iv) one or more child nodes that descend from the second node; and

wherein the method further comprises;

merging the one or more parent nodes from which the first node descends with the one or more parent nodes from which the second node descends to produce a set of parent nodes for the combined node; and

merging the one or more child nodes that descend from the first node with the one or more child nodes that descend from the second node to produce a set of children nodes for the combined node.

5. The method of claim 2, wherein determining, based on the probabilistic generative model, that the first node explains the second node comprises:

generating, for the second node, a query that includes a set of terms associated with the second node;

processing the generated query using a modified probabilistic generative model to generate a set of resulting nodes, wherein the resulting nodes include the first node; and

determining that the first node explains the second node based on an activation strength of the first node exceeding a threshold.

6. The method of claim 5, wherein the modified probabilistic generative model comprises the probabilistic generative model without the second node.

7. The method of claim 5, wherein the set of terms comprise terms that correspond to nodes that are classified as being likely to fire when the second node fires.

8. The method of claim 1, wherein obtaining the probabilistic generative model further comprises:

obtaining a probabilistic generative model whose nodes (I) each correspond to a different cluster of terms in the probabilistic generative model, and (II) include (i) a first node that descends from one or more parent nodes, and (ii) one or more child nodes that descend from a second node.

9. The method of claim 8, wherein determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend comprises:

determining to merge the first node that corresponds to a first cluster of terms in the probabilistic generative model with the second node corresponds to a second cluster of terms in the probabilistic generative model to generate the combined node that corresponds to the first and second clusters of terms in the probabilistic generative model.

10. 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;

receiving, from a device of a user, a search query comprising one or more terms;

in response to the received search query, accessing data identifying contents of one or more web pages;

obtaining a probabilistic generative model that includes (i) a first node that descends from one or more parent nodes, and (ii) one or more child nodes that descend from a second node;

determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend;

in response to determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend, determining that, before the first node and the second node are merged, a particular node of the probabilistic generative model is both (i) one of the one or more parent nodes of the first node, and (ii) one of the one or more child nodes of the second node, then, after the first node and the second node are merged, designating the particular node as (i) a child node that descends from a combined node that results from merging the first node with the second node, and (ii) not a parent node from which the combined node that results from merging the first node with the second node descends;

generating a first concept characterizing the search query and one or more second concepts characterizing each of the web pages using the probabilistic generative model;

determining that at least one of the second concepts matches the first concept, the at least one second concept being associated with at least one of the web pages; and

transmitting, to the user device, a response to the search query that identifies the at least one of the web pages.

11. The system of claim 10, wherein the operations further comprise:

determining, based on the probabilistic generative model, that the first node explains the second node; and

wherein determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend to generate the combined node comprises;

based on determining that the first node explains the second node, determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend to generate the combined node.

12. The system of claim 11, wherein the operations further comprise:

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

applying the set of training documents to the probabilistic generative model to produce a new probabilistic generative model; and

selecting the new probabilistic generative model as the probabilistic generative model.

13. The system of claim 11, wherein obtaining the probabilistic generative model comprises:

obtaining a probabilistic generative mode that includes (i) a first node that descends from one or more respective parent nodes, (ii) a second node that descends from one or more respective parent nodes, (iii) one or more child nodes that descend from the first node, and (iv) one or more child nodes that descend from the second node; and

wherein the operations further comprise;

merging the one or more parent nodes from which the first node descends with the one or more parent nodes from which the second node descends to produce a set of parent nodes for the combined node; and

merging the one or more child nodes that descend from the first node with the one or more child nodes that descend from the second node to produce a set of children nodes for the combined node.

14. The system of claim 11, wherein determining, based on the probabilistic generative model, that the first node explains the second node comprises:

generating, for the second node, a query that includes a set of terms associated with the second node;

processing the generated query using a modified probabilistic generative model to generate a set of resulting nodes, wherein the resulting nodes include the first node; and

determining that the first node explains the second node based on an activation strength of the first node exceeding a threshold.

15. The system of claim 14, wherein the modified probabilistic generative model comprises the probabilistic generative model without the second node.

16. The system of claim 14, wherein the set of terms comprise terms that correspond to nodes that are classified as being likely to fire when the second node fires.

17. A non-transitory computer-readable medium having instructions stored thereon that, when executed by a processor, cause the processor to perform operations comprising:

receiving, from a device of a user, a search query comprising one or more terms;

in response to the received search query, accessing data identifying contents of one or more web pages;

obtaining a probabilistic generative model that includes (i) a first node that descends from one or more parent nodes, and (ii) one or more child nodes that descend from a second node;

determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend;

in response to determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend, determining that, before the first node and the second node are merged, a particular node of the probabilistic generative model is both (i) one of the one or more parent nodes of the first node, and (ii) one of the one or more child nodes of the second node, then, after the first node and the second node are merged, designating the particular node as (i) a child node that descends from a combined node that results from merging the first node with the second node, and (ii) not a parent node from which the combined node that results from merging the first node with the second node descends;

generating a first concept characterizing the search query and one or more second concepts characterizing each of the web pages using the probabilistic generative model;

determining that at least one of the second concepts matches the first concept, the at least one second concept being associated with at least one of the web pages; and

transmitting, to the user device, a response to the search query that identifies the at least one of the web pages.

18. The medium of claim 17, wherein the operations further comprise:

determining, based on the probabilistic generative model, that the first node explains the second node; and

wherein determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend to generate the combined node comprises;

based on determining that the first node explains the second node, determining to merge the first node that descends from the one or more parent nodes of the first node with the second node from which the one or more child nodes of the second node descend to generate the combined node.

19. The medium of claim 18, wherein the operations further comprise:

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

applying the set of training documents to the probabilistic generative model to produce a new probabilistic generative model; and

selecting the new probabilistic generative model as the probabilistic generative model.

20. The medium of claim 18, wherein obtaining the probabilistic generative model comprises:

obtaining a probabilistic generative mode that includes (i) a first node that descends from one or more respective parent nodes, (ii) a second node that descends from one or more respective parent nodes, (iii) one or more child nodes that descend from the first node, and (iv) one or more child nodes that descend from the second node; and

wherein the operations further comprise;

merging the one or more parent nodes from which the first node descends with the one or more parent nodes from which the second node descends to produce a set of parent nodes for the combined node; and

merging the one or more child nodes that descend from the first node with the one or more child nodes that descend from the second node to produce a set of children nodes for the combined node.

21. The medium of claim 18, wherein determining, based on the probabilistic generative model, that the first node explains the second node comprises:

generating, for the second node, a query that includes a set of terms associated with the second node;

processing the generated query using a modified probabilistic generative model to generate a set of resulting nodes, wherein the resulting nodes include the first node; and

determining that the first node explains the second node based on an activation strength of the first node exceeding a threshold.