Multiclass Probability Estimation With Support Vector Machines

Multiclass classification and probability estimation have important applications in data analytics. Support vector machines (SVMs) have shown great success in various real-world problems due to their high classification accuracy. However, one main limitation of standard SVMs is that they do not provide class probability estimates, and thus fail to offer uncertainty measure about class prediction. In this article, we propose a simple yet effective framework to endow kernel SVMs with the feature of multiclass probability estimation. The new probability estimator does not rely on any parametric assumption on the data distribution, therefore, it is flexible and robust. Theoretically, we show that the proposed estimator is asymptotically consistent. Computationally, the new procedure can be conveniently implemented using standard SVM softwares. Our extensive numerical studies demonstrate competitive performance of the new estimator when compared with existing methods such as multiple logistic regression, linear discrimination analysis, tree-based methods, and random forest, under various classification settings. Supplementary materials for this article are available online.     

Analysis of Support Vector Machines Regression

Support vector machines regression (SVMR) is a regularized learning algorithm in reproducing kernel Hilbert spaces with a loss function called the ε-insensitive loss function. Compared with the well-understood least square regression, the study of SVMR is not satisfactory, especially the quantitative estimates of the convergence of this algorithm. This paper provides an error analysis for SVMR, and introduces some recently developed methods for analysis of classification algorithms such as the projection operator and the iteration technique. The main result is an explicit learning rate for the SVMR algorithm under some assumptions. Research supported by NNSF of China No. 10471002, No. 10571010 and RFDP of China No. 20060001010.     

Feature Selection using Fuzzy Support Vector Machines

The feature selection consists of obtaining a subset of these features to optimally realize the task without the irrelevant ones. Since it can provide faster and cost-effective learning machines and also improve the prediction performance of the predictors, it is a crucial step in machine learning. The feature selection methods using support machines have obtained satisfactory results, but the noises and outliers often reduce the performance. In this paper, we propose a feature selection approach using fuzzy support vector machines and compare it with the previous work, the results of experiments on the UCI data sets show that feature selection using fuzzy SVM obtains better results than using SVM.     

Multicategory Classification by Support Vector Machines

We examine the problem of how to discriminate between objects of three or more classes. Specifically, we investigate how two-class discrimination methods can be extended to the multiclass case. We show how the linear programming (LP) approaches based on the work of Mangasarian and quadratic programming (QP) approaches based on Vapnik's Support Vector Machine (SVM) can be combined to yield two new approaches to the multiclass problem. In LP multiclass discrimination, a single linear program is used to construct a piecewise-linear classification function. In our proposed multiclass SVM method, a single quadratic program is used to construct a piecewise-nonlinear classification function. Each piece of this function can take the form of a polynomial, a radial basis function, or even a neural network. For the k > 2-class problems, the SVM method as originally proposed required the construction of a two-class SVM to separate each class from the remaining classes. Similarily, k two-class linear programs can be used for the multiclass problem. We performed an empirical study of the original LP method, the proposed k LP method, the proposed single QP method and the original k QP methods. We discuss the advantages and disadvantages of each approach.     

Massive Data Classification via Unconstrained Support Vector Machines

A highly accurate algorithm, based on support vector machines formulated as linear programs (Refs. 1–2), is proposed here as a completely unconstrained minimization problem (Ref. 3). Combined with a chunking procedure (Ref. 4), this approach, which requires nothing more complex than a linear equation solver, leads to a simple and accurate method for classifying million-point datasets. Because a 1-norm support vector machine underlies the proposed approach, the method suppresses input space features as well. A state-of-the-art linear programming package (CPLEX, Ref. 5) fails to solve problems handled by the proposed algorithm.This research was supported by National Science Foundation Grants CCR-0138308 and IIS-0511905.     

Gradient methods for multiple state optimal design problems

We optimise a distribution of two isotropic materials α I and β I (α < β) occupying the given body in R ^d . The optimality is described by an integral functional (cost) depending on temperatures u ₁, . . . , u _m of the body obtained for different source terms f ₁, . . . ,f _m with homogeneous Dirichlet boundary conditions. The relaxation of this optimal design problem with multiple state equations is needed, introducing the notion of composite materials as fine mixtures of different phases, mathematically described by the homogenisation theory. The necessary conditions of optimality are derived via the Gateaux derivative of the cost functional. Unfortunately, there could exist points in which necessary conditions of optimality do not give any information on the optimal design. In the case m < d we show that there exists an optimal design which is a rank-m sequential laminate with matrix material α I almost everywhere on Ω. Contrary to the optimality criteria method, which is commonly used for the numerical solution of optimal design problems (although it does not rely on a firm theory of convergence), this result enables us to effectively use classical gradient methods for minimising the cost functional.      

Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds

