Method and apparatus for characterizing documents based on clusters of related words

• US 8,688,720 B1
• Filed: 06/02/2008
• Issued: 04/01/2014
• Est. Priority Date: 10/03/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Harik, Georges, Shazeer, Noam M.
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US12/131,637
• Time in Patent Office: 2,129 Days
• Field of Search: 707/736, 707/737, 707/738, 707/739, 707/748, 707/752, 707/754, 707/755, 707/756, 707/758, 707/769, 707/771
• US Class Current: 707/755
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

One embodiment of the present invention provides a system characterizes a document with respect to clusters of conceptually related words. Upon receiving a document containing a set of words, the system selects “candidate clusters” of conceptually related words that are related to the set of words. These candidate clusters are selected using a model that explains how sets of words are generated from clusters of conceptually related words. Next, the system constructs a set of components to characterize the document, wherein the set of components includes components for candidate clusters. Each component in the set of components indicates a degree to which a corresponding candidate cluster is related to the set of words.

Claims

1. A computer-implemented method comprising:

receiving resource that includes a set of words;

identifying a set of candidate clusters from a probabilistic model that are classified as likely to be active in generating the set of words;

generating a vector that characterizes the resource, wherein, for each cluster of the set of candidate clusters, a component of the vector indicates a degree to which the cluster was active in generating the set of words; and

using the vector in performing an operation related to the resource.

2. The method of claim 1, wherein identifying a set of candidate clusters from a probabilistic model that are classified as likely to be active in generating the set of words comprises:

generating an evidence tree for the set of words, wherein the evidence tree identifies one or more clusters that each link to terminal nodes associated with the set of words;

determining, using the evidence tree and for each cluster, a respective likelihood that the cluster is active in generating the set of words; and

selecting one or more of the clusters as candidate clusters based on their respective likelihoods.

3. The method of claim 1, wherein generating a vector that characterizes the resource, wherein, for each cluster of the set of candidate clusters, a component of the vector indicates a degree to which the cluster was active in generating the set of words comprises:

selecting, for the probabilistic model, one or more states that are likely to generate the set of words;

generating, using the one or more selected states and for each cluster in the set of candidate clusters, a respective likelihood that the cluster is active in generating the set of words; and

generating, based on the respective likelihoods, a vector that characterizes the resource, wherein the vector includes a respective component for each cluster of the set of candidate clusters, and wherein each component indicates a respective likelihood that the cluster is active in generating the set of words.

4. The method of claim 3, wherein the respective likelihood that the cluster is active in generating the set of words is based on a ratio of a numerator and a denominator, wherein the numerator is a sum of probabilities for states, in the one or more states, in which the cluster is determined to be active, and wherein the denominator is a sum of probabilities for all states in the one or more states in which the cluster is determined to be active or inactive.

5. The method of claim 3, wherein selecting, using the probabilistic model, one or more states that are likely to generate the set of words comprises:

selecting, for the probabilistic model, a starting state, wherein the starting state identifies nodes in the probabilistic model as being active or inactive; and

determining, using the starting state, one or more states that are likely to generate the set of words, the one or more states having been determined based on a hill climbing operation.

6. The method of claim 5, wherein the nodes in the probabilistic model comprise one or more clusters that correspond to the set of words and one or more terminal nodes that correspond to the set of words.

7. The method of claim 1, wherein using the vector in performing an operation related to the resource comprises identifying, based on the vector, one or more concepts related to the resource, the concepts providing a meaning of the resource.

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;

receiving resource that includes a set of words;

identifying a set of candidate clusters from a probabilistic model that are classified as likely to be active in generating the set of words;

generating a vector that characterizes the resource, wherein, for each cluster of the set of candidate clusters, a component of the vector indicates a degree to which the cluster was active in generating the set of words; and

using the vector in performing an operation related to the resource.

9. The system of claim 8, wherein identifying a set of candidate clusters from a probabilistic model that are classified as likely to be active in generating the set of words comprises:

generating an evidence tree for the set of words, wherein the evidence tree identifies one or more clusters that each link to terminal nodes associated with the set of words;

determining, using the evidence tree and for each cluster, a respective likelihood that the cluster is active in generating the set of words; and

