Stochastic subset selection for learning with kernel machines

Kernel machines have gained much popularity in applications of machine learning. Support vector machines (SVMs) are a subset of kernel machines and generalize well for classification, regression, and anomaly detection tasks. The training procedure for traditional SVMs involves solving a quadratic programming (QP) problem. The QP problem scales super linearly in computational effort with the number of training samples and is often used for the offline batch processing of data. Kernel machines operate by retaining a subset of observed data during training. The data vectors contained within this subset are referred to as support vectors (SVs). The work presented in this paper introduces a subset selection method for the use of kernel machines in online, changing environments. Our algorithm works by using a stochastic indexing technique when selecting a subset of SVs when computing the kernel expansion. The work described here is novel because it separates the selection of kernel basis functions from the training algorithm used. The subset selection algorithm presented here can be used in conjunction with any online training technique. It is important for online kernel machines to be computationally efficient due to the real-time requirements of online environments. Our algorithm is an important contribution because it scales linearly with the number of training samples and is compatible with current training techniques. Our algorithm outperforms standard techniques in terms of computational efficiency and provides increased recognition accuracy in our experiments. We provide results from experiments using both simulated and real-world data sets to verify our algorithm.     

支持向量机的缺陷及改进算法

传统支持向量机通常关注于数据分布的边缘样本,支持向量通常在这些边缘样本中产生。本文提出一个新的支持向量算法,该算法的支持向量从全局的数据分布中产生,其稀疏性能在大部分数据集上远远优于经典支持向量机算法。该算法在多类问题上的时间复杂度仅等价于原支持向量机算法的二值问题,解决了设计多类算法时变量数目庞大或者二值子分类器数目过多的问题。     

Adaptive binary tree for fast SVM multiclass classification

This paper presents an adaptive binary tree (ABT) to reduce the test computational complexity of multiclass support vector machine (SVM). It achieves a fast classification by: (1) reducing the number of binary SVMs for one classification by using separating planes of some binary SVMs to discriminate other binary problems; (2) selecting the binary SVMs with the fewest average number of support vectors (SVs). The average number of SVs is proposed to denote the computational complexity to exclude one class. Compared with five well-known methods, experiments on many benchmark data sets demonstrate our method can speed up the test phase while remain the high accuracy of SVMs.     

基于同心超球面分割的支持向量预抽取方法

支持向量机仅仅由支持向量所决定,因此预先抽取支持向量参与训练是非常重要的。提出了一个基于同心超球面分割的支持向量预抽取方法,并在此基础上给出了HD-SVM训练算法。首先对样本的每一类分别用一些半径足够大的同心超球面进行分割,抽取出距离最优分类面较近的边界样本,这些样本最有可能成为支持向量;然后让边界样本作为初始工作集先参与训练。实验结果表明,该文的方法可以有效地对支持向量进行预抽取,避免了训练全部样本,使得训练速度明显得到提高。     

基于支持向量的分层并行筛选训练样本方法

基于支持向量能够代表训练集分类特征的特点，该文提出了一种基于支持向量的分层并行筛选训练样本的机器学习方法。该方法按照分而治之的思想将原分类问题分解成若干子问题，将训练样本的筛选过程分解成级联的2个层次。每层采用并行方法提取各训练集中的支持向量，这些被提取的支持向量将作为下一层的训练样本，各层训练集中的非支持向量通过学习被逐步筛选掉。为了保证问题的一致性，引入了交叉合并规则，仿真实验结果表明该方法在保证分类器推广能力的情况下，缩短了支持向量机的训练时间，减少了支持向量的数目。     

An online incremental learning support vector machine for large-scale data

