Multicycle disassembly-based decomposition algorithm to train multiclass support vector machines

doi:10.1016/j.patcog.2023.109479

2023-08-01

PRE

Tong Gao

Hao Chen *

DOI：10.1016/j.patcog.2023.109479

原文链接

原文求助

摘要

En 中文

Employing the classic optimization solver to train a multiclass support vector machine (SVM) requires prohibitive training time as the sample size and number of categories increase. It has been proposed to develop the corresponding decomposition algorithm (DA) as it is efficient for training SVMs. How-ever, the dual problem of multiclass SVM comprises complex constraints that complicate DA design, so no corresponding DA has yet been developed. We propose a multicycle disassembly-based DA (MCD-DA) to efficiently solve the training problem of multiclass SVM. First, a graph model is constructed to re -express the constraints in multiclass SVM. Then, the original complex feasible region is partitioned into several simple sub-feasible regions, and multiple cycle-based disassembly strategies are designed to up-date the working variables analytically within each specific sub-feasible region. We mathematically verify that MCD-DA can stop within a finite number of cycle disassemblies and reach the tau-optimal solution satisfying relaxed Karush-Kuhn-Tucker conditions. Remarkably, MCD-DA as a universal decomposition algorithm can be used to solve many other SVM variants, including C-SVM, v-SVM, and one-class SVM. Experimental results using six UCI datasets demonstrate that MCD-DA outperforms typical optimization algorithms for more sample cases. (c) 2023 Published by Elsevier Ltd.

Keyword:

Multicycle disassembly -based

decomposition algorithm

Multiclass support vector machine

Decomposition algorithm

Support vector machine training