Distributed hierarchical text classification framework

• US 7,809,723 B2
• Filed: 08/15/2006
• Issued: 10/05/2010
• Est. Priority Date: 06/26/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Liu, Tie-Yan, Zeng, Hua-Jun
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Shmatov; Alexey
• Application Number:
  US11/464,761
• Publication Number:
  US 20080126280A1
• Time in Patent Office: 1,512 Days
• Field of Search: 707/7, 707/3, 707/2, 707/999.007, 707/999.003, 707/999.002, 707/736
• US Class Current: 707/736
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

A method and system for distributed training of a hierarchical classifier for classifying documents using a classification hierarchy is provided. A training system provides training data that includes the documents and classifications of the documents within the classification hierarchy. The training system distributes the training of the classifiers of the hierarchical classifier to various agents so that the classifiers can be trained in parallel. For each classifier, the training system identifies an agent that is to train the classifier. Each agent then trains its classifiers.

Claims

1. A method in a computing device with a processor for training a hierarchical classifier for classification of documents into a classification hierarchy, the method comprising:

providing the classification hierarchy in which classifications have sub-classifications except for leaf classifications;

providing training data for training the classifiers, the training data including documents and classifications of the documents within the classification hierarchy, the classification of a document indicating that the document is in that classification and ancestor classifications of that classification, each classification having a number of documents;

generating a classifier for each classification within the classification hierarchy by, for each classification within the classification hierarchy,

determining a complexity for the classifier for the classification, the complexity of the classifier varying nonlinearly based on the number of documents within the classification;

identifying by the processor one of a plurality of agents to train the classifier for that classification such that one agent is identified to train one classifier and some of the agents are identified to train multiple classifiers, the agents being identified to balance training load of the agents that is determined based on the determined complexity of the classifiers identified to be trained by each agent wherein the identifying of one of the agents includes;

when a classifier has not yet been assigned to an agent, assigning the classifier to that agent; and

when a classifier has already been assigned to each agent, assigning the classifier to an agent based on complexity of the classifier and complexities of classifiers assigned to each agent such that a classifier with the highest complexity is assigned to an agent that has been assigned classifiers with the smallest total complexity; and

under control of the identified agent, training the classifier for that classification using the documents of the training data that are classified within that classification of the classification hierarchy;

wherein each agent trains classifiers for a varying number of documents of the training data,

wherein the classifiers trained by the multiple agents form the hierarchical classifier, and

wherein the agent for a classifier is identified based on number of documents used.

2. The method of claim 1 wherein each agent executes on a distinct computing device.

3. The method of claim 1 wherein each classifier is a binary classifier for a classification that classifies documents within that classification as being within or not within one sub-classification.

4. The method of claim 3 wherein the training is performed with a support vector machine.

5. The method of claim 1 wherein the classifiers are binary classifiers and the training of a classifier uses a cross validation technique to determine a confidence threshold for being within a classification.

6. The method of claim 5 including selecting a confidence threshold based on a middle of a largest interval with a maximum F1 score.

7. The method of claim 1 wherein the complexity of training a classifier is based on the number of documents in the training data times the number of classifications.

8. The method of claims 7 wherein the number of classifications for a binary classifier is two.

9. The method of claim 1 wherein a controller identifies agents to train the classifiers and notifies the identified agents.

10. A computer system with a processor and a memory for training a hierarchical classifier for classification into a classification hierarchy, comprising:

a classification hierarchy store containing a classification hierarchy in which classifications have sub-classifications except for leaf classifications;

a training data store having training data for training classifiers of the hierarchical classifier, the training data including documents and classifications of the documents within the classification hierarchy, the classification of a document indicating that the document is in that classification and ancestor classifications of that classification as specified by the classification hierarchy; and

a select features for classifier component, a controller, and a plurality of agents implemented as instructions stored in the memory for execution by the processor such that

the select features for classifier component that for each classification of the classification hierarchy, identifies features of the documents of the training data that are to be used for training a classifier for that classification;

the controller that, for each classifier of a classification within the classification hierarchy, identifies one of a plurality of agents to train the classifier and notifies the identified agent to train the classifier, wherein the controller identifies agents by assigning a classifier to each agent and then assigning unassigned classifiers to agents based on complexities of training the unassigned classifiers and complexities of training classifiers already assigned to each agent, wherein an unassigned classifier with the highest complexity is assigned to an agent that has been assigned classifiers with the smallest total complexity, and wherein the complexity of training a classifier varies nonlinearly based on number of documents in the training data for that classifier, each classifier for a classification being trained using documents classified into the classification of which the classification is a sub-classification; and

the plurality of agents executing on different computer devices that receive notifications to train classifiers and train the classifiers using the features of the documents identified for each classification from the training data

wherein the classifiers trained by the multiple agents form the hierarchical classifier.

11. The computer system of claim 10 wherein a classifier is a binary classifier for a classification that classifies documents within that classification as being within or not within a sub-classification.

12. The computer system of claim 10 wherein the classifiers are binary classifiers and the training of a classifier uses a multi-fold cross validation technique to determine a confidence threshold for being within a classification.

13. The computer system of claim 12 wherein the confidence threshold is based on a middle point of a largest interval with a maximum F1 score.

14. A computer-readable storage medium containing instructions for controlling a computer to train a hierarchical classifier for classification into classification hierarchy, by a method comprising:

providing the classification hierarchy in which classifications have sub-classifications except for leaf classifications;

training data for training classifiers of the hierarchical classifier, the training data including documents and classifications of the documents within the classification hierarchy, the classification of a document indicating that the document is in that classification and ancestor classifications of that classification, each classification having a number of documents; and

for each classifier of a classification within the classification hierarchy,

determining a complexity for the classifier for the classification, the complexity of the classifier varying nonlinearly based on the number of documents within the classification;

identifying one of a plurality of agents to train the classifier based on complexities of classifiers assigned to the agent and the determined complexity of the classifier such that one agent is identified to train one classifier and some of the agents are identified to train multiple classifiers, the agents being identified to balance training load of the agents that is determined based on the determined complexity of training the classifiers identified to be trained by each agent wherein the identifying of one of the agents includes;

when a classifier has not yet been assigned to an agent, assigning the classifier to that agent; and

when a classifier has already been assigned to each agent, assigning the classifier to an agent based on complexity of the classifier and complexities of classifiers assigned to each agent such that a classifier with the highest complexity is assigned to an agent that has been assigned classifiers with the smallest total complexity; and

notifying the identified agent to train the classifier using training data that includes documents and classifications.

15. The computer-readable storage medium of claim 14 wherein features for use in training each classifier are automatically selected based on analysis of training data.