A simple decomposition algorithm for support vector machines with polynomial-time convergence

doi:10.1016/j.patcog.2006.12.024

A simple decomposition algorithm for support vector machines with polynomial-time convergence

2007-09-01

6

PRE

AI

DOI：10.1016/j.patcog.2006.12.024

Original

Original request for help

Save

Abstract

En 中文

Support vector machines (SVMs) are a new and important toot in data classification. Recently much attention has been devoted to large scale data classifications where decomposition methods for SVMs play an important role. So far. several decomposition algorithms for SVMs have been proposed and applied in practice. The algorithms proposed recently and based on rate certifying pair/set provide very attractive features compared with many other decomposition algorithms. They converge not only with finite termination but also in polynomial time. However, it is difficult to reach a good balance between low computational cost and fast convergence. In this paper, we propose a new simple decomposition algorithm based on a new philosophy on working set selection. It has been proven that the working set selected by the new algorithm is a rate certifying set. Further, compared with the existing algorithms based on rate certifying pair/set, our algorithm provides a very good feature in combination of lower computational complexity and faster convergence. (c) 2007 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.

Keywords:

support vector machines

decomposition methods

convergence

statistical learning theory

pattern recognition

A simple decomposition algorithm for support vector machines with polynomial-time convergence

Abstract

AI Summary

Journal

Organization

Cited Papers