Systems and methods of applying semantic features for machine learning of message categories

A method of assigning categories to electronic messages is performed at a computing device having one or more processors and memory. The method includes receiving an electronic message and extracting one or more syntactic pairs of words from content of the electronic message. At least one of syntactic pairs includes a verb in a first sentence and an object in the same sentence, where the verb operates on the object. The method forms a feature vector based on the extracted syntactic pairs and uses the feature vector as input to a classifier. The classifier is trained on a set of training feature vectors, and each training feature vector is associated with a respective category. The method assigns a first category to the electronic message based on output of the classifier and displays the message in a group with other messages associated with the first category.

TECHNICAL FIELD

The disclosure relates generally to categorizing electronic messages, and more specifically to categorizing electronic messages using semantic features of message content.

BACKGROUND

Electronic messaging, such as through email, is a powerful communication tool for the dissemination of information. However, the ease of sending messages can result in a recipient receiving large numbers of messages in a single day. This is because, in addition to messages sent by actual people, a recipient may receive messages generated by machines from third party services such as airlines, invitation generating companies, courier services, and social media sites. These messages may include confirmations, notifications, promotions, social media updates, and messages from collaboration systems.

The classification of messages into message categories helps recipients to parse through all of these messages. For example, having messages classified into just a few basic categories (e.g., promotions, social, updates, and forums) greatly assists a recipient in determining which messages to review, and allows the recipient to review message that are of a similar type at the same time (e.g., all personal messages at the same time, all promotional messages at the same time, etc.). Moreover, such classification helps to put similar messages in the same place, for ease of comparison. Message classification provides a more efficient, productive environment for recipients.

Classification using sets of rules can be effective for many messages, but certain messages are not well suited for rules-based classification. Some automated classifiers, such as neural networks, can be trained to categorize messages based on words, but categorization based on a list of words is imperfect as well. For example, in some instances it is difficult to distinguish between a promotion and an important message from a company.

SUMMARY

Disclosed implementations address the above deficiencies and other problems associated with categorizing electronic messages.

In accordance with some implementations, a method assigns categories to electronic messages. The method is performed at a computing device having one or more processors and memory storing one or more programs configured for execution by the one or more processors. The computing device receives an electronic message and extracts one or more syntactic pairs of words from content of the electronic message. At least one of the one or more syntactic pairs comprises a verb in a first sentence and an object in the same sentence, and the verb operates on the object. In some implementations, at least one of the one or more syntactic pairs comprises a verb in a second sentence and a subject in the same second sentence, where the subject performs the verb. The computing device forms a feature vector based on the extracted syntactic pairs and uses the feature vector as input to a classifier. The classifier is trained on a set of training feature vectors, and each training feature vector is associated with a respective category. In some implementations, each training feature vector corresponds to an electronic message previously received by one or more users, and the set of training feature vectors is selected based upon failure of rules-based categorization to identify correct categories for the electronic messages corresponding to the training feature vectors. The computing device assigns a first category to the electronic message based on output of the classifier and displays the message in a group with other messages associated with the first category.

Some implementations compute a classification score for the electronic message, and assign the first category to the electronic message only when the classification score exceeds a threshold value.

Some implementations group together in a folder the message and the other messages associated with the first category. Some implementations display all of the messages assigned to the first category together.

In some implementations, the one or more programs are part of an email application or an instant messaging application.

In some implementations, the extracted syntactic pairs of words are limited to a predetermined universe of syntactic pairs. For example, some implementations define a universe of 10000 syntactic pairs, and only those pairs are extracted. In some implementations, the universe of syntactic pairs is larger or smaller (e.g., a universe of 500 syntactic pairs or 50,000 syntactic pairs).

In some implementations, the feature vector includes one or more features based on metadata from the message. In some implementations, the feature vector includes one or more features based on individual words.

Thus methods and systems are provided that classify electronic messages more accurately.

Reference will now be made to implementations, examples of which are illustrated in the accompanying drawings. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one of ordinary skill in the art that the present invention may be practiced without these specific details.

DESCRIPTION OF IMPLEMENTATIONS

