Hierarchial Classification

• US 20100306282A1
• Filed: 06/02/2009
• Published: 12/02/2010
• Est. Priority Date: 06/02/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hguyen, Nam H., Bennett, Paul Nathan
• Granted Patent: US 8,296,330 B2
• Time in Patent Office: Days
• US Class Current: 707/803
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

The hierarchical approach may start at the bottom of the hierarchy. As it moves up the hierarchy, knowledge from children and cousins is used to classify items at the parent. In addition, knowledge of improper classifications at a low level are raised to a higher level to create new rules to better identify mistaken classifications at a higher level. Once the top of the hierarchy is reached, a top down approach is used to further refine the classification of items.

Claims

1. A method creating a hierarchical learner to electronically classifying data received from a source into a hierarchical tree of categories comprising:

storing and accessing pre-categorized training data wherein the pre-categorized training data comprises elements and assigned labels;

accessing specified subsets of the pre-categorized training data;

accessing the elements the assigned labels in the specified subsets;

starting at the top of a hierarchy;

creating a base learner to learn a top down model for each category of the hierarchy using a basic representation and a specified subset of the training;

providing the base learner the specified subset of an entire set of pre-categorized training data as input;

storing top down model output from the base learner for a category to be used as part of a prediction model for the hierarchical learner;

estimating performance of the top down model learned for the category comprising;

partitioning the specified subset of the data into non-overlapping subsets;

for each subset, creating a stored output model comprising;

providing the base learner all but that subset as training data to obtain a base model;

using the top down model together with the base learner'"'"'s prediction component to create a prediction for the category of every element in the subset withheld from training;

storing the predictions as stored predictions;

using the stored predictions over the specified subset and actual categories to assess performance of the base model;

using errors committed by the base model as well as the actual categories to compute a weighting of the examples that should be used as the training data at each child of the category;

storing this distribution to be used as the specified subset at the creating a base learner block;

repeating a creating a block learner block for each child category of the category;

using a top down prediction component that uses a stored output models to predict starting from a top-down by;

predicting membership at a topmost category;

for each category of which the element is predicted to be a member, predicting membership in that category'"'"'s children;

continuing down the hierarchy until no further categories are predicted or the bottom of the hierarchy has been reached.

2. The method of claim 1, further comprising:

learning bottom-up prediction models for each category in the hierarchy comprising;

starting at a lowest level of the hierarchy

for each element in the pre-categorized training data, creating an extended representation comprising extending a representation of an example with meta-attributes for the category computed using bottom-up prediction of all categories at lower levels than the category;

creating a learner comprising learning a prediction model for the category over a specified subset of the training data using the extended representation and storing this as a bottom-up model for the category to be used in a hierarchical model'"'"'s prediction component;

estimating behavior/performance of the model learned for the category;

partitioning the specified subset of the data into non-overlapping subsets;

for each subset,

giving the learner all but the subset as the training data with the extended representation to obtain a model;

using the model together with the prediction model of the learner to predict the category of every element in the subset withheld from training;

storing the predictions as bottom-up predictions for the category for the elements in the subset;

for any element in a full pre-categorized training set but not in the specified subset given to the learner, using a stored bottom-up model to make predictions for those elements and storing them;

using the stored predictions over the pre-categorized training data and the actual categories to assess the performance of the base model;

using the errors committed by the bottom-up model at the category as well as the actual categories to compute a weighting of the examples that should be used at a parent as the training data in conjunction with errors and the actual categories from the parent'"'"'s other children;

continuing until a root is reached.

3. The method of claim 2, further comprising;

using a prediction component that uses the stored output models to predict by;

predicting pre-categorized training data as belonging to an initial set of bottom-up categories using predictions over a basic set of example attributes;

starting at the lowest level of the hierarchy that has descendants belonging to the bottom-up categories, predict membership at the category by;

using the bottom-up predictions of all categories below a level of the category'"'"' in the hierarchy to extend the representation of a document with metafeatures;

using the stored bottom-up model for this node in the hierarchy to make the prediction of this category'"'"'s membership using the extended representation and store the prediction as the bottom-up prediction for the category;

continuing up the hierarchy, applying bottom-up models, predicting bottom-up membership and storing the metafeatures for each node in the hierarchy until the root is reached;

starting at the top of the hierarchy,

substituting the extended representation in the top down prediction component and

a stored top-down output models are used at each node in the hierarchy.

