Training procedure for N-gram-based statistical content classification

A training procedure for N-gram based statistical document classification has been disclosed. In one embodiment, a set of N-grams is selected out of a second set of N-grams, each of the N-grams having a sequence of N bytes, where N is an integer. Then a statistical content classification model is generated based on occurrences of the N-grams, if any, in a set of training documents and a set of validation documents. The statistical content classification model is provided to content filters to classify content.

FIELD OF INVENTION

The present invention relates to content rating, and more particularly, to building an N-gram-based statistical model for content rating.

BACKGROUND

Today, various content filtering mechanisms are provided to entities to manage and/or control user access to the Internet via facilities provided by the entities. For example, a company typically implements some form of content filtering mechanism to control the use of the company's computers and/or servers to access contents (e.g., web pages and/or emails) from the Internet. Contents as used herein broadly refer to expressive work, which may include one or more of literary, graphics, audio, and video data. Access to content within certain predetermined categories using the company's computers and/or servers may not be allowed during some predetermined periods of time.

Conventionally, a content rating engine or a content classification engine may be installed in a firewall to screen contents coming into a system from an external network, such as email received and web pages retrieved from the Internet. The content rating engine may retrieve rating of the incoming contents from a rating database, if any, and/or attempt to rate the contents in real-time. To rate the content in real-time, the content rating engine may parse the contents to identify some predetermined keywords and/or tokens and then determine a rating for the contents based on the presence and/or absence of the keywords and/or tokens.

However, the above rating mechanism typically relies on delimiters between words in the contents in order to identify the keywords and/or tokens. Some major languages (e.g., Chinese, That, Japanese, etc.) do not have delimiters, such as spaces, between words, and thus, are referred to as non-delimited languages. Because of the lack of delimiters between words, segmenting a stream of text in such a language requires a preprocessing stage, which is language-specific and computationally intensive. For example, the following sentence may appear in a Chinese blog:. The correct split into words is:(daughter),(possessive particle),(writing),(level),(still),(consider),(acceptable). With this split, the sentence means “The daughter's writing level is still considered acceptable.” Note that some words are two-character long, some are one character long, and one is three-character long. Moreover, the whole context is necessary to split it correctly. For example, one could also have split it as follows:(daughter),(possessive particle),(write),(make),(water),(Ping, a person's name),(still),(consider),(past tense particle),(must),(go). With this split, the sentence means “The daughter's write make water, Ping had already considered must go,” which makes no sense. But for a computer system to detect automatically that this is nonsense, a word list is not sufficient. The computer system also needs a model of language usage. Developing and maintaining such a model is a knowledge-intensive task, and it would need to be repeated for each non-delimited language supported. Moreover, maintaining and using the model may be resource-intensive and may not be suitable for real-time applications. Thus, many conventional word-based real-time content rating mechanisms perform poorly on contents written in these non-delimited languages.

SUMMARY

The present invention includes a training procedure for N-gram based statistical content classification. In one embodiment, a set of N-grams is selected, each of the N-grams having a sequence of N bytes, where N is an integer. Then a statistical content classification model is generated based on occurrences of the N-grams, if any, in a set of training documents and a set of validation documents. The statistical content classification model is provided to content filters to classify content.

DETAILED DESCRIPTION

A training procedure for N-gram based statistical content classification is described. In the following description, numerous specific details are set forth. However, it is understood that embodiments of the invention may be practiced without these specific details. In other instances, well-known components, structures, and techniques have not been shown in detail in order not to obscure the understanding of this description.

FIG. 1Aillustrates a flow diagram of one embodiment of a process to select one or more values of N. The process is performed by processing logic that may comprise hardware (e.g., circuitry, dedicated logic, etc.), software (such as is run on a general-purpose computer system, a server, or a dedicated machine), firmware, or a combination of any of the above. Note that the basic tradeoff involved is that long N-grams generally tend to be more significant in content classification, but also tend to occur less frequently. To be useful for content classification, an N-gram needs to be both significant enough and frequent enough.