The implementations described herein provide various technical solutions to improving the categorization of electronic messages generally, and to improving classifiers that automatically determine the category of electronic messages.

FIG. 1is a block diagram illustrating conceptually a context in which some implementations operate. Electronic messages may be generated by many different devices102, such as a desktop computer102A, a smart phone102B, a laptop computer102C, a telephone102D, or an automated server102E. The messages are transmitted over a communication network104, and processed by a categorization system120at a server300, or by a categorization module224within a messaging application106running on the message recipient's user device102U. More generally, devices102that may transmit messages include phones (mobile or landline, smart phone or otherwise), tablet computers, other computers (mobile or otherwise, personal devices or servers), fax machines, and audio/video recorders.

In some implementations, a device102U obtains an electronic message and transmits the electronic message to the categorization system120. After categorization, the electronic message can be displayed with other electronic messages in the same category. For example, after determining that user Jack sends an electronic message to user Mary, the device102U transmits the electronic message to the categorization system120, which assigns the electronic message to a category and generates a visual object for display in a listing of electronic messages. This is illustrated below inFIG. 4. In some implementations, the message is initially received at the server300, categorized by the categorization system120, and displayed appropriately at the user device102U. In some implementations, the message is received at the user device102U, processed by a categorization module224, and displayed appropriately.

In some implementations, an electronic message is a file transfer110-a(e.g., a photo, document, or video download/upload), an email110-b, an instant message110-c, a fax message110-d, a social network update110-e, or a voice message110-f. In some implementations, an electronic message is contact information, an indication of a document, a calendar entry, an email label, a recent search query, a suggested search query, or a web search result.

In some implementations, the user device102U includes a messaging application106. In some implementations, the messaging application106processes incoming and outgoing electronic messages into and from the device102U, such as an outgoing email sent by a user of the device102U to another user, or a chat message from another user to a user of the device102U. In some implementations the messaging application106is an e-mail application or an instant messaging application.

In some implementations, the communication network104interconnects one or more devices102with each other, and with the server300. In some implementations, the communication network104includes the Internet, one or more local area networks (LANs), one or more wide area networks (WANs), other types of networks, or a combination of such networks.

An example of a set of message categories is {promotions, social, updates, and forums}. Each message category in the set of message categories requires that a message have certain characteristics. A message containing a reservation may be classified as an “update” message. A message containing information about an event may be “promotion” message. If a recipient is asked to rate something, the email may be a “social” message. Some implementations include additional messages categories and/or allow users to create custom message categories.

In some implementations, the server300is part of a server system that includes a plurality of servers300. In some implementations, the servers300are connected by an internal communication network or bus. A server system may include one or more web servers322, which receive requests from users (e.g., from client devices102) and return appropriate information, resources, links, and so on. In some implementations, the server system includes one or more application servers324, which provide various applications, such as a messaging application106. The server system typically includes one or more databases332, which store information such as web pages, a user list334, and various user information338(e.g., user names and encrypted passwords, user preferences, and so on).

FIG. 2is a block diagram illustrating a computing device102, which a user uses to access a messaging application106. A computing device is also referred to as a client device or a user device, which may be a tablet computer, a laptop computer, a smart phone, a desktop computer, a PDA, or other computing device that can run a messaging application106and has access to a communication network104. A client device102typically includes one or more processing units (CPUs)202for executing modules, programs, or instructions stored in memory214and thereby performing processing operations; one or more network or other communications interfaces204; memory214; and one or more communication buses212for interconnecting these components. The communication buses212may include circuitry (sometimes called a chipset) that interconnects and controls communications between system components. A client device102includes a user interface206comprising a display device208and one or more input devices or mechanisms210. In some implementations, the input device/mechanism includes a keyboard and a mouse; in some implementations, the input device/mechanism includes a “soft” keyboard, which is displayed as needed on the display device208, enabling a user to “press keys” that appear on the display208.

