An extended one-versus-rest support vector machine for multi-label classification

Hybrid strategy, which generalizes a specific single-label algorithm while one or two data decomposition tricks are applied implicitly or explicitly, has become an effective and efficient tool to design and implement various multi-label classification algorithms. In this paper, we extend traditional binary support vector machine by introducing an approximate ranking loss as its empirical loss term to build a novel support vector machine for multi-label classification, resulting into a quadratic programming problem with different upper bounds of variables to characterize label correlation of individual instance. Further, our optimization problem can be solved via combining one-versus-rest data decomposition trick with modified binary support vector machine, which dramatically reduces computational cost. Experimental study on ten multi-label data sets illustrates that our method is a powerful candidate for multi-label classification, compared with four state-of-the-art multi-label classification approaches.     

Multi-label core vector machine with a zero label

Multi-label core vector machine (Rank-CVM) is an efficient and effective algorithm for multi-label classification. But there still exist two aspects to be improved: reducing training and testing computational costs further, and detecting relevant labels effectively. In this paper, we extend Rank-CVM via adding a zero label to construct its variant with a zero label, i.e., Rank-CVMz, which is formulated as the same quadratic programming form with a unit simplex constraint and non-negative ones as Rank-CVM, and then is solved by Frank–Wolfe method efficiently. Attractively, our Rank-CVMz has fewer variables to be solved than Rank-CVM, which speeds up training procedure dramatically. Further, the relevant labels are effectively detected by the zero label. Experimental results on 12 benchmark data sets demonstrate that our method achieves a competitive performance, compared with six existing multi-label algorithms according to six indicative instance-based measures. Moreover, on the average, our Rank-CVMz runs 83 times faster and has slightly fewer support vectors than its origin Rank-CVM.     

Random block coordinate descent method for multi-label support vector machine with a zero label

Multi-label support vector machine with a zero label (Rank-SVMz) is an effective SVM-type technique for multi-label classification, which is formulated as a quadratic programming (QP) problem with several disjoint equality constraints and lots of box ones, and then is solved by Frank–Wolfe method (FWM) embedded one-versus-rest (OVR) decomposition trick. However, it is still highly desirable to speed up the training and testing procedures of Rank-SVMz for many real world applications. Due to the special disjoint equality constraints, all variables to be solved in Rank-SVMz are naturally divided into several blocks via OVR technique. Therefore we propose a random block coordinate descent method (RBCDM) for Rank-SVMz in this paper. At each iteration, an entire QP problem is divided into a series of small-scale QP sub-problems, and then each QP sub-problem with a single equality constraint and many box ones is solved by sequential minimization optimization (SMO) used in binary SVM. The theoretical analysis shows that RBCDM has a much lower time complexity than FWM for Rank-SVMz. Our experimental results on six benchmark data sets demonstrate that, on the average, RBCDM runs 11 times faster, produces 12% fewer support vectors, and achieves a better classification performance than FWM for Rank-SVMz. Therefore Rank-SVMz with RBCDM is a powerful candidate for multi-label classification.     

Multi-label optimal margin distribution machine

Machine Learning - Multi-label support vector machine (Rank-SVM) is a classic and effective algorithm for multi-label classification. The pivotal idea is to maximize the minimum margin of label...     

基于线性规划支持向量回归的混沌系统预测

支持向量机是一种基于统计学习理论的新颖的机器学习方法,该方法已经广泛用于解决分类与回归问题。标准的支持向量机算法需要解一个二次规划问题,当训练样本较多时,其运算速度一般很慢。为了提高运算速度,介绍了一种基于线性规划的支持向量回归算法,并由此提出几种新的回归模型,同时将它们应用到混沌时间序列预测中,并比较了它们的预测性能。在实际应用中,可以根据具体情况灵活地选择所需模型。     

Iterative support vector machine with guaranteed accuracy and run time

Abstract: Using a conjugate gradient method, a novel iterative support vector machine (FISVM) is proposed, which is capable of generating a new non‐linear classifier. We attempt to solve a modified primal problem of proximal support vector machine (PSVM) and show that the solution of the modified primal problem reduces to solving just a system of linear equations as opposed to a quadratic programming problem in SVM. This algorithm not only has no requirement for special optimization solvers, such as linear or quadratic programming tools, but also guarantees fast convergence. The full algorithm merely needs four lines of MATLAB codes, which gives results that are similar to or better than that of several new learning algorithms, in terms of classification accuracy. Besides, the proposed stand‐alone approach is capable of dealing with instability of classification performance of smooth support vector machine, generalized proximal support vector machine, PSVM and reduced support vector machine. Experiments carried out on UCI datasets show the effectiveness of our approach.     

