Named entity recognition in query

• US 9,009,134 B2
• Filed: 03/16/2010
• Issued: 04/14/2015
• Est. Priority Date: 03/16/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Xu, Gu, Li, Hang, Guo, Jiafeng
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US12/725,342
• Publication Number:
  US 20110231347A1
• Time in Patent Office: 1,855 Days
• Field of Search: None
• US Class Current: 707/708
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Named Entity Recognition in Query (NERQ) involves detection of a named entity in a given query and classification of the named entity into one or more predefined classes. The predefined classes may be based on a predefined taxonomy. A probabilistic approach may be taken to detecting and classifying named entities in queries, the approach using either query log data or click through data and Weakly Supervised Latent Dirichlet Allocation (WS-LDA) to construct and train a topic model.

Claims

1. A computer-implemented method of recognizing named entities in a query with a recognition module operating on a processor, the method comprising:

receiving an input query from a user;

detecting a named entity in the input query;

representing the input query as one or more triples (e, t, c), wherein e represents the detected named entity, t represents a context of the detected named entity, and c represents a classification for the detected named entity that is determined based at least in part on a trained probabilistic topic model and a predefined taxonomy;

calculating a joint probability for individual ones of the one or more triples;

identifying a largest joint probability associated with a respective one of the one or more triples;

predicting an assigned classification for the detected named entity based at least in part on the identified largest joint probability; and

outputting the detected named entity and the assigned classification to the user.

2. The method of claim 1, wherein multiple classifications are predicted for the detected named entity based on the trained probabilistic topic model and the predefined taxonomy.

3. The method of claim 1, wherein the trained probabilistic topic model is trained using a Weakly Supervised Latent Dirichlet Allocation (WS-LDA) learning method, the WS-LDA learning method comprising determining, by a human, that the detected named entity can belong to the classification.

4. The method of claim 1, wherein the representing the input query as one or more triples (e, t, c) comprises determining that a plurality of triples (e, t, c) represent the input query by:

determining multiple possible ways of segmenting the input query into at least one named entity and at least one context;

labeling the at least one named entity with multiple possible classes for the multiple possible ways of segmenting the input query; and

determining the plurality of triples (e, t, c) that represent the input query as a set of unique triples that are formed by the multiple possible ways of segmenting the query and the multiple possible classes.

5. A method of recognizing named entities in a query with a recognition module operating on a processor, the method comprising:

defining a seed set comprising a seed named entity;

assigning a classification to the seed named entity based on a predefined taxonomy;

training a probabilistic topic model based on the seed named entity and the classification;

receiving an input query from a user;

detecting, by the processor, another named entity in the input query;

representing the input query as one or more triples (e, t, c), wherein e represents the detected other named entity, t represents a context of the detected other named entity, and c represents a particular classification for the detected other named entity that is determined based at least in part on the trained probabilistic topic model and the predefined taxonomy;

calculating a joint probability for individual ones of the one or more triples;

identifying a largest joint probability associated with a respective one of the one or more triples;

predicting, by the recognition module, an assigned classification for the detected other named entity based at least in part on the identified largest joint probability; and

outputting the detected other named entity and the assigned classification to the user.

6. The method of claim 5, wherein the classification assigned to the seed named entity is assigned manually, and

wherein the probabilistic topic model is trained using a Weakly Supervised Latent Dirichlet Allocation (WS-LDA) learning method, the WS-LDA learning method comprising determining, by a human, that the detected named entity can belong to the classification.

7. The method of claim 5, wherein the seed set is selected based at least in part on a data set comprising a plurality of search queries.

8. The method of claim 5, wherein a plurality of classifications is assigned to the seed named entity.

9. The method of claim 5, further comprising generating training data, the generating comprising:

scanning a data source for a first search query having the seed named entity;

collecting the first search query having the seed named entity;

identifying an associated context of the first search query having the seed named entity;

scanning the data source for a second search query having the associated context;

collecting the second search query having the associated context; and

extracting a new named entity from the second search query having the associated context.

10. The method of claim 9, wherein the data source is a click-through data set comprising queries received and selected Uniform Resource Locators (URLs) associated with the queries received.

11. The method of claim 9, wherein the associated context comprises a remainder of the first search query other than the seed named entity.

12. The method of claim 9, wherein the collecting the first search query further comprises calculating a frequency of occurrence for the seed named entity in the data source.

13. The method of claim 9, further comprising:

estimating a probability P_r(c|e) for the seed named entity and estimating a probability P_r(t|c) for the classification,

wherein c represents the classification, e represents the seed named entity, and t represents the associated context of the first search query.

14. The method of claim 9, further comprising:

estimating probabilities P_r(c|e) and P_r(e) for the new named entity while a probability P_r(t|c) is a fixed constant,

wherein c represents the classification, e represents the new named entity, and t represents the associated context of the second search query.

15. The method of claim 14, wherein the estimating P_r(c|e) and P_r(e) for the new named entity is performed at least in part using Weakly Supervised Latent Dirichlet Allocation (WS-LDA) comprising a determination, by a human, that the new named entity can belong to the classification.

16. The method of claim 9, further comprising collecting the extracted new named entity based on a heuristic threshold, wherein the new named entity is collected if the new named entity appears with at least a predefined number of unique contexts.

17. A system comprising:

a memory; and

a processor coupled to the memory, the processor executing components comprising;

an offline training component configured to;

construct training data comprising a first named entity and a classification for the first named entity, and

train a probabilistic topic model based on the first named entity and the classification for the first named entity using a weakly supervised learning method; and

an online prediction component configured to;

detect another named entity in an input query,

represent the input query as one or more triples (e, t, c), wherein e represents the detected other named entity, t represents a context of the detected other named entity, and c represents a particular classification for the detected other named entity that is determined based at least in part on the trained probabilistic topic model and a predefined taxonomy,

calculate a joint probability for individual ones of the one or more triples,

identify a largest joint probability associated with a respective one of the one or more triples,

predict an assigned classification for the detected other named entity based at least in part on the identified largest joint probability, and

output the detected other named entity and the assigned classification for the detected other named entity to a user.

18. The system of claim 17, wherein the constructing training data comprises:

defining a seed set from a data set comprising a plurality of search queries, the seed set comprising a seed named entity;

receiving, at least in part from a human, the classification for the seed named entity based on the predefined taxonomy;

scanning a data source for a first search query having the seed named entity;

collecting the first search query having the seed named entity;

identifying an associated context of the first search query having the seed named entity;

scanning the data source for a second search query having the associated context;

collecting the second search query having the associated context; and

extracting the first named entity from the second search query having the associated context.

19. The system of claim 18, wherein the data source is a click-through data set comprising queries received and clicked Uniform Resource Locators (URLs) associated with the queries received.

20. The system of claim 17, wherein

the weakly supervised learning method is a Weakly Supervised Latent Dirichlet Allocation (WS-LDA) learning method comprising determining, by a human, that the first named entity can belong to the classification for the first named entity.