An exact solver for the Weston-Watkins SVM subproblem
An exact solver for the Weston-Watkins SVM subproblem
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Yutong Wang;C. Scott
中科院分区：
文献类型：
--
作者：
Yutong Wang;C. Scott
最近的经验证据表明，Weston-Watkins支持向量机是二进制SVM的最佳多类扩展之一。当前最先进的求解器重复地近似使用迭代策略来解决特定的子问题。在这项工作中，我们提出了一种算法，解决了子问题，正是使用一种新的reparametrization的韦斯顿-沃特金斯对偶问题。对于线性WW-SVM，当类的数量很大时，我们的求解器比最先进的求解器显示出显着的速度提高。我们的精确子问题求解器还允许我们证明整体求解器的线性收敛。
Recent empirical evidence suggests that the Weston-Watkins support vector machine is among the best performing multiclass extensions of the binary SVM. Current state-of-the-art solvers repeatedly solve a particular subproblem approximately using an iterative strategy. In this work, we propose an algorithm that solves the subproblem exactly using a novel reparametrization of the Weston-Watkins dual problem. For linear WW-SVMs, our solver shows significant speed-up over the state-of-the-art solver when the number of classes is large. Our exact subproblem solver also allows us to prove linear convergence of the overall solver.