Safe Screening Rules for Accelerating Twin Support Vector Machine Classification

A Survey on Scenario Theory, Complexity, and Compression-Based Learning and Generalization

This work investigates formal generalization error bounds that apply to support vector machines (SVMs) in realizable and agnostic learning problems. We focus on recently observed parallels between probably approximately correct (PAC)-learning bounds, such as compression and complexity-based bounds, and novel error guarantees derived within scenario theory. Scenario theory provides nonasymptotic and distributional-free error bounds for models trained by solving data-driven decision-making problems. Relevant theorems and assumptions are reviewed and discussed. We propose a numerical comparison of the tightness and effectiveness of theoretical error bounds for support vector classifiers trained on several randomized experiments from 13 real-life problems. This analysis allows for a fair comparison of different approaches from both conceptual and experimental standpoints. Based on the numerical results, we argue that the error guarantees derived from scenario theory are often tighter for realizable problems and always yield informative results, i.e., probability bounds tighter than a vacuous [0, 1] interval. This work promotes scenario theory as an alternative tool for model selection, structural-risk minimization, and generalization error analysis of SVMs. In this way, we hope to bring the communities of scenario and statistical learning theory closer, so that they can benefit from each other's insights.

Safe screening rules for multi-view support vector machines

Multi-view learning aims to make use of the advantages of different views to complement each other and fully mines the potential information in the data. However, the complexity of multi-view learning algorithm is much higher than that of single view learning algorithm. Based on the optimality conditions of two classical multi-view models: SVM-2K and multi-view twin support vector machine (MvTwSVM), this paper analyzes the corresponding relationship between dual variables and samples, and derives their safe screening rules for the first time, termed as SSR-SVM-2K and SSR-MvTwSVM. It can assign or delete four groups of different dual variables in advance before solving the optimization problem, so as to greatly reduce the scale of the optimization problem and improve the solution speed. More importantly, the safe screening criterion is "safe", that is, the solution of the reduced optimization problem is the same as that of the original problem before screening. In addition, we further give a sequence screening rule to speed up the parameter optimization process, and analyze its properties, including the similarities and differences of safe screening rules between multi-view SVMs and single-view SVMs, the computational complexity, and the relationship between the parameter interval and screening rate. Numerical experiments verify the effectiveness of the proposed methods.

A simple and reliable instance selection for fast training support vector machine: Valid Border Recognition

Support vector machines (SVMs) are powerful statistical learning tools, but their application to large datasets can cause time-consuming training complexity. To address this issue, various instance selection (IS) approaches have been proposed, which choose a small fraction of critical instances and screen out others before training. However, existing methods have not been able to balance accuracy and efficiency well. Some methods miss critical instances, while others use complicated selection schemes that require even more execution time than training with all original instances, thus violating the initial intention of IS. In this work, we present a newly developed IS method called Valid Border Recognition (VBR). VBR selects the closest heterogeneous neighbors as valid border instances and incorporates this process into the creation of a reduced Gaussian kernel matrix, thus minimizing the execution time. To improve reliability, we propose a strengthened version of VBR (SVBR). Based on VBR, SVBR gradually adds farther heterogeneous neighbors as complements until the Lagrange multipliers of already selected instances become stable. In numerical experiments, the effectiveness of our proposed methods is verified on benchmark and synthetic datasets in terms of accuracy, execution time and inference time.

Elastic Net Nonparallel Hyperplane Support Vector Machine and Its Geometrical Rationality

Twin support vector machine (TWSVM), which constructs two nonparallel classifying hyperplanes, is widely applied to various fields. However, TWSVM solves two quadratic programming problems (QPPs) separately such that the final classifiers lack consistency and enough prediction accuracy. Moreover, by reason of only considering the 1-norm penalty for slack variables, TWSVM is not well defined in the geometrical view. In this article, we propose a novel elastic net nonparallel hyperplane support vector machine (ENNHSVM), which adopts elastic net penalty for slack variables and constructs two nonparallel separating hyperplanes simultaneously. We further discuss the properties of ENNHSVM theoretically and derive the violation tolerance upper bound to better demonstrate the relative violations of training samples in the same class. In particular, we design a safe screening rule for ENNHSVM to speed up the calculations. We finally compare the performance of ENNHSVM on both synthetic datasets and benchmark datasets with the Lagrangian SVM, the twin parametric-margin SVM, the elastic net SVM, the TWSVM, and the nonparallel hyperplane SVM.

A Safe Feature Elimination Rule for L1-Regularized Logistic Regression

The L₁-regularized logistic regression (L1-LR) is popular for classification problems. To accelerate its training speed for high-dimensional data, techniques named safe screening rules have been proposed recently. They can safely delete the inactive features in data so as to greatly reduce the training cost of L1-LR. The screening power of these rules is determined by their corresponding safe regions, which is also the core technique of safe screening rules. In this paper, we introduce a new safe feature elimination rule (SFER) for L1-LR. Compared to existing safe rules, the safe region of SFER is improved in two aspects: (1) a smaller sphere region is constructed by using the strong convexity of dual L1-LR twice; (2) multiple half-spaces, which correspond to the potential active constraints, are added for further contraction. Both improvements can enhance the screening ability of SFER. As for the complexity of SFER, an iterative filtering framework is given by decomposing the safe region into multiple "domes". In this way, SFER admits a closed form solution and the identified features will not be scanned repeatedly. Experiments on ten benchmark data sets demonstrate that SFER gives superior performance than existing methods on training efficiency.

A Novel and Safe Two-Stage Screening Method for Support Vector Machine

To make support vector machine (SVM) applicable to large-scale data sets, safe screening rules are developed recently. The main idea is to reduce the scale of SVM by safely discarding the redundant training samples. Among existing safe screening rules, the dual screening method with variational inequalities (DVI) and the dynamic screening rule (DSR) based on duality gap are two representative strategies. DVI is efficient, while its safety may be affected by inaccurate solving algorithms. DSR is guaranteed to be safe; however, accurate feasible solutions are required for good efficiency. Based on the above-mentioned studies, in this paper, a two-stage screening (TSS) rule, which fully exploits the advantages of the above-mentioned two approaches and improves their shortcomings, is proposed. First, DVI is applied prior to training for sample screening. It reduces the scale of SVM and, meanwhile, produces a better initial feasible solution for DSR. Then, by embedding DSR into the solving algorithm, the solver becomes more accurate, and the safety of DVI can be strengthened. In the end, for safety guarantee, a postchecking step is added to search the wrongly identified samples and retrain them. To theoretically analyze the safety of DVI, an upper bound of the deviation in DVI is estimated, and a Safe-DVI is given based on it. To ensure the efficiency of TSS, the superiority of DVI over initial DSR is verified. In addition, kernel version of TSS is also given for nonlinear SVM. Numerical experiments on synthetic data sets and 12 real-world data sets verify the efficiency and safety of this TSS.