System and method for inducing a top-down hierarchical categorizer

• US 6,990,485 B2
• Filed: 08/02/2002
• Issued: 01/24/2006
• Est. Priority Date: 08/02/2002
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Suermondt, Henri Jacques, Forman, George H.
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/211,840
• Publication Number:
  US 20040024769A1
• Time in Patent Office: 1,271 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206
• US Class Current: 707/737
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method of inducing a top-down hierarchical categorizer includes providing a set of labeled training items. Each labeled training item includes an associated label representing a single category assignment for the training item. A set of unlabeled training items is provided. A prior is associated with the set of unlabeled training items that is independent of any particular feature contained in the unlabeled training items. The prior represents a plurality of possible category assignments for the set of unlabeled training items. A top-down hierarchical categorizer is induced with a machine learning algorithm based on the set of labeled training items, the set of unlabeled training items, and the prior.

Claims

1. A computer-implemented method for inducing a top-down hierarchical categorizer, comprising:

providing a set of labeled training items, each labeled training item including an associated label representing a single category assignment for the training item;

providing a set of unlabeled training items;

associating a prior with the set of unlabeled training items that is independent of any particular feature contained in the unlabeled training items, the prior representing a plurality of possible category assignments for the set of unlabeled training items; and

inducing a top-down hierarchical categorizer with a machine learning algorithm based on the set of labeled training items, the set of unlabeled training items, and the prior.

2. The method of claim 1, wherein the step of inducing a top-down hierarchical categorizer comprises:

determining whether the possible category assignments for the set of unlabeled training items all map to a single category; and

using the sot of unlabeled training items as training examples for the single category.

3. The method of claim 1, wherein the unlabeled training items are used as positive training examples for a category.

4. The method of claim 1, wherein the unlabeled training items are used as negative training examples for a category.

5. The method of claim 1, wherein the prior comprises probabilistic information.

6. The method of claim 5, wherein the probabilistic information represents a probability for each of the possible category assignments that the unlabeled training items fall under that category.

7. The method of claim 1, wherein the machine learning algorithm is selected from the group consisting of:

Naï

ve Bayes, Support Vector Machines, k-Nearest Neighbors, Neural Networks, and C4.5.

8. A computer-implemented system for inducing a top-down hierarchical categorizer based on labeled training items and unlabeled training items, each labeled training item including a plurality of features and a label identifying a single category assignment, each unlabeled training item including a plurality of features and prior information representing a plurality of possible category assignments for the unlabeled training item, the system comprising:

a plurality of categories organized in a hierarchy of categories; and

an inducer for inducing a plurality of categorizers corresponding to the plurality of categories, the inducer configured to induce each categorizer based on the features of labeled training items assigned to categories under that categorizer and based on the features of unlabeled training items with prior information representing category assignments that map to a category under that categorizer.

9. The system of claim 8, wherein the unlabeled training items are used as positive training examples for at least one of the categories in the hierarchy of categories.

10. The system of claim 8, wherein the unlabeled training items are used as negative training examples for at least one of the categories in the hierarchy of categories.

11. The system of claim 8, wherein the prior information for each unlabeled training item comprises probabilistic information.

12. The system of claim 11, wherein the probabilistic information for each unlabeled training item represents a probability for each of the possible category assignments that the unlabeled training item falls under that category.

13. The system of claim 8, wherein the inducer induces the plurality of categorizers based on a general-purpose induction algorithm.

14. The system of claim 13, wherein the general-purpose induction algorithm is selected from the group consisting of Naï

ve Bayes, Support Vector Machines, k-Nearest Neighbors, Neural Networks, and C4.5.

15. A computer-implemented system for inducing a top-down hierarchical categorizer from a set of labeled training items and a set of unlabeled training items, each labeled training item including an associated label representing a single category assignment for the training item, the system comprising:

means for associating a prior with each unlabeled training item that is independent of any particular feature contained in the unlabeled training item, the prior representing a plurality of possible category assignments for the unlabeled training item; and

means for inducing a plurality of categorizers based on a machine learning algorithm, the set of labeled training items, the set of unlabeled training items, and the priors associated with the unlabeled training items, the plurality of categorizers including a root categorizer and a plurality of sub-categorizers organized in a tree structure.

16. The system of claim 15, wherein the means for inducing comprises:

means for determining whether the possible category assignments for a first prior all map to a common category; and

using the training item associated with the first prior as a training example for the common category.

17. The system of claim 15, wherein at least one of the unlabeled training items is used as a positive training example for a category.

18. The system of claim 15, wherein at least one of the unlabeled training items is used as a negative training example for a category.

19. The system of claim 15, wherein at least one of the priors comprises probabilistic information.

20. The system of claim 19, wherein the probabilistic information includes a probability for each of the possible category assignments that the unlabeled training item falls under that category.

21. The system of claim 15, wherein the machine learning algorithm is selected from the group consisting of Naï

ve Bayes, Support Vector Machines, k-Nearest Neighbors, Neural Networks, and C4.S.

22. A computer-readable medium having computer-executable instructions for performing a method of inducing a top-down hierarchical categorizer based on labeled training items and unlabeled training items, each labeled training item including a label identifying a single category assignment, each unlabeled training item including prior information representing a plurality of possible category assignments for the unlabeled training item, the method comprising:

providing a plurality of categories organized in a hierarchy of categories;

inducing a plurality of categorizers corresponding to the plurality of categories; and

associating a set of features with each category based on features of labeled training items assigned to that category and based on features of unlabeled training items with prior information representing category assignments that map to that category.

23. The computer-readable medium of claim 22, wherein the method further comprises:

using the unlabeled training items as positive training examples for at least one of the categories in the hierarchy of categories.

24. The computer-readable medium of claim 22, wherein the method further comprises:

using the unlabeled training items as negative training examples for at least one of the categories in the hierarchy of categories.

25. The computer-readable medium of claim 22, wherein the prior information for at least one unlabeled training item comprises probabilistic information.

26. The computer-readable medium of claim 25, wherein the probabilistic information represents a probability for each of the possible category assignments that the unlabeled training item falls under that category.

27. The computer-readable medium of claim 22, wherein the step of inducing a plurality of categorizers further comprises:

inducing a plurality of categorizers corresponding to the plurality of categories based on a general-purpose induction algorithm.

28. The computer-readable medium of claim 27, wherein the general-purpose induction algorithm is selected from the group consisting of Naï

ve Bayes, Support Vector Machines, k-Nearest Neighbors, Neural Networks, and C4.5.

29. The computer-readable medium of claim 22, wherein the method further comprises:

restructuring the hierarchy of categories based on the prior information.