selecting one or more of the clusters as candidate clusters based on their respective likelihoods.

10. The system of claim 8, wherein generating a vector that characterizes the resource, wherein, for each cluster of the set of candidate clusters, a component of the vector indicates a degree to which the cluster was active in generating the set of words comprises:

selecting, for the probabilistic model, one or more states that are likely to generate the set of words;

generating, using the one or more selected states and for each cluster in the set of candidate clusters, a respective likelihood that the cluster is active in generating the set of words; and

generating, based on the respective likelihoods, a vector that characterizes the resource, wherein the vector includes a respective component for each cluster of the set of candidate clusters, and wherein each component indicates a respective likelihood that the cluster is active in generating the set of words.

11. The system of claim 10, wherein the respective likelihood that the cluster is active in generating the set of words is based on a ratio of a numerator and a denominator, wherein the numerator is a sum of probabilities for states, in the one or more states, in which the cluster is determined to be active, and wherein the denominator is a sum of probabilities for all states in the one or more states in which the cluster is determined to be active or inactive.

12. The system of claim 10, wherein selecting, using the probabilistic model, one or more states that are likely to generate the set of words comprises:

selecting, for the probabilistic model, a starting state, wherein the starting state identifies nodes in the probabilistic model as being active or inactive; and

determining, using the starting state, one or more states that are likely to generate the set of words, the one or more states having been determined based on a hill climbing operation.

13. The system of claim 12, wherein the nodes in the probabilistic model comprise one or more clusters that correspond to the set of words and one or more terminal nodes that correspond to the set of words.

14. The system of claim 8, wherein using the vector in performing an operation related to the resource comprises identifying, based on the vector, one or more concepts related to the resource, the concepts providing a meaning of the resource.

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

receiving resource that includes a set of words;

identifying a set of candidate clusters from a probabilistic model that are classified as likely to be active in generating the set of words;

generating a vector that characterizes the resource, wherein, for each cluster of the set of candidate clusters, a component of the vector indicates a degree to which the cluster was active in generating the set of words; and

using the vector in performing an operation related to the resource.

16. The medium of claim 15, wherein identifying a set of candidate clusters from a probabilistic model that are classified as likely to be active in generating the set of words comprises:

generating an evidence tree for the set of words, wherein the evidence tree identifies one or more clusters that each link to terminal nodes associated with the set of words;

determining, using the evidence tree and for each cluster, a respective likelihood that the cluster is active in generating the set of words; and

selecting one or more of the clusters as candidate clusters based on their respective likelihoods.

17. The medium of claim 15, wherein generating a vector that characterizes the resource, wherein, for each cluster of the set of candidate clusters, a component of the vector indicates a degree to which the cluster was active in generating the set of words comprises:

selecting, for the probabilistic model, one or more states that are likely to generate the set of words;

generating, using the one or more selected states and for each cluster in the set of candidate clusters, a respective likelihood that the cluster is active in generating the set of words; and

generating, based on the respective likelihoods, a vector that characterizes the resource, wherein the vector includes a respective component for each cluster of the set of candidate clusters, and wherein each component indicates a respective likelihood that the cluster is active in generating the set of words.

18. The medium of claim 17, wherein the respective likelihood that the cluster is active in generating the set of words is based on a ratio of a numerator and a denominator, wherein the numerator is a sum of probabilities for states, in the one or more states, in which the cluster is determined to be active, and wherein the denominator is a sum of probabilities for all states in the one or more states in which the cluster is determined to be active or inactive.

19. The medium of claim 17, wherein selecting, using the probabilistic model, one or more states that are likely to generate the set of words comprises:

selecting, for the probabilistic model, a starting state, wherein the starting state identifies nodes in the probabilistic model as being active or inactive; and

determining, using the starting state, one or more states that are likely to generate the set of words, the one or more states having been determined based on a hill climbing operation.

20. The medium of claim 19, wherein the nodes in the probabilistic model comprise one or more clusters that correspond to the set of words and one or more terminal nodes that correspond to the set of words.

21. The medium of claim 15, wherein using the vector in performing an operation related to the resource comprises identifying, based on the vector, one or more concepts related to the resource, the concepts providing a meaning of the resource.