Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Currently I have a data set which are known to belong to two classes, and would like to build a classifier using SVM. However, there exist different confidence levels for this data set. For example, for some data points, we are very certain that they belong to class 1; while for some data points, we think they should belong to class 1 but not so certain. We can quantify this kind of confidence information as weight. But how can we cast these weight information into the training process? Does LibSVM support this type of training?

share|improve this question

3 Answers 3

up vote 2 down vote accepted

What you are asking doesn't really fall into the framework of the SVM. There is some work on incorporating prior knowledge into SVMs (see e.g. here but these approaches are generally not on an example by example basis.

I can think of one way in which you could approach this, if you have a lot of samples. You could use the weights as probabilities for inclusion in random subsets. You would then learn the SVM on each subset, and your final classifier is then a linear combination of these subsets. This is a variation on bootstrapping, which normally works over subsets of the features (see e.g. here, and might be quite interesting to analyse.

[Edit 1]:

Based on the answers from Jeff and Dikran it occured to me that you can just incorporate into the SVM objective. Normally the primal form looks like:

$\min_{\mathbf{w},\mathbf{\xi}, b } \left\{\frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \right\}$

subject to (for any $i=1,\dots n$)

$y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i, ~~~~\xi_i \ge 0 .$

but you could just include another vector of confidence values, e.g. $0 < \delta_i \leq 1, ~~~~i=1,\dots n$:

$\min_{\mathbf{w},\mathbf{\xi}, b } \left\{\frac{1}{2} \|\mathbf{w}\|^2 + \frac{C}{\delta_i} \sum_{i=1}^n \xi_i \right\}$

subject to (for any $i=1,\dots n$)

$y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i, ~~~~\xi_i \ge 0 .$

which would mean that instances with low probability would receive a greater penalty in the objective. Note that now the $C$ parameter performs two roles - as a regulariser and as a scaling factor for the confidence scores. This may cause its own problems, so it might be better to split it into two parts, but then of course you would have an extra hyperparameter to tune.

[Edit 2]:

This can be done with libSVM (MATLAB and Python interfaces are included). There is also code available in several languages for the SMO algorithm which can solve the SVM problem efficiently. Alternatively you could use an optimisation package, such as quadprog in matlab or CVX, to write a custom solver.

share|improve this answer
1  
An anonymous user has argued that libsvm would be able to do this. See here: Weights for data instances. –  gung Mar 6 '13 at 0:13
    
I've updated the answer, thanks –  tdc Mar 6 '13 at 8:20

A paper that might be of interest is "Estimating a Kernel Fisher Discriminant in the Presence of Label Noise" by Lawrence and Scholkopf, which deals with KFD rather than SVM, but the two classifiers are closely related and will give similar results for most problems. Note that the KFD is equivalent to kernel ridge regression, and a 2-norm SVM is equivalent to KRR computed on only the support vectors, so it may be possible to port this approach to SVM.

In general dealing with label noise is easiest when you have a fully probabilistic classifier, so as tdc suggests, the SVM is probably not the best approach. It might be worth looking at semi-supervised versions of the SVM, as the problem is similar in that in both cases you only have uncertain information about some of the labels (very uncertain for semi-supervised methods). The approach tdc suggests is probably worth trying, or alternatively present each pattern twice, with different labels each time, with weights $p$ and $1-p$.

share|improve this answer

There is a technique called weighted SVM (see ref below), that appears to be supported by LibSVM (which I've never actually used). Weighted SVM solves the problem of having two classes with unequal training data. In this case, classification is biased towards the class with more observations. To compensate, W-SVM sets the penalty parameter C in proportion to the size of the class.

The same idea can be applied to confidence information by giving each observation its own C; though I'm not sure if LibSVM supports this. In this sense, you give a larger penalty to observations in which you have a lot of confidence, and a small penalty to observations with which you have little confidence. The end result is that the hyperplane is determined by weighting each observation by its confidence interval, as you desire.

Huang, & Du (2005). Weighted support vector machine for classification with uneven training class sized. Proc. of the 4th Int. Conf. on Machine Learning and Cybernetics, 4365-4369. Retrieved from http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1527706

share|improve this answer
    
Huang and Du were by no means the first to come up with this idea. Setting the penatly in proportion to the size of the class has some theoretical justification, however it breaks down with finite samples, so it is better to choose the weighting factor by cross-validation (or minimising a generalisation bound etc.) However, in this case, I don't think this is what was meant by weight, but instead is to do with the confidence of the sign of the label. –  Dikran Marsupial Jan 30 '12 at 15:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.