Support Vector Machines (SVMs) have gained outstanding generalization in many fields. However, standard SVM and most of modified SVMs are in essence batch learning, which make them unable to handle incremental learning or online learning well. Also, such SVMs are not able to handle large-scale data effectively because they are costly in terms of memory and computing consumption. In some situations, plenty of Support Vectors (SVs) are produced, which generally means a long testing time. In this paper, we propose an online incremental learning SVM for large data sets. The proposed method mainly consists of two components: the learning prototypes (LPs) and the learning Support Vectors (LSVs). LPs learn the prototypes and continuously adjust prototypes to the data concept. LSVs are to get a new SVM by combining learned prototypes with trained SVs. The proposed method has been compared with other popular SVM algorithms and experimental results demonstrate that the proposed algorithm is effective for incremental learning problems and large-scale problems.     

Rule extraction from support vector machines by genetic algorithms

Support vector machines (SVMs) are state-of-the-art tools used to address issues pertinent to classification. However, the explanation capabilities of SVMs are also their main weakness, which is why SVMs are typically regarded as incomprehensible black box models. In the present study, a rule extraction algorithm to extract the comprehensible rule from SVMs and enhance their explanation capability is proposed. The proposed algorithm seeks to use the support vectors from a training model of SVMs and combine genetic algorithms for constructing rule sets. The proposed method can not only generate rule sets from SVMs based on the mixed discrete and continuous variables but can also select important variables in the rule set simultaneously. Measurements of accuracy, sensitivity, specificity, and fidelity are utilized to compare the performance of the proposed method with direct learner algorithms and several rule-extraction techniques from SVMs. The results indicate that the proposed method performs at least as well as with the most successful direct rule learners. Finally, an actual case of pressure ulcer was studied, and the results indicated the practicality of our proposed method in real applications.     

一种基于个人身份认证的正面人脸识别算法

利用小波分解提取人脸特征技术和支持向量机 (SVM)分类模型 ,提出了一种基于个人身份认证的正面人脸识别算法 (或称为人脸认证方法 ) .针对 M个用户的人脸认证算法包括二个阶段 :(1)训练阶段 :使用小波分解方法对脸像训练集中的人脸图象进行特征提取 ,并用所提取的人脸特征向量训练 M个 SVM(对应 M个用户 ) ;(2 )认证阶段 :先由待认证者所声称的用户身份 (姓名或密码等 )确定对应的一训练好的 SVM,然后用这一 SVM对小波分解方法提取的待认证人的脸像特征向量进行分类 ,分类结果将显示待认证人所声称的身份是否真实 .利用 ORL人脸图象库对该算法的实验测试结果 ,以及与径向基函数神经网络作为分类器时的实验结果比较表明了该算法性能的优越性     

Comparison of artificial neural networks and support vector machine classifiers for land cover classification in Northern China using a SPOT-5 HRG image

This article presents a sufficient comparison of two types of advanced non-parametric classifiers implemented in remote sensing for land cover classification. A SPOT-5 HRG image of Yanqing County, Beijing, China, was used, in which agriculture and forest dominate land use. Artificial neural networks (ANNs), including the adaptive backpropagation (ABP) algorithm, Levenberg–Marquardt (LM) algorithm, Quasi-Newton (QN) algorithm and radial basis function (RBF) were carefully tested. The LM–ANN and RBF–ANN, which outperform the other two, were selected to make a detailed comparison with support vector machines (SVMs). The experiments show that those well-trained ANNs and SVMs have no significant difference in classification accuracy, but the SVM usually performs slightly better. Analysis of the effect of the training set size highlights that the SVM classifier has great tolerance on a small training set and avoids the problem of insufficient training of ANN classifiers. The testing also illustrates that the ANNs and SVMs can vary greatly with regard to training time. The LM–ANN can converge very quickly but not in a stable manner. By contrast, the training of RBF–ANN and SVM classifiers is fast and can be repeatable.     

Incremental training of support vector machines

We propose a new algorithm for the incremental training of support vector machines (SVMs) that is suitable for problems of sequentially arriving data and fast constraint parameter variation. Our method involves using a "warm-start" algorithm for the training of SVMs, which allows us to take advantage of the natural incremental properties of the standard active set approach to linearly constrained optimization problems. Incremental training involves quickly retraining a support vector machine after adding a small number of additional training vectors to the training set of an existing (trained) support vector machine. Similarly, the problem of fast constraint parameter variation involves quickly retraining an existing support vector machine using the same training set but different constraint parameters. In both cases, we demonstrate the computational superiority of incremental training over the usual batch retraining method.     

Rule Extraction from Support Vector Machines: A Sequential Covering Approach

In this paper, we propose a novel algorithm for rule extraction from support vector machines (SVMs), termed SQRex-SVM. The proposed method extracts rules directly from the support vectors (SVs) of a trained SVM using a modified sequential covering algorithm. Rules are generated based on an ordered search of the most discriminative features, as measured by interclass separation. Rule performance is then evaluated using measured rates of true and false positives and the area under the receiver operating characteristic (ROC) curve (AUC). Results are presented on a number of commonly used data sets that show the rules produced by SQRex-SVM exhibit both improved generalization performance and smaller more comprehensible rule sets compared to both other SVM rule extraction techniques and direct rule learning techniques.     

Access the IEEE Computer Society Digital Library

In this paper, we propose a novel algorithm for rule extraction from support vector machines (SVMs), termed SQRex-SVM. The proposed method extracts rules directly from the support vectors (SVs) of a trained SVM using a modified sequential covering algorithm. Rules are generated based on an ordered search of the most discriminative features, as measured by interclass separation. Rule performance is then evaluated using measured rates of true and false positives and the area under the receiver operating characteristic (ROC) curve (AUC). Results are presented on a number of commonly used data sets that show the rules produced by SQRex-SVM exhibit both improved generalization performance and smaller more comprehensible rule sets compared to both other SVM rule extraction techniques and direct rule learning techniques     

一种用于文本分类的语义SVM及其在线学习算法

该文利用SVM在小训练样本集条件下仍有高泛化能力的特性,结合文本分类问题中同类别文本的特征在特征空间中具有聚类性分布的特点,提出一种使用语义中心集代替原训练样本集作为训练样本和支持向量的SVM:语义SVM。文中给出语义中心集的生成步骤,进而给出语义SVM的在线学习(在线分类知识积累)算法框架,以及基于SMO算法的在线学习算法的实现。实验结果说明语义SVM及其在线学习算法具有巨大的应用潜力:不仅在线学习速度和分类速度相对于标准SVM及其简单增量算法有数量级提高,而且分类准确率方面具有一定优势。     

Dual margin approach on a Lagrangian support vector machine

In this paper, we propose a new support vector machine (SVM) called dual margin Lagrangian support vectors machine (DMLSVM). Unlike other SVMs which use only support vectors to determine the separating hyperplanes, DMLSVM utilizes all the available training data for training the classifier, thus producing robust performance. The training data are weighted differently depending on whether they are in a marginal region or surplus region. For fast training, DMLSVM borrows its training algorithm from Lagrangian SVM (LSVM) and tailors the algorithm to its formulation. The convergence of our training method is rigorously proven and its validity is tested on a synthetic test set and UCI dataset. The proposed method can be used in a variety of applications such as a recommender systems for web contents of IPTV services.     

Pruning Support Vector Machines Without Altering Performances

Support vector machines (SV machines, SVMs) have many merits that distinguish themselves from many other machine-learning algorithms, such as the nonexistence of local minima, the possession of the largest distance from the separating hyperplane to the SVs, and a solid theoretical foundation. However, SVM training algorithms such as the efficient sequential minimal optimization (SMO) often produce many SVs. Some scholars have found that the kernel outputs are frequently of similar levels, which insinuate the redundancy of SVs. By analyzing the overlapped information of kernel outputs, a succinct separating-hyperplane-securing method for pruning the dispensable SVs based on crosswise propagation (CP) is systematically developed. The method also circumvents the problem of explicitly discerning SVs in feature space as the SVM formulation does. Experiments with the famous SMO-based software LibSVM reveal that all typical kernels with different parameters on the data sets contribute the dispensable SVs. Some 1% ~ 9% (in some scenarios, more than 50%) dispensable SVs are found. Furthermore, the experimental results also verify that the pruning method does not alter the SVMs' performances at all. As a corollary, this paper further contributes in theory a new lower upper bound on the number of SVs in the high-dimensional feature space.     

