Rapid iterative development of classifiers

• US 8,849,790 B2
• Filed: 12/24/2008
• Issued: 09/30/2014
• Est. Priority Date: 12/24/2008
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Merugu, Srujana, Selvaraj, Sathiya Keerthi, Bellare, Kedar
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): BROMELL, ALEXANDRIA Y
• Application Number:
  US12/344,132
• Publication Number:
  US 20100161652A1
• Time in Patent Office: 2,106 Days
• Field of Search: 707/707, 707/708, 707/731, 707/737, 706/45
• US Class Current: 707/708
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

A classifier development process seamlessly and intelligently integrates different forms of human feedback on instances and features into the data preparation, learning and evaluation stages. A query utility based active learning approach is applicable to different types of editorial feedback. A bi-clustering based technique may be used to further speed up the active learning process.

Claims

1. A computer-implemented method of training a classifier, such that the trained classifier is configured to map an instance to one of a plurality of classes, comprising:

providing a query space, wherein each of a plurality of queries of the query space is associated with a subset of a plurality of instances and a subset of a plurality of features, where each of the plurality of queries of the query space includes a relevant characteristic function that describes, for that query, a function of instance-feature values associated with that query and of instance-class probabilities associated with that query, wherein the instance-class probabilities are an indication of a probabilistic model of mapping of the instances associated with the query to at least one of the plurality of classes, the query space tangibly embodied in a computer-readable medium;

for each of the plurality of queries, applying a query utility function to determine a query utility value for that query;

based, at least in part, upon the query utility value determined for each of the plurality of queries, identifying one or more queries of the plurality of queries to be presented for editorial feedback;

operating a computing device to present the identified queries and receive an indication of commentary from at least one editor for each of the identified one or more queries of the plurality of queries;

maintaining a classifier framework tangibly embodied in a computer-readable medium, the classifier framework configured to provide class probabilities for the instances according to a tunable parameter vector;

operating a computing device to determine a distortion value for the identified queries by applying a distortion function to a deviation of the classifier framework response from the indication of editorial commentary for that query; and

operating a computing device to adjust the tunable parameter vector based on a cost function that considers a regularization component and the distortion values over the queries for which the editors gave commentary.

2. The method of claim 1, wherein:

for at least some, but not all, of the plurality of queries, at least one of the subset of instances and the subset of features is a null set.

3. The method of claim 1, wherein:

the commentary includes, for each of at least some of the queries, a relative importance score for the query, the relative importance score indicating a relative importance of the query; and

the distortion value for each of at least some of the queries is weighted by the relative importance score for that query.

4. The method of claim 1, wherein:

the distortion function for at least some of the queries is different from the distortion functions for other queries.

5. The method of claim 4, wherein:

the distortion function associated with a query is determined by the choice of relevant characteristic function made for the query.

6. The method of claim 1 wherein:

the distortion value for each of at least some of the queries is weighted by a relative importance score for that query; and

the relative importance score of a query is the same for all queries which share the same relevant characteristic function.

7. The method of claim 1, wherein the query utility value comprises an expected reduction in uncertainty of model predictions over the plurality of instances.

8. The method of claim 7, wherein applying the query utility function comprises determining an expected reduction in uncertainty of model predictions over the plurality of instances.

9. The computer-implemented method of claim 1, wherein the commentary for each identified query being the editor'"'"'s estimate of a value of the relevant characteristic function for that query.

10. The computer-implemented method of claim 1, wherein the plurality of queries are unanswered queries.

11. The computer-implemented method of claim 1, wherein at least one of the identified queries requests an indication of a class purity of the corresponding subset of instances or relevance of specific features to classification.

12. The computer-implemented method of claim 1, wherein each of the plurality of queries is designed for presentation to at least one editor for editorial commentary.

13. The computer-implemented method of claim 1, wherein the indication of commentary indicates an answer to the corresponding one of the identified queries.

14. A computer program product comprising at least one non-transitory computer readable medium having computer program instructions tangibly embodied thereon, the computer program instructions to configure at least one computing device to train a classifier such that the trained classifier is configured to map an instance to one of a plurality of classes, the computer program instructions, when executed by a processor, causing the processor to perform steps, comprising:

