最小二乘分解算法在车型识别中的应用

　　1　引言

　　随着现代交通的快速发展,车型的种类也是越来越多。

　　在很多场合中,需要对车辆型号进行快速自动的识别。在高速公路自动收费、大型广场的管理和道路监控中,车型识别有着重要的应用价值。

　　支持向量机(SupportVectormachines, SVM)是建立在统计学习理论上的一种性能良好的学习机器。它是一种基于结构风险最小化原则的模式分类方法,在解决小样本、非线性和高维模式识别问题中表现出许多自己的优势,可以很好地解决车型识别问题。经典的SVM算法基本上都是求解一个凸二次规划问题,得到最优分类面。通过对算法的改进,J.A.K. Sukens和J. Vandewalle提出了最小二乘支持向量机(LS-SVM)算法[1],它通过求解一组线性方程而获得最优分类面。

　　但是在利用这种方法训练数据时,会遇到很多问题,比如存储核函数矩阵时需要一个随样本大小二次增长的内存空间,即使样本仅有几千个点,内存空间也要达到上百兆字节。针对上述问题,人们利用支持向量机解的稀疏性、优化问题的凸性和特征空间的隐式映射开发了很多实现技术,如块方法和分解方法。文献[2]提出一种序贯最小优化SMO类型分解方法的工作集选择方法,它利用梯度二阶信息使得工作集的选择可以快速的收敛。Kristin P. Bennet等人提出一种最大增益的工作集选择方法[3],关注的重点在于每次迭代时的核估计数目的最小化。文献[4]提出针对最小二乘支持向量机的工作集方法,寻求的是最大违反Karush-Kuhn-Tucker互补条件和核函数相关值的最大函数增益来选择工作集。本文采用梯度二阶信息选择工作集方法,实现LS-SVM分解算法,并将其应用到车型识别中。

　　2　最小二乘支持向量机

　　3　LS-SVM的SMO分解算法

　　从式(7)、(8)中可以看到,需要训练集大小数目的二次增长的内存空间来存储核函数矩阵,训练问题的复杂度随着矩阵的规模上升。对较大规模的问题,要在优化中利用所谓的“工作集”方法。这种方法可以描述为:若事先知道哪个约束是积极的,既有可能放弃所有非积极约束,从而简化问题。

　　3. 1　SMO分解方法

　　分解算法[2]只更新乘子αi的一个固定大小的子集,其他保持不变。在这个算法中,目标是每次在数据的一个小的子集上优化全局问题。迭代中选择工作集的一种有效的启发式方法是使用停止条件:比如包含那些违反Karush-Kuhn-Tucker互补条件最严重的点。

　　支持向量机求解问题可以归结为凸二次规划问题,即代价函数为二次函数,约束条件为线性函数的二次优化问题。

　　因此,考虑一种普通形式,最优求解问题如下: