Incorporating prior knowledge in support vector machines for classification: A review

For classification, support vector machines (SVMs) have recently been introduced and quickly became the state of the art. Now, the incorporation of prior knowledge into SVMs is the key element that allows to increase the performance in many applications. This paper gives a review of the current state of research regarding the incorporation of two general types of prior knowledge into SVMs for classification. The particular forms of prior knowledge considered here are presented in two main groups: class-invariance and knowledge on the data. The first one includes invariances to transformations, to permutations and in domains of input space, whereas the second one contains knowledge on unlabeled data, the imbalance of the training set or the quality of the data. The methods are then described and classified into the three categories that have been used in literature: sample methods based on the modification of the training data, kernel methods based on the modification of the kernel and optimization methods based on the modification of the problem formulation. A recent method, developed for support vector regression, considers prior knowledge on arbitrary regions of the input space. It is exposed here when applied to the classification case. A discussion is then conducted to regroup sample and optimization methods under a regularization framework.     

Three-parameter sequential minimal optimization for support vector machines

The well-known sequential minimal optimization (SMO) algorithm is the most commonly used algorithm for numerical solutions of the support vector learning problems. At each iteration in the traditional SMO algorithm, also called 2PSMO algorithm in this paper, it jointly optimizes only two chosen parameters. The two parameters are selected either heuristically or randomly, whilst the optimization with respect to the two chosen parameters is performed analytically. The 2PSMO algorithm is naturally generalized to the three-parameter sequential minimal optimization (3PSMO) algorithm in this paper. At each iteration of this new algorithm, it jointly optimizes three chosen parameters. As in 2PSMO algorithm, the three parameters are selected either heuristically or randomly, whilst the optimization with respect to the three chosen parameters is performed analytically. Consequently, the main difference between these two algorithms is that the optimization is performed at each iteration of the 2PSMO algorithm on a line segment, whilst that of the 3PSMO algorithm on a two-dimensional region consisting of infinitely many line segments. This implies that the maximum can be attained more efficiently by 3PSMO algorithm. Main updating formulae of both algorithms for each support vector learning problem are presented. To assess the efficiency of the 3PSMO algorithm compared with the 2PSMO algorithm, 14 benchmark datasets, 7 for classification and 7 for regression, will be tested and numerical performances are compared. Simulation results demonstrate that the 3PSMO outperforms the 2PSMO algorithm significantly in both executing time and computation complexity.     

Density-induced margin support vector machines

This paper proposes a new classifier called density-induced margin support vector machines (DMSVMs). DMSVMs belong to a family of SVM-like classifiers. Thus, DMSVMs inherit good properties from support vector machines (SVMs), e.g., unique and global solution, and sparse representation for the decision function. For a given data set, DMSVMs require to extract relative density degrees for all training data points. These density degrees can be taken as relative margins of corresponding training data points. Moreover, we propose a method for estimating relative density degrees by using the K nearest neighbor method. We also show the upper bound on the leave-out-one error of DMSVMs for a binary classification problem and prove it. Promising results are obtained on toy as well as real-world data sets.     

Choosing the kernel parameters for support vector machines by the inter-cluster distance in the feature space

Determining the kernel and error penalty parameters for support vector machines (SVMs) is very problem-dependent in practice. A popular method to deciding the kernel parameters is the grid search method. In the training process, classifiers are trained with different kernel parameters, and only one of the classifiers is required for the testing process. This makes the training process time-consuming. In this paper we propose using the inter-cluster distances in the feature spaces to choose the kernel parameters. Calculating such distance costs much less computation time than training the corresponding SVM classifiers; thus the proper kernel parameters can be chosen much faster. Experiment results show that the inter-cluster distance can choose proper kernel parameters with which the testing accuracy of trained SVMs is competitive to the standard ones, and the training time can be significantly shortened.     

Support vector machines for interval discriminant analysis

The use of data represented by intervals can be caused by imprecision in the input information, incompleteness in patterns, discretization procedures, prior knowledge insertion or speed-up learning. All the existing support vector machine (SVM) approaches working on interval data use local kernels based on a certain distance between intervals, either by combining the interval distance with a kernel or by explicitly defining an interval kernel. This article introduces a new procedure for the linearly separable case, derived from convex optimization theory, inserting information directly into the standard SVM in the form of intervals, without taking any particular distance into consideration.     

Asymptotic efficiency of kernel support vector machines (SVM)