determining, from a plurality of instances that each have corresponding features of a plurality of features, clusters of instances that are homogeneous with respect to dependency of instance class assignments on the instance-feature values;

constructing a reduced query space from a query space based on the determined clusters, the query space including a plurality of queries, each of the plurality of queries being associated with a subset of the plurality of instances and a subset of the plurality of features, wherein the reduced query space includes a second plurality of queries, the second plurality of queries including a subset of the plurality of queries;

approximating a query utility function using the determined clusters;

for each of the second plurality of queries, applying the query utility function to determine a query utility value for that query;

based, at least in part, upon the query utility value determined for each of the second plurality of queries, identifying one or more queries of the second plurality of queries to be presented for editorial feedback;

operate a computing device to present the identified queries and receive an indication of commentary from at least one editor for each of the identified queries;

maintain a classifier framework tangibly embodied in a computer-readable medium, the classifier framework configured to provide class probabilities for the instances according to a tunable parameter vector;

determine a distortion value for each of the identified queries by applying a distortion function to a deviation of the classifier framework response from the indication of editorial commentary for that query; and

adjust the tunable parameter vector based on a cost function that considers a regularization component and the distortion values over the queries for which the editors gave commentary.

15. The computer program product of claim 14, wherein:

the distortion value for each of at least some of the queries is weighted by a relative importance score for that query.

16. The computer program product of claim 15 wherein:

the relative importance score of a query is the same for all queries which share the same relevant characteristic function.

17. The computer program product of claim 14, wherein:

the commentary includes, for each of at least some of the queries, a relative importance score for the query indicating a relative importance of the query;

wherein the distortion value for at least some of the queries is weighted by the relative importance score for that query.

18. The computer program product of claim 14, wherein:

the distortion function associated with a query is determined by the choice of relevant characteristic function made for the query.

19. The computer program product of claim 14, the commentary for each identified query being the editor'"'"'s estimate of the true value of a relevant characteristic function for that query.

20. The computer program product of claim 14, wherein applying the utility function is not performed for queries in the plurality of queries that are not in the second plurality of queries.

21. The computer program product of claim 14, wherein approximating the utility function is further performed using a set of test instances, wherein the set of test instances includes at least one of:

an instance in the plurality of instances or an instance that is not in the plurality of instances.

22. The computer program product of claim 14, where each of the plurality of queries of the query space comprises a relevant characteristic function that describes, for that query, a function of instance-feature values associated with that query and of instance-class probabilities associated with that query, wherein the instance-class probabilities are an indication of a probabilistic model of mapping of the instances associated with the query to at least one of the plurality of classes.

23. A computer program product comprising at least one non-transitory computer readable medium having computer program instructions tangibly embodied thereon, the computer program instructions to configure at least one computing device to train a classifier such that the trained classifier is configured to map an instance to one of a plurality of classes, the computer program instructions, when executed by a processor, causing the processor to perform steps, comprising:

providing a query space, wherein each of a plurality of queries of the query space pertains to a subset of a plurality of instances and a subset of a plurality of features, and wherein each of the plurality of queries of the query space includes a relevant characteristic function that describes, for that query, a function of instance-feature values associated with that query and of instance-class probabilities associated with that query, wherein the instance-class probabilities are an indication of a probabilistic model of mapping of the instances associated with the query to at least one of the plurality of classes, the query space tangibly embodied in a computer-readable medium;

for each of the plurality of queries, applying a query utility function to determine a query utility value for that query;

based, at least in part, upon the query utility value determined for each of the plurality of queries, identifying one or more queries of the plurality of queries to be presented for editorial feedback;

operating a computing device to present the identified queries and receive an indication of commentary from at least one editor for each of the identified one or more queries of the plurality of queries;

maintaining a classifier framework tangibly embodied in a computer-readable medium, the classifier framework configured to provide class probabilities for the instances according to a tunable parameter vector;

operating a computing device to determine a distortion value for the identified queries by applying a distortion function to a deviation of the classifier framework response from the indication of editorial commentary for that query; and

operating a computing device to adjust the tunable parameter vector based on a cost function that considers a regularization component and the distortion values over the queries for which the editors gave commentary.