Feasible Direction Decomposition Algorithms for Training Support Vector Machines

The article presents a general view of a class of decomposition algorithms for training Support Vector Machines (SVM) which are motivated by the method of feasible directions. The first such algorithm for the pattern recognition SVM has been proposed in Joachims, T. (1999, Schölkopf et al. (Eds.) Advances in kernel methods-Support vector learning (pp. 185–208). MIT Press). Its extension to the regression SVM—the maximal inconsistency algorithm—has been recently presented by the author (Laskov, 2000, Solla, Leen, & Müller (Eds.) Advances in neural information processing systems 12 (pp. 484–490). MIT Press). A detailed account of both algorithms is carried out, complemented by theoretical investigation of the relationship between the two algorithms. It is proved that the two algorithms are equivalent for the pattern recognition SVM, and the feasible direction interpretation of the maximal inconsistency algorithm is given for the regression SVM. The experimental results demonstrate an order of magnitude decrease of training time in comparison with training without decomposition, and, most importantly, provide experimental evidence of the linear convergence rate of the feasible direction decomposition algorithms.     

A Simple Decomposition Method for Support Vector Machines

The decomposition method is currently one of the major methods for solving support vector machines. An important issue of this method is the selection of working sets. In this paper through the design of decomposition methods for bound-constrained SVM formulations we demonstrate that the working set selection is not a trivial task. Then from the experimental analysis we propose a simple selection of the working set which leads to faster convergences for difficult cases. Numerical experiments on different types of problems are conducted to demonstrate the viability of the proposed method.     

关于支持向量机几何算法的研究

支持向量机是一种新的机器学习方法。它以统计学习理论为基础,从结构风险最小化原则出发,具有很好的泛化及推广能力。传统的SVM训练算法都是把原问题转化为对偶的二次规划问题进行求解。但对偶优化问题求解存在着计算量大、速度慢等问题。几何算法利用了训练集中的几何信息,从SVM的几何意义出发求解问题,并具有直观、计算精度高等优点,易于应用。在对支持向量分类机进行理论分析基础上,对其几何算法进行了初步研究并分析了其优缺点。     

支持向量机分解算法研究

分解算法是目前大量数据下支持向量机最主要训练方法。各种分解算法的区别在于工作集的大小、产生原则以及子QP问题的求解方法不同。介绍分解算法的产生以及发展过程,以及相应的工作集选择算法,重点指出分解算法在子工作集优化方法、工作集的选择策略所采用的新的方法以及有关收敛性的证明。     

基于SVM与遗传算法的非线性模式识别

设计了一种支持向量机的模型结构,以遗传算法进行该模型参数的组合优化建模,并将其用于非线性模式识别,该方法不仅对线性问题有效,对非线性问题同样适用有效;该法简洁易行,优于多段线性分类器设计方法与BP误差回传网络算法,通过实例验证其识别效率达100％。     

最小二乘隐空间支持向量机

在隐空间中采用最小二乘损失函数,提出了最小二乘隐空间支持向量机（LSHSSVMs）．同隐空间支持向量机（HSSVMs）一样,最小二乘隐空间支持向量机不需要核函数满足正定条件,从而扩展了支持向量机核函数的选择范围．由于采用了最小二乘损失函数,最小二乘隐空问支持向量机产生的优化问题为无约束凸二次规划,这比隐空间支持向量机产生的约束凸二次规划更易求解．仿真实验结果表明所提算法在计算时间和推广能力上较隐空间支持向量机存在一定的优势．     

最小二乘双支持向量机的在线学习算法

针对具有两个非并行分类超平面的最小二乘双支持向量机,提出了一种在线学习算法。通过利用矩阵求逆分解引理,所提在线学习算法能充分利用历史的训练结果,避免了大型矩阵的求逆计算过程,从而降低了计算的复杂性。仿真结果验证了所提学习算法的有效性。     

Recursive Update Algorithm for Least Squares Support Vector Machines

In this Letter an efficient recursive update algorithm for least squares support vector machines (LSSVMs) is developed. Using the previous solution and some matrix equations, the algorithm completely avoids training the LSSVM all over again whenever new training sample is available. The gain in speed using the recursive update algorithm is illustrated on four data sets from UCI repository: the Statlog Australian credit, the Pima Indians diabetes, the Wisconsin breast cancer, and the adult income data sets.     

Digital Least Squares Support Vector Machines

This paper presents a very simple digital architecture that implements a Least-Squares Support Vector Machine. The simplicity of the whole system and its good behavior when used to solve classification problems hold good prospects for the application of such a kind of learning machines to build embedded systems.     

模糊支持向量分类机

研究了当训练点的输出为模糊数时支持向量分类机的构建问题。对于线性模糊分类问题,首先将其转化为模糊系数规划。利用模糊系数规划的λ-最优规划,求解模糊系数规划得到模糊最优解（模糊集合）以及模糊最优分类函数集（取值为最优分类函数而隶属度为λ（0≤λ≤1）的模糊集合）,从而构造线性模糊支持向量分类机。对于非线性模糊分类问题,引入核函数,类似干线性模糊分类问题得到非线性模糊支持向量分类机。最后构造显示模糊支持向量分类机特点的模糊支持向量集（取值为模糊训练点,隶属度为λ（0≤λ≤1）的模糊集合）。模糊支持向量分类机较好地解决了支持向量机中含有模糊信息的分类问题。     

