Hierarchical Maximum Margin Learning for Multi-Class Classification

Jian-Bo Yang, Ivor W. Tsang

TL;DR

This paper introduces a novel method for learning hierarchical class structures to improve multi-class classification efficiency and accuracy. By proposing a "maximum separating margin" criterion, the authors develop an algorithm that constructs a binary tree representing class relationships, leading to significant speedups and competitive accuracy on large-scale datasets.

What Problem Does This Paper Address?

Traditional multi-class classification methods, like one-vs-one (1vs1) and one-vs-rest (1vsR), decompose a problem with $c$ classes into $O(c^2)$ or $O(c)$ binary classification problems. While effective for a small number of classes, these approaches become computationally prohibitive when dealing with datasets having hundreds or thousands of classes, especially during prediction where all binary classifiers might need to be evaluated. This paper addresses the challenge of efficiently classifying data with a massive number of classes by learning an explicit hierarchical structure among the classes. This structure allows for a more efficient, tree-traversal-based prediction process with a computational cost of $O(\log c)$.

Methods

The core of the proposed method is learning a binary hierarchical tree structure for the classes. The authors introduce a Maximum Separating Margin (MSM) model to determine how to split an internal node (representing a group of classes) into two child nodes.

  1. Separating Margin Criterion: The key idea is to ensure that the two groups of classes represented by sibling nodes are as separable as possible. This is quantified by the "separating margin," which is the minimum distance between the decision boundaries of the two class groups.
  2. MSM Model: This model aims to find the optimal split of classes for an internal node by maximizing this separating margin. Initially formulated as a mixed-integer programming (MIP) problem, it's computationally expensive.
  3. Convex Relaxation and MKL: To make the problem tractable, the MIP is relaxed into a convex optimization problem. This is achieved by introducing auxiliary variables and reformulating it within the Multiple Kernel Learning (MKL) framework. This allows leveraging existing MKL solvers.
  4. Cutting Plane Method: To handle the large number of potential constraints arising from the relaxation, a cutting plane algorithm is used to iteratively refine the set of active constraints, improving efficiency.
  5. Tree Construction: The MSM model is applied recursively from the root node downwards, splitting each internal node until all leaf nodes represent individual classes, thus constructing the entire class structure tree.

Datasets

The paper evaluates the proposed method on several real-world, large-scale datasets:

  • svmguide4
  • vowel
  • segment
  • satimage
  • usps
  • news20
  • sector
  • Caltech 101

For Caltech 101, a specific preprocessing step was followed, excluding the background class and using SIFT features with a dense grid sampling strategy.

Key Insights and Ideas

  • Maximizing Separability is Key: The intuition that classes likely to be confused should be grouped together is formalized by maximizing the separating margin between sibling nodes. This is a more direct approach to learning class relationships than relying on confusion matrices from other methods.
  • MKL as a Powerful Tool for Structure Learning: The reformulation of the complex optimization problem into an MKL framework highlights the versatility of MKL in solving challenging learning tasks beyond standard kernel selection.
  • Convex Relaxation Enables Scalability: The ability to transform a difficult integer programming problem into a solvable convex one is crucial for applying the method to large datasets.
  • Hierarchical Structure for Efficiency: The learned tree structure directly translates to significant prediction speedups, making it practical for scenarios with a vast number of classes.

Key Results

  • Accuracy: The proposed MSM method achieved the best accuracy on 9 out of 13 dataset settings tested. For the remaining datasets, it was ranked among the top 2 or 3 methods.
  • Efficiency: The class structure learning methods, including MSM, were significantly faster than 1vs1 and 1vsR methods. They were 2-200 times faster than 1vs1 and 1.3-50 times faster than 1vsR.
  • Qualitative Analysis: Figure 1 demonstrates that MSM effectively groups similar-looking digits (e.g., "8" and "9") in the USPS dataset, aligning with the method's motivation. Other methods like I-BWG showed some success, but FT performed poorly due to its random nature, and CPT was better but still missed some groupings.

Limitations and Future Work

  • Computational Cost of MKL: While the cutting plane method helps, solving the MKL problem can still be computationally intensive, especially for very large numbers of classes. The paper notes that for linear or polynomial kernels, kernel matrix storage can be avoided, making MKL more efficient.
  • Graph Cut for Optimal z: The paper uses a maximum spanning tree algorithm (Kruskal's) as a graph cut method to determine the optimal class assignments for internal nodes. While effective, exploring other graph cut algorithms could potentially yield further improvements.
  • Future Work: The paper implicitly suggests that further exploration of different kernel types and optimization strategies within the MKL framework could enhance performance. The effectiveness of the learned structure for other machine learning tasks beyond classification could also be an avenue for future research.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yang2011hierarchical,
  author = {Jian-Bo Yang and Ivor W. Tsang},
  title = {{Hierarchical Maximum Margin Learning for Multi-Class Classification}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=WUNrMbBYwE},
}
Figure