The paper analyzes the asymptotic properties of Vapnik’s SVM-estimates of a regression function as the size of the training sample tends to infinity. The estimation problem is considered as infinite-dimensional minimization of a regularized empirical risk functional in a reproducing kernel Hilbert space. The rate of convergence of the risk functional on SVM-estimates to its minimum value is established. The sufficient conditions for the uniform convergence of SVM-estimates to a true regression function with unit probability are given. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 81–97, July–August 2009     

一种支持向量机的混合核函数

核函数是支持向量机的核心,不同的核函数将产生不同的分类效果.由于普通核函数各有其利弊,为了得到学习能力和泛化能力较强的核函数,根据核函数的基本性质,两个核函数之和仍然是核函数,将局部核函数和全局核函数线性组合构成新的核函数--混合核函数.该核函数吸取了局部核函数和全局核函数的优点.利用混合核函数进行流程企业供应链预测实验,仿真结果验证了该核函数的有效性和正确性.     

Robust self-tuning semi-supervised learning

We investigate the issue of graph-based semi-supervised learning (SSL). The labeled and unlabeled data points are represented as vertices in an undirected weighted neighborhood graph, with the edge weights encoding the pairwise similarities between data objects in the same neighborhood. The SSL problem can be then formulated as a regularization problem on this graph. In this paper we propose a robust self-tuning graph-based SSL method, which (1) can determine the similarities between pairwise data points automatically; (2) is not sensitive to outliers. Promising experimental results are given for both synthetic and real data sets.     

e-Learning中基于支持向量机的个性化学习资源推送

e-Learning这种能满足个性化、适应性学习要求的重要学习方式,要求能协作感知学习者的学习情况,能依据学习情况自动推送个性化学习资源-将支持向量机这种机器学习方法应用到e-Learning中,并结合e-Learning系统的应用情况,对于学习样本的选取和预处理,以及支持向量机训练算法等进行了应用研究.解决了学习者学习情况评价分类,根据分类结果实现个性化学习资源的主动推送问题.     

An algorithm for semi-supervised learning in image retrieval

We study the problem of image retrieval based on semi-supervised learning. Semi-supervised learning has attracted a lot of attention in recent years. Different from traditional supervised learning. Semi-supervised learning makes use of both labeled and unlabeled data. In image retrieval, collecting labeled examples costs human efforts, while vast amounts of unlabeled data are often readily available and offer some additional information. In this paper, based on support vector machine (SVM), we introduce a semi-supervised learning method for image retrieval. The basic consideration of the method is that, if two data points are close to each, they should share the same label. Therefore, it is reasonable to search a projection with maximal margin and locality preserving property. We compare our method to standard SVM and transductive SVM. Experimental results show efficiency and effectiveness of our method.     

Possibilistic support vector machines

We propose new support vector machines (SVMs) that incorporate the geometric distribution of an input data set by associating each data point with a possibilistic membership, which measures the relative strength of the self class membership. By using a possibilistic distance measure based on the possibilistic membership, we reformulate conventional SVMs in three ways. The proposed methods are shown to have better classification performance than conventional SVMs in various tests.     

Decision confidence-based multi-level support vector machines

Support vector machines (SVM) have been showing high accuracy of prediction in many applications. However, as any statistical learning algorithm, SVM's accuracy drops if some of the training points are contaminated by an unknown source of noise. The choice of clean training points is critical to avoid the overfitting problem which occurs generally when the model is excessively complex, which is reflected by a high accuracy over the training set and a low accuracy over the testing set (unseen points). In this paper we present a new multi-level SVM architecture that splits the training set into points that are labeled as ‘easily classifiable’ which do not cause an increase in the model complexity and ‘non-easily classifiable’ which are responsible for increasing the complexity. This method is used to create an SVM architecture that yields on average a higher accuracy than a traditional soft margin SVM trained with the same training set. The architecture is tested on the well known US postal handwritten digit recognition problem, the Wisconsin breast cancer dataset and on the agitation detection dataset. The results show an increase in the overall accuracy for the three datasets. Throughout this paper the word confidence is used to denote the confidence over the decision as commonly used in the literature.     

A second order cone programming approach for semi-supervised learning

