NPA Algorithm and it''''s Modification
NPA算法及其修正

1 引言支撑向量机(Support Vector Machine,简称 SVM)是九十年代中期发展起来的机器学习技术,随着这项技术越来越受到人们重视,一些训练算法应运而生。1998年,Platt提出一个迭代算法称为SMO算法(Sequential Minimal Opti-mization),基本思想是运用一种顺序最小优化方法解二次规划的对偶问题,这是目前最好的算法之一。最近,Keerthi等人提出最近点NPA算法(Nearest Point Algorithm),它基于以下事实:支撑向量机的优化问题等价于两个凸多面体之间的最近点问题。Keerthi等人的工作是把求最近点问题的Gilbert算法和MDM算法巧妙地结合在一起。NPA与SMO相比训练速度毫不逊色,甚至还有优势。本文在大量实验和深入分析的基础上,发现NPA算法还存在某些欠缺,进