A new method is proposed here for obtaining a hierarchical class decomposition that is based on a max-cut formulation, searches the maximum total distance between two class partitions and extends SVM to handle multi-class problems.

In a max-cut problem, an undirected graph with nonnegative edge weights is partitioned into two groups. The cuts between these two groups have the maximum weight. The max-cut problem can be represented using an integer quadratic programming formulation, which is NP-hard. The combination of the feasible solutions grows exponentially as the number of nodes increases. Goemans and Williamson proposed that the original max-cut problem can be relaxed into a constrained quadratic problem and be solved using a semi-definite programming. The interor point method extended by Nesterov and Nemirovskii provides a computationally efficient method for solving the semi-definite problem. The relaxed max-cut problem solved using SDP achieves optimal or near optimal results and has an expected value of 87.7% of the optimal max-cut.

The proposed max-cut hierarchical output space decomposition method searches the maximum total distance between the two class partitions. The original class samples are treated as an undirected graph where node $n_i$ represent class $i$ and the non-negarive weight: $w_{ij}$ is the average Kullback-Leibler distance between the density function of class $i$ and class $j$.

It has been shown that HSVM uses distance measures to exploit the natural class groupings, the hierarchical structure results in a fast and intuitive SVM training process that requires little runing and gives high classification accuracy and good generalization.

HSVM Resouraces

This HSVM matlab code is distributed under GNU license. HSVM is a MATLAB code that has been tested using MATLAB 6.5 on RedHat and SUSE linux. It requires CSR training and testing data format which can be created using CSRinput.m, which is included in the HSVM package.
  • IGARSS 04 paper
    • Y. Chen, M.M. Crawford and J. Ghosh. "Integrating Support Vector Machines in a Hierarchical Output Space Decomposition Framework", IEEE International Geoscience and Remote Sensing Symposium. Alaska AK. Sep. 2004. Volume II: pp. 949 - 952
  • HSVM Package
  • posted by Yangchi Chen