Multilabel Classification over Category Taxonomies
Lijuan Cai · 2008
Multilabel classification is the task of assigning a pattern to one or more classes or categories from a pre-defined set of classes. It is a crucial tool in knowledge and content management. Standard machine learning techniques such as Support Vector Machines (SVMs) and Perceptron have been successfully applied to this task. How-ever, many real-world classification problems involve large numbers of overlapping categories that are arranged in a hierarchy or taxonomy. This poses a challenge to learning algorithms as they ignore the class hierarchies thereby losing valuable infor-mation. In this thesis, we propose to systematically incorporate prior knowledge on category taxonomy directly into the learning architecture. We present two methods, hierarchi-cal SVM learning and hierarchical Perceptron learning. Both methods take a ranking view of the multilabel problem by focusing on ranking category relevances. In the hierarchical SVM, the hierarchical learning problem is expressed as a joint large mar-gin formulation that simultaneously learns the discriminant functions of each class. As the resulting optimization problem can be prohibitively large, we also present a variable selection algorithm to efficiently solve it. In the hierarchical Perceptron method, the construction of weight vectors and the update rule are made to capture the category taxonomy. Both methods can leverage kernel techniques, work with arbitrary directed acyclic graph taxonomy, and be applied to general settings where categories can be characterized by attributes. We also present an automatic approach to learn a taxonomy if one isn’t available. Our approach is adapted from the hier-archical agglomerative clustering algorithm. The learned hierarchy can then be used in existing hierarchical classification approaches. Extensive experiments demonstrate the performance advantage of our approaches.