In some implementations, the memory214includes high-speed random access memory, such as DRAM, SRAM, DDR RAM or other random access solid state memory devices. In some implementations, the memory214includes non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid state storage devices. In some implementations, the memory214includes one or more storage devices remotely located from the CPU(s)202. The memory214, or alternately the non-volatile memory device(s) within the memory214, comprises a non-transitory computer readable storage medium. In some implementations, the memory214, or the computer readable storage medium of the memory214, stores the following programs, modules, and data structures, or a subset thereof:an operating system216, which includes procedures for handling various basic system services and for performing hardware dependent tasks;a communications module218, which is used for connecting the client device102to other computers and devices via the one or more communication network interfaces204(wired or wireless) and one or more communication networks104, such as the Internet, other wide area networks, local area networks, metropolitan area networks, and so on;a display module220, which receives input from the one or more input devices210, and generates user interface elements for display on the display device208;a web browser222, which enables a user to communicate over a network104(such as the Internet) with remote computers or devices;a messaging application106, which enables the user to send and receive electronic messages. In some implementations, the messaging application is an email application. In some implementations, the messaging application is an instant messaging application. In some implementations, the messaging application106runs within the web browser222. In some implementations, the messaging application106runs independently of a web browser222(e.g., a desktop application). In some implementations, the messaging application includes a categorization module224, which assigns a category to each message. The categorization module is functionally similar to a categorization system120, described below with respect to the server300; anda plurality of categories226, such as the categories226-1and226-2illustrated inFIG. 2. Each category may be assigned to zero or more messages so that messages assigned to the same category can be displayed together. In the illustrated example ofFIG. 2, the first category226-1includes a first message228-1and a second message228-2. Similarly, the second category226-2includes a third message228-3and a fourth message228-4.

AlthoughFIG. 2shows a client device102,FIG. 2is intended more as a functional description of the various features that may be present rather than as a structural schematic of the implementations described herein. In practice, and as recognized by those of ordinary skill in the art, items shown separately could be combined and some items could be separated.

FIG. 3is a block diagram illustrating a server300, which may be used individually or as part of a server system. A typical server system includes many individual servers300, such as 3, 10, or 100 individual servers. A server300typically includes one or more processing units (CPUs)302for executing modules, programs, or instructions stored in the memory314and thereby performing processing operations; one or more network or other communications interfaces304; memory314; and one or more communication buses312for interconnecting these components. The communication buses312may include circuitry (sometimes called a chipset) that interconnects and controls communications between system components. In some implementations, a server300includes a user interface306, which may include a display device308and one or more input devices310, such as a keyboard and a mouse.

In some implementations, the memory314includes high-speed random access memory, such as DRAM, SRAM, DDR RAM or other random access solid state memory devices. In some implementations, the memory314includes non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid state storage devices. In some implementations, the memory314includes one or more storage devices remotely located from the CPU(s)302. The memory314, or alternately the non-volatile memory device(s) within the memory314, comprises a non-transitory computer readable storage medium. In some implementations, the memory314, or the computer readable storage medium of the memory314, stores the following programs, modules, and data structures, or a subset thereof:an operating system316, which includes procedures for handling various basic system services and for performing hardware dependent tasks;a communications module318, which is used for connecting the server300to other computers via the one or more communication network interfaces304(wired or wireless), an internal network or bus, or other communication networks104, such as the Internet, other wide area networks, local area networks, metropolitan area networks, and so on;a display module320, which receives input from one or more input devices310, and generates user interface elements for display on a display device308;one or more web servers322, which receive requests from a client device102, and return responsive web pages, resources, or links. In some implementations, each request is logged in the database332;one or more application servers324, which provide various applications (such as an email or other messaging application106) to the client devices102. In some instances, applications are provided as a set of web pages, which are delivered to the client devices102and displayed in a web browser222. The web pages are delivered as needed or requested. In some instances, an application is delivered to a client device102as a download, which is installed and run from the client device102outside of a web browser222;in some implementations, the messaging application106includes a categorization system120, which is used to categorize received messages so that they can be grouped together for the recipient. Some implementations include a rules-based categorization module326, which categorizes received messages based on a set of rules (e.g., if a message is from a certain set of senders and includes a specific keyword, then the message is categorized as a “social update”). In some implementations, rules-based categorization is effective for a large percentage of the incoming messages. Disclosed implementations include a syntactic extraction module328, which extracts syntactic pairs of words from content of the received message (or the subject line). Some implementations use SAFT (Semantic Analysis and Filtering of Text) to extract the syntactic pairs. Each syntactic pair is a pair of words from a single sentence with a specific relationship. Some pairs consist of a finite verb and a direct object of the verb. Some pairs consist of a subject and a finite verb that specifies an action taken (or to be taken) by the subject. The extracted syntactic pairs are used to form a feature vector that is used as input to one or more machine classifiers330, which categorize the message. The categorization process is illustrated inFIG. 4, and a process for selecting training messages is illustrated inFIG. 5; andone or more databases332, which store various data used by the modules or programs identified above. In some implementations, the database332includes a list of authorized users334, which may include user names, encrypted passwords, and other relevant information about each user. The database332also stores categories336, and information about the categories. Some implementations provide both system-defined categories as well as user-defined categories. The database also stores other user data338. In particular, the user data338includes the received messages228and the assigned categories340for the messages. In some implementations, each message228is assigned to a unique category, but other implementations allow assignment to two or more categories. In some implementations, the database stores a universe342of syntactic pairs, which identifies the pairs that will be used in the categorization process (e.g., limiting the pairs to ones that are useful and reasonably likely to occur).

