Measuring entity extraction complexity

• US 9,128,933 B2
• Filed: 02/10/2012
• Issued: 09/08/2015
• Est. Priority Date: 04/13/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Padovitz, Amir J., Nagarajan, Bala Meenakshi
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US13/370,965
• Publication Number:
  US 20120143869A1
• Time in Patent Office: 1,306 Days
• Field of Search: 707/736, 707/737
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

A named entity input is received and a target sense for which the named entity input is to be extracted from a set of documents is identified. An extraction complexity feature is generated based on the named entity input, the target sense, and the set of documents. The extraction complexity feature indicates how difficult or complex it is deemed to be to identify the named entity input for the target sense in the set of documents.

Claims

1. A method implemented in a device, the method comprising:

receiving a named entity input;

identifying a target sense for which the named entity input is to be extracted from a set of documents; and

generating, based at least in part on both the named entity input and the set of documents, an extraction complexity feature that indicates how difficult it is deemed to be to identify the named entity input for the target sense in the set of documents, the generating including building an undirected graph based on the named entity input and the set of documents and looking for contexts in the undirected graph that are related to the target sense, the undirected graph including multiple vertices and multiple edges.

2. A method as recited in claim 1, further comprising providing the extraction complexity feature to a named entity recognition module that identifies the named entity input in the set of documents based at least in part on the extraction complexity feature.

3. A method as recited in claim 1, wherein generating the extraction complexity feature comprises generating the extraction complexity feature by performing a graph-based spreading activation technique to generate a language model, and performing a clustering technique to refine the language model.

4. A method as recited in claim 3, wherein performing the graph-based spreading activation technique comprises:

incrementing scores of selected ones of the multiple vertices by propagating a relevance of one or more of the multiple vertices through the undirected graph; and

normalizing, after incrementing the scores of the selected ones of the multiple vertices, scores of the multiple vertices to obtain the language model.

5. A method as recited in claim 4, wherein performing the clustering technique comprises refining the language model using a graph-based clustering technique.

6. A method as recited in claim 5, wherein generating the extraction complexity feature further comprises determining an extraction complexity measurement for the named entity input based on the refined language model.

7. A method as recited in claim 1, wherein the device is included in an open system having no knowledge of all the different senses in which the named entity input can be used.

8. A method as recited in claim 1, wherein generating the extraction complexity feature further comprises:

incrementing scores of selected ones of the multiple vertices by propagating a relevance of one or more of the multiple vertices through the undirected graph.

9. A method as recited in claim 8, wherein generating the extraction complexity feature further comprises:

normalizing, after incrementing the scores of the selected ones of the multiple vertices, scores of the multiple vertices to obtain the language model.

10. A method as recited in claim 9, wherein normalizing the scores of the multiple vertices comprises normalizing the scores of the multiple vertices in a range of values from 0 to 1 so that ones of the multiple vertices that were not touched by the propagating have a value of 0 and ones of the multiple vertices that were touched by the propagating have values that are proportionately weighted based on a highest activation score received by the multiple vertices.

11. One or more computer storage media having stored thereon multiple instructions that, when executed by one or more processors of a computing device, cause the one or more processors to:

receive a named entity input from a source;

identify a target sense for the named entity input, wherein the target sense is a particular desired usage of the named entity input in a document set; and

generate, based at least in part on both the named entity input and the document set, an extraction complexity measurement that indicates a complexity of identifying the named entity input in the document set for the target sense, wherein to generate the extraction complexity measurement is to build an undirected graph based on the named entity input and the document set, the undirected graph including multiple vertices and multiple edges, the multiple vertices comprising co-occurring contexts surrounding occurrences of the named entity input in the set of documents.

12. One or more computer storage media as recited in claim 11, wherein the multiple instructions further cause the one or more processors to provide the extraction complexity measurement to a named entity recognition module that identifies the named entity input in the document set based at least in part on the extraction complexity measurement.

13. One or more computer storage media as recited in claim 11, wherein to generate the extraction complexity measurement is to generate the extraction complexity measurement by performing a graph-based spreading activation technique to generate a language model, and to perform a clustering technique to refine the language model.

14. One or more computer storage media as recited in claim 11, wherein to generate the extraction complexity measurement is further to:

increment scores of selected ones of the multiple vertices by propagating a relevance of one or more of the multiple vertices through the undirected graph; and

normalize, after the scores of the selected ones of the multiple vertices are incremented, scores of the multiple vertices to obtain a language model.

