Sparse kernel SVMs via cutting-plane training

We explore an algorithm for training SVMs with Kernels that can represent the learned rule using arbitrary basis vectors, not just the support vectors (SVs) from the training set. This results in two benefits. First, the added flexibility makes it possible to find sparser solutions of good quality, substantially speeding-up prediction. Second, the improved sparsity can also make training of Kernel SVMs more efficient, especially for high-dimensional and sparse data (e.g. text classification). This has the potential to make training of Kernel SVMs tractable for large training sets, where conventional methods scale quadratically due to the linear growth of the number of SVs. In addition to a theoretical analysis of the algorithm, we also present an empirical evaluation.     

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

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

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.     

Kernel Factory: An ensemble of kernel machines

We propose an ensemble method for kernel machines. The training data is randomly split into a number of mutually exclusive partitions defined by a row and column parameter. Each partition forms an input space and is transformed by an automatically selected kernel function into a kernel matrix K. Subsequently, each K is used as training data for a base binary classifier (Random Forest). This results in a number of predictions equal to the number of partitions. A weighted average combines the predictions into one final prediction. To optimize the weights, a genetic algorithm is used. This approach has the advantage of simultaneously promoting (1) diversity, (2) accuracy, and (3) computational speed. (1) Diversity is fostered because the individual K’s are based on a subset of features and observations, (2) accuracy is sought by automatic kernel selection and the genetic algorithm, and (3) computational speed is obtained because the computation of each K can be parallelized. Using five times twofold cross validation we benchmark the classification performance of Kernel Factory against Random Forest and Kernel-Induced Random Forest (KIRF). We find that Kernel Factory has significantly better performance than Kernel-Induced Random Forest. When the right kernel is selected Kernel Factory is also significantly better than Random Forest. In addition, an open-source R-software package of the algorithm (kernelFactory) is available from CRAN.     

Feature subset selection for support vector machines through discriminative function pruning analysis

In many pattern classification applications, data are represented by high dimensional feature vectors, which induce high computational cost and reduce classification speed in the context of support vector machines (SVMs). To reduce the dimensionality of pattern representation, we develop a discriminative function pruning analysis (DFPA) feature subset selection method in the present study. The basic idea of the DFPA method is to learn the SVM discriminative function from training data using all input variables available first, and then to select feature subset through pruning analysis. In the present study, the pruning is implement using a forward selection procedure combined with a linear least square estimation algorithm, taking advantage of linear-in-the-parameter structure of the SVM discriminative function. The strength of the DFPA method is that it combines good characters of both filter and wrapper methods. Firstly, it retains the simplicity of the filter method avoiding training of a large number of SVM classifier. Secondly, it inherits the good performance of the wrapper method by taking the SVM classification algorithm into account.     

Training SVMs on a bound vectors set based on Fisher projection

Standard support vector machines (SVMs) training algorithms have O(l ³) computational and O(l ²) space complexities, where l is the training set size. It is thus computationally infeasible on very large data sets. To alleviate the computational burden in SVM training, we propose an algorithm to train SVMs on a bound vectors set that is extracted based on Fisher projection. For linear separate problems, we use linear Fisher discriminant to compute the projection line, while for non-linear separate problems, we use kernel Fisher discriminant to compute the projection line. For each case, we select a certain ratio samples whose projections are adjacent to those of the other class as bound vectors. Theoretical analysis shows that the proposed algorithm is with low computational and space complexities. Extensive experiments on several classification benchmarks demonstrate the effectiveness of our approach.     

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

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

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.     

A sparse kernel algorithm for online time series data prediction

Kernel based methods have been widely applied for signal analysis and processing. In this paper, we propose a sparse kernel based algorithm for online time series prediction. In classical kernel methods, the kernel function number is very large which makes them of a high computational cost and only applicable for off-line or batch learning. In online learning settings, the learning system is updated when each training sample is obtained and it requires a higher computational speed. To make the kernel methods suitable for online learning, we propose a sparsification method based on the Hessian matrix of the system loss function to continuously examine the significance of the new training sample in order to select a sparse dictionary (support vector set). The Hessian matrix is equivalent to the correlation matrix of sample inputs in the kernel weight updating using the recursive least square (RLS) algorithm. This makes the algorithm able to be easily implemented with an affordable computational cost for real-time applications. Experimental results show the ability of the proposed algorithm for both real-world and artificial time series data forecasting and prediction.     

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.     

Online Multiple Kernel Classification

Although both online learning and kernel learning have been studied extensively in machine learning, there is limited effort in addressing the intersecting research problems of these two important topics. As an attempt to fill the gap, we address a new research problem, termed Online Multiple Kernel Classification (OMKC), which learns a kernel-based prediction function by selecting a subset of predefined kernel functions in an online learning fashion. OMKC is in general more challenging than typical online learning because both the kernel classifiers and the subset of selected kernels are unknown, and more importantly the solutions to the kernel classifiers and their combination weights are correlated. The proposed algorithms are based on the fusion of two online learning algorithms, i.e., the Perceptron algorithm that learns a classifier for a given kernel, and the Hedge algorithm that combines classifiers by linear weights. We develop stochastic selection strategies that randomly select a subset of kernels for combination and model updating, thus improving the learning efficiency. Our empirical study with 15 data sets shows promising performance of the proposed algorithms for OMKC in both learning efficiency and prediction accuracy.     

Error tolerance based support vector machine for regression

