Frank-Wolfe Algorithm for Learning SVM-Type Multi-Category Classifiers

Kenya TAJIMA  Yoshihiro HIROHASHI  Esmeraldo ZARA  Tsuyoshi KATO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E104-D    No.11    pp.1923-1929
Publication Date: 2021/11/01
Publicized: 2021/08/11
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2021EDP7025
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
Keyword: 
SVM,  convex optimization,  Frank-Wolfe,  dual problem,  multi-category classification,  

Full Text: PDF(459.9KB)>>
Buy this Article



Summary: 
The multi-category support vector machine (MC-SVM) is one of the most popular machine learning algorithms. There are numerous MC-SVM variants, although different optimization algorithms were developed for diverse learning machines. In this study, we developed a new optimization algorithm that can be applied to several MC-SVM variants. The algorithm is based on the Frank-Wolfe framework that requires two subproblems, direction-finding and line search, in each iteration. The contribution of this study is the discovery that both subproblems have a closed form solution if the Frank-Wolfe framework is applied to the dual problem. Additionally, the closed form solutions on both the direction-finding and line search exist even for the Moreau envelopes of the loss functions. We used several large datasets to demonstrate that the proposed optimization algorithm rapidly converges and thereby improves the pattern recognition performance.


open access publishing via