Each of the above identified elements inFIG. 3may be stored in one or more of the previously mentioned memory devices. Each executable program, module, or procedure corresponds to a set of instructions for performing a function described above. The above identified modules or programs (i.e., sets of instructions) need not be implemented as separate software programs, procedures or modules, and thus various subsets of these modules may be combined or otherwise re-arranged in various implementations. In some implementations, the memory314may store a subset of the modules and data structures identified above. Furthermore, the memory314may store additional modules or data structures not described above.

AlthoughFIG. 3illustrates a server300,FIG. 3is intended more as a functional illustration of the various features that may be present in a set of one or more servers rather than as a structural schematic of the implementations described herein. In practice, and as recognized by those of ordinary skill in the art, items shown separately could be combined and some items could be separated. The actual number of servers used to implement these features, and how features are allocated among them, will vary from one implementation to another, and may depend in part on the amount of data traffic that the system must handle during peak usage periods as well as during average usage periods.

As illustrated inFIGS. 2 and 3, the functionality for a messaging application may be shared between a client device102and a server300. In some implementations, after the messaging application is installed on a client device102, the majority of the subsequent processing occurs on the client device102. For example, the classification is performed by a categorization module on the client device. In other implementations, the majority of the processing and data storage occurs at a server300, and the client device102uses a web browser222to view and interact with the data. For example, the categorization of messages may be performed by the categorization system120at the server300, and the messages themselves are stored in the database332on the server. One of skill in the art recognizes that various allocations of functionality between the client device102and the server300are possible, and some implementations support multiple configurations (e.g., based on user selection).

FIG. 4illustrates a process of categorizing a received message. In this skeletal example, the received message402has a small amount of content, which is a message to Bob from the social media team at a social networking site. The syntactic extraction module328analyzes (420) the message402and extracts (420) various syntactic pairs404from sentences in the message402. In some implementations, the syntactic extraction module also extracts syntactic pairs from the subject line of the message402(not shown). In some implementations, the extraction process uses SAFT. In some implementations, the potential syntactic pairs are compared to a syntactic pair universe342, which limits the extracted pairs to those that are more likely to be useful in the classification process.

Using the extracted syntactic pairs404, the categorization system120forms (422) a feature vector406. In some implementations, a universe342of syntactic pairs is applied while forming the feature vector406, in order to reduce the number of less useful pairs. For example, here the pairs “(have, questions)” and “(contact staff)” have been omitted from the feature vector. These two pairs would probably not be useful to classify the message402.

