|
ABSTRACT
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented. The technique is applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions. The effective number of parameters is adjusted automatically to match the complexity of the problem. The solution is expressed as a linear combination of supporting patterns. These are the subset of training patterns that are closest to the decision boundary. Bounds on the generalization performance based on the leave-one-out method and the VC-dimension are given. Experimental results on optical character recognition problems demonstrate the good generalization obtained when compared with other learning algorithms.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
ABR64
|
M.A. Aizerman, E.M. Braverman, and L.I. Rozonoer. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821-837, 1964.
|
| |
BH89
|
|
| |
BL88
|
D.S. Broomhead and D. Lowe. Multivariate functional interpolation and adaptive networks. Complex Systems, 2:321 - 355, 1988.
|
| |
CBD+90
|
Y. Le Cun , B. Boser , J. S. Denker , R. E. Howard , W. Habbard , L. D. Jackel , D. Henderson, Handwritten digit recognition with a back-propagation network, Advances in neural information processing systems 2, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
|
| |
CH53
|
R. Courant and D. Hilbert. Methods of mathematical physics. Interscience, New York, 1953.
|
| |
DH73
|
R.O. Duda and P.E. Hart. Pattern Classification And Scene Analysis. Wiley and Son, 1973.
|
| |
GBD92
|
|
| |
GPP+89
|
I. Guyon, I. Poujaud, L. Personnaz, G. Dreyfus, J. Denker, and Y. LeCun. Comparing different neural network architectures for classifying handwritten digits. In Proc. Int. Joint Conf. Neural Networks. Int. Joint Conference on Neural Networks, 1989.
|
| |
GVB+92
|
Isabelle Guyon, Vladimir Vapnik, Bernhard Boser, Leon Bottou, and Sara Solla. Structural risk minimization for character recognition. In David S. Touretzky, editor, Neural Information Processing Systems, volume 4. Morgan Kaufmann Publishers, San Mateo, CA, 1992. To appear.
|
| |
HLW88
|
David Haussler, Nick Littlestone, and Manfred Warmuth. Predicting 0,1-functions on randomly drawn points. In Proceedings of the 29th Annual Symposium on the Foundations of Computer Science, pages 100-109. IEEE, 1988.
|
| |
KM87
|
W. Krauth and M. Mezard. Learning algorithms with optimal stability in neural networks. J. Phys. A: Math. gen., 20:L745, 1987.
|
| |
Loo72
|
F.A. Lootsma, editor. Numerical Methods for Non-linear Optimization. Academic Press, London, 1972.
|
| |
Lue84
|
David Luenberger. Linear and Nonlinear Programming. Addison-Wesley, 1984.
|
| |
Mac92
|
D. MacKay. A practical bayesian framework for backprop networks. In David S. Touretzky, editor, Neural Information Processing Systems, volume 4. Morgan Kaufmann Publishers, San Mateo, CA, 1992. To appear.
|
| |
MD89
|
J. Moody and C. Darken. Fast learning in networks of locally tuned processing units. Neural Computation, i (2):281 - 294, 1989.
|
| |
MGB+92
|
N. Matte, I. Guyon, L. Bottou, J. Denker, and V. Vapnik. Computer-aided cleaning of large databases for character recognition. In Digest ICPR. ICPR, Amsterdam, August 1992.
|
| |
Moo92
|
J. Moody. Generalization, weight decay, and architecture selection for nonlinear learning systems. In David S. Touretzky, editor, Neural Information Processing Systems, volume 4. Morgan Kaufrnann Publishers, San Mateo, CA, 1992. To appear.
|
| |
NY83
|
A.S. Nemirovsky and D. Do Yudin. Problem Complexzty and Method Efficiency in Optimization. Wiley, New York, 1983.
|
| |
Omo91
|
|
| |
PG90
|
T. Poggio and F. Girosi. Regularization algorithms for learning that are equivalent to nmltilayer networks. Science, 247:978 - 982, February 1990.
|
| |
Pog75
|
T. Poggio. On optimal nonlinear associative recall. Biol. Cybernetics, Vol. 19:201-209, 1975.
|
| |
Ros62
|
F. Rosenblatt. Princzples of neurodynamics. Spartan Books, New York, 1962.
|
| |
SLD92
|
P. Simard, Y. LeCun, and J. Denker. Tangent prop--a formalism for specifying selected invariances in an adaptive network. In David S. Touretzky, editor, Neural Information Processing Systems, volume 4. Morgan Kaufmann Publishers, San Mateo, CA, 1992. To appear.
|
| |
TLS89
|
N. Tishby, E. Levin, and S. A. Solla. Consistent inference of probabilities in layered networks: Predictions and generalization. In Proceedings of the International Joint Conference on Neural Networks, Washington DC, 1989.
|
| |
Vap82
|
|
| |
VC74
|
V.N. Vapnik and A.Ya. Chervonenkis. The theory of pattern recognition. Nauka, Moscow, 1974.
|
CITED BY 276
|
|
Wenyuan Dai , Gui-Rong Xue , Qiang Yang , Yong Yu, Co-clustering based classification for out-of-domain documents, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
Ying Guo , Peter L. Bartlett , John Shawe-Taylor , Robert C. Williamson, Covering numbers for support vector machines, Proceedings of the twelfth annual conference on Computational learning theory, p.267-277, July 07-09, 1999, Santa Cruz, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
Wee Sun Lee , Peter L. Bartlett , Robert C. Williamson, Lower bounds on the VC-dimension of smoothly parametrized function classes, Proceedings of the seventh annual conference on Computational learning theory, p.362-367, July 12-15, 1994, New Brunswick, New Jersey, United States
|
|
|
Yi Li , Philip M. Long , Aravind Srinivasan, Improved bounds on the sample complexity of learning, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.309-318, January 09-11, 2000, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sebastian Mika , Gunnar Rätsch , Jason Weston , Bernhard Schölkopf , Alex Smola , Klaus-Robert Müller, Constructing Descriptive and Discriminative Nonlinear Features: Rayleigh Coefficients in Kernel Feature Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.623-633, May 2003
|
|
|
Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Shawe-Taylor , Peter L. Bartlett , Robert C. Williamson , Martin Anthony, A framework for structural risk minimisation, Proceedings of the ninth annual conference on Computational learning theory, p.68-76, June 28-July 01, 1996, Desenzano del Garda, Italy
|
|
|
|
|
|
|
|
|
|
|
|
Tony Van Gestel , Johan A. K. Suykens , Bart Baesens , Stijn Viaene , Jan Vanthienen , Guido Dedene , Bart De Moor , Joos Vandewalle, Benchmarking Least Squares Support Vector Machine Classifiers, Machine Learning, v.54 n.1, p.5-32, January 2004
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dekai Wu , Grace Ngai , Marine Carpuat, A stacked, voted, stacked model for named entity recognition, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.200-203, May 31, 2003, Edmonton, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mike Brzozowski , Kendra Carattini , Scott R. Klemmer , Patrick Mihelich , Jiang Hu , Andrew Y. Ng, groupTime: preference based group scheduling, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jason Weston , Ronan Collobert , Fabian Sinz , Léon Bottou , Vladimir Vapnik, Inference with the Universum, Proceedings of the 23rd international conference on Machine learning, p.1009-1016, June 25-29, 2006, Pittsburgh, Pennsylvania
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yih-Lon Lin , Wei-Chih Teng , Jyh-Horng Jeng , Jer-Guang Hsieh, Characterization of canonical robust template values for a class of uncoupled CNNs implementing linearly separable Boolean functions, Proceedings of the 9th WSEAS International Conference on Computers, p.1-5, July 14-16, 2005, Athens, Greece
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hu Chengwen , Zhao Yannan , Wang Jiaxin , Yang Zehong, An improved method for the character recognition based on SVM, Proceedings of the 24th IASTED international conference on Artificial intelligence and applications, p.457-461, February 13-16, 2006, Innsbruck, Austria
|
|
|
|
|
|
|
|
|
|
|
|
Rutger Rienks , Dong Zhang , Daniel Gatica-Perez , Wilfried Post, Detection and application of influence rankings in small group meetings, Proceedings of the 8th international conference on Multimodal interfaces, November 02-04, 2006, Banff, Alberta, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wenyuan Dai , Qiang Yang , Gui-Rong Xue , Yong Yu, Boosting for transfer learning, Proceedings of the 24th international conference on Machine learning, p.193-200, June 20-24, 2007, Corvalis, Oregon
|
|
|
Isabelle Guyon , Jiwen Li , Theodor Mader , Patrick A. Pletscher , Georg Schneider , Markus Uhr, Competitive baseline methods set new standards for the NIPS 2003 feature selection benchmark, Pattern Recognition Letters, v.28 n.12, p.1438-1444, September, 2007
|
|
|
|
|
|
Arthur Tenenhaus , Alain Giron , Emmanuel Viennet , Michel Béra , Gilbert Saporta , Bernard Fertil, Kernel logistic PLS: A tool for supervised nonlinear dimensionality reduction and binary classification, Computational Statistics & Data Analysis, v.51 n.9, p.4083-4100, May, 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dawei Song , Raymond Y. K. Lau , Peter D. Bruza , Kam-Fai Wong , Ding-Yi Chen, An intelligent information agent for document title classification and filtering in document-intensive domains, Decision Support Systems, v.44 n.1, p.251-265, November, 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hichem Sahbi , Jean-Yves Audibert , Jaonary Rabarisoa , Renaud Keriven, Robust matching and recognition using context-dependent kernels, Proceedings of the 25th international conference on Machine learning, p.856-863, July 05-09, 2008, Helsinki, Finland
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xiao Ling , Gui-Rong Xue , Wenyuan Dai , Yun Jiang , Qiang Yang , Yong Yu, Can chinese web pages be classified with english data source?, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
|
|
|
Victor Zordan , Adriano Macchietto , Jose Medina , Marc Soriano , Chun-Chih Wu, Interactive dynamic response for games, Proceedings of the 2007 ACM SIGGRAPH symposium on Video games, August 04-05, 2007, San Diego, California
|
|
|
|
|
|
|
|
|
David A. Elizondo , Ralph Birkenhead , Mario Góngora , Eric Taillard , Patrick Luyima, Analysis and test of efficient methods for building recursive deterministic perceptron neural networks, Neural Networks, v.20 n.10, p.1095-1108, December, 2007
|
|
|
|
|
|
Victor Zordan , Adriano Macchietto , Jose Medin , Marc Soriano , Chun-Chih Wu , Ronald Metoyer , Robert Rose, Anticipation from example, Proceedings of the 2007 ACM symposium on Virtual reality software and technology, November 05-07, 2007, Newport Beach, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alfred Fuller , Robert Zawadzki , Stacey Choi , David Wiley , John Werner , Bernd Hamann, Segmentation of Three-dimensional Retinal Image Data, IEEE Transactions on Visualization and Computer Graphics, v.13 n.6, p.1719-1726, November 2007
|
|
|
Mateja Verlic , Gregor Stiglic , Peter Kokol, Identifying psycho-social fingerprints in medical and engineering documents, Proceedings of the 7th WSEAS International Conference on Artificial intelligence, knowledge engineering and data bases, p.62-66, February 20-22, 2008, Cambridge, UK
|
|
|
I. C. Constantin , A. Epureanu , V. Paunoiu , G. Brabie , V. Marinescu , F. B. Marin, Springback adaptive-predictive control, Proceedings of the 10th WSEAS International Conference on Automatic Control, Modelling & Simulation, p.326-331, May 27-30, 2008, Istanbul, Turkey
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S. Sathiya Keerthi , S. Sundararajan , Kai-Wei Chang , Cho-Jui Hsieh , Chih-Jen Lin, A sequential dual method for large scale multi-class linear svms, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
|
|
|
Cho-Jui Hsieh , Kai-Wei Chang , Chih-Jen Lin , S. Sathiya Keerthi , S. Sundararajan, A dual coordinate descent method for large-scale linear SVM, Proceedings of the 25th international conference on Machine learning, p.408-415, July 05-09, 2008, Helsinki, Finland
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Youngjoo Lee , Joon Beom Seo , June Goo Lee , Song Soo Kim , Namkug Kim , Suk Ho Kang, Performance testing of several classifiers for differentiating obstructive lung diseases based on texture analysis at high-resolution computerized tomography (HRCT), Computer Methods and Programs in Biomedicine, v.93 n.2, p.206-215, February, 2009
|
|
|
|
|
|
Wenyuan Dai , Gui-Rong Xue , Qiang Yang , Yong Yu, Transferring naive bayes classifiers for text classification, Proceedings of the 22nd national conference on Artificial intelligence, p.540-545, July 22-26, 2007, Vancouver, British Columbia, Canada
|
|
|
Wenyuan Dai , Ou Jin , Gui-Rong Xue , Qiang Yang , Yong Yu, EigenTransfer: a unified framework for transfer learning, Proceedings of the 26th Annual International Conference on Machine Learning, p.193-200, June 14-18, 2009, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
Matthieu Kowalski , Marie Szafranski , Liva Ralaivola, Multiple indefinite kernel learning with mixed norm regularization, Proceedings of the 26th Annual International Conference on Machine Learning, p.545-552, June 14-18, 2009, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Brett Poulin , Roman Eisner , Duane Szafron , Paul Lu , Russ Greiner , D. S. Wishart , Alona Fyshe , Brandon Pearcy , Cam MacDonell , John Anvik, Visual explanation of evidence in additive classifiers, Proceedings of the 18th conference on Innovative applications of artificial intelligence, p.1822-1829, July 16-20, 2006, Boston, Massachusetts
|
|
|
|
|
|
|
|
|
Pranam Kolari , Akshay Java , Tim Finin , Tim Oates , Anupam Joshi, Detecting spam blogs: a machine learning approach, proceedings of the 21st national conference on Artificial intelligence, p.1351-1356, July 16-20, 2006, Boston, Massachusetts
|
|
|
|
|
|
Simon Durrant , David R. Hardoon , Andre Brechmann , John Shawe-Taylor , Eduardo R. Miranda , Henning Scheich, GLM and SVM analyses of neural response to tonal and atonal stimuli: new techniques and a comparison, Connection Science, v.21 n.2-3, p.161-175, June 2009
|
|
|
|
|
|
Zhisong Wang , Alexander Maier , Nikos K. Logothetis , Hualou Liang, Single-trial classification of bistable perception by integrating empirical mode decomposition, clustering, and support vector machine, EURASIP Journal on Advances in Signal Processing, 2008, p.1-8, January 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
M. A. Sotelo , J. Nuevo , D. Fernandez , I. Parra , L. M. Bergasa , M. Ocana , R. Flores, SVM-based obstacles recognition for road vehicle applications, Proceedings of the 19th international joint conference on Artificial intelligence, p.1740-1741, July 30-August 05, 2005, Edinburgh, Scotland
|
|