Tong Luo, Lawrence Hall, Dmitry B. Goldgof et al. · 2006
Support vector machines are very accurate classifiers and have been widely used in many applications. However, the training and to a lesser extent prediction time of support vector machines on very large data sets can be very long. This paper presents a fast compression method to scale up support vector machines to large data sets. A simple bit reduction method is applied to reduce the cardinality of the data by weighting representative examples. We then develop support vector machines which may be trained on weighted data. Experiments indicate that the bit reduction support vector machine produces a significant reduction in the time required for both training and prediction with minimum loss in accuracy. It is also shown to be more accurate than random sampling, when the data is not over-compressed.
Cited by 10
Frédéric Magoulès, Hai‐Xiang Zhao · 2016
Cited by 0
Lin Ye, Ping Ling · 2024
Support Vector Machine (SVM) is an algorithm based on statistical theory and the principle of structural risk minimization, known for its excellent generalization performance. However, with the increase in the number of training samples, the learning efficiency of SVM decreases significantly, requiring a large amount of storage space and computation during the training process, resulting in slow training speed of SVM. Meanwhile, due to the sensitivity of SVM algorithm to noisy data, the existence of noise in the training data may lead to bias in the classification results. To overcome these problems, a Boundary-Points-based Reduction Support Vector Machine (BPR_SVM) algorithm is proposed. Firstly, the centered kernel alignment (CKA) method is introduced to calculate the similarity between each sample and samples of different classes, and a corresponding sample contribution formula is designed to determine whether it may be a boundary point. Then, inspired by the K-nearest neighbors method, refinement selection is carried out by computing the number of samples of the same class in each sample's neighborhood set to reduce the size of samples, removing samples in boundary set that are heavily mixed or crossed with samples of different classes and eliminating the influence of noise points and outlier points in the boundary training samples on the decision hyperplane. Finally, efficient reduction of the training samples is achieved. Experimental results on classical datasets show that, compared with similar algorithms, the BPR _ SVM algorithm speeds up the training process without the decrease of classification accuracy.
Cited by 0
Jinbo Bi, Kristin P. Bennett, Mark J. Embrechts et al. · 2003
We describe a methodology for performing variable ranking and selection using support vector machines (SVMs). The method constructs a series of sparse linear SVMs to generate linear models that can generalize well, and uses a subset of nonzero weighted variables found by the linear models to produce a final nonlinear model. The method exploits the fact that a linear SVM (no kernels) with ℓ1-norm regularization inherently performs variable selection as a side-effect of minimizing capacity of the SVM model. The distribution of the linear model weights provides a mechanism for ranking and interpreting the effects of variables. Starplots are used to visualize the magnitude and variance of the weights for each variable. We illustrate the effectiveness of the methodology on synthetic data, benchmark problems, and challenging regression problems in drug design. This method can dramatically reduce the number of variables and outperforms SVMs trained using all attributes and using the attributes selected according to correlation coefficients. The visualization of the resulting models is useful for understanding the role of underlying variables.
Cited by 419
Riera Molina, Carles Roger · QRU Quaderns de Recerca en Urbanisme · 2014
Treball acadèmic realitzat a la Facultat de Matemàtiques de la Universitat de Barcelona
Cited by 0Open access
Amin Allahyar, Hadi Sadoghi Yazdi · 2014
Since introduction, the Support Vector Machines (SVM) has been popularly used in machine learning and data mining tasks due to their strong mathematical background and promising result. Nevertheless, they are noticeably slow in the prediction stage. The speed is influenced by number of support vectors determined in the training phase. Motivated by this fact, several studies are done to reduce the number of support vectors. The reduction should consider the degeneration of learning quality and preserve it at much as possible. Most previous methodologies either reduce the training set or apply a post-processing step to reduce the number of support vectors. In this paper, we proposed a new SVM cost function called Step Regularized Support Vector Machine (SRSVM), which is a standard SVM with extra constrained to reduce the number of support vectors, which can be defined by user. Experimental results are done to evaluate the efficiency and speed of proposed algorithm. SRSVM are also compared to other related SVM algorithms. The comparisons showed that the proposed method is effective in reducing number of support vectors while preserving the high performance of the classifier.
Cited by 0
Qing Tao, Dejun Chu, Jue Wang · IEEE Transactions on Neural Networks · 2008
The usual dimensionality reduction technique in supervised learning is mainly based on linear discriminant analysis (LDA), but it suffers from singularity or undersampled problems. On the other hand, a regular support vector machine (SVM) separates the data only in terms of one single direction of maximum margin, and the classification accuracy may be not good enough. In this letter, a recursive SVM (RSVM) is presented, in which several orthogonal directions that best separate the data with the maximum margin are obtained. Theoretical analysis shows that a completely orthogonal basis can be derived in feature subspace spanned by the training samples and the margin is decreasing along the recursive components in linearly separable cases. As a result, a new dimensionality reduction technique based on multilevel maximum margin components and then a classifier with high accuracy are achieved. Experiments in synthetic and several real data sets show that RSVM using multilevel maximum margin features can do efficient dimensionality reduction and outperform regular SVM in binary classification problems.
Cited by 65
Kuan-ming Lin · 2002
Recently two kinds of reduction techniques which aimed at saving training time for SVM problems with nonlinear kernels were proposed. Instead of solving the standard SVM formulation, these methods explicitly alter the SVM formulation, and solutions for them are used to classify data. The first approach, reduced support vector machine (RSVM) [21], preselects a subset of data as support vectors and solves a smaller optimization problem. The second approach [11] uses imcomplete Cholesky factorization (ICF) to obtain a low-rank approximation of the kernel matrix. Therefore, an easier optimization problem is obtained. We find that several issues of their practical uses have not been fully discussed yet. For example, we do not know if they possess comparable generalization ability as the standard SVM. In addition, we would like to see for how large problems they outperform SVM on training time. In this thesis we show that the formulation of each technique is already in a form of linear SVM and discuss several suitable implementations. Experiments indicate that in general the test accuracy of both techniques is a little lower than that of the standard SVM. In addition, for problems with up to tens of thousands of data, if the percentage of support vectors is not high, existing implementations for SVM is quite competitive on the training time. Thus, the two techniques will be mainly useful for either larger problems or those with many support vectors. Experiments in this thesis also serve as comparisons of (1) different implementations for linear SVM; (2) standard SVM using linear and quadratic cost functions; and (3) two ICF algorithms for positive definite dense matrices. ii
Cited by 0
NTUR (臺灣機構典藏) · 2002
Cited by 0
Jakovljević, Živana · MACHINERY - Repository of the Faculty of Mechanical Engineering (University of Belgrade) · 2012
This paper explores the possibilities of point cloud reduction using \epsilon insensitive support vector regression (\epsilon-SVR). \epsilon-SVR is a technique that can carry out the regression using different kernel functions (sigmoid, radial basis function, B-spline, spline, etc.) and it is suitable for detection of flat regions and regions with high curvature in scanned data. Using \epsilon-SVR the density of preserved points is adaptive – preserved points are denser at highly curved region and rare at flat regions. Adjusting the error cost in the regression, the number of preserved points can be fine tuned.
Cited by 0Open access
Le-Minh Nguyen, Akira Shimazu, Susumu Horiguchi et al. · 2004
This paper investigates a novel application of support vector machines (SVMs) for sentence reduction. We also propose a new probabilistic sentence reduction method based on support vector machine learning. Experimental results show that the proposed methods outperform earlier methods in term of sentence reduction performance.
Cited by 24Open access
Ho Gi Jung, Gahyun Kim · IEEE Transactions on Intelligent Transportation Systems · 2013
Although a support vector machine (SVM) is one of the most frequently used classifiers in the field of intelligent transportation systems and shows competitive performances in various problems, it has the disadvantage of requiring relatively large computations in the testing phase. To make up for this weakness, diverse methods have been researched to reduce the number of support vectors determining the computations in the testing phase. This paper is intended to help engineers using the SVM to easily apply support vector number reduction to their own particular problems by providing a state-of-the-art survey and quantitatively comparing three implementations belonging to postpruning, which exploits the result of a standard SVM. In particular, this paper confirms that the support vector number of a pedestrian classifier using a histogram-of-oriented-gradient-based feature and a radial-basis-function-kernel-based SVM can be reduced by more than 99.5% without any accuracy degradation using iterative preimage addition, which can be downloaded from the Internet.
Cited by 25
Hwei-Jen Lin, Jih Pin Yeh · Applied Mathematics and Computation · 2009
Cited by 42
Yu Hui, Sun Wenzhu, Zhou Xiuzhi et al. · 2016
Support vector regression (SVR) has become one of the most promising methods for function approximation and regression estimation. However, SVR has a time complexity of O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) and a space complexity of O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ). When dealing with very large sizes of training sets, SVR takes a lot computational time. To solve this problem, a method called heuristic sample reduction (HSR) is proposed for obtaining a reduced training set that is manageable for SVR. HSR maintains the regression accuracy of SVR by building the reduced training set heuristically with the samples selected from the original. The experimental result shows that the method is very effective.
Cited by 4
山北昌毅, MASAKI YAMAKITA · Tokyo Tech Research Repository (Tokyo Institute of Technology) · 2014
Cited by 0
Vahid R. Riasati, Wenhue Gao · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2012
Principal Component Analysis (PCA) has been used in a variety of applications like feature extraction for classification, data compression and dimensionality reduction. Often, a small set of principal components are sufficient to capture the largest variations in the data. As a result, the eigen-values of the data covariance matrix with the lowest magnitude are ignored (along with their corresponding eigen-vectors) and the remaining eigenvectors are used for a 'coarse' representation of the data. It is well known that this process of choosing a few principal components naturally induces a loss in information from a signal reconstruction standpoint. We propose a new technique to represent the data in terms of a new set of basis vectors where the high-frequency detail is preserved, at the expense of a 'feature-scale blurring'. In other words, the 'blurring' that occurs due to possible colinearities in the bases vectors is relative to the eigen-features' scales; this is inherently different from a systematic blurring function. Instead of thresholding the eigen-values, we retain all eigen-values, and apply thresholds on the components of each eigen-vector separately. The resulting basis vectors can no longer be interpreted as eigenvectors and will, in general, lose their orthogonality properties, but offer benefits in terms of preserving detail that is crucial for classification tasks. We test the merits of this new basis representation for magnitude synthetic aperture radar (SAR) Automatic Target Recognition (ATR). A feature vector is obtained by projecting a SAR image onto the aforementioned basis. Decision engines such as support vector machines (SVMs) are trained on example feature vectors per class and ultimately used to recognize the target class in real-time. Experimental validation are performed on the MSTAR database and involve comparisons against a PCA based ATR algorithm.
Cited by 2
Daniel Garc · 2007
Support Vector Machines (SVMs) with few support vectors are quite desirable, as they have a fast application to new, unseen pat- terns. In this work we shall study the coefficient structure of the dual representation of SVMs constructed for nonlinearly separable problems through kernel perceptron training. We shall relate them with the margin of their support vectors (SVs) and also with the number of iterations in which these SVs take part. These considerations will lead to a remove- and-retrain procedure for building SVMs with a small number of SVs where both suitably small and large coefficient SVs will be taken out from the training sample. Besides providing a significant SV reduction, our method's computational cost is comparable to that of a single SVM training.
Cited by 0
Mainak Biswas, Sanjeev Kumar, Truong Q. Nguyen et al. · Journal of the Society for Information Display · 2007
Abstract— A compression artifact‐reduction algorithm based on support vector regression is proposed. The algorithm belongs to a broad family of standard reconstruction methods, but a standardization model is determined from a set of training samples of original images and the corresponding noise‐corrupted version. As opposed to artifact‐reduction methods specific to each type of compression artifact ( e.g. , blocking, ringing, etc. ), we treat such artifacts as a manifestation of the same problem, which is the quantization of DCT coefficients. In the testing step, the algorithm tries to undo the effect of quantization by using the relationship between the original and artifact‐corrupted image, determined during the training step. Experimental results exhibit significant reduction in all types of compression artifacts.
Cited by 2
Nicola Ancona, Grazia Cicirelli, A. Distante · 2003
We focus on two central issues regarding the application of support vector machines (SVM) for classification in real contexts. The first one deals with the reduction of the computational complexity of a reference classifier during the test phase, without increasing the generalization error of the classifier. In particular, we show that the complexity in the test phase can be reduced by training SVM classifiers on a new set of uncorrelated features obtained by using the principal component analysis and explicitly mapping the new input space in the feature space induced by the adopted kernel function. The second issue deals with the problem of parameter selection. In particular we show that the receiver operating characteristic curves, measured on a suitable validation set, are effective for selecting among the classifiers the machine implements the one having performances similar to the reference classifier. We address these two issues in the context of object detection in images and in particular for the specific problem of detecting goal during a football match.
Cited by 5
ZHANG Daili, WANG Tinghua, ZHU Xinglin · SHILAP Revista de lepidopterología · 2024
Support vector machine(SVM) is a supervised machine learning algorithm developed based on statistical learning theory and the principle of structural risk minimization,which effectively overcomes the problems of local minimum and curse of dimensionality and has good generalization performance.SVM has been widely used in the fields of pattern recognition and artificial intelligence.However,the learning efficiency of SVM decreases significantly with the increase of the number of training samples.For large-scale training datasets,the traditional SVM with standard optimization methods will be confronted with the problems of excessive memory requirements,slow training speed,and sometimes even being unable to execute.To alleviate the problems of high storage requirements and long training time of SVM on large-scale training sets,scholars have proposed SVM sample reduction algorithms.This paper firstly introduces the theoretical basis of the SVM and then systematically reviews the current research status of the SVM sample reduction algorithms from five aspects based on clustering,geometric analysis,active learning,incremental learning and random sampling,respectively.And it discusses the advantages and disadvantages of these algorithms,and finally presents an outlook on the future research of the SVM sample reduction methods.
Cited by 0Open access