Functional iterative approaches for solving support vector classification problems based on generalized Huber loss

Classical support vector machine (SVM) and its twin variant twin support vector machine (TWSVM) utilize the Hinge loss that shows linear behaviour, whereas the least squares version of SVM (LSSVM) and twin least squares support vector machine (LSTSVM) uses L₂-norm of error which shows quadratic growth. The robust Huber loss function is considered as the generalization of Hinge loss and L₂-norm loss that behaves like the quadratic L₂-norm loss for closer error points and the linear Hinge loss after a specified distance. Three functional iterative approaches based on generalized Huber loss function are proposed in this paper to solve support vector classification problems of which one is based on SVM, i.e. generalized Huber support vector machine and the other two are in the spirit of TWSVM, namely generalized Huber twin support vector machine and regularization on generalized Huber twin support vector machine. The proposed approaches iteratively find the solutions and eliminate the requirements to solve any quadratic programming problem (QPP) as for SVM and TWSVM. The main advantages of the proposed approach are: firstly, utilize the robust Huber loss function for better generalization and for lesser sensitivity towards noise and outliers as compared to quadratic loss; secondly, it uses functional iterative scheme to find the solution that eliminates the need to solving QPP and also makes the proposed approaches faster. The efficacy of the proposed approach is established by performing numerical experiments on several real-world datasets and comparing the result with related methods, viz. SVM, TWSVM, LSSVM and LSTSVM. The classification results are convincing.

     

Mixed-norm linear support vector machine

This paper presents a new version of support vector machine (SVM) named l ₂ ? l _p SVM (0 < p < 1) which introduces the l _p -norm (0 < p < 1) of the normal vector of the decision plane in the standard linear SVM. To solve the nonconvex optimization problem in our model, an efficient algorithm is proposed using the constrained concave–convex procedure. Experiments with artificial data and real data demonstrate that our method is more effective than some popular methods in selecting relevant features and improving classification accuracy.     

Evolution strategies based adaptive Lp LS-SVM

Not only different databases but two classes of data within a database can also have different data structures. SVM and LS-SVM typically minimize the empirical ?-risk; regularized versions subject to fixed penalty (L₂ or L₁ penalty) are non-adaptive since their penalty forms are pre-determined. They often perform well only for certain types of situations. For example, LS-SVM with L₂ penalty is not preferred if the underlying model is sparse. This paper proposes an adaptive penalty learning procedure called evolution strategies (ES) based adaptive L_p least squares support vector machine (ES-based L_p LS-SVM) to address the above issue. By introducing multiple kernels, a L_p penalty based nonlinear objective function is derived. The iterative re-weighted minimal solver (IRMS) algorithm is used to solve the nonlinear function. Then evolution strategies (ES) is used to solve the multi-parameters optimization problem. Penalty parameterp, kernel and regularized parameters are adaptively selected by the proposed ES-based algorithm in the process of training the data, which makes it easier to achieve the optimal solution. Numerical experiments are conducted on two artificial data sets and six real world data sets. The experiment results show that the proposed procedure offer better generalization performance than the standard SVM, the LS-SVM and other improved algorithms.     

p范数正则化支持向量机分类算法

L2范数罚支持向量机(Support vector machine,SVM)是目前使用最广泛的分类器算法之一,同时实现特征选择和分类器构造的L1范数和L0范数罚SVM算法也已经提出.但是,这两个方法中,正则化阶次都是事先给定,预设p=2或p=1.而我们的实验研究显示,对于不同的数据,使用不同的正则化阶次,可以改进分类算法的预测准确率.本文提出p范数正则化SVM分类器算法设计新模式,正则化范数的阶次p可取范围为02范数罚SVM,L1范数罚SVM和L0范数罚SVM.     

Adaptive feature selection via a new version of support vector machine

This paper focuses on feature selection in classification. A new version of support vector machine (SVM) named p-norm support vector machine ( $p\in[0,1]$ ) is proposed. Different from the standard SVM, the p-norm $(p\in[0,1])$ of the normal vector of the decision plane is used which leads to more sparse solution. Our new model can not only select less features but also improve the classification accuracy by adjusting the parameter p. The numerical experiments results show that our p-norm SVM is more effective than some usual methods in feature selection.     

A Feature Selection Method for Projection Twin Support Vector Machine

In this paper, we propose a novel feature selection method which can suppress the input features during the process of model construction automatically. The main idea is to obtain better performance and sparse solutions by introducing Tikhonov regularization terms and measuring the objective function with \(L_1 \)-norm, based on projection twin support vector machine. Furthermore, to make the problem easy to solve, the exterior penalty theory is adopted to convert the original problem into an unconstrained problem. In contrast with twin support vector machine which needs solve two QPPs, our method only solves two linear equations by using a fast generalized Newton algorithm. In order to improve performance, a recursive algorithm is proposed to generate multiple projection axes for each class. To disclose the feasibility and effectiveness of our method, we conduct some experiments on UCI and Binary Alpha-digits data sets.     

KNN-based least squares twin support vector machine for pattern classification

The least squares twin support vector machine (LSTSVM) generates two non-parallel hyperplanes by directly solving a pair of linear equations as opposed to solving two quadratic programming problems (QPPs) in the conventional twin support vector machine (TSVM), which makes learning speed of LSTSVM faster than that of the TSVM. However, LSTSVM fails to discover underlying similarity information within samples which may be important for classification performance. To address the above problem, we apply the similarity information of samples into LSTSVM to build a novel non-parallel plane classifier, called K-nearest neighbor based least squares twin support vector machine (KNN-LSTSVM). The proposed method not only retains the superior advantage of LSTSVM which is simple and fast algorithm but also incorporates the inter-class and intra-class graphs into the model to improve classification accuracy and generalization ability. The experimental results on several synthetic as well as benchmark datasets demonstrate the efficiency of our proposed method. Finally, we further went on to investigate the effectiveness of our classifier for human action recognition application.     

ν-Nonparallel support vector machine for pattern classification

In this paper, we propose a novel nonparallel hyperplane classifier, named ν-nonparallel support vector machine (ν-NPSVM), for binary classification. Based on our recently proposed method, i.e., nonparallel support vector machine (NPSVM), which has been proved superior to the twin support vector machines, ν-NPSVM is parameterized by the quantity ν to let ones effectively control the number of support vectors. By combining the ν-support vector classification and the ν-support vector regression together to construct the primal problems, ν-NPSVM inherits the advantages of ν-support vector machine so that enables us to eliminate one of the other free parameters of the NPSVM: the accuracy parameter ε and the regularization constant C. We describe the algorithm, give some theoretical results concerning the meaning and the choice of ν, and also report the experimental results on lots of data sets to show the effectiveness of our method.     

Sparse regularization for semi-supervised classification

Manifold regularization (MR) is a promising regularization framework for semi-supervised learning, which introduces an additional penalty term to regularize the smoothness of functions on data manifolds and has been shown very effective in exploiting the underlying geometric structure of data for classification. It has been shown that the performance of the MR algorithms depends highly on the design of the additional penalty term on manifolds. In this paper, we propose a new approach to define the penalty term on manifolds by the sparse representations instead of the adjacency graphs of data. The process to build this novel penalty term has two steps. First, the best sparse linear reconstruction coefficients for each data point are computed by the l¹-norm minimization. Secondly, the learner is subject to a cost function which aims to preserve the sparse coefficients. The cost function is utilized as the new penalty term for regularization algorithms. Compared with previous semi-supervised learning algorithms, the new penalty term needs less input parameters and has strong discriminative power for classification. The least square classifier using our novel penalty term is proposed in this paper, which is called the Sparse Regularized Least Square Classification (S-RLSC) algorithm. Experiments on real-world data sets show that our algorithm is very effective.     

二阶收敛的光滑正则化压缩感知信号重构方法

目的压缩感知信号重构过程是求解不定线性系统稀疏解的过程。针对不定线性系统稀疏解3种求解方法不够鲁棒的问题:最小化l₀-范数属于NP问题,最小化l₁-范数的无解情况以及最小化l_p-范数的非凸问题,提出一种基于光滑正则凸优化的方法进行求解。方法为了获得全局最优解并保证算法的鲁棒性,首先,设计了全空间信号l₀-范数凸拟合函数作为优化的目标函数;其次,将n元函数优化问题转变为n个一元函数优化问题;最后,求解过程中利用快速收缩算法进行求解,使收敛速度达到二阶收敛。结果该算法无论在仿真数据集还是在真实数据集上,都取得了优于其他3种类型算法的效果。在仿真实验中,当信号维数大于150维时,该方法重构时间为其他算法的50%左右,具有快速性;在真实数据实验中,该方法重构出的信号与原始信号差的F-范数为其他算法的70%,具有良好的鲁棒性。结论本文算法为二阶收敛的凸优化算法,可确保快速收敛到全局最优解,适合处理大型数据,在信息检索、字典学习和图像压缩等领域具有较大的潜在应用价值。     