用于手写数字识别的改进模糊支持向量机

针对训练样本在训练过程中的不同作用和支持向量机在推广到多类问题时存在不可分区域,可构造两类模糊支持向量机,其分别克服了过学习问题和减少了不可分区域.构造两类问题和多类问题综合的改进模糊支持向量机并用于手写数字识别,训练时,其利用数据与其类中心的相对距离定义隶属函数,测试时,利用S.Abe定义的隶属函数判别其类别,实验结果表明,该学习机具有比传统支持向量机和模糊支持向量机更高的精度.     

支持向量机多类分类算法研究

提出一种新的基于二叉树结构的支持向量(SVM)多类分类算法.该算法解决了现有主要算法所存在的不可分区域问题.为了获得较高的推广能力,必须让样本分布广的类处于二叉树的上层节点,才能获得更大的划分空间.所以,该算法采用最小超立方体和最小超球体类包含作为二叉树的生成算法.实验结果表明,该算法具有一定的优越性.     

Hierarchical Learning in Polynomial Support Vector Machines

We study the typical properties of polynomial Support Vector Machines within a Statistical Mechanics approach that takes into account the number of high order features relative to the input space dimension. We analyze the effect of different features' normalizations on the generalization error, for different kinds of learning tasks. If the normalization is adequately selected, hierarchical learning of features of increasing order takes place as a function of the training set size. Otherwise, the performance worsens, and there is no hierarchical learning at all.     

加权光滑CHKS孪生支持向量机

针对光滑孪生支持向量机(smooth twin support vector machines,简称STWSVM)采用的Sigmoid 光滑函数逼近精度低和STWSVM 对异常点敏感的问题,引入一种性能更好的光滑函数——CHKS 函数,提出了光滑CHKS孪生支持向量机模型(smooth CHKS twin support vector machines,简称SCTWSVM).在此基础上,根据样本点的位置为每个训练样本赋予不同的重要性,以降低异常点对非平行超平面的影响,提出了加权光滑CHKS 孪生支持向量机(weighted smooth CHKS twin support vector machines,简称WSCTWSVM).不仅从理论上证明了SCTWSVM 具有严凸性和任意阶光滑的性能,而且在数据集上的实验结果表明,相对于STWSVM,SCTWSVM 可以在更短的时间内获得更高的分类精度,同时验证了WSCTWSVM 的有效性和可行性.     

Authorship Attribution with Support Vector Machines

In this paper we explore the use of text-mining methods for the identification of the author of a text. We apply the support vector machine (SVM) to this problem, as it is able to cope with half a million of inputs it requires no feature selection and can process the frequency vector of all words of a text. We performed a number of experiments with texts from a German newspaper. With nearly perfect reliability the SVM was able to reject other authors and detected the target author in 60–80% of the cases. In a second experiment, we ignored nouns, verbs and adjectives and replaced them by grammatical tags and bigrams. This resulted in slightly reduced performance. Author detection with SVMs on full word forms was remarkably robust even if the author wrote about different topics.     

基于奇异值分解和支持向量机的人脸检测

人脸检测在自动人脸鉴别工作中具有重要的意义。由于人脸图像特征的复杂性和多样性，使得人脸模式分类器的训练十分困难。本文提出了一种基于支持向量机（SVM）的人脸检测算法，使用了奇异值分解对训练样本进行特征提取，再由SVM分类器进行分类，有效的降低了训练难度，采用二阶多项式作为SVM分类器的核函数，实验结果表明，该方法是十分有效的。     

最小二乘支持向量机的一种稀疏化算法

介绍了一种稀疏化最小二乘支持向量机的剪枝算法。由于支持值图谱中小的支持值所对应的训练样本在算法执行阶段所起的作用较小,所以删除它们不会引起性能的显著下降。仿真实验表明,该算法不但简单、易于实现,而且能够保持良好的分类性能。     

基于小波包分解和支持向量机的图像隐秘检测算法

提出了一种新的小波包分解算法,该算法只对图像的低频部分进行分解,从而大大减少了特征向量的维数,提高了运行效率。在模式分类上采用了支持向量机的算法,实验证明,该算法与Fisher线性判别算法相比,其检测率明显提高。     

基于支持向量机方法的人脸识别研究

采用 SVM方法进行人脸识别研究 ,将人脸识别这一典型的多分类问题构造成适合 SVM处理的二分类问题 ,克服了传统 SVM方法在解决多分类问题上的一些缺陷 .实验以手工与自动两种预处理方式在 FERET和 Bio ID人脸库上完成 ,并与 PCA方法进行了对比 ,结果表明本文的 SVM方法比 PCA方法有更好的概括能力和更高的正确识别率 ,使得今后建立一个基于 SVM方法的人脸自动检测和识别系统成为可能     

基于约束投影的支持向量机选择性集成

提出两种基于约束投影的支持向量机选择性集成算法。首先利用随机选取的must-link和cannot-link成对约束集确定投影矩阵,将原始训练样本投影到不同的低维空间训练一组基分类器;然后,分别采用遗传优化和最小化偏离度误差两种选择性集成技术对基分类器进行组合。基于UCI数据的实验表明,提出的两种集成算法均能有效提高支持向量机的泛化性能,显著优于Bagging,Boosting,特征Bagging及LoBag等集成算法。