A Formal Analysis of Stopping Criteria of Decomposition Methods for Support Vector Machines  

Oleh:

Lin, Chih-Jen

Jenis: Article from Journal - ilmiah internasional
Dalam koleksi: IEEE Transactions on Neural Networks vol. 13 no. 5 (2002), page 1045-1052.
Topik: vectors; decomposition; support vector machines

Ketersediaan

Perpustakaan Pusat (Semanggi) Nomor Panggil: II36.7A Non-tandon: 1 (dapat dipinjam: 0) Tandon: tidak ada

Lihat Detail Induk

Isi artikel

In a previous paper, the author (2001) proved the convergence of a commonly used decomposition method for support vector machines (SVM s). 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.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali