Frank-Wolfe algorithm for learning SVM-type multi-category classifiers

被引：0

作者：

Tajima K. ^{[1
]}

Hirohashi Y. ^{[1
]}

Zara E. ^{[1
]}

Kato T. ^{[1
]}

机构：

[1] Graduate School of Science and Technology, Gunma University, Kiryu-shi

来源：

IEICE Transactions on Information and Systems | 2021年 / 104卷 / 11期

基金：

日本学术振兴会;

关键词：

Convex optimization; Dual problem; Frank-Wolfe; Multi-category classification; SVM;

D O I：

10.1587/TRANSINF.2021EDP7025

中图分类号：

学科分类号：

摘要：

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. Copyright © 2021 The Institute of Electronics, Information and Communication Engineers

引用

页码：1923 / 1929

页数：6

共 20 条

[1]

Bertsekas D.P., Nonlinear Programming, (1999)

[2]

Chu D., Lu R., Li J., Yu X., Zhang C., Tao Q., Optimizing top-k multiclass SVM via semismooth newton algorithm, IEEE Transactions on Neural Networks and Learning Systems, 29, 12, pp. 6264-6275, (2018)

[3]

Crammer K., Singer Y., On the algorithmic implementation of multiclass kernel-based vector machines, J. Mach. Learn. Res, 2, pp. 265-292, (2002)

[4]

Felzenszwalb P.F., Girshick R.B., McAllester D., Ramanan D., Object detection with discriminatively trained part-based models, IEEE Trans. Pattern Anal. Mach. Intell, 32, 9, pp. 1627-1645, (2010)

[5]

Frank M., Wolfe P., An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3, 1-2, pp. 95-110, (1956)

[6]

Hare S., Golodetz S., Saffari A., Vineet V., Cheng M.-M., Hicks S.L., Torr P.H.S., Struck: Structured output tracking with kernels, IEEE Trans. Pattern Anal. Mach. Intell, 38, 10, pp. 2096-2109, (2016)

[7]

Huber P.J., Robust estimation of a location parameter, The Annals of Mathematical Statistics, 35, 1, pp. 73-101, (1964)

[8]

Jaggi M., Revisiting Frank-Wolfe: Projection-free sparse convex optimization, Proceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research, 28, 1, pp. 427-435, (2013)

[9]

Joachims T., A support vector method for multivariate performance measures, Proceedings of the 22nd international conference on Machine learning - ICML’05, pp. 377-384, (2005)

[10]

Joachims T., Finley T., John Yu C.-N., Cutting-plane training of structural SVMs, Machine Learning, 77, 1, pp. 27-59, (2009)

← 1 2 →