多项式核函数SVM快速分类算法

标准的SVM分类计算过程中有大量的支持向量参与了计算,导致了分类速度缓慢。该文为提高SVM的分类速度,提出了一种快速的多项式核函数SVM分类算法,即将使用多项式核的SVM分类决策函数展开为关于待分类向量各分量的多项式,分类时通过计算各个多项式的值而得到分类结果,使分类计算量和支持向量数量无关,又保留了全部支持向量的信息。当多项式核函数的阶数或待分类向量的维数较低而支持向量数量较多时,使用该算法可以使SVM 分类的速度得到极大的提高。针对实际数据集的实验表明了该算法的有效性。     

Relationship Between Support Vector Set and Kernel Functions in SVM

Based on a constructive learning approach,covering algorithms,we investigate the relationship between support vector sets and kernel functions in support vector machines (SVM).An interesting result is obtained.That is,in the linearly non-separable case,any sample of a given sample set K can become a support vector under a certain kernel function.The result shows that when the sample set K is linearly non-separable,although the chosen kernel function satisfies Mercer‘s condition its corresponding support vector set is not necessarily the subset of K that plays a crucial role in classifying K.For a given sample set,what is the subset that plays the crucial role in classification?In order to explore the problem,a new concept,boundary or boundary points,is defined and its properties are discussed.Given a sample set K,we show that the decision functions for classifying the boundary points of K are the same as that for classifying the K itself.And the boundary points of K only depend on K and the structure of the space at which k is located and independent of the chosen approach for finding the boundary.Therefore,the boundary point set may become the subset of K that plays a crucial role in classification.These results are of importance to understand the principle of the support vector machine(SVM) and to develop new learning algorithms.     

Classification of faces in man and machine

We attempt to shed light on the algorithms humans use to classify images of human faces according to their gender. For this, a novel methodology combining human psychophysics and machine learning is introduced. We proceed as follows. First, we apply principal component analysis (PCA) on the pixel information of the face stimuli. We then obtain a data set composed of these PCA eigenvectors combined with the subjects' gender estimates of the corresponding stimuli. Second, we model the gender classification process on this data set using a separating hyperplane (SH) between both classes. This SH is computed using algorithms from machine learning: the support vector machine (SVM), the relevance vector machine, the prototype classifier, and the K-means classifier. The classification behavior of humans and machines is then analyzed in three steps. First, the classification errors of humans and machines are compared for the various classifiers, and we also assess how well machines can recreate the subjects' internal decision boundary by studying the training errors of the machines. Second, we study the correlations between the rank-order of the subjects' responses to each stimulus-the gender estimate with its reaction time and confidence rating-and the rank-order of the distance of these stimuli to the SH. Finally, we attempt to compare the metric of the representations used by humans and machines for classification by relating the subjects' gender estimate of each stimulus and the distance of this stimulus to the SH. While we show that the classification error alone is not a sufficient selection criterion between the different algorithms humans might use to classify face stimuli, the distance of these stimuli to the SH is shown to capture essentials of the internal decision space of humans. Furthermore, algorithms such as the prototype classifier using stimuli in the center of the classes are shown to be less adapted to model human classification behavior than algorithms such as the SVM based on stimuli close to the boundary between the classes.     

On-line voltage security assessment of power systems using core vector machines

This paper presents a core vector machine (CVM)-based algorithm for on-line voltage security assessment of power systems. To classify the system security status, a CVM has been trained for each contingency. The proposed CVM-based security assessment has very small training time and space in comparison with support vector machines (SVM) and artificial neural networks (ANNs)-based algorithms. The proposed algorithm produces less support vectors (SV) and therefore is faster than existing algorithms. In this paper, a new decision tree (DT)-based feature selection technique has been presented, too. The proposed CVM algorithm has been applied to New England 39-bus power system. The simulation results show the effectiveness and the stability of the proposed method for on-line voltage security assessment procedure of large-scale power system.     

Accurate on-line support vector regression