鲁棒最小二乘孪生支持向量机及其稀疏算法

最小二乘孪生支持向量机通过求解两个线性规划问题来代替求解复杂的二次规划问题,具有计算简单和训练速度快的优势。然而,最小二乘孪生支持向量机得到的超平面易受异常点影响且解缺乏稀疏性。针对这一问题,基于截断最小二乘损失提出了一种鲁棒最小二乘孪生支持向量机模型,并从理论上验证了模型对异常点具有鲁棒性。为使模型可处理大规模数据,基于表示定理和不完全Cholesky分解得到了新模型的稀疏解,并提出了适合处理带异常点的大规模数据的稀疏鲁棒最小二乘孪生支持向量机算法。数值实验表明,新算法比已有算法分类准确率、稀疏性、收敛速度分别提高了1.97%~37.7%、26~199倍和6.6~2 027.4倍。     

Alternating Direction Method for Covariance Selection Models

The covariance selection problem captures many applications in various fields, and it has been well studied in the literature. Recently, an l ₁-norm penalized log-likelihood model has been developed for the covariance selection problem, and this novel model is capable of completing the model selection and parameter estimation simultaneously. With the rapidly increasing magnitude of data, it is urged to consider efficient numerical algorithms for large-scale cases of the l ₁-norm penalized log-likelihood model. For this purpose, this paper develops the alternating direction method (ADM). Some preliminary numerical results show that the ADM approach is very efficient for large-scale cases of the l ₁-norm penalized log-likelihood model.     

Robust energy-based least squares twin support vector machines

Twin support vector machine (TSVM), least squares TSVM (LSTSVM) and energy-based LSTSVM (ELS-TSVM) satisfy only empirical risk minimization principle. Moreover, the matrices in their formulations are always positive semi-definite. To overcome these problems, we propose in this paper a robust energy-based least squares twin support vector machine algorithm, called RELS-TSVM for short. Unlike TSVM, LSTSVM and ELS-TSVM, our RELS-TSVM maximizes the margin with a positive definite matrix formulation and implements the structural risk minimization principle which embodies the marrow of statistical learning theory. Furthermore, RELS-TSVM utilizes energy parameters to reduce the effect of noise and outliers. Experimental results on several synthetic and real-world benchmark datasets show that RELS-TSVM not only yields better classification performance but also has a lower training time compared to ELS-TSVM, LSPTSVM, LSTSVM, TBSVM and TSVM.     

Face recognition by sparse discriminant analysis via joint L2,1-norm minimization

Recently, joint feature selection and subspace learning, which can perform feature selection and subspace learning simultaneously, is proposed and has encouraging ability on face recognition. In the literature, a framework of utilizing L_2,1-norm penalty term has also been presented, but some important algorithms cannot be covered, such as Fisher Linear Discriminant Analysis and Sparse Discriminant Analysis. Therefore, in this paper, we add L_2,1-norm penalty term on FLDA and propose a feasible solution by transforming its nonlinear model into linear regression type. In addition, we modify the optimization model of SDA by replacing elastic net with L_2,1-norm penalty term and present its optimization method. Experiments on three standard face databases illustrate FLDA and SDA via L_2,1-norm penalty term can significantly improve their recognition performance, and obtain inspiring results with low computation cost and for low-dimension feature.     

Estimating actual distances by norm functions: a comparison between the lk,p,θ-norm and the lb1,b2,θ-norm and a study about the selection of the data set

The aim of this paper is two-fold. First, the weighted l_p-norm, which has proved to be an accurate distance predicting function and has been proposed by several authors as the most suitable predictor of distances, is compared through an empirical study with the l_2b-norm, a function with the same number of parameters as the first one. The results show that neither distance function dominates the other. On the contrary, depending on the region considered either norm may be significantly better than the other. The second aim is to investigate how the selection of the data set representing the network of the region affects the ability of the distance predicting function for predicting distances, and to try to deduce how to obtain a suitable data set which adequately represents a given geographical region. Through another empirical study it is shown that the selection of the data set dramatically affects the accuracy of the predictions. To obtain a suitable data set it is important to choose a good sample size, and more importantly, the cities should be chosen so that they are distributed all over the region and represent the density of the cities in the region.     

Imbalanced data classification using second-order cone programming support vector machines