Self-Universum support vector machine

In this paper, for an improved twin support vector machine (TWSVM), we give it a theoretical explanation based on the concept of Universum and then name it Self-Universum support vector machine (SUSVM). For the binary classification problem, SUSVM takes the positive class and negative class as Universum separately to construct two classification problems with Universum; therefore, two nonparallel hyperplanes are derived. SUSVM has several improved advantages compared with TWSVMs. Furthermore, we improve SUSVM by formulating it as a pair of linear programming problems instead of quadratic programming problems (QPPs), which leads to the better generalization performance and less computational time. The effectiveness of the enhanced method is demonstrated by experimental results on several benchmark datasets.     

基于线性规划的多类支持向量机算法

多类支持向量机一般采用多个两类分类支持向量机来求解,这就需要解多个二次规划问题,从而导致算法的计算复杂性很高.根据一类分类思想,提出一种基于线性规划的多类分类算法及其分解形式,所给算法通过引入核函数能够独立地对每一类样本形成一个紧致的优化区域,从而达到分类的目的.对人工三螺旋线数据和几组实际数据库的识别实验表明,所给算法在保持良好的分类精度前提下,能有效地降低程序的运行时间.     

A support vector machine classifier with automatic confidence and its application to gender classification

In this paper, we propose a support vector machine with automatic confidence (SVMAC) for pattern classification. The main contributions of this work to learning machines are twofold. One is that we develop an algorithm for calculating the label confidence value of each training sample. Thus, the label confidence values of all of the training samples can be considered in training support vector machines. The other one is that we propose a method for incorporating the label confidence value of each training sample into learning and derive the corresponding quadratic programming problems. To demonstrate the effectiveness of the proposed SVMACs, a series of experiments are performed on three benchmarking pattern classification problems and a challenging gender classification problem. Experimental results show that the generalization performance of our SVMACs is superior to that of traditional SVMs.     

互补支持向量机

基于支持向量机的修正模型,得到一个互补支持向量机。利用Fischer-Burmeister互补函数,提出了一个新的下降算法。该算法不是基于支持向量机最优化问题本身,而是一个与之等价的互补问题。新算法不需要计算任何Hesse矩阵或矩阵求逆运算,实现简单,计算量小,克服了Mangasarian等人提出的LSVM算法需要求逆矩阵而造成不适合求解大规模非线性分类问题的缺陷。在不需要任何假设的情况下,证明了算法的全局收敛性。仿真实验表明算法是可行有效的。     

基于最小二乘支持向量回归的水质预测

水质系统是一个开放的、复杂的、非线性动力学系统,具有时变复杂性,针对水质预测方法的研究虽然已经取得了一些成果,但也存在预测精度与计算复杂度等难题。为此,本文提出一种基于最小二乘支持向量回归的水质预测算法。支持向量机是机器学习中一种常用的分类模型,通过核函数将非线性数据从低维映射到高维空间,在高维空间实现线性分类和回归,最小二乘支持向量回归（LS-SVR）利用所有的样本参与回归拟合,使得回归的损失函数不再只与小部分支持向量样本有关,而是由所有样本参与学习修正误差,提高预测精度;同时该算法将标准SVR求解问题由不等式的约束条件及凸二次规划问题转化成线性方程组来求解,提高了运算速度,解决了非线性复杂特性的水质预测问题。     

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.     

Clustered intrinsic label correlations for multi-label classification

Currently a consensus on multi-label classification is to exploit label correlations for performance improvement. Many approaches build one classifier for each label based on the one-versus-all strategy, and integrate classifiers by enforcing a regularization term on the global weights to exploit label correlations. However, this strategy might be suboptimal since it may be only part of the global weights that support the assumption. This paper proposes clustered intrinsic label correlations for multi-label classification (CILC), which extends traditional support vector machine to the multi-label setting. The predictive function of each classifier consists of two components: one component is the common information among all labels, and the other component is a label-specific one which highly depends on the corresponding label. The label-specific one representing the intrinsic label correlations is regularized by clustered structure assumption. The appealing features of the proposed method are that it separates the common information and the label-specific information of the labels and utilizes clustered structures among labels represented by the label-specific parts. The practical multi-label classification problems can be directly solved by the proposed CILC method, such as text categorization, image annotation and sentiment analysis. Experiments across five data sets validate the effectiveness of CILC, compared with six well-established multi-label classification algorithms.     

引入调整项的模糊孪生支持向量机