Semi-supervised learning (SSL) involves the training of a decision rule from both labeled and unlabeled data. In this paper, we propose a novel SSL algorithm based on the multiple clusters per class assumption. The proposed algorithm consists of two stages. In the first stage, we aim to capture the local cluster structure of the training data by using the k-nearest-neighbor (kNN) algorithm to split the data into a number of disjoint subsets. In the second stage, a maximal margin classifier based on the second order cone programming (SOCP) is introduced to learn an inductive decision function from the obtained subsets globally. For linear classification problems, once the kNN algorithm has been performed, the proposed algorithm trains a classifier using only the first and second order moments of the subsets without considering individual data points. Since the number of subsets is usually much smaller than the number of training points, the proposed algorithm is efficient for handling big data sets with a large amount of unlabeled data. Despite its simplicity, the classification performance of the proposed algorithm is guaranteed by the maximal margin classifier. We demonstrate the efficiency and effectiveness of the proposed algorithm on both synthetic and real-world data sets.     

Feature selection in the Laplacian support vector machine

Traditional classifiers including support vector machines use only labeled data in training. However, labeled instances are often difficult, costly, or time consuming to obtain while unlabeled instances are relatively easy to collect. The goal of semi-supervised learning is to improve the classification accuracy by using unlabeled data together with a few labeled data in training classifiers. Recently, the Laplacian support vector machine has been proposed as an extension of the support vector machine to semi-supervised learning. The Laplacian support vector machine has drawbacks in its interpretability as the support vector machine has. Also it performs poorly when there are many non-informative features in the training data because the final classifier is expressed as a linear combination of informative as well as non-informative features. We introduce a variant of the Laplacian support vector machine that is capable of feature selection based on functional analysis of variance decomposition. Through synthetic and benchmark data analysis, we illustrate that our method can be a useful tool in semi-supervised learning.     

A review of optimization methodologies in support vector machines

Support vector machines (SVMs) are theoretically well-justified machine learning techniques, which have also been successfully applied to many real-world domains. The use of optimization methodologies plays a central role in finding solutions of SVMs. This paper reviews representative and state-of-the-art techniques for optimizing the training of SVMs, especially SVMs for classification. The objective of this paper is to provide readers an overview of the basic elements and recent advances for training SVMs and enable them to develop and implement new optimization strategies for SVM-related research at their disposal.     

Optimal feature selection for support vector machines

Selecting relevant features for support vector machine (SVM) classifiers is important for a variety of reasons such as generalization performance, computational efficiency, and feature interpretability. Traditional SVM approaches to feature selection typically extract features and learn SVM parameters independently. Independently performing these two steps might result in a loss of information related to the classification process. This paper proposes a convex energy-based framework to jointly perform feature selection and SVM parameter learning for linear and non-linear kernels. Experiments on various databases show significant reduction of features used while maintaining classification performance.     

基于支持向量机的加筋板健康监测

故障样本缺乏是制约智能监测发展的重要原因。支持向量机(SVM)基于结构风险最小化原则,对小样本决策具有较好的学习推广性。将SVM的多类分类算法用于航空航天结构中的加强筋结构健康监测,并与BP神经网络进行对比研究,取得了满意的效果。试验表明:在小样本条件下,SVM具有比BP网络更好的分类性能。     

A multi-manifold semi-supervised Gaussian mixture model for pattern classification

Semi-supervised Gaussian mixture model (SGMM) has been successfully applied to a wide range of engineering and scientific fields, including text classification, image retrieval, and biometric identification. Recently, many studies have shown that naturally occurring data may reside on or near manifold structures in ambient space. In this paper, we study the use of SGMM for data sets containing multiple separated or intersecting manifold structures. We propose a new multi-manifold regularized, semi-supervised Gaussian mixture model (M2SGMM) for classifying multiple manifolds. Specifically, we model the data manifold using a similarity graph with local and geometrical consistency properties. The geometrical similarity is measured by a novel application of local tangent space. We regularize the model parameters of the SGMM by incorporating the enhanced Laplacian of the graph. Experiments demonstrate the effectiveness of the proposed approach.     

Optimizing resources in model selection for support vector machine

Tuning support vector machine (SVM) hyperparameters is an important step in achieving a high-performance learning machine. It is usually done by minimizing an estimate of generalization error based on the bounds of the leave-one-out (LOO) such as radius-margin bound and on the performance measures such as generalized approximate cross-validation (GACV), empirical error, etc. These usual automatic methods used to tune the hyperparameters require an inversion of the Gram-Schmidt matrix or a resolution of an extra-quadratic programming problem. In the case of a large data set these methods require the addition of huge amounts of memory and a long CPU time to the already significant resources used in SVM training. In this paper, we propose a fast method based on an approximation of the gradient of the empirical error, along with incremental learning, which reduces the resources required both in terms of processing time and of storage space. We tested our method on several benchmarks, which produced promising results confirming our approach. Furthermore, it is worth noting that the gain time increases when the data set is large.