Batch implementations of support vector regression (SVR) are inefficient when used in an on-line setting because they must be retrained from scratch every time the training set is modified. Following an incremental support vector classification algorithm introduced by Cauwenberghs and Poggio (2001), we have developed an accurate on-line support vector regression (AOSVR) that efficiently updates a trained SVR function whenever a sample is added to or removed from the training set. The updated SVR function is identical to that produced by a batch algorithm. Applications of AOSVR in both on-line and cross-validation scenarios are presented. In both scenarios, numerical experiments indicate that AOSVR is faster than batch SVR algorithms with both cold and warm start.     

A simple decomposition algorithm for support vector machines with polynomial-time convergence

Support vector machines (SVMs) are a new and important tool in data classification. Recently much attention has been devoted to large scale data classifications where decomposition methods for SVMs play an important role.So far, several decomposition algorithms for SVMs have been proposed and applied in practice. The algorithms proposed recently and based on rate certifying pair/set provide very attractive features compared with many other decomposition algorithms. They converge not only with finite termination but also in polynomial time. However, it is difficult to reach a good balance between low computational cost and fast convergence.In this paper, we propose a new simple decomposition algorithm based on a new philosophy on working set selection. It has been proven that the working set selected by the new algorithm is a rate certifying set. Further, compared with the existing algorithms based on rate certifying pair/set, our algorithm provides a very good feature in combination of lower computational complexity and faster convergence.     

两种基于等式约束支持向量回归机比较研究

为了减小支持向量回归机(SVR)的计算复杂度、缩短训练时间,将应用于分类问题的近似支持向量机(PSVM)扩展到回归问题中,针对其原始优化问题采用直接法求取最优解,而不是转换为对偶问题求解,给出了近似支持向量回归机(PSVR)线性和非线性回归算法.并与同样基于等式约束的最小二乘支持向量回归机(LSSVR)进行了比较,在一维、二维函数回归以及不同规模通用数据集上的测试结果表明,PSVR算法简单,训练速度快,尤其在大规模数据集处理上更具优势.     

支持向量机和最小二乘支持向量机的比较及应用研究

介绍和比较了支持向量机分类器和量小二乘支持向量机分类器的算法。并将支持向量机分类器和量小二乘支持向量机分类器应用于心脏病诊断，取得了较高的准确率。所用数据来自UCI bench—mark数据集。实验结果表明，支持向量机和量小二乘支持向量机在医疗诊断中有很大的应用潜力。     

Odor classification using similarity-based representation

In this paper a new approach to odor classification is presented, founded on the similarity-based representation paradigm. The proposed approach builds a new representation space, called similarity space, in which each object is not represented by features, but by its similarities with respect to other objects in the data set. The classification step is performed using support vector machines, a technique introduced in the statistical learning theory context. One of the major drawbacks of the similarity-based representation paradigm is the dimensionality of the similarity space: a method for addressing this problem has been introduced in this paper, based on a notion of the unsupervised classification (clustering) theory, namely the medoid concept. The approach outperforms standard features-based representations on tests regarding data gathered from a chemical sensors array electronic nose.     

On Taxonomies for Multi-class Image Categorization

We study the problem of classifying images into a given, pre-determined taxonomy. This task can be elegantly translated into the structured learning framework. However, despite its power, structured learning has known limits in scalability due to its high memory requirements and slow training process. We propose an efficient approximation of the structured learning approach by an ensemble of local support vector machines (SVMs) that can be trained efficiently with standard techniques. A?first theoretical discussion and experiments on toy-data allow to shed light onto why taxonomy-based classification can outperform taxonomy-free approaches and why an appropriately combined ensemble of local SVMs might be of high practical use. Further empirical results on subsets of Caltech256 and VOC2006 data indeed show that our local SVM formulation can effectively exploit the taxonomy structure and thus outperforms standard multi-class classification algorithms while it achieves on par results with taxonomy-based structured algorithms at a significantly decreased computing time.     

A Novel Active Learning Method Using SVM for Text Classification

Support vector machines (SVMs) are a popular class of supervised learning algorithms, and are particularly applicable to large and high-dimensional classification problems. Like most machine learning methods for data classification and information retrieval, they require manually labeled data samples in the training stage. However, manual labeling is a time consuming and errorprone task. One possible solution to this issue is to exploit the large number of unlabeled samples that are easily accessible via the internet. This paper presents a novel active learning method for text categorization. The main objective of active learning is to reduce the labeling effort, without compromising the accuracy of classification, by intelligently selecting which samples should be labeled. The proposed method selects a batch of informative samples using the posterior probabilities provided by a set of multi-class SVM classifiers, and these samples are then manually labeled by an expert. Experimental results indicate that the proposed active learning method significantly reduces the labeling effort, while simultaneously enhancing the classification accuracy.     

