Leveraging cross-document context to label entity

• US 7,970,808 B2
• Filed: 05/05/2008
• Issued: 06/28/2011
• Est. Priority Date: 05/05/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ganti, Venkatesh, Konig, Arnd Christian
• Primary Examiner(s): EHICHIOYA, IRETE FRED
• Application Number:
  US12/114,824
• Publication Number:
  US 20090282012A1
• Time in Patent Office: 1,149 Days
• Field of Search: 707/609, 707/705, 707/765, 707/802, 707/962, 707/E17.048
• US Class Current: N/A
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Entities, such as people, places and things, are labeled based on information collected across a possibly large number of documents. One or more documents are scanned to recognize the entities, and features are extracted from the context in which those entities occur in the documents. Observed entity-feature pairs are stored either in an in-memory store or an external store. A store manager optimizes use of the limited amount of space for an in-memory store by determining which store to put an entity-feature pair in, and when to evict features from the in-memory store to make room for new pairs. Feature that may be observed in an entity'"'"'s context may take forms such as specific word sequences or membership in a particular list.

Claims

1. A method of classifying entities, the method comprising:

using a processor to perform acts comprising;

recognizing occurrences of an entity in a plurality of documents;

identifying a plurality of features in contexts of said occurrences, a first one of the features being derived from a first context of a first one of the occurrences in a first one of the documents, and a second one of the features being derived from a second context of a second one of the occurrences in a second one of the documents;

calculating a sum of a plurality of weights, wherein each of the features is associated with one of the weights;

making a first determination that said sum exceeds a first threshold;

making a second determination that a label applies to said entity based on said first determination; and

storing or communicating a fact that said label applies to said entity, wherein said features comprise membership in a list, and wherein said acts further comprise;

choosing a subset of members of said members of said list based on members in said subset being estimated to occur more frequently in said documents than other members of said list; and

comparing a string that occurs in at least one of said contexts with members of said subset; and

making a third determination that said string represents a member of said list, said third determination being made (a) based on said string'"'"'s being among said subset, and (b) without use of a filter that accepts all strings that are members of said list and accepts at least one string that is not a member of said list.

2. The method of claim 1, wherein said features comprise a text n-gram, and wherein said identifying comprises:

determining that said text n-gram occurs in at least one of said contexts.

3. The method of claim 1, wherein said identifying comprises:

determining that a surface form of a member of said list occurs in at least one of said contexts.

4. The method of claim 1, wherein said acts further comprise:

storing a pair that comprises said entity and one of said features in either a first store or a second store; and

choosing whether to store said pair in said first store or said second store based on an estimate of a frequency of said pair in said documents.

5. The method of claim 1, wherein said documents contain a third feature of said entity, said third feature not being among said features, and wherein said acts further comprise:

determining that a probability that said label applies to said entity exceeds a second threshold, said second determination being made without consideration of said third feature.

6. The method of claim 1, wherein said documents contain a third feature of said entity, said third feature not being among said features, and wherein said acts further comprise:

verifying, based on data that comprises said third feature, that said label applies to said entity, said third feature having a sign opposite said label, said second determination having been made without consideration of said third feature.

7. The method of claim 1, wherein said features comprise membership in a list, and wherein said acts further comprise:

using said filter to identify a string that occurs in at least one of said contexts as a member of a set of candidates; and

performing a join of said set of candidates and said list to determine that said string is a member of said list and not a false positive accepted by said filter.

8. A system that classifies entities, the system comprising:

a volatile random-access memory;

an entity recognizer that identifies occurrence of a first entity in a document;

a feature extractor that identifies a feature that occurs in a context of said occurrence of said first entity;

a first entity-feature store that is located in said memory and that stores entity-feature pairs;

a second entity-feature store that is not located in said memory and that stores entity-feature pairs; and

a store manager that receives a first entity-feature pair obtained from a document processed by collective action of said entity recognizer and said feature extractor, wherein said store manager maintains a first list of entity-feature pairs and defines a subset of said first list as being those entity feature pairs that are estimated to occur at least with a first estimated frequency, a second entity-feature pair being stored in said first entity-feature store and being in said subset, and wherein said store manager determines whether to store said first entity-feature pair in said first entity-feature store or said second entity-feature store based on a first estimated frequency of said second entity-feature pair.

9. The system of claim 8, further comprising:

a component that, given an entity-feature pair (e,f) in which e is an entity and f is a feature, estimates the frequency of (e,f) based on a product of an estimated frequency of e and an estimated frequency of f.

10. The system of claim 8, further comprising:

a component that estimates a frequency of an entity-feature pair based on information comprising a frequency, in a training data set, of a feature in said entity-feature pair.

11. The system of claim 8, wherein said first entity-feature pair and said second entity-feature pair have the same entity as each other, wherein said store manager makes a determination that a second estimated frequency, of said first entity-feature pair, is higher than said first estimated frequency, and evicts said second entity-feature pair based on said determination.

12. The system of claim 8, wherein said first entity-feature pair comprises said first entity, e wherein said first entity does not appear in said first entity-feature store, and wherein said store manager determines that there is an entity, e′

, in said first entity-feature store that has a lower estimated frequency than e, there being k entity-feature pairs in said entity-feature store having feature e′

, said store manager determining that a sum of frequencies of the entity-feature pairs in which e′

is the feature is greater than a sum of the k lowest-frequency features in the first entity-feature store, said second entity-feature pair being one of said k lowest-frequency features, said store manager storing said first entity-feature pair in said first entity-feature store and evicting said second entity-feature pair from said first entity-feature store.

13. The system of claim 8, wherein said feature comprises membership in a second list, and wherein said feature extractor identifies said feature as occurring in said context of said first entity based on a finding that a second entity occurs both in said second list and in said context.

14. One or more computer-readable storage media that store executable instructions to perform a method of classifying entities, the method comprising:

recognizing occurrences of an entity in a plurality of documents;

identifying a plurality of first features in contexts of said occurrences;

assigning a label to said entity, based on weights of said first features, when probability of correctness of said label reaches a threshold, there being at least some second features in said document that are associated with said entity but that are not included among said first features;

verifying correctness of said label based one or more of said second features;

storing a first pair that comprise said entity and one of said first features in either a first entity-feature store that is in volatile random access memory, or a second entity feature store that is not in said memory;

choosing whether to store said first pair in said first entity-feature store based on a first estimate of said frequency of said first pair in said plurality of documents;

determining that said first estimate of said frequency is higher than an estimated frequency of a second pair that is stored in said first entity-feature store; and

evicting said second pair from said first entity-feature store.

15. The one or more computer-readable storage media of claim 14, wherein the method further comprises:

calculating said first estimate as a product of a second estimate of a frequency of said entity in said documents and a third estimate of a frequency of said feature in said documents.

16. The one or more computer-readable storage media of claim 14, wherein the method further comprises:

encountering one of said second features in said documents; and

storing a third pair that comprises said entity and said one of said second features based on a finding that a weight associated with said third pair has a sign opposite said label.

17. The one or more computer-readable storage media of claim 14, wherein the method further comprises:

after evaluation of said documents, assigning labels to entities to which a label is not assigned during evaluation of said documents.