執行多類SVM的最佳方法


18

我知道SVM是二進制分類器。我想將其擴展到多類SVM。哪種方法是最好的,也許是最簡單的?

代碼:在MATLAB中

   u=unique(TrainLabel); 
    N=length(u); 
    if(N>2)    
        itr=1;    
        classes=0;   
        while((classes~=1)&&(itr<=length(u)))   
            c1=(TrainLabel==u(itr));    
            newClass=double(c1); 
            tst = double((TestLabel == itr));
            model = svmtrain(newClass, TrainVec, '-c 1 -g 0.00154');  
            [predict_label, accuracy, dec_values] = svmpredict(tst, TestVec, model);    
            itr=itr+1;   
        end
        itr=itr-1;
    end

該如何改善?

16

There are a lot of methods for multi-class classification. Two classic options, which are not SVM-specific are:

  1. One-vs-all (OVA) classification:
    Suppose you have classes A, B, C, and D. Instead of doing a four way classification, train up four binary classifiers: A vs. not-A, B vs. not-B, C vs. not-C, and D vs. not-D. Then, pick either the positive class that's "best" (e.g., furtherest from the margin across all four runs). If none of the classifications are positive (i.e., they're all not-X), pick the "opposite" of class that's worst (e.g., closest to the margin).

  2. All-vs-All:
    Train all possible pairs of classifications. Rank the classes by some factor (e.g., # of times selected), and pick the best.

Which works best has been contentious: Duan and Keerthi have an empirical study that suggests a specific all-vs-all method, while Rifkin and Klautau argue for a one-vs-all scheme. There are even schemes where one learns error-correcting codes describing the class labels, instead of the labels themselves.

Good luck!

Edit: What you really want, particularly for OVA, is the posterior probability of each class. For some methods, like Naive Bayes, that's trivial to get out. SVMs typically don't give you probabilities, but there are ways to compute them. See John Platt's 1999 paper "Probabilistic Outputs for Support Vector Machines..."


6

Let me add that there is work on extending SVMs to multiple classes (as opposed to the methods Matt Krause describes that are decomposition into several binary classification tasks). One important work is: On the Algorithmic Implementation of Multiclass Kernel-based Vector Machine