A Novel Model of Working Set Selection for SMO Decomposition Methods
Published 1 October 2007Open access
Zhendong Zhao, Lei Yuan, Yuxuan Wang, Forrest Sheng Bao, Shunyi Zhang, Yanfei Sun
Citations24
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new model for working set selection in sequential minimal optimization (SMO) decomposition methods is proposed, which selects B as working set without reselection.
Abstract
In the process of training support vector machines (SVMs) by decomposition methods, working set selection is an important technique, and some exciting schemes were employed into this field. To improve working set selection, we propose a new model for working set selection in sequential minimal optimization (SMO) decomposition methods. In this model, it selects B as working set without reselection. Some properties are given by simple proof, and experiments demonstrate that the proposed method is in general faster than existing methods.
Keywords
Computer Science
Machine LearningSupport-vector networks
40,463 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
The MIT Press eBooksFast Training of Support Vector Machines Using Sequential Minimal Optimization
5,462 Citations1998John Platt
Training support vector machines: an application to face detection
2,496 Citations2002E. Osuna, Robert M. Freund +1 more
A decomposition algorithm that guarantees global optimality, and can be used to train SVM's over very large data sets is presented, and the feasibility of the approach on a face detection problem that involves a data set of 50,000 data points is demonstrated.
TechnometricsMachine Learning, Neural and Statistical Classification
2,188 Citations1995Bill Fulkerson, D. Michie +2 more
Neural ComputationImprovements to Platt's SMO Algorithm for SVM Classifier Design
1,817 Citations2001S. Sathiya Keerthi, Shirish Shevade +2 more
Using clues from the KKT conditions for the dual problem, two threshold parameters are employed to derive modifications of SMO that perform significantly faster than the original SMO on all benchmark data sets tried.
Mining quantitative association rules in large relational tables
1,484 Citations1996Ramakrishnan Srikant, Rakesh Agrawal
This work deals with quantitative attributes by fine-partitioning the values of the attribute and then combining adjacent partitions as necessary and introduces measures of partial completeness which quantify the information lost due to partitioning.
Journal of Machine Learning ResearchWorking Set Selection Using Second Order Information for Training Support Vector Machines
1,413 Citations2005Rong-En Fan, Pai-Hsuen Chen +1 more
A new technique for working set selection in SMO-type decomposition methods that uses second order information to achieve fast convergence andoretical properties such as linear convergence are established.
Efficient mining of emerging patterns
1,005 Citations1999Guozhu Dong, Jinyan Li
It is believed that EPs with low to medium support, such as 1%-20%, can give useful new insights and guidance to experts, in even “well understood” applications.
ACM SIGMOD RecordMining quantitative association rules in large relational tables
573 Citations1996Ramakrishnan Srikant, Rakesh Agrawal
Data Mining and Knowledge DiscoveryDetecting Group Differences: Mining Contrast Sets
362 Citations2001Stephen D. Bay, Michael J. Pazzani
This work provides a search algorithm for mining contrast sets with pruning rules that drastically reduce the computational complexity and post-process the results to present a subset that is surprising to the user given what the user has already shown.
IEEE Transactions on Neural NetworksA Study on SMO-Type Decomposition Methods for Support Vector Machines
345 Citations2006Pai-Hsuen Chen, Rong-En Fan +1 more
The main results include a simple asymptotic convergence proof, a general explanation of the shrinking and caching techniques, and the linear convergence of the methods.
Machine LearningEfficient SVM Regression Training with SMO
317 Citations2002Gary William Flake, Steve Lawrence
This work generalizes SMO so that it can handle regression problems, and addresses problems with several modifications that enable caching to be effectively used with SMO.
Knowledge Discovery and Measures of Interest
222 Citations2001Robert J. Hilderman, Howard J. Hamilton
This paper presents a data mining technique and an interestingness framework based on heuristic measures of interestingness that were developed in the second part of this monograph on interestingness and data mining.
Detecting change in categorical data
194 Citations1999Stephen D. Bay, Michael J. Pazzani
An algorithm for mining contrast-sets as well as several pruning rules to reduce the computational complexity are provided and a subset that is surprising to the user given what has already been shown is presented.
A statistical theory for quantitative association rules
147 Citations1999Yonatan Aumann, Yehuda Lindell
On detecting differences between groups
109 Citations2003Geoffrey I. Webb, Shane M. Butler +1 more
It is observed that straightforward application of an existing commercial rule-discovery system, Magnum Opus, could successfully perform the contrast-set-mining task, leading to the realization that contrast- set mining is a special case of the more general rule-Discovery task.
Building projectable classifiers of arbitrary complexity
97 Citations1996Tin Kam Ho, E. M. Kleinberg
This work presents a method that constructs a classifier up to arbitrary complexity while presenting generalization accuracy, and reveals that the conflict is resolvable by building classifiers based on projectable elements, which are weak discriminators that perform equally well for both training and testing data.
Discovering associations with numeric variables
89 Citations2001Geoffrey I. Webb
This paper further develops Aumann and Lindell's proposal for a variant of association rules for which the consequent is a numeric variable and it is argued that these rules can discover useful interactions with numeric data that cannot be discovered directly using traditional association rules with discretization.
On the discovery of significant statistical quantitative rules
68 Citations2004Hong Zhang, Balaji Padmanabhan +1 more
This paper considers statistical quantitative rules (SQ rules) that are quantitative rules in which the RHS can be any statistic that is computed for the segment satisfying the LHS of the rule.
Data Mining and Knowledge DiscoveryOn the Complexity of Mining Quantitative Association Rules
54 Citations1998Jef Wijsen, Robert Meersman
This paper studies the computational complexity of mining quantitative association rules in large databases using LaSalle's inequality and Bayesian inference.
Mining rank-correlated sets of numerical attributes
46 Citations2006Toon Calders, Bart Goethals +1 more
Instead of the usual discretization methods, the use of rank based measures to score the similarity of sets of numerical attributes are proposed, based on extensions of Kendall's tau, and Spearman's Footrule and rho.
Lecture notes in computer scienceThe Lorenz Dominance Order as a Measure of Interestingness in KDD
3 Citations2002Robert J. Hilderman
This paper shows that the Lorenz dominance order can be used to rank the summaries prior to presentation to the domain expert, and represents an objective evaluation of their relative interestingness and provides thedomain expert with a starting point for further subjective evaluation of the summary.