US6161130A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Technique which utilizes a probabilistic classifier to detect "junk" e-mail by automatically updating a training and re-training the classifier based on the updated training set
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-06-23
•
Granted: 2000-12-12
•
Expires: 2018-06-23
Abstract
Abstract A technique, specifically a method and apparatus that implements the method, which through a probabilistic classifier (370) and, for a given recipient, detects electronic mail (e-mail) messages, in an incoming message stream, which that recipient is likely to consider "junk". Specifically, the invention discriminates message content for that recipient, through a probabilistic classifier (e.g., a support vector machine) trained on prior content classifications. Through a resulting quantitative probability measure, i.e., an output confidence level, produced by the classifier for each message and subsequently compared against a predefined threshold, that message is classified as either, e.g., spam or legitimate mail, and, e.g., then stored in a corresponding folder (223, 227) for subsequent retrieval by and display to the recipient. Based on the probability measure, the message can alternatively be classified into one of a number of different folders, depicted in a pre-defined visually distinctive manner or simply discarded in its entirety.
Inventors
- 👤 Eric Horvitz
- 👤 David E. Heckerman
- 👤 Susan T. Dumais
- 👤 Mehran Sahami
- 👤 John C. Platt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 07:06
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/10; G06Q10/107; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/353; G06F18/00; G06F18/20; G06F18/24; G06F18/241; G06F18/2411; H; H04; H04L; H04L51/00; H04L51/21; H04L51/212; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 67
Claim 1
Independent Claim
242 words
A method of classifying an incoming electronic message, as a function of content of the message, into one of a plurality of predefined classes, the method comprising the steps of: determining whether each one of a pre-defined set of N features (where N is a predefined integer) is present in the incoming message so as to yield feature data associated with the message; applying the feature data to a probabilistic classifier so as to yield an output confidence level for the incoming message which specifies a probability that the incoming message belongs to said one class, wherein the classifier has been trained, on past classifications of message content for a plurality of messages that form a training set and belong to said one class, to recognize said N features in the training set; classifying, in response to a magnitude of the output confidence level, the incoming message as a member of said one class of messages; automatically updating the training set to include classification of message content for an incoming message which has been classified by a user in another one of the predefined classes other than said one class specified by the classifier so as to form an updated training set; and automatically re-training the classifier based on the updated training set so as to adapt the operation of the classifier to changes in either message content that affect message classification or in user perceptions of the content of incoming messages.
Claim 2
Independent Claim
242 words
A method of classifying an incoming electronic message, as a function of content of the message, into one of a plurality of predefined classes, the method comprising the steps of: determining whether each one of a pre-defined set of N features (where N is a predefined integer) is present in the incoming message so as to yield feature data associated with the message; applying the feature data to a probabilistic classifier so as to yield an output confidence level for the incoming message which specifies a probability that the incoming message belongs to said one class, wherein the classifier has been trained, on past classifications of message content for a plurality of messages that form a training set and belong to said one class, to recognize said N features in the training set; classifying, in response to a magnitude of the output confidence level, the incoming message as a member of said one class of messages; automatically updating the training set to include classification of message content for an incoming message which has been classified by a user in another one of the predefined classes other than said one class specified by the classifier so as to form an updated training set; and automatically re-training the classifier based on the updated training set so as to adapt the operation of the classifier to changes in either message content that affect message classification or in user perceptions of the content of incoming messages.
Claim 3
Dependent Claim
22 words
The method in claim 1 wherein the classes comprise first and second classes for first and second predefined categories of messages, respectively.
Claim 4
Dependent Claim
22 words
The method in claim 2 wherein the classes comprise a plurality of sub-classes and said one class is one of said sub-classes.
Claim 5
Dependent Claim
69 words
The method in claim 2 further comprising the steps of: comparing the output confidence level for the incoming message to a predefined probabilistic threshold value so as to yield a comparison result; and distinguishing said incoming message, in a predefined manner associated with the first class, from messages associated with the second class if the comparison result indicates that the output confidence level equals or exceeds the threshold level.
Claim 6
Dependent Claim
39 words
The method in claim 3 wherein the predefined manner comprises storing the first and second classes of messages in separate corresponding folders, or providing a predefined visual indication that said incoming message is a member of the first class.
Claim 7
Dependent Claim
22 words
The method in claim 5 wherein said indication is a predefined color coding of all or a portion of the incoming message.
Claim 8
Dependent Claim
28 words
The method in claim 6 wherein a color of said color coding varies with the confidence level that the incoming message is a member of the first class.
Claim 9
Dependent Claim
153 words
The method in claim 4 further comprising the steps of: detecting whether each of a first group of predefined handcrafted features exists in the incoming message so as to yield first output data; analyzing text in the incoming message so as to break the text into a plurality of constituent tokens; ascertaining, using a word-oriented indexer and in response to said tokens, whether each of a second group of predefined word-oriented features exists in the incoming message so as to yield second output data, said first and second groups collectively defining an n-element feature space (where n is an integer greater than N); forming, in response to the first and second output data, an N-element feature vector which specifies whether each of said N features exists in the incoming message; and applying the feature vector as input to the probabilistic classifier so as to yield the output confidence level for the incoming message.
Claim 10
Dependent Claim
15 words
The method in claim 8 wherein the feature space comprises both word-based and handcrafted features.
Claim 11
Dependent Claim
22 words
The method in claim 8 wherein the classes comprise a plurality of sub-classes and said one class is one of said sub-classes.
Claim 12
Dependent Claim
26 words
The method in claim 8 wherein the message is an electronic mail (e-mail) message and said first and second classes are non-legitimate and legitimate messages, respectively.
Claim 13
Dependent Claim
30 words
The method in claim 9 wherein the handcrafted features comprise features correspondingly related to formatting, authoring, delivery or communication attributes that characterize a message as belonging to the first class.
Claim 14
Dependent Claim
38 words
The method in claim 12 wherein the formatting attributes comprises whether a predefined word in the text of the incoming message is capitalized, or whether the text of the incoming message contains a series of predefined punctuation marks.
Claim 15
Dependent Claim
37 words
The method in claim 12 wherein the delivery attributes comprise whether the incoming message contains an address of a single recipient or addresses of plurality of recipients, or a time at which the incoming message was transmitted.
Claim 16
Dependent Claim
44 words
The method in claim 12 wherein the authoring attributes comprise whether the incoming message contains an address of a single recipient, or contains addresses of plurality of recipients or contains no sender at all, or a time at which the incoming message was transmitted.
Claim 17
Dependent Claim
28 words
The method in claim 12 wherein the communication attributes comprise whether the incoming message has an attachment, or whether the message was sent from a predefined domain type.
Claim 18
Dependent Claim
38 words
The method in claim 8 wherein the probabilistic classifier comprises a Naive Bayesian classifier, a limited dependence Bayesian classifier, a Bayesian network classifier, a decision tree, a support vector machine, or is implemented through use of content matching.
Claim 19
Dependent Claim
56 words
The method in claim 17 wherein: the feature data applying step comprises the step of yielding the output confidence level for said incoming message through a support vector machine; and the comparing step comprises the step of thresholding the output confidence level through a predefined sigmoid function to produce the comparison result for the incoming message.
Claim 20
Dependent Claim
142 words
The method in claim 4 further comprises a training phase having the steps of: detecting whether each one of a plurality of predetermined features exists in each message of a training set of m messages belonging to the first class so as to yield a feature matrix containing feature data for all of the training messages, wherein the plurality of predetermined features defines a predefined n-element feature space and each of the training messages has been previously classified as belonging to the first class; reducing the feature matrix in size to yield a reduced feature matrix having said N features (where n, N and m are integers with n>N); and applying the reduced feature matrix and the known classifications of each of said training messages to the classifier and training the classifier to recognize the N features in the m-message training set.
Claim 21
Dependent Claim
22 words
The method in claim 19 wherein said indication is a predefined color coding of all or a portion of the incoming message.
Claim 22
Dependent Claim
28 words
The method in claim 20 wherein a color of said color coding varies with the confidence level that the incoming message is a member of the first class.
Claim 23
Dependent Claim
20 words
The method of claim 19 further comprising the step of utilizing messages in the first class as the training set.
Claim 24
Dependent Claim
102 words
The method in claim 19 wherein the reducing step comprises the steps of: eliminating all features from the feature matrix, that occur less than a predefined amount in the training set, so as to yield a partially reduced feature matrix; determining a mutual information measure for all remaining features in the partially reduced feature matrix; selecting, from all the remaining features in the partially reduced matrix, the N features that have highest corresponding quantitative mutual information measures; and forming the reduced feature matrix containing an associated data value for each of the N features and for each of the m training messages.
Claim 25
Dependent Claim
15 words
The method in claim 19 wherein the feature space comprises both word-oriented and handcrafted features.
Claim 26
Dependent Claim
22 words
The method in claim 19 wherein the classes comprise a plurality of sub-classes and said one class is one of said sub-classes.
Claim 27
Dependent Claim
26 words
The method in claim 24 wherein the message is an electronic mail (e-mail) message and said first and second classes are non-legitimate and legitimate messages, respectively.
Claim 28
Dependent Claim
31 words
The method in claim 26 wherein the handcrafted features comprise features correspondingly related to formatting, authoring, delivery or communication attributes that characterize an e-mail message as belonging to the first class.
Claim 29
Dependent Claim
38 words
The method in claim 27 wherein the formatting attributes comprises whether a predefined word in the text of the incoming message is capitalized, or whether the text of the incoming message contains a series of predefined punctuation marks.
Claim 30
Dependent Claim
37 words
The method in claim 27 wherein the delivery attributes comprise whether the incoming message contains an address of a single recipient or addresses of plurality of recipients, or a time at which the incoming message was transmitted.
Claim 31
Dependent Claim
44 words
The method in claim 27 wherein the authoring attributes comprise whether the incoming message contains an address of a single recipient, or contains addresses of plurality of recipients or contains no sender at all, or a time at which the incoming message was transmitted.
Claim 32
Dependent Claim
28 words
The method in claim 27 wherein the communication attributes comprise whether the incoming message has an attachment, or whether the message was sent from a predefined domain type.
Claim 33
Dependent Claim
27 words
The method in claim 8 further comprising the step of updating, from a remote server, the probabilistic classifier and definitions of features associated with the first class.
Claim 34
Dependent Claim
17 words
A computer readable medium having computer executable instructions stored therein for performing the steps of claim 1.
Claim 35
Dependent Claim
257 words
Apparatus for classifying an incoming electronic message, as a function of content of the message, into one of a plurality of predefined classes, the apparatus comprising: a processor; a memory having computer executable instructions stored therein; wherein, in response to the stored instructions, the processor: determines whether each one of a pre-defined se. of N features (where N is a predefined integer) is present in the incoming message so as to yield feature data associated with the message; applies the feature data to a probabilistic classifier so as to yield an output confidence level for the incoming message which specifies a probability that the incoming message belongs to said one class, wherein the classifier has been trained, on past classifications of message content for a plurality of messages that form a training set and belong to said one class, to recognize said N features in the training set; classifies, in response to a magnitude of the output confidence level, the incoming message as a member of said one class of messages; automatically updates the training set to include classification of message content for an incoming message which has been classified by a user in another one of the predefined classes other than said one class specified by the classifier so as to form an updated training set; and automatically re-trains the classifier based on the updated training set so as to adapt the operation of the classifier to changes in either message content that affect message classification or in user perceptions of the content of incoming messages.
Claim 36
Dependent Claim
257 words
Apparatus for classifying an incoming electronic message, as a function of content of the message, into one of a plurality of predefined classes, the apparatus comprising: a processor; a memory having computer executable instructions stored therein; wherein, in response to the stored instructions, the processor: determines whether each one of a pre-defined se. of N features (where N is a predefined integer) is present in the incoming message so as to yield feature data associated with the message; applies the feature data to a probabilistic classifier so as to yield an output confidence level for the incoming message which specifies a probability that the incoming message belongs to said one class, wherein the classifier has been trained, on past classifications of message content for a plurality of messages that form a training set and belong to said one class, to recognize said N features in the training set; classifies, in response to a magnitude of the output confidence level, the incoming message as a member of said one class of messages; automatically updates the training set to include classification of message content for an incoming message which has been classified by a user in another one of the predefined classes other than said one class specified by the classifier so as to form an updated training set; and automatically re-trains the classifier based on the updated training set so as to adapt the operation of the classifier to changes in either message content that affect message classification or in user perceptions of the content of incoming messages.
Claim 37
Dependent Claim
22 words
The apparatus in claim 34 wherein the classes comprise first and second classes for first and second predefined categories of messages, respectively.
Claim 38
Dependent Claim
22 words
The apparatus in claim 35 wherein the classes comprise a plurality of sub-classes and said one class is one of said sub-classes.
Claim 39
Dependent Claim
73 words
The apparatus in claim 35 wherein the processor, in response to the stored instructions: compares the output confidence level for the incoming message to a predefined probabilistic threshold value so as to yield a comparison result; and distinguishes said incoming message, in a predefined manner associated with the first class, from messages associated with the second class if the comparison result indicates that the output confidence level equals or exceeds the threshold level.
Claim 40
Dependent Claim
48 words
The apparatus in claim 36 wherein the processor, in response to the stored instructions, implements the predefined manner by storing the first and second classes of messages in separate corresponding folders, or providing a predefined visual indication that said incoming message is a member of the first class.
Claim 41
Dependent Claim
22 words
The apparatus in claim 38 wherein said indication is a predefined color coding of all or a portion of the incoming message.
Claim 42
Dependent Claim
28 words
The apparatus in claim 39 wherein a color of said color coding varies with the confidence level that the incoming message is a member of the first class.
Claim 43
Dependent Claim
157 words
The apparatus in claim 37 wherein the processor, in response to the stored instructions: detects whether each of a first group of predefined handcrafted features exists in the incoming message so as to yield first output data; analyzes text in the incoming message so as to break the text into a plurality of constituent tokens; ascertains, using a word-oriented indexer and in response to said tokens, whether each of a second group of predefined word-oriented features exists in the incoming message so as to yield second output data, said first and second groups collectively defining an n-element feature space (where n is an integer greater than N); forms, in response to the first and second output data, an N-element feature vector which specifies whether each of said N features exists in the incoming message; and applies the feature vector as input to the probabilistic classifier so as to yield the output confidence level for the incoming message.
Claim 44
Dependent Claim
15 words
The apparatus in claim 41 wherein the feature space comprises both word-based and handcrafted features.
Claim 45
Dependent Claim
22 words
The apparatus in claim 41 wherein the classes comprise a plurality of sub-classes and said one class is one of said sub-classes.
Claim 46
Dependent Claim
26 words
The apparatus in claim 41 wherein the message is an electronic mail (e-mail) message and said first and second classes are non-legitimate and legitimate messages, respectively.
Claim 47
Dependent Claim
30 words
The apparatus in claim 42 wherein the handcrafted features comprise features correspondingly related to formatting, authoring, delivery or communication attributes that characterize a message as belonging to the first class.
Claim 48
Dependent Claim
38 words
The apparatus in claim 45 wherein the formatting attributes comprises whether a predefined word in the text of the incoming message is capitalized, or whether the text of the incoming message contains a series of predefined punctuation marks.
Claim 49
Dependent Claim
37 words
The apparatus in claim 45 wherein the delivery attributes comprise whether the incoming message contains an address of a single recipient or addresses of plurality of recipients, or a time at which the incoming message was transmitted.
Claim 50
Dependent Claim
44 words
The apparatus in claim 45 wherein the authoring attributes comprise whether the incoming message contains an address of a single recipient, or contains addresses of plurality of recipients or contains no sender at all, or a time at which the incoming message was transmitted.
Claim 51
Dependent Claim
28 words
The apparatus in claim 45 wherein the communication attributes comprise whether the incoming message has an attachment, or whether the message was sent from a predefined domain type.
Claim 52
Dependent Claim
38 words
The apparatus in claim 41 wherein the probabilistic classifier comprises a Naive Bayesian classifier, a limited dependence Bayesian classifier, a Bayesian network classifier, a decision tree, a support vector machine, or is implemented through use of content matching.
Claim 53
Dependent Claim
48 words
The apparatus in claim 50 wherein the processor, in response to the stored instructions: yields the output confidence level for said incoming message through a support vector machine; and thresholds the output confidence level through a predefined sigmoid function to produce the comparison result for the incoming message.
Claim 54
Dependent Claim
147 words
The apparatus in claim 37 further comprises a training phase wherein the processor, in response to the stored instructions: detects whether each one of a plurality of predetermined features exists in each message of a training set of m messages belonging to the first class so as to yield a feature matrix containing feature data for all of the training messages, wherein the plurality of predetermined features defines a predefined n-element feature space and each of the training messages has been previously classified as belonging to the first class; reduces the feature matrix in size to yield a reduced feature matrix having said N features (where n, N and m are integers with n>N); and applies the reduced feature matrix and the known classifications of each of said training messages to the classifier and training the classifier to recognize the N features in the m-message training set.
Claim 55
Dependent Claim
22 words
The apparatus in claim 52 wherein said indication is a predefined color coding of all or a portion of the incoming message.
Claim 56
Dependent Claim
28 words
The apparatus in claim 53 wherein a color of said color coding varies with the confidence level that the incoming message is a member of the first class.
Claim 57
Dependent Claim
25 words
The apparatus of claim 52 further wherein the processor, in response to the stored instructions, utilizes messages in the first class as the training set.
Claim 58
Dependent Claim
103 words
The apparatus in claim 52 wherein the processor, in response to the stored instructions: eliminates all features from the feature matrix, that occur less than a predefined amount in the training set, so as to yield a partially reduced feature matrix; determines a mutual information measure for all remaining features in the partially reduced feature matrix; selects, from all the remaining features in the partially reduced matrix, the N features that have highest corresponding quantitative mutual information measures; and forms the reduced feature matrix containing an associated data value for each of the N features and for each of the m training messages.
Claim 59
Dependent Claim
15 words
The apparatus in claim 52 wherein the feature space comprises both word-oriented and handcrafted features.
Claim 60
Dependent Claim
22 words
The apparatus in claim 52 wherein the classes comprise a plurality of sub-classes and said one class is one of said sub-classes.
Claim 61
Dependent Claim
26 words
The apparatus in claim 57 wherein the message is an electronic mail (e-mail) message and said first and second classes are non-legitimate and legitimate messages, respectively.
Claim 62
Dependent Claim
31 words
The apparatus in claim 59 wherein the handcrafted features comprise features correspondingly related to formatting, authoring, delivery or communication attributes that characterize an e-mail message as belonging to the first class.
Claim 63
Dependent Claim
38 words
The apparatus in claim 60 wherein the formatting attributes comprises whether a predefined word in the text of the incoming message is capitalized, or whether the text of the incoming message contains a series of predefined punctuation marks.
Claim 64
Dependent Claim
37 words
The apparatus in claim 60 wherein the delivery attributes comprise whether the incoming message contains an address of a single recipient or addresses of plurality of recipients, or a time at which the incoming message was transmitted.
Claim 65
Dependent Claim
44 words
The apparatus in claim 60 wherein the authoring attributes comprise whether the incoming message contains an address of a single recipient, or contains addresses of plurality of recipients or contains no sender at all, or a time at which the incoming message was transmitted.
Claim 66
Dependent Claim
28 words
The apparatus in claim 60 wherein the communication attributes comprise whether the incoming message has an attachment, or whether the message was sent from a predefined domain type.
Claim 67
Dependent Claim
31 words
The apparatus in claim 41 wherein the processor, in response to the stored instructions, updates, from a remote server, the probabilistic classifier and definitions of features associated with the first class.
References Cited (Backward Citations)
EP0413537A2
Cited
US5377354A
Cited
US5835087A
Cited
EP0720333A2
Cited
US5619648A
Cited
US5638487A
Cited
WO1996035994A1
Cited
US6003027A
Cited
US6023723A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-12 | 2004-06-12 | 2004-12-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-12 | 2008-06-12 | 2008-12-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-12 | 2012-06-12 | 2012-12-12 | $7700.00 | Window Closed / Lapsed |