Multi-parametric Solution-path Algorithm for Instance-weighted Support Vector Machines

Details Multi-parametric Solution-path Algorithm for Instance-weighted Support Vector Machines Multi-parametric Solution-path Algorithm for Instance-weighted Support Vector Machines

2010-09-24

arxiv.org/abs/1009.4791v2

Computer Science

Learning

Submitted to Journal of Machine Learning Research

Scientific paper

An instance-weighted variant of the support vector machine (SVM) has attracted considerable attention recently since they are useful in various machine learning tasks such as non-stationary data analysis, heteroscedastic data modeling, transfer learning, learning to rank, and transduction. An important challenge in these scenarios is to overcome the computational bottleneck---instance weights often change dynamically or adaptively, and thus the weighted SVM solutions must be repeatedly computed. In this paper, we develop an algorithm that can efficiently and exactly update the weighted SVM solutions for arbitrary change of instance weights. Technically, this contribution can be regarded as an extension of the conventional solution-path algorithm for a single regularization parameter to multiple instance-weight parameters. However, this extension gives rise to a significant problem that breakpoints (at which the solution path turns) have to be identified in high-dimensional space. To facilitate this, we introduce a parametric representation of instance weights. We also provide a geometric interpretation in weight space using a notion of critical region: a polyhedron in which the current affine solution remains to be optimal. Then we find breakpoints at intersections of the solution path and boundaries of polyhedrons. Through extensive experiments on various practical applications, we demonstrate the usefulness of the proposed algorithm.

Affiliated with

Also associated with

No associations

Rating

Multi-parametric Solution-path Algorithm for Instance-weighted Support Vector Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multi-parametric Solution-path Algorithm for Instance-weighted Support Vector Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-parametric Solution-path Algorithm for Instance-weighted Support Vector Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-274145