  Due to myriads of classes, designing accurate and efficient classifiers
becomes very challenging for multi-class classification. Recent research has
shown that class structure learning can greatly facilitate multi-class
learning. In this paper, we propose a novel method to learn the class structure
for multi-class classification problems. The class structure is assumed to be a
binary hierarchical tree. To learn such a tree, we propose a maximum separating
margin method to determine the child nodes of any internal node. The proposed
method ensures that two classgroups represented by any two sibling nodes are
most separable. In the experiments, we evaluate the accuracy and efficiency of
the proposed method over other multi-class classification methods on real world
large-scale problems. The results show that the proposed method outperforms
benchmark methods in terms of accuracy for most datasets and performs
comparably with other class structure learning methods in terms of efficiency
for all datasets.
