More Web Proxy on the site http://driver.im/

Article

Large-scale RLSC learning without agony

Authors:

Kwong-Sak LeungAuthors Info & Claims

ICML '07: Proceedings of the 24th international conference on Machine learning

Pages 529 - 536

https://doi.org/10.1145/1273496.1273563

Published: 20 June 2007 Publication History

Abstract

The advances in kernel-based learning necessitate the study on solving a large-scale non-sparse positive definite linear system. To provide a deterministic approach, recent researches focus on designing fast matrix-vector multiplication techniques coupled with a conjugate gradient method. Instead of using the conjugate gradient method, our paper proposes to use a domain decomposition approach in solving such a linear system. Its convergence property and speed can be understood within von Neumann's alternating projection framework. We will report signi ficant and consistent improvements in convergence speed over the conjugate gradient method when the approach is applied to recent machine learning problems.

References

[1]

Barrett, R., Berry, M., Chan, T. F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., & van der Vorst, H. (1994). Templates for the solution of linear systems: Building blocks for iterative methods. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics.

[2]

Beatson, R., Light, W., & Billings, S. (2000). Fast solution of the radial basis function interpolation equations: Domain decomposition methods. SIAM J. Sci. Comput., 22, 1717--1740.

Digital Library

[3]

Faul, A., & Powell, M. (1999). Proof of convergence of an iterative technique for thin plate spline interpolation in two dimensions. Advances in Computational Mathematics, 11, 183--192.

[4]

Fine, S., & Scheinberg, K. (2001). Efficient svm training using low-rank kernel representations. Journal of Machine Learning Research, 2, 243--264.

Digital Library

[5]

Freitas, N. D., Wang, Y., Mahdaviani, M., & Lang, D. (2006). Fast Krylov methods for n-body learning. In Y. Weiss, B. Schöölkopf and J. Platt (Eds.), Advances in neural information processing systems 18, 251--258. Cambridge, MA: MIT Press.

[6]

Fung, G., & Mangasarian, O. (2001). Proximal support vector machine classifiers. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-01) (pp. 77--86). New York: ACM Press.

Digital Library

[7]

Golub, G. H., & van Loan, C. F. (1996). Matrix computations. John Hopkins Studies in the Mathematical Sciences. Baltimore, Maryland: Johns Hopkins University Press. Third edition.

[8]

Hastie, T., & Tibshirani, R. (1986). Generalized additive models. Statistical Science, 1, 297--318.

[9]

Kimeldorf, G., & Wahba, G. (1971). Some results on Tchebycheffian spline functions. J. Math. Anal. Appl., 33, 82--95.

[10]

Lee, Y.-J., & Mangasarian, O. (2001). Rsvm: Reduced support vector machines. First SIAM International Conference on Data Mining. Chicago.

[11]

Li, W., Lee, K.-H., & Leung, K.-S. (2007). Generalized regularized least-squares learning with predefined features in a Hilbert space. In B. Schölkopf, J. Platt and T. Hoffman (Eds.), Advances in neural information processing systems 19. Cambridge, MA: MIT Press.

[12]

Poggio, T., & Girosi, F. (1990). Regularization algorithms for learning that are equivalent to multilayer networks. Science, 247, 978--982.

[13]

Poggio, T., & Smale, S. (2003). The mathematics of learning: Dealing with data. Not. Am. Math. Soc, 50, 537--544.

[14]

Preparata, F. P., & Shamos, M. I. (1985). Computational geometry: An introduction. Springer.

Digital Library

[15]

Ratliff, N. D., & Bagnell, J. A. (2007). Kernel conjugate gradient for fast kernel machines. IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007 (pp. 1017--1022).

Digital Library

[16]

Rifkin, R. (2002). Everything old is new again: A fresh look at historical approaches in machine learning. Doctoral dissertation, Massachusetts Institute of Technology.

Digital Library

[17]

Saad, Y., & van der Vorst, H. A. (2000). Iterative solution of linear systems in the 20th century. Journal of Computational and Applied Mathematics, 123, 1--33. Numerical analysis 2000, Vol. III. Linear algebra.

Digital Library

[18]

Schaback, R., & Wendland, H. (2000). Numerical techniques based on radial basis functions. Curve and Surface Fitting (pp. 359--374). Nashville, TN: Vanderbilt University Press.

[19]

Shen, Y., Ng, A., & Seeger, M. (2006). Fast Gaussian process regression using kd-trees. In Y. Weiss, B. Schöölkopf and J. Platt (Eds.), Advances in neural information processing systems 18, 1227--1234. Cambridge, MA: MIT Press.

[20]

Smith, K., Solomon, D., & Wagner, S. (1977). Practical and mathematical aspects of the problem of reconstructing objects from radiographs. Bulletin of the American Mathematical Society, 1227--1270.

[21]

Smola, A. J., & Schöölkopf, B. (2000). Sparse greedy matrix approximation for machine learning. Proceedings of the Seventeenth International Conference on Machine Learning (pp. 911--918). Morgan Kaufmann.