模糊孪生支持向量机是一种重要的机器学习方法,克服了噪声或异常数据对分类的影响;然而,该方法考虑的仍是经验风险,从而使得训练过程易出现过拟合现象。为了解决该问题,通过引入调整项,提出了一种改进的模糊孪生支持向量机模型,利用二次规划求解方法和超松弛迭代法对模型进行求解,获得了用于分类的决策面。实验中选取UCI标准数据集验证了所提方法的有效性。     

未确知支持向量机

提出一种处理样本中含有未确知信息(一种不确定性信息)的支持向量机未确知支持向量机(Unascertained support vector machine, USVM)算法.首先,以未确知数学为基础,将含有未确知信息的分类问题转化为求解未确知机会约束规划问题.然后,将其转化为与其等价的二次规划. 据此给出未确知支持向量机.理论分析和试验结果均表明,该算法是有效、可行的.     

Maximum margin of twin spheres machine with pinball loss for imbalanced data classification

The maximum margin of twin spheres support vector machine (MMTSVM) is an effective method for the imbalanced data classification. However, the hinge loss is used in the MMTSVM and easily leads to sensitivity for the noises and instability for re-sampling. In contrast, the pinball loss is related to the quantile distance and less sensitive to noises. To enhance the performance of MMTSVM, we propose a maximum margin of twin spheres machine with pinball loss (Pin-MMTSM) for the imbalanced data classification in this paper. The Pin-MMTSM finds two homocentric spheres by solving a quadratic programming problem (QPP) and a linear programming problem (LPP). The small sphere captures as many majority samples as possible; and the large sphere pushes out most minority samples by increasing the margin between two homocentric spheres. Moreover, our Pin-MMTSM is equipped with noise insensitivity by employing the pinball loss. Experimental results on eighteen imbalanced datasets indicate that our proposed Pin-MMTSM yields a good generalization performance.     

基于邻域原理计算海量数据支持向量的研究

使用支持向量机理论计算海量数据的支持向量是相当困难的.为了解决这个问题,提出了基于邻域原理计算支持向量的方法.在对支持向量机原理与邻域原理比较分析的基础上讨论了以下问题:(1)构建了从样本空间经过特征空间到扩维空间的复合内积函数,给出计算支持向量的邻域思想;(2)将支持向量机的理论建立在距离空间上,设计出了计算支持向量的邻域算法,从而把该算法理解为简化计算二次规划的方法;(3)实验结果说明,邻域原理可以有效地解决对海量数据计算支持向量的问题.     

求解互补支持向量机的非单调信赖域算法

求解支持向量机的核心问题是对一个大规模凸二次规划问题进行求解。基于支持向量机的修正模型,得到一个与之等价的互补问题,利用Fischer-Burmeister互补函数,从一个新的角度提出了求解互补支持向量机的非单调信赖域算法。新算法避免了求解Hesse矩阵或矩阵求逆运算,减少了工作量,提高了运算效率。在不需要任何假设的情况下,证明算法具有全局收敛性。数值实验结果表明,对于大规模非线性分类问题,该算法的运行速度比LSVM算法和下降法快,为求解SVM优化问题提供了一种新的可行方法。     

A new fuzzy support vector machine to evaluate credit risk

Due to recent financial crises and regulatory concerns, financial intermediaries' credit risk assessment is an area of renewed interest in both the academic world and the business community. In this paper, we propose a new fuzzy support vector machine to discriminate good creditors from bad ones. Because in credit scoring areas we usually cannot label one customer as absolutely good who is sure to repay in time, or absolutely bad who will default certainly, our new fuzzy support vector machine treats every sample as both positive and negative classes, but with different memberships. By this way we expect the new fuzzy support vector machine to have more generalization ability, while preserving the merit of insensitive to outliers, as the fuzzy support vector machine (SVM) proposed in previous papers. We reformulate this kind of two-group classification problem into a quadratic programming problem. Empirical tests on three public datasets show that it can have better discriminatory power than the standard support vector machine and the fuzzy support vector machine if appropriate kernel and membership generation method are chosen.     

关于支持向量机几何算法的研究

支持向量机是一种新的机器学习方法。它以统计学习理论为基础,从结构风险最小化原则出发,具有很好的泛化及推广能力。传统的SVM训练算法都是把原问题转化为对偶的二次规划问题进行求解。但对偶优化问题求解存在着计算量大、速度慢等问题。几何算法利用了训练集中的几何信息,从SVM的几何意义出发求解问题,并具有直观、计算精度高等优点,易于应用。在对支持向量分类机进行理论分析基础上,对其几何算法进行了初步研究并分析了其优缺点。