Most existing online algorithms in support vector machines (SVM) can only grow support vectors. This paper proposes an online error tolerance based support vector machine (ET-SVM) which not only grows but also prunes support vectors. Similar to least square support vector machines (LS-SVM), ET-SVM converts the original quadratic program (QP) in standard SVM into a group of easily solved linear equations. Different from LS-SVM, ET-SVM remains support vectors sparse and realizes a compact structure. Thus, ET-SVM can significantly reduce computational time while ensuring satisfactory learning accuracy. Simulation results verify the effectiveness of the newly proposed algorithm.     

A parallel mixture of SVMs for very large scale problems

Support vector machines (SVMs) are the state-of-the-art models for many classification problems, but they suffer from the complexity of their training algorithm, which is at least quadratic with respect to the number of examples. Hence, it is hopeless to try to solve real-life problems having more than a few hundred thousand examples with SVMs. This article proposes a new mixture of SVMs that can be easily implemented in parallel and where each SVM is trained on a small subset of the whole data set. Experiments on a large benchmark data set (Forest) yielded significant time improvement (time complexity appears empirically to locally grow linearly with the number of examples). In addition, and surprisingly, a significant improvement in generalization was observed.     

基于向量投影的支撑向量预选取

支撑向量机是近年来新兴的模式识别方法,在解决小样本、非线性及高维模式识别问题中表现出了突出的优点．但在支撑向量机中,支撑向量的选取相当困难,这也成为限制其应用的瓶颈问题．该文对支撑向量机的机理经过认真分析,研究其支撑向量的分布特性,在不影响分类性能的前提下,提出了基于向量投影的支撑向量预选取法,从训练样本中预先选择具有一定特征的边界向量来代替训练样本进行训练,这样就减少了训练样本,大大加快了支撑向量机的训练速度。     

Kernel Nearest-Neighbor Algorithm

The ‘kernel approach’ has attracted great attention with the development of support vector machine (SVM) and has been studied in a general way. It offers an alternative solution to increase the computational power of linear learning machines by mapping data into a high dimensional feature space. This ‘approach’ is extended to the well-known nearest-neighbor algorithm in this paper. It can be realized by substitution of a kernel distance metric for the original one in Hilbert space, and the corresponding algorithm is called kernel nearest-neighbor algorithm. Three data sets, an artificial data set, BUPA liver disorders database and USPS database, were used for testing. Kernel nearest-neighbor algorithm was compared with conventional nearest-neighbor algorithm and SVM Experiments show that kernel nearest-neighbor algorithm is more powerful than conventional nearest-neighbor algorithm, and it can compete with SVM. This revised version was published online in June 2006 with corrections to the Cover Date.     

序贯最小优化的改进算法

序贯最小优化(sequential minimal optimization,简称SMO)算法是目前解决大量数据下支持向量机(support vector machine,简称SVM)训练问题的一种十分有效的方法,但是确定工作集的可行方向策略会降低缓存的效率.给出了SMO的一种可行方向法的解释,进而提出了一种收益代价平衡的工作集选择方法,综合考虑与工作集相关的目标函数的下降量和计算代价,以提高缓存的效率.实验结果表明,该方法可以提高SMO算法的性能,缩短SVM分类器的训练时间,特别适用于样本较多、支持向量较多、非有界支持向量较多的情况.     

Forecasting foreign exchange rates using kernel methods

First, the all-important no free lunch theorems are introduced. Next, kernel methods, support vector machines (SVMs), preprocessing, model selection, feature selection, SVM software and the Fisher kernel are introduced and discussed. A hidden Markov model is trained on foreign exchange data to derive a Fisher kernel for an SVM, the DC algorithm and the Bayes point machine (BPM) are also used to learn the kernel on foreign exchange data. Further, the DC algorithm was used to learn the parameters of the hidden Markov model in the Fisher kernel, creating a hybrid algorithm. The mean net returns were positive for BPM; and BPM, the Fisher kernel, the DC algorithm and the hybrid algorithm were all improvements over a standard SVM in terms of both gross returns and net returns, but none achieved net returns as high as the genetic programming approach employed by Neely, Weller, and Dittmar (1997) and published in Neely, Weller, and Ulrich (2009). Two implementations of SVMs for Windows with semi-automated parameter selection are built.     

基于样本相似度曲面重构的核函数构造

根据数据特征构造核函数是当前SVM(支持向量机)的难点，文章采用重构数据样本相似度曲面的方法构造三种新的核函数．证明前两种核是Mercer核，并且讨论了三种核的存在性、稳定性和唯一性．指出核函数的本质是表达相似性的工具，核函数与Mercer条件、正定性、对称性互为非充分非必要条件．仿真研究表明，本核函数对学习样本本身的分类是完美的，而且其泛化能力优于传统核函数的SVM．     

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

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

Support vector machines for speaker and language recognition

Support vector machines (SVMs) have proven to be a powerful technique for pattern classification. SVMs map inputs into a high-dimensional space and then separate classes with a hyperplane. A critical aspect of using SVMs successfully is the design of the inner product, the kernel, induced by the high dimensional mapping. We consider the application of SVMs to speaker and language recognition. A key part of our approach is the use of a kernel that compares sequences of feature vectors and produces a measure of similarity. Our sequence kernel is based upon generalized linear discriminants. We show that this strategy has several important properties. First, the kernel uses an explicit expansion into SVM feature space—this property makes it possible to collapse all support vectors into a single model vector and have low computational complexity. Second, the SVM builds upon a simpler mean-squared error classifier to produce a more accurate system. Finally, the system is competitive and complimentary to other approaches, such as Gaussian mixture models (GMMs). We give results for the 2003 NIST speaker and language evaluations of the system and also show fusion with the traditional GMM approach.