15. One or more computer storage media as recited in claim 14, wherein to generate the extraction complexity measurement is further to perform a graph-based clustering technique to refine the language model, and determine the extraction complexity measurement for the named entity input based on the refined language model.

16. One or more computer storage media as recited in claim 11, wherein to generate the extraction complexity measurement is to perform a graph-based clustering technique to refine a language model obtained from performing a graph-based spreading activation technique.

17. One or more computer storage media as recited in claim 16, wherein to generate the extraction complexity measurement is to determine the extraction complexity measurement for the named entity input based on the refined language model.

18. One or more computer storage media as recited in claim 17, wherein the refined language model includes multiple clusters each including one or more documents, and wherein to determine the extraction complexity measurement for the named entity input based on the refined language model is to:

determine a relatedness of each of the multiple clusters in the refined language model to the target sense;

assign, for each of the multiple clusters, a score to the cluster based on the relatedness of the cluster to the target sense;

determine an average cluster score that is an average of the scores of the multiple clusters;

identify, as a value |C*|, a number of documents in clusters having a score greater than the average cluster score;

identify, as a value |D|, a number of documents in the document set; and

determine the extraction complexity measurement as;

19. One or more computer storage media as recited in claim 11, wherein the computing device is included in an open system in which the computing device has no knowledge of all the different senses in which the named entity input can be used.

20. One or more computer storage media having stored thereon multiple instructions that, when executed by one or more processors of a computing device, cause the one or more processors to:

receive a named entity input from a source;

identify a target sense for the named entity input, wherein the target sense is a particular desired usage of the named entity input in a set of documents; and

generate, based at least in part on both the named entity input and the set of documents, an extraction complexity measurement that indicates how difficult it is deemed to be to identify the named entity input in the set of documents for the target sense, wherein to generate the extraction complexity measurement is to;

perform a graph-based spreading activation technique to generate a language model by;

building an undirected graph based on the named entity input and the set of documents, the undirected graph including multiple vertices and multiple edges,

incrementing scores of selected ones of the multiple vertices by propagating a relevance of one or more of the multiple vertices through the undirected graph, and

normalizing, after incrementing the scores of the selected ones of the multiple vertices, scores of the multiple vertices to obtain the language model;

perform a graph-based clustering technique to refine the language model; and

determine the extraction complexity measurement based on the refined language model.

21. A computing device comprising:

one or more processors; and

one or more computer storage media having stored thereon multiple instructions that, responsive to execution by the one or more processors, cause the one or more processors to perform acts comprising;

receiving a named entity input;

identifying a target sense for which the named entity input is to be extracted from a set of documents; and

generating, based at least in part on both the named entity input and the set of documents, an extraction complexity feature that indicates how difficult it is deemed to be to identify the named entity input for the target sense in the set of documents, the generating including building an undirected graph based on the named entity input and the set of documents and looking for contexts in the undirected graph that are related to the target sense, the undirected graph including multiple vertices and multiple edges.

22. A computing device as recited in claim 21, the acts further comprising providing the extraction complexity feature to a named entity recognition module that identifies the named entity input in the set of documents based at least in part on the extraction complexity feature.

23. A computing device as recited in claim 21, wherein generating the extraction complexity feature comprises generating the extraction complexity feature by performing a graph-based spreading activation technique to generate a language model, and performing a clustering technique to refine the language model.

24. A computing device comprising:

one or more processors; and

one or more computer storage media having stored thereon multiple instructions that, responsive to execution by the one or more processors, cause the one or more processors to;

receive a named entity input from a source;

identify a target sense for the named entity input, wherein the target sense is a particular desired usage of the named entity input in a document set; and

generate, based at least in part on both the named entity input and the document set, an extraction complexity measurement that indicates a complexity of identifying the named entity input in the document set for the target sense, wherein to generate the extraction complexity measurement is to build an undirected graph based on the named entity input and the document set, the undirected graph including multiple vertices and multiple edges, the multiple vertices comprising co-occurring contexts surrounding occurrences of the named entity input in the set of documents.

25. A computing device as recited in claim 24, wherein the multiple instructions further cause the one or more processors to provide the extraction complexity measurement to a named entity recognition module that identifies the named entity input in the document set based at least in part on the extraction complexity measurement.

26. A computing device as recited in claim 24, wherein to generate the extraction complexity measurement is to generate the extraction complexity measurement by performing a graph-based spreading activation technique to generate a language model, and to perform a clustering technique to refine the language model.