In a weighted support vector machine (WSVM), each training instance has its own weight. So, for example, in nonstationary data analysis, earlier instances may have less weight than later ones, or in heteroscedastic data modeling, larger weights are assigned to data points with smaller noise variance. Such SVMs introduce a major computational bottleneck because of the need to recompute the SVM for each new instance.

This paper develops an algorithm that allows the efficient updating of the solutions for a WSVM. The method is a modification of the conventional solution path algorithm to allow for more than one or two weights. For a change in weights from C1 to C2, one has a linear path in the weight space connecting the two weights in the space of weights. These paths can be represented in terms of a parametric representation of instance weights. The weight space can be decomposed into a series of polyhedral regions in each of which the current solution remains optimal. Using the parametric representation enables the method to detect the breakpoints at the intersection of the solution path and the boundaries of these polyhedral regions. At such a breakpoint, the solution will change. The algorithm is described in detail, with a brief discussion of its computational complexity. I note that there is an issue related to the number of break points that are encountered, which depends on the sensitivity of the model.

The authors give some experimental results on the application of the method to various machine learning tasks, including classification, regression, ranking, and transduction, that show the efficacy of their method.