Generating implicit labels and training a tagging model using such labels

• US 8,250,015 B2
• Filed: 04/07/2009
• Issued: 08/21/2012
• Est. Priority Date: 04/07/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Xiao, Wang, Ye-Yi
• Primary Examiner(s): Rivas, Omar Fernandez
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US12/419,336
• Publication Number:
  US 20100256969A1
• Time in Patent Office: 1,232 Days
• Field of Search: 706/45
• US Class Current: 706/45
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks

Abstract

A training module is described for training a conditional random field (CRF) tagging model. The training module trains the tagging model based on an explicitly-labeled training set and an implicitly-labeled training set. The explicitly-labeled training set includes explicit labels that are manually selected via human annotation, while the implicitly-labeled training set includes implicit labels that are generated in an unsupervised manner. In one approach, the training module can train the tagging model by treating the implicit labels as non-binding evidence that has a bearing on values of hidden state sequence variables. In another approach, the training module can treat the implicit labels as binding or hard evidence. A labeling system is also described for providing the implicit labels.

Claims

1. A training module implemented on one or more computers comprised of one or more processors and storage, for training a tagging model, the training module comprising:

logic that receives and stores an explicitly-labeled training set in the storage, the explicitly-labeled training set including explicit labels that have been manually selected;

logic that receives and stores an implicitly-labeled training set in the storage, the implicitly-labeled training set including implicit labels that have been generated by a labeling system; and

logic performed by the one or more processors that trains a tagging model based on the explicitly-labeled training set and the implicitly-labeled training set, and that stores the tagging model in the storage, wherein the logic that trains also maximizes a training objective, wherein the training objective is a function of implicit label information, query information, and state variable information.

2. The training module of claim 1, wherein, for the implicitly-labeled training set, said logic configured to train:

treats the implicit labels as fixing state sequence variables that correspond to the implicit labels; and

treats any state sequence variable for which there is a missing label as a hidden variable.

3. The training module of claim 1, wherein, for the implicitly-labeled training set, said logic that trains:

treats state sequence variables as hidden variables; and

treats the implicit labels as non-binding evidence regarding values of the state sequence variables.

4. The training module of claim 1, wherein said logic configured that trains also maximizes a training objective using an expectation-maximization algorithm.

5. The training module of claim 1, wherein said logic that trains also maximizes a training objective using a Viterbi algorithm.

6. The training module of claim 1, wherein the training objective applies a representation of conditional probability that includes, in part, a soft evidence feature function, wherein the soft evidence feature function expresses an influence of the implicit labels in training the tagging model.

7. The training module of claim 6, wherein the representation of conditional probability includes a weighting parameter that controls an extent of influence of the implicit labels in training the tagging model.

8. A computer readable storage medium storing computer readable instructions, the computer readable instructions providing a training module that when executed by one or more processing devices performs a process comprising:

training a tagging model by optimizing a training objective, wherein the training objective applies a representation of conditional probability that includes, in part, a soft evidence feature function,

the soft evidence feature function expressing an influence of implicit labels on hidden state variables.

9. The computer readable storage medium of claim 8, wherein the conditional probability is expressed by:

10. The computer readable storage medium of claim 9, wherein the soft evidence feature function s(y_t, z_t) equals 0 if z_t =null, 1 if y_t=Z_t, and −

1 otherwise.

11. A method using electronic computing functionality to provide implicit labels for use in training a statistical tagging model, comprising:

identifying, using the electronic computing functionality, items selected by users in association with queries submitted by the users;

identifying, using the electronic computing functionality, schema information associated with the items;

selecting, using the electronic computing functionality, implicit labels associated with the queries, based on the schema information

training a tagging model based, at least in part, on a training set that includes the implicit labels; and

using the tagging model to associate terms of an input query with labels to transform the input query to a structured query.

12. The method of claim 11, wherein said identifying items comprises identifying the items from a store which associates queries made by users with selections made by the users.

13. The method of claim 11, wherein the items correspond to network-accessible pages selected by the users.

14. The method of claim 11, wherein the items are associated with respective products.

15. The method of claim 11, wherein said identifying schema information comprises:

extracting information associated with the items to provide extracted information;

using the extracted information to identify descriptive information associated with the items within a descriptive store; and

providing the schema information based on the descriptive information.

16. The method of claim 15, wherein the extracted information corresponds to titles associated with the items, and wherein said using of the extracted information comprises matching the titles with title information in the descriptive store.

17. The method of claim 15, wherein the descriptive information corresponds to descriptive metadata associated with the items.

18. The method of claim 11, wherein said identifying the schema information comprises:

identifying schema information expressed in a source schema; and

mapping the schema information expressed in the source schema to schema information expressed in a target schema.