Weighted linear loss twin support vector machine for large-scale classification

Universal consistency of twin support vector machines

A classification problem aims at constructing a best classifier with the smallest risk. When the sample size approaches infinity, the learning algorithms for a classification problem are characterized by an asymptotical property, i.e., universal consistency. It plays a crucial role in measuring the construction of classification rules. A universal consistent algorithm ensures that the larger the sample size of the algorithm is, the more accurately the distribution of the samples could be reconstructed. Support vector machines (SVMs) are regarded as one of the most important models in binary classification problems. How to effectively extend SVMs to twin support vector machines (TWSVMs) so as to improve performance of classification has gained increasing interest in many research areas recently. Many variants for TWSVMs have been proposed and used in practice. Thus in this paper, we focus on the universal consistency of TWSVMs in a binary classification setting. We first give a general framework for TWSVM classifiers that unifies most of the variants of TWSVMs for binary classification problems. Based on it, we then investigate the universal consistency of TWSVMs. To do this, we give some useful definitions of risk, Bayes risk and universal consistency for TWSVMs. Theoretical results indicate that universal consistency is valid for various TWSVM classifiers under some certain conditions, including covering number, localized covering number and stability. For applications of our general framework, several variants of TWSVMs are considered.

Robust capped L1-norm twin support vector machine

Twin support vector machine (TWSVM) is a classical and effective classifier for binary classification. However, its robustness cannot be guaranteed due to the utilization of squared L2-norm distance that can usually exaggerate the influence of outliers. In this paper, we propose a new robust capped L1-norm twin support vector machine (CTWSVM), which sustains the advantages of TWSVM and promotes the robustness in solving a binary classification problem with outliers. The solution of the proposed method can be achieved by optimizing a pair of capped L1-norm related problems using a newly-designed effective iterative algorithm. Also, we present some theoretical analysis on existence of local optimum and convergence of the algorithm. Extensive experiments on an artificial dataset and several UCI datasets demonstrate the robustness and feasibility of our proposed CTWSVM.

Safe Screening Rules for Accelerating Twin Support Vector Machine Classification

The twin support vector machine (TSVM) is widely used in classification problems, but it is not efficient enough for large-scale data sets. Furthermore, to get the optimal parameter, the exhaustive grid search method is applied to TSVM. It is very time-consuming, especially for multiparameter models. Although many techniques have been presented to solve these problems, all of them always affect the performance of TSVM to some extent. In this paper, we propose a safe screening rule (SSR) for linear-TSVM, and give a modified SSR (MSSR) for nonlinear TSVM, which contains multiple parameters. The SSR and MSSR can delete most training samples and reduce the scale of TSVM before solving it. Sequential versions of SSR and MSSR are further introduced to substantially accelerate the whole parameter tuning process. One important advantage of SSR and MSSR is that they are safe, i.e., we can obtain the same solution as the original problem by utilizing them. Experiments on eight real-world data sets and an imbalanced data set with different imbalanced ratios demonstrate the efficiency and safety of SSR and MSSR.