Introduction
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.