Learning from imbalanced data sets is an important machine learning challenge, especially in Support Vector Machines (SVM), where the assumption of equal cost of errors is made and each object is treated independently. Second-order cone programming SVM (SOCP-SVM) studies each class separately instead, providing quite an interesting formulation for the imbalanced classification task. This work presents a novel second-order cone programming (SOCP) formulation, based on the LP-SVM formulation principle: the bound of the VC dimension is loosened properly using the _l∞$l_{\infty }$-norm, and the margin is directly maximized using two margin variables associated with each class. A regularization parameter C is considered in order to control the trade-off between the maximization of these two margin variables. The proposed method has the following advantages: it provides better results, since it is specially designed for imbalanced classification, and it reduces computational complexity, since one conic restriction is eliminated. Experiments on benchmark imbalanced data sets demonstrate that our approach accomplishes the best classification performance, compared with the traditional SOCP-SVM formulation and with cost-sensitive formulations for linear SVM.     

TROP-ELM: A double-regularized ELM using LARS and Tikhonov regularization

In this paper an improvement of the optimally pruned extreme learning machine (OP-ELM) in the form of a L₂ regularization penalty applied within the OP-ELM is proposed. The OP-ELM originally proposes a wrapper methodology around the extreme learning machine (ELM) meant to reduce the sensitivity of the ELM to irrelevant variables and obtain more parsimonious models thanks to neuron pruning. The proposed modification of the OP-ELM uses a cascade of two regularization penalties: first a L₁ penalty to rank the neurons of the hidden layer, followed by a L₂ penalty on the regression weights (regression between hidden layer and output layer) for numerical stability and efficient pruning of the neurons. The new methodology is tested against state of the art methods such as support vector machines or Gaussian processes and the original ELM and OP-ELM, on 11 different data sets; it systematically outperforms the OP-ELM (average of 27% better mean square error) and provides more reliable results - in terms of standard deviation of the results - while remaining always less than one order of magnitude slower than the OP-ELM.     

Application of non-normal p-norm trapezoidal fuzzy number in reliability evaluation of electrical substations

This paper presented a non-normal p-norm trapezoidal fuzzy number–based fault tree technique to obtain the reliability analysis for substations system. Due to uncertainty in the collected data, all the failure probabilities are represented by non-normal p-norm trapezoidal fuzzy number. In this paper, the fault tree incorporated with the non-normal p-norm trapezoidal fuzzy number and minimal cut sets approach are used for reliability assessment of substations. An example of 66/11 kV substation is given to demonstrate the method. Further, fuzzy risk analysis problems are described to find out the probability of failure of each components of the system using linguistic variables, which could be used for managerial decision making and future system maintenance strategy.     

Density-based weighting multi-surface least squares classification with its applications

Traditionally, multi-plane support vector machines (SVM), including twin support vector machine (TWSVM) and least squares twin support vector machine (LSTSVM), consider all of points and view them as equally important points. In real cases, most of the samples of a dataset are highly correlated. These samples generally lie in the high-density regions and may be important for performances of classifiers. This motivates the rush toward new classifiers that can sufficiently take advantage of the points in the high-density regions. Illuminated by several new geometrically motivated algorithms, we propose density-based weighting multi-surface least squares classification (DWLSC) method, which is designed for classification. Considering the special features of multi-plane SVMs, DWLSC can measure the importance of points sharing the same labels by density weighting method and sufficiently make the full use of margin point information between pairs of points from different classes. It also includes naturally an extension of the non-linear case. In addition to keeping the respective advantages of both TWSVM and LSTSVM, our method improves the separation of the points sharing different classes and is shown to be better than other multi-plane classifiers in favor of reduction in space complexity, especially when confronted with the non-linear case. In addition, experimental evidence suggests that our method is effective in performing classification tasks.     

Research on parameter selection method for support vector machines

The kernel parameter and penalty parameter C are the main factors that affect the learning performance of the support vector machine. However, there are many deficiencies in the existing kernel parameters and penalty parameters C. These methods do not have high accuracy when it comes to classifying multi-category samples, and even ignore some of the samples to conduct training, which violates the integrity of the experimental data. In contrast, this paper improves the selection method of support vector machine kernel parameters and penalty parameters in two ways. First, it obtains the kernel parameter value by optimizing the maximum separation interval between the samples. Second, it optimizes the generalization ability estimation via the influence of the non-boundary support vector on the stability of the support vector machine. The method takes full account of all the training sample data, which is applicable to most sample types, and has the characteristics of low initialization requirements and high-test accuracy. The paper finally uses multiple sets of UCI sample data sets and facial image recognition to verify the method. The experimental results show that the method is feasible, effective and stable.