一种基于支持向量的二进制粒子群网络故障特征选择算法

网络故障诊断中大量无关或冗余的特征会降低诊断的精度,需要对初始特征进行选择。Wrapper模式特征选择方法分类算法计算量大,为了降低计算量,本文提出了基于支持向量的二进制粒子群（SVB-BPSO）的故障特征选择方法。该算法以SVM为分类器,首先通过对所有样本的SVM训练选出SV集,在封装的分类训练中仅使用SV集,然后采用异类支持向量之间的平均距离作为SVM的参数进行训练,最后根据分类结果,利用BPSO在特征空间中进行全局搜索选出最优特征集。在DARPA数据集上的实验表明本文提出的方法能够降低封装模式特征选择的计算量且获得了较高的分类精度以及较明显的降维效果。     

支持向量预选取的域着色Voronoi图方法

支持向量机是建立在统计学习理论基础上的一种机器学习方法,它通过对支持向量的训练而具有很好的分类推广能力。但是从训练样本中选取合适的支持向量很困难,而对噪音样本的训练会使支持向量机的泛化能力下降。在分析了支持向量的分布特性和Voronoi图在特征空间划分的优势后,提出一种利用域着色Voronoi图来选取支持向量的方法。该方法能大量减少训练样本集中的非支持向量,排除孤立噪音样本,最终得到一个包含候选支持向量的训练样本集。仿真实验结果说明了该方法的有效性和可行性。     

一种文本分类的在线SVM学习算法

本文提出了一种用于文本分类的RBF 支持向量机在线学习算法。利用RBF 核函数的局部性,该算法仅对新训练样本的某一大小邻域内且位于“可能带”中的训练样本集进行重新训练,以实现对现有SVM的更新。为高效的实现该邻域大小的自适应确定,使用ξa 泛化错误估计在所有现有训练样本集上对当前SVM的泛化错误进行定性估计。同时引入泛化能力进化因子,使得结果SVM在分类效果上具有自动调整能力,并防止分类能力的退化。在TREC - 5 真实语料上的对比测试结果表明,该算法显著地加速了增量学习的过程而同时保证结果SVM的分类效果。     

超立方体多处理机系统中基于扩展安全向量的容错路由

针对超立方体结构的多处理机系统中存在链路故障的情况,修改了吴杰提出的安全向量的概念,提出了扩展安全向量的概念,并给出了一个基于扩展安全向量的容错路由算法,与基于安全向量的路由算法相比,基于扩展安全向量的路由算法搜索最优通路的能力有了非常大的提高,即使故障数较多时,它仍能保证把绝大多数源、目的节点间有最优通路和消息沿最优通路传递。超立方体结构中各节点扩展安全向量的赋值可以通过ｎ－１轮邻接点的信息交换     

Combining support vector machine learning with the discrete cosine transform in image compression

We present an algorithm for the application of support vector machine (SVM) learning to image compression. The algorithm combines SVMs with the discrete cosine transform (DCT). Unlike a classic radial basis function networks or multilayer perceptrons that require the topology of the network to be defined before training, an SVM selects the minimum number of training points, called support vectors, that ensure modeling of the data within the given level of accuracy (a.k.a. insensitivity zone /spl epsi/). It is this property that is exploited as the basis for an image compression algorithm. Here, the SVMs learning algorithm performs the compression in a spectral domain of DCT coefficients, i.e., the SVM approximates the DCT coefficients. The parameters of the SVM are stored in order to recover the image. Results demonstrate that even though there is an extra lossy step compared with the baseline JPEG algorithm, the new algorithm dramatically increases compression for a given image quality; conversely it increases image quality for a given compression ratio. The approach presented can be readily applied for other modeling schemes that are in a form of a sum of weighted basis functions.