CAJ | 학술논문

割平面方法可高效求解线性支持向量机问题，其主要思路是通过不断添加割平面并利用精确线性搜索实现算法的加速和优化。针对其中的非光滑线性搜索问题，文中提出一种基于非精确步长搜索的加速割平面方法。该方法使用较少的迭代次数就能确定最优步长所在的子区间。在此基础上，用二点二次插值的闭式解逼近最优步长，从而较精确线性搜索方法速度更快、开销更小，且保持同样的收敛边界。大量实验表明，文中方法效率优于基于精确线性搜索的优化割平面方法，在一些数据库上的收敛速度甚至提升50%。
할평면방법가고효구해선성지지향량궤문제，기주요사로시통과불단첨가할평면병이용정학선성수색실현산법적가속화우화。침대기중적비광활선성수색문제，문중제출일충기우비정학보장수색적가속할평면방법。해방법사용교소적질대차수취능학정최우보장소재적자구간。재차기출상，용이점이차삽치적폐식해핍근최우보장，종이교정학선성수색방법속도경쾌、개소경소，차보지동양적수렴변계。대량실험표명，문중방법효솔우우기우정학선성수색적우화할평면방법，재일사수거고상적수렴속도심지제승50%。
Cutting plane method efficiently solves the primal problem of linear support vector machines by adding cutting planes incrementally, and thus it can be accelerated through the exact line search. In this paper, an optimized cutting plane method with inexact line search is presented, and it determines the interval containing the optimal step size with fewer iterations. The acceptable step size is obtained by the closed-form solution of quadratic interpolation with two points. The theoretical analysis shows that the proposed method has the same optimal convergence bound as the exact line search method with a higher speed and low cost. The experiments on large-scale datasets demonstrate that the proposed method outperforms the exact line search method. In some cases, it achieves even more than 50% speedup.