Reliability measure for a classifier

• US 8,024,413 B1
• Filed: 07/14/2009
• Issued: 09/20/2011
• Est. Priority Date: 02/17/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: AOL Inc. (Apollo Global Management, Inc.)
• Inventors: Kolcz, Aleksander
• Primary Examiner(s): Gillis, Brian J
• Application Number:
  US12/502,688
• Time in Patent Office: 798 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 computing a classification threshold for a classifier, the method comprising:

applying a classification model to a data item stored in a memory and having a known classification to produce a first classification score for the data item;

determining a first classification of the data item based on the first classification score;

determining an amount of retraining needed to change the first classification of the data item to a second, different classification;

determining a reliability measure based on the amount of retraining needed to change the first classification of the data item to a second, different classification;

modifying the first classification score based on the reliability measure to compute a second classification score;

computing, using a processor, a threshold value that minimizes misclassification costs based, at least in part, on the second classification score and the known classification; and

setting the classification threshold to the determined threshold value.

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 having the second classification to result in the classifier indicating that the data item has the second classification.

3. The method of claim 1 wherein determining an amount of retraining comprises determining an amount of change to the classification model to result in the classifier indicating that the data item has the second classification.

4. The method of claim 1, further comprising assigning different misclassification costs to different classifications.

5. The method of claim 4, wherein business-related or personal classifications have higher assigned misclassification costs than advertising or promotional classifications.

6. The method of claim 1 wherein the classification model is a Naï

ve Bayes based classification model.

7. The method of claim 1 wherein the data item comprises an e-mail.

8. A non-transitory computer-readable storage medium storing a program for determining a classification threshold for a classifier, the program comprising code for causing a processing device to perform the following operations:

apply a classification model to a data item with a known classification to produce a first classification score for the data item;

determine a first classification of the data item based on the first classification score;

determine an amount of retraining needed to change the first classification of the data item to a second, different classification;

determine a reliability measure based on the amount of retraining needed to change the first classification of the data item to a second, different classification;

modify the first classification score based on the reliability measure to compute a second classification score;

compute a threshold value that minimizes misclassification costs based, at least in part, on the second classification score and the known classification; and

set the classification threshold to the determined threshold value.

9. The medium of claim 8 wherein determining an amount of retraining comprises determining a number of times that the data item needs to be added to training data items having the second classification to result in the classifier indicating that the data item has the second classification.

10. The medium of claim 8 wherein determining an amount of retraining comprises determining an amount of change to the classification model to result in the classifier indicating that the data item has the second classification.

11. The medium of claim 8, further comprising code for causing a processing device to assign different misclassification costs to different classifications.

12. The medium of claim 11, wherein business-related or personal classifications have higher assigned misclassification costs than advertising or promotional classifications.

13. The medium of claim 8 wherein the classification model is a Naï

ve Bayes based classification model.

14. The medium of claim 8 wherein the data item comprises an e-mail.

15. A method for computing a classification threshold for a classifier, the method comprising:

determining a first classification of a data item stored in a memory, wherein the first classification is based on a first classification score;

determining an amount of retraining needed to change the first classification of the data item to a second, different classification;

determining a reliability measure based on the amount of retraining needed to change the first classification of the data item to a second, different classification;

modifying the first classification score based on the reliability measure to compute a second classification score;

computing, using a processor, a threshold value that minimizes misclassification costs based, at least in part, on the second classification score and a known classification; and

setting the classification threshold to the determined threshold value.

16. The method of claim 15 further comprising determining the amount of retraining by determining a number of times that the data item needs to be added to training data items having the second classification to result in the classifier indicating that the data item has the second classification.

17. The method of claim 15 further comprising determining the amount of retraining by determining an amount of change to a classification model to result in the classifier indicating that the data item has the second classification.

18. The method of claim 15, further comprising assigning different misclassification costs to different classifications.

19. The method of claim 18, wherein business-related or personal classifications have higher assigned misclassification costs than advertising or promotional classifications.

20. The method of claim 15 wherein the first classification score is computed according to a Naï

ve Bayes based classification model.

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