RAPID ITERATIVE DEVELOPMENT OF CLASSIFIERS

• US 20100161652A1
• Filed: 12/24/2008
• Published: 06/24/2010
• Est. Priority Date: 12/24/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: BELLARE, Kedar, MERUGU, Srujana, SELVARAJ, Sathiya Keerthi
• Granted Patent: US 8,849,790 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• 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 data framework corresponding to a plurality of instances and a plurality of features, the data framework tangibly embodied in a computer-readable medium;

providing a query space, wherein each of a plurality of queries of the query space comprises a subset of the plurality of instances, a subset of the plurality of features and a relevant characteristic function that describes, for that query, a function of instance-feature values associated with that query and of the 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;

operating a computing device to receive an indication of commentary from at least one editor for each of the plurality of queries of the query space, wherein the commentary for each query being the editor'"'"'s estimate of the true value of the relevant characteristic for that query and storing the estimates in the query space in correspondence with the 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, from the classifier model, relevant characteristic values corresponding to the queries in the query space;

operating a computing device to determine a distortion value for each query 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 plurality of 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 distortion value for each of at least some of the queries is weighted by a relative importance score for that query.

4. The method of claim 1, wherein:

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

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

5. 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.

6. The method of claim 5, wherein:

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

7. The method of claim 1 wherein:

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

8. 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:

a) providing a data framework corresponding to a plurality of instances and a plurality of features, the data framework tangibly embodied in a computer-readable medium;

b) providing a query space, wherein each of a plurality of queries of the query space comprises a subset of the plurality of instances, a subset of the plurality of features and a relevant characteristic function that describes, for that query, a function of instance-feature values associated with that query and of the 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;

c) 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;

d) operating a computing device to provide a query utility function and a stopping criterion function that depend on the plurality of instances and features and the class probabilities associated with the classifier;

e) operating a computing device to provide a stopping criterion threshold value;

f) operating a computing device to initialize the tunable parameter vector and using it to compute class probabilities of the plurality of instances;

g) for each of the plurality of queries, operating a computing device to apply a query utility function to determine a query utility value for that query;

h) operating a computing device to present a subset of the plurality of the queries for editorial commentary, wherein a determination of which of the plurality of queries are in the subset is based at least in part on the query utility values;

i) operating a computing device to receive an indication of editorial commentary from at least one editor for each of at least some of the subset of queries, wherein the commentary for each query of the subset of queries being the editor'"'"'s estimate of the true value of the relevant characteristic for that query and storing the estimates in the query space in correspondence with the queries;

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

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

l) operating a computing device to determine class probabilities of the plurality of instances;

m) operating a computing device to determine a stopping criterion function;

n) repeating g) to m) until the stopping criterion function goes below the stopping criterion threshold value.

9. The method of claim 8, wherein:

the query utility function determines an expected reduction in uncertainty of model predictions over the plurality of instances.

10. The method of claim 9, wherein:

determining the expected reduction in uncertainty of model predictions over the plurality of instances includes considering a response distribution over which expectation is taken, an uncertainty measure, and a test instance set.

11. The method of claim 8, further comprising:

operating a computing device to determine clusters of instance-feature pairs that are homogeneous with respect to dependency of instance class assignments on the instance-feature values; and

operating a computing device to construct a reduced query space based on the determined clusters, wherein the plurality of queries are obtained from the reduced query space.

12. The method of claim 11, further comprising:

operating a computing device to approximate the query utility function using the clusters of instance-feature pairs.

13. A computer program product comprising at least one tangible 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, including to:

provide a data framework corresponding to a plurality of instances and a plurality of features, the data framework tangibly embodied in a computer-readable medium;

provide a query space, wherein each of a plurality of queries of the query space comprises a subset of the plurality of instances, a subset of the plurality of features and a relevant characteristic function that describes, for that query, a function of instance-feature values associated with that query and of the 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;

operate a computing device to receive an indication of commentary from at least one editor for each of the plurality of queries of the query space, wherein the commentary for each query being the editor'"'"'s estimate of the true value of the relevant characteristic for that query and storing the estimates in the query space in correspondence with the 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, from the classifier model, relevant characteristic values corresponding to the queries in the query space;

determine a distortion value for each query 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 plurality of queries for which the editors gave commentary.

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

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

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

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

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

16. The computer program product of claim 13, wherein:

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

17. The computer program product of claim 13 wherein:

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

18. A computer program product comprising at least one tangible 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, including to:

a) provide a data framework corresponding to a plurality of instances and a plurality of features;

b) provide a query space, wherein each of a plurality of queries of the query space comprises a subset of the plurality of instances, a subset of the plurality of features and a relevant characteristic function that describes, for that query, a function of instance-feature values associated with that query and of the 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;

c) maintaining a classifier framework configured to provide class probabilities for the instances according to a tunable parameter vector;

d) providing a query utility function and a stopping criterion function that depend on the plurality of instances and features and the class probabilities associated with the classifier;

e) providing a stopping criterion threshold value;

f) initializing the tunable parameter vector and using it to compute class probabilities of the plurality of instances;

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

h) presenting a subset of the plurality of the queries for editorial commentary, wherein a determination of which of the plurality of queries are in the subset is based at least in part on the query utility values;

i) receiving an indication of editorial commentary from at least one editor for each of at least some of the subset of queries, wherein the commentary for each query of the subset of queries being the editor'"'"'s estimate of the true value of the relevant characteristic for that query and storing the estimates in the query space in correspondence with the queries;

j) determining a distortion value for each query by applying a distortion function to a deviation of the classifier framework response from the indication of editorial commentary for that query;

k) adjusting a tunable parameter vector based on a cost function that considers a regularization component and the distortion values over the plurality of queries for which the editors gave commentary;

l) determining class probabilities of the plurality of instances;

m) determining a stopping criterion function;

n) repeating g) to m) until the stopping criterion function goes below the stopping criterion threshold value.

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

the query utility function determines an expected reduction in uncertainty of model predictions over the plurality of instances.

20. The computer program product of claim 19, wherein:

determining the expected reduction in uncertainty of model predictions over the plurality of instances includes considering a response distribution over which expectation is taken, an uncertainty measure, and a test instance set.

21. The computer program product of claim 18, wherein the computer program instructions are to configure the computing device to further:

determine clusters of instance-feature pairs that are homogeneous with respect to dependency of instance class assignments on the instance-feature values; and

construct a reduced query space based on the determined clusters, wherein the plurality of queries are obtained from the reduced query space.

22. The computer program product of claim 18, wherein the computer program instructions are to configure the computing device to further:

approximate the query utility function using the clusters of instance-feature pairs.