In order to select the values of N, for each N-gram of a set of N-grams for each N within a range of values, processing logic first compares a frequency of occurrence of the N-gram in documents in a set of training documents that have been classified in a particular category with a frequency of occurrence of the N-gram in documents not classified in the category (processing block101). In some embodiments, the range of values is from one to a predetermined maximum value. The predetermined maximum value may be selected based on knowledge of a given language (e.g., Chinese, Japanese, etc.), such as the longest N-grams found in a dictionary for the given language.

In some embodiments, a category-wise significance function is defined as sig(N-gram, Category):=abs(log(frequency of N-gram occurring in document not in Category)/(frequency of N-gram occurring in document in Category), where abs denotes absolute value, and log denotes natural logarithm. To avoid division by zero or logarithm of zero, processing logic may add one to all N-gram occurrence counts. Further, the category-independent significance may be defined as the maximum, taken over all categories, of the category-wise significance: sig(N-gram):=max(sig(N-gram, Category)).

Processing logic further measures each N-gram's utility (processing block102). In some embodiments, processing logic measures an N-gram's utility by combining the N-gram's significance with the N-gram's frequency. The utility function may be defined as the N-gram's frequency in the training set multiplied by the significance, i.e., utility(N-gram):=frequency(N-gram)*sig(N-gram).

Note that the best values of N may include those associated the most N-grams with the highest utility. Thus, processing logic generates statistics about the utilities found at each value of N (processing block104). For example, processing logic may compute a sum of utility of all N-grams of size N for each N within the range. Based on the statistics, processing logic may select the values of N with the highest utilities (processing block106).

FIG. 1Bshows a flow diagram of one embodiment of a process to generate a statistical content classification model. The process is performed by processing logic that may comprise hardware (e.g., circuitry, dedicated logic, etc.), software (such as is run on a general-purpose computer system, a server, or a dedicated machine), firmware, or a combination of any of the above.

Referring toFIG. 1B, processing logic selects a sub-range of the range of values of N having one or more values of N, which is an integer (e.g., 1, 2, 3, etc.), from a range of values of N (processing block110). Then processing logic puts N-grams associated with the selected values of N into a feature set (processing block112). Details of some embodiments of selecting values of N have been discussed above with reference toFIG. 1A.

In some embodiments, processing logic searches for the N-grams of the feature set in a set of training documents (processing block114). The set of training documents may include emails, web pages, and/or downloadable files that have been previously classified. For instance, some people may have already classified the training set of documents manually into a set of categories (e.g., pornographic content, violent content, gambling content, online chat room related content, etc.). Note that this technique is particularly useful for non-delimited languages because the search for N-grams does not rely on delimiters. As processing logic searches for the N-grams in the set of training documents, processing logic may keep track of the number of occurrences of each N-gram in training documents classified into each category. After searching through the training documents, processing logic computes scores of the N-grams with respect to each category based on the result of the search in the training documents (processing block116). One exemplary embodiment of score computation is discussed in details below.

In some embodiments, processing logic has selected a set of N-grams for N within a predetermined range. Processing logic searches for each N-gram in the set of N-grams for each N within the predetermined range in the set of training documents. For each N-gram occurring in a training document and each category of which the training document is a member, processing logic increments a corresponding count or entry in a feature occurrence table. As such, processing logic tallies up the occurrences of each N-grams in the training documents with respect to each category. For each N-gram and for each category, processing logic computes a probability of a respective N-gram occurring in the training documents in a respective category and a probability of the respective N-gram not occurring in the training documents in the respective category. The processing logic may assign a score for the respective N-gram with respect to the respective category to be −log(probability in category/probability not in category).

Referring toFIG. 1B, processing logic then searches for the N-grams in a set of validation documents (processing block118). Like the training documents, the set of validation documents may include web pages and/or downloadable files having content previously classified. For instance, some people may have already classified the validation set of documents manually into a set of categories (e.g., pornographic content, violent content, gambling content, online chat room related content, etc.). Then processing logic sets a threshold for each of the category based on the scores of the N-grams and the result of the search in the set of validation documents (processing block120). One exemplary embodiment of threshold computation is discussed in details below.

In some embodiments, for each validation document and each category, processing logic determines the frequency of each N-gram found in the validation document appearing in a category and the frequency of this N-gram not appearing in the category. Then processing logic computes a result associated with the validation document and the category (c) as −log(frequency in c/frequency not in c)+Σ score (f, c) for all N-grams f found in the validation document. Processing logic holds the results computed in a result table. Then for each category c, processing logic sorts the set of values in the result table associated with the validation document and the category c from the lowest to the highest. For each value v in the set of values, processing logic determines the false positive rate (i.e., the number of entries in the result table with document not in the category c and with a result greater than or equal to v). If the false positive rate is greater than a predetermined desired false positive limit, then the threshold of the category c is set to be the previous value of v and then processing logic skips to the next category.

Finally, processing logic generates a statistical content classification model based on the scores and the thresholds determined above (processing block122). The statistical content classification model may be stored in a repository accessible by content filters. Alternatively, the statistical content classification model may be transferred to content filters. Using the statistical content classification model, content filters may rate documents (e.g., web pages, emails, etc.) based on N-grams present and/or N-grams absent in the documents. More details of some embodiments of content rating using the statistical content classification model are discussed below.

FIG. 2illustrates one embodiment of a training server. The training server200includes a pattern matching engine211, a processing module213, and a model generator215. The server200is coupled to a model repository220.

In some embodiments, the processing module213determines a value or a range of values of N and selects a set of N-grams for each value of N based on criteria as discussed above. Then the pattern matching engine211receives a set of training documents201and searches for the N-grams in the training documents201. The pattern matching engine211generates a set of scores213for each of the N-grams with respect to each of a set of categories based on the occurrence of the N-grams in the training documents201. The scores213are provided to the model generator215. Furthermore, the pattern matching engine211receives a set of validation documents203and searches for the N-grams in the validation documents203. Based on the pre-classification of the validation documents203, the occurrence of the N-grams in the validation documents203, and the scores213, the pattern matching engine211computes a set of results and then sets a threshold for each category based on the results and a predetermined false positive limit. The pattern matching engine211then sends the set of thresholds214set to the model generator215.

The model generator215generates a statistical content classification model218based on the scores213and the thresholds214. The model218may include a set of weights for each N-gram, where each weight is associated with a distinct one of the categories. Then the model218is stored in the model repository220. Content filters may access the model218in the model repository220and use the model218to rate content of documents (e.g., web pages, emails, etc.). Alternatively, the training server200may transfer the model218to content filters, which stores the model218locally at the content filters for rating content of documents.

FIG. 3illustrates a flow diagram for rating a document (e.g., a web page, an email, etc.) using N-gram-based rating according to one embodiment of the invention. The process is performed by processing logic that may comprise hardware (e.g., circuitry, dedicated logic, etc.), software (such as is run on a general-purpose computer system or a dedicated machine), firmware, or a combination of any of the above.

Referring toFIG. 3, processing logic receives a document from an external network (e.g., a web page, an email, etc.) (processing block310). Then processing logic determines whether the document has already been rated (processing block320). If the document has already been rated, then processing logic retrieves the content rating of the document, locally or remotely, from a storage device, such as a cache or a database, over a network (processing block325).

If the web page has not been rated yet, then processing logic searches the document for a set of predetermined N-grams (processing block340). Then processing logic uses the statistical content classification model to rate the content of the document based on the result of the search for the N-grams (processing block360). In some embodiments, the statistical content classification model includes a set of weights for each N-gram, where each weight is associated with a distinct one of the categories. Processing logic generates a score for the document for each category based on a product of the number of occurrences of the N-grams by the corresponding weights. If the score of the document with respect to a category is higher than a threshold of the category, processing logic classifies the document to be in the category. Otherwise, processing logic does not classify the document to be in the category. Based on the classification of the document, processing logic may take different courses of actions, such as passing the document, blocking the document, warning a user of the document, etc. For example, if the document is an email and is classified to be in a category of spam, then processing logic may block the email and/or flag it to the email recipient. Alternatively, if the document is a web page and is classified to be in a prohibited category (e.g., pornographic material, violent material, etc.), then processing logic may block the web page.

The techniques discussed above may be implemented in various embodiments of a networked system. Some exemplary embodiments are discussed below to illustrate the concept. However, one should appreciate that the invention is not limited to the configurations in the following embodiments. For example, the N-gram-based rating engine may run on a dedicated machine or on different devices within the system, such as the content filtering module, the server, etc. Furthermore, the N-gram-based rating engine may rate documents in real time and/or at the back end. Moreover, the handling of documents that have to be rated may vary from system to system. Likewise, the timing for when to access a server and when to access a N-gram-based rating engine may vary from system to system.

FIG. 4illustrates one embodiment of a system usable with the invention. The system400includes a client machine401, a content filtering module410, a firewall415, a server420, a database425, and a N-gram-based rating engine430. The content filtering module410is executable on the firewall415, which may be implemented on a proxy server, a personal computer, a workstation, etc. Alternatively, the content filtering module410may be executable on the client machine401, in which case, the firewall415could be eliminated. Referring back toFIG. 4, the content filtering module410is communicably coupled to the server420. The server420is also communicably coupled to the N-gram-based rating engine430. Alternatively, the N-gram-based rating engine430may be executable on the server420. Referring back toFIG. 4, the database425has stored therein the ratings of web pages already rated. The database425may be within the server420as shown inFIG. 4. Alternatively, the database425may be a separate unit communicably coupled to the server420.

Note that any or all of the components and the associated hardware illustrated inFIG. 4may be used in various embodiments of the system400. However, it should be appreciated that other configurations of the system400may include more or less devices than those shown inFIG. 4.

The N-gram-based rating engine430searches for a predetermined set of N-grams in documents and uses a statistical content classification model generated as described above to rate the documents. One exemplary flow of operations in the system400is described in detail below to illustrate the concept.

In one embodiment, the content filtering module410sends a request for rating (1) to the server420when the content filtering module410receives a document. For example, the document may be an email or a web page from a web page host. In response to the request (1), the server420checks the database425for the rating. If the rating is available in the database425, the server420retrieves the rating from the database425and sends the rating to the content filtering module410with a response (2). Otherwise, the server420may send a response (2) without rating to the content filtering module410and may send a request (3) for the rating to the N-gram-based rating engine430. In one embodiment, the N-gram-based rating engine430performs N-gram-based rating on the document received as described above with reference toFIG. 3. After rating the document, the N-gram-based rating engine430may return the rating (4) to the server420to log the corresponding document, the rating, and to populate the database425with the rating. Therefore, next time the server420receives a request for the rating of the same document, the server420would have the rating available in the database425.

If the content filtering module410receives the response (2) without the rating, the content filtering module410may take a variety of actions. For example, it may pass the document. When the same document is received again, the database425would have the rating available because the document would have been rated by then as discussed above. As another example, the content filtering module410may block the document, thereby requiring the user to request it until a rating is available.

Alternatively, the server420may request the N-gram-based rating engine430to rate the document in real time. The server420may wait until the N-gram-based rating engine430completes rating the document and sends the rating to the server420before the server420sends the response (2) with the rating to the content filtering module410. In such a system, the content filtering module410may be implemented to wait for a predetermined period for a response from the server420. If the predetermined period expires and the server420has not sent a response with the rating to the content filtering module410yet, the content filtering module410may take a variety of actions (e.g., pass the document, block the document, etc.).

FIGS. 5A and 5Billustrate an alternate embodiment of a system usable with the invention. The system500includes a content filtering module510, a database525, and a server520. The content filtering module510is communicably coupled to the server520. In one embodiment, the content filtering module510includes a N-gram-based rating engine512and a buffer514. The database525may be within the server520as shown inFIGS. 5A and 5B. Alternatively, the database525may be a separate unit communicably coupled to the server520.

Note that any or all of the components and the associated hardware illustrated inFIGS. 5A and 5Bmay be used in various embodiments of the system500. However, it should be appreciated that other configurations of the system500may include more or less devices than those shown inFIGS. 5A and 5B.

Various embodiments may populate the database525differently (e.g., N-gram-based rating, token-based rating, manually, keywords, combinations thereof, etc.). Also, various embodiments may provide the initial training set and statistics to the N-gram-based rating engine512differently (e.g., from the server520, from a separate server, preinstalled, etc.) and may optionally provide updates (7) (e.g., from server520, from a separate server, etc.).

When the content filtering module510receives a document, the content filtering module510sends a request (1) for the rating of the document to the server520. In response to the request (1), the server520checks the database525for the rating. If the rating is available in the database525, the server520retrieves the rating and sends the rating with a response (2) to the content filtering module510as shown inFIG. 5A.

In some embodiments, the content filtering module510may hold the document until the rating arrives and then determine whether to pass the document held based on the rating. In some embodiments, if the rating does not arrive within a predetermined period, the content filtering module510take a variety of actions (e.g., pass the document, block the document, etc.).

Referring toFIG. 5B, if the rating is not available in the database520, the server520may return a response (2) to the content filtering module510without the rating. When the content filtering module510receives the response (2) without the rating, the content filtering module510uses the N-gram-based rating engine512to rate the document. As described above, the content filtering client510may have pulled the document substantially simultaneously with sending the request (1) for the rating. All or part of the document pulled may be stored in the buffer514temporarily (3). In one embodiment, the N-gram-based rating engine512retrieves a string representing the stored document from the buffer514(4) and searches for a set of predetermined N-grams in the string (5). As discussed above, the N-gram-based rating engine512may periodically receive an updated statistical content classification model (7) from the server520. The N-gram-based rating engine512may rate the document using the statistical content classification model based on presence and/or absence of the predetermined N-grams in the document.

In some embodiments, the N-gram-based rating engine512rates the document in real time and the content filtering module510holds the document until the rating is available and the content filtering module510can determine whether the document can be passed. Alternatively, if the N-gram-based rating engine512does not complete rating the document within a predetermined period, the content filtering module510may go ahead to pass the document in order to keep the document retrieval latency below a predetermined limit.

When the server lacks a rating for a document, the rating to be stored in the server (which may differ from the real time rating that could be produced by the N-gram-based engine512), may be obtained in a variety of ways. For example, it may be obtained as described with reference toFIG. 4. Alternatively, it may be logged and obtained manually. As another alternative, it may be obtained from the N-gram-based rating engine512. Specifically, once the N-gram-based rating engine512determines the rating of the document, the content filtering module510sends the rating to the server520to update the database525with the rating (6). Hence, the next time a request for the same document is received, the content filtering module510or others can receive the rating from the database525without rating the document again. In some embodiments, the rating may be stored with a predetermined time-to-live (TTL) parameter in the database525such that documents that have been rated before a predetermined period have to be rated again because the content of some documents may change over time, and thus, the old rating may have become obsolete.

In one embodiment, the content filtering module (e.g.,410and/or510inFIGS. 4,5A, and5B, respectively) may include a cache (a local storage device that may include any of various types of machine readable media, such as, for example, random access memory (RAM), dynamic random access memory (DRAM), flash memory, etc.). Recent ratings are stored in the cache (e.g., from the server, from the on-board N-gram-based rating engine, etc.). In some embodiments, the content filtering module may check the cache to see if the rating of the document is available in the cache while the document is being pulled. If the rating is available in the cache, then the content filtering module may use the rating from the cache to determine whether to pass the document.

Furthermore, in some embodiments, the rating may be stored with a predetermined TTL parameter such that documents that have been rated before a predetermined period have to be rated again to ensure the rating is current.