Extracting semantic classes and instances from text

• US 8,510,308 B1
• Filed: 06/16/2010
• Issued: 08/13/2013
• Est. Priority Date: 06/16/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pasca, Marius, Van Durme, Benjamin
• Primary Examiner(s): LIAO, JASON G
• Application Number:
  US12/816,852
• Time in Patent Office: 1,154 Days
• Field of Search: None
• US Class Current: 707/740
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for extracting semantic classes and corresponding instances from a collection of text. One aspect of the subject matter described in this specification can be embodied in methods that include the actions of receiving a collection of text; identifying an initial collection of instance-class pairs for the collection of text; clustering a collection of semantically similar phrases using the collection of text; generating, using one or more processors, an extracted collection of instance-class pairs using the initial collection of instance-class pairs and the semantically similar phrase clusters; and storing the extracted collection of instance-class pairs for use in information retrieval.

Claims

1. A method performed by data processing apparatus, the method comprising:

receiving a collection of text;

identifying a first collection of instance-class pairs for the collection of text, wherein the first collection of instance-class pairs are identified by applying one or more template patterns to a collection of documents;

clustering a collection of semantically similar phrases using the collection of text;

determining, for each class in the first collection of instance-class pairs;

whether a threshold number of instances within a cluster in the semantically similar phrase clusters are labeled by the class, and

whether a threshold number of clusters in the semantically similar phrase clusters include at least one instance that is labeled by the class;

in response to determining that a threshold number of instances within a cluster are labeled by a class and a threshold number of clusters in the semantically similar phrase clusters include at least one instance that is labeled by the class, selecting each instance in the first collection of instance-class pairs that are labeled by the class to be included in a second collection of instance-class pairs; and

storing the second collection of instance-class pairs for use in information retrieval.

2. The method of claim 1, where the threshold number of instances is a minimum number of instances paired with the class found within the cluster.

3. The method of claim 1, where the threshold number of clusters is a maximum number of clusters that includes an instance of the class.

4. The method of claim 1, where identifying a first collection of instance-class pairs comprises receiving previously generated instance-class pairs.

5. The method of claim 1, were clustering a collection of semantically similar phrases comprises:

receiving an input vocabulary of phrases;

identifying matches for the vocabulary of phrases in a collection of documents;

identifying a context associated with each identified match;

generating a vector associated with each matching phrase having the corresponding context as an entry in the respective vector; and

clustering phrases using the vectors.

6. The method of claim 1, further comprising:

receiving a query;

identifying one or more terms in the query corresponding to a class;

retrieving instances corresponding to the class; and

processing documents identified as responsive to the query such that documents in which the retrieved instances occur relative to the remaining query terms are promoted in a search results ranking.

7. A computer-readable storage device storing instructions that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

receiving a collection of text;

identifying a first collection of instance-class pairs for the collection of text, wherein the first collection of instance-class pairs are identified by applying one or more template patterns to a collection of documents;

clustering a collection of semantically similar phrases using the collection of text;

determining, for each class in the first collection of instance-class pairs;

whether a threshold number of instances within a cluster in the semantically similar phrase clusters are labeled by the class, and

whether a threshold number of clusters in the semantically similar phrase clusters include at least one instance that is labeled by the class;

in response to determining that a threshold number of instances within a cluster are labeled by a class and a threshold number of clusters in the semantically similar phrase clusters include at least one instance that is labeled by the class, selecting each instance in the first collection of instance-class pairs that are labeled by the class to be included in a second collection of instance-class pairs; and

storing the second collection of instance-class pairs for use in information retrieval.

8. The computer-readable storage device of claim 7, where the threshold number of instances is a minimum number of instances paired with the class found within the cluster.

9. The computer-readable storage device of claim 7, where the threshold number of clusters is a maximum number of clusters that includes an instance of the class.

10. The computer-readable storage device of claim 7, where identifying an first collection of instance-class pairs comprises receiving previously generated instance-class pairs.

11. The computer-readable storage device of claim 7, were clustering a collection of semantically similar phrases comprises:

receiving an input vocabulary of phrases;

identifying matches for the vocabulary of phrases in a collection of documents;

identifying a context associated with each identified match;

generating a vector associated with each matching phrase having the corresponding context as an entry in the respective vector; and

clustering phrases using the vectors.

12. The computer-readable storage device of claim 7, further comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations including:

receiving a query;

identifying one or more terms in the query corresponding to a class;

retrieving instances corresponding to the class; and

processing documents identified as responsive to the query such that documents in which the retrieved instances occur relative to the remaining query terms are promoted in a search results ranking.

13. A system comprising:

one or more processors configured to perform operations comprising;

receiving a collection of text;

identifying a first collection of instance-class pairs for the collection of text, wherein the first collection of instance-class pairs are identified by applying one or more template patterns to a collection of documents;

clustering a collection of semantically similar phrases using the collection of text;

determining, for each class in the first collection of instance-class pairs;

whether a threshold number of instances within a cluster in the semantically similar phrase clusters are labeled by the class, and

whether a threshold number of clusters in the semantically similar phrase clusters include at least one instance that is labeled by the class;

in response to determining that a threshold number of instances within a cluster are labeled by a class and a threshold number of clusters in the semantically similar phrase clusters include at least one instance that is labeled by the class, selecting each instance in the first collection of instance-class pairs that are labeled by the class to be included in a second collection of instance-class pairs; and

storing the second collection of instance-class pairs for use in information retrieval.

14. The system of claim 13, where the threshold number of instances is a minimum number of instances paired with the class found within the cluster.

15. The system of claim 13, where the threshold number of clusters is a maximum number of clusters that includes an instance of the class.

16. The system of claim 13, where identifying a first collection of instance-class pairs comprises receiving previously generated instance-class pairs.

17. The system of claim 13, were clustering a collection of semantically similar phrases comprises:

receiving an input vocabulary of phrases;

identifying matches for the vocabulary of phrases in a collection of documents;

identifying a context associated with each identified match;

generating a vector associated with each matching phrase having the corresponding context as an entry in the respective vector; and

clustering phrases using the vectors.

18. The system of claim 13, further configured to perform operations comprising:

receiving a query;

identifying one or more terms in the query corresponding to a class;

retrieving instances corresponding to the class; and

processing documents identified as responsive to the query such that documents in which the retrieved instances occur relative to the remaining query terms are promoted in a search results ranking.