Method for multi-class, multi-label categorization using probabilistic hierarchical modeling

• US 20050187892A1
• Filed: 02/09/2004
• Published: 08/25/2005
• Est. Priority Date: 02/09/2004
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Goutte, Cyril, Gaussier, Eric
• Granted Patent: US 7,139,754 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for categorizing a set of objects includes defining a set of categories in which at least one category in the set is dependent on another category in the set; organizing the set of categories in a hierarchy that embodies any dependencies among the categories in the set; for each object, assigning to the object one or more categories l₁ . . . l_P where l_iε{1 . . . L} from a set {1 . . . L} of possible categories, wherein the assigned categories represent a subset of categories for which the object is relevant; defining a new set of labels z comprising all possible combinations of any number of the categories, zε{{1},{2}, . . . {L},{1,2}, . . . {1,L},{2,3}, . . . {1,2,3}, . . . {1,2, . . . L}}, such that if an object is relevant to several categories, the object must be assigned the label z corresponding to the subset of all relevant categories; and assigning to the object the several categories and the subcategories of the several categories.

Claims

1. A method for categorizing a set of objects, comprising:

defining a set of categories in which at least one category in the set is dependent on another category in the set;

organizing the set of categories in a hierarchy that embodies any dependencies among the categories in the set;

for each object, assigning to the object one or more categories l₁ . . . l_P where l<sub>iε

{1</sub> . . . L} from a set {1 . . . L} of possible categories, wherein the assigned categories represent a subset of categories for which the object is relevant;

defining a new set of labels z comprising all possible combinations of any number of the categories, zε

{{1},{2}, . . . {L},{1,2}, . . . {1,L},{2,3}, . . . {1,2,3}, . . . {1,2, . . . L}}, such that if an object is relevant to several categories, the object must be assigned the unique label z corresponding to the subset of all relevant categories; and

assigning to the object the several categories and the subcategories of the several categories.

2. The method of claim 1, wherein an object comprises a document d generated by co-occurrence of words within the document.

3. The method of claim 2, wherein the hierarchy is generated by:

for each document d, choosing a document category α

according to the probability P(α

|d)∝

P(d|α

)P(α

);

selecting a label v according to the category-conditional probability P(v|α

);

selecting a word in the document according to a label-specific word distribution P(w|v); and

restricting P(v|α

) to give positive probability only to labels that are above the category in the hierarchy.

4. The method of claim 1, wherein an object is expressed as a vector in an arbitrary vector space.

5. The method of claim 1, wherein the set of categories further includes an independent category for including objects that fit none of the other categories in the set.

6. The method of claim 1, wherein the hierarchy comprises a directed acyclic graph.

7. The method of claim 1, wherein the hierarchy organizes the sets of categories which embodies dependencies between the categories.

8. The method of claim 3, wherein the category-conditional probability is defined as a uniform distribution over all nodes above the first class.

9. The method of claim 3, wherein the category-conditional probability is defined such that the probability is inversely proportional to a distance of a node to a first class.

10. The method of claim 3, wherein the category-conditional probability of a node is proportional to the number of documents that belong to the node.