基于近似支持向量机的Web文本分类研究

文本分类技术是知识管理系统实现知识有效组织、存储和检索的重要手段.本文提出了一种新的基于近似支持向量机的分类算法,并将该分类算法应用于文本分类分析.实验过程中与现有的分类方法比较,新的分类方法具有训练速度快、分类精度比较高的优点.     

Applying a novel decision rule to the sphere-structured support vector machines algorithm

The traditional sphere-structured support vector machines algorithm is one of the learning methods. It can partition the training samples space by means of constructing the spheres with the minimum volume covering all training samples of each pattern class in high-dimensional feature space. However, the decision rule of the traditional sphere-structured support vector machines cannot assign ambiguous sample points such as some encircled by more than two spheres to valid class labels. Therefore, the traditional sphere-structured support vector machines is insufficient for obtaining the better classification performance. In this article, we propose a novel decision rule applied to the traditional sphere-structured support vector machines. This new decision rule significantly improves the performance of labeling ambiguous points. Experimental results of seven real datasets show the traditional sphere-structured support vector machines based on this new decision rule can not only acquire the better classification accuracies than the traditional sphere-structured support vector machines but also achieve the comparable performance to the classical support vector machines. An erratum to this article can be found at     

一种新型的多元分类支持向量机

最小二乘支持向量机采用最小二乘线性系统代替传统的支持向量机采用二次规划方法解决模式识别问题。该文详细推理和分析了二元分类最小二乘支持向量机算法，构建了多元分类最小二乘支持向量机，并通过典型样本进行测试，结果表明采用多元分类最小二乘支持向量机进行模式识别是有效、可行的。     

基于改进秃鹰搜索算法的同步优化特征选择

针对传统支持向量机在封装式特征选择中分类效果差、子集选取冗余、计算性能易受核函数参数影响的不足,利用元启发式优化算法对其进行同步优化.首先利用莱维飞行策略和模拟退火机制对秃鹰搜索算法的局部搜索能力与勘探利用解空间能力进行改进,通过标准函数的测试结果验证其改进的有效性;其次将支持向量机核函数参数作为待优化目标,利用改进后...     

Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

Ruzzo [Tree-size bounded alternation, J. Comput. Syst. Sci. 21] introduced the notion of tree-size for alternating Turing machines (ATMs) and showed that it is a reasonable measure for classification of complexity classes. We establish in this paper that computations by tree-size and space simultaneously bounded ATMs roughly correspond to computations by time and space simultaneously bounded nondeterministic TMs (NTMs).We also show that not every polynomial time bounded and sublinear space simultaneously bounded NTM can be simulated by any deterministic TM with a slightly increased time bound and a slightly decreased space bound simultaneously.     

Time series prediction using support vector machines,the orthogonal and the regularized orthogonal least-squares algorithms

Generalization properties of support vector machines, orthogonal least squares and zero-order regularized orthogonal least squares algorithms are studied using simulation. For high signal-to-noise ratios (40 dB), mixed results are obtained, but for a low signal-to-noise ratio, the prediction performance of support vector machines is better than the orthogonal least squares algorithm in the examples considered. However, the latter can usually give a parsimonious model with very fast training and testing time. Two new algorithms are therefore proposed that combine the orthogonal least squares algorithm with support vector machines to give a parsimonious model with good prediction accuracy in the low signal-to-noise ratio case.     

线性支持向量机优化问题的极大熵方法

支特向量机是一种新的机器学习方法，已成功地应用于模式分类、回归分析和密度估计等问题中．本文依据统计学习理论和最优化理论建立了线性支特向量机的无约束优化模型，并给出了一种有效的近似解法一极大熵方法,为求解支持向量机优化问题提供了一种新途径,本文方法特别易于计算机实现。数值实验结果表明了模型和算法的可行性和有效性．