Many real applications can be formulated as nonlinear minimization problems with a single linear equality constraint and box constraints. We are interested in solving problems where the number of variables is so huge that basic operations, such as the evaluation of the objective function or the updating of its gradient, are very time consuming. Thus, for the considered class of problems (including dense quadratic programs), traditional optimization methods cannot be applied directly. In this paper, we define a decomposition algorithm model which employs, at each iteration, a descent search direction selected among a suitable set of sparse feasible directions. The algorithm is characterized by an acceptance rule of the updated point which on the one hand permits to choose the variables to be modified with a certain degree of freedom and on the other hand does not require the exact solution of any subproblem. The global convergence of the algorithm model is proved by assuming that the objective function is continuously differentiable and that the points of the level set have at least one component strictly between the lower and upper bounds. Numerical results on large-scale quadratic problems arising in the training of support vector machines show the effectiveness of an implemented decomposition scheme derived from the general algorithm model.     

半监督支持向量机及其在县域可持续发展综合实力评价中的应用

给出了基于全部风险(ORM)最小化基础上的半监督支持向量机分类算法,该算法通过加入工作集进行训练,提高了标准SVM对训练集提供信息不充分的数据集的分类泛化能力,而且能有效地处理大量的无标示数据.并将凹半监督支持向量机算法应用于县域可持续发展综合实力评价中.通过邯郸15个县作实证分析,论证了该算法的可行性和有效性.     

EMD-SVM在南京市月平均气温预测中的应用

南京市月平均气温具有非平稳性、噪声大、序列宽频等特征.为了提高温预测精度,本文提出一种经验模态分解(EMD)和支持向量机(SVM)回归相组合的预测模型(EMD-SVM).首先应用EMD分解算法把南京市月平均气温分解成不同尺度的基本模态分量(IMF),再运用支持向量机回归模型对每个IMF预测,最后将预测结果重构得到南京市月平均气温预测值.结果表明:EMD-SVM模型预测与单一支持向量机回归模型预测相比,平均预测精度提高0.59度,是一种有效的预测气温的模型.     

SSVM: A Smooth Support Vector Machine for Classification

Smoothing methods, extensively used for solving important mathematical programming problems and applications, are applied here to generate and solve an unconstrained smooth reformulation of the support vector machine for pattern classification using a completely arbitrary kernel. We term such reformulation a smooth support vector machine (SSVM). A fast Newton–Armijo algorithm for solving the SSVM converges globally and quadratically. Numerical results and comparisons are given to demonstrate the effectiveness and speed of the algorithm. On six publicly available datasets, tenfold cross validation correctness of SSVM was the highest compared with four other methods as well as the fastest. On larger problems, SSVM was comparable or faster than SVM ^light (T. Joachims, in Advances in Kernel Methods—Support Vector Learning, MIT Press: Cambridge, MA, 1999), SOR (O.L. Mangasarian and David R. Musicant, IEEE Transactions on Neural Networks, vol. 10, pp. 1032–1037, 1999) and SMO (J. Platt, in Advances in Kernel Methods—Support Vector Learning, MIT Press: Cambridge, MA, 1999). SSVM can also generate a highly nonlinear separating surface such as a checkerboard.     

Parallel algorithm for training multiclass proximal Support Vector Machines

In this paper we describe a proximal Support Vector Machine algorithm for multiclassification problem by one-vs-all scheme. The computational requirement for the new algorithm is almost the same as training one of its element binary proximal Support Vector Machines. Low rank approximation is taken to reduce computational costs when the kernel matrix is too large. An error bound estimation for the approximated solution is given, which is used as a stopping criteria for low rank approximation. A post-processing strategy is developed to overcome the difficulty arising from unbalanced data and to improve the classification accuracy. A parallel implementation of the algorithm using standard MPI communication routines is provided to handle large-scale problems and to accelerate the training process. Experiment results on several public datasets validate the effectiveness of our proposed algorithm.     

Fixed-size Least Squares Support Vector Machines: A Large Scale Application in Electrical Load Forecasting

Based on the Nyström approximation and the primal-dual formulation of the least squares support vector machines, it becomes possible to apply a nonlinear model to a large scale regression problem. This is done by using a sparse approximation of the nonlinear mapping induced by the kernel matrix, with an active selection of support vectors based on quadratic Renyi entropy criteria. The methodology is applied to the case of load forecasting as an example of a real-life large scale problem in industry. The forecasting performance, over ten different load series, shows satisfactory results when the sparse representation is built with less than 3% of the available sample.     

基于独立分量分析——最小二乘支持向量机的公路建设项目投资估算新模型

为快速、准确地进行公路建设项目投资估算,提出了一种新型的公路建设项目投资估算模型.该模型首先基于独立分量分析技术,根据最小互信息原理,有效分离出公路建设项目投资估算的独立影响因素源.然后,将这些独立影响因素源用于最小二乘支持向量机的训练,从而建立了基于独立分量分析技术—最小二乘支持向量机的公路建设项目投资估算模型.该模型将独立分量分析技术的盲信号分离能力与最小二乘支持向量机处理有限样本条件下非线性回归问题的优势有机结合,提高了模型预测的准确性.     

基于支持向量机的混沌时间序列模型在房产价格指数预测中的应用

针对房产价格指数的预测问题,建立了混沌时间序列的支持向量机的非线性预测模型.首先运用Cao氏法进行相空间重构,并利用改进型小数据量法计算最大的Lyapunov指数,分析上海房产价格指数时间序列的混沌特性.然后以最小嵌入维数作为支持向量机的输入节点,建立房地价格指数的预测模型.实例表明,该方法能较好地处理复杂的房地产数据,具有较高的泛化能力和很好的预测精度.     

Support vector machines for default prediction of SMEs based on technology credit

In Korea, many forms of credit guarantees have been issued to fund small and medium enterprises (SMEs) with a high degree of growth potential in technology. However, a high default rate among funded SMEs has been reported. In order to effectively manage such governmental funds, it is important to develop an accurate scoring model for selecting promising SMEs. This paper provides a support vector machines (SVM) model to predict the default of funded SMEs, considering various input variables such as financial ratios, economic indicators, and technology evaluation factors. The results show that the accuracy performance of the SVM model is better than that of back-propagation neural networks (BPNs) and logistic regression. It is expected that the proposed model can be applied to a wide range of technology evaluation and loan or investment decisions for technology-based SMEs.     

Kernel Logistic Regression and the Import Vector Machine

The support vector machine (SVM) is known for its good performance in two-class classification, but its extension to multiclass classification is still an ongoing research issue. In this article, we propose a new approach for classification, called the import vector machine (IVM), which is built on kernel logistic regression (KLR). We show that the IVM not only performs as well as the SVM in two-class classification, but also can naturally be generalized to the multiclass case. Furthermore, the IVM provides an estimate of the underlying probability. Similar to the support points of the SVM, the IVM model uses only a fraction of the training data to index kernel basis functions, typically a much smaller fraction than the SVM. This gives the IVM a potential computational advantage over the SVM.     

An optimal regularized projection method for solving ill-posed problems via dynamical systems method

A new regularized projection method was developed for numerically solving ill-posed equations of the first kind. This method consists of combining the dynamical systems method with an adaptive projection discretization scheme. Optimality of the proposed method was proved on wide classes of ill-posed problems.     

A convergent decomposition algorithm for support vector machines

In this work we consider nonlinear minimization problems with a single linear equality constraint and box constraints. In particular we are interested in solving problems where the number of variables is so huge that traditional optimization methods cannot be directly applied. Many interesting real world problems lead to the solution of large scale constrained problems with this structure. For example, the special subclass of problems with convex quadratic objective function plays a fundamental role in the training of Support Vector Machine, which is a technique for machine learning problems. For this particular subclass of convex quadratic problem, some convergent decomposition methods, based on the solution of a sequence of smaller subproblems, have been proposed. In this paper we define a new globally convergent decomposition algorithm that differs from the previous methods in the rule for the choice of the subproblem variables and in the presence of a proximal point modification in the objective function of the subproblems. In particular, the new rule for sequentially selecting the subproblems appears to be suited to tackle large scale problems, while the introduction of the proximal point term allows us to ensure the global convergence of the algorithm for the general case of nonconvex objective function. Furthermore, we report some preliminary numerical results on support vector classification problems with up to 100 thousands variables.     

An optimal randomized algorithm for d-variate zonoid depth

A randomized linear expected-time algorithm for computing the zonoid depth [R. Dyckerhoff, G. Koshevoy, K. Mosler, Zonoid data depth: Theory and computation, in: A. Prat (Ed.), COMPSTAT 1996—Proceedings in Computational Statistics, Physica-Verlag, Heidelberg, 1996, pp. 235–240; K. Mosler, Multivariate Dispersion, Central Regions and Depth. The Lift Zonoid Approach, Lecture Notes in Statistics, vol. 165, Springer-Verlag, New York, 2002] of a point with respect to a fixed dimensional point set is presented.