Next, one or more classifiers330are applied (424) to the feature vector406to identify an appropriate category for the message402. In this example, the categorized message408E has been assigned to the “account updates” category. In some implementations, classification scores are computed for one or more of the possible categories, where each score estimates the probability that the corresponding category is proper. In some implementations, the category with the highest score is assigned to the message402. In some implementations, the category with the highest score is assigned to the message402only when the score exceeds a predefined threshold and/or exceeds the scores of other categories by a predefined positive margin. For example, with scores on a percentile scale, a threshold of 90% may be required or a positive margin of 10% or 20% greater than other categories may be required. In some implementations, if the threshold or margin requirements are not met, no category is assigned. In some implementations, two or more categories may be assigned if they each have a high classification score. In some implementations, a message can be assigned to only one system-defined category, but may be assigned to one or more user-defined categories as well.

In some implementations, machine classifiers330are used in conjunction with a rules-based classification module326. For example, in some implementations, the rules-based classification module326determines an appropriate category and computes a score that indicates the probability that the classification is correct. The rules-based classification score may be compared to the score(s) of the classification scores of the one or more categories determined by the machine classifiers330. In some implementations, the machine classification is used when the classification score for the machine classifier is greater than the classification score of the rules-based classification (or greater by a predefined positive margin).

After the message402has been assigned to a category, the message (or a summary indicator of the message) may be displayed (426) in a user interface410. The skeletal user interface410displayed inFIG. 4includes a group412of messages in the “account update” category, and the categorized message408E is displayed. In some implementations, the categorization process illustrated inFIG. 4occurs at a server300, but the display occurs on the user device102. In some implementations, the categorization occurs at the user device102, and the message is then displayed on the same device.

FIG. 5illustrates a process that is used in some implementations to select the set of training messages for the machine classifier(s). Whereas some implementations use a large set of randomly selected training messages (e.g., all messages received by some group of people during a one day period), some implementations select training messages in a more targeted way. For example, because rules-based classification has gotten fairly good, the greatest value for a machine classifier is for messages that are not handled well by rules-based classification.

The process inFIG. 5starts with a set of messages502, which can be arbitrary or random. A rules-based categorization module326identifies (520) categories for these messages to create a set of categorized messages. Note that not all of the messages are necessarily assigned to a category. In some instances, rules-based classification recognizes that it is not able to assign a category with a high enough certainty. Therefore, the categorized messages504typically include both messages that have been assigned to a category by the rules-based categorization module as well as some messages that could not be classified.

After assignment (or non-assignment) of categories to messages, users can correct (522) the assignments. User corrections are valuable because users are providing explicit information about the proper category for a message. After the corrections, the set of messages506includes: (1) messages that were categorized by the rules-based categorization module326, and not changed by the recipient; (2) messages that were assign a rules-based category that were subsequently corrected by the recipient; (3) messages that were unassigned to any category by the rules-based categorization module, but subsequently assigned to a category by the recipient; and (4) messages that were not assigned to a category by the rules-based classification module and not assigned a category by the recipient.

Some implementations select (524) a subset of the categorized and re-categorized messages506to form a training set for the machine classifiers330. In some implementations, the training set consists of those messages that were either corrected by the user and/or unclassified by the user (i.e., sets (2), (3), and (4) above). However, the fourth set may not be as useful because the proper category for those messages is not known. Therefore, some implementations select (524) the training set as those messages for which the user made an explicit assignment (i.e., sets (2) and (3) above).

Although not illustrated inFIG. 5, the training process extracts the syntactic pairs from each training message (similar to the process shown inFIG. 4) in order to correlate the syntactic pairs to the proper categories. In some implementations, the training process also identifies which of the syntactic pairs are useful, and builds the universe342based on the useful pairs.

FIGS. 6A and 6Bprovide a flowchart of a process600, performed by a computing device (e.g., a device102or a server300), for categorizing (602) electronic messages. The method is performed (604) at a computing device having one or more processors and memory. The memory stores (604) one or more programs configured for execution by the one or more processors. In some implementations, the one or more programs are (606) part of an email application or an instant messaging application.

The computing device receives (608) an electronic message, such as an email or an instant message. A syntactic extraction module328extracts (610) one or more pairs of words from content of the electronic message. In some implementations, this is supplemented with syntactic pairs extracted from the subject line of the electronic message. At least one of the syntactic pairs comprises (612) a verb in a first sentence from the message content and an object in the same first sentence. The verb operates (612) on the object. For example, in the sentence/phrase “unsubscribe from the list,” the verb is “unsubscribe” and the object is “list.”