Digital Library

[22]

Sun, X., & Pitsianis, N. P. (2001). A matrix version of the fast multipole method. SIAM Review, 43, 289--300.

Digital Library

[23]

Tikhonov, A., & Arsenin, V. (1977). Solutions of illposed problems. Winston and Sons.

[24]

von Neumann, J. (1955). Mathematical foundations of quantum mechanics. Princeton University Press.

[25]

Williams, C. K. I., & Rasmussen, C. E. (1996). Gaussian processes for regression. In D. S. Touretzky, M. C. Mozer and M. E. Hasselmo (Eds.), Advances in neural information processing systems, vol. 8. Cambridge, MA: MIT Press.

[26]

Williams, C. K. I., & Seeger, M. (2001). Using the Nyströöm method to speed up kernel machines. In T. K. Leen, T. G. Dietterich and V. Tresp (Eds.), Advances in neural information processing systems 13, 682--688. MIT Press.

[27]

Yang, C., Duraiswami, R., & Davis, L. (2005). Efficient kernel machines using the improved fast Gauss transform. In L. K. Saul, Y. Weiss and L. Bottou (Eds.), Advances in neural information processing systems 17, 1561--1568. Cambridge, MA: MIT Press.

Cited By

Chen HLi W(2015)An Empirical Study of Spectral Social Network Partition on GPGPU PlatformsProceedings of the 2015 Second International Conference on Soft Computing and Machine Intelligence (ISCMI)10.1109/ISCMI.2015.18(112-115)Online publication date: 23-Nov-2015
https://dl.acm.org/doi/10.1109/ISCMI.2015.18
Tan JLi WLi H(2014)Automated text categorization by generalized kernel machines2014 IEEE International Conference on Information and Automation (ICIA)10.1109/ICInfA.2014.6932685(376-381)Online publication date: Jul-2014
https://doi.org/10.1109/ICInfA.2014.6932685
Li W(2014)Early-Stopping Regularized Least-Squares ClassificationAdvances in Neural Networks – ISNN 201410.1007/978-3-319-12436-0_31(278-285)Online publication date: 19-Nov-2014
https://doi.org/10.1007/978-3-319-12436-0_31
Show More Cited By

Large-scale RLSC learning without agony
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms

Recommendations

Cuneiform: A Functional Language for Large-Scale Data Analysis
A new spectral conjugate gradient method for large-scale unconstrained optimization

The spectral conjugate gradient methods, with simple construction and nice numerical performance, are a kind of effective methods for solving large-scale unconstrained optimization problems. In this paper, based on quasi-Newton direction and quasi-...
Optimization of large-scale systems

Problems and techniques related to the difficulties of analyzing and synthesizing optimal controls for large scale systems are discussed. The intuitive ideas of decomposition and aggregation are described in mathematical terms along with various optimum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '07: Proceedings of the 24th international conference on Machine learning

June 2007

1233 pages

ISBN:9781595937933

DOI:10.1145/1273496

Editor:
Zoubin Ghahramani
University of Cambridge, United Kingdom

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Machine Learning Journal

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICML '07 & ILP '07

Sponsor:

ICML '07 & ILP '07: The 24th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 20 - 24, 2007

Oregon, Corvalis, USA

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
165
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen HLi W(2015)An Empirical Study of Spectral Social Network Partition on GPGPU PlatformsProceedings of the 2015 Second International Conference on Soft Computing and Machine Intelligence (ISCMI)10.1109/ISCMI.2015.18(112-115)Online publication date: 23-Nov-2015
https://dl.acm.org/doi/10.1109/ISCMI.2015.18
Tan JLi WLi H(2014)Automated text categorization by generalized kernel machines2014 IEEE International Conference on Information and Automation (ICIA)10.1109/ICInfA.2014.6932685(376-381)Online publication date: Jul-2014
https://doi.org/10.1109/ICInfA.2014.6932685
Li W(2014)Early-Stopping Regularized Least-Squares ClassificationAdvances in Neural Networks – ISNN 201410.1007/978-3-319-12436-0_31(278-285)Online publication date: 19-Nov-2014
https://doi.org/10.1007/978-3-319-12436-0_31
Li W(2014)Gaussian Process Learning: A Divide-and-Conquer ApproachAdvances in Neural Networks – ISNN 201410.1007/978-3-319-12436-0_29(262-269)Online publication date: 19-Nov-2014
https://doi.org/10.1007/978-3-319-12436-0_29
Sun PYao X(2010)Sparse approximation through boosting for learning large scale kernel machinesIEEE Transactions on Neural Networks10.1109/TNN.2010.204424421:6(883-894)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1109/TNN.2010.2044244
Chang FKao LKuo YLiu C(2010)Artificial neural networks for estimating regional arsenic concentrations in a blackfoot disease area in TaiwanJournal of Hydrology10.1016/j.jhydrol.2010.04.029388:1-2(65-76)Online publication date: Jun-2010
https://doi.org/10.1016/j.jhydrol.2010.04.029

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents