大规模SVDD的坐标下降算法

Coordinate Descent Algorithms for Large-Scale SVDD

支持向量数据描述(SVDD)是一种无监督学习算法,在图像识别和信息安全等领域有重要应用.坐标下降方法是求解大规模分类问题的有效方法,具有简洁的操作流程和快速的收敛速率.文中针对大规模SVDD提出一种高效的对偶坐标下降算法,算法每步迭代的子问题都可获得解析解,并可使用加速策略和简便运算减少计算量.同时给出3种子问题的选择方法,并分析对比各自优劣.实验对仿真和真实大规模数据库进行算法验证.与LibSVDD相比,文中方法更具优势,1.4s求解105样本规模的ijcnn文本库.

Support vector data description （SVDD） is an unsupervised learning method with significant application in image recognition and information security. Coordinate descent is an effective method for large-scale classification problems with simple operation and high convergence speed. In this paper, an efficient coordinate descent algorithm for solving large-scale SVDD is presented. The solution of concerned sub-problem at each iteration is derived in closed form and the computational cost is decreased through the accelerating strategy and cheap computation. Meanwhile, three methods for selecting sub-problem, analyzing and comparing their advantage and disadvantage are developed. The experiments on simulation and real large-scale database validate the performance of the proposed algorithm. Compared with LibSVDD, the proposed algorithm has great superiority which takes less than 1.4 seconds to solve a text database from ijcnn with 105 training examples.