In some instances, at least one of the syntactic pairs includes (614) a verb in a second sentence and a subject in the same second sentence, and the subject performs (614) the verb. For example, in the sentence “Company XYZ announces a new product,” the subject is “Company XYZ” and the verb is “announces.” Note that in this example, the subject consists of two separate words.

In some implementations, extracting the one or more syntactic pairs of words includes (616) limiting the extracted pairs to a predetermined universe of syntactic pairs. There are many syntactic pairs that have little or no value in classifying a message, so it can be useful to exclude those. In some implementations, the universe may be fairly small (e.g.,500pairs), but in other implementations, the universe can be much larger (e.g., 5000 or more pairs).

The categorization system120or categorization module224forms (618) a feature vector based on the extracted syntactic pairs, as illustrated inFIG. 4above. In some implementations, additional features in the feature vector are based on (620) metadata from the message.

Nonlimiting examples of metadata include, but are not limited a determination as to whether a user associated with the message communicates directly with a certain other user, a message sender identity, a message recipient identity, a message category, a message date, a message sender domain, and a personal contact of the user associated with the message.

Additional examples of metadata are any of the fields found in the header of the protocol under which the electronic message is governed. For instance, if the electronic message is governed by the Simple Mail Transfer Protocol (See Request for Comments: 4321, dated October 2008, http://tools.ietf.org/html/rfc5321, last accessed Nov. 6, 2014, which is hereby incorporated by reference), than any of the message header sections or the elements contained therein, as referenced in companion document Request for Comments: 5322, dated October 2008, http://tools.ietf.org/html/rfc5322, last accessed Nov. 6, 2014 (“RFC 5322”), which is hereby incorporated by reference, can be extracted for use in the disclosed systems and methods. RFC 5322 details and defines metadata such as address, mailbox, name-addre, angle-addre, group, display-name, mailbox-list, address-list, group-list, addr-spec, local-part, domain, domain-literal, and dtext as exemplary header fields, any of which can be used as meta data in the disclosed systems and methods. Moreover, in some embodiments, the message category assigned (or not assigned) by a classifier to a message (e.g., social, promotions, updates, forums) constitute metadata in some embodiments. Moreover, in some embodiments, actions taken (or not taken) by a user on a message can constitute metadata. For instance, respective events (taken or not taken) such as reading an electronic message, replying to the electronic message, or recategorizing the electronic message can each constitute metadata for the electronic message. Further still, system labels that are (or are not) applied to a message can constitute metadata for a message. Examples of system labels include, but are not limited to inbox, starred, important, chats, sent mail, drafts, all mail, spam, and trash. Further still, social (circle) labels (e.g., friends, family, acquaintances, following, popular on social media, clients) that are (or are not) applied to a message can constitute meta data for the respective message.

The feature vector is used (622) as input to one or more machine classifiers330. Each classifier is trained on (624) a set of training feature vectors, and each training feature vector is associated with (624) a respective category. In some implementations, each training vector corresponds to (626) an electronic message previously received by one or more users. In some implementations, the set of training feature vectors is selected (628) based upon failure of rules-based categorization to identify correct categories for electronic messages corresponding to the training feature vectors. This is illustrated above inFIG. 5.

The categorization system120or categorization module224assigns (630) a first category to the electronic message based on output of the classifier. In some implementations, a classification score is computed (632) for one or more categories, and the assignment is based on the score(s). In some implementations, the first category is assigned (634) to the electronic message only when the classification score exceeds a threshold value (e.g., 80th percentile). This is described above with respect toFIG. 4.

After the message is classified, the message is displayed (636) in a group with other messages associated with the first category. This is illustrated inFIG. 4. In some implementations, the message and the other messages associated with the first category are grouped (638) in a folder.

The foregoing description, for purpose of explanation, has been described with reference to specific implementations. However, the illustrative discussions above are not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The implementations described herein were chosen and described in order to explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to best utilize the invention and various implementations with various modifications as are suited to the particular use contemplated.