4. The method of claim 1, wherein the specified subset comprises a weighting of the elements.

5. The method of claim 1, wherein the specified subset comprising an inclusion/exclusion decision.

6. The method of claim 1, wherein errors comprise assigning data into an improper branch.

7. The method of claim 2, wherein extended representation comprises extending the representation of an example with meta-attributes for the category computed using bottom-up predictions of all categories at lower levels than the category.

8. A computer storage medium comprising computer executable instructions for creating a hierarchical learner to electronically classifying data received from a source into a hierarchical tree of categories, the computer executable instructions comprising instructions for:

storing and accessing pre-categorized training data wherein the pre-categorized training data comprises elements and assigned labels;

accessing specified subsets of the pre-categorized training data;

accessing the elements the assigned labels in the specified subsets;

starting at the top of a hierarchy;

creating a base learner to learn a top down model for each category of the hierarchy using a basic representation and a specified subset of the training;

providing the base learner the specified subset of an entire set of pre-categorized training data as input;

storing top down model output from the base learner for a category to be used as part of a prediction model for the hierarchical learner;

estimating performance of the top down model learned for the category comprising;

partitioning the specified subset of the data into non-overlapping subsets;

for each subset, creating a stored output model comprising;

providing the base learner all but that subset as training data to obtain a base model;

using the top down model together with the base learner'"'"'s prediction component to create a prediction for the category of every element in the subset withheld from training;

storing the predictions as stored predictions;

using the stored predictions over the specified subset and actual categories to assess performance of the base model;

using errors committed by the base model as well as the actual categories to compute a weighting of the examples that should be used as the training data at each child of the category;

storing this distribution to be used as the specified subset at the creating a base learner block;

repeating a creating a block learner block for each child category of the category;

using a top down prediction component that uses a stored output models to predict starting from a top-down by;

predicting membership at a topmost category;

for each category of which the element is predicted to be a member, predicting membership in that category'"'"'s children;

continuing down the hierarchy until no further categories are predicted or the bottom of the hierarchy has been reached;

9. The computer storage medium of claim 8, further comprising computer executable instructions for:

learning bottom-up prediction models for each category in the hierarchy comprising;

starting at a lowest level of the hierarchy

for each element in the pre-categorized training data, creating an extended representation comprising extending a representation of an example with meta-attributes for the category computed using bottom-up prediction of all categories at lower levels than the category;

creating a learner comprising learning a prediction model for the category over a specified subset of the training data using the extended representation and storing this as a bottom-up model for the category to be used in a hierarchical model'"'"'s prediction component;

estimating behavior/performance of the model learned for the category;

partitioning the specified subset of the data into non-overlapping subsets;

for each subset,

giving the learner all but the subset as the training data with the extended representation to obtain a model;

using the model together with the prediction model of the learner to predict the category of every element in the subset withheld from training;

storing the predictions as bottom-up predictions for the category for the elements in the subset;

for any element in a full pre-categorized training set but not in the specified subset given to the learner, using a stored bottom-up model to make predictions for those elements and storing them;

using the stored predictions over the pre-categorized training data and the actual categories to assess the performance of the base model;

using the errors committed by the bottom-up model at the category as well as the actual categories to compute a weighting of the examples that should be used at a parent as the training data in conjunction with errors and the actual categories from the parent'"'"'s other children;

continuing until a root is reached.

10. The computer storage medium of claim 9, further comprising computer executable instructions for;

using a prediction component that uses the stored output models to predict by;

predicting pre-categorized training data as belonging to an initial set of bottom-up categories using predictions over a basic set of example attributes;

starting at the lowest level of the hierarchy that has descendants belonging to the bottom-up categories, predict membership at the category by;

using the bottom-up predictions of all categories below a level of the category'"'"' in the hierarchy to extend the representation of a document with metafeatures;

using the stored bottom-up model for this node in the hierarchy to make the prediction of this category'"'"'s membership using the extended representation and store the prediction as the bottom-up prediction for the category;

continuing up the hierarchy, applying bottom-up models, predicting bottom-up membership and storing the metafeatures for each node in the hierarchy until the root is reached;

starting at the top of the hierarchy,

substituting the extended representation in the top down prediction component and

a stored top-down output models are used at each node in the hierarchy.

11. The computer storage medium of claim 9, wherein the specified subset comprises a weighting of the elements.

12. The computer storage medium of claim 9, wherein the specified subset comprising an inclusion/exclusion decision.

13. The computer storage medium of claim 9, wherein errors comprise assigning data into an improper branch.

14. The computer storage medium of claim 9, wherein extended representation comprises extending the representation of an example with meta-attributes for the category computed using bottom-up predictions of all categories at lower levels than the category.

15. A computer system comprising a processor physically configured according to computer executable instructions for creating a hierarchical learner to electronically classifying data received from a source into a hierarchical tree of categories, the computer executable instructions comprising instructions for:

storing and accessing pre-categorized training data wherein the pre-categorized training data comprises elements and assigned labels;

accessing specified subsets of the pre-categorized training data;

accessing the elements the assigned labels in the specified subsets;

starting at the top of a hierarchy;

creating a base learner to learn a top down model for each category of the hierarchy using a basic representation and a specified subset of the training;

providing the base learner the specified subset of an entire set of pre-categorized training data as input;

storing top down model output from the base learner for a category to be used as part of a prediction model for the hierarchical learner;

estimating performance of the top down model learned for the category comprising;

partitioning the specified subset of the data into non-overlapping subsets;

for each subset, creating a stored output model comprising;

providing the base learner all but that subset as training data to obtain a base model;

using the top down model together with the base learner'"'"'s prediction component to create a prediction for the category of every element in the subset withheld from training;

storing the predictions as stored predictions;

using the stored predictions over the specified subset and actual categories to assess performance of the base model;

using errors committed by the base model as well as the actual categories to compute a weighting of the examples that should be used as the training data at each child of the category;

storing this distribution to be used as the specified subset at the creating a base learner block;

repeating a creating a block learner block for each child category of the category;

using a top down prediction component that uses a stored output models to predict starting from a top-down by;

predicting membership at a topmost category;

for each category of which the element is predicted to be a member, predicting membership in that category'"'"'s children;

continuing down the hierarchy until no further categories are predicted or the bottom of the hierarchy has been reached.

18. The computer system of claim 15, wherein the specified subset comprises a weighting of the elements.

19. The computer system of claim 15, wherein the specified subset comprising an inclusion/exclusion decision.

20. The computer system of claim 15, wherein extended representation comprises extending the representation of an example with meta-attributes for the category computed using bottom-up predictions of all categories at lower levels than the category.

16. The computer system 15, further comprising computer executable instructions for:

learning bottom-up prediction models for each category in the hierarchy comprising;

starting at a lowest level of the hierarchy

for each element in the pre-categorized training data, creating an extended representation comprising extending a representation of an example with meta-attributes for the category computed using bottom-up prediction of all categories at lower levels than the category;

creating a learner comprising learning a prediction model for the category over a specified subset of the training data using the extended representation and storing this as a bottom-up model for the category to be used in a hierarchical model'"'"'s prediction component;

estimating behavior/performance of the model learned for the category;

partitioning the specified subset of the data into non-overlapping subsets;

for each subset,

giving the learner all but the subset as the training data with the extended representation to obtain a model;

using the model together with the prediction model of the learner to predict the category of every element in the subset withheld from training;

storing the predictions as bottom-up predictions for the category for the elements in the subset;

for any element in a full pre-categorized training set but not in the specified subset given to the learner, using a stored bottom-up model to make predictions for those elements and storing them;

using the stored predictions over the pre-categorized training data and the actual categories to assess the performance of the base model;

using the errors committed by the bottom-up model at the category as well as the actual categories to compute a weighting of the examples that should be used at a parent as the training data in conjunction with errors and the actual categories from the parent'"'"'s other children;

continuing until a root is reached.

17. The computer system of claim 16, further comprising computer executable instructions for;

using a prediction component that uses the stored output models to predict by;

predicting pre-categorized training data as belonging to an initial set of bottom-up categories using predictions over a basic set of example attributes;

starting at the lowest level of the hierarchy that has descendants belonging to the bottom-up categories, predict membership at the category by;

using the bottom-up predictions of all categories below a level of the category'"'"' in the hierarchy to extend the representation of a document with metafeatures;

using the stored bottom-up model for this node in the hierarchy to make the prediction of this category'"'"'s membership using the extended representation and store the prediction as the bottom-up prediction for the category;

continuing up the hierarchy, applying bottom-up models, predicting bottom-up membership and storing the metafeatures for each node in the hierarchy until the root is reached;

starting at the top of the hierarchy,

substituting the extended representation in the top down prediction component and

a stored top-down output models are used at each node in the hierarchy.