On topics of multi-category classification with large margin based methods.

Abstract

In multi-class classification, the cost for misclassification may vary over each class. This is a situation in structured learning, where the focus is how to leverage dependency among different classes to enhance the performance of classification that ignores such dependency structure. Examples include hierarchical classification, sequence alignment, and natural language processing, among others. This paper develops a framework for multi-class margin classification with un-equal (equal) cost. Within the framework, structured learning is formulated, where the dependency is taken into account through the cost of misclassification. This framework is implemented for support vector machines. An application to hierarchical classification is discussed. In addition, some simulations are performed, indicating that the proposed methodology achieves the desired objective. As a special case of multi-classification, in hierarchical classification, class label is structured in that each label value corresponds to one non-root node in a tree, where the inter-class relationship is specified by directed paths of the tree. In such a situation, the focus has been on how to leverage the inter-class relationship to enhance the performance of flat classification ignoring such dependency. This is critical when the number of classes becomes large relative to the size of sample. This paper considers single-path hierarchical classification, where only one path is permitted from the root to one node. A large margin method is introduced based on a new concept of generalized margins with respect to hierarchy. For implementation, we consider support vector machines and $\psi$-learning. Numerical and theoretical analyses suggest that the proposed method achieves the desired objective and outperforms its competitors, particularly its flat counterpart. Finally, an application to gene function discovery is examined.