Reliability measure for a classifier

• US 7,577,709 B1
• Filed: 02/17/2006
• Issued: 08/18/2009
• Est. Priority Date: 02/17/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: AOL LLC (Apollo Global Management, Inc.)
• Inventors: Kolcz, Aleksander
• Primary Examiner(s): Donaghue, Larry D
• Assistant Examiner(s): Gillis, Brian J
• Application Number:
  US11/356,322
• Time in Patent Office: 1,278 Days
• Field of Search: 709/206, 709/224, 706/14, 706/20, 706/25
• US Class Current: 709/206
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06F 18/24155 Bayesian classification
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

In one aspect, a data item is input into a scoring classifier such that the scoring classifier indicates that the data item belongs to a first class. A determination is made as to the amount of retraining of the scoring classifier, based on the data item, that is required to cause the scoring classifier to indicate that the data item belongs to a second class. A reliability measure is determined based on the required amount of retraining and a class of the data item is determined based, at least in part, on the reliability measure.

Claims

1. A method for determining a class for at least one data item, the method comprising:

inputting a data item into a scoring classifier such that the scoring classifier indicates that the data item belongs to a first class;

determining an amount of retraining of the scoring classifier that is required to cause the scoring classifier to indicate that the data item belongs to a second class that is different from the first class;

determining a reliability measure based on the required amount of retraining; and

determining a class of the data item based, at least in part, on the reliability measure.

2. The method of claim 1 wherein determining an amount of retraining comprises determining a number of times that the data item needs to be added to training data items belonging to the second class to result in the scoring classifier indicating that the data item belongs to the second class.

3. The method of claim 1 wherein the scoring classifier indicates the data item belongs to the first class by producing a classification score that indicates that the data item belongs to the first class, the method further comprising modifying the classification score based on the reliability measure to produce a classification output.

4. The method of claim 3 wherein determining a class of the data item based on the reliability measure comprises comparing the classification output to a classification threshold.

5. The method of claim 1 wherein determining the reliability measure based on the required amount of retraining comprises:

determining a new probability distribution of features for the second class based on the required amount of retraining; and

measuring a difference between an original probability distribution of features for the second class and the new probability distribution of features for the second class.

6. The method of claim 5 wherein the scoring classifier indicates that the item belongs to the first class by producing a classification score that indicates that the data item belongs to the first class, the method further comprising obtaining a classification output by modifying the classification score based on the measured difference between the original probability distribution of features for the second class and the new probability distribution of features for the second class.

7. The method of claim 6 wherein:

measuring the difference between the original probability distribution of features for the second class and the new probability distribution of features for the second class comprises determining the Kullback-Leibler (KL) divergence between the original probability distribution of features for the second class and the new probability distribution of features for the second class; and

modifying the classification score based on the measured difference between the original probability distribution of features for the second class and the new probability distribution of features for the second class comprises modifying the first classification score based on the determined KL divergence.

8. The method of claim 6 wherein determining a class of the data item based on the reliability measure comprises comparing the classification output to a classification threshold.

9. The method of claim 1 wherein the scoring classifier comprises a Naï

ve Bayes based classifier.

10. A computer-readable storage medium storing a program for determining a class for at least one data item, the program comprising code for causing a processing device to perform the following operations:

input a data item into a scoring classifier such that the scoring classifier indicates that the data item belongs to a first class;

determine an amount of retraining of the scoring classifier that is required to cause the scoring classifier to indicate that the data item belongs to a second class that is different from the first class;

determining a reliability measure based on the required amount of retraining; and

determining a class of the data item based, at least in part, on the reliability measure.

11. The medium of claim 10 wherein, to determine an amount of retraining, the program further comprises code for causing the processing device to determine a number of times that the data item needs to be added to training data items belonging to the second class to result in the scoring classifier indicating that the data item belongs to the second class.

12. The medium of claim 10 wherein the scoring classifier indicates the data item belongs to the first class by producing a classification score that indicates that the data item belongs to the first class, the program further comprises code for causing the processing device to modify the classification score based on the reliability measure to produce a classification output.

13. The medium of claim 12 wherein, to determine a of the data item based on the reliability measure, the program further comprises code for causing the processing device to compare the classification output to a classification threshold.

14. The medium of claim 10 wherein, to determine the reliability measure based on the required amount of retraining, the program further comprises code for causing the processing device to:

determine a new probability distribution of features for the second class based on the required amount of retraining; and

measure a difference between an original probability distribution of features for the second class and the new probability distribution of features for the second class.

15. The medium of claim 14 wherein the scoring classifier indicates that the data item belongs to the first class by producing a classification score that indicates that the data item belongs to the first class, the program further comprising code for causing the processing device to obtain a classification output by modifying the classification score based on the measured difference between the original probability distribution of features for the second class and the new probability distribution of features for the second class.

16. The medium of claim 15 wherein:

to measure the difference between the original probability distribution of features for the second class and the new probability distribution of features for the second class, the program further comprises code for causing the processing device to determine the Kullback-Leibler (KL) divergence between the original probability distribution of features for the second class and the new probability distribution of features for the second class; and

to modify the classification score based on the measured difference between the original probability distribution of features for the second class and the new probability distribution of features for the second class, the program further comprises code for causing the processing device to modify the first classification score based on the determined KL divergence.

17. The medium of claim 15 wherein, to determine a class of the data item based on the reliability measure, the program further comprises code for causing the processing device to compare the classification output to a classification threshold.

18. The medium of claim 10 wherein the scoring classifier comprises a Naï

ve Bayes based classifier.

19. A method for determining a class for a data item, the method comprising:

developing a classification model based on a set of training data items, the set of training data items including a first group of training data items having a first class and a second group of training data items having a second class different from the first class;

applying the classification model to a data item to produce a first classification score for the data item, the first classification score indicating that the data item belongs to the first class;

determining a number of times the data item would need to be added to the second group of training data items to create a modified set of training data items such that, if the classification model was developed with the modified set of training data items, applying the classification model to the data item would produce a second classification score that indicates the data item belongs to the second class;

determining a reliability measure based on the number of times the data item would need to be added to the second group of data items to create the modified training set of data items;

modifying the first classification score based on the reliability measure to produce a classification output; and

comparing the classification output to a classification threshold to determine whether the data item belongs to the first class or the second class.

20. The method of claim 19 wherein the classification model is a Naï

ve Bayes based classification model.

21. The method of claim 19 wherein the data item comprises an e-mail.

22. A method for determining a class for at least one data item, the method comprising:

inputting a data item into a scoring classifier such that the scoring classifier indicates that the data item belongs to a first class;

determining an amount of retraining of the scoring classifier based on the data item that is required to cause the scoring classifier to indicate that the data item belongs to a second class;

determining a reliability measure based on the required amount of retraining; and

determining a class of the data item based, at least in part, on the reliability measure, wherein determining the reliability measure based on the required amount of retraining comprises;

determining a new probability distribution of features for the second class based on the required amount of retraining; and

measuring a difference between an original probability distribution of features for the second class and the new probability distribution of features for the second class.

23. The method of claim 22, wherein the first class and the second class are the same class.