Display Settings:

Format

Send to:

Choose Destination
See comment in PubMed Commons below
IEEE Trans Neural Netw. 2002;13(5):1045-52. doi: 10.1109/TNN.2002.1031937.

A formal analysis of stopping criteria of decomposition methods for support vector machines.

Author information

  • Dept. of Comput. Sci. and Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan.

Abstract

In a previous paper, the author (2001) proved the convergence of a commonly used decomposition method for support vector machines (SVMs). However, there is no theoretical justification about its stopping criterion, which is based on the gap of the violation of the optimality condition. It is essential to have the gap asymptotically approach zero, so we are sure that existing implementations stop in a finite number of iterations after reaching a specified tolerance. Here, we prove this result and illustrate it by two extensions: /spl nu/-SVM and a multiclass SVM by Crammer and Singer (2001). A further result shows that, in final iterations of the decomposition method, only a particular set of variables are still being modified. This supports the use of the shrinking and caching techniques in some existing implementations. Finally, we prove the asymptotic convergence of a decomposition method for this multiclass SVM. Discussions on the difference between this convergence proof and the one in another paper by Lin are also included.

PMID:
18244502
[PubMed]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for IEEE Engineering in Medicine and Biology Society
    